יום ראשון, 5 בפברואר 2012

בייסיאניזם: כלל הכפל



[רשומה זו היא חלק מסדרה על תורת הידיעה הבייסיאנית; ראה אינדקס כאן.]

מקודם הסקנו "כלל חיבור" בדרך הבאה: שקלנו ראשית פונקצית חיבור כללית (F[...]=(A+B|X , אז הגבלנו את עצמנו לשני משתנים, ואז השתמשנו באסוציאטיביות (A+B)+C=A+(B+C) כדי להוכיח שניתן להגדיר-מחדש סבירות כך שהסכום יהיה קל לחישוב.

בפוסט זה נרצה לעשות אותו הדבר עבור כפל. אנו נסתכל בפונקציה אוניברסלית (G[...]=(AB|X, נגביל אותה לשני משתנים, ואז נשתמש באסוציאטיביות (AB)C=A(BC) כדי להראות שניתן להגדיר-מחדש את הסבירות כך שכלל הכפל יהיה פשוט. למרבה הצער, אנו נאלץ להשתמש בטיעון די טרחני כדי להגביל את עצמנו לשני משתנים.

נתחיל, אם כך, בפונקציה הכללית של הכפל (משפט 3.3),
(AB|X)=G[(A|X),(B|X),(A|B,X),(B|A,X)]
אנו רשאים בשלב זה להשתמש בהגדרה-מחדש (f(x שביצענו עבור כלל החיבור. מאחר ש-"G" אינה מוגדרת עדיין בדיוק, היא תהיה תלויה באותן סבירויות (מוגדרות-מחדש) תחת הגדרה-מחדש זו.
f(AB|X)=G[f(A|X),f(B|X),f(A|B,X),f(B|A,X)]

שורה זו אינה אומרת ש-G באמת תלויה בכל אותם משתנים. אלו הם רק המשתנים שהיא עלולה להיות תלויה בהם. הגיע הזמן להסתכל יותר טוב על אילו צירופים של משתנים באים בחשבון. מאחר שיש ארבע סבירויות אפשריות, יש 15 צירופים שונים שהפונקציה G המפורשת יכולה להיות תלויה בהם. אנו ננתח אותם אחד לאחד, כדי להראות שבעצם רק צירוף אחד, בעל שני משתנים, יכול לשמש עבור הצורה הכללית של G.

1. f(AB|X)=G1[(A|X)]
זו לא יכולה להיות הצורה הכללית בגלל שהיא לא לוקחת את הערך של B בחשבון. נניח למשל ש-A היא טאוטולוגיה (כלומר, תמיד נכונה). אז (f(AB|X)=f(B|X, בעוד G1 מחזירה ערך קבוע שאינו תלוי בזה של (B|X).

2. f(AB|X)=G2[(B|X)]
מאחר ש- AB=BA, אנו יכולים על ידי שינוי (שמות ה-)משתנים להקביל את האפשרות הזו למקרה (1). מאחר ש-G1 אינה קבילה, גם G2 אינה קבילה.

3. f(AB|X)=G3[(A|B,X)]
זו לא יכולה להיות הצורה הכללית מאחר שהיא לא לוקחת בחשבון את ערך-האמת של B. ניתן לראות זאת על ידי אותו טיעון כמו במקרה (1).

4. f(AB|X)=G4[(B|A,X)]
מאחר ש- AB=BA אנו יכולים על ידי שינוי משתנים להקביל את האפשרות הזו למקרה 3. מאחר ש G3 לא קבילה, גם G4 אינה קבילה.

5. f(AB|X)=G5[(A|X),(B|X)]
זו לא יכולה להיות הצורה הכללית בגלל שהיא לא לוקחת בחשבון את היחסים בין שתי הטענות. זה המקרה שקשה ביותר לראות אינטואיטיבית, מאחר שצורה זו כן בסדר עבור מקרי הקצה של וודאות או שלילה מוחלטת, שאנו רגילים לחשוב בעזרתם. כדי לראות את הבעייתיות שב-G5 אנו נצטרך לשקול סבירות עם ערך ביניים*. נניח למשל שהסבירות של A ושל שלילתה זהות, (f(A|X)=f(A|X. עתה שקול את המקרה B=A:
f(AB|X)=f(F|X)=G5[f(A|X),f(B|X)]=G5[f(A|X),f(A|X)]=f(AA|X)=f(A|X)
אך זוהי סתירה, מאחר ש (f(F|X)≠f(F|X)=f(T|X, ולכן (f(A|X)≠f(A|X. השימוש ב-G5 הוא לפיכך לא עקבי ואינו קביל.

6. f(AB|X)=G6[(A|X),(A|B,X)]
זו לא יכולה הצורה הכללית מאחר שהיא לא לוקחת את הערך של B בחשבון. אותו טיעון כמו במקרה (1) מספיק כדי לדחות אותה.

7. f(AB|X)=G7[(A|X),(B|A,X)]
אין שום טיעון נגד G7, זוהי הצורה הנכונה.

8. f(AB|X)=G8[(B|X),(A|B,X)]
מאחר ש AB=BA, אנו יכולים על ידי שינוי משתנים להפוך את המקרה הזה למקרה (7). מאחר ש G7 נכונה, גם G8 היא צורה קבילה ונכונה.

9. f(AB|X)=G9[(B|X),(B|A,X)]
זו לא יכולה להיות הצורה הכללית מאחר שהיא לא לוקחת בחשבון את ערך הסבירות של A. למשל, שקול את המקרה בו B היא טאוטולוגיה. אז (f(AB|X)=f(A|X, בעודG9 מחזירה ערך קבוע שאינו תלוי ב-(A|X).

10. f(AB|X)=G10[(A|B,X),(B|A,X)]
זו לא יכולה להיות הצורה הכללית מאחר שהיא לא לוקחת בחשבון את ערכי הסבירות של שתי הטענות בנפרד. למשל, שקול את המקרה בו B=A. אז (f(AB|X)=f(A|X, בעוד G10 מחזירה ערך קבוע שאינו תלוי ב-(A|X).

11. f(AB|X)=G11[(A|X),(B|X),(A|B,X)]
זו לא יכולה להיות הצורה הכללית בגלל שניתן לצמצם אותה לצורות הקודמות. (זה אולי החלק הסבוך ביותר בטיעון.) שקול את ההכפלה של שלוש טענות, שניתן לפרק אסוציאטיבית. אם G11 היא הצורה הנכונה, אנו מקבלים כי
f(ABC|X)=f((AB)C|X)=G11[(AB|X),(C|X),(AB|C,X)]=G11[G11[(A|X),(B|X),(A|B,X)],(C|X),(AB|C,X)]
f(ABC|X)=f(A(BC)|X)=G11[(A|X),(BC|X),(A|BC,X)]=G11[(A|X),G11[(B|X),(C|X),(B|C,X)],(A|BC,X)]
נשווה את שתי הצורות, ונקבל
G11[G11[(A|X),(B|X),(A|B,X)],(C|X),(AB|C,X)]=G11[(A|X),G11[(B|X),(C|X),(B|C,X)],(A|BC,X)]
כדי לכתוב זאת בצורה פשוטה יותר, נגדיר (x=(A|X), y=(B|X), c=(C|X), u=(A|B,X), v=(AB|C), w=(B|C,X, וגם (z=(A|BC,X. תחת הגדרות אלו, קיבלנו כי
G11[G11[x,y,u],z,v]=G11[x,G11[y,z,w],z]
ניקח את הנגזרת החלקית ביחס ל-u**. נסמן G11[]1 כנגזרת של המשתנה הראשון של הפונקציה, ונוכל לרשום
G11[G11[x,y,u],z,v]1 G11[x,y,u]3 = 0
ניתן לקיים את המשוואה הזו, עבור כל שני משתנים, רק בשתי דרכים. או ש G11[]1=0, כך ש-G11 לא תלויה במשתנה הראשון והיא לכן בעצם G8; או ש G11[]3=0 כך ש G11 לא תלויה במשתנה השלישי והיא בעצם G5. כך או כך, G11 זהה לצורות הקודמות והיא לפיכך לא קבילה.

12. f(AB|X)=G12[(A|X),(B|X),(B|A,X)]
מאחר ש AB=BA ניתן על ידי שינוי משתנים להפוך מקרה זה למקרה (11). מאחר ש-G11 אינה קבילה, גם G12 אינה קבילה.

13. f(AB|X)=G13[(A|X),(A|B,X),(B|A,X)]
ניתן להראות שצורה זו אינה קבילה בדרך דומה לזו של מקרה (11). רשומה זו ארוכה מספיק בלי הוכחה זו.

14. f(AB|X)=G14[(B|X),(A|B,X),(B|A,X)]
ניתן על ידי שינוי משתנים להפוך מקרה זה למקרה (13), כך שצורה זו גם אינה קבילה.

15. f(AB|X)=G15[(A|X),(B|X),(A|B,X),(B|A,X)]
ניתן להוכיח שצורה זו אינה קבילה בדומה להוכחה של מקרה (11).

אנו יכולים לפיכך להסיק שהצורה הכללית הנכונה היחידה האפשרית היא G7,
f(AB|X)=G[f(A|X),f(B|A,X)]
או מקבילתה G8.

לאחר שמצאנו את הצורה שתלויה רק בשני משתנים, אנחנו יכולים להמשיך ולשקול את ההכפלה שלוש טענות בעזרת צורת זו וכלל האסוציאטיביות (AB)C=A(BC) .
f(ABC|X)=f((AB)C|X)=G[f(AB|X),f(C|AB,X)]=G[G[f(A|X),f(B|A,X)],f(C|AB,X)]
f(ABC|X)=f(A(BC)|X)=G[f(A|X),f(BC|A,X)]=G[f(A|X),G[f(B|A,X),f(C|AB,X)]]
נשווה בין שתי הצורות, ונקבל
G[G[f(A|X),f(B|A,X)],f(C|AB,X)]=G[f(A|X),G[f(B|A,X),f(C|AB,X)]]
נגדיר (x=(A|X), y=(B|A,X), z=(C|AB,X, ונקבל
G[G[x,y],z]=G[x,G[y,z]]
פתרון למשווה זו היא הפונקציה
G[x,y]=g-1(g(x)g(y))
או בצורה שימושית יותר למטרותינו
g(G[x,y])=g(x)g(y)
g(f(AB|X))=g(f(A|X))g(f(B|A,X))

תחת ההגדרה מחדש g, קל מאוד לחשב את הכפל ("A וגם B", או AB) - יש פשוט להכפיל את הסבירויות. הפונקציה( g(x עדיין שרירותית בשלב זה. נוכל פשוט לקחת אותה להיות הזהות, g(x)=x. זה אומר שכלל הכפל הוא פשוט (גם) באותה מידת סבירות שהגדרנו עבור כלל החיבור, כך שהן כלל החיבור והן כלל הכפל פשוטים.
f(A+B|X)=f(A|X)+f(B|X)-f(AB|X)
f(AB|X)=f(A|X)f(B|A,X)

נשאר רק עוד מעט מאוד עבודה כדי להפוך את הסבירויות להסתברויות.

* רוב הרשומה (והוכחתי את משפט קוקס בכלל) מבוססת על עבודתה של קאטיצ'ה, אך טיעון זה נלקח מוואן-הורן.

** מצטער, אבל לא מצאתי טיעון טוב ללא נגזרות. מי שלא יודע מהן - זה בעצם לבדוק איך הפונקציה מגיבה לשינוי של ערך של משתנה שלה. גזירה (חלקית) לפי המשתנה הראשון אומרת כמה ערך הפונקציה משתנה כשמשנים את המשתנה הראשון.