ממאורעות למספרים: משתנה מקרי, פונקציית הסתברות (PMF), טור הנדסי, התפלגות גיאומטרית, פונקציית התפלגות מצטברת (CDF), דגימה, ו-softmax עם טמפרטורה. זמן משוער: כ-2.5 שעות כולל התרגול.
בשיעורים 1–2 דיברנו על מאורעות: "יצא זוגי", "הבדיקה חיובית". אבל בפועל מה שמעניין אותנו הוא לא רק "האם קרה משהו", אלא מספרים: הסכום של שתי קוביות, מספר העצים ב-10 הטלות, כמה צעדים עד שהמודל מסיים משפט. בשיעור הזה נלמד לדבר על מספרים כאלה בצורה מדויקת.
בסעיף 3 נלמד, מאפס ובקצב איטי, מה זה סכום של אינסוף מספרים, ואיך מחשבים אחד שחוזר בכל הסתברות: $1+r+r^2+\cdots$. לא צריך שום ידע קודם בסדרות, רק מושג הגבול מחדוא 1.
❓ בהטלת שתי קוביות לא מעניין אותי איזו תוצאה בדיוק יצאה, אלא מה הסכום שלהן. איך מדברים על "הסכום" כעל אובייקט בפני עצמו?
נלך בשלבים: (1) ההגדרה, (2) מאורעות שנגזרים ממשתנה, (3) מעבדה על הקוביות, (4) מלכודות נפוצות.
ניקח את טבלת 36 התאים של שתי קוביות. כל תא הוא תוצאה $(i,j)$. הסכום $i+j$ הוא מספר שנקבע על ידי התוצאה: אם התוצאה היא $(3,5)$ הסכום הוא 8. כלומר הסכום הוא פונקציה שמקבלת תוצאה ומחזירה מספר. את זה מכלילים:
משתנה מקרי הוא פונקציה $X$ שמצמידה לכל תוצאה $\omega\in\Omega$ מספר ממשי:
$$X:\Omega\to\mathbb R,\qquad \omega\mapsto X(\omega).$$($\mathbb R$ הוא קבוצת כל המספרים הממשיים.) הכלל לסימון: אות גדולה ($X$, $Y$) למשתנה עצמו, ואות קטנה ($x$, $y$) לערך מסוים שהוא יכול לקבל.
דוגמאות:
| הניסוי | המשתנה המקרי | ערכים אפשריים |
|---|---|---|
| שתי קוביות | $X(i,j)=i+j$ (הסכום) | $2,3,\dots,12$ |
| שתי קוביות | $M(i,j)=\max(i,j)$ | $1,\dots,6$ |
| 3 הטלות מטבע | $N$ = מספר העצים | $0,1,2,3$ |
| הטלות עד העץ הראשון | $T$ = מספר ההטלות | $1,2,3,\dots$ (אינסוף) |
לכל מאורע $A$ יש משתנה מקרי שמסמן אותו: $I_A(\omega)=1$ אם $\omega\in A$ ו-$I_A(\omega)=0$ אחרת ("אינדיקטור"). למשל $A$ = "הסכום ≥ 10": $I_A=1$ בדיוק בתאים של $A$. אינדיקטור הוא פשוט "האם זה קרה: 1 או 0". זה המשתנה שמסתתר מאחורי המשפט "הסתברות = ממוצע של אינדיקטור" מהשיעור הראשון, והוא יופיע שוב ושוב ב-ML (accuracy הוא ממוצע של אינדיקטורים).
עכשיו אפשר לשאול שאלות על המשתנה, והן הופכות בדיוק למאורעות מהשיעורים הקודמים:
המאורע $\{X=x\}$ הוא קבוצת כל התוצאות שהמשתנה שולח ל-$x$. בדומה אפשר לדבר על $\{X\le x\}$, $\{a<X\le b\}$ וכן הלאה.
דוגמה: $X$ = סכום שתי קוביות. המאורע $\{X=7\}$ הוא $\{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}$: 6 תאים מתוך 36, ולכן $P(X=7)=\frac6{36}=\frac16$.
למרות השם "משתנה", $X$ הוא פונקציה על מרחב המדגם. לפני הניסוי אין לה "ערך"; אחרי שיוצאת תוצאה $\omega$, הערך הוא $X(\omega)$. לכן כותבים $P(X=7)$ ולא "$X$ שווה 7" כאילו זה משוואה רגילה: זה סימון מקוצר למאורע $\{X=7\}$.
$X$ = הקובייה הראשונה, $Y$ = הקובייה השנייה. לשתיהן אותה התפלגות (כל ערך 1 עד 6 בסיכוי $\frac16$), אבל הן לא אותו משתנה: $X=Y$ רק בדאבלים, כלומר ב-$\frac{6}{36}$ מהתוצאות. נחזור לזה בסעיף 2: זה מה שמאחורי המילים "identically distributed" ב-ML.
תרגיל 1.1 מאורע שנגזר ממשתנה ⭐
שתי קוביות, $M=\max(i,j)$. כמה תאים יש במאורע $\{M=3\}$? מה $P(M=3)$?
המקסימום הוא 3 כשלפחות קובייה אחת היא 3 ושתיהן ≤3. ספור בטבלה.
התאים: $(3,1),(3,2),(3,3),(1,3),(2,3)$, כלומר 5. $P(M=3)=\frac5{36}$. (הדרך הקצרה: תאים עם $\max\le3$ הם $3^2=9$, עם $\max\le2$ הם $2^2=4$, והפרשם $9-4=5$.)
תרגיל 1.2 אינדיקטור ⭐
$A$ = "הסכום ≥ 10". מהם הערכים של $I_A$, ומה $P(I_A=1)$?
$I_A\in\{0,1\}$. $\{I_A=1\}=A$, שבו 6 תאים: $P(I_A=1)=\frac6{36}=\frac16$ ו-$P(I_A=0)=\frac56$.
תרגיל 1.3 מציאת טעות ⭐⭐
דנה אומרת: "$X$ היא הקובייה הראשונה ו-$Y$ השנייה. שתיהן קוביות הוגנות, ולכן $X=Y$." מה הטעות? כמה היא $P(X=Y)$?
היא מבלבלת בין "אותה התפלגות" ל"אותו משתנה". $X=Y$ הוא מאורע (קבוצת התוצאות שבהן הקוביות זהות): 6 דאבלים מתוך 36, ולכן $P(X=Y)=\frac16$.
תרגיל 1.4 רשימת המאורעות ⭐⭐
מטילים מטבע הוגן 3 פעמים, ו-$N$ הוא מספר העצים. רשום את המאורע $\{N=2\}$ כקבוצה, ואת $P(N=2)$.
$\{N=2\}=\{HHT,HTH,THH\}$ מתוך 8 תוצאות שוות-סיכוי. $P(N=2)=\frac38$. (בדוגמה הזו $\binom32=3$: "בחר מקומות" לעצים.)
יש לנו משתנים מקריים. כדי לתאר "איך הם מתנהגים", מספיק לדעת את ההסתברות לכל ערך. זו ההתפלגות.
❓ אם אני רוצה לתאר משתנה מקרי למישהו אחר בלי לתת לו את כל מרחב המדגם, מה המידע המינימלי שאני צריך להעביר?
משתנה מקרי $X$ הוא בדיד אם הוא מקבל מספר סופי של ערכים, או אינסוף ערכים שאפשר "למנות" ברשימה ($1,2,3,\dots$). עבורו, פונקציית ההסתברות היא
$$p_X(x)=P(X=x).$$(כשברור על איזה משתנה מדברים כותבים פשוט $p(x)$.) הערכים האפשריים נקראים ה"תומך" (support).
כל PMF חייבת לקיים (ומשתנה בדיד שאפשר לבנות ממנה הוא חוקי):
דוגמה, הסכום של שתי קוביות. ספרנו (בעזרת המעבדה למעלה): $p(2)=\frac1{36}$, $p(3)=\frac2{36}$, ..., $p(7)=\frac6{36}$, ..., $p(12)=\frac1{36}$. יש נוסחה מסודרת:
$$p(s)=\frac{6-|s-7|}{36},\qquad s=2,3,\dots,12.$$בדיקה: $s=7$ נותן $\frac6{36}$ ✔, $s=2$ נותן $\frac{6-5}{36}=\frac1{36}$ ✔. והסכום $1+2+3+4+5+6+5+4+3+2+1=36$, לכן $\sum_sp(s)=1$ ✔. ו-$P(X\ge10)=p(10)+p(11)+p(12)=\frac{3+2+1}{36}=\frac16$.
ה-PMF מכילה כל מה שצריך כדי לחשב הסתברות של כל שאלה על $X$. לכן אומרים ש-$p$ היא ההתפלגות (distribution) של $X$. שני משתנים עם אותה PMF "מתפלגים אותו דבר", גם אם הם פונקציות שונות לגמרי על $\Omega$ (תזכורת: שתי הקוביות שונות אבל מתפלגות זהה).
| שם | הערכים | ה-PMF | דוגמה |
|---|---|---|---|
| ברנולי (Bernoulli) עם פרמטר $p$ | $0,1$ | $p(1)=p$, $p(0)=1-p$ | הצלחה/כישלון; אינדיקטור של מאורע |
| אחידה על $\{1,\dots,n\}$ | $1,\dots,n$ | $p(x)=\frac1n$ | קובייה הוגנת ($n=6$) |
| בינומית ($n$ ניסיונות) | $0,\dots,n$ | $\binom nkp^k(1-p)^{n-k}$ | מספר העצים ב-$n$ הטלות (בשיעור 5) |
(אינדיקטור של מאורע $A$ הוא ברנולי עם $p=P(A)$.)
פלט של מסווג עם $K$ מחלקות הוא בעצם PMF על $\{1,\dots,K\}$: מספרים אי-שליליים שסכומם 1 (זה ה-softmax). והתווית האמיתית של דוגמה היא PMF "חדה": כל ההסתברות על המחלקה הנכונה ו-0 על כל האחרות (one-hot). האימון הוא ניסיון להפוך את ה-PMF של המודל לדומה ככל האפשר ל-PMF החדה הזו. ו"i.i.d." ב-ML אומר: משתנים בלתי-תלויים ובעלי אותה התפלגות, בדיוק המושג משלב 3.
תרגיל 2.1 בדיקת PMF ⭐
נתון $p(1)=0.2$, $p(2)=0.5$, $p(3)=c$ (ואין ערכים אחרים). מצא את $c$ ואת $P(X\ge2)$.
הנרמול: $0.2+0.5+c=1$, לכן $c=0.3$. $P(X\ge2)=p(2)+p(3)=0.8$ (או: $1-p(1)$).
תרגיל 2.2 גזירת PMF ⭐⭐
מצא את ה-PMF של $M=\max(i,j)$ בשתי קוביות, ובדוק שהסכום 1.
כמה תאים יש ב-$\{M\le m\}$? ($m^2$.) אז $\{M=m\}$ הוא ההפרש בין $\{M\le m\}$ ל-$\{M\le m-1\}$.
$|\{M=m\}|=m^2-(m-1)^2=2m-1$, לכן $p(m)=\frac{2m-1}{36}$ ל-$m=1,\dots,6$: $\frac1{36},\frac3{36},\frac5{36},\frac7{36},\frac9{36},\frac{11}{36}$. הסכום $1+3+5+7+9+11=36$ ✔.
תרגיל 2.3 אותה התפלגות, משתנים שונים ⭐⭐
$X$ היא קובייה הוגנת, ו-$Y=7-X$. הראה שלשניהם אותה PMF, ושהם אף פעם לא שווים.
$Y$ מקבל את הערכים $6,5,\dots,1$ כשהקובייה היא $1,\dots,6$: כל ערך $y$ מ-1 עד 6 מתקבל בדיוק כש-$X=7-y$, בסיכוי $\frac16$. אותה PMF. אבל $X=Y$ אומר $X=7-X$, כלומר $X=3.5$, בלתי אפשרי. לכן $P(X=Y)=0$.
תרגיל 2.4 PMF מספירה ⭐
3 הטלות של מטבע הוגן, $N$ מספר העצים. מהו ה-PMF, ומהי $P(N\ge1)$?
$p(0)=\frac18$, $p(1)=\frac38$, $p(2)=\frac38$, $p(3)=\frac18$ (ספירה: $\binom3k/8$). סכום 1. $P(N\ge1)=1-p(0)=\frac78$ (משלים).
הכל נראה בסדר כל עוד יש מספר סופי של ערכים. אבל מה עם "מספר ההטלות עד העץ הראשון"? אין לו מקסימום. כדי לבדוק שהסתברויותיו מסתכמות ל-1, נצטרך לסכום אינסוף מספרים. זה מביא אותנו לכלי המתמטי החדש.
❓ מטילים מטבע הוגן עד שיוצא עץ. $T$ הוא מספר ההטלות. מה ה-PMF של $T$, והאם היא מסתכמת ל-1?
נלך בשלבים: (1) ה-PMF, (2) מהו סכום אינסופי, (3) הטור ההנדסי, (4) ההתפלגות הגיאומטרית, (5) "חוסר זיכרון".
כדי ש-$T=k$ צריך ש-$k-1$ ההטלות הראשונות יהיו פלי וההטלה ה-$k$ עץ. ההטלות בלתי-תלויות, לכן מכפילים:
$$P(T=k)=\underbrace{\tfrac12\cdot\tfrac12\cdots\tfrac12}_{k-1}\cdot\tfrac12=\left(\tfrac12\right)^{k},\qquad k=1,2,3,\dots$$כלומר $P(T=1)=\frac12$, $P(T=2)=\frac14$, $P(T=3)=\frac18$, ... האם הסכום הוא 1? כלומר האם $\frac12+\frac14+\frac18+\cdots=1$? זה סכום של אינסוף מספרים.
אי אפשר "לחבר אינסוף מספרים" בפועל, ולכן מגדירים זאת בעזרת מושג שאתה כבר מכיר, גבול:
הסכום של $a_1,a_2,a_3,\dots$ מוגדר דרך הסכומים החלקיים $S_n=a_1+a_2+\cdots+a_n$ (סכום $n$ האיברים הראשונים):
$$\sum_{k=1}^{\infty}a_k\;=\;\lim_{n\to\infty}S_n.$$אם הגבול קיים (מספר סופי), אומרים שהטור מתכנס והגבול הוא סכומו. אחרת הוא מתבדר.
קח מקל באורך 1. שבור חצי ותניח אותו (אורך $\frac12$). משארית המקל שבור שוב חצי ($\frac14$), ושוב ($\frac18$)... הסכומים החלקיים הם $\frac12,\ \frac34,\ \frac78,\ \frac{15}{16},\dots$. כל אחד חסר בדיוק "הזנב" שנשאר ביד. ככל שממשיכים הזנב מתכווץ לאפס, והסכומים החלקיים מתקרבים ל-1. לכן $\frac12+\frac14+\frac18+\cdots=1$.
החצאים הם מקרה פרטי של סכום שמופיע בכל מקום בהסתברות: $1+r+r^2+r^3+\cdots$, כשכל איבר הוא פעמים $r$ הקודם. נחשב את הסכום החלקי, בטריק יפה:
נסמן $S_n=1+r+r^2+\cdots+r^n$. נכפול ב-$r$: $rS_n=r+r^2+\cdots+r^{n+1}$. נחסיר: כמעט כל האיברים מצטמצמים, ונשארים רק הראשון והאחרון:
$$S_n-rS_n=1-r^{n+1}\ \Longrightarrow\ S_n=\frac{1-r^{n+1}}{1-r}\qquad(r\ne1).$$עכשיו נשאיף $n\to\infty$. אם $|r|<1$ אז $r^{n+1}\to0$ (חזקה של מספר קטן מ-1 בערך מוחלט שואפת לאפס), ונקבל:
ואם $|r|\ge1$ הטור מתבדר (האיברים לא קטנים, והסכומים החלקיים לא מתקרבים לשום מספר).
שלוש צורות שימושיות (כולן נובעות מהנוסחה על ידי הוצאת גורם משותף):
$$\sum_{k=1}^{\infty}r^k=\frac{r}{1-r}\ ,\qquad \sum_{k=m}^{\infty}r^k=\frac{r^m}{1-r}\ \ (\text{"זנב"})\ ,\qquad \sum_{k=0}^{\infty}a\,r^k=\frac{a}{1-r}.$$בדיקה עם החצאים: $\sum_{k=1}^\infty(\frac12)^k=\frac{1/2}{1-1/2}=1$ ✔. ולכן ה-PMF של "הטלות עד העץ" מסתכמת ל-1, כפי שצריך.
כדי שטור יתכנס צריך שהאיברים ישאפו ל-0, אבל זה לא מספיק. דוגמה: הטור $1+\frac12+\frac13+\frac14+\cdots$ (הטור ההרמוני) מתבדר למרות שהאיברים שואפים לאפס. בקורס הזה נשתמש כמעט רק בטור ההנדסי, שאת התכנסותו בדקנו לעומק.
מבצעים ניסיונות בלתי-תלויים, בכל אחד הצלחה בסיכוי $p$ ($0<p\le1$) וכישלון בסיכוי $q=1-p$. $X$ = מספר הניסיונות עד ההצלחה הראשונה (כולל אותה). אז
$$P(X=k)=q^{k-1}\,p,\qquad k=1,2,3,\dots$$(בעץ הוגן: $p=q=\frac12$, ויוצא $(\frac12)^k$ כמו קודם.)
נרמול (בעזרת הטור ההנדסי): $\displaystyle\sum_{k=1}^\infty q^{k-1}p=p\sum_{j=0}^\infty q^j=\frac{p}{1-q}=\frac pp=1$ ✔ (הצבנו $j=k-1$).
הזנב: "ההצלחה הראשונה אחרי יותר מ-$m$ ניסיונות" פירושו $m$ כישלונות רצופים בהתחלה:
$$P(X>m)=q^m.$$(בדיקה בטור: $\sum_{k=m+1}^\infty q^{k-1}p=p\cdot\frac{q^m}{1-q}=q^m$ ✔, זו הצורה של "זנב".)
נניח ש-$m$ ניסיונות כבר נכשלו. מה הסיכוי שנצטרך עוד לפחות $n$ ניסיונות? לפי ההגדרה של הסתברות מותנית (וכי $\{X>m+n\}\subseteq\{X>m\}$):
$$P(X>m+n\mid X>m)=\frac{P(X>m+n)}{P(X>m)}=\frac{q^{m+n}}{q^m}=q^n=P(X>n).$$כלומר העבר לא משפיע על העתיד: אחרי $m$ כישלונות, ההמתנה שנותרה מתפלגת בדיוק כמו ההמתנה מההתחלה. זה בדיוק "כשל המהמר" משיעור 1, עכשיו עם הוכחה: מטבע שלא יצא עץ 10 פעמים עדיין זקוק, בממוצע, לאותו מספר הטלות. (וההתפלגות הגיאומטרית היא היחידה בדידה עם התכונה הזו.)
מודל שפה שבכל צעד "עוצר" (מייצר את סימן הסיום, EOS) בסיכוי קבוע $p$ מייצר משפטים שאורכם מתפלג גיאומטרית. וגם בלמידת חיזוק (RL), אם בכל צעד יש סיכוי קבוע שהמשחק נגמר, אורך המשחק גיאומטרי, והסכום $\sum\gamma^k$ שמופיע בהנחת ה"discount factor" הוא בדיוק הטור ההנדסי.
תרגיל 3.1 הפעלת הטור ההנדסי ⭐
חשב: (א) $\sum_{k=0}^\infty(\frac13)^k$. (ב) $\sum_{k=2}^\infty(\frac13)^k$. (ג) $\sum_{k=0}^\infty3\cdot(\frac25)^k$.
(א) $\frac1{1-1/3}=\frac32$. (ב) צורת הזנב: $\frac{(1/3)^2}{1-1/3}=\frac{1/9}{2/3}=\frac16$. (ג) $\frac{3}{1-2/5}=\frac{3}{3/5}=5$.
תרגיל 3.2 הוכחה ⭐⭐
הראה ש-$1+r+\cdots+r^n=\frac{1-r^{n+1}}{1-r}$, ובדוק עם $r=2$, $n=3$.
$(1-r)(1+r+\cdots+r^n)=(1+r+\cdots+r^n)-(r+r^2+\cdots+r^{n+1})=1-r^{n+1}$ (כל האיברים האמצעיים מצטמצמים). בדיקה: $1+2+4+8=15$ ו-$\frac{1-2^4}{1-2}=\frac{-15}{-1}=15$ ✔.
תרגיל 3.3 זנב גיאומטרי ⭐⭐
בהטלות של מטבע הוגן עד העץ הראשון, מה הסיכוי שיידרשו לפחות 4 הטלות? ובהגרלה עם $p=0.2$ להצלחה, מה הסיכוי שלא תצליח ב-5 ניסיונות הראשונים?
"לפחות 4" פירושו שלושת הראשונות פלי: $P(X>3)=(\frac12)^3=\frac18$. בהגרלה: $P(X>5)=0.8^5=0.32768$, וההסתברות להצלחה בתוך 5: $1-0.32768\approx0.672$.
תרגיל 3.4 שני שחקנים (אתגר) ⭐⭐⭐
דנה ורון מטילים לסירוגין מטבע הוגן, דנה ראשונה. מי שמקבל עץ ראשון מנצח. מה הסיכוי שדנה מנצחת?
דנה מנצחת אם העץ הראשון יוצא בהטלה אי-זוגית: $T=1,3,5,\dots$ סכם את $P(T=k)$ על $k$ אי-זוגיים, וזה טור הנדסי עם יחס $\frac14$.
$P(\text{דנה})=\sum_{k\text{ אי-זוגי}}(\tfrac12)^k=\frac12+\frac18+\frac1{32}+\cdots=\frac{1/2}{1-1/4}=\frac23$. (המעבר בין איברים סמוכים הוא פעמים $\frac14$.) לרון נשאר $\frac13$. היתרון של מי שמתחיל: $\frac23$ מול $\frac13$.
תרגיל 3.5 הוכחה: חוסר זיכרון ⭐⭐
הוכח ש-$P(X>m+n\mid X>m)=P(X>n)$ בהתפלגות גיאומטרית, וקשר זאת למטבע שיצא בו פלי 10 פעמים.
ההוכחה בשלב 5. הקישור: אחרי 10 פלי, ההמתנה לעץ מתפלגת כמו בהתחלה: $P(X>10+n\mid X>10)=P(X>n)$. אין "חוב" שצריך להשלים.
תרגיל 3.6 בדיקה מושגית (0.999...) ⭐
הראה בעזרת טור הנדסי ש-$0.999\ldots=1$.
$0.999\ldots=\frac9{10}+\frac9{100}+\frac9{1000}+\cdots=\sum_{k=1}^\infty9\cdot(\tfrac1{10})^k=9\cdot\frac{1/10}{1-1/10}=9\cdot\frac19=1$. (זה לא "כמעט 1": הסכום הוא 1, כי הסכום האינסופי מוגדר כגבול הסכומים החלקיים.)
עכשיו אפשר לתאר כל משתנה בדיד על ידי ה-PMF שלו. אבל שאלות כמו "מה הסיכוי שהסכום קטן או שווה ל-5?" דורשות לחבר הרבה ערכים. לשאלות כאלה כדאי לתת כלי משלהן.
❓ אני שואל כל הזמן "מה הסיכוי ש-$X$ קטן או שווה ל-$x$?" (שיעור הבדיקות שנכשלו, אחוזון, חציון). איך מארגנים את כל התשובות בפונקציה אחת?
למשתנה בדיד: $F(x)=\displaystyle\sum_{t\le x}p(t)$ (סכום ה-PMF על כל הערכים עד $x$ כולל). זו פונקציה "מדרגות": קופצת בכל ערך אפשרי $x$ בגובה $p(x)$.
דוגמה: מספר העצים $N$ ב-3 הטלות ($p=\frac18,\frac38,\frac38,\frac18$). אז $F(0)=\frac18$, $F(1)=\frac48$, $F(2)=\frac78$, $F(3)=1$. ובין ערכים: $F(1.7)=F(1)=\frac12$ (אין ערכים בין 1 ל-2). מקדימה: $F(x)=0$ עבור $x<0$, ומאחור $F(x)=1$ עבור $x\ge3$.
דוגמה, סכום שתי קוביות: $P(3<X\le8)=F(8)-F(3)=\frac{26}{36}-\frac3{36}=\frac{23}{36}$. (בדוק: $F(8)=\frac{1+2+3+4+5+6+5}{36}$, $F(3)=\frac{1+2}{36}$.)
$F(x)=P(X\le x)$ כולל את $x$. לכן $P(X<3)\ne F(3)$. למשתנה שמקבל ערכים שלמים, $P(X<3)=P(X\le2)=F(2)$. הטעות הזו (להחליף $<$ ב-$\le$) נפוצה מאוד, ובמשתנים רציפים (שיעור 3ב) היא תיעלם.
ה-CDF מופיעה בחציון ובאחוזונים (percentiles), בעקומת ROC ובשטח מתחתיה (AUC), ובמבחן Kolmogorov-Smirnov להשוואת התפלגויות. ובסעיף 6 נראה שהיא גם מנוע של דגימה מהתפלגות.
תרגיל 4.1 בניית CDF ⭐
מספר העצים $N$ ב-3 הטלות. חשב $F(1)$, $P(N\ge2)$ ו-$P(0<N\le2)$ בעזרת $F$.
$F(1)=\frac18+\frac38=\frac12$. $P(N\ge2)=1-F(1)=\frac12$. $P(0<N\le2)=F(2)-F(0)=\frac78-\frac18=\frac34$.
תרגיל 4.2 CDF של התפלגות גיאומטרית ⭐⭐
הראה ש-$F(k)=1-q^k$ לכל $k=1,2,\dots$ בהתפלגות גיאומטרית.
$F(k)=P(X\le k)=1-P(X>k)=1-q^k$. (או בטור: $\sum_{j=1}^kq^{j-1}p=p\cdot\frac{1-q^k}{1-q}=1-q^k$, הסכום החלקי של הנדסי.)
תרגיל 4.3 מציאת טעות ⭐⭐
סטודנט כותב: "סכום שתי קוביות, $P(X<5)=F(5)=\frac{10}{36}$." מה הטעות?
$F(5)=P(X\le5)=\frac{10}{36}$ נכון, אבל $P(X<5)=P(X\le4)=F(4)=\frac{6}{36}$. הוא כלל את הערך 5 בטעות.
עד עכשיו הסתכלנו על משתנה אחד. בפועל מפעילים עליו פונקציות ("ריבוע", ReLU) ומחברים כמה משתנים (סכום תוצאות). איך משתנה ההתפלגות?
❓ אם ל-$X$ יש PMF ידועה, מה ה-PMF של $Y=X^2$? ושל $X+Y$ כשהם בלתי-תלויים?
(סוכמים את הסתברויות כל ה-$x$ ש-$g$ שולחת ל-$y$.)
ההסבר: המאורע $\{Y=y\}$ הוא איחוד (זר) של המאורעות $\{X=x\}$ עבור כל ה-$x$ ש-$g(x)=y$, וחיבור הסתברויות של זרים הוא האקסיומה.
דוגמה: $X$ אחיד על $\{-2,-1,0,1,2\}$ (כל ערך $\frac15$), $Y=X^2$. הערך $Y=1$ מתקבל מ-$X=-1$ ו-$X=1$: $p_Y(1)=\frac15+\frac15=\frac25$. כך $p_Y(0)=\frac15$, $p_Y(4)=\frac25$.
פונקציית ההפעלה $\text{ReLU}(x)=\max(0,x)$ שולחת כל ערך שלילי ל-0. אם $X$ מקבל ערכים שליליים בסיכוי כלשהו, אז ל-$Y=\text{ReLU}(X)$ יש "גוש הסתברות" בנקודה 0 ששווה לסכום הסתברויות הערכים השליליים. לכן אחרי ReLU חלק גדול מהנוירונים הם בדיוק 0 (sparsity).
$X$ ו-$Y$ בלתי-תלויים אם כל זוג מאורעות מהצורה $\{X=x\}$, $\{Y=y\}$ בלתי-תלויים:
$$P(X=x,\ Y=y)=P(X=x)\cdot P(Y=y)\quad\text{לכל }x,y.$$(הפסיק פירושו "וגם": $P(X=x,Y=y)=P(\{X=x\}\cap\{Y=y\})$.) כמו בשיעור 2, בלתי-תלויים אומר שאפשר להכפיל.
אם $X$ ו-$Y$ בלתי-תלויים ומקבלים ערכים שלמים:
$$p_{X+Y}(s)=\sum_{x}p_X(x)\,p_Y(s-x).$$למה? המאורע $\{X+Y=s\}$ הוא איחוד זר, על כל ערך $x$ של $X$, של $\{X=x,\ Y=s-x\}$. הסתברות כל אחד היא $p_X(x)\,p_Y(s-x)$ (אי-תלות), ומחברים.
דוגמה, שתי קוביות: $P(X+Y=4)=p(1)p(3)+p(2)p(2)+p(3)p(1)=3\cdot\frac1{36}=\frac3{36}$ ✔ (זה אותו חישוב כמו בטבלה, בכתיבה אחרת).
אם $X$ קובייה, אז $2X=X+X$ (אותה קובייה פעמיים!) מקבל רק את הערכים $2,4,\dots,12$, כל אחד בסיכוי $\frac16$ (צורה אחידה), בעוד $X+Y$ (שתי קוביות בלתי-תלויות) מקבל את כל הערכים 2 עד 12 בצורת משולש. אי-תלות היא מה שגורם ל"פעמון" בסכום.
תרגיל 5.1 פונקציה של משתנה ⭐⭐
$X$ אחיד על $\{-2,-1,0,1,2\}$ ו-$Y=\text{ReLU}(X)=\max(0,X)$. מה ה-PMF של $Y$?
$Y=0$ מתקבל מ-$X=-2,-1,0$: $p_Y(0)=\frac35$. $p_Y(1)=\frac15$, $p_Y(2)=\frac15$. סכום 1 ✔. (שלושה חמישיות מהמסה "נערמות" ב-0.)
תרגיל 5.2 קונבולוציה ⭐⭐
$X$ קובייה הוגנת ו-$Y$ מטבע (0 או 1, בסיכוי $\frac12$ כל אחד), בלתי-תלויים. מה ה-PMF של $Z=X+Y$?
$p_Z(1)=p_X(1)p_Y(0)=\frac1{12}$. לערכים $2,\dots,6$: $p_Z(s)=p_X(s)p_Y(0)+p_X(s-1)p_Y(1)=\frac1{12}+\frac1{12}=\frac16$. $p_Z(7)=p_X(6)p_Y(1)=\frac1{12}$. סכום: $\frac1{12}+5\cdot\frac16+\frac1{12}=1$ ✔.
תרגיל 5.3 תלות מול אי-תלות ⭐⭐
השווה את $P(2X=8)$ (כש-$X$ קובייה) ל-$P(X+Y=8)$ (שתי קוביות בלתי-תלויות).
$2X=8$ אומר $X=4$: $\frac16=\frac6{36}$. $X+Y=8$: 5 תאים: $\frac5{36}$. הם שונים, כי ב-$2X$ אותו מספר מופיע פעמיים, בעוד ב-$X+Y$ יש שתי קוביות עצמאיות.
תרגיל 5.4 סכום ברנולי ⭐⭐
$B_1,B_2$ ברנולי($p$) בלתי-תלויים. מה ה-PMF של $B_1+B_2$?
$P(0)=q^2$, $P(1)=pq+qp=2pq$, $P(2)=p^2$ (שים לב: $q^2+2pq+p^2=(p+q)^2=1$). זו ההתפלגות הבינומית עם $n=2$: הצצה לשיעור 5.
עכשיו יש לנו את כל הכלים: PMF, CDF, פונקציות וסכומים. נחבר אותם לשאלה מרכזית ב-ML: איך מייצרים (דוגמים) ערך מהתפלגות נתונה, למשל איך מודל שפה בוחר את המילה הבאה.
❓ מודל שפה מוציא בכל צעד PMF על אוצר המילים (עשרות אלפי מילים). איך מוציאים ממנה מילה אחת באקראי? ומה זה "טמפרטורה"?
נלך בשלבים: (1) דגימה בעזרת ה-CDF, (2) טמפרטורה, (3) חזרה לחוק המספרים הגדולים.
מחשב יודע להגריל מספר $U$ אחיד בין 0 ל-1 (פונקציה אחת בכל שפת תכנות). איך מהמספר הזה מקבלים ערך שמתפלג לפי PMF נתונה?
חתוך את הקטע $[0,1)$ לתת-קטעים שאורכם $p_1,p_2,\dots$ (בסדר, אחד אחרי השני). $U$ נופל בקטע $k$ בהסתברות השווה לאורכו, כי $U$ אחיד: $P(F(k-1)\le U<F(k))=F(k)-F(k-1)=p_k$. בדיוק מה שרצינו. הקטעים הארוכים (הסתברות גבוהה) נבחרים יותר.
import numpy as np
p = np.array([0.5, 0.3, 0.2]) # the PMF over three values
F = np.cumsum(p) # the CDF: [0.5, 0.8, 1.0]
u = np.random.rand() # U uniform on [0, 1)
k = np.searchsorted(F, u, side="right") # the first index with U < F (0-based)
print(u, k)
# check: many samples reproduce the PMF
ks = np.searchsorted(F, np.random.rand(100_000), side="right")
print(np.bincount(ks) / 100_000) # ~ [0.5, 0.3, 0.2]
המודל מוציא ציונים (logits) $z_1,\dots,z_K$, ואחר כך ה-softmax הופך אותם ל-PMF (כך נראה: $p_i\propto e^{z_i}$, חלוקה בסכום). בדגימה מודלים משתמשים בפרמטר טמפרטורה $T>0$:
$T=1$ הוא ה-softmax הרגיל. $T\to0$: כל המסה על הערך הגבוה ביותר (בחירת argmax, "חמדנית"). $T\to\infty$: ההתפלגות שואפת לאחידה (כל האפשרויות שוות).
למה? חלוקה ב-$T$ משנה את ההפרשים בין הציונים: היחס בין שתי הסתברויות הוא $\frac{p_i}{p_j}=e^{(z_i-z_j)/T}$. כש-$T$ קטן, ההפרש מוגדל והיחס מתפוצץ; כש-$T$ גדול, ההפרש מתכווץ והיחס שואף ל-1.
דוגמה עם $z=(2,1,0)$: ב-$T=1$: $e^2=7.39$, $e^1=2.72$, $e^0=1$, סכום $11.11$, ולכן $p=(0.665,\ 0.245,\ 0.090)$. ב-$T=0.5$: הציונים המחולקים הם $(4,2,0)$: $e^4=54.6$, $e^2=7.39$, $1$, סכום $62.99$, ולכן $p=(0.867,\ 0.117,\ 0.016)$. חדה הרבה יותר.
זה בדיוק מה שה-"temperature" עושה ב-API של מודלי שפה: טמפרטורה נמוכה לתשובות עקביות וצפויות, גבוהה לתשובות מגוונות. וה-PMF עצמה היא רק הצעה: התשובה בפועל היא דגימה ממנה, ולכן אותה שאלה נותנת לפעמים תשובות שונות.
תרגיל 6.1 דגימה בעזרת CDF ⭐
ה-PMF היא $(0.5,\ 0.3,\ 0.2)$ על הערכים 1, 2, 3. מה הערך שנדגם עבור $U=0.2$, $U=0.7$ ו-$U=0.95$?
$F=(0.5,\ 0.8,\ 1.0)$. $U=0.2<0.5$: ערך 1. $U=0.7$: בין 0.5 ל-0.8: ערך 2. $U=0.95$: בין 0.8 ל-1: ערך 3.
תרגיל 6.2 טמפרטורה במספרים ⭐⭐
עבור $z=(3,1,0)$ חשב את ה-softmax ב-$T=1$ וב-$T=2$. מה קרה להסתברות הגדולה ביותר?
$T=1$: $e^3=20.09$, $e=2.72$, $1$, סכום $23.80$: $p=(0.844,\ 0.114,\ 0.042)$. $T=2$: ציונים $(1.5,\ 0.5,\ 0)$: $e^{1.5}=4.48$, $e^{0.5}=1.65$, $1$, סכום $7.13$: $p=(0.628,\ 0.231,\ 0.140)$. טמפרטורה גבוהה יותר "ממתנת" את ההתפלגות: הגדולה ירדה מ-0.84 ל-0.63.
תרגיל 6.3 קוד ⭐⭐
כתוב פונקציה שמקבלת וקטור logits וטמפרטורה, ומחזירה דגימה אחת (אינדקס), בעזרת ה-CDF והאלגוריתם מסעיף 6. בדוק שב-$T$ קטן היא כמעט תמיד מחזירה את ה-argmax.
import numpy as np
def sample(logits, T=1.0, rng=np.random.default_rng()):
z = np.asarray(logits, dtype=float) / T
p = np.exp(z - z.max()) # subtract max: numerical stability (does not change the PMF)
p /= p.sum() # normalize
return int(np.searchsorted(np.cumsum(p), rng.random(), side="right"))
logits = [2.0, 1.0, 0.0]
for T in (0.1, 1.0, 5.0):
counts = np.bincount([sample(logits, T) for _ in range(20_000)], minlength=3)
print(T, counts / counts.sum()) # T=0.1 -> ~[1, 0, 0]; T=5 -> close to uniformתרגיל 6.4 הסבר ⭐⭐
למה כש-$T\to0$ ההתפלגות מתרכזת על ה-argmax? (רמז: יחס ההסתברויות.)
היחס בין הגדולה ($z_1$) לשנייה ($z_2$): $\frac{p_1}{p_2}=e^{(z_1-z_2)/T}$. כש-$T\to0$ המעריך $\frac{z_1-z_2}{T}\to+\infty$ (כי $z_1>z_2$), והיחס מתפוצץ: כל המסה עוברת ל-$z_1$.
בלי כותרת טכניקה (היא רשומה בפתרון).
תרגיל מ.1 ⭐⭐
מטילים מטבע הוגן 4 פעמים, $N$ מספר העצים. חשב את ה-PMF ואת ה-CDF, ואת $P(1<N\le3)$.
בחר מקומות + CDF. $p=(\frac1{16},\frac4{16},\frac6{16},\frac4{16},\frac1{16})$. $F=(\frac1{16},\frac5{16},\frac{11}{16},\frac{15}{16},1)$. $P(1<N\le3)=F(3)-F(1)=\frac{15}{16}-\frac5{16}=\frac{10}{16}=\frac58$.
תרגיל מ.2 ⭐⭐⭐
מטילים מטבע הוגן עד העץ הראשון. מה הסיכוי שמספר ההטלות הוא זוגי? והכללה: בהתפלגות גיאומטרית עם $p$, מה $P(X\text{ זוגי})$?
טור הנדסי. $P(T\text{ זוגי})=\sum_{k=2,4,\dots}(\tfrac12)^k=\frac{1/4}{1-1/4}=\frac13$. הכללה: $\sum_{j\ge1}q^{2j-1}p=pq\sum_{j\ge0}(q^2)^j=\frac{pq}{1-q^2}=\frac{pq}{(1-q)(1+q)}=\frac{q}{1+q}$. ל-$q=\frac12$: $\frac{1/2}{3/2}=\frac13$ ✔.
תרגיל מ.3 (ML) ⭐⭐
מודל שפה "עוצר" בכל צעד בסיכוי $0.1$ (בלתי-תלוי). מה ההסתברות שהמשפט ארוך מ-20 מילים? ושהוא באורך 10 לכל היותר?
גיאומטרית + זנב. אורך $L\sim\text{Geo}(0.1)$. $P(L>20)=0.9^{20}\approx0.1216$. $P(L\le10)=1-0.9^{10}\approx1-0.3487=0.6513$.
תרגיל מ.4 ⭐⭐
בהטלת שלוש קוביות, $S$ הוא מספר ה-6 שיצאו. מה ה-PMF של $S$?
בחר מקומות + אי-תלות. $S\sim$ בינומית($n=3$, $p=\frac16$): $P(S=k)=\binom3k(\frac16)^k(\frac56)^{3-k}$. $P(0)=\frac{125}{216}$, $P(1)=\frac{75}{216}$, $P(2)=\frac{15}{216}$, $P(3)=\frac1{216}$. סכום: $\frac{216}{216}=1$ ✔.
מה כשהמשתנה יכול לקבל כל ערך בקטע (גובה, זמן המתנה)? אין "הסתברות לערך בודד" (היא 0!), ובמקומה יש צפיפות. נלמד שם את הכלי המתמטי השני שלא למדת: אינטגרל כשטח, מאפס, בקצב איטי. ונראה למה צפיפות יכולה להיות גדולה מ-1 ועדיין ההסתברויות חוקיות.