שיעור 1 — איך מדברים במדויק על "סיכוי"?

זמן משוער: כ-90 דקות כולל התרגול. דרישות קדם: אין. כל סימון מוסבר ברגע שהוא מופיע.

★הסיפור של השיעור

בשיעור הזה אין "רשימת נושאים". יש שרשרת של שאלות, וכל נושא הוא התשובה לשאלה שהנושא הקודם השאיר פתוחה. אם בנקודה כלשהי תרגיש "למה אני לומד את זה עכשיו", תחפש את השאלה שהובילה לשם.

  1. מה זה בכלל אומר ש"הסיכוי לעץ הוא חצי"? ← חלק יחסי מתוך הרבה ניסיונות
  2. "חלק יחסי של מה?" ← תוצאות, מרחב מדגם ומאורעות
  3. איך מדברים על "זוגי או גדול מ-4", "לא 6"? ← קבוצות ופעולות עליהן
  4. אילו חוקים חייבים להתקיים לכל "חלק יחסי"? ← אקסיומות, וכל שאר החוקים נגזרים מהן
  5. איך מחשבים בפועל? ← ספירה
  6. האם החישוב מתיישב עם האינטואיציה? ← פרדוקס יום ההולדת
  7. ומה כל זה קשור ל-ML? ← מה המשמעות של "המודל בטוח ב-90%"
🎯 איך לעבוד עם השיעור

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

1מה זה אומר ש"הסיכוי הוא חצי"?

❓ אם אני מטיל מטבע פעמיים, לא בהכרח יצא עץ פעם אחת. אז מה בדיוק טענתי כשאמרתי "הסיכוי הוא 1/2"?

הסעיף בנוי בשלבים: (0) על מה מדברים, (1) מה "חצי" לא יכול להיות, (2) מה הוא כן, (3) ניסוי חי, (4) מה נקבל מזה, (5) מלכודת נפוצה.

שלב 0: על מה בכלל מדברים?

הסתברות עוסקת בניסוי מקרי: משהו שאפשר לחזור עליו, ושאת התוצאה שלו אי אפשר לנבא מראש. דוגמאות: הטלת מטבע, הטלת קובייה, בחירת תמונה אקראית מתוך דאטהסט.

שלב 1: מה "הסיכוי הוא חצי" לא יכול להיות

נטיל מטבע הוגן פעם אחת. תהיה תוצאה אחת: עץ או פלי. אין דבר כזה "חצי עץ". לכן "1/2" לא מתאר את ההטלה הבודדת.

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

שלב 2: תדירות יחסית

נניח שחזרנו על ניסוי $n$ פעמים, והמאורע שמעניין אותנו (למשל "יצא עץ") קרה $k$ מהפעמים. אז:

📐 תדירות יחסית
$$\text{תדירות יחסית}=\frac{k}{n}=\frac{\text{כמה פעמים זה קרה}}{\text{כמה פעמים ניסינו}}.$$

דוגמה: 10 הטלות, 7 מהן עץ: התדירות היחסית היא $7/10=0.7$.

עכשיו הנה ריצה אופיינית (המספרים ישתנו מריצה לריצה, אבל התבנית קבועה):

מספר ההטלות $n$101001,000100,000
כמה פעמים עץ, $k$75450849,930
תדירות יחסית $k/n$0.7000.5400.5080.4993

שים לב: בהתחלה המספר "קופץ" (0.7), ואחר כך הוא מתקרב ל-0.5. זה הפירוש של "הסיכוי הוא חצי":

📐 הפרשנות התדירותית של הסתברות

"ההסתברות למאורע $A$ היא $p$" פירושו: כשחוזרים על הניסוי הרבה פעמים, התדירות היחסית של $A$ מתקרבת ל-$p$.

(הפרשנות הזו נקראת תדירותית, ב-frequentist. התכונה "התדירות מתקרבת ל-p" נקראת חוק המספרים הגדולים. נוכיח אותה בשיעור 7. כרגע אנחנו פשוט רואים אותה.)

שלב 3: ראה את זה קורה

🪙 הטל מטבע שוב ושוב, ועקוב אחרי התדירות היחסית של עץ
איך קוראים את הגרף: הקו הכחול הוא התדירות היחסית של עץ עד כה. הקו הכתום המקווקו הוא ה-p האמיתי. הציר האופקי הוא מספר ההטלות, בסקאלה לוגריתמית (כל שנתה = פי 10 יותר הטלות), כדי שנראה גם את ההתחלה הרועשת וגם את ההמשך.
נסה בסדר הזה: (1) לחץ +10 כמה פעמים: הקו רועש מאוד. (2) לחץ +10,000: הקו כמעט ישר, ליד הכתום. (3) שנה את p ל-0.8 והתחל מחדש: הקו מתיישב על 0.8.

שלב 4: מה אנחנו לוקחים מזה?

מכיוון שהסתברות היא מה שהתדירות $\frac kn$ מתקרבת אליו, היא "יורשת" ממנה כמה תכונות מיידיות. (זה ישמש אותנו בסעיף 4, כשננסח את החוקים.)

שלב 5: המלכודת הנפוצה, "כשל המהמר"

נניח שיצאו 10 עצים ברצף. מישהו אומר: "עכשיו פלי חייב לצאת, כדי שזה יתאזן". זה לא נכון. למטבע אין זיכרון, וההטלה הבאה היא עדיין חצי-חצי.

אבל אז איך התדירות בכל זאת מתכנסת ל-1/2? לא על ידי "תיקון". ננסה לראות עם מספרים:

שים לב: העודף של 5 עצים לא נעלם: עדיין יש 505 עצים במקום 500. פשוט 5 מתוך 1,000 הוא כמעט כלום. העודף "נמס" בתוך המספרים הגדולים, ולא תוקן. השורה "הפרש מוחלט" בסימולציה למעלה מראה את זה: ההפרש לא הולך ל-0, רק היחס שלו למספר ההטלות.

📜 עוד כמה פרשנויות לדרך שבה מבינים הסתברות (לא חובה)

יש מצבים שאי אפשר "לחזור על הניסוי": "מה הסיכוי שמחר ירד גשם?" מחר קורה פעם אחת. בגישה הבייסיאנית הסתברות היא דרגת אמונה. בגישה הקלאסית היא נספרת מסימטריה ("6 פאות שוות, לכן 1/6"). שלושת הגישות מסכימות על אותם חוקי חישוב, ובשיעור 9 נראה למה ההבדל בכל זאת חשוב ל-ML. בינתיים תחזיק בתדירותית, שהיא הכי קלה לדמיין.

תרגול לסעיף 1

תרגיל 1.1 הבנה מושגית מטבע הוגן הוטל 10 פעמים ויצא עץ בכולן. מה ההסתברות לעץ בהטלה ה-11?

תרגיל 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 הוא ממוצע של "האם ניחשתי נכון".

🔗 איפה אנחנו בסיפור

הבנו שהסתברות היא "חלק יחסי של פעמים". עכשיו צריך להיות מדויקים: חלק של מה? של הפעמים שבהן קרה "משהו". צריך לתת שם לאותו "משהו".

2תוצאות, מרחב מדגם ומאורעות

❓ "התדירות היחסית של הפעמים שבהן קרה משהו". איך מגדירים "משהו" בצורה שאפשר לעבוד איתה?

נלך בשלבים: (1) תוצאה, (2) מרחב מדגם, (3) מאורע, (4) שתי קוביות, (5) מלכודות.

שלב 1: תוצאה

תוצאה (outcome) היא התשובה המלאה והבודדת של ריצה אחת של הניסוי. הטלת מטבע: התוצאה היא "עץ" או "פלי". הטלת קובייה: התוצאה היא המספר שהקובייה הראתה, 1 או 2 או ... או 6. בכל ריצה מתממשת בדיוק תוצאה אחת.

שלב 2: מרחב מדגם

נאסוף את כל התוצאות האפשריות לקבוצה אחת. קבוצה היא אוסף של דברים, ואותה כותבים בסוגריים מסולסלים $\{\ \}$ (הסדר לא משנה, וכל איבר מופיע פעם אחת). את הקבוצה הזו מסמנים ב-$\Omega$ (האות היוונית "אומגה"), ונקראת מרחב מדגם (sample space):

שלב 3: מאורע

לפעמים השאלה שלנו לא על תוצאה בודדת. "האם יצא מספר זוגי?" נכון לשלוש תוצאות שונות: 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
בדיקה מהירה: הקובייה הראתה 5. אילו מהמאורעות הבאים קרו? $A=\{2,4,6\}$ (זוגי), $B=\{5,6\}$ (גדול מ-4).
💡 למה לתאר מאורע כקבוצה?

"יצא זוגי" נשמע כמו משפט. אבל כשהופכים אותו לקבוצה של תוצאות, אפשר לספור. עכשיו "תדירות יחסית" הופכת ל"כמה תוצאות בקבוצה, מתוך כמה בסך הכל": בקובייה, "זוגי" תופס 3 מתוך 6, ולכן נצפה שבערך $3/6$ מההטלות יהיו זוגיות. זו הסיבה שהקבוצות כל כך שימושיות.

שלב 4: שתי קוביות, ולמה צריך טבלה

כשמטילים שתי קוביות, תוצאה היא זוג מספרים $(i,j)$: "הראשונה יצאה $i$, השנייה יצאה $j$". יש $6\cdot6=36$ תוצאות, ונוח לשרטט אותן בטבלה. כל תא הוא תוצאה אחת (שים לב: $(2,5)$ ו-$(5,2)$ הן שתי תוצאות שונות):

🧱 בנה מאורע בעצמך: לחץ על תאים כדי לסמן אותם

מה ראית: מאורע הוא קבוצה של תאים, וההסתברות שלו היא החלק היחסי של התאים המסומנים. למשל "הסכום הוא 7" תופס 6 תאים מתוך 36, ולכן ההסתברות שלו היא $6/36=1/6$. חישבת הסתברות בלי שום נוסחה, רק מספירת תאים. זה הרעיון המרכזי.

שלב 5: מלכודות

⚠️ אי-הבנה נפוצה (שאפילו לייבניץ נפל בה)

"בשתי קוביות יש 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

תרגיל 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". איך כותבים כאלה? בעזרת פעולות על קבוצות.

3איך משלבים מאורעות? פעולות על קבוצות

❓ אם $A$ ו-$B$ מאורעות, מהם "$A$ או $B$", "$A$ וגם $B$", "לא $A$"?

נלך בשלבים: (1) ארבע פעולות על דוגמה קטנה, (2) מושג ה"זרים", (3) הפעולות על הטבלה של שתי קוביות, (4) הפעולות בציור כללי, (5) דה-מורגן.

שלב 1: ארבע פעולות, על קובייה אחת

מאחר שמאורע הוא קבוצה, כל שילוב הגיוני של מאורעות הוא פעולה על קבוצות. ניקח קובייה אחת: $\Omega=\{1,2,3,4,5,6\}$, ושני מאורעות:

① איחוד: "$A$ או $B$", סימון $A\cup B$

כל התוצאות שנמצאות לפחות באחת מהקבוצות. ($\cup$ נראה כמו כוס שאוספת הכל.)
$A\cup B=\{2,4,5,6\}$. שים לב: "או" במתמטיקה הוא "או" מכליל: גם 6 נכלל, כי הוא ב-$A$ וגם ב-$B$. והוא נכתב פעם אחת בלבד (בקבוצה אין כפילויות).

② חיתוך: "$A$ וגם $B$", סימון $A\cap B$

התוצאות שנמצאות בשתי הקבוצות יחד. $A\cap B=\{6\}$ (רק 6 גם זוגי וגם גדול מ-4).

③ משלים: "לא $A$", סימון $A^c$

כל מה שב-$\Omega$ ולא ב-$A$. $A^c=\{1,3,5\}$ (אי-זוגי).

④ הפרש: "$A$ אבל לא $B$", סימון $A\setminus B$

מה שב-$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\}$
בדיקה מהירה: באותה קובייה, $A=\{2,4,6\}$ ו-$B=\{5,6\}$. מהו $B\setminus A$ ("$B$ אבל לא $A$")?

שלב 2: מאורעות זרים

שני מאורעות הם זרים (disjoint) אם אין להם אף תוצאה משותפת: $A\cap B=\emptyset$. כלומר אי אפשר ששניהם יקרו באותה הטלה. למשל "יצא זוגי" $\{2,4,6\}$ ו"יצא אי-זוגי" $\{1,3,5\}$ הם זרים. ("זוגי" ו"גדול מ-4" אינם זרים, כי 6 משותף.)

המושג הזה חשוב: בסעיף הבא נראה שרק מאורעות זרים אפשר פשוט "לחבר".

שלב 3: אותן פעולות, על שתי קוביות

עכשיו נפעיל אותן על הטבלה של שתי קוביות (36 תאים). בחר שני מאורעות $A$ ו-$B$ ופעולה, וראה אילו תאים נדלקים:

🎲 מעבדת הקוביות

ניסוי מודרך (שלוש דקות):

  1. בחר $A$ = "הסכום הוא 7", $B$ = "הראשונה = 6", והצג $A\cap B$. ראה שדלוק תא אחד בלבד: $(6,1)$.
  2. עכשיו הצג $A\cup B$: 11 תאים. שים לב בשורת ההסבר שכתוב $\frac6{36}+\frac6{36}-\frac1{36}=\frac{11}{36}$ (האתר מציג את השברים מצומצמים: $\frac16+\frac16-\frac1{36}$). התא המשותף נספר פעמיים אם סוכמים סתם, ולכן מחסרים אותו פעם אחת. (זה יהיה חוק בסעיף 4.)
  3. החלף ל-$B$ = "הסכום ≥ 10". עכשיו $A\cap B=\emptyset$ והשורה אומרת "A ו-B זרים".

שלב 4: אותן פעולות בציור כללי

לא תמיד יש טבלה. לכן מציירים כך: המלבן הוא $\Omega$, העיגולים הם המאורעות $A$ ו-$B$, והאזור הכחול הוא התוצאה של הפעולה שבחרת:

🎨 מעבדת Venn: בחר פעולה בכל צד, והאתר יגיד אם זה אותו מאורע
נסה: (1) בחר בצד שמאל $A\cup B$ ובצד ימין $A\cap B$ וראה את ההבדל. (2) שמאל $(A\cup B)^c$ וימין $A^c\cap B^c$: האתר אומר "אותו מאורע". זה חוק דה-מורגן, והוא מוסבר מיד.

שלב 5: חוקי דה-מורגן

נחזור לקובייה. $A=\{2,4,6\}$, $B=\{5,6\}$. נחשב "לא (זוגי או גדול מ-4)" בשתי דרכים:

אותה תשובה. זה לא מקרי:

📐 חוקי דה-מורגן
$$(A\cup B)^c = A^c\cap B^c \qquad\qquad (A\cap B)^c = A^c\cup B^c$$

במילים: "לא (גשם או שלג)" שווה ל"לא גשם וגם לא שלג". ו-"לא (גשם וגם שלג)" שווה ל"לא גשם או לא שלג". בקוד: not (a or b) == (not a) and (not b). הכלל לזכירה: הכנסת ה"לא" לתוך הסוגריים מחליפה "או" ב"וגם" ולהפך.

תרגול לסעיף 3

תרגיל 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$.

הרעיון: אפשר לפרק איחוד לא-זר לחלקים זרים.

🔗 איפה אנחנו בסיפור

עכשיו יש לנו מאורעות מכל סוג. נחזור לשאלה מהסעיף הראשון: הסתברות היא "חלק יחסי". אילו חוקים חייב לקיים כל חלק יחסי, בלי קשר למה שאנחנו מודדים?

4החוקים: אקסיומות הסתברות

❓ ברור ש"חלק יחסי" מתנהג יפה. מה בדיוק ה"יפה" הזה, כך שאפשר יהיה לגזור ממנו הכל?

הסעיף הזה הולך בשלבים: (0) מה מחפשים, (1) שלוש תצפיות על הטבלה, (2) ניסוח רשמי, (3) איך מוכיחים דברים מהחוקים, (4) הטריק הכי שימושי.

שלב 0: מה בעצם מחפשים?

עד עכשיו חישבנו הסתברות בספירת תאים בטבלת הקוביות. עכשיו נרצה כללים שנכונים לא רק לקוביות אלא לכל מצב. נסמן ב-$P$ "מכונת הסתברות": היא מקבלת מאורע (קבוצה) ומחזירה מספר. למשל:

$$P(\text{הסכום הוא }7)=\frac{6}{36}.$$

נכתוב $P(A)$ ונקרא "ההסתברות של $A$". השאלה: אילו כללים חייבת לקיים כל מכונה כזו כדי שנוכל לקרוא לה "חלק יחסי"? נחפש אותם בטבלה.

שלב 1: שלוש תצפיות על טבלת הקוביות

  1. אי אפשר "חלק שלילי". מאורע תופס 0 תאים או יותר, ולכן החלק שלו הוא 0 או יותר. אין מאורע שתופס "מינוס 3 תאים".
  2. "קורה משהו" הוא 1. המאורע $\Omega$ ("יצאה איזושהי תוצאה") תופס את כל 36 התאים מתוך 36, כלומר 36/36 = 1.
  3. חיבור כשאין חפיפה. נניח $A$ = "הסכום הוא 7" (6 תאים) ו-$B$ = "הסכום ≥ 10" (6 תאים). אין אף תא משותף. "$A$ או $B$" תופס $6+6=12$ תאים, כלומר $\frac{12}{36}=\frac{6}{36}+\frac{6}{36}$. החיבור עובד.
    אבל כשיש חפיפה זה נכשל: נקח $C$ = "הקובייה הראשונה יצאה 6" (גם 6 תאים). ב-$A$ וב-$C$ יש תא משותף אחד: $(6,1)$. "$A$ או $C$" תופס 11 תאים ולא 12. התא המשותף נספר פעמיים אם סוכמים בלי לחשוב.

תבדוק בעצמך: גלול למעבדת הקוביות בסעיף 3, בחר $A$ = "הסכום הוא 7", $B$ = "הסכום ≥ 10", ואז $A\cup B$. אחר כך החלף ל-$B$ = "הראשונה = 6", וראה את ההבדל.

שלב 2: הניסוח הרשמי

קולמוגורוב (1933) הבין שהשלוש האלה הן כל מה שצריך. כל פונקציה $P$ שמקיימת אותן נקראת "הסתברות", בין אם היא נולדה מספירת תאים, מתדירויות או מאמונה:

📐 אקסיומות קולמוגורוב
  1. אי-שליליות: $P(A)\ge 0$ לכל מאורע $A$.
  2. נרמול: $P(\Omega)=1$.
  3. אדיטיביות ("חיבור"): אם $A$ ו-$B$ זרים ($A\cap B=\emptyset$), אז $P(A\cup B)=P(A)+P(B)$.

הערות על הניסוח:

תרגיל 4.0 בדיקת הבנה נתון $P(A)=0.3$ ו-$P(B)=0.5$, והמאורעות זרים. מה $P(A\cup B)$?

שלב 3: איך מוכיחים דברים מהאקסיומות

יש לנו רק שלושה כללים, והשלישי הוא היחיד שיודע לחבר. לכן יש טכניקה אחת שחוזרת בכל ההוכחות:

🎯 המפתח: "לפרק לחלקים זרים, ואז לחבר"

כשרוצים לחשב הסתברות של מאורע מסובך, מפרקים אותו לחלקים שלא חופפים, ומחברים את ההסתברויות שלהם באקסיומה 3. תראה: בכל אחד משלושת החוקים הבאים נעשה בדיוק את זה.

חוק ①: המשלים

מה רוצים: לדעת את $P(\text{לא }A)$ כשידוע $P(A)$.

  1. $A$ ו-$A^c$ ("לא $A$") ביחד ממלאים את כל $\Omega$: $A\cup A^c=\Omega$.
  2. הם זרים: אין תוצאה שנמצאת גם ב-$A$ וגם "לא ב-$A$".
  3. אקסיומה 3 ואחר כך 2: $P(A)+P(A^c)=P(\Omega)=1$.
  4. לכן $\displaystyle P(A^c)=1-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$.

  1. מפרקים: $B=A\cup(B\setminus A)$, כלומר "החלק של $A$" ועוד "השאר של $B$".
  2. שני החלקים זרים (השאר הוא מה שלא ב-$A$).
  3. לכן $P(B)=P(A)+P(B\setminus A)$.
  4. $P(B\setminus A)\ge 0$ (אקסיומה 1), ולכן $P(B)\ge P(A)$.

בדיקה בטבלה: $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).$$

הוכחה בשני שלבים:

  1. $A\cup B=A\cup(B\setminus A)$ בפירוק זר (כמו בחוק ②), לכן $P(A\cup B)=P(A)+P(B\setminus A)$.
  2. גם $B$ מתפרק לשני חלקים זרים: $B=(B\setminus A)\cup(A\cap B)$, כלומר "חלק שמחוץ ל-$A$" ו"חלק שבתוך $A$". לכן $P(B)=P(B\setminus A)+P(A\cap B)$, ומכאן $P(B\setminus A)=P(B)-P(A\cap B)$.
  3. מציבים את 2 ב-1, ומקבלים את הנוסחה. ∎

בדיקה בטבלה: $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)$חפיפה נספרת פעמייםחוק ③

שלב 4: טריק המשלים, הכלי הכי שימושי בהסתברות

נניח שהשאלה היא "מה הסיכוי שיקרה לפחות אחד מ..." ("לפחות אחד" פירושו אחד, או שניים, או שלושה, או יותר). ספירה ישירה של כל המקרים עמוסה. אבל "לפחות אחד" ו"אף אחד" הם זה ההפך של זה, ולכן לפי חוק ①:

$$P(\text{לפחות אחד})=1-P(\text{אף אחד}).$$

ו"אף אחד" הוא בדרך כלל מקרה אחד פשוט. המתכון:

  1. נסח את ההפך של מה שנשאלת.
  2. חשב את ההסתברות שלו (בדרך כלל קל).
  3. החסר מ-1.
דוגמה מלאה, צעד אחר צעד

שאלה: מטילים קובייה 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$.

🤖 הצצה ל-ML: חסם האיחוד (אפשר לדלג)

מחוק ③ נובע $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

תרגיל 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)$? במקרה הכי נפוץ (כל התוצאות שוות-סיכוי) התשובה היא "ספור".

5איך מחשבים בפועל? ספירה

❓ אם כל התוצאות שוות-סיכוי, איך מחשבים את $P(A)$? ואיך סופרים כשיש מיליוני תוצאות ואי אפשר לצייר טבלה?

נלך בשלבים: (0) מה הבעיה, (1) עיקרון הכפל, (2) כשהסדר חשוב, (3) כשהסדר לא חשוב, (4) הסתברות באמצעות ספירה, (5) טעויות נפוצות.

שלב 0: המקרה האחיד, וממה נובעת הבעיה

נניח שיש $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 תוצאות. אי אפשר לרשום אותן. צריך לספור בלי לרשום, וזה מה שהשלבים הבאים מלמדים.

שלב 1: עיקרון הכפל

יש לי 3 חולצות ו-2 מכנסיים. כמה תלבושות אפשריות? כל חולצה אפשר לשלב עם כל מכנס, ולכן $3\cdot2=6$. בטבלה:

מכנס אמכנס ב
חולצה 11א1ב
חולצה 22א2ב
חולצה 33א3ב
📐 עיקרון הכפל

אם תהליך מורכב משני שלבים, ובשלב הראשון יש $a$ אפשרויות ובשני $b$ אפשרויות (לכל בחירה בשלב הראשון), אז בסך הכל $a\cdot b$. (יש $a$ שורות, ובכל שורה $b$ תאים.) זה נכון גם לכמה שלבים: מכפילים את כולם.

דוגמאות: שתי קוביות $6\cdot6=36$ (זה ה-$|\Omega|$ שלנו!). סיסמה של 4 ספרות: $10\cdot10\cdot10\cdot10=10^4$.

שלב 2: כשהסדר חשוב

בתחרות ריצה של 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: כשהסדר לא חשוב

עכשיו אותה בחירה, אבל לא לפי תפקיד: בוחרים ועדה של 3 אנשים מתוך 5, וכל השלושה שווים. הסדר לא משנה. קודם נתחיל בדוגמה קטנה כדי להבין את הרעיון: בחירת 2 מתוך $\{A,B,C\}$.

כל קבוצה של 2 נספרה פעמיים בספירה עם סדר ($AB$ ו-$BA$ הן אותה קבוצה). לכן $6\div2=3$.

באותו אופן, בחירת 3 מתוך 5: עם סדר יש 60. כל ועדה של 3 אנשים נספרה $3!=6$ פעמים (כל הסדרים האפשריים של שלושה אנשים). לכן $60\div6=10$.

📐 "$n$ בוחר $k$"
$$\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$$

זה מספר הדרכים לבחור קבוצה של $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$) וסיסמאות.

🔢 מחשבון ספירה
איך קוראים: השורה "סדר חשוב, בלי החזרה" היא $n!/(n-k)!$. "סדר לא חשוב, בלי החזרה" היא $\binom nk$. בשורה "סדר חשוב", העמודה "עם החזרה" היא $n^k$. נסה: n=5, k=3 (ראה 60 ו-10 מהדוגמה). אחר כך n=52, k=5 (ידי פוקר). אחר כך k=n.

שלב 4: הסתברות באמצעות ספירה

דוגמה קטנה (אפשר לרשום הכל): מטילים מטבע 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.

שלב 5: טעויות נפוצות

⚠️ שלוש מלכודות בספירה
➕ הרחבה: מקרה רביעי, "בלי סדר, עם החזרה"

בחירת $k$ פריטים מתוך $n$ סוגים כשאפשר לחזור על סוג, והסדר לא חשוב (למשל 5 כדורי גלידה מ-3 טעמים): $\binom{n+k-1}{k}$ (שיטת "כוכבים וקווים"). נפגוש את זה רק מעט, אז אפשר לדלג. הסבר מלא עם מעבדה וקישור ל-ML בנספח א1.

🤖 קשר ל-ML

ספירה מסבירה למה בעיות ML קשות: יש $2^d$ קבוצות חלקיות של $d$ פיצ'רים, ולכן בחירת פיצ'רים בכוח גס בלתי-אפשרית כבר ב-$d=50$ ($2^{50}\approx10^{15}$). מספר הפונקציות הבוליאניות על $d$ ביטים הוא $2^{2^d}$. מכאן החשיבות של הנחות על המבנה (inductive bias).

תרגול לסעיף 5

תרגיל 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, נבדוק שהם עומדים במבחן המציאות: האם התשובות מתיישבות עם האינטואיציה? לפעמים לא, וזה כשהכי מרוויחים.

6פרדוקס יום ההולדת: כל הכלים ביחד

❓ בכיתה של 23 אנשים, מה הסיכוי שלשניים יש יום הולדת באותו יום?

נלך בשלבים: (0) הגדרת הבעיה, (1) ניחוש, (2) חישוב בשלוש דוגמאות קטנות, (3) הנוסחה, (4) ניסוי חי, (5) למה זה מפתיע.

שלב 0: הגדרת הבעיה

כדי שהשאלה תהיה מדויקת, נניח: יש 365 ימים בשנה (בלי 29 בפברואר), וכל אדם נולד בכל יום בסיכוי שווה, ללא קשר לאחרים. "יש התאמה" פירושו שלפחות שני אנשים נולדו באותו יום.

שלב 1: ניחוש

לפני שמחשבים: כמה היית מנחש? רוב האנשים אומרים 5%–10%. נבדוק.

שלב 2: איך מחשבים? מדגם קטן, שלושה אנשים

נשתמש בכלים שיש לנו:

  1. טריק המשלים. "לפחות שני אנשים חולקים יום" הוא ההפך של "כל הימים שונים". נחשב את ה"הפך" ונחסר מ-1.
  2. ספירה של תוצאות. בשלושה אנשים, כל תוצאה היא שלישייה (יום של אדם 1, יום של אדם 2, יום של אדם 3). לפי עיקרון הכפל יש $365\cdot365\cdot365=365^3$ שלישיות, והן שוות-סיכוי (בדיוק כמו 36 תוצאות הקוביות).
  3. כמה שלישיות עם ימים שונים? לאדם 1: 365 ימים. לאדם 2: נשארו 364 (לא יום של אדם 1). לאדם 3: נשארו 363. סה"כ $365\cdot364\cdot363$ (סדר חשוב, בלי החזרה, שלב 2 בסעיף הקודם).

לכן: $$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$, פחות מאחוז.

שלב 3: הנוסחה ל-$n$ אנשים

אותו חישוב עם $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}$, וכן הלאה.)

שלב 4: ניסוי חי

🎂 כמה אנשים צריך?
נסה: (1) הזז את ה-n ל-3: ראה ~0.8%, כמו שחישבנו. (2) הגדל עד שהעקומה חוצה את 50%: זה ב-n=23. (3) לחץ "סימולציה" ובדוק שהאחוז מתקרב לנוסחה (כמו חוק המספרים הגדולים). (4) הגדל ל-60 ומעלה.

שלב 5: למה זה מפתיע?

💡 אנחנו סופרים אנשים, אבל השאלה היא על זוגות

האינטואיציה שואלת "האם מישהו חולק איתי יום הולדת?", וזה רק 22 השוואות. אבל השאלה האמיתית היא על כל זוג בכיתה: יש $\binom{23}{2}=253$ זוגות (בחירת 2 מתוך 23, בלי סדר: ספירה מהסעיף הקודם). מספר הזוגות גדל ריבועית עם $n$, ולכן ההסתברות מזנקת מהר.

🤖 קשר ל-ML

אותה תופעה גורמת להתנגשויות hash (feature hashing) ולדליפת נתונים בין train ל-test: בדאטהסט גדול מספר הזוגות עצום, ושכפולים כמעט-זהים כמעט מובטחים.

תרגול לסעיף 6

תרגיל 6.1 בדיקת הבנה בכיתה של 366 אנשים, מה הסיכוי שיש התאמה (תתעלם משנה מעוברת)?

תרגיל 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?

7גשר ל-ML: מה זה אומר ש"המודל בטוח ב-90%"?

❓ מסווג מחזיר "חתול: 90%". מאיפה המספר הזה בא, והאם הוא באמת "הסתברות"?

הסעיף הזה הולך לאט, בשלבים. אם שלב לא ברור, עצור שם לפני שאתה ממשיך.

שלב 0: מה זה "מסווג" ו"מחלקה"?

סיווג (classification) היא אחת המשימות הכי נפוצות ב-ML. נותנים למחשב קלט, למשל תמונה, והוא צריך לשייך אותו לאחת מכמה קטגוריות שהוגדרו מראש. למשל: האם בתמונה יש חתול, כלב או ארנב?

💡 איך זה קשור למה שלמדנו?

מנקודת המבט של המודל, המחלקה האמיתית של התמונה היא לא ידועה. יש שלוש אפשרויות, בדיוק כמו שלוש תוצאות של ניסוי מקרי. כלומר: $\Omega=\{\text{חתול},\text{כלב},\text{ארנב}\}$.

המודל רוצה לדווח "כמה הוא מאמין בכל אפשרות". כלומר לתת לכל תוצאה ב-$\Omega$ מספר: $p_{\text{חתול}},\,p_{\text{כלב}},\,p_{\text{ארנב}}$. כדי שהמספרים האלה יהיו "הסתברויות" במובן של סעיף 4 (כשיש מספר סופי של תוצאות), מספיקות שתי דרישות:

  1. כל מספר $\ge 0$.
  2. הסכום של כולם $=1$.

(ואז ההסתברות של מאורע כמו "חתול או כלב" היא פשוט סכום ההסתברויות של תוצאותיו, כי תוצאות שונות הן מאורעות זרים, והאקסיומה השלישית.)

שלב 1: מה המודל באמת מוציא? "ציונים"

בפנים, המודל (למשל רשת נוירונים) מבצע המון חישובים על התמונה, ובסוף מוציא רשימה של $K$ מספרים, אחד לכל מחלקה. נקרא להם ציונים (בז'רגון: logits) ונסמן $z_1,z_2,\dots,z_K$. הסימון $z_i$ פירושו "הציון של מחלקה מספר $i$".

למשל, על תמונה מסוימת המודל מחזיר:

מחלקהחתולכלבארנב
ציון $z$2.01.00.1

המשמעות: ציון גבוה יותר = "התמונה דומה יותר למחלקה הזו". כאן "חתול" מוביל.

⚠️ למה אי אפשר פשוט להשתמש בציונים כהסתברויות?

הציונים יכולים להיות שליליים (למשל $-3$), יכולים להיות גדולים (כמו 17), והסכום שלהם הוא סתם מספר. הסתברות לא יכולה להיות שלילית, ולא יכולה להיות 17. בטבלה למעלה הסכום הוא $3.1$ ולא $1$. אז צריך ממיר שהופך כל רשימת ציונים לרשימה של הסתברויות, ושומר על הסדר (ציון גבוה ⟹ הסתברות גבוהה).

שלב 2: הממיר (softmax) בשני צעדים

נבנה אותו עם הציונים $(2.0,\;1.0,\;0.1)$:

צעד א: להפוך הכל לחיובי, בלי לקלקל את הסדר

מחשבים $e^{z}$ לכל ציון. ($e\approx2.718$ הוא קבוע מתמטי; חשוב רק שהפונקציה $e^x$ תמיד חיובית, גם עבור $x$ שלילי, ושהיא עולה: ציון גבוה יותר נותן תוצאה גבוהה יותר.)

חתולכלבארנב
$z$2.01.00.1
$e^{z}$7.392.721.11

עכשיו כל המספרים חיוביים (דרישה 1 ✔), אבל הסכום הוא בערך $11.2$, עדיין לא 1.

צעד ב: לנרמל, כלומר לתת לכל אחד את "החלק שלו" מהסך הכל

מחלקים כל מספר בסכום של כולם: $7.39+2.72+1.11\approx11.2$.

חתולכלבארנבסכום
$e^{z}$7.392.721.11≈11.2
חלקי הסכום0.6590.2420.0991.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 חי: הזז את הציונים וראה איך ההסתברויות מגיבות
מה לנסות: (1) הגדל את ציון החתול ותראה שהאחרים מתכווצים: העוגה קבועה, והחלק של אחד גדל על חשבון האחרים. (2) הורד ציון ל-4− : ההסתברות כמעט 0 אבל לא שלילית לעולם. (3) הצג את שלושת הציונים שווים: מתקבל 1/3 לכל אחד. (4) לחץ על "הוסף 1 לכל הציונים" והסתכל: ההסתברויות לא משתנות כלל! רק ההפרשים בין הציונים קובעים.

שלב 3: למה זו "הסתברות חוקית"?

בדוק את שתי הדרישות מהתיבה למעלה, עבור כל ציונים אפשריים:

  1. אי-שליליות: $e^{z_i}>0$ ולכן $p_i>0$ ✔
  2. נרמול: $\sum_i p_i=\frac{\sum_i e^{z_i}}{\sum_j e^{z_j}}=1$ ✔ (המונה והמכנה זהים)

לכן הפלט של softmax מקיים את אקסיומות קולמוגורוב (למרחב סופי), וכל מה שלמדנו בשיעור חל עליו: למשל, ההסתברות ש"זה חתול או כלב" היא $p_{\text{חתול}}+p_{\text{כלב}}=0.659+0.242=0.901$, ובטריק המשלים: $1-p_{\text{ארנב}}=1-0.099$.

⚠️ "למה דווקא $e^x$? אפשר להשתמש בפונקציה אחרת?"

שאלה מצוינת, והתשובה הכנה: אפשר. כל פונקציה חיובית ועולה הייתה מקיימת את שתי הדרישות. מה שלא עובד: הרמה בריבוע (ציון $-3$ יקבל יותר מציון $+1$, והסדר מתקלקל) או סתם חילוק בסכום הציונים (ציונים שליליים נותנים הסתברות שלילית). $e^x$ נבחרה כי יש לה תכונה נוספת נוחה (ההפרשים בלבד קובעים, כפי שראית עם הכפתור), וכי היא מתחברת בטבעיות ל-log-likelihood ולנגזרות פשוטות. את זה נבין לעומק בשיעורים 8 ו-10, ובינתיים מספיק לדעת שזו הבחירה הסטנדרטית.

שלב 4: אז מה זה אומר "90%"?

כאן חוזרת השאלה מתחילת השיעור: מהי הסתברות? לפי הפרשנות התדירותית (סעיף 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

תרגיל 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

8סיכום: הסיפור בקצרה

  1. הסתברות = חלק יחסי מתוך הרבה חזרות (חוק המספרים הגדולים; בלי "כשל המהמר").
  2. החלק הוא "של מאורעות": מאורע = קבוצת תוצאות מתוך $\Omega$. בחר $\Omega$ סימטרי ("תצבע את הקוביות").
  3. "או/וגם/לא" = איחוד/חיתוך/משלים, ודה-מורגן הופך ביניהם.
  4. שלוש אקסיומות: לא שלילי, נרמול, אדיטיבי לזרים. מהן נגזרים משלים, מונוטוניות והכלה והפרדה.
  5. במקרה האחיד: $P(A)=|A|/|\Omega|$ וסופרים (כפל, סדר/בלי סדר, "ספור עם עודף וחלק").
  6. טריק המשלים: "לפחות אחד" = 1 פחות "אפס".
  7. ב-ML: softmax חוקי כהסתברות בזכות האקסיומות; ו"נכון" רק אם מכויל.
🔭 בשיעור הבא

כל מה שעשינו הניח שאין לנו שום מידע. מה קורה כשמקבלים מידע חדש ("ידוע שהסכום זוגי, מה הסיכוי שיצא 6?")? זו הסתברות מותנית, וממנה נגיע גם לאי-תלות (הסיבה הכללית לכך ש-(5/6)⁴ הוא מכפלה, שראינו בסעיף 4 דרך ספירה) ולמשפט בייס, הלב של סיווג ב-ML.

← מפת הדרכים שיעור 2 →