זמן משוער: כ-90 דקות כולל התרגול. דרישות קדם: אין. כל סימון מוסבר ברגע שהוא מופיע.
בשיעור הזה אין "רשימת נושאים". יש שרשרת של שאלות, וכל נושא הוא התשובה לשאלה שהנושא הקודם השאיר פתוחה. אם בנקודה כלשהי תרגיש "למה אני לומד את זה עכשיו", תחפש את השאלה שהובילה לשם.
אחרי כל סעיף יש תרגילים קצרים. הם ממוינים לפי טכניקה (כתוב ליד כל תרגיל), כדי שתראה בכל פעם כלי אחר. נסה לפתור על דף לפני שאתה פותח רמז או פתרון.
❓ אם אני מטיל מטבע פעמיים, לא בהכרח יצא עץ פעם אחת. אז מה בדיוק טענתי כשאמרתי "הסיכוי הוא 1/2"?
הסעיף בנוי בשלבים: (0) על מה מדברים, (1) מה "חצי" לא יכול להיות, (2) מה הוא כן, (3) ניסוי חי, (4) מה נקבל מזה, (5) מלכודת נפוצה.
הסתברות עוסקת בניסוי מקרי: משהו שאפשר לחזור עליו, ושאת התוצאה שלו אי אפשר לנבא מראש. דוגמאות: הטלת מטבע, הטלת קובייה, בחירת תמונה אקראית מתוך דאטהסט.
נטיל מטבע הוגן פעם אחת. תהיה תוצאה אחת: עץ או פלי. אין דבר כזה "חצי עץ". לכן "1/2" לא מתאר את ההטלה הבודדת.
אולי הכוונה "בכל שתי הטלות יצא עץ בדיוק פעם אחת"? גם לא: אפשר לקבל עץ-עץ, ואף אחד לא יגיד שהמטבע "לא הוגן". לכן הטענה חייבת להיות על משהו אחר: מה שקורה כשחוזרים על הניסוי הרבה פעמים.
נניח שחזרנו על ניסוי $n$ פעמים, והמאורע שמעניין אותנו (למשל "יצא עץ") קרה $k$ מהפעמים. אז:
דוגמה: 10 הטלות, 7 מהן עץ: התדירות היחסית היא $7/10=0.7$.
עכשיו הנה ריצה אופיינית (המספרים ישתנו מריצה לריצה, אבל התבנית קבועה):
| מספר ההטלות $n$ | 10 | 100 | 1,000 | 100,000 |
|---|---|---|---|---|
| כמה פעמים עץ, $k$ | 7 | 54 | 508 | 49,930 |
| תדירות יחסית $k/n$ | 0.700 | 0.540 | 0.508 | 0.4993 |
שים לב: בהתחלה המספר "קופץ" (0.7), ואחר כך הוא מתקרב ל-0.5. זה הפירוש של "הסיכוי הוא חצי":
"ההסתברות למאורע $A$ היא $p$" פירושו: כשחוזרים על הניסוי הרבה פעמים, התדירות היחסית של $A$ מתקרבת ל-$p$.
(הפרשנות הזו נקראת תדירותית, ב-frequentist. התכונה "התדירות מתקרבת ל-p" נקראת חוק המספרים הגדולים. נוכיח אותה בשיעור 7. כרגע אנחנו פשוט רואים אותה.)
מכיוון שהסתברות היא מה שהתדירות $\frac kn$ מתקרבת אליו, היא "יורשת" ממנה כמה תכונות מיידיות. (זה ישמש אותנו בסעיף 4, כשננסח את החוקים.)
נניח שיצאו 10 עצים ברצף. מישהו אומר: "עכשיו פלי חייב לצאת, כדי שזה יתאזן". זה לא נכון. למטבע אין זיכרון, וההטלה הבאה היא עדיין חצי-חצי.
אבל אז איך התדירות בכל זאת מתכנסת ל-1/2? לא על ידי "תיקון". ננסה לראות עם מספרים:
שים לב: העודף של 5 עצים לא נעלם: עדיין יש 505 עצים במקום 500. פשוט 5 מתוך 1,000 הוא כמעט כלום. העודף "נמס" בתוך המספרים הגדולים, ולא תוקן. השורה "הפרש מוחלט" בסימולציה למעלה מראה את זה: ההפרש לא הולך ל-0, רק היחס שלו למספר ההטלות.
יש מצבים שאי אפשר "לחזור על הניסוי": "מה הסיכוי שמחר ירד גשם?" מחר קורה פעם אחת. בגישה הבייסיאנית הסתברות היא דרגת אמונה. בגישה הקלאסית היא נספרת מסימטריה ("6 פאות שוות, לכן 1/6"). שלושת הגישות מסכימות על אותם חוקי חישוב, ובשיעור 9 נראה למה ההבדל בכל זאת חשוב ל-ML. בינתיים תחזיק בתדירותית, שהיא הכי קלה לדמיין.
תרגיל 1.2 סימולציה (Monte Carlo) ⭐⭐
בלי לחשב כלום, כתוב ב-numpy קוד שמעריך את ההסתברות שבהטלת שתי קוביות הסכום הוא 7, על ידי חזרה על הניסוי 100,000 פעמים. מה אתה מצפה לקבל?
צור שני מערכים של מספרים אקראיים 1–6 (rng.integers(1, 7, size=N)), חבר אותם, וחשב את הממוצע של הביטוי הבוליאני (a+b) == 7. ממוצע של True/False הוא בדיוק "החלק היחסי".
import numpy as np
rng = np.random.default_rng(0)
N = 100_000
a = rng.integers(1, 7, size=N)
b = rng.integers(1, 7, size=N)
print(np.mean(a + b == 7)) # ~0.166 (בקרוב נחשב: 1/6)
הטריק שחשוב לזכור: הסתברות = ממוצע של אינדיקטור. (True נספר כ-1.) זה יחזור שוב ושוב ב-ML, למשל accuracy הוא ממוצע של "האם ניחשתי נכון".
הבנו שהסתברות היא "חלק יחסי של פעמים". עכשיו צריך להיות מדויקים: חלק של מה? של הפעמים שבהן קרה "משהו". צריך לתת שם לאותו "משהו".
❓ "התדירות היחסית של הפעמים שבהן קרה משהו". איך מגדירים "משהו" בצורה שאפשר לעבוד איתה?
נלך בשלבים: (1) תוצאה, (2) מרחב מדגם, (3) מאורע, (4) שתי קוביות, (5) מלכודות.
תוצאה (outcome) היא התשובה המלאה והבודדת של ריצה אחת של הניסוי. הטלת מטבע: התוצאה היא "עץ" או "פלי". הטלת קובייה: התוצאה היא המספר שהקובייה הראתה, 1 או 2 או ... או 6. בכל ריצה מתממשת בדיוק תוצאה אחת.
נאסוף את כל התוצאות האפשריות לקבוצה אחת. קבוצה היא אוסף של דברים, ואותה כותבים בסוגריים מסולסלים $\{\ \}$ (הסדר לא משנה, וכל איבר מופיע פעם אחת). את הקבוצה הזו מסמנים ב-$\Omega$ (האות היוונית "אומגה"), ונקראת מרחב מדגם (sample space):
לפעמים השאלה שלנו לא על תוצאה בודדת. "האם יצא מספר זוגי?" נכון לשלוש תוצאות שונות: 2, 4 ו-6. אז נגדיר:
מאורע (event) הוא קבוצה של תוצאות, כלומר חלק מתוך $\Omega$. את זה כותבים $A\subseteq\Omega$ ("$A$ מוכלת ב-$\Omega$", כלומר $A$ היא חלק מ-$\Omega$). אומרים ש"$A$ קרה" אם התוצאה שיצאה נמצאת ב-$A$.
דוגמאות בקובייה:
| במילים | כקבוצה | כמה תוצאות |
|---|---|---|
| "יצא זוגי" | $A=\{2,4,6\}$ | 3 |
| "יצא מספר גדול מ-4" | $B=\{5,6\}$ | 2 |
| "יצא 3" | $\{3\}$ | 1 (גם תוצאה בודדת היא מאורע) |
| "יצא משהו" (כל תוצאה) | $\Omega$ | 6 |
| "יצא 7" (בלתי אפשרי) | $\emptyset$ (הקבוצה הריקה) | 0 |
"יצא זוגי" נשמע כמו משפט. אבל כשהופכים אותו לקבוצה של תוצאות, אפשר לספור. עכשיו "תדירות יחסית" הופכת ל"כמה תוצאות בקבוצה, מתוך כמה בסך הכל": בקובייה, "זוגי" תופס 3 מתוך 6, ולכן נצפה שבערך $3/6$ מההטלות יהיו זוגיות. זו הסיבה שהקבוצות כל כך שימושיות.
כשמטילים שתי קוביות, תוצאה היא זוג מספרים $(i,j)$: "הראשונה יצאה $i$, השנייה יצאה $j$". יש $6\cdot6=36$ תוצאות, ונוח לשרטט אותן בטבלה. כל תא הוא תוצאה אחת (שים לב: $(2,5)$ ו-$(5,2)$ הן שתי תוצאות שונות):
מה ראית: מאורע הוא קבוצה של תאים, וההסתברות שלו היא החלק היחסי של התאים המסומנים. למשל "הסכום הוא 7" תופס 6 תאים מתוך 36, ולכן ההסתברות שלו היא $6/36=1/6$. חישבת הסתברות בלי שום נוסחה, רק מספירת תאים. זה הרעיון המרכזי.
"בשתי קוביות יש 21 תוצאות: $\{1,1\},\{1,2\},\dots,\{6,6\}$ (בלי חשיבות לסדר), ולכן הסיכוי לסכום 3 הוא 1/21." לא נכון. שים לב מה קורה בטבלה: "אחת 1 ואחת 2" יכול לקרות בשתי דרכים, $(1,2)$ או $(2,1)$ (שני תאים), ואילו "שתיהן 1" בדרך אחת בלבד: $(1,1)$ (תא אחד). ל-21 האפשרויות אין אותה הסתברות, ולכן לא נכון לספור אותן כאילו הן שוות.
דמיין קובייה אדומה וקובייה כחולה. עכשיו ברור ש-$(1,2)$ ו-$(2,1)$ הן תוצאות שונות. כלל אצבע: בחר מרחב מדגם שבו התוצאות סימטריות זו לזו (כל התאים באותו "משקל"), כי אז הסתברות היא פשוט ספירה.
$\Omega$ הוא בחירה שלך כמודל, והוא צריך להיות עשיר מספיק כדי לענות על השאלות שלך. הטלת קובייה אפשר לתאר כ-$\{1..6\}$, או רק כ-$\{\text{זוגי},\text{אי-זוגי}\}$ אם זה כל מה שמעניין אותך. ב-ML זו בדיוק ההחלטה "מה ה-features והתוויות".
עוד כמה דוגמאות למרחבי מדגם (המקרים האינסופיים והרציפים מחכים לשיעור 3):
| ניסוי | מרחב מדגם $\Omega$ | גודל |
|---|---|---|
| מטבע | $\{H,T\}$ | 2 |
| שתי קוביות | זוגות $(i,j)$ | 36 |
| הטלות עד העץ הראשון | $\{1,2,3,\dots\}$ | אינסוף, אפשר למנות |
| זמן המתנה לאוטובוס | $[0,\infty)$ | אינסוף, רציף |
| בחירת תמונה מדאטהסט של $N$ תמונות | $\{1,\dots,N\}$ | $N$ |
תרגיל 2.1 כתיבת מאורע כקבוצה ⭐
בהטלת שתי קוביות, רשום במפורש את המאורעות הבאים כקבוצות של זוגות, וקבע כמה תוצאות בכל אחד: (א) הסכום הוא 5. (ב) הראשונה גדולה מהשנייה. (ג) הסכום קטן מ-2.
(א) $\{(1,4),(2,3),(3,2),(4,1)\}$: 4 תוצאות, סיכוי $4/36=1/9$.
(ב) כל זוג עם $i>j$: יש $\binom62=15$ כאלה (אפשר גם: מתוך 36, 6 שוות, ומחצית מ-30 הנותרות): $15/36=5/12$.
(ג) הסכום המינימלי הוא 2, לכן המאורע ריק: $\emptyset$, 0 תוצאות, סיכוי 0.
תרגיל 2.2 מציאת הטעות ⭐⭐
דני טוען: "מטילים שני מטבעות. יש 3 תוצאות אפשריות: שני עצים, שני פלי, או אחד מכל סוג. לכן הסיכוי ל'אחד מכל סוג' הוא 1/3." איפה הטעות, ומה התשובה הנכונה?
אותה טעות של לייבניץ: שלוש התוצאות שלו לא שוות-סיכוי. "אחד מכל סוג" מכסה שתי תוצאות סימטריות מתוך ארבע: $\{HH, HT, TH, TT\}$. הסיכוי הנכון: $2/4=1/2$. (תצבע את המטבעות!)
יש לנו שפה: תוצאות, מרחב מדגם, מאורע = קבוצה. אבל מאורעות אמיתיים הם מורכבים: "זוגי או גדול מ-4", "סכום 7 וגם הראשונה 6", "לא 6". איך כותבים כאלה? בעזרת פעולות על קבוצות.
❓ אם $A$ ו-$B$ מאורעות, מהם "$A$ או $B$", "$A$ וגם $B$", "לא $A$"?
נלך בשלבים: (1) ארבע פעולות על דוגמה קטנה, (2) מושג ה"זרים", (3) הפעולות על הטבלה של שתי קוביות, (4) הפעולות בציור כללי, (5) דה-מורגן.
מאחר שמאורע הוא קבוצה, כל שילוב הגיוני של מאורעות הוא פעולה על קבוצות. ניקח קובייה אחת: $\Omega=\{1,2,3,4,5,6\}$, ושני מאורעות:
כל התוצאות שנמצאות לפחות באחת מהקבוצות. ($\cup$ נראה כמו כוס שאוספת הכל.)
$A\cup B=\{2,4,5,6\}$. שים לב: "או" במתמטיקה הוא "או" מכליל: גם 6 נכלל, כי הוא ב-$A$ וגם ב-$B$. והוא נכתב פעם אחת בלבד (בקבוצה אין כפילויות).
התוצאות שנמצאות בשתי הקבוצות יחד. $A\cap B=\{6\}$ (רק 6 גם זוגי וגם גדול מ-4).
כל מה שב-$\Omega$ ולא ב-$A$. $A^c=\{1,3,5\}$ (אי-זוגי).
מה שב-$A$ ולא ב-$B$. $A\setminus B=\{2,4\}$ (זוגי, אבל לא גדול מ-4).
למתכנת זה מוכר: אותו דבר כמו or, and, not:
| סימון | שם | במילים | בקוד | בדוגמה |
|---|---|---|---|---|
| $A\cup B$ | איחוד | $A$ או $B$ | a or b | $\{2,4,5,6\}$ |
| $A\cap B$ | חיתוך | גם $A$ וגם $B$ | a and b | $\{6\}$ |
| $A^c$ | משלים | לא $A$ | not a | $\{1,3,5\}$ |
| $A\setminus B$ | הפרש | $A$ אבל לא $B$ | a and not b | $\{2,4\}$ |
שני מאורעות הם זרים (disjoint) אם אין להם אף תוצאה משותפת: $A\cap B=\emptyset$. כלומר אי אפשר ששניהם יקרו באותה הטלה. למשל "יצא זוגי" $\{2,4,6\}$ ו"יצא אי-זוגי" $\{1,3,5\}$ הם זרים. ("זוגי" ו"גדול מ-4" אינם זרים, כי 6 משותף.)
המושג הזה חשוב: בסעיף הבא נראה שרק מאורעות זרים אפשר פשוט "לחבר".
עכשיו נפעיל אותן על הטבלה של שתי קוביות (36 תאים). בחר שני מאורעות $A$ ו-$B$ ופעולה, וראה אילו תאים נדלקים:
ניסוי מודרך (שלוש דקות):
לא תמיד יש טבלה. לכן מציירים כך: המלבן הוא $\Omega$, העיגולים הם המאורעות $A$ ו-$B$, והאזור הכחול הוא התוצאה של הפעולה שבחרת:
נחזור לקובייה. $A=\{2,4,6\}$, $B=\{5,6\}$. נחשב "לא (זוגי או גדול מ-4)" בשתי דרכים:
אותה תשובה. זה לא מקרי:
במילים: "לא (גשם או שלג)" שווה ל"לא גשם וגם לא שלג". ו-"לא (גשם וגם שלג)" שווה ל"לא גשם או לא שלג". בקוד: not (a or b) == (not a) and (not b). הכלל לזכירה: הכנסת ה"לא" לתוך הסוגריים מחליפה "או" ב"וגם" ולהפך.
תרגיל 3.1 תרגום מילים לקבוצות ⭐
בקבוצת סטודנטים, $A$ = "עבר את מבחן המתמטיקה", $B$ = "עבר את מבחן הפיזיקה". רשום בעזרת $A,B$ ופעולות: (א) עבר לפחות אחד. (ב) עבר את שניהם. (ג) לא עבר אף אחד. (ד) עבר בדיוק אחד. (ה) נכשל בלפחות אחד.
(א) $A\cup B$. (ב) $A\cap B$. (ג) $(A\cup B)^c=A^c\cap B^c$. (ד) $(A\setminus B)\cup(B\setminus A)$ (שים לב שהשניים זרים). (ה) $(A\cap B)^c=A^c\cup B^c$.
שים לב איך (ג) ו-(ה) מקבלים שתי צורות שקולות בזכות דה-מורגן. תבחר את מה שנוח יותר לחישוב.
תרגיל 3.2 עובדה על גדלים של קבוצות ⭐
בטבלת הקוביות נתון: $|A|=18$ (הראשונה זוגית), $|B|=6$ (סכום ≥10), $|A\cap B|=4$. כמה תאים יש ב-$A\cup B$? ואיך זה מתקשר ל"ספירה כפולה"?
$|A\cup B|=18+6-4=20$. אם פשוט מחברים $18+6=24$, ארבעת התאים המשותפים נספרים פעמיים, אז מחסירים אותם פעם אחת. (נראה את זה בסעיף 4 כחוק הסתברות.)
תרגיל 3.3 הוכחה / אימות שקילות ⭐⭐
הוכח שהמאורעות $A\cup B$ ו-$A\cup(B\setminus A)$ הם אותו מאורע, ושהחלק השני הוא איחוד של שני מאורעות זרים. (הרעיון הזה ישמש אותנו בסעיף הבא.)
קח תוצאה כלשהי $\omega\in A\cup B$ ושאל: האם היא ב-$A$? אם לא, איפה היא?
אם $\omega\in A$ אז היא באיחוד הימני. אם $\omega\notin A$, אבל היא ב-$A\cup B$, אז היא חייבת להיות ב-$B$, כלומר ב-$B\setminus A$. בכיוון ההפוך כל אחד מ-$A$ ו-$B\setminus A$ מוכל ב-$A\cup B$. הזרות: $B\setminus A$ מכיל רק דברים שאינם ב-$A$, לכן $A\cap(B\setminus A)=\emptyset$.
הרעיון: אפשר לפרק איחוד לא-זר לחלקים זרים.
עכשיו יש לנו מאורעות מכל סוג. נחזור לשאלה מהסעיף הראשון: הסתברות היא "חלק יחסי". אילו חוקים חייב לקיים כל חלק יחסי, בלי קשר למה שאנחנו מודדים?
❓ ברור ש"חלק יחסי" מתנהג יפה. מה בדיוק ה"יפה" הזה, כך שאפשר יהיה לגזור ממנו הכל?
הסעיף הזה הולך בשלבים: (0) מה מחפשים, (1) שלוש תצפיות על הטבלה, (2) ניסוח רשמי, (3) איך מוכיחים דברים מהחוקים, (4) הטריק הכי שימושי.
עד עכשיו חישבנו הסתברות בספירת תאים בטבלת הקוביות. עכשיו נרצה כללים שנכונים לא רק לקוביות אלא לכל מצב. נסמן ב-$P$ "מכונת הסתברות": היא מקבלת מאורע (קבוצה) ומחזירה מספר. למשל:
$$P(\text{הסכום הוא }7)=\frac{6}{36}.$$נכתוב $P(A)$ ונקרא "ההסתברות של $A$". השאלה: אילו כללים חייבת לקיים כל מכונה כזו כדי שנוכל לקרוא לה "חלק יחסי"? נחפש אותם בטבלה.
תבדוק בעצמך: גלול למעבדת הקוביות בסעיף 3, בחר $A$ = "הסכום הוא 7", $B$ = "הסכום ≥ 10", ואז $A\cup B$. אחר כך החלף ל-$B$ = "הראשונה = 6", וראה את ההבדל.
קולמוגורוב (1933) הבין שהשלוש האלה הן כל מה שצריך. כל פונקציה $P$ שמקיימת אותן נקראת "הסתברות", בין אם היא נולדה מספירת תאים, מתדירויות או מאמונה:
הערות על הניסוח:
יש לנו רק שלושה כללים, והשלישי הוא היחיד שיודע לחבר. לכן יש טכניקה אחת שחוזרת בכל ההוכחות:
כשרוצים לחשב הסתברות של מאורע מסובך, מפרקים אותו לחלקים שלא חופפים, ומחברים את ההסתברויות שלהם באקסיומה 3. תראה: בכל אחד משלושת החוקים הבאים נעשה בדיוק את זה.
מה רוצים: לדעת את $P(\text{לא }A)$ כשידוע $P(A)$.
בדיקה בטבלה: $P(\text{סכום }7)=\frac6{36}$, ו"לא 7" תופס $30$ תאים: $\frac{30}{36}=1-\frac6{36}$ ✔.
(תוצאה נלווית: $P(\emptyset)=0$, כי $\emptyset=\Omega^c$ ולכן $P(\emptyset)=1-P(\Omega)=0$.)
מה רוצים: אם $A\subseteq B$ (כל תוצאה של $A$ היא גם תוצאה של $B$), אז $P(A)\le P(B)$. דוגמה: $A$ = "הסכום 12" (רק $(6,6)$), $B$ = "דאבל" (שתי הקוביות שוות). ברור ש-$A$ בתוך $B$.
בדיקה בטבלה: $P(A)=\frac1{36}\le P(B)=\frac6{36}$ ✔. (מכאן גם $P(A)\le1$ תמיד, כי כל מאורע מוכל ב-$\Omega$.)
מה רוצים: לחשב $P(A\cup B)$ גם כשהמאורעות חופפים. זה התיקון לבעיה שראינו בתצפית 3.
הרעיון: שני שטיחים שחופפים חלקית. שטח הרצפה שהם מכסים הוא $\text{שטח}_1+\text{שטח}_2$ פחות שטח החפיפה, כי החפיפה נספרה פעמיים. הנוסחה:
$$P(A\cup B)=P(A)+P(B)-P(A\cap B).$$הוכחה בשני שלבים:
בדיקה בטבלה: $A$ = "הראשונה זוגית" (18 תאים), $B$ = "הסכום ≥ 10" (6 תאים), החיתוך 4 תאים. $\frac{18}{36}+\frac{6}{36}-\frac{4}{36}=\frac{20}{36}$, וזה בדיוק מספר התאים באיחוד ✔.
| החוק | במילים | מקור |
|---|---|---|
| $P(A)\ge0$ | אין הסתברות שלילית | אקסיומה 1 |
| $P(\Omega)=1$ | משהו קורה בוודאות | אקסיומה 2 |
| $P(A\cup B)=P(A)+P(B)$ כש-$A,B$ זרים | זרים: מחברים | אקסיומה 3 |
| $P(A^c)=1-P(A)$ | "לא" = 1 פחות | חוק ① |
| $A\subseteq B\Rightarrow P(A)\le P(B)$ | קטן בתוך גדול | חוק ② |
| $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ | חפיפה נספרת פעמיים | חוק ③ |
נניח שהשאלה היא "מה הסיכוי שיקרה לפחות אחד מ..." ("לפחות אחד" פירושו אחד, או שניים, או שלושה, או יותר). ספירה ישירה של כל המקרים עמוסה. אבל "לפחות אחד" ו"אף אחד" הם זה ההפך של זה, ולכן לפי חוק ①:
$$P(\text{לפחות אחד})=1-P(\text{אף אחד}).$$ו"אף אחד" הוא בדרך כלל מקרה אחד פשוט. המתכון:
שאלה: מטילים קובייה 4 פעמים. מה הסיכוי ל"לפחות פעם אחת 6"?
(1) ההפך: "אף פעם לא יצא 6" (בכל 4 ההטלות יצא משהו מ-1 עד 5).
(2) חישוב "אף פעם לא 6" בספירה. נתחיל מקטן: שתי הטלות. יש $6\cdot6=36$ תוצאות (הטבלה שלנו), ובלי 6 בכלל יש $5\cdot5=25$ מהן (הטבלה ללא השורה והעמודה של 6). לכן הסיכוי הוא $\frac{25}{36}=\left(\frac56\right)^2$. אותו דבר עבור 4 הטלות: $6^4=1296$ תוצאות בסך הכל, ובלי 6 יש $5^4=625$. לכן $P(\text{אף פעם לא 6})=\frac{625}{1296}=\left(\frac56\right)^4\approx0.482$.
(3) החסרה: $P(\text{לפחות פעם 6})=1-\frac{625}{1296}=\frac{671}{1296}\approx0.518$.
מחוק ③ נובע $P(A\cup B)\le P(A)+P(B)$, כי מה שמחסירים ($P(A\cap B)$) אינו שלילי. אז "סכום ההסתברויות" הוא תמיד חסם עליון להסתברות של "לפחות אחד". זה שימושי כשאי אפשר לחשב את החפיפה. למשל: 100 מודלים, ולכל אחד סיכוי של 0.1% להיכשל בצורה חמורה. הסיכוי שלפחות אחד נכשל הוא לכל היותר $100\cdot0.1\%=10\%$, בלי לדעת איך הכישלונות קשורים זה לזה. זו "חסם האיחוד" (union bound), ותראה אותו בהוכחות בתורת הלמידה.
במרחבים רציפים כמו $[0,1]$ קיימות קבוצות "פתולוגיות" שאי אפשר להקצות להן אורך בצורה עקבית. לכן ההגדרה הפורמלית דורשת שהמאורעות יגיעו ממשפחה $\mathcal F$ סגורה למשלים ולאיחודים בני-מניה (σ-אלגברה), והשלשה $(\Omega,\mathcal F,P)$ נקראת מרחב הסתברות. בקורס ML אפשר לשכוח מזה, אבל עכשיו אתה יודע מה הסימון בספר.
תרגיל 4.1 הכלה והפרדה במספרים ⭐
נתון $P(A)=0.5$, $P(B)=0.4$, $P(A\cap B)=0.2$. חשב: $P(A\cup B)$, $P(\text{אף אחד})$, $P(A\setminus B)$.
$P(A\cup B)=0.5+0.4-0.2=0.7$. אף אחד: $1-0.7=0.3$. $P(A\setminus B)=P(A)-P(A\cap B)=0.3$ (מפרקים $A=(A\setminus B)\cup(A\cap B)$, זרים).
תרגיל 4.2 בדיקת שפיות (האם זה אפשרי?) ⭐
האם יתכן $P(A)=0.3$, $P(B)=0.5$ ו-$P(A\cap B)=0.4$?
לא. $A\cap B\subseteq A$, ולכן (מונוטוניות) $P(A\cap B)\le P(A)=0.3<0.4$. כללי אצבע לבדיקה: חיתוך לא עולה על אף אחד מהמאורעות, ואיחוד לא קטן מאף אחד מהם.
תרגיל 4.3 מציאת הטעות + חסם תחתון ⭐⭐
סיכוי הגשם בשבת הוא 0.6 ובראשון 0.7. תלמידה טוענת: "אז סיכוי הגשם לפחות באחד מהימים הוא $0.6+0.7=1.3$." (א) למה זה לא יכול להיות? (ב) מה אפשר לומר על ההסתברות שירד גשם בשני הימים?
הכלה והפרדה, ושים לב שהאיחוד חייב להיות ≤ 1.
(א) היא סכמה כאילו המאורעות זרים, אבל ייתכן שגשם בשבת וגם בראשון, ואז הסיכוי נספר פעמיים. הסכום יצא יותר מ-1, וזו סתירה לאקסיומות.
(ב) $1\ge P(A\cup B)=1.3-P(A\cap B)$, לכן $P(A\cap B)\ge 0.3$. כלומר, בלי לדעת שום דבר נוסף, בהכרח ירד גשם בשני הימים בסיכוי של לפחות 30%. (והחסם החד: $P(A\cap B)\le\min(0.6,0.7)=0.6$.)
תרגיל 4.4 הוכחה: פירוק לזרים ⭐⭐
הוכח, רק מהאקסיומות, ש-$P(A\cup B)\le P(A)+P(B)$ לכל שני מאורעות (לאו דווקא זרים).
$A\cup B=A\cup(B\setminus A)$, איחוד זר (תרגיל 3.3). לכן $P(A\cup B)=P(A)+P(B\setminus A)$. ומכיוון ש-$B\setminus A\subseteq B$, מונוטוניות נותנת $P(B\setminus A)\le P(B)$. סיימנו.
תרגיל 4.5 טריק המשלים (בעיית שבלייה דה-מרה, 1654) ⭐⭐
(א) מטילים קובייה 4 פעמים. סיכוי ל"לפחות פעם אחת 6"? (ב) מטילים זוג קוביות 24 פעמים. סיכוי ל"לפחות פעם אחת (6,6)"? איזה הימור משתלם?
(א) $1-(5/6)^4\approx 0.518$. (ב) בהטלה אחת של זוג, סיכוי ל-(6,6) הוא $1/36$, ולכן ל"לא": $35/36$. התשובה: $1-(35/36)^{24}\approx 0.491$.
הראשון מעל חצי (משתלם), והשני מתחת (מפסיד). דה-מרה ציפה לאותה תוצאה כי "4 מתוך 6 דומה ל-24 מתוך 36", אבל הסתברות לא גדלה לינארית. (מזה נולדה ההסתברות כתחום: הוא כתב לפסקל, ופסקל לפרמה.)
יש לנו חוקים. אבל כדי להפעיל אותם צריך לדעת ערכים: כמה זה $P(A)$? במקרה הכי נפוץ (כל התוצאות שוות-סיכוי) התשובה היא "ספור".
❓ אם כל התוצאות שוות-סיכוי, איך מחשבים את $P(A)$? ואיך סופרים כשיש מיליוני תוצאות ואי אפשר לצייר טבלה?
נלך בשלבים: (0) מה הבעיה, (1) עיקרון הכפל, (2) כשהסדר חשוב, (3) כשהסדר לא חשוב, (4) הסתברות באמצעות ספירה, (5) טעויות נפוצות.
נניח שיש $N$ תוצאות שוות-סיכוי. מהאקסיומות: כל אחת מהן מקבלת אותה הסתברות $p$, והסכום של כולן הוא 1 (אקסיומה 2, ואקסיומה 3 לחיבור). לכן $N\cdot p=1$, כלומר $p=1/N$. בקובייה: $N=6$ וכל תוצאה מקבלת $1/6$. מאורע שיש בו $k$ תוצאות מקבל $k\cdot\frac1N$:
$$P(A)=\frac{|A|}{|\Omega|}=\frac kN.$$($|A|$ פירושו "מספר האיברים ב-$A$".) למשל "זוגי" בקובייה: $|A|=3$, $|\Omega|=6$, ולכן $3/6$. זו בדיוק הספירה של התאים בטבלה.
הבעיה: מה אם $\Omega$ ענק? ב-"5 קלפים מחפיסה של 52" יש 2,598,960 תוצאות. אי אפשר לרשום אותן. צריך לספור בלי לרשום, וזה מה שהשלבים הבאים מלמדים.
יש לי 3 חולצות ו-2 מכנסיים. כמה תלבושות אפשריות? כל חולצה אפשר לשלב עם כל מכנס, ולכן $3\cdot2=6$. בטבלה:
| מכנס א | מכנס ב | |
|---|---|---|
| חולצה 1 | 1א | 1ב |
| חולצה 2 | 2א | 2ב |
| חולצה 3 | 3א | 3ב |
אם תהליך מורכב משני שלבים, ובשלב הראשון יש $a$ אפשרויות ובשני $b$ אפשרויות (לכל בחירה בשלב הראשון), אז בסך הכל $a\cdot b$. (יש $a$ שורות, ובכל שורה $b$ תאים.) זה נכון גם לכמה שלבים: מכפילים את כולם.
דוגמאות: שתי קוביות $6\cdot6=36$ (זה ה-$|\Omega|$ שלנו!). סיסמה של 4 ספרות: $10\cdot10\cdot10\cdot10=10^4$.
בתחרות ריצה של 5 רצים מחלקים מדליית זהב, כסף וארד. כמה דרכים? קודם בוחרים מי הזהב: 5 אפשרויות. אחר כך הכסף: נשארו 4 (אותו רץ לא יכול לקבל שתי מדליות). אחר כך הארד: 3. לפי עיקרון הכפל: $5\cdot4\cdot3=60$.
כדי לכתוב זאת בקיצור משתמשים בעצרת (factorial): $n!=n\cdot(n-1)\cdot(n-2)\cdots2\cdot1$. למשל $5!=120$, ובהגדרה $0!=1$. אז:
$$5\cdot4\cdot3=\frac{5\cdot4\cdot3\cdot2\cdot1}{2\cdot1}=\frac{5!}{2!}=\frac{5!}{(5-3)!}.$$והכלל הכללי: בוחרים $k$ פריטים מתוך $n$, בסדר חשוב וללא החזרה:
$$n\cdot(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$עכשיו אותה בחירה, אבל לא לפי תפקיד: בוחרים ועדה של 3 אנשים מתוך 5, וכל השלושה שווים. הסדר לא משנה. קודם נתחיל בדוגמה קטנה כדי להבין את הרעיון: בחירת 2 מתוך $\{A,B,C\}$.
כל קבוצה של 2 נספרה פעמיים בספירה עם סדר ($AB$ ו-$BA$ הן אותה קבוצה). לכן $6\div2=3$.
באותו אופן, בחירת 3 מתוך 5: עם סדר יש 60. כל ועדה של 3 אנשים נספרה $3!=6$ פעמים (כל הסדרים האפשריים של שלושה אנשים). לכן $60\div6=10$.
זה מספר הדרכים לבחור קבוצה של $k$ איברים מתוך $n$, בלי חשיבות לסדר. הסבר הנוסחה: $\frac{n!}{(n-k)!}$ הוא הספירה עם סדר, ומחלקים ב-$k!$ כי כל קבוצה נספרה $k!$ פעמים.
למשל $\binom53=\frac{5!}{3!\,2!}=\frac{120}{6\cdot2}=10$ ✔.
כשקשה לספור ישירות, ספור משהו קל שסופר כל פריט אותו מספר פעמים, ואז חלק בגורם הזה. כך קיבלנו את $\binom nk$, וכך נפתור את תרגיל 5.5 (אנגרמות).
$\binom nk=\binom n{n-k}$. הסיבה: לבחור $k$ שנכנסים לוועדה זה אותו דבר כמו לבחור $n-k$ שנשארים בחוץ. למשל $\binom53=\binom52=10$. אם $k$ גדול, חשב עם $n-k$.
ומקרה נוסף שכבר פגשנו: עם החזרה (אפשר לבחור שוב את אותו פריט). בכל בחירה יש $n$ אפשרויות, לכן $n^k$ בסדר חשוב. זה המקרה של הטלות קובייה ($6^k$) וסיסמאות.
דוגמה קטנה (אפשר לרשום הכל): מטילים מטבע 3 פעמים. מה הסיכוי לבדיוק 2 עצים? יש $2^3=8$ רצפים שוות-סיכוי: HHH, HHT, HTH, THH, HTT, THT, TTH, TTT. אלה עם בדיוק 2 עצים (H): HHT, HTH, THH, כלומר 3 רצפים. לכן $3/8$.
אותה שאלה בלי לרשום: רצף עם בדיוק 2 עצים נקבע על ידי באילו 2 מקומות מתוך 3 יושב העץ. זו בחירה של 2 מקומות מתוך 3, בלי סדר: $\binom32=3$. אותה תשובה.
כמה מחרוזות בינאריות באורך $n$ יש עם בדיוק $k$ אחדות? מספיק לדעת באילו מקומות האחדות יושבות: $\binom nk$. את זה נראה שוב בהתפלגות הבינומית.
דוגמה בגודל אמיתי: מקבלים 5 קלפים מחפיסה של 52. מה הסיכוי שכולם לב? כל הידיים: $\binom{52}{5}=2{,}598{,}960$ (בוחרים 5 קלפים בלי סדר). ידיים שכולן לב: $\binom{13}{5}=1287$ (בוחרים 5 מתוך 13 הלבבות). לכן $\frac{1287}{2598960}\approx0.0005$, כלומר בערך 1 ל-2,000.
בחירת $k$ פריטים מתוך $n$ סוגים כשאפשר לחזור על סוג, והסדר לא חשוב (למשל 5 כדורי גלידה מ-3 טעמים): $\binom{n+k-1}{k}$ (שיטת "כוכבים וקווים"). נפגוש את זה רק מעט, אז אפשר לדלג. הסבר מלא עם מעבדה וקישור ל-ML בנספח א1.
ספירה מסבירה למה בעיות ML קשות: יש $2^d$ קבוצות חלקיות של $d$ פיצ'רים, ולכן בחירת פיצ'רים בכוח גס בלתי-אפשרית כבר ב-$d=50$ ($2^{50}\approx10^{15}$). מספר הפונקציות הבוליאניות על $d$ ביטים הוא $2^{2^d}$. מכאן החשיבות של הנחות על המבנה (inductive bias).
תרגיל 5.1 עיקרון הכפל + משלים ⭐
מטילים מטבע 5 פעמים. (א) כמה תוצאות יש? (ב) מה הסיכוי ל"לפחות עץ אחד"?
(א) $2^5=32$. (ב) משלים: "אף עץ" = תוצאה אחת (TTTTT), לכן $1-1/32=31/32$.
תרגיל 5.2 בחר מקומות ⭐
מטילים מטבע הוגן 5 פעמים. מה הסיכוי לבדיוק 2 עצים?
כל רצף הוא תוצאה שוות-סיכוי. כמה רצפים באורך 5 יש עם בדיוק שני עצים?
מספר הרצפים עם בדיוק 2 עצים: בוחרים באילו 2 מקומות מתוך 5 מופיע עץ: $\binom52=10$. לכן $10/32=5/16\approx0.31$.
תרגיל 5.3 סדר חשוב, עם / בלי החזרה ⭐⭐
סיסמה אקראית של 8 אותיות קטנות (26 אותיות, חזרות מותרות). מה הסיכוי שכל האותיות שונות?
כל הסיסמאות: $26^8\approx 2.09\cdot10^{11}$. סיסמאות עם אותיות שונות (סדר חשוב, בלי החזרה): $26\cdot25\cdots19=\frac{26!}{18!}\approx6.30\cdot10^{10}$. היחס: $\approx 0.30$. (בלי לדמות את זה בראש: שימו לב שזה כבר מזכיר את יום ההולדת בסעיף 6.)
תרגיל 5.4 מציאת הטעות (ספירה כפולה) ⭐⭐
מחפיסה של 52 קלפים בוחרים 5 קלפים. סטודנט מחשב את מספר הידיים שיש בהן "לפחות אס" כך: "בוחרים אס ($4$ דרכים), ואז עוד 4 קלפים מ-51: $\binom{51}{4}$, סה"כ $4\binom{51}{4}$." למה זה שגוי? ואיך מחשבים נכון?
יד עם שני אסים: כמה פעמים היא נספרת בחישוב שלו? ומה כוח המשלים?
יד עם 2 אסים נספרת פעמיים (כל אחד מהם יכול להיות "האס שבחרתי"), יד עם 3 אסים שלוש פעמים וכו'. נכון: משלים. ידיים בלי אף אס: $\binom{48}{5}=1{,}712{,}304$ מתוך $\binom{52}{5}=2{,}598{,}960$. לכן $P(\text{לפחות אס})=1-\frac{1712304}{2598960}\approx 0.341$.
תרגיל 5.5 ספור עם עודף, ואז חלק (אתגר) ⭐⭐⭐
כמה מילים שונות אפשר ליצור מסידור כל האותיות של MISSISSIPPI? (יש שם: M פעם אחת, I ארבע פעמים, S ארבע פעמים, P פעמיים.)
דמיין שכל האותיות שונות (I₁,I₂,...). כמה סידורים יש אז? כמה מהם מייצרים את אותה מילה בפועל?
כשהאותיות "צבועות", יש $11!$ סידורים. כל מילה אמיתית נספרה $4!\cdot4!\cdot2!$ פעמים (הסדרים הפנימיים של האותיות החוזרות). לכן: $\dfrac{11!}{4!\,4!\,2!}=34{,}650$.
יש לנו חוקים וכלי חישוב. לפני שנשתמש בהם ב-ML, נבדוק שהם עומדים במבחן המציאות: האם התשובות מתיישבות עם האינטואיציה? לפעמים לא, וזה כשהכי מרוויחים.
❓ בכיתה של 23 אנשים, מה הסיכוי שלשניים יש יום הולדת באותו יום?
נלך בשלבים: (0) הגדרת הבעיה, (1) ניחוש, (2) חישוב בשלוש דוגמאות קטנות, (3) הנוסחה, (4) ניסוי חי, (5) למה זה מפתיע.
כדי שהשאלה תהיה מדויקת, נניח: יש 365 ימים בשנה (בלי 29 בפברואר), וכל אדם נולד בכל יום בסיכוי שווה, ללא קשר לאחרים. "יש התאמה" פירושו שלפחות שני אנשים נולדו באותו יום.
לפני שמחשבים: כמה היית מנחש? רוב האנשים אומרים 5%–10%. נבדוק.
נשתמש בכלים שיש לנו:
לכן: $$P(\text{כל הימים שונים})=\frac{365\cdot364\cdot363}{365\cdot365\cdot365}=\frac{365}{365}\cdot\frac{364}{365}\cdot\frac{363}{365}\approx0.992.$$ ולכן הסיכוי להתאמה בשלושה אנשים הוא $1-0.992=0.008$, פחות מאחוז.
אותו חישוב עם $n$ אנשים: במונה $365\cdot364\cdots(365-n+1)$, ובמכנה $365^n$. אפשר לכתוב כמכפלה של שברים (כל שבר הוא "בחירה של אדם חדש"):
$$P(\text{אין התאמה})=\prod_{i=0}^{n-1}\Big(1-\frac{i}{365}\Big)\ ,\qquad P(\text{יש התאמה})=1-\prod_{i=0}^{n-1}\Big(1-\frac{i}{365}\Big).$$($\prod$ הוא סימון למכפלה, כמו ש-$\sum$ הוא לסכום: $\prod_{i=0}^{n-1}$ פירושו "הכפל את הביטוי עבור $i=0,1,\dots,n-1$". עבור $i=0$ השבר הוא $\frac{365}{365}$, עבור $i=1$ הוא $\frac{364}{365}$, וכן הלאה.)
האינטואיציה שואלת "האם מישהו חולק איתי יום הולדת?", וזה רק 22 השוואות. אבל השאלה האמיתית היא על כל זוג בכיתה: יש $\binom{23}{2}=253$ זוגות (בחירת 2 מתוך 23, בלי סדר: ספירה מהסעיף הקודם). מספר הזוגות גדל ריבועית עם $n$, ולכן ההסתברות מזנקת מהר.
אותה תופעה גורמת להתנגשויות hash (feature hashing) ולדליפת נתונים בין train ל-test: בדאטהסט גדול מספר הזוגות עצום, ושכפולים כמעט-זהים כמעט מובטחים.
תרגיל 6.2 סימולציה והרחבה ⭐⭐
כתוב סימולציה שמאמתת שב-23 אנשים הסיכוי להתאמה הוא כ-0.507. אחר כך שנה אותה כדי להעריך את הסיכוי לשלושה אנשים עם אותו יום הולדת. האם הוא קרוב ל-0.507?
import numpy as np
rng = np.random.default_rng(0)
def has_match(n):
b = rng.integers(0, 365, size=n)
return len(set(b)) < n
def has_triple(n):
b = rng.integers(0, 365, size=n)
return np.bincount(b).max() >= 3
print(np.mean([has_match(23) for _ in range(100_000)])) # ~0.507
print(np.mean([has_triple(23) for _ in range(100_000)])) # ~0.013
שלישייה נדירה הרבה יותר (כ-1.3%). צריך 88 אנשים כדי לעבור 50%. לא מנחשים ב"אינטואיציה"; מחשבים או מדמים.
סגרנו את המעגל עם חשבון שמתיישב עם המציאות. נשאר לחבר את זה למה שבאת ללמוד: איפה כל זה חי ב-ML?
❓ מסווג מחזיר "חתול: 90%". מאיפה המספר הזה בא, והאם הוא באמת "הסתברות"?
הסעיף הזה הולך לאט, בשלבים. אם שלב לא ברור, עצור שם לפני שאתה ממשיך.
סיווג (classification) היא אחת המשימות הכי נפוצות ב-ML. נותנים למחשב קלט, למשל תמונה, והוא צריך לשייך אותו לאחת מכמה קטגוריות שהוגדרו מראש. למשל: האם בתמונה יש חתול, כלב או ארנב?
מנקודת המבט של המודל, המחלקה האמיתית של התמונה היא לא ידועה. יש שלוש אפשרויות, בדיוק כמו שלוש תוצאות של ניסוי מקרי. כלומר: $\Omega=\{\text{חתול},\text{כלב},\text{ארנב}\}$.
המודל רוצה לדווח "כמה הוא מאמין בכל אפשרות". כלומר לתת לכל תוצאה ב-$\Omega$ מספר: $p_{\text{חתול}},\,p_{\text{כלב}},\,p_{\text{ארנב}}$. כדי שהמספרים האלה יהיו "הסתברויות" במובן של סעיף 4 (כשיש מספר סופי של תוצאות), מספיקות שתי דרישות:
(ואז ההסתברות של מאורע כמו "חתול או כלב" היא פשוט סכום ההסתברויות של תוצאותיו, כי תוצאות שונות הן מאורעות זרים, והאקסיומה השלישית.)
בפנים, המודל (למשל רשת נוירונים) מבצע המון חישובים על התמונה, ובסוף מוציא רשימה של $K$ מספרים, אחד לכל מחלקה. נקרא להם ציונים (בז'רגון: logits) ונסמן $z_1,z_2,\dots,z_K$. הסימון $z_i$ פירושו "הציון של מחלקה מספר $i$".
למשל, על תמונה מסוימת המודל מחזיר:
| מחלקה | חתול | כלב | ארנב |
|---|---|---|---|
| ציון $z$ | 2.0 | 1.0 | 0.1 |
המשמעות: ציון גבוה יותר = "התמונה דומה יותר למחלקה הזו". כאן "חתול" מוביל.
הציונים יכולים להיות שליליים (למשל $-3$), יכולים להיות גדולים (כמו 17), והסכום שלהם הוא סתם מספר. הסתברות לא יכולה להיות שלילית, ולא יכולה להיות 17. בטבלה למעלה הסכום הוא $3.1$ ולא $1$. אז צריך ממיר שהופך כל רשימת ציונים לרשימה של הסתברויות, ושומר על הסדר (ציון גבוה ⟹ הסתברות גבוהה).
נבנה אותו עם הציונים $(2.0,\;1.0,\;0.1)$:
מחשבים $e^{z}$ לכל ציון. ($e\approx2.718$ הוא קבוע מתמטי; חשוב רק שהפונקציה $e^x$ תמיד חיובית, גם עבור $x$ שלילי, ושהיא עולה: ציון גבוה יותר נותן תוצאה גבוהה יותר.)
| חתול | כלב | ארנב | |
|---|---|---|---|
| $z$ | 2.0 | 1.0 | 0.1 |
| $e^{z}$ | 7.39 | 2.72 | 1.11 |
עכשיו כל המספרים חיוביים (דרישה 1 ✔), אבל הסכום הוא בערך $11.2$, עדיין לא 1.
מחלקים כל מספר בסכום של כולם: $7.39+2.72+1.11\approx11.2$.
| חתול | כלב | ארנב | סכום | |
|---|---|---|---|---|
| $e^{z}$ | 7.39 | 2.72 | 1.11 | ≈11.2 |
| חלקי הסכום | 0.659 | 0.242 | 0.099 | 1.000 |
הסכום הוא בדיוק 1 (דרישה 2 ✔), כי חילקנו כל חלק בסכום החלקים. זה כל ה-softmax.
צעד א נותן לכל מחלקה "גודל נתח". צעד ב לוקח את העוגה כולה (הסכום) ושואל: איזה חלק יחסי מהעוגה כל מחלקה קיבלה? זה בדיוק "חלק יחסי" מסעיף 1, והסיבה שהתוצאה מתנהגת כמו הסתברות. "חתול" קיבל 65.9% מהעוגה.
עכשיו נכתוב את זה בנוסחה. כל מה שעשינו הוא:
$$p_i=\frac{e^{z_i}}{e^{z_1}+e^{z_2}+\cdots+e^{z_K}}=\frac{e^{z_i}}{\sum_{j=1}^K e^{z_j}}.$$המונה: הנתח של מחלקה $i$ (צעד א). המכנה: סכום כל הנתחים (הסימון $\sum_{j=1}^K$ פירושו "תחבר את הביטוי עבור $j=1$, $j=2$, ... עד $j=K$"). החלוקה: צעד ב.
בדוק את שתי הדרישות מהתיבה למעלה, עבור כל ציונים אפשריים:
לכן הפלט של softmax מקיים את אקסיומות קולמוגורוב (למרחב סופי), וכל מה שלמדנו בשיעור חל עליו: למשל, ההסתברות ש"זה חתול או כלב" היא $p_{\text{חתול}}+p_{\text{כלב}}=0.659+0.242=0.901$, ובטריק המשלים: $1-p_{\text{ארנב}}=1-0.099$.
שאלה מצוינת, והתשובה הכנה: אפשר. כל פונקציה חיובית ועולה הייתה מקיימת את שתי הדרישות. מה שלא עובד: הרמה בריבוע (ציון $-3$ יקבל יותר מציון $+1$, והסדר מתקלקל) או סתם חילוק בסכום הציונים (ציונים שליליים נותנים הסתברות שלילית). $e^x$ נבחרה כי יש לה תכונה נוספת נוחה (ההפרשים בלבד קובעים, כפי שראית עם הכפתור), וכי היא מתחברת בטבעיות ל-log-likelihood ולנגזרות פשוטות. את זה נבין לעומק בשיעורים 8 ו-10, ובינתיים מספיק לדעת שזו הבחירה הסטנדרטית.
כאן חוזרת השאלה מתחילת השיעור: מהי הסתברות? לפי הפרשנות התדירותית (סעיף 1), "90%" אמור להיות חלק יחסי בטווח הארוך.
דמיין שנתת למודל 1,000 תמונות, ובכל אחת מהן הוא דיווח "חתול: 90%". אם הוא "אומר אמת", בערך 900 מהן צריכות להיות באמת חתולים. אם רק 700 הן חתולים, המודל בטוח בעצמו יותר מדי, והסתברויות הפלט שלו חוקיות (האקסיומות מתקיימות) אבל לא נכונות. מודל שבו המספרים אכן תואמים לחלקים היחסיים האמיתיים נקרא מכויל (calibrated).
האקסיומות אומרות רק שהמספרים חוקיים (לא שליליים וסכומם 1). האם הם נכונים זו שאלה אחרת, אמפירית, וניתנת לבדיקה: בודקים אם החלק היחסי שמתקבל בפועל תואם למה שהמודל טען.
import numpy as np
z = np.array([2.0, 1.0, 0.1]) # הציונים של 3 המחלקות (חתול, כלב, ארנב)
e = np.exp(z) # צעד א: e^z לכל ציון -> [7.39, 2.72, 1.11]
p = e / e.sum() # צעד ב: חלוקה בסכום -> [0.659, 0.242, 0.099]
print(p) # ההסתברויות
print(p.sum()) # 1.0 : מקיים את נרמול
print(p[0] + p[1]) # P(חתול או כלב) = 0.901 : אדיטיביות
print(1 - p[2]) # אותו דבר, בטריק המשלים
| מה שלמדנו עכשיו | מופיע ב-ML כ... |
|---|---|
| הסתברות = חלק יחסי | calibration, ו-accuracy כממוצע של אינדיקטור |
| מרחב מדגם, מאורע = קבוצה | מרחב הדוגמאות/התוויות, "המודל טעה" |
| אקסיומות | למה softmax ו-sigmoid הם התפלגויות תקפות |
| טריק המשלים | $1-\text{accuracy}=\text{error}$; "סיכוי לטעות לפחות פעם אחת" |
| חסם האיחוד | הוכחות בתורת הלמידה |
| ספירה | גודל מרחב ההשערות, מספר הדגימות האפשריות |
תרגיל 7.1 חישוב softmax ⭐
מסווג נתן logits $z=(1,\,1,\,1)$. מה ה-softmax? ומה אם $z=(10,\,0,\,0)$? מה רואים על יחס בין ה-logits לבין ההסתברויות?
$(1,1,1)$: שלושה ערכים שווים, ולכן $p=(1/3,1/3,1/3)$. $(10,0,0)$: $e^{10}\approx22026$, והאחרים 1: $p\approx(0.9999,\,0.00005,\,0.00005)$. שים לב: רק ההפרשים בין ה-logits חשובים (הוספת אותו קבוע לכולם לא משנה את התוצאה), וגדל ההפרש ⟹ ההתפלגות חדה יותר.
תרגיל 7.2 פרשנות (calibration) ⭐⭐
מודל נתן הסתברות 0.8 ל"חתול" ב-500 תמונות, ו-350 מהן באמת חתולים. (א) מה היית מצפה אם המודל מכויל? (ב) מה המשמעות של התוצאה?
(א) כ-$0.8\cdot500=400$ חתולים. (ב) התקבלו 350 (70%), פחות מהצפוי: המודל בטוח בעצמו יתר על המידה (overconfident), תופעה שכיחה ברשתות עמוקות. החלק היחסי שבפועל הוא ההסתברות ה"אמיתית" לפי הפרשנות התדירותית.
עכשיו בלי כותרת של טכניקה: תחליט בעצמך איזה כלי מתאים. (הטכניקה כתובה בתוך הפתרון.)
תרגיל מ.1 ⭐⭐
מטילים מטבע הוגן 10 פעמים. מה הסיכוי שמספר העצים זוגי?
אל תחשב את $\binom{10}{0}+\binom{10}{2}+\cdots$ בכוח. חשוב על סימטריה: מה קורה אם הופכים את תוצאת ההטלה הראשונה?
טכניקה: סימטריה / התאמה חח"ע. הפיכת ההטלה הראשונה (H↔T) מחליפה זוגיות של מספר העצים, וממפה תוצאות לתוצאות שונות באופן הפיך. לכן מספר הרצפים עם מספר זוגי של עצים שווה למספר הרצפים עם מספר אי-זוגי: $512$ מתוך $1024$. התשובה: $1/2$. (ובכוח: $\sum_{k\text{ זוגי}}\binom{10}{k}=2^9=512$.)
תרגיל מ.2 ⭐⭐
סטודנט עונה על 4 שאלות אמריקאיות (4 תשובות בכל שאלה) בניחוש. מה הסיכוי שיצליח בלפחות שאלה אחת?
טכניקה: משלים. סיכוי לטעות בשאלה: $3/4$. לטעות בכולן: $(3/4)^4=81/256$. לפחות הצלחה אחת: $1-81/256=175/256\approx0.68$.
תרגיל מ.3 (אתגר) ⭐⭐⭐
ארבעה אנשים מניחים את הכובעים בערימה, וכל אחד מקבל כובע אקראי בחזרה (תמורה אקראית). מה הסיכוי שאף אחד לא קיבל את הכובע שלו?
הגדר $A_i$ = "אדם $i$ קיבל את הכובע שלו". אתה רוצה $1-P(A_1\cup A_2\cup A_3\cup A_4)$. הכללה של הכלה והפרדה לארבעה מאורעות היא: סכום היחידים, פחות סכום הזוגות, ועוד סכום השלשות, פחות הרביעיה.
טכניקה: הכלה והפרדה בהכללה + ספירה. $P(A_i)=3!/4!=1/4$ (4 מקרים); $P(A_i\cap A_j)=2!/4!=1/12$ (6 זוגות); $P(A_i\cap A_j\cap A_k)=1/24$ (4 שלשות); הרביעיה $1/24$. לכן $$P(\cup)=4\cdot\tfrac14-6\cdot\tfrac1{12}+4\cdot\tfrac1{24}-\tfrac1{24}=\tfrac{15}{24},\qquad P(\text{אף אחד})=\tfrac{9}{24}=\tfrac38.$$ כשמגדילים את מספר האנשים, התוצאה מתקרבת ל-$e^{-1}\approx0.368$. תוצאה מפתיעה: כמעט לא תלוי ב-$n$!
תרגיל מ.4 (קוד) ⭐⭐
אמת את תרגיל מ.3 בעזרת סימולציה: ערבב את הרשימה [0,1,2,3] אקראית פעמים רבות, וחשב באיזה חלק מהמקרים אין "נקודת קבע" ($\pi(i)=i$).
import numpy as np
rng = np.random.default_rng(0)
def derangement():
p = rng.permutation(4)
return not np.any(p == np.arange(4))
print(np.mean([derangement() for _ in range(200_000)])) # ~0.375 = 3/8כל מה שעשינו הניח שאין לנו שום מידע. מה קורה כשמקבלים מידע חדש ("ידוע שהסכום זוגי, מה הסיכוי שיצא 6?")? זו הסתברות מותנית, וממנה נגיע גם לאי-תלות (הסיבה הכללית לכך ש-(5/6)⁴ הוא מכפלה, שראינו בסעיף 4 דרך ספירה) ולמשפט בייס, הלב של סיווג ב-ML.