מודל הלמידה האינדוקטיבית ולמידה מונחית
מבוא מתמטי ופילוסופי ללמידת מכונה: הגדרת בעיית הקירוב של פונקציית המטרה $f$ באמצעות השערה $h$, מרחב ההשערות $\mathcal{H}$ וגודלו הכפול-מעריכי $2^{2^n}$, סיווג מול רגרסיה, פרדיגמות הלמידה והעיקרון המנחה של תערו של אוקאם.
להבין את האינטואיציה שמאחורי הקלעים: הפער האינדוקטיבי ופרדוקס מרחב ההשערות
בלוגיקה דדוקטיבית קלאסית, המסקנה נובעת בוודאות מוחלטת מתוך ההנחות ($A \to B$). לעומת זאת, למידה אינדוקטיבית נדרשת לבצע "זינוק אמוני" מתמטי: מתוך מדגם תצפיות סופי וחלקי בלבד $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N$, עלינו להכליל ולגלות את פונקציית המטרה האמיתית $f: \mathcal{X} \to \mathcal{Y}$ של היקום.
אם נבחן $n$ תכונות בוליאניות, מרחב הקלטים האפשריים מכיל $2^n$ צירופים, ומספר הפונקציות הבוליאניות האפשריות השונות הוא $|\mathcal{H}| = 2^{2^n}$ – גודל כפול-מעריכי מפלצתי! (עבור 6 תכונות בלבד מדובר בכ-$1.8 \times 10^{19}$ פונקציות). אינספור פונקציות שונות בתוך $\mathcal{H}$ יסכימו במדויק עם נתוני האימון, אך יחזו תוצאות הפוכות לחלוטין על נתון חדש. לכן, למידה ללא הנחות מוקדמות היא בלתי אפשרית מתמטית! הפתרון הוא הטיה אינדוקטיבית (Inductive Bias) המונחית על ידי תערו של אוקאם (Occam's Razor): העדפת ההשערה הפשוטה והקומפקטית ביותר המסבירה את הנתונים.
💡 אינטואיציה בגובה העיניים: משחק 20 השאלות והצופה הזר
דמיינו תייר מכוכב אחר שמביט מבעד לחלון על משחק שחמט. אף אחד לא מסביר לו את החוקים, והוא רואה רק 10 מהלכים ראשונים. קיימים טריליוני "ספרי חוקים" שונים שעקביים עם 10 המהלכים הללו – כולל חוק מופרך שטוען שבמהלך ה-11 הפרש הופך ליונה ועף מהלוח.
מדוע המוח האנושי אינו שוקל אפילו את האפשרות הזו? כי אנחנו מתוכנתים לחפש חוקיות אלגנטית, הרמונית ופשוטה. הלמידה המונחית פועלת בדיוק כך: היא אינה מחפשת סתם "נוסחה שמסכימה עם העבר", אלא את התבנית הקומפקטית ביותר שיש לה סיכוי אמיתי להמשיך לתפקד נכון גם בעתיד.
📊 תרשים 11.1: תהליך הלמידה האינדוקטיבית וארכיטקטורת מרחב ההשערות
מפונקציית המטרה הנסתרת $f$, דרך מדגם האימון $\mathcal{D}$, ועד בחירת ההשערה $h \in \mathcal{H}$ באמצעות תערו של אוקאם
הגדרת הבעיה ויסודות הלמידה המונחית
Supervised Learning Foundations: Target Function, Training Set, and Hypothesis
בלמידת מכונה מונחית (Supervised Learning), מטרת המערכת היא ללמוד פונקציית מיפוי בלתי ידועה מראש, המכונה פונקציית המטרה (Target Function) ומסומנת ב-$f: \mathcal{X} \to \mathcal{Y}$. הפונקציה $f$ מייצגת את החוקיות האמיתית והשלמה של העולם. בעולם האמיתי, $f$ נחשבת למונח תיאורטי בלבד – אין לנו גישה ישירה למבנה שלה, למשוואותיה או לקוד המקור שלה, אלא אך ורק למדגם סופי של דוגמאות מתוכה.
מורכבת מ-$N$ זוגות של קלט-פלט מתויגים: $$\mathcal{D} = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\}$$ כאשר לכל $i$, מתקיים $y_i = f(x_i)$. כל איבר $x_i$ הוא וקטור תכונות (Attributes), והתווית $y_i$ היא התשובה הנכונה (Ground Truth).
פונקציה שהאלגוריתם מציע ומחלץ מתוך מרחב ההשערות ($\mathcal{H}$), השואפת לדמות ולקרב את פונקציית המטרה האמיתית: $$h \approx f, \quad h: \mathcal{X} \to \mathcal{Y}$$ השערה מוצלחת מסוגלת להכליל (Generalize) ולנבא במדויק ערכים עבור קלטים חדשים $x \notin \mathcal{D}$.
השערה $h$ מוגדרת כעקבית אם היא מסכימה ומנבאת במדויק ובאופן מושלם את ערכי $f$ על פני כל הדוגמאות בקבוצת האימון ללא יוצא מן הכלל: $$\forall (x_i, y_i) \in \mathcal{D}: \quad h(x_i) = y_i$$
סיווג: כאשר מרחב הפלטים $\mathcal{Y}$ הוא בדיד וקטגורי (למשל $\{0, 1\}$, $\{$חולה, בריא$\}$, $\{$פילאטיס, ריצה$\}$).
רגרסיה: כאשר מרחב הפלטים $\mathcal{Y}$ הוא רציף ומספרי (למשל $\mathcal{Y} \subseteq \mathbb{R}$, כגון חיזוי מחיר מניה, טמפרטורה או צריכת דלק).
שלוש פרדיגמות הלמידה במכונה
Supervised, Unsupervised, and Reinforcement Learning Taxonomy
תחום למידת המכונה נחלק לשלוש פרדיגמות מרכזיות, הנבדלות זו מזו באופי הנתונים, בנוכחותו של תיוג חיצוני, ובסוג המשוב (Feedback) שהאלגוריתם מקבל:
| מאפיין השוואתי | למידה מונחית (Supervised) | למידה בלתי מונחית (Unsupervised) | למידת חיזוק (Reinforcement) |
|---|---|---|---|
| אופי הנתונים | זוגות מתויגים $(x_i, y_i)$ | קלטים בלבד $\{x_i\}$ (ללא תוויות) | מצבים (States), פעולות ותגמולים |
| מטרת האלגוריתם | מציאת $h \approx f$ לחיזוי פלט על קלט חדש | גילוי תבניות, אשכולות (Clusters) ומבנים סמויים | למידת מדיניות $\pi^*$ הממקסמת תגמול מצטבר |
| סוג המשוב (Feedback) | מיידי ומדויק לכל דוגמה (תיוג ישיר) | ללא משוב חיצוני מפורש כלל | מושהה (Delayed) וסקלרי (חיזוק חיובי/עונש) |
| משימות קלאסיות | סיווג תמונות, אבחון רפואי, עצי החלטה | K-Means, PCA, פילוח לקוחות, איתור חריגות | משחקי לוח (שחמט, Go), ניווט רובוטים אוטונומיים |
התער של אוקאם (Ockham's Razor) ועקרון הפשטות
Simplicity Principle, Generalization, and Inductive Bias
"אין להרבות בישים ללא צורך" (Entia non sunt multiplicanda praeter necessitatem).
בהקשר של למידה מונחית: מבין כל ההשערות העקביות עם קבוצת האימון, יש להעדיף תמיד את ההשערה הפשוטה ביותר.
המתח בין עקביות מושלמת להכללה (Generalization):
בניית מודל שיהיה עקבי ב-100% עם קבוצת האימון היא משימה קלה אך מטעה. מודל מורכב ביותר (כגון פולינום מדרגה גבוהה או עץ החלטה עמוק עד רמת דוגמה בודדת בעלה) עלול להשיג אפס שגיאות אימון, אך למעשה הוא שינן את רעשי הרקע (Noise) של המדגם המסוים הזה. כאשר יגיעו דוגמאות חדשות מתוך אותה התפלגות סטטיסטית, המודל המורכב יקרוס וישגה קשות. תופעה הרסנית זו מכונה התאמת-יתר (Overfitting).
לעומת זאת, מודל פשוט מניח פחות הנחות ספקולטיביות על המבנה הנסתר של העולם, מתעלם מרעשים אקראיים נקודתיים, ומייצג את התבנית המרכזית והעקבית של הנתונים. לכן, פשטות המודל מגנה עליו מפני שגיאות מבחן עתידיות.
מורכבות מרחב ההשערות: הגידול הכפול-מעריכי $2^{2^n}$
Boolean Hypothesis Space Size and the Impossibility of Exhaustive Search
נניח בעיית סיווג בינארית שבה הדוגמאות מיוצגות על ידי $n$ תכונות (Attributes) בוליאניות: $X_1, X_2, \dots, X_n \in \{0, 1\}$.
- מספר הצירופים השונים של ערכי התכונות (מספר שורות בטבלת האמת של מרחב הקלט) הוא: $2^n$.
- פונקציית מטרה בוליאנית $f$ קובעת עבור כל שורה בטבלת האמת פלט של $0$ או $1$.
- לפיכך, מספר הפונקציות הבוליאניות השונות האפשריות מעל $n$ משתנים הוא: $$\mathbf{|\mathcal{H}| = 2^{2^n}}$$
משמעות אלגוריתמית: מכיוון שלא ניתן לסרוק את כל מרחב ההשערות $\mathcal{H}$, אנו חייבים להשתמש באלגוריתמי למידה מבוססי הטיה אינדוקטיבית (Inductive Bias) וחיפוש היוריסטי חמדני (כדוגמת DTL/ID3), שמנווטים ישירות לעבר עצים פשוטים וקומפקטיים.
מגרש המשחקים של מרחב ההשערות (The Hypothesis Playground)
המחשה אינטראקטיבית של גבולות החלטה (Decision Boundaries), מורכבות מודל, תערו של אוקאם, והזרקת נתוני מבחן לחשיפת התאמת-יתר.
עצי החלטה ואלגוריתם הלמידה DTL / ID3
היררכיית עץ החלטה, מודל "קופסה לבנה" (White-box model), הוכחת ה-NP-שלמות של מציאת עץ אופטימלי, הפסאודו-קוד של אלגוריתם DTL ושלושת תנאי העצירה הקריטיים, ודוגמת ההמתנה במסעדה.
להבין את האינטואיציה שמאחורי הקלעים: פילוסופיית הקופסה הלבנה וחיפוש חמדני
מדוע עצי החלטה הם מודל הדגל של ה-White-Box AI? בשונה מרשתות עצביות עמוקות הפועלות כ"קופסה שחורה" בלתי ניתנת לפיענוח, עץ החלטה מעניק שקיפות מלאה (Interpretability): כל החלטה ניתנת לתרגום ישיר לרצף של כללי היסק לוגיים ($IF \dots THEN$).
עם זאת, התיאוריה מוכיחה כי מציאת עץ ההחלטה האופטימלי הקטן ביותר היא בעיה NP-Complete! חיפוש מלא על פני כל העצים האפשריים אינו מעשי חישובית. לכן אלגוריתם DTL (ו-ID3) מאמץ גישה חמדנית (Greedy Top-Down Induction): בכל צומת נבחרת התכונה המפצלת הטובה ביותר מקומית, מבלי להביט צעד אחד קדימה (No Backtracking). מנגנון זה מחייב 3 תנאי עצירה רקורסיביים מוחלטים:
1. עלה טהור: כל הדוגמאות שנותרו שייכות לאותה מחלקה.
2. ענף ריק: לא הגיעו דוגמאות לענף (נחזיר עלה עם רוב האב - Default Prior).
3. מיצוי תכונות עם רעש: נותרו דוגמאות בעלות תוויות שונות אך ללא תכונות נוספות להבדלה (נחזיר עלה עם רוב מקומי - Current Mode).
💡 אינטואיציה בגובה העיניים: הרופא המומחה במיון דחוף
כשמטופל נכנס לחדר מיון, הרופא אינו שואל 40 שאלות אקראיות בסדר שרירותי ("מה מידת הנעליים שלך?", "האם אכלת תפוח אתמול?"). הרופא המנוסה שואל קודם כל את השאלה המבדלת והקריטית ביותר: "האם יש כאב חריף בחזה או קוצר נשימה?".
תשובה אחת חותכת מיד 90% מהמחלות האפשריות ומנתבת את המטופל למסלול ייעודי. בכל שלב, הרופא שואל את השאלה הבאה שמצמצמת את חוסר הוודאות בצורה המרבית. עץ החלטה מבצע בדיוק את אותו הליך אבחון מובנה וקפדני – שלב אחר שלב, עד לקבלת דיאגנוזה ודאית.
📊 תרשים 11.2: אנטומיית עץ ההחלטה וההחלטה החמדנית של אלגוריתם DTL
מבנה הצמתים: צומת שורש, פיצולים לפי רווח מידע, 3 תנאי עצירה רקורסיביים ועלי סיווג
מבנה עץ ההחלטה ומודל הקופסה הלבנה
Internal Nodes, Branches, Leaf Nodes, and Rule Extraction
עץ החלטה (Decision Tree) הוא ייצוג היררכי אינטואיטיבי הממפה מאפייני קלט לסיווג סופי. המודל מורכב משני סוגי צמתים עיקריים:
כל צומת פנימי מייצג שאלת בדיקה (Test) על ערכה של תכונה מסוימת $X$. מכל צומת כזה יוצאים ענפים המייצגים את הערכים האפשריים השונים שהתכונה יכולה לקבל: $v_1, v_2, \dots, v_k$.
צומת קצה ללא ענפים יוצאים המכיל את התחזית (סיווג המטרה). כאשר לעלה מגיעות דוגמאות בעלות תוויות שונות (עלה שאינו טהור), הסיווג נקבע לפי הצבעת רוב (Majority Vote / MODE) של הדוגמאות שהגיעו לאותו עלה.
בניגוד לרשתות נוירונים או מודלים מורכבים הנחשבים ל"קופסה שחורה" (Black-box), עצי החלטה ניתנים להסבר מלא (Interpretable). כל מסלול מהשורש ועד לעלה ספציפי ניתן לתרגום ישיר לחוק לוגי תקני בצורת פסוקי תנאי:
סיבוכיות חישובית: מדוע נדרש אלגוריתם חמדני?
NP-Completeness of Minimal Decision Trees and Quinlan's ID3 Solution
בשל גודל מרחב ההשערות המפלצתי ($2^{2^n}$ עצים), לא קיים אלגוריתם היכול להבטיח מציאת עץ אופטימלי גלובלי בזמן פולינומיאלי. כדי לעקוף מחסום זה, פיתח רוס קווינלן (Ross Quinlan) את אלגוריתם ה-ID3, המוכר במבנהו הכללי כאלגוריתם DTL (Decision Tree Learning).
אלגוריתם ה-DTL מאמץ גישה חמדנית (Greedy Approach) מלמעלה למטה: בכל שלב רקורסיבי, הוא בוחר את התכונה שמספקת את ההפרדה הסטטיסטית הטובה ביותר באופן מקומי, מבלי לחקור צעדים עתידיים ומבלי לבצע נסיגה לאחור (No Backtracking).
הפסאודו-קוד של DTL וארבעת מצבי הפיצול והעצירה
Recursive Partitioning, The 4 Core Conditions, and Multi-Valued Attributes
function DTL(examples, attributes, parent_examples) returns a decision tree
// תנאי 1: לא הגיעו דוגמאות אימון לענף זה (ענף ריק)
if examples is empty then return PLURALITY-VALUE(parent_examples)
// תנאי 2: כל הדוגמאות חולקות את אותו הסיווג בדיוק (עלה טהור)
else if all examples have the same classification then return the classification
// תנאי 3: רשימת התכונות התרוקנה אך יש סיווגים סותרים (רעש / מחסור בתכונות)
else if attributes is empty then return PLURALITY-VALUE(examples)
// תנאי 4: שלב הפיצול הרקורסיבי החמדני (בחירת התכונה הטובה ביותר)
else
best ← CHOOSE-ATTRIBUTE(attributes, examples)
tree ← a new decision tree with root test best
for each value v_i of best do
examples_i ← {e : e ∈ examples and e.best = v_i}
subtree ← DTL(examples_i, attributes - best, examples)
add a branch to tree with label v_i and subtree subtree
return tree
לאף דוגמת אימון לא היה הערך $v_i$. מייצרים עלה עם רוב צומת האב (parent_examples) המשמש כ-Prior הסתברותי עבור דוגמאות מבחן עתידיות שיגיעו לענף זה.
כל הדוגמאות שהגיעו שייכות לתווית אחת (למשל 100% "כן" או 100% "לא"). האנטרופיה היא $H=0$. העצירה מיידית והעלה מסווג לפלח זה.
נותרו דוגמאות אך נגמרו כל התכונות לבדיקה, והסיווגים סותרים (מעיד על רעש או אי-דטרמיניזם). הסיווג נקבע לפי רוב הדוגמאות המקומיות הנוכחיות (examples).
נותרו דוגמאות מגוונות ותכונות פנויות. נבחרת התכונה הממקסמת את רווח המידע $Gain(A)$, ונוצרים ענפים עבור כל ערך אפשרי $v_i \in Values(A)$.
מרצים במבחנים מרבים לבחון האם התלמיד מבין מאיזה מאגר נלקח רוב הקולות בכל תרחיש עצירה:
| מאפיין ההשוואה | תנאי 1: ענף ריק (examples is empty) | תנאי 3: התרוקנות תכונות (attributes is empty) |
|---|---|---|
| מצב הדוגמאות | אפס דוגמאות הגיעו לענף ($|examples| = 0$) | ישנן דוגמאות בענף, אך סיווגיהן סותרים |
| מצב התכונות | ייתכן שנותרו עוד תכונות רבות שלא נבדקו | כל התכונות נבדקו במסלול מהשורש ונוצלו ($|attributes| = 0$) |
| מקור קביעת הסיווג | PLURALITY(parent_examples) - צומת האב! | PLURALITY(examples) - הדוגמאות המקומיות הנוכחיות! |
| משמעות תיאורטית | חוסר כיסוי בסט האימון. אומדן בייסיאני אפרופו האב. | רעש בנתונים (Noise) או שתי דוגמאות זהות בתכונות אך שונות בתיוג. |
חישוב אנטרופיה ורווח מידע לתכונה בעלת 3 ערכים (או יותר)
כאשר תכונה $A$ מקבלת 3 ערכים אפשריים $\{v_1, v_2, v_3\}$ (למשל: Patrons ∈ {None, Some, Full} או Temp ∈ {Cool, Mild, Hot}), נוסחת האנטרופיה השיורית ($Remainder$) מתפצלת ל-3 איברים משוקללים:
- ערך $v_1$ (4 דוגמאות): 2 חיוביות, 2 שליליות ← $B(2/4) = 1.0$. משקל: $4/12 = 1/3$.
- ערך $v_2$ (4 דוגמאות): 4 חיוביות, 0 שליליות ← $B(4/4) = 0$ (עלה טהור!). משקל: $4/12 = 1/3$.
- ערך $v_3$ (4 דוגמאות): 0 חיוביות, 4 שליליות ← $B(0/4) = 0$ (עלה טהור!). משקל: $4/12 = 1/3$.
מקרה המבחן הקלאסי: ההחלטה האם להמתין במסעדה
The 12-Example Restaurant Dataset & Feature Partitioning
מטרת הסוכן היא לנבא האם לקוח ימתין לשולחן במסעדה (משתנה המטרה $Wait \in \{T, F\}$) בהינתן 10 תכונות שונות ו-12 דוגמאות אימון שבהן חלוקה שווה: 6 דוגמאות חיוביות ($T$) ו-6 שליליות ($F$).
| דוגמה | Patrons (סועדים) | Hungry (רעב) | Type (סוג מסעדה) | Fri/Sat | WaitEstimate | Wait? (מטרה) |
|---|---|---|---|---|---|---|
| $X_1$ | Some | T | French | F | 0-10 | T |
| $X_2$ | Full | T | Thai | F | 30-60 | F |
| $X_3$ | Some | F | Burger | F | 0-10 | T |
| $X_4$ | Full | T | Thai | F | 10-30 | T |
| $X_5$ | Full | F | French | F | >60 | F |
| $X_6$ | Some | T | Italian | F | 0-10 | T |
| $X_7$ | None | F | Burger | F | 0-10 | F |
| $X_8$ | Some | T | Thai | F | 0-10 | T |
| $X_9$ | Full | F | Burger | F | >60 | F |
| $X_{10}$ | Full | T | Italian | T | 10-30 | F |
| $X_{11}$ | None | F | Thai | F | 0-10 | F |
| $X_{12}$ | Full | T | Burger | T | 30-60 | T |
Patrons (כמות הסועדים: None, Some, Full) מפרידה באופן כמעט מיידי:
עבור Some (4 דוגמאות) כולן ממתינות (100% $T$) ← עלה טהור!
עבור None (2 דוגמאות) כולן עוזבות (100% $F$) ← עלה טהור!
עבור Full (6 דוגמאות) ישנן 2 חיוביות ו-4 שליליות, ולכן הענף מצריך פיצול נוסף (תכונת רעב Hungry).
חמשת האתגרים המעשיים המרכזיים בלמידת עצי החלטה
חמשת האתגרים המעשיים המרכזיים: רעש, מחסור בדוגמאות, תכונות רציפות, מחיר בדיקות וערכים חסרים
בעולם האקדמי והמעשי, אלגוריתם ID3 הבסיסי נתקל במגבלות כאשר הנתונים אינם אידיאליים. להלן ניתוח 5 אתגרים קריטיים ופתרונם האלגוריתמי המלא:
הבעיה: דוגמאות אימון שגויות, או דוגמאות בעלות ערכי תכונות זהים לחלוטין אך סיווגים סותרים (למשל אחת "חיובית" ואחת "שלילית"). בעץ נוצר מצב שבו לא ניתן לפצל עוד את הצומת (מוצו כל התכונות), אך הדוגמאות בעלה אינן טהורות.
הבעיה: תכונה מסוימת כוללת ערך אפשרי (למשל צבע "צהוב"), אך בקבוצת האימון הנוכחית של הצומת לא הגיעה אף דוגמה עם ערך זה ($|Examples| = 0$).
הבעיה: אלגוריתם ID3 המקורי מתאים רק לתכונות בדידות (דיסקרטיות). מה עושים עם תכונה מספרית רציפה כמו משקל, גובה או טמפרטורה?
- דיסקרטיזציה סטטית: חלוקה מוגדרת מראש לתחומים קבועים (למשל: נמוך, בינוני, גבוה).
- דיסקרטיזציה דינמית: מציאת סף חיתוך אופטימלי $t$ הממקסם את רווח המידע $IG(A > t)$ מתוך הערכים שמופיעים בדוגמאות האימון.
הבעיה: בעולם האמיתי (למשל בדיקות רפואיות), מדידת דופק עולה 10 שקלים ואינה פולשנית, בעוד בדיקת MRI עולה 5,000 שקלים. בחירה עיוורת לפי $IG$ בלבד עלולה לשלוח מטופלים לבדיקות יקרות ומיותרות.
כאשר בדוגמת אימון מסוימת ערך התכונה חסר ("לא ידוע"):
מפל הנתונים החזותי (Visual Data Cascade)
סימולציית מפל פיזיקלית להמחשת זרימת הדוגמאות, פיצול צמתים לפי תכונות, נעילת עלים טהורים ופעולת אלגוריתם ה-DTL.
תורת האינפורמציה: אנטרופיה, שארית ותוספת מידע
היסודות המתמטיים של קלוד שאנון לבחירת תכונות ב-DTL: מדד האנטרופיה $H(Y)$, אנטרופיה מותנית ושארית (Remainder), תוספת אינפורמציה (Information Gain - $IG$), וחישוב צעד-אחר-צעד עבור בעיית המסעדה.
להבין את האינטואיציה שמאחורי הקלעים: תורת המידע וכימות חוסר הוודאות של שנון
כיצד אלגוריתם מתמטי יודע איזה פיצול הוא "הטוב ביותר"? קלוד שנון (Claude Shannon, 1948) הניח את היסודות למהפכת המידע עם הגדרת האנטרופיה $H(V)$: כמות המידע הממוצעת (בביטים) הנדרשת לקידוד תוצאה של משתנה אקראי. עבור תוצאה בוליאנית עם הסתברות $q$ להצלחה: $$B(q) = -q \log_2(q) - (1-q) \log_2(1-q)$$
כאשר $q=0.5$ (אי-ודאות מקסימלית, הטלת מטבע הוגן), $B(0.5) = 1.0\text{ bit}$. כאשר הקבוצה טהורה לחלוטין ($q=0$ או $q=1$), מתקיים בהגדרה $0 \log_2(0) = 0$ והאנטרופיה מתאפסת $B(q) = 0$. רווח המידע (Information Gain) הוא מדד השיפור: $$IG(A) = H(Y) - \text{Remainder}(A)$$ כאשר $\text{Remainder}(A) = \sum_{v} \frac{p_v + n_v}{p + n} B\left(\frac{p_v}{p_v + n_v}\right)$ הוא ממוצע האנטרופיות המשוקלל של תת-הקבוצות לאחר הפיצול.
💡 אינטואיציה בגובה העיניים: תחנת רדיו רועשת ופיצוח קוד מורס
דמיינו שאתם מאזינים למקלט רדיו ישן שמשדר רעש "שלג" סטטי מחריש אוזניים. זהו מצב של אנטרופיה מקסימלית (1 ביט): כל שבריר שנייה מלא ברעש כאוטי ואין לכם שמץ של מושג איזה צליל יגיע מיד.
פתאום מישהו מסובב את כפתור התדרים והאות מתייצב על צליל מורס קבוע וברור: 'ביפ... ביפ...'. חוסר הוודאות צנח לאפס! רווח המידע (Information Gain) הוא בדיוק המרחק שבין הרעש הסטטי המבולבל לצליל הצלול והחד. בכל צומת בעץ ההחלטה, אנו בוחרים את השאלה שמסובבת את כפתור הרדיו ומנקה את כמות הרעש הגדולה ביותר.
📊 תרשים 11.3: עקומת אנטרופיית שנון הבוליאנית $B(q)$ ומאזן רווח המידע $IG(A)$
גרף התפלגות אי-הוודאות המקסימלית ($B(0.5)=1.0$) ומאזן החיסור: $IG(A) = H(Y) - \text{Remainder}(A)$
אנטרופיה (Entropy): מדד האי-סדר וחוסר הוודאות
Claude Shannon's Mathematical Measure of Information & Chaos
כדי לממש את הפונקציה CHOOSE-ATTRIBUTE הקובעת את טיב הפיצול, אלגוריתם ה-ID3 משתמש במדד האנטרופיה שפותח על ידי אבי תורת האינפורמציה, קלוד שאנון.
הגדרה ומשמעות פיזיקלית-מתמטית: אנטרופיה היא מדד כמותי לרמת האי-סדר, חוסר הוודאות או ה"לכלוך" (Impurity) בצומת. במילים פשוטות: כמה שאלות כן/לא (בביטים) נדרשות בממוצע כדי לנחש בוודאות את התווית של דוגמה המוגרלת באקראי מתוך הצומת?
עבור סיווג בינארי שבו פרופורציית הדוגמאות החיוביות היא $q = \frac{p}{p+n}$ והשליליות היא $1-q = \frac{n}{p+n}$: $$B(q) = -q \log_2(q) - (1-q) \log_2(1-q)$$ או בסימון שכיחויות: $$I\left(\frac{p}{p+n}, \frac{n}{p+n}\right) = -\frac{p}{p+n} \log_2\left(\frac{p}{p+n}\right) - \frac{n}{p+n} \log_2\left(\frac{n}{p+n}\right)$$
אנטרופיה מותנית ושארית האנטרופיה (Remainder)
Conditional Entropy After Splitting by Feature X
כאשר אנו בוחנים פיצול לפי תכונה מסוימת $X$, עלינו למדוד כמה אי-ודאות תישאר במשתנה המטרה $Y$ לאחר שביררנו את ערכו של $X$. מדד זה מכונה אנטרופיה מותנית (Conditional Entropy) או שארית (Remainder).
השארית מחושבת כממוצע משוקלל של האנטרופיות של כל תת-הקבוצות שנוצרו, לפי גודלן היחסי מתוך כלל הדוגמאות בקבוצת האב:
רציונל המשקולות: תת-קבוצה המכילה 90% מהדוגמאות משפיעה הרבה יותר על חוסר הוודאות של המודל מאשר תת-קבוצה זניחה המכילה דוגמה בודדת. לכן, כל ענף משוקלל בפרופורציה $\frac{p_i + n_i}{p + n}$.
תוספת אינפורמציה (Information Gain - $IG$)
Mutual Information and Feature Selection Criterion
רווח מידע (Information Gain - $IG$) מבטא בדיוק את מידת הפחתת האנטרופיה (צמצום הכאוס) שהושגה הודות לפיצול לפי התכונה $A$:
חישוב מפורט צעד-אחר-צעד: דוגמת המסעדה
Mathematical Breakdown for Patrons vs. Type Attributes
נבחן את 12 דוגמאות המסעדה, שבהן יש 6 דוגמאות חיוביות ($p=6$) ו-6 שליליות ($n=6$). האנטרופיה ההתחלתית בשורש העץ: $$H(\text{Root}) = I\left(\frac{6}{12}, \frac{6}{12}\right) = -0.5 \log_2(0.5) - 0.5 \log_2(0.5) = \mathbf{1.0 \text{ bit}}$$
4 חיוביות, 0 שליליות.
$I(4/4, 0/4) = \mathbf{0 \text{ bits}}$.
0 חיוביות, 2 שליליות.
$I(0/2, 2/2) = \mathbf{0 \text{ bits}}$.
2 חיוביות, 4 שליליות.
$I(2/6, 4/6) = \mathbf{0.918 \text{ bits}}$.
עבור כל אחד מארבעת סוגי המסעדות, יש פיזור שווה בדיוק של חיוביות ושליליות: צרפתית (1+, 1-), איטלקית (1+, 1-), תאילנדית (2+, 2-), המבורגר (2+, 2-). האנטרופיה של כל ענף היא $I(0.5, 0.5) = 1.0$.
תובנה מרכזית: $IG(Type) = 0$ מעיד שתכונת סוג המסעדה אינה מספקת שום מידע מועיל לסיווג, וההתפלגות אחריה כאוטית בדיוק כפי שהייתה לפניה!
תרגיל מפתח מהבחינה: מערכת לניבוי "האם אני אוהב מעדן חלב?"
שאלת דגל ממבחני הקורס – 14 דוגמאות, 5 תכונות, חישוב אנטרופיית שורש I(10, 4) וחישוב Gain לתכונת הטעם
נתונה טבלת נתונים אמיתית של 14 מעדני חלב (מסומנים $A$ עד $N$) המתוארים על ידי 5 תכונות: אחוזי שומן (עד 3%, עד 10%, מעל 10%), טעם (וניל, שוקולד, פירות, אחר), קצפת (יש/אין), כמות סוכר (נמוך/גבוה), וחתיכות ותוספות (יש/אין). משתנה המטרה הוא "אוהב?" ($כן / לא$).
| מעדן | אחוזי שומן | טעם (Taste) | קצפת | כמות סוכר | תוספות וחתיכות | אוהב? (מטרה) |
|---|---|---|---|---|---|---|
| A | מעל 10% (גבוה) | וניל | יש | גבוה | עם | כן |
| B | עד 10% (בינוני) | שוקו | אין | נמוך | בלי | כן |
| C | עד 3% (נמוך) | וניל | יש | נמוך | עם | כן |
| D | עד 3% (נמוך) | פירות | אין | נמוך | בלי | כן |
| E | עד 10% (בינוני) | אחר | יש | גבוה | בלי | כן |
| F | מעל 10% (גבוה) | אחר | יש | נמוך | עם | כן |
| G | מעל 10% (גבוה) | וניל | אין | גבוה | עם | כן |
| H | מעל 10% (גבוה) | שוקו | יש | גבוה | בלי | כן |
| I | עד 10% (בינוני) | וניל | אין | נמוך | עם | לא |
| J | עד 3% (נמוך) | אחר | יש | נמוך | עם | לא |
| K | מעל 10% (גבוה) | אחר | יש | נמוך | עם | לא |
| L | מעל 10% (גבוה) | שוקו | אין | גבוה | בלי | לא |
| M | עד 3% (נמוך) | פירות | אין | גבוה | בלי | לא |
| N | עד 10% (בינוני) | פירות | אין | נמוך | בלי | לא |
מתוך 14 מעדנים: 10 חיוביים ($p=10$, "כן") ו-4 שליליים ($n=4$, "לא"):
תכונת הטעם מפצלת את 14 הדוגמאות ל-4 ענפים:
3 חיוביות, 1 שלילית.
I(3, 1) = 0.8113 bits
2 חיוביות, 1 שלילית.
I(2, 1) = 0.9183 bits
1 חיובית, 2 שליליות.
I(1, 2) = 0.9183 bits
2 חיוביות, 2 שליליות.
I(2, 2) = 1.0000 bit
בהשוואה בין כל חמש התכונות של מעדן החלב, תכונת הטעם (Taste) היא זו שהניבה את האנטרופיה המשוקללת הנמוכה ביותר ביחס לשאר התכונות (אחוזי שומן, קצפת, סוכר ותוספות), ולכן היא זו שנבחרה לפתוח את שורש עץ ההחלטה! לאחר מכן, בכל תת-עץ (וניל, שוקו, פירות, אחר) חוזרים רקורסיבית על התהליך עם התכונות הנותרות עד לקבלת עלים טהורים.
שולחן המיון והאנטרופיה הדינמי (Dynamic Entropy Workbench)
המחשה בזמן אמת של מד כאוס (Analog Entropy Gauge), עקומת $B(q)$, חישוב שארית משוקללת ורווח מידע אינטראקטיבי.
התאמת-יתר, גיזום (Pruning) ושיווי משקל הטיות-שונות
התמודדות עם תופעת ה-Overfitting בעצי החלטה עמוקים: מאזן Bias-Variance, אפקט האופק (Horizon Effect), גיזום מראש לעומת גיזום בדיעבד, אלגוריתמי REP ו-Cost-Complexity ($R_\alpha(T)$), ומבוא לאנסמבל ויערות אקראיים (Random Forests).
להבין את האינטואיציה שמאחורי הקלעים: טרגדיית התאמת-היתר ומדע הגיזום
אם נאפשר לאלגוריתם DTL לרוץ ללא מגבלה על נתונים ללא סתירות, הוא תמיד יבנה עץ בעל 0% שגיאת אימון ($E_{train} = 0$). אך זוהי אשליה מסוכנת: העץ אינו לומד את החוקיות הכללית, אלא פשוט משנן את רעשי המדגם (Overfitting). ככל שהעץ עמוק ומסועף יותר, השונות שלו (Variance) מזנקת, ושגיאת ההכללה על נתונים חדשים ($E_{test}$) מתפוצצת.
כדי להילחם בכך פותחו שתי אסטרטגיות גיזום מרכזיות:
1. גיזום מקדים (Pre-pruning / Early Stopping): עצירת פיצול הצומת מראש אם מספר הדוגמאות קטן מדי או שרווח המידע אינו מובהק סטטיסטית (מבחן $\chi^2$). חיסרון: קוצר ראייה (Horizon Effect).
2. גיזום פוסט-אופטימיזציה (Post-pruning / Cost-Complexity): גידול עץ מלא ואז כריתת ענפים מלמטה למעלה על ידי מזעור פונקציית העלות הממושטרת $R_\alpha(T) = R(T) + \alpha |T|$ על גבי קבוצת אימות בלתי תלויה (Validation Set).
💡 אינטואיציה בגובה העיניים: הסטודנט שמשנן מבחנים מול הבנה עקרונית
חשבו על סטודנט שמכין עצמו למבחן על ידי שינון מוחלט של כל הפתרונות מ-10 השנים האחרונות, עד רמת הפסיק והנקודה. בבחינות התרגול בבית הוא משיג 100 עגול! אך בבחינה האמיתית, המרצה משנה רק ספרה אחת קטנה בשאלה. הסטודנט ששינן נכשל לחלוטין כי הוא לא הבין את העיקרון הפיזיקלי, אלא רק שינן את צירוף המילים.
עץ החלטה שאינו גזום מתנהג בדיוק כמו הסטודנט הזה: הוא מייצר ענף נפרד לכל תצפית חריגה ורועשת. גיזום העץ (Pruning) הוא פעולת המשמעת שמאלצת את המודל למחוק את החוקים המיקרוסקופיים ולהישאר אך ורק עם עקרונות המפתח הרחבים והחזקים.
📊 תרשים 11.4: דינמיקת התאמת-היתר (Overfitting) וארכיטקטורת גיזום עלויות-מורכבות
שגיאת אימון מול שגיאת מבחן כפונקציה של גודל העץ, ונקודת הגיזום האופטימלית $\alpha$
תופעת התאמת-היתר (Overfitting) ומאזן Bias-Variance
The Problem of Memorizing Noise and the Bias-Variance Dilemma
כאשר עץ החלטה צומח ללא כל הגבלות, האלגוריתם ממשיך לפצל את הנתונים עד שכל העלים הופכים לטהורים (Pure Leaves), לעיתים עד לרמה שכל עלה מכיל דוגמה אחת בלבד. עץ כזה ישיג אמנם 100% דיוק על קבוצת האימון ($E_{train} = 0$), אך במקביל הוא:
- משנן את רעשי הרקע האקראיים (Random Noise) וחריגים (Outliers).
- יוצר גבולות החלטה (Decision Boundaries) סבוכים ומפורצים המלאים במובלעות זעירות.
- כושל לחלוטין בביצוע הכללה לנתונים חדשים, מה שמתבטא בשגיאת מבחן גבוהה במיוחד ($E_{test} \gg E_{train}$).
הטיה נמוכה (Low Bias) + שונות גבוהה (High Variance):
המודל גמיש במיוחד ויכול לקרב פונקציות מסובכות, אך הוא רגיש באופן מופרז לשינויים זעירים במדגם האימון. תוספת דוגמה בודדת יכולה לשנות לחלוטין את מבנה העץ.
הטיה גבוהה (High Bias) + שונות נמוכה (Low Variance):
המודל יציב ואינו מושפע מרעשים מקומיים, אך הוא פשטני מדי ואינו מסוגל לתפוס את התבניות המרכזיות בנתונים (תת-התאמה / Underfitting).
אסטרטגיות גיזום: מראש (Pre) מול בדיעבד (Post)
Early Stopping, The Horizon Effect, and Post-Pruning Reliability
כדי לרסן את מורכבות העץ, מפותחות שתי גישות עקרוניות לגיזום:
עצירת צמיחת העץ בטרם עת על בסיס קריטריונים קשיחים: הגבלת עומק מקסימלי (Max Depth), דרישת כמות דוגמאות מינימלית בעלה, או עצירה אם רווח המידע $IG$ נמוך מסף $\epsilon$.
בגישה זו, מאפשרים לעץ לגדול במלואו עד תומו (Overfit Tree), ולאחר מכן מקצצים ענפים מיותרים בסדרת בדיקות "מלמטה למעלה" (Bottom-Up).
אלגוריתמי גיזום בדיעבד: REP ו-Cost-Complexity
Reduced Error Pruning and Cost-Complexity Regularization
- שיטת "מלמטה-למעלה" המשתמשת בקבוצת אימות נפרדת (Validation Set) שלא שימשה לבניית העץ.
- עבור כל צומת פנימי, האלגוריתם בוחן מה יקרה אם נסיר את תת-העץ שלו ונהפוך אותו לעלה יחיד המסווג לפי הצבעת רוב.
- הקיצוץ מתבצע אם ורק אם ביצועי הדיוק על קבוצת האימות אינם יורדים (או משתפרים) כתוצאה מהסרת תת-העץ.
- איסור מתודולוגי חמור: לעולם אין לבצע REP על בסיס קבוצת האימון, משום שעל סט האימון הסרת ענף לעולם לא תקטין שגיאה!
הגישה המרכזית באלגוריתם ה-CART. גישה זו מייצרת אמת מידה המאזנת בין שגיאת המודל לבין מורכבותו באמצעות פרמטר עונש (Penalty) $\alpha \ge 0$:
שגיאת הסיווג של העץ $T$ על פני הנתונים.
מספר עלי הקצה (סמן למורכבות המבנית של העץ).
מקדם הרגולציה הקובע את מחיר המורכבות.
כדי לעקוף את השונות הגבוהה (Variance) של עצי החלטה בודדים, שיטת Random Forest מאמנת מאות עצים שונים במקביל באמצעות דגימת שורות ותכונות אקראית (Bagging), וממזגת את תחזיותיהם בהצבעת רוב. המחיר: איבוד היתרון ההסברתי של מודל "קופסה לבנה".
מזמרת הגיזום ופרמטר ה-$\alpha$ (The Alpha Pruner)
שליטה אינטראקטיבית בסליידר Cost-Complexity $\alpha$, אנימציית גיזום ענפים בזמן אמת, החלקת גבולות החלטה ועקומת ה-Bias-Variance.
אבחון מורכבויות, גרפי החלטה ומקרי בוחן מעמיקים
ניתוח מתמטי ותרגול מעשי מלא: עץ החלטה מול גרף החלטה (BDD) בפונקציית XOR, שאלת העדפת קפה ($IG=0.014$), שאלת פעילות ספורטיבית והוכחת $IG=0$, חידת המתמחה המתחזה, ובניית עץ החלטה שלם לסרטים עם שבירת שוויונות.
להבין את האינטואיציה שמאחורי הקלעים: הגיאומטריה של גבולות ההחלטה ומלכודת ה-Parity
מבחינה גיאומטרית במרחב התכונות ה-Continuous/Discrete, עץ החלטה חותך את המרחב באמצעות היפר-מישורים המקבילים לצירים (Axis-Aligned Orthogonal Splits). משמעות הדבר: כל עלה מייצג היפר-מלבן במרחב.
מגבלה מבנית זו מביאה לקושי מהותי בשני תרחישים קלאסיים:
1. גבול החלטה אלכסוני ($X_1 + X_2 > c$): עץ החלטה נאלץ לקרב את הקו האלכסוני באמצעות "גרם מדרגות" מסועף ועמוק של עשרות פיצולים אורתוגונליים.
2. פונקציית הזוגיות (Parity / XOR Function): אם $Y = X_1 \oplus X_2 \oplus \dots \oplus X_n$, כל תכונה בודדת מציגה בדיוק חצי חיוביים וחצי שליליים בכל ענף, ולכן רווח המידע של כל תכונה בודדת הוא 0 עגול ($IG=0$)! אלגוריתם חמדן עיוור לחלוטין לקשרים כאלה ואינו מסוגל להתקדם ללא הרחבת מרחב התכונות או מעבר למודלים עמוקים.
💡 אינטואיציה בגובה העיניים: מתגי התאורה בחדר המדרגות
חשבו על מערכת תאורה בחדר מדרגות עם 3 מתגים שונים (בכניסה, בקומה הראשונה ובקומה השנייה). האור דולק אם ורק אם מספר המתגים המורמים הוא אי-זוגי (פונקציית XOR תלת-ממדית).
אם תבחנו מתג אחד בלבד במנותק ("האם מתג 1 למעלה?"), תגלו שבדיוק ב-50% מהמקרים האור דולק וב-50% הוא כבוי. ידיעת מצבו של מתג בודד אינה מקדמת אתכם אפילו במילימטר לקראת פתרון הבעיה! רק כאשר בוחנים את כל 3 המתגים יחד כצירוף שלם, התמונה מתבהרת. זוהי בדיוק "נקודת התורפה" של עצי החלטה חמדניים, שבוחנים כל תכונה בנפרד ומחמיצים תלויות הדדיות מורכבות.
📊 תרשים 11.5: חלוקת מרחב התכונות להיפר-מלבנים צמודי-צירים (Axis-Aligned)
מדוע פיצולים אורתוגונליים מתקשים בהפרדה אלכסונית ומהי מלכודת פונקציית הזוגיות (Parity)
פונקציית XOR / זוגיות: עץ החלטה מול גרף החלטה (BDD)
Parity Function, Subtree Duplication, and Directed Acyclic Graphs (DAG)
פונקציית הזוגיות (Parity / XOR) של $n$ משתנים מחזירה $1$ אם ורק אם מספר המשתנים המקבלים $1$ הוא אי-זוגי. תכונה זו מהווה מקרה קצה מפורסם בלמידת מכונה:
מכיוון ששינוי של כל ביט בודד הופך לחלוטין את התוצאה, שום תכונה אינה מספקת רווח מידע מקומי ($IG=0$). העץ נאלץ לחקור את כל הקומבינציות ולהפוך לעץ בינארי שלם בעל $2^n$ עלי קצה.
בגרף החלטה (DAG), צומת יכול להחזיק יותר מאב קדמון אחד (Multiple Parents). מסלולים שונים מתמזגים לאותם צמתים, תוך שיתוף תתי-עצים שקילים (Subtree Sharing).
שאלת העדפת קפה ברשת בתי קפה ($IG = 0.014$)
10 Training Examples, Entropy of Target, and Negligible Gain Feature
נתונות 10 דוגמאות של לקוחות (כמות מים, כמות קפה, ממתיק) וסיווג האם אוהב (כן/לא). מתוכן 6 דוגמאות חיוביות ("כן") ו-4 שליליות ("לא").
עבור קפה = רגיל (6 דוגמאות: 4 חיוביות, 2 שליליות) ← $H(4/6, 2/6) \approx 0.918$.
עבור קפה = כפול (4 דוגמאות: 2 חיוביות, 2 שליליות) ← $H(2/4, 2/4) = 1.0$.
מסקנה: רווח מידע זעום של 0.014 ביטים מעיד כי תכונת כמות הקפה כמעט שאינה תורמת להפרדה. היא לא תיבחר לצומת מפתח בעץ ותהיה מועמדת מובילה להסרה בגיזום.
התאמת פעילות ספורטיבית והוכחה ש-$IG$ עשוי להיות אפס
Pilates vs. Running, Attribute Contest, and Theoretical Proof
נתונות 8 דוגמאות של בחירת פעילות (5 פילאטיס, 3 ריצה) לפי תכונות "אנרגיה" (עייף, ערני) ו"זמן" (בוקר, צהריים, ערב). האנטרופיה ההתחלתית: $H(S) = -(5/8)\log_2(5/8) - (3/8)\log_2(3/8) = \mathbf{0.9544 \text{ bits}}$.
IG(Energy) = 0.9544 - 0.6068 = 0.3476
IG(Time) = 0.9544 - 0.5000 = 0.4544
כן, בהחלט. אם תכונה בינארית $A$ מפצלת את הנתונים לשני חצאים שווים שבהם יחס החיוביות והשליליות זהה בדיוק ליחס המקורי (למשל 50%-50% בכל צד), האנטרופיה המותנית היא: $$H(C|A) = 0.5 \times 1 + 0.5 \times 1 = 1.0 = H(C) \implies IG(A) = 1.0 - 1.0 = \mathbf{0}$$
חידת המתמחים והמתחזה בקרדיולוגיה (The Imposter Intern)
Feature Inversion Invariance and Mathematical Proof of Tree Equivalence
קרדיולוג נעזר ב-20 מתמחים לאבחון מחלת לב ("כן"/"לא"/"לא יודע"). אחד מהם הוא מתחזה חסר השכלה (עובד תחזוקה) שעונה תמיד הפוך בדיוק ממתמחה אמיתי ספציפי (ומעתיק "לא יודע" כפי שהוא). כל מתמחה אמיתי צודק בלפחות 60% מהמקרים.
המתמחה האמיתי והמתחזה מייצגים בדיוק את אותו הפיצול של מרחב הדוגמאות לקבוצות שוות, רק תחת תוויות הפוכות. לפיכך: $IG(\text{Intern}) = IG(\text{Imposter})$. אם נסיר את המתחזה, האלגוריתם ישתמש במתמחה האמיתי באותם מקומות. המבנה הטופולוגי, איכות הסיווג ודיוק העלים יישארו זהים לחלוטין!
בניית עץ החלטה מלא: בחירת סרט לצפייה
9 Examples, Tie-Breaking Rules, and Handling Attribute Exhaustion
הסוכן רוצה להחליט האם לצפות בסרט על בסיס 3 תכונות בוליאניות: קומדיה (Comedy), ליצנים (Clowns), אקדחים (Guns) מתוך 9 דוגמאות אימון (4 חיוביות ו-5 שליליות).
חישוב השארית מגלה כי לתכונות אקדחים וליצנים יש בדיוק את אותה שארית אנטרופיה: $$remainder(\text{Guns}) = \frac{4}{9} B(3/4) + \frac{5}{9} B(2/5) = remainder(\text{Clowns}) < remainder(\text{Comedy})$$ לפי חוק שבירת השוויונות ("העדיפו אקדחים על ליצנים"), אקדחים (Guns) נבחרת לשורש העץ!
סיווג מבוסס דוגמאות (IBL), השכן הקרוב ביותר (1-NN) ואלגוריתם IB3 המלא
למידה עצלה (Lazy Learning), פונקציית מרחק משולבת, מסנן למידה ומבחני מובהקות סטטיסטית
בניגוד לעצי החלטה המבצעים למידה קדחתנית (Eager Learning) — שבה בונים מראש מודל הכללה גלובלי ויקר על פני כל הדוגמאות — פרדיגמת סיווג מבוסס דוגמאות (Instance-Based Learning - IBL) שייכת למשפחת הלמידה העצלה (Lazy Learning): המערכת שומרת את דוגמאות האימון, ודוחה את כל מאמץ ההכללה והחישוב עד לרגע שבו מגיעה שאילתת סיווג חדשה.
- לתכונות מספריות רציפות: הפרש ערכים פשוט: $h(a_i(x), a_i(y)) = a_i(x) - a_i(y)$ (לרוב מנורמל לתחום $[0,1]$).
- לתכונות קטגוריות / בדידות: מרחק בינארי: $$h(a_i(x), a_i(y)) = \begin{cases} 0 & a_i(x) = a_i(y) \quad (\text{ערכים זהים}) \\ 1 & a_i(x) \neq a_i(y) \quad (\text{ערכים שונים}) \end{cases}$$
החיסרון הגדול של 1-NN קלאסי הוא בזבוז זיכרון עצום (שומר את כל הדוגמאות לעד) ורגישות קיצונית לרעש (דוגמה רועשת בודדת תטה את הסיווג בסביבתה). אלגוריתם IB3 פותר בעיות אלו באמצעות מנגנון סינון ומבחני מובהקות:
הדיוק שלה גבוה באופן מובהק מתדירות הסיווג במאגר. הדוגמה משתתפת באופן פעיל בסיווג דוגמאות חדשות כנציגה אמינה ומדויקת.
הדיוק שלה נמוך באופן מובהק. הדוגמה מסומנת כדוגמה רועשת או מטעה, ונמחקת לחלוטין ממאגר הנתונים (Pruning)!
דוגמה חדשה שטרם צברה מובהקות. אינה משתתפת בסיווג, אך אם היא קרובה לדוגמה חדשה יותר מהקבילים, מעדכנים את מונה ההצלחה שלה עד להכרעה.
- חיסכון דרמטי בזיכרון: המאגר מכיל רק שבריר קטן מסך הדוגמאות (במקום לשמור את כל מיליוני הדוגמאות).
- עמידות גבוהה לרעש: דוגמאות רועשות או שגויות נמחקות מהר מאוד מהמאגר עקב דיוק סטטיסטי ירוד.
- ביצועים עדיפים: בבדיקות אמפיריות אלגוריתם IB3 מציג דיוק סיווג גבוה יותר מ-NN קלאסי תוך שימוש בפחות משאבי מחשוב.
מחשבון הפיצולים ובונה העצים האינטראקטיבי (The Split Calculator Game)
חקירת 4 תרחישי מפתח: שאלת הקפה ($IG=0.014$), שאלת הספורט, שבירת שוויונות בסרטים, והשוואת עץ מלא מול BDD בפונקציית XOR.
סיכום מאסטר, צ'יט-שיט נוסחאות ומלכודות קריטיות
דף נוסחאות מרוכז בניגודיות מוגברת, מטריצת השוואה מלאה בין אלגוריתמי עצי החלטה (ID3, C4.5, CART, Random Forest), 10 מלכודות מבחן שכיחות, מילון מונחים מקצועי וגשר פדגוגי לחזית ה-AI.
להבין את האינטואיציה שמאחורי הקלעים: מהפכת האנסמבלים (Ensemble Methods) ומדוע שלם עולה על סך חלקיו
מדוע בעולם מדעי הנתונים המודרני כמעט אף אחד לא משתמש בעץ החלטה בודד? התשובה נעוצה בפירוק השגיאה להטיה ושונות (Bias-Variance Tradeoff): עץ החלטה מלא סובל מהטיה נמוכה (Low Bias) אך משונות גבוהה ביותר (High Variance) – שינוי של דוגמה אחת במדגם האימון עלול להפוך לחלוטין את מבנה העץ כולו.
הפתרון הגאוני הוא אנסמבלים מבוססי יערות אקראיים (Random Forests) ו-Bagging: במקום לבטוח בעץ יחיד, אנו מאמנים מאות עצים שונים על דגימות Bootstrap עם תת-מרחב תכונות אקראי ($m \approx \sqrt{p}$), ומבצעים הצבעת רוב. תורת ההסתברות (משפט הגבול המרכזי) מוכיחה כי ממוצע התחזיות של מודלים בלתי תלויים מצמצם את השונות בפקטור של $\frac{1}{M}$, ומייצר מודל יציב, מדויק וחסין להפליא לרעש.
💡 אינטואיציה בגובה העיניים: מועצת מומחים רפואית ותא הטייס המשולש
כשחולה עומד בפני ניתוח מוח מורכב, הוא לעולם לא יסתמך על חוות דעת של רופא בודד – מבריק ככל שיהיה, הרופא עלול להיות עייף, מוטה או לטעות. במקום זאת, בית החולים מכנס קונסיליום: פאנל של 20 מנתחים בכירים מתחומים שונים, שכל אחד מהם בוחן את הבדיקות מזווית ייחודית ומצביע על ההליך הרצוי.
גם במטוסי נוסעים מודרניים פועלים שלושה מחשבי טיסה נפרדים במקביל (Triple Redundancy), והמטוס מציית להצבעת הרוב ביניהם. זהו בדיוק העיקרון של Random Forest: חוכמת ההמונים הממוחשבת הופכת עשרות "מומחים חלשים" ולא יציבים למערכת קבלת החלטות חסינה ובלתי מנוצחת.
📊 תרשים 11.6: מפת האקוסיסטם הכוללת של למידה מונחית ועצי החלטה
השתלשלות האלגוריתמים: מ-ID3 ו-C4.5 הקלאסיים, דרך CART, ועד שיטות אנסמבל מתקדמות ויערות אקראיים
צ'יט-שיט נוסחאות ליבה: למידה מונחית ועצי החלטה
Essential Mathematical Equations for Rapid Recall & Exam Calculations
עבור $n$ תכונות בוליאניות, יש $2^n$ צירופי קלט ו-$2^{2^n}$ פונקציות אפשריות. למידה מחייבת הטיה אינדוקטיבית!
מדד לחוסר הסדר. במקרה קצה: $0 \log_2(0) \equiv 0$. מקסימלי בהתפלגות אחידה ($\log_2 k$) ומינימלי במצב טהור (0).
פרבולה סימטרית על פני $q \in [0,1]$. מגיעה לשיא $B(0.5) = 1.0$ ביט, ומתאפסת ב-$B(0) = B(1) = 0$.
ממוצע משוקלל של האנטרופיה שנותרת בכל תת-קבוצה לאחר הפיצול לפי ערכי התכונה $A$.
הרווח הנקי בצמצום אי-הוודאות. תמיד אי-שלילי: $IG(A) \ge 0$. בוחרים תכונה הממקסמת ערך זה!
מעניש תכונות בעלות ערכים ייחודיים מרובים (כמו ת"ז) המנפחות את $IG$ באופן שקרי.
מדד אי-טוהר חלופי לאנטרופיה שאינו דורש חישוב לוגריתמי יקר. בסיווג בינארי: $\text{Gini} \in [0, 0.5]$.
$R(T)$ שגיאת העץ, $|\tilde{T}|$ מספר העלים. $\alpha$ קובע את הקנס: $\alpha=0$ נותן עץ מלא, $\alpha \to \infty$ משאיר שורש בלבד.
בכל צומת בוחרים תת-מרחב אקראי של $m$ תכונות בלבד מתוך $p$. מונע מתכונה דומיננטית להשתלט על כל העצים ומקטין שונות.
מטריצת השוואה מקיפה: אלגוריתמי עצי החלטה ואנסמבל
Structural Comparison Across Modern Decision Tree Paradigms
| קריטריון | ID3 (Quinlan 1986) | C4.5 (Quinlan 1993) | CART (Breiman 1984) | Random Forest (2001) |
|---|---|---|---|---|
| מדד פיצול (Split Criterion) | Information Gain ($IG$) | Gain Ratio ($\text{GR}$) | Gini Impurity | Gini על $\sqrt{p}$ תכונות |
| סוגי תכונות נתמכות | בדידות וקטגוריות בלבד | בדידות + רציפות (דיסקרטיזציה) | בדידות + רציפות | כל הסוגים (עוצמתי לנתוני טבלה) |
| מבנה העץ (Branching) | מרובה ענפים (ענף לכל ערך) | מרובה ענפים (בדיד) / בינארי (רציף) | בינארי בלבד (Strictly Binary) | יער של מאות עצים בינאריים |
| אסטרטגיית גיזום (Pruning) | ללא גיזום מובנה (Overfits) | Pessimistic Error Pruning | Cost-Complexity ($R_\alpha(T)$) | ללא גיזום (מבוטל ע"י מיצוע) |
| טיפול בנתונים חסרים | אינו תומך (קריסה) | משקולות הסתברותיות לענפים | משתנים חלופיים (Surrogate Splits) | זקיפת נתונים מבוססת קרבה (Proximity) |
| יכולת הסבר (Explainability) | גבוהה מאוד (חוקי IF-THEN) | גבוהה מאוד | גבוהה מאוד | קופסה אפורה / חשיבות תכונות |
10 מלכודות מבחן קריטיות בלמידה מונחית ועצי החלטה
Common Academic Pitfalls & Edge Cases to Master for Exams
תכונה בעלת ערכים ייחודיים רבים (כמו מספר ת"ז או שם לקוח) תפצל כל דוגמה לעלה טהור בודד, ותשיג $\text{Remainder}=0$ ו-$IG$ מקסימלי שקרי! המודל לא לומד שום חוקיות. הפתרון: שימוש ב-Gain Ratio המעניש $\text{SplitInfo}$ גבוה.
בפונקציית זוגיות, לכל תכונה בודדת יש $IG=0$ בדיוק. אלגוריתם חמדן ייבחר תכונה אקראית וייצר עץ ענק בגודל $2^n$. אין משמעות לכך ש-$IG=0$ – ייתכן ששילוב של 2 תכונות יחד פותר את הבעיה במושלם!
עצירת גידול העץ אם $IG < \epsilon$ מפספסת תכונות סינרגטיות. זו הסיבה שגיזום בדיעבד (Post-Pruning) תמיד עדיף: הוא בונה את העץ במלואו ורק אז גוזם מהעלים כלפי מעלה לפי ביצועי Validation.
באלגוריתם Reduced Error Pruning, אם נבדוק את השגיאה על קבוצת האימון – אף ענף לעולם לא ייגזם, כי העץ הלא גזום כבר משיג עליה 100%! חובה להשתמש ב-Validation Set נפרד לחלוטין.
אם קבוצת הדוגמאות ריקה (תנאי 2) – העלה מקבל את רוב האב (Parent Mode). אם נותרו דוגמאות אך אזלו התכונות (תנאי 3) – העלה מקבל את הרוב המקומי מבין הדוגמאות הנוכחיות (Current Mode)! ערבוב ביניהם זו טעות נפוצה בבחינה.
עבור סיווג בינארי ($k=2$), האנטרופיה חסומה ב-$H(Y) \le 1$. אך עבור $k > 2$ מחלקות, האנטרופיה יכולה להגיע עד $\log_2(k)$! לדוגמה, בהתפלגות אחידה של 4 מחלקות: $H(Y) = \log_2(4) = 2.0$ ביטים.
בפיצול תכונה רציפה ($x \le c$), אין צורך לבדוק את כל הערכים האפשריים! ממיינים את הערכים, ובוחנים ספים $c = (x_i + x_{i+1})/2$ אך ורק בנקודות שבהן תגית המחלקה מתחלפת.
עץ החלטה בודד הוא בעל הטיה נמוכה ושונות גבוהה. יער אקראי מקטין את השונות ע"י מיצוע עצים רבים, אך הוא מקריב את ה-White-box Interpretability – כבר אי אפשר להציג את ההחלטה ככלל לוגי פשוט.
עצי החלטה קלאסיים מפצלים אך ורק במקביל לצירי התכונות ($x_1 \le c$). אם גבול ההפרדה האמיתי הוא אלכסוני ($x_1 + x_2 \ge 1$), העץ ייאלץ לבנות קירוב "מדרגות" עמוק ומסורבל מאוד.
בפונקציה $R_\alpha(T) = R(T) + \alpha|\tilde{T}|$: כאשר $\alpha = 0$, נקבל את העץ המלא ללא גיזום. כאשר $\alpha \to \infty$, הקנס על עלים אינסופי ונקבל עץ בעל עלה יחיד (שורש בלבד עם רוב גלובלי).
מילון מונחים מקצועי: מושגי יסוד
Key Academic Terminology for Supervised Learning & Trees
גשר פדגוגי: מעצי החלטה אל אנסמבל ובינה מלאכותית מודרנית
בפרק זה השלמנו את המסע מתוך הלמידה האינדוקטיבית הבסיסית אל עצי ההחלטה המפורשים (White-box models). הבנו את עוצמתה של תורת האינפורמציה של שאנון, את האלגוריתמיקה החמדנית של DTL/ID3, ואת מדע הגיזום שמציל מודלים מהתאמת-יתר.
אך עולם ה-Machine Learning אינו עוצר כאן: ההבנה של אי-יציבות העץ הבודד הובילה ישירות להמצאת היערות האקראיים (Random Forests) ושיטות ה-Gradient Boosting (XGBoost) השולטות כיום בכל תחרות מדעי נתונים טבלאיים בעולם. במקביל, רעיונות הפיצול הרציף והמזעור הדיפרנציאבילי סללו את הדרך לרשתות נוירונים עמוקות (Deep Learning) – היכן שחוקי ההיסק מתחלפים במשקולות רציפות וגרדיאנטים.