טופולוגיה של רשתות, כלל השרשרת וסיבוכיות פרמטרית של CPT
הסמנטיקה המקומית של רשתות בייסיאניות (DAG), פירוק התפלגות משותפת מלאה באמצעות כלל השרשרת, וספירת פרמטרים חופשיים במעבר ממשתנים בינאריים למשתנים רב-ערכיים תוך התמודדות עם קללת הממדיות (Curse of Dimensionality).
להבין את האינטואיציה שמאחורי הקלעים: מדוע רשתות בייסיאניות הן פריצת הדרך הגדולה בבינה מלאכותית?
ברוכים הבאים לפרק 9! בפרק 8 גילינו את כוחה של ההסתברות לכמת אי-ודאות. אולם שם נתקלנו גם בחומה בצורה: טבלת התפלגות משותפת מלאה של 100 משתנים בינאריים דורשת לשמור $2^{100}-1 \approx 1.26 \times 10^{30}$ מספרים — יותר ממספר האטומים בכדור הארץ! שום מחשב אינו מסוגל לאחסן זאת, ושום מאגר נתונים אינו מסוגל לאמוד ערכים אלו. פריצת הדרך ההיסטורית של ג'ודאה פרל (חתן פרס טיורינג) הייתה ההבנה שהעולם אינו "הכל תלוי בהכל": תופעות בעולם האמיתי מושפעות ישירות רק ממספר זעיר של גורמים מקומיים (הורים). גרף מכוון ללא מעגלים (DAG) מאפשר לנו "לפרק" את ההתפלגות המפלצתית למכפלה של טבלאות CPT מקומיות וקטנות. ביחידה זו נלמד כיצד כלל השרשרת, תכונת מרקוב המקומית ומודלים פרמטריים כמו Noisy-OR מכניעים את קללת הממדיות והופכים את הבלתי-אפשרי למעשי.
💡 אינטואיציה בגובה העיניים: שיחת קבוצת וואטסאפ מול לחישת שרשרת שכנים
תארו לעצמכם עיר עם 1,000 תושבים. אם כל תושב היה חייב לדעת את המצב האישי של כל 999 האחרים לפני שהוא מחליט האם לקחת מטרייה (טבלה משותפת מלאה), המוח שלו היה קורס מעודף מידע. במציאות, כל אדם מביט רק בשני דברים: האם השמיים מעל ביתו מעוננים, והאם השכן שיוצא מהבניין פתח מטרייה (אלו הם "ההורים" שלו ברשת). מרגע שהוא יודע את מצבם, כל המידע על מה שקורה בקצה השני של העיר הופך לבלתי-רלוונטי (אי-תלות מותנית). רשת בייסיאנית עושה בדיוק את זה: היא חוסכת מיליארדי שיחות סרק ומאפשרת לסוכן AI לחשב הסתברויות מורכבות תוך התבוננות בקומץ השכנים הקרובים ביותר בלבד.
📊 תרשים 9.1: התפוצצות פרמטרית בטבלה מלאה לעומת חיסכון אקספוננציאלי ב-DAG
השוואה כמותית בין שמירת $2^n-1$ מצבים אטומיים לבין פירוק מקומי מבוסס תכונת מרקוב
1. הסמנטיקה המקומית וכלל השרשרת (Chain Rule)
כיצד גרף מכוון חסר מעגלים (DAG) מקודד התפלגות משותפת מלאה בצורה קומפקטית?
רשת בייסיאנית (Bayesian Network) היא מודל גרפי הסתברותי המוגדר על ידי גרף מכוון חסר מעגלים (DAG), שבו כל צומת מייצג משתנה מקרי וכל קשת מייצגת תלות ישירה (לרוב בעלת משמעות סיבתית).
כל צומת $X_i$ ברשת בלתי-תלוי באופן מותנה בכל שאר הצמתים שאינם צאצאיו (Non-Descendants), בהינתן קבוצת הוריו הישירים בלבד: $$X_i \perp \text{NonDescendants}(X_i) \mid \text{Parents}(X_i)$$
תכונה יסודית זו מאפשרת לנו להפעיל את כלל השרשרת בהסתברות ולפרק את ההתפלגות המשותפת המלאה של $n$ משתנים למכפלה של התפלגויות מותנות מקומיות: $$P(X_1, X_2, \dots, X_n) = \prod_{i=1}^n P(X_i \mid \text{Parents}(X_i))$$
נתונה רשת בעלת חמישה משתנים: $A, S, H, E, C$. מבנה הקשתות בגרף הוא: $A, S, H$ הם שורשים חסרי הורים; $E$ מקבל קשתות מ-$A, S, H$; ו-$C$ מקבל קשתות מ-$E$ ומ-$H$.
רשמו את הביטוי להסתברות המשותפת של האירוע $P(A, \neg S, H, E, \neg C)$.
✓ פירוק מדויק לפי הורי כל צומת ברשת!
האם הטענה $P(A, \neg C, E) = P(A)P(\neg C)P(E)$ נכונה תמיד ברשת זו?
שוויון זה מתקיים אך ורק אם $A, \neg C, E$ בלתי תלויים שולית. בפועל, קיים קשר סיבתי ישיר $A \to E$ וקשר ישיר $E \to C$. המשתנים תלויים זה בזה באופן מובהק.
2. ספירת פרמטרים חופשיים (Parameter Counting) וקללת הממדיות
חישוב גודל ה-CPT עבור משתנים בינאריים מול משתנים רב-ערכיים (Non-Boolean)
בכל צומת ברשת נשמרת טבלת הסתברות מותנית (CPT). מכיוון שסכום ההסתברויות עבור כל השורות בהתפלגות מותנית מסתכם ל-1 ($\sum P(X=x \mid \dots) = 1$), הערך האחרון נקבע אוטומטית כמשלים, ולכן מספר הערכים החופשיים שנדרש לאחסן וללמוד עבור צומת בעל $d$ ערכים הוא $d - 1$.
עבור צומת $X$ בעל מרחב מצבים בגודל $d$, שלו $k$ הורים בעלי תחומי ערכים $d_{p1}, d_{p2}, \dots, d_{pk}$: $$\text{Free Parameters} = (d - 1) \times \prod_{i=1}^k d_{pi}$$
- • $A$ (בינארי, 0 הורים): $2-1$= 1
- • $S$ (בינארי, 0 הורים): $2-1$= 1
- • $H$ (בינארי, 0 הורים): $2-1$= 1
- • $E$ (הורים: $A, S, H$): $(2-1) \times 2^3$= 8
- • $C$ (הורים: $E, H$): $(2-1) \times 2^2$= 4
- • $A$ ($d=5$, 0 הורים): $5-1$= 4
- • $S$ (בינארי, 0 הורים): $2-1$= 1
- • $H$ (בינארי, 0 הורים): $2-1$= 1
- • $E$ (הורים: $A(5), S(2), H(2)$): $(5-1) \times (5 \times 2 \times 2)$= 4 × 20 = 80!
- • $C$ (הורים: $E(5), H(2)$): $(2-1) \times (5 \times 2)$= 1 × 10 = 10
לעיתים מופיע חישוב שגוי של 90 פרמטרים במקום 96 (חישוב $4 + 1 + 1 + 80 + 4 = 90$). הטעות נובעת מהשמטת השפעת המשתנה $E$ ($5$ ערכים) על $C$: מכיוון של-$C$ יש הורים $E(5)$ ו-$H(2)$, מספר שילובי ההורים הוא $5 \times 2 = 10$, ולכן נדרשים $10 \times 1 = 10$ ערכים עבור $C$ ולא 4. החישוב האקדמי המדויק והנכון הוא **96 ערכים חופשיים**.
3. ייצוגים פרמטריים קומפקטיים: מודל Noisy-OR ו-Leaky Noisy-OR
כיצד לצמצם את סיבוכיות ה-CPT מגידול אקספוננציאלי לגידול ליניארי $O(k)$?
כאשר לצומת יש מספר רב של הורים ($k$), טבלת CPT מלאה דורשת $2^k$ פרמטרים. עבור $k=30$ הורים, הטבלה תכיל מעל מיליארד ערכים! הפתרון המקובל הוא מודל **Noisy-OR**, המניח אי-תלות בהשפעת הגרימה הסיבתית בין ההורים.
לכל הורה $X_i$ מוגדרת הסתברות עיכוב $q_i = P(\neg Y \mid X_i, \neg \text{others})$. האפקט $Y$ לא יתרחש אם ורק אם כל ההורים הפעילים כשלו בגירוי שלו:
כולל פרמטר "דלף" (Leak Parameter, $q_0$) המייצג את ההסתברות שהאפקט יתרחש באופן ספונטני עקב גורמי רקע נסתרים שאינם ממודלים ברשת:
| סוג ייצוג צומת בייסיאני | סיבוכיות מקום ($k$ הורים בינאריים) | יתרונות מרכזיים | חסרונות ומגבלות |
|---|---|---|---|
| טבלת CPT מלאה | $2^k$ (אקספוננציאלי) | ייצוג מדויק ושלם של כל סוגי התלויות והסינרגיה | צמיחה מעריכית, סכנת Overfitting, קושי באיסוף מידע |
| Noisy-OR | $k$ (ליניארי) | חיסכון עצום בזיכרון, אינטואיטיבי להגדרה ממומחים | מניח אי-תלות בגרימה, לא מתאים לשילובים סינרגטיים |
| Leaky Noisy-OR | $k + 1$ (ליניארי) | כולל גורמי רקע לא ידועים ומונע חלוקה באפס | דורש כיול מקדים של פרמטר הדלף (Leak) |
סימולציה 9.1: מעבדת סיבוכיות CPT וקללת הממדיות
הסקה מדויקת, אבחון רפואי ותופעת ההסבר החלופי (Explaining Away)
ניתוח מעמיק של מערכת אבחון רפואית רב-סיבתית, חישובי דחיקה לשוליים (Marginalization), הפעלת חוק בייס תחת ראיות מורכבות, והבנת הדינמיקה הפסיכולוגית-מתמטית של הסבר חלופי במבנה התכנסות (V-Structure).
להבין את האינטואיציה שמאחורי הקלעים: הקסם המתמטי של Explaining Away
ביחידה זו נצלול לאחת התופעות המרתקות ביותר בחשיבה האנושית ובבינה מלאכותית: תופעת ההסבר החלופי (Explaining Away). במבנה שבו שני גורמים עצמאיים לחלוטין מובילים לאותה תוצאה משותפת ($A \to S \leftarrow B$), הגורמים אינם משפיעים זה על זה בעולם הרגיל: ידיעה שחטפת קלקול קיבה אינה משנה את הסיכוי שיש לך שפעת. אולם, ברגע שהתוצאה המשותפת נצפית (אתה מקיא וחולה), נפתח מסלול תלות אקטיבי בין שתי הסיבות! אם כעת תגלה שאכלת סושי מקולקל אתמול, ההסתברות שיש לך שפעת צונחת מיידית. הסושי "הסביר" את המחלה, ואין עוד צורך להניח שגם לקית בשפעת. נלמד כיצד למדל תחרות זו בעזרת חוק בייס וטבלאות CPT.
💡 אינטואיציה בגובה העיניים: אזעקת הרכב והחתול שקפץ על מכסה המנוע
אתם יושבים בסלון ולפתע שומעים את אזעקת הרכב שלכם צופרת ברחוב. יש שני הסברים אפשריים: רעידת אדמה קלה או ניסיון פריצה. בהתחלה, שתי האפשרויות עולות בסבירותן. אתם רצים לחלון ורואים חתול שמן קופץ ממכסה המנוע של הרכב. ברגע שראיתם את החתול, הפאניקה מרעידת אדמה נעלמת מיד. החתול סיפק הסבר מלא ומספק לצפירת האזעקה, ובכך "מחק" (Explained Away) את ההשערה המפחידה. זוהי בדיוק הדינמיקה של מבנה V-structure נצפה.
💡 תרשים 9.2: מנגנון Explaining Away (תחרות בין סיבות במבנה V-Structure)
כיצד תצפית בילד משותף פותחת מסלול פעיל והופכת שתי סיבות בלתי-תלויות למתחרות
1. מבנה רשת האבחון הרפואי וטבלאות ה-CPT
מידול סיבתי של נטייה גנטית, שתי מחלות מתחרות וסימפטום משותף
נתבונן ברשת אבחון רפואי הכוללת 4 משתנים מקריים בוליאניים:
- • $G$ (וריאציה גנטית): משתנה שורש פריורי. $P(+g) = 0.1 \implies P(\neg g) = 0.9$.
- • $A$ (מחלה א'): מושפעת מהגנטיקה ($G \to A$). $P(+a \mid +g) = 1.0$, $P(+a \mid \neg g) = 0.1$.
- • $B$ (מחלה ב'): משתנה שורש עצמאי ללא תלות ב-$G$. $P(+b) = 0.4 \implies P(\neg b) = 0.6$.
- • $S$ (סימפטום קליני): ילד משותף של שתי המחלות ($A \to S \leftarrow B$ – מבנה V-Structure).
- • $P(+s \mid +b, +a) = 1.0$ (שתי המחלות יחד גורמות לסימפטום בוודאות)
- • $P(+s \mid +b, \neg a) = 0.9$ (מחלה ב' בלבד גורמת לסימפטום בסבירות גבוהה)
- • $P(+s \mid \neg b, +a) = 0.8$ (מחלה א' בלבד גורמת לסימפטום)
- • $P(+s \mid \neg b, \neg a) = 0.1$ (הסתברות רקע ספונטנית)
2. מהלך החישובים שלב אחר שלב (חישובי עזר ודחיקה לשוליים)
פירוק אירוע משותף, חישוב הסתברות שולית והסקה מותנית מלאה
לפי מבנה הרשת, ההתפלגות המשותפת מתפרקת ל: $$P(G, A, B, S) = P(G) \cdot P(A \mid G) \cdot P(B) \cdot P(S \mid A, B)$$ בהצבת הערכים עבור המצב שבו כל המשתנים חיוביים: $$P(+g, +a, +b, +s) = P(+g) \cdot P(+a \mid +g) \cdot P(+b) \cdot P(+s \mid +b, +a) = (0.1) \cdot (1.0) \cdot (0.4) \cdot (1.0) = \mathbf{0.04}$$
המשתנה $A$ תלוי במשתנה הנסתר $G$. כדי לחלץ את ההסתברות הא-פריורית של $A$, נבצע דחיקה לשוליים (Summing Out) על פני המשתנה $G$: $$P(+a) = P(+a \mid +g)P(+g) + P(+a \mid \neg g)P(\neg g)$$ $$P(+a) = (1.0 \times 0.1) + (0.1 \times 0.9) = 0.10 + 0.09 = \mathbf{0.19}$$
💡 משמעות: ללא כל תסמינים, הסבירות שאדם באוכלוסייה סובל ממחלה א' היא 19%.
מהי ההסתברות למחלה א' בהינתן שידוע כי לפציינט יש את מחלה ב'? $$P(+a \mid +b) = P(+a) = \mathbf{0.19}$$ נימוק טופולוגי: $A$ ו-$B$ אינם מקושרים ישירות ואינם חולקים אב קדמון משותף. כל עוד הילד המשותף $S$ אינו ידוע, המסלול דרכו חסום (Blocked), ולכן המחלות בלתי תלויות שולית לחלוטין!
כעת מגיע פציינט הידוע כסובל מהסימפטום ($+s$) וגם אובחן בוודאות עם מחלה ב' ($+b$). מה ההסתברות שיש לו גם את מחלה א'? נשתמש בחוק בייס מורחב ובדחיקה לשוליים: $$P(+a \mid +s, +b) = \frac{P(+a, +b, +s)}{P(+b, +s)} = \frac{P(+a, +b, +s)}{P(+a, +b, +s) + P(\neg a, +b, +s)}$$
שימו לב לדרמה ההסתברותית: כאשר חולה מציג שיעול/סימפטום בלבד ($+s$), ההסתברות למחלה א' מזנקת מעלה לכ-65% (הסקה אבחנתית). אך ברגע שבדיקת מעבדה מאשרת כי החולה סובל ממחלה ב' ($+b$), מחלה ב' "מסבירה" (Explains Away) את קיומו של הסימפטום, וההכרח להניח שהחולה נושא גם את מחלה א' צונח בחזרה ל-22.67% בלבד!
3. הרחבת המודל: הוספת צומת בדיקה מעבדתית ($T$)
כיצד נשמרת הכיווניות הסיבתית ואילו אי-תלויות חדשות נוצרות בגרף?
נניח שפותחה בדיקת מעבדה חדשה $T$ לאיתור מחלה א'. מבחינה מתודולוגית, המחלה היא שגורמת לתוצאת הבדיקה ולא להפך. לכן, הקשת חייבת להימתח מ-$A$ אל $T$ ($A \to T$).
- • בהינתן המחלה $A$, הבדיקה $T$ בלתי-תלויה מותנית בכל שאר המשתנים ברשת: $T \perp \{G, B, S\} \mid A$.
- • שמיכת מרקוב (Markov Blanket) של הצומת $T$ מורכבת אך ורק מהורו היחיד $A$. ברגע ש-$A$ ידוע, שום מידע מסימפטומים או מווריאציות גנטיות לא משנה את מהימנות הבדיקה.
סימולציה 9.2: המרפאה הווירטואלית ומעבדת Explaining Away
בעיית הבחירות והמדיניות העירונית (הסקה אבחנתית והרחבת רשת)
ניתוח חישובי ואלגברי של מערכת בחירות עירונית: הסקה אבחנתית (Diagnostic Inference), שרשור תלויות דרך משתנים מתווכים, התפלגות משותפת מלאה, שריון מרקובי, וניתוח טופולוגי קפדני של טענות אי-תלות מותנית תחת מבנה V-Structure.
להבין את האינטואיציה שמאחורי הקלעים: מידול מדיניות ציבורית וקבלת החלטות בסדום
בעולם האמיתי, מערכות סוציו-אקונומיות ופוליטיות כוללות מארג סבוך של אינטרסים, מחקרים, בחירות ופשיעה. ביחידה זו ננתח לעומק את תרחיש "עיריית סדום" המפורסם: כיצד מחקר מדעי ($S$) וזכיית מפלגת הירוקים ($G$) משפיעים על חוקיות המריחואנה ($M$), וכיצד זו משפיעה על צריכת סמים קשים ($C$) ושוחד שוטרים ($B$). נלמד להבחין מתי ראיה זורמת אחורה (הסקה אבחנתית), כיצד משתנה מתווך יוצר שריון מרקובי המבודד את השפעת הבחירות משיעור השוחד, וכיצד לפתור בעיות מורכבות אלו במבחן בביטחון מלא ובמהירות שיא.
💡 אינטואיציה בגובה העיניים: מנכ"ל החברה, מסך הברזל והחתימה על החוזה
תארו לעצמכם דירקטוריון בחברה המחליט האם לחתום על עסקת ענק ($M$). ההחלטה מושפעת מחוות דעת משפטית ($S$) ומתוצאות סקר שוק ($G$). לאחר שהעסקה נחתמת ($M$), מנהל הלוגיסטיקה מוציא הזמנות סחורה ($B$). אם אתם כבר יודעים שהעסקה נחתמה באופן סופי ($M=\text{true}$), האם אכפת לכם מה אמרה חוות הדעת המשפטית כדי לדעת אם הסחורה תסופק? ברור שלא! החוזה החתום הוא "מסך הברזל" שחוסם כל השפעה של מה שקדם לו. זוהי בדיוק אי-התלות המותנית $P(B \mid M, G) = P(B \mid M)$.
🏛️ תרשים 9.3: רשת המדיניות של סדום ועמורה וניתוח חסימת d-separation
מידול סיבתי של בחירות ומחקר מדעי ($S, G \to M$), פשיעה ושוחד ($M \to C, B$), ושריון מרקובי
1. הרשת הבסיסית והסקה אבחנתית ($P(G \mid M)$)
חישוב הסתברות הזכייה של מפלגת הירוקים בהינתן שהמריחואנה הפכה לחוקית
נגדיר שני משתנים מקריים בוליאניים:
- • $G$ – מועמד מפלגת הירוקים נבחר לראשות העיר ($P(G) = 0.1 \implies P(\neg G) = 0.9$).
- • $M$ – מריחואנה הופכת לחוקית. ההסתברויות המותנות: $P(M \mid G) = 0.667$ ($\approx \frac{2}{3}$), $P(M \mid \neg G) = 0.25$ ($\approx \frac{1}{4}$).
א. חישוב הסתברות המכנה $P(M)$ לפי נוסחת ההסתברות השלמה:
ב. הפעלת חוק בייס:
💡 היגיון אינטואיטיבי: ההסתברות הפריורית לבחירת הירוקים נמוכה מאוד (10%). אך מאחר שמפלגת הירוקים תומכת בלגליזציה באופן מובהק לעומת יריבותיה, קבלת הראיה שהמריחואנה הפכה לחוקית מקפיצה את ההסתברות שהירוקים נבחרו ליותר מפי שניים – ל-22.86%.
2. הרחבת הרשת: הוספת תקציב מאוזן ($B$) ונוכחות במפגשים ($C$)
שרשור השפעות סיבתיות דרך הצומת המתווך $M$ ($M \to B, M \to C$)
נוספים לרשת שני משתנים המושפעים ישירות מחוקיות המריחואנה:
חישוב עבור המצב שבו כל המשתנים חיוביים ($+g, +m, +b, +c$):
מאחר ש-$G$ ו-$C$ בלתי-תלויים מותנית בהינתן המתווך $M$ ($G \perp C \mid M$), נשתמש ב-$M$ לדחיקה לשוליים:
💡 היגיון אינטואיטיבי: ההגעה למפגשים ירדה ($\neg C$). מאחר שלגליזציה מעלה את הסבירות לירידה בנוכחות ($P(\neg C \mid M) = 0.75$ לעומת $0.5$), קבלת הראיה $\neg C$ מעלה את הסבירות שהמריחואנה חוקית, ובכך מעלה בעקיפין את ההסתברות שהירוקים נבחרו מ-10% ל-11.63%.
$$P(B) = P(B \mid M)P(M) + P(B \mid \neg M)P(\neg M)$$ $$= 0.4(0.2917) + 0.2(0.7083) = \mathbf{0.2583}$$
$$P(C \mid B) = \frac{P(C, B)}{P(B)} = \frac{0.10}{0.2583} \approx \mathbf{0.3871}$$
שונה מ-$P(C) = 0.4271$, מראה תלות הדדית דרך $M$.$$P(B \mid M, G) = P(B \mid M) = \mathbf{0.40}$$
בהינתן ההורה הישיר $M$, המשתנה $B$ מבודד לחלוטין מ-$G$.3. הוספת משתנה מחקר מדעי ($S$) ובחינת 7 טענות אי-תלות
יצירת מבנה V-Structure ($S \to M \leftarrow G$) ובחינה טופולוגית לפי חוקי d-separation
נוסף משתנה שורש $S$ (פרסום מחקר מדעי התומך בלגליזציה) המצביע ישירות על $M$ ($S \to M$). כעת $M$ מקבל שני חצים נכנסים: $S \to M \leftarrow G$, וממנו יוצאות קשתות ל-$B$ ול-$C$. השפעה על CPT: טבלת ה-CPT של $M$ תכיל כעת 4 שורות מותנות ($P(M \mid S, G)$) במקום 2.
לא נכון: קיים מסלול פתוח ביניהם דרך הסיבה המשותפת $M$ ($B \leftarrow M \to C$).
לא נכון: קיים מסלול פתוח ללא חסימה $G \to M \to B$.
נכון! $G$ ו-$S$ הם הורים של צומת התנגשות $M$ ($S \to M \leftarrow G$). מכיוון ש-$M$ וצאצאיו אינם נצפים, המסלול דרך $M$ חסום לחלוטין וההורים בלתי-תלויים שולית.
לא נכון: בהינתן $M$, $C$ בלתי תלוי ב-$G$, ולכן הביטוי שווה ל-$P(C \mid M)$ ולא ל-$P(C \mid G)$.
לא נכון: התניה על הילד המשותף $M$ פותחת את המסלול בין ההורים עקב תופעת ההסבר החלופי (Explaining Away!).
לא נכון: התניה על $B$ (שהוא צאצא ישיר של הילד המשותף $M$) פותחת אף היא את המסלול בין $G$ ל-$S$.
לא נכון: בהיעדר התניה על $M$, מידע מ-$G$ זורם דרך $M$ אל $B$.
סימולציה 9.3: מנוע הסקת בחירות ומדיניות עירונית (סדום Causal Engine)
סדר משתנים טופולוגי, אלגוריתם Variable Elimination ומבנה ה-Junction Tree
כיצד סדר הוספת המשתנים קובע את צפיפות הרשת ואת גודל טבלאות ה-CPT, אלגוריתם העלמת משתנים (Variable Elimination) המבוסס על תכנון דינמי ודיסטריבוטיביות, מושג רוחב העץ (Treewidth), וכלל צומת העקרה (Barren Node Rule).
להבין את האינטואיציה שמאחורי הקלעים: Variable Elimination - חישוב גורמים חכם במקום מכפלות עיוורות
כיצד מחשבים הסתברות מותנית מבלי לפתוח טבלאות ענק? בבית ספר יסודי למדנו את חוק הפילוג: במקום לחשב $ab + ac$, אנו מוציאים גורם משותף ומחשבים $a(b+c)$. אלגוריתם Variable Elimination (VE) עושה בדיוק את זה בעולם ההסתברות! במקום לסכום טבלה מלאה, הוא "דוחף" את פעולות הסכימה פנימה ומעלים משתנים לא רלוונטיים בזה אחר זה. ביחידה זו נבין לעומק את שתי פעולות היסוד (Pointwise Product ו-Summing Out), נכיר את חשיבותו הקריטית של סדר העלמת המשתנים הנשלט על ידי רוחב העץ (Treewidth), ונלמד כיצד אופטימיזציית צומת עקרה (Barren Node Rule) מאפשרת למחוק ענפים שלמים באפס פעולות מתמטיות.
💡 אינטואיציה בגובה העיניים: סידור תרמיל למסע ומחיקת משקל עודף מראש
תארו לעצמכם שאתם אורזים תרמיל לטיול הרים. אם תארזו כל חפץ אפשרי ואז תנסו לסחוב את התיק במעלה ההר, הגב שלכם יישבר (פיצוץ זיכרון). לעומת זאת, מטייל חכם עובר על הרשימה ומסלק מראש כל חפץ שאינו חיוני ליעד: עלים בלתי נצפים שאינם משפיעים על שאלת המטרה נזרקים לפח מיד (Barren Nodes), ואת שאר הציוד מאחדים באריזות דחוסות לפי סדר הגיוני. סדר אריזה נכון שומר על התרמיל קל וקומפקטי לכל אורך הדרך.
🔢 תרשים 9.4: צנרת אלגוריתם Variable Elimination (מכפלת גורמים וסכימה החוצה)
ארבעת שלבי האלגוריתם: גורמים ראשוניים $\to$ מכפלה נקודתית $\to$ סכימה החוצה $\to$ נרמול סופי
1. השפעת סדר הוספת המשתנים על צפיפות ה-CPT
השוואה כמותית בין סדר סיבתי טבעי (10 ערכים) לסדר שרירותי (13 ערכים)
נתונה רשת בעלת חמישה משתנים בינאריים עם המבנה הסיבתי המקורי הבא: $A \to B \to D$ ו-$B \to E \leftarrow C$ (מבנה V-Structure ב-$E$).
- • $A$ (ללא הורים): $2^0 = 1$ ערך
- • $C$ (ללא הורים): $2^0 = 1$ ערך
- • $B$ (הורה $A$): $2^1 = 2$ ערכים
- • $D$ (הורה $B$): $2^1 = 2$ ערכים
- • $E$ (הורים $B, C$): $2^2 = 4$ ערכים
- • הוספת $D$: ראשון בגרף $\implies$ ללא הורים ($1$ ערך).
- • הוספת $A$: תלוי ב-$D$ (דרך $B$) $\implies$ קשת $D \to A$ ($2$ ערכים).
- • הוספת $B$: תלוי ב-$D$ וב-$A$ $\implies$ קשתות $D \to B, A \to B$ ($4$ ערכים).
- • הוספת $E$: מושפע ישירות מ-$B$ $\implies$ קשת $B \to E$ ($2$ ערכים).
- • הוספת $C$: עקב ההתניה על $E$, נוצרת תלות בין $B$ ל-$C$ (Explaining away) שמחייבת הוספת קשתות $E \to C$ ו-$B \to C$ ($4$ ערכים).
אם יש ספק האם שני משתנים בלתי-תלויים מותנית תחת סדר חדש, חובה להוסיף קשת ביניהם! השמטת קשת תטען לאי-תלות שאינה קיימת במציאות ותעוות את ההתפלגות המשותפת. לכן, בנייה בסדר סיבתי טבעי עדיפה בהרבה, שכן היא מונעת קשתות גישור (Fill-in Edges) מיותרות ושומרת על הרשת דלילה וחסכונית.
2. אלגוריתם Variable Elimination (העלמת משתנים)
חישוב שאילתות הסתברות מדויקות על ידי דחיפת סכומי שוליות לתוך מכפלות גורמים
במקום לחשב את כל מרחב ההתפלגות המשותפת (שגוזל $O(d^n)$ פעולות), אלגוריתם Variable Elimination מנצל את חוק הפילוג (Distributivity) כדי לבצע סכימה מקומית מוקדמת ככל האפשר.
איסוף כל ה-CPTs וגורמי הביניים המכילים את המשתנה שיש להעלימו ($Z$), וביצוע מכפלה נקודתית (Pointwise Product) לטבלה מאוחדת:
ביצוע דחיקה לשוליים של המשתנה $Z$ על ידי סכימת כל שורותיו מתוך הגורם המשותף, מה שמניב גורם קומפקטי חדש:
סיבוכיות הזמן והמקום של האלגוריתם נשלטת לחלוטין על ידי גודל הגורם המקסימלי שנוצר במהלך הריצה. אם במהלך העלמת משתנה נוצר גורם המכיל $w$ משתנים, גודל הטבלה בזיכרון יהיה $d^w$. מציאת סדר העלמת משתנים שממזער את $w$ (רוחב העץ של הגרף, Treewidth) היא בעיה NP-Hard.
אם ברשת קיים צומת עלה (Leaf Node) שאינו חלק ממשתני השאילתה (Query) ואינו מכיל ראיה (Evidence) – ניתן למחוק אותו מהגרף באופן מיידי באפס זמן ריצה! זאת משום שסכימת ההסתברות המותנית של צומת עלה על פני כל ערכיו שווה תמיד ל-1 ($\sum_x P(x \mid parents) = 1$) ולכן אינה משפיעה על שאר המשתנים.
סימולציה 9.4: מעבדת סדר משתנים ו-Variable Elimination Flow
הנדסה לאחור (Structure Learning), שקילות מרקובית ואלגוריתם Bayes-Ball
חילוץ מבנה רשת מתוך טבלת התפלגות אמפירית, בחינה של 6 רשתות מועמדות ופסילתן, גישות למידת מבנה מבוססות אילוצים (PC) ומבוססות ציון (BIC/BDeu), וחוקי זרימת כדורי Bayes-Ball לבדיקת אי-תלות מותנית בזמן ליניארי.
להבין את האינטואיציה שמאחורי הקלעים: הנדסה לאחור ולמידת מבנה בעזרת Bayes-Ball
עד כה הנחנו שמומחה אנושי צייר עבורנו את הרשת. אך מה עושים כאשר יש לנו רק קובץ נתונים גולמי של מיליוני רשומות רפואיות או פיננסיות, ואנו רוצים שהמחשב יגלה בעצמו את חוקי הסיבתיות? זוהי למידת מבנה (Structure Learning). ביחידה זו נחקור כיצד מסיקים אי-תלויות מתוך טבלת נתונים, כיצד פוסלים רשתות שגויות, ונכיר את האלגוריתם הקינטי המבריק Bayes-Ball של שחטר (Ross Shachter): מעין כדור פינג-פונג דמיוני שמתגלגל בגרף, מקפץ לאחור בצמתים חסומים או עובר בחופשיות בצמתים פתוחים, ומאפשר לנו להכריע בשבריר שנייה האם שני משתנים בלתי-תלויים מותנית.
💡 אינטואיציה בגובה העיניים: משחק ביליארד במבוך שסתומים חד-כיווניים
תארו לעצמכם שולחן פליפר (Pinball) מלא שסתומים ומחסומים. בשרשרת רגילה, הכדור מתגלגל ישר דרך השסתום הפתוח. אך אם מישהו "נועל" את השסתום באמצעות תצפית (Evidence), הכדור פוגע בקיר וקופץ לאחור — המסלול נחסם! במבנה קוליידר (שני חצים נפגשים), השסתום נעול כברירת מחדל והכדור נבלם. רק אם תציבו ראיה על הקוליידר, השסתום ייפתח במפתיע והכדור יוכל לחמוק דרכו. חוקי הפיזיקה של הכדור הזה מקבילים בדיוק לחוקי זרימת המידע ההסתברותי ב-d-separation.
⚾ תרשים 9.5: מטריצת 6 חוקי הכדור המקפץ (Bayes-Ball) בכל מבני הרשת
מתי הכדור עובר בחופשיות (מסלול פעיל) ומתי הוא נבלם וקופץ לאחור (מסלול חסום)
1. הנדסה לאחור: התאמת רשת בייסיאנית להתפלגות נתונה
ניתוח מדוקדק של טבלת 8 שורות עבור $P(A, B, C)$ ובחירת הרשת המייצגת מתוך 6 מועמדות
נתונה טבלת התפלגות משותפת מלאה של שלושה משתנים בוליאניים ($A, B, C$):
| A | B | C | P(A, B, C) |
|---|---|---|---|
| 0 | 0 | 0 | 0.15 |
| 0 | 0 | 1 | 0.10 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0.25 |
| 1 | 0 | 0 | 0.15 |
| 1 | 0 | 1 | 0.10 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0.25 |
- • $P(A=0) = 0.15 + 0.10 + 0 + 0.25 = \mathbf{0.50} \implies P(A=1) = \mathbf{0.50}$
- • $P(B=0) = 0.15 + 0.10 + 0.15 + 0.10 = \mathbf{0.50} \implies P(B=1) = \mathbf{0.50}$
- • $P(C=0) = 0.15 + 0 + 0.15 + 0 = \mathbf{0.30} \implies P(C=1) = \mathbf{0.70}$
נתבונן בהתפלגות המשותפת של $A$ עם $B$ ושל $A$ עם $C$:
- • $P(A=0, B=0) = 0.15 + 0.10 = 0.25 = P(A=0) \times P(B=0) \implies A \perp B$
- • $P(A=0, C=0) = 0.15 + 0 = 0.15 = P(A=0) \times P(C=0) \implies A \perp C$
💡 תובנה מכרעת: שימו לב שבכל שורה ושורה בטבלה, עבור כל ערך של $(B, C)$, ההסתברות של $A=0$ שווה במדויק להסתברות של $A=1$ (למשל $P(0,0,0) = P(1,0,0) = 0.15$). מכאן נובע כי $A$ בלתי תלוי לחלוטין בקבוצה $\{B, C\}$ ביחד: $P(A, B, C) = P(A) \cdot P(B, C)$!
$$P(B=1, C=0) = P(0,1,0) + P(1,1,0) = 0 + 0 = \mathbf{0}$$ אולם מכפלת השוליות היא: $$P(B=1) \times P(C=0) = 0.50 \times 0.30 = \mathbf{0.15} \neq 0$$
❌ מכיוון ש-$P(B=1, C=0) \neq P(B=1)P(C=0)$, המשתנים $B$ ו-$C$ תלויים זה בזה בהכרח!
נפסלת: מניחה ש-$B \perp C$, אך הוכחנו שהם תלויים חזק.
נפסלת: מניחה תלות בין $A$ ל-$B$, למרות שהם בלתי-תלויים.
נפסלת: מניחה אי-תלות מותנית $B \perp C \mid A$. בפועל $P(B=1, C=0 \mid A=0) = 0 \neq 0.15$.
נפסלת: במבנה V זה, $B$ ו-$C$ בלתי תלויים שולית, בסתירה מוחלטת לנתונים.
ברשת 3, הצומת $A$ מבודד לחלוטין, וקיימת קשת מכוונת $C \to B$ (או $B \to C$). פירוק הרשת הוא: $P(A, B, C) = P(A) \cdot P(B \mid C) \cdot P(C) = P(A) \cdot P(B, C)$. פירוק זה משחזר בדיוק של 100% את כל 8 השורות בטבלה המקורית ללא הוספת פרמטרים מיותרים!
2. זרימת מידע דינמית ואלגוריתם ה-Bayes-Ball (שקטר, 1998)
בדיקת אי-תלות מותנית (d-separation) בזמן ליניארי $O(V + E)$ על הגרף המקורי
אלגוריתם Bayes-Ball משגר "כדור" דמיוני מצומת המקור ובודק האם קיים מסלול פתוח שבו יוכל הכדור להגיע לצומת היעד, בהינתן קבוצת הצמתים הנצפים (Evidence).
• אם $C$ נסתר: הכדור עובר חופשי (תלויים).
• אם $C$ נצפה: נופל קיר חוסם, הכדור נהדף לאחור (אי-תלות מותנית).
• אם $C$ נסתר: הכדור עובר דרך השורש לשני הענפים.
• אם $C$ נצפה: המסלול נחסם לחלוטין ($A \perp B \mid C$).
• אם $C$ וצאצאיו נסתרים: בור פתוח! הכדור נופל ונחסם ($A \perp B$).
• אם $C$ או מי מצאצאיו נצפים: מופיע גשר! הכדור חוצה בין ההורים (Explaining Away!).
הרחבה מתקדמת של d-separation המזהה אי-תלות שאינה נובעת מטופולוגיית הגרף אלא מערכים ספציפיים ב-CPT. לדוגמה, אם משתנה מתג $S=\text{false}$ גורם לכך שערכו של $Y$ נקבע כ-0 בכל מקרה, אזי בהקשר $S=\text{false}$ המשתנה $Y$ בלתי תלוי בשאר הוריו.
סימולציה 9.5: מעבדת הנדסה לאחור ומגרש כדורי Bayes-Ball
צ'יט-שיט מאסטר וסיכום מקיף לבחינה: רשתות בייסיאניות מתקדמות
ריכוז כל הנוסחאות, חוקי d-separation ו-Bayes-Ball, צעדי אלגוריתם Variable Elimination, מטריצת השוואת אלגוריתמי הסקה, 10 מלכודות בחינה נפוצות, מילון מונחים מקצועי וגשר לפרק 10.
להבין את האינטואיציה שמאחורי הקלעים: המפה הפנורמית של רשתות בייסיאניות לקראת הבחינה
הגעתם ללשונית הסיכום והמאסטר של פרק 9! פרק זה מהווה את אחד מעמודי התווך המרכזיים ביותר בבחינה בקורס מבוא לבינה מלאכותית (20551). כאן מאוגדים כל הכלים שלמדתם: מנוסחאות הפירוק של ה-DAG, דרך חוקי חסימת מסלולים אקטיביים ב-d-separation וב-Bayes-Ball, צעדי החישוב של אלגוריתם Variable Elimination, ועד למידת מבנה והשוואת אלגוריתמי הסקה מדויקים ומקורבים. השתמשו בצ'יט-שיט זה כמדריך חירום מהיר: עברו על 10 מלכודות הבחינה הנפוצות, שריינו את מילון המונחים המלא, והכינו את הקרקע למעבר מאי-ודאות פסיבית לקבלת החלטות אקטיבית בפרק 10 (רשתות החלטה ו-MDP).
💡 אינטואיציה בגובה העיניים: ארגז הכלים של מהנדס הבינה המלאכותית
מהנדס תוכנה טוב אינו משתמש באותו כלי לכל בעיה: אם הגרף שלכם צר ודליל (רוחב עץ קטן), אתם לוקחים את כלי המנתחים המדויק Variable Elimination. אם הגרף הוא רשת חברתית ענקית ומסועפת עם מיליוני לולאות, הניסיון לבצע הסקה מדויקת ישרוף את השרתים — במקום זאת, אתם שולפים את כלי הדגימות הסטטיסטיות Gibbs Sampling ומקבלים הערכה מעולה בזמן קצר. הבנת היתרונות והמגבלות של כל כלי היא ההבדל בין פתרון תיאורטי כושל למערכת בינה מלאכותית אמיתית שעובדת בעולם האמיתי.
🗺️ תרשים 9.6: מפת האקוסיסטם הכוללת של רשתות בייסיאניות
ארבעת עמודי התווך של פרק 9: ייצוג $\to$ אי-תלות $\to$ אלגוריתמי הסקה $\to$ למידת מבנה ופרמטרים
נוסחאות מפתח וקשרי חישוב יסודיים
חוקי יסוד לפתרון תרגילים וחישובי גדלי CPT ברשתות בייסיאניות
- • כלל השרשרת לפירוק DAG:
$P(X_1,\dots,X_n) = \prod_{i=1}^n P(X_i \mid \text{Parents}(X_i))$ - • גודל CPT חופשי (משתנה בדיד כללי):
$(d_X - 1) \times \prod_{j=1}^k d_{parent_j}$ (עבור משתנה בינארי: $1 \times 2^k$) - • מודל Noisy-OR (חיסכון ליניארי בפרמטרים):
$P(Y=1 \mid \mathbf{X}) = 1 - \prod_{i: X_i=1} q_i$ כאשר $q_i = P(Y=0 \mid X_i=1)$ - • מודל Leaky Noisy-OR (גורם רקע נסתר):
$P(Y=1 \mid \mathbf{X}) = 1 - q_0 \prod_{i: X_i=1} q_i$ ($q_0$ מייצג דליפת רקע) - • דחיקה לשוליים (Marginalization / Law of Total Probability):
$P(X) = \sum_y P(X, y) = \sum_y P(X \mid y)P(y)$
- • שרשרת ($X \to Y \to Z$):
$Y$ נסתר = פתוח | $Y$ נצפה = חסום ($X \perp Z \mid Y$) - • מזלג ($X \leftarrow Y \to Z$):
$Y$ נסתר = פתוח | $Y$ נצפה = חסום ($X \perp Z \mid Y$) - • התכנסות/קוליידר ($X \to Y \leftarrow Z$):
$Y$ וצאצאיו נסתרים = חסום! | $Y$ או צאצא נצפה = פעיל (פתוח)! - • שמיכת מרקוב (Markov Blanket):
$\text{MB}(X) = \text{Parents}(X) \cup \text{Children}(X) \cup \text{Spouses}(X)$ - • צומת עקרה (Barren Node Rule):
עלה שאינו נצפה ואינו מטרת השאילתה נמחק מיד עוד לפני הפעלת אלגוריתם VE.
⚖️ מטריצת השוואת אלגוריתמי הסקה ברשתות בייסיאניות
מתי להשתמש בכל אלגוריתם? השוואת סיבוכיות זמן, זיכרון, יתרונות ומגבלות
| אלגוריתם | סוג הסקה | סיבוכיות זמן | סיבוכיות זיכרון | יתרון מנצח | צוואר בקבוק עיקרי |
|---|---|---|---|---|---|
| מנייה נאיבית (Enumeration) | מדויקת | $O(n \cdot d^n)$ | $O(n)$ | פשוט ביותר למימוש, חיסכון בזיכרון | פיצוץ זמן אקספוננציאלי ($n > 25$ קורס) |
| Variable Elimination (VE) | מדויקת | $O(n \cdot d^{w+1})$ | $O(d^{w+1})$ | אופטימלי לגרפים דלילים (רוחב עץ $w \le 15$) | מציאת סדר העלמה אופטימלי היא NP-קשה |
| עץ קליקות (Junction Tree) | מדויקת | $O(N_C \cdot d^w)$ | $O(N_C \cdot d^w)$ | מחשב שוליות של כל המשתנים ב-2 מעברי מסרים | דרישות זיכרון כבדות לאחסון כל הקליקות |
| שקילת נראות (Likelihood Weighting) | מקורבת | $O(N \cdot |E|)$ | $O(n)$ | מתמודד עם גרפים ענקיים, כל דגימה תורמת | מתנוון למשקלים אפסיים כשהראיות נדירות |
| דגימת גיבס (Gibbs Sampling / MCMC) | מקורבת MCMC | $O(N \cdot |\text{MB}|)$ | $O(n)$ | עמיד לראיות נדירות; תלוי רק בשמיכת מרקוב | דורש שלב חימום (Burn-in), דגימות תלויות עוקבות |
🎯 ריכוז תוצאות החישוב המספריות של בעיות הליבה בקורס
בדיקה מהירה של תוצאות סופיות לכל אחד מהתרחישים המרכזיים בבחינות
- • $P(M) = 0.667(0.1) + 0.25(0.9) = \mathbf{0.2917}$
- • $P(G \mid M) = \frac{0.0667}{0.2917} \approx \mathbf{0.2286} \quad (22.86\%)$
- • $P(G \mid \neg C) = \frac{0.06666}{0.5729} \approx \mathbf{0.1163} \quad (11.63\%)$
- • $P(B) = \mathbf{0.2583}, \quad P(C \mid B) \approx \mathbf{0.3871}$
- • שריון מרקוב: $P(B \mid M, G) = P(B \mid M) = \mathbf{0.40}$
- • $P(+g, +a, +b, +s) = 0.1 \times 1.0 \times 0.4 \times 1.0 = \mathbf{0.04}$
- • שוליות מחלה א': $P(+a) = 1.0(0.1) + 0.1(0.9) = \mathbf{0.19}$
- • הסקה ללא ראיה: $P(+a \mid +b) = P(+a) = \mathbf{0.19}$ (אי-תלות)
- • הסבר חלופי: $P(+a \mid +s, +b) = \frac{0.076}{0.076 + 0.2592} \approx \mathbf{0.2267}$
- • 5 משתנים בינאריים: $1 + 1 + 2 + 2 + 4 = \mathbf{10 \text{ ערכים}}$
- • סדר משתנים לא סיבתי ($D, A, B, E, C$): $1 + 2 + 4 + 2 + 4 = \mathbf{13 \text{ ערכים}}$
- • מעבר ל-$A(5)$ ו-$E(5)$: $4 + 1 + 1 + 80 + 10 = \mathbf{96 \text{ ערכים}}$ (מול 15)
- • $A$ בלתי תלוי בקבוצה $\{B, C\}$: $P(A, B, C) = P(A)P(B, C)$
- • $B$ ו-$C$ תלויים: $P(B=1, C=0) = 0 \neq 0.15$ (פוסל רשת 1 ו-6)
- • רשת 3 ($A$ מנותק, $C \to B$) היא המייצגת המינימלית הנכונה!
⚠️ 10 מלכודות הבחינה הקלאסיות ברשתות בייסיאניות (איך לא ליפול בפח!)
טעויות חוזרות של סטודנטים בבחינות מהשנים האחרונות וכיצד להימנע מהן
1. בלבול בין היעדר קשת לבין אי-תלות שולית ▼
המלכודת: הנחה שאם אין קשת ישירה בין $X$ ל-$Z$, הם בהכרח בלתי-תלויים ($X \perp Z$).
התיקון: שגוי לחלוטין! אם קיים ביניהם מסלול של שרשרת ($X \to Y \to Z$) או מזלג ($X \leftarrow Y \to Z$) כאשר $Y$ נסתר, המידע זורם בחופשיות והם תלויים לחלוטין.
2. מתי קוליידר באמת נפתח? (אב מול צאצא) ▼
המלכודת: תצפית בהורה של קוליידר פותחת את המסלול.
התיקון: קוליידר ($X \to Y \leftarrow Z$) נפתח אך ורק אם $Y$ בעצמו או אחד מצאצאיו ($Y \to \dots \to W$) נצפה! תצפית באב קדמון של $X$ אינה פותחת את $Y$.
3. שכחת ה- (d-1) בספירת פרמטרים חופשיים ▼
המלכודת: כפל ערכי המשתנה בכל הצירופים: $d \times \prod d_{parent}$.
התיקון: סכום ההסתברויות בכל שורת CPT הוא בדיוק 1. לכן הערך האחרון נקבע אוטומטית. חובה לכפול ב-$(d-1)$ בלבד!
4. כשל שיעור הבסיס (Base Rate Fallacy) ▼
המלכודת: הנחה שבדיקה עם 99% דיוק מעידה על 99% סיכוי למחלה נדירה.
התיקון: חוק בייס תלוי בשכיחות הפריורית $P(Disease)$. אם המחלה שכיחה ב-1 ל-10,000, רוב התוצאות החיוביות הן False Positives!
5. שכחת הנרמול (קבוע α) באלגוריתם VE ▼
המלכודת: סכימה של הגורם הסופי ומחשבה שערכיו מייצגים הסתברויות תקפות שסכומן אינו 1.
התיקון: בהינתן ראיות, הגורם הסופי $f(Q)$ אינו מנורמל. חובה לנרמל על ידי חלוקה בסכום ערכיו: $\alpha = 1 / \sum_q f(q)$.
6. מחיקת עלי ראיה תחת Barren Node Rule ▼
המלכודת: מחיקת צומת עלה שמכיל תצפית (ראיה $e$).
התיקון: כלל צומת עקרה חל אך ורק על עלים בלתי-נצפים. אם בעלה יש ראיה, הסכום אינו 1 ואסור למחוק אותו!
7. שכחת ההורים המשותפים (Spouses) בשמיכת מרקוב ▼
המלכודת: הגדרת שמיכת מרקוב כהורים וילדים בלבד.
התיקון: הילדים הם קוליידרים! ידיעת הילד פותחת מסלול להורה האחר שלו (ההורה המשותף). לכן חובה לכלול גם את ההורים הנוספים של כל הילדים.
8. הנחת שוויון זמנים בין סדרי העלמה שונים ▼
המלכודת: חשיבה שכל סדר העלמה ייתן את אותה סיבוכיות ריצה.
התיקון: סדר גרוע יוצר גורם ענק (קליקה בגודל $O(2^n)$) וקורס. סדר טוב (יוריסטיקת Min-Fill) שומר על גורמים קטנים $O(2^w)$ ומסתיים בשניות.
9. שקילות מרקובית: היפוך חץ אסור ▼
המלכודת: היפוך חץ במבנה V-structure ($X \to Y \leftarrow Z$) בטענה שהגרף שקול מרקובית.
התיקון: V-structures בלתי-מוסריים (ללא קשת בין ההורים) חייבים להישמר בכיוונם המדויק! רק חצים שאינם יוצרים או הורסים V-structures מותרים בהיפוך.
10. בלבול בין דגימת גיבס לשקילת נראות בראיות נדירות ▼
המלכודת: שימוש ב-Likelihood Weighting כאשר הראיה בעלת הסתברות אפסית ($10^{-6}$).
התיקון: בראיה נדירה, כמעט כל המשקלים ב-LW יהיו 0, וההערכה תהיה חסרת ערך. במצב זה יש להשתמש ב-Gibbs Sampling / MCMC המקבעת את הראיות וחוקרת את מרחב המצבים הרלוונטי בלבד.
📖 מילון מונחים מקצועי: מושגי מפתח ברשתות בייסיאניות
הגדרות מתמטיות ואינטואיטיביות של כל מונחי הפרק
גרף מכוון ללא מעגלים. הצמתים מייצגים משתנים מקריים, והחצים מקודדים קשרים סטטיסטיים וסיבתיים ישירים.
טבלת הסתברויות מותנות המפרטת את ההתפלגות $P(X \mid \text{Parents}(X))$ עבור כל צירוף אפשרי של ערכי ההורים.
כל צומת בלתי-תלוי מותנית בכל הצמתים שאינם צאצאיו, בהינתן הוריו הישירים בלבד.
מבנה $X \to Y \leftarrow Z$ שבו שני חצים נפגשים באותו צומת. חסום כברירת מחדל, ונפתח כאשר $Y$ או צאצאו נצפים.
תופעה במבנה קוליידר נצפה, שבה אימות סיבה אחת מקטין את ההסתברות של סיבה חלופית לאותה תוצאה.
קבוצת הצמתים המבודדת צומת $X$ לחלוטין מכל שאר הגרף: הוריו, ילדיו, וההורים הנוספים של ילדיו.
טבלה רב-ממדית הממפה צירופי ערכים של קבוצת משתנים למספרים אי-שליליים (אינה בהכרח מנורמלת ל-1).
מדד למידת ה"צפיפות" והמעגליות הלא-מכוונת של הגרף, הקובע את גודל הגורם המקסימלי באלגוריתם VE.
צומת עלה בלתי-נצפה שאינו משתנה המטרה. סכימה עליו שווה תמיד ל-1, וניתן למחוק אותו ואת צאצאיו מראש.
מדד ללמידת מבנה המאזן בין נראות המודל ($\log L$) לבין קנס על כמות הקשתות: $-\frac{\log N}{2} \cdot \text{Dim}(G)$.
גשר לפרק 10: מאי-ודאות פסיבית לקבלת החלטות אקטיבית
כיצד הידע שנרכש ברשתות בייסיאניות מהווה את התשתית למודלי החלטה ולמידת חיזוק (RL)
בפרקים 8 ו-9 עסקנו בהסקה פסיבית: הסוכן קיבל תצפיות וחישב מחדש את מידת אמונתו ($P(Q \mid e)$). אך סוכן תבוני אמיתי אינו מסתפק בהתבוננות — עליו לפעול בעולם כדי למקסם תועלת (Utility)! בפרק 10 נרחיב את הרשתות הבייסיאניות באמצעות הוספת צומתי החלטה (מלבנים) וצומתי תועלת (מעוינים) וניצור רשתות החלטה (Influence Diagrams). בהמשך, נרחיב זאת לרצף של החלטות לאורך זמן תחת אי-ודאות — תהליכי החלטה מרקוביים (MDP), משוואות בלמן, ואלגוריתמי Value Iteration שיובילו אותנו ישירות ללמידת חיזוק מודרנית (Reinforcement Learning).