הרעיון: הרבה מסווגים חלשים, מסווג אחד חזק
AdaBoost, קיצור של Adaptive Boosting, הוא אלגוריתם-חיזוק (Boosting): שיטה שבונה מסווג יחיד חזק לא מאפס, אלא משרשרת של מסווגים "חלשים" — כל אחד מהם צריך רק להיות מעט טוב יותר מניחוש אקראי, לא מדויק בפני עצמו. כל מסווג חדש בשרשרת מתאמן בעדיפות על הדוגמאות שהמסווגים הקודמים טעו בהן, ובסוף התהליך כולם מצביעים יחד, כל אחד במשקל שנקבע לפי מידת-ההצלחה שלו — הצבעה משוקללת ולא רוב פשוט. המילה "אדפטיבי" בשם מתייחסת בדיוק לכך: המשקלים מתעדכנים באופן אדפטיבי בכל סבב, בהתאם לביצועי-הסבב הקודם.
שאלה תיאורטית מ-1988, ותשובה מעשית ב-1995–1997
עוד ב-1988–1989 שאלו מייקל קרנס ולסלי ואליאנט שאלה תיאורטית: האם אפשר בכלל להפוך אוסף של לומדים-חלשים ללומד חזק אחד? רוברט שפיירא ענה עליה בחיוב כבר ב-1989, באלגוריתם-חיזוק ראשון שהוכיח זאת באופן פורמלי; ב-1990 הציג יואב פרוינד גרסה יעילה יותר, "boost-by-majority". לשני האלגוריתמים המוקדמים האלה היה חיסרון מעשי משותף: הם נדרשו לדעת מראש עד כמה כל לומד-חלש טוב. AdaBoost, שפרוינד ושפיירא ניסחו יחד ב-1995 ופרסמו במלואו במאמר "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting" בכתב-העת Journal of Computer and System Sciences ב-1997, פתר את זה: המשקלים מתעדכנים אדפטיבית תוך כדי האימון עצמו, בלי צורך לדעת שום דבר מראש. פרוינד ושפיירא זכו על כלל העבודה הזו בפרס גדל ב-2003.
איך המשקלים זזים בפועל
בתחילת האימון כל דוגמאות-האימון מקבלות משקל שווה. בכל סבב מאומן מסווג-חלש חדש — לרוב "גדם-החלטה" (Decision Stump), עץ-החלטה ברמת-עומק אחת בלבד — ואז מחושב עד כמה טעה. דוגמאות שהוא טעה בהן מקבלות משקל גבוה יותר לקראת הסבב הבא, כדי שהמסווג הבא יתמקד דווקא בהן; דוגמאות שסווגו נכון מקבלות משקל נמוך יותר. תהליך זה חוזר על עצמו מספר קבוע-מראש של סבבים, וכל מסווג בשרשרת מקבל בסוף משקל-הצבעה לפי דיוקו שלו — מסווג מדויק יותר משפיע יותר על ההחלטה הסופית מאשר מסווג שרק מעט טוב מניחוש אקראי.
היישום שהפך אותו מפורסם: זיהוי-פנים בזמן-אמת
הדגמה מוקדמת ומשפיעה במיוחד הייתה מערכת-זיהוי-הפנים של פול ויולה ומייקל ג'ונס, שפורסמה ב-2001 בכנס CVPR, ומבוססת על שרשרת (Cascade) של מסווגי-AdaBoost פשוטים ומהירים, שכל אחד בודק תבנית-ניגודיות פשוטה בפני האדם. המערכת רצה מהר מספיק לזיהוי-פנים בזמן-אמת במצלמות רגילות של אותה תקופה — הישג שהפך את AdaBoost משם מוכר בעיקר בקרב חוקרים לכלי מוכר גם בתעשיית הראייה-הממוחשבת, שנים לפני שרשתות-קונבולוציה תפסו את מקומו במשימה הזו.
היסוד ההיסטורי של חיזוק גרדיאנט
AdaBoost אינו רק דוגמה מוקדמת ל"חיזוק" — הוא הבסיס ההיסטורי הישיר שממנו התפתח חיזוק-גרדיאנט (Gradient Boosting). ב-2001 פרסם ג'רום פרידמן מסגרת כללית יותר שמנסחת את רעיון-החיזוק כאופטימיזציית-גרדיאנט במרחב-הפונקציות, ומראה ש-AdaBoost הוא בעצם מקרה פרטי של המסגרת הזו עבור פונקציית-איבוד מסוימת. כך ש-AdaBoost לא רק קדם לחיזוק-גרדיאנט בזמן — ארבע שנים לפני מאמרו של פרידמן — אלא גם נכלל בתוכו מתמטית כמקרה-קצה.
AdaBoost מול יער-אקראי: שני סוגי אנסמבל
בניגוד ל"יער אקראי" (Random Forest), שבו עצי-החלטה רבים נבנים במקביל ובאופן בלתי-תלוי ומצביעים יחד, ב-AdaBoost כל מסווג נבנה ברצף ותלוי ישירות בטעויות קודמיו — בדיוק כמו בחיזוק-גרדיאנט. ההבדל בין AdaBoost לחיזוק-גרדיאנט טכני יותר: AdaBoost מעדכן משקלי-דוגמאות ישירות, בעוד חיזוק-גרדיאנט מתאמן על השארית (Residual) של השגיאה הנוכחית — שני מנגנונים שונים להשגת אותו רעיון-יסוד של תיקון-הדרגתי. כיום, ברוב היישומים המעשיים, ספריות חיזוק-גרדיאנט כמו XGBoost דוחקות את AdaBoost הצידה בזכות ביצועים וגמישות טובים יותר, אך AdaBoost עדיין נלמד כמבוא לרעיון החיזוק כולו, בזכות פשטותו היחסית.