אלגוריתם AdaBoost
 | |
| איור המדגים את עקרון הפעולה של האלגוריתם. בכל שלב, מסווג חלש מאומן על הנתונים, כאשר הדוגמאות שסווגו שגוי מקבלות משקל גבוה יותר באיטרציה הבאה. המסווגים החלשים מתמקדים בדוגמאות הקשות יותר בכל שלב. לבסוף, המסווגים החלשים משולבים למסווג חזק על ידי שקלול מבוסס ביצועים. | |
| סוג | אלגוריתם סיווג |
|---|---|
| סיבוכיות זמן | O(T) |
| סיבוכיות מקום | O(T⋅M) |
| ממציא | יואב פרוינד ורוברט שפיר |
| נקרא על שם | Adaptive Boosting |
AdaBoost (קיצור של Adaptive Boosting – "בוסטינג אדפטיבי") הוא מטא-אלגוריתם בתחום לימוד מכונה המיועד לשיפור דיוק הסיווג על ידי שילוב של מסווגים חלשים למסווג חזק. אלגוריתם זה פותח בשנת 1995 על ידי הישראלי יואב פרוינד ורוברט שפיר, אשר עבור עבודתם זו זכו בפרס גדל בשנת 2003.[1]
AdaBoost עובד בשילוב עם מגוון אלגוריתמי למידה בסיסיים, ומפיק מסווג סופי באמצעות סכימה משוקללת של תוצאות "מסווגים חלשים" מרובים. לרוב הוא מוצג עבור בעיות סיווג בינאריות, אך הוא הורחב גם לטיפול בריבוי קטגוריות ולמשימות אחרות.[2][3] השם "בוסטינג אדפטיבי" נובע מיכולתו של האלגוריתם להתאים את עצמו לשגיאות: כל מסווג חלש נוסף מתמקד במקרים שבהם המסווגים הקודמים טעו. במקרים מסוימים, AdaBoost נמצא כפחות רגיש לבעיית התאמת יתר (overfitting) בהשוואה לאלגוריתמי למידה אחרים, אך הוא עלול להיות רגיש לנוכחות רעש וחריגות בנתונים.
למרות שבדרך כלל נעשה שימוש ב-AdaBoost לשילוב של לומדי בסיס חלשים (כגון גזעי החלטה), הוכח כי הוא משלב ביעילות גם לומדים בסיס חזקים (כגון עצי החלטה עמוקים יותר), ומייצר מודל מדויק עוד יותר.[4]
מבוא והיסטוריה
הרעיון של Boosting (הגברה) בלמידת מכונה צמח מתוך שאלה תאורטית במסגרת מודל הלמידה PAC שהציג לסלי וליאנט ב-1988.
רוברט שפיר הציע ב-1989 אלגוריתם Boosting פולינומי ראשון שהוכיח עקרונית כי התשובה חיובית, וב-1990 הציג יואב פרוינד שיפור יעיל יותר לאלגוריתם זה. עם זאת, הגישות המוקדמות הללו סבלו מקשיים פרקטיים, והיו מורכבות ליישום ולאימון.[5]
בשנת 1995 פיתחו פרוינד ושפיר את AdaBoost (קיצור של "Adaptive Boosting"), אלגוריתם Boosting פשוט יחסית שהצליח להתגבר על רבות מהבעיות המעשיות של קודמיו. האלגוריתם הוצג לראשונה בכנס COLT באותה שנה, ומאוחר יותר פורסם במאמר מקיף ב-1997.[5]
AdaBoost היה לאחד האלגוריתמים הראשונים בתחום ה-Ensemble learning שזכה לתשומת לב רחבה בשל פשטותו, יעילותו ותוצאותיו הטובות.[5] תרומתם של פרוינד ושפיר זכתה כאמור להכרה בדמות פרס גדל בשנת 2003 על הישגיהם בתחום Boosting, ומהר מאוד שולב האלגוריתם במגוון רחב של יישומים בלמידת מכונה.[1]
יתרונות וחסרונות
יתרונות
- פשטות ושקיפות – האלגוריתם קל למימוש ומבוסס על רעיון ישיר של שיפור איטרטיבי של הביצועים. הוא אינו דורש כוונון רב של פרמטרים (מלבד מספר הסבבים) וניתן להשתמש בו עם מגוון סוגי מסווגים חלשים לפי צורכי הבעיה.[6] התוצר – אוסף מסווגים עם משקלות – גם ניתן לפרשנות מסוימת; למשל, ניתן להבין אילו מאפיינים (דרך המסווגים החלשים) תרמו יותר להחלטה הסופית.
- שיפור דיוק – האלגוריתם לרוב משיג דיוק גבוה יותר מאשר כל מסווג חלש בנפרד, ולעיתים אף משתווה לביצועי מסווגים מתקדמים בהרבה. בשילוב עם עצי החלטה קטנים האלגוריתם ידוע כאחד המסווגים הטובים ביותר ללא צורך בהתאמה מרובה. הוא מתאים את עצמו לדאטה על ידי התמקדות בדוגמאות קשות, ובכך מצמצם את הטעות הכוללת באופן יעיל.
- התאמה אדפטיבית וחסינות מסוימת – היכולת להתרכז בדוגמאות שקשה לסווגן בכל שלב מקנה ל-AdaBoost יתרון בהתמודדות עם מקרים מורכבים ועם בעיות של חוסר איזון בנתונים.[6] דוגמאות מהמיעוט שתויגו לא נכון יקבלו משקל גבוה ויזכו להתייחסות בסבבים הבאים, וכך האלגוריתם יכול באופן אדפטיבי להתמודד גם עם מערכי נתונים לא מאוזנים שבהם אחת הקטגוריות נדירה.
- עמידות מסוימת להתאמת יתר (Overfitting) – במחקרים אמפיריים נמצא של-AdaBoost נטייה מופחתת להתאמת יתר בהשוואה לאלגוריתמים חזקים אחרים, במיוחד במצבים של נתונים נקיים מרעש. במילים אחרות, כל עוד לא קיימות שגיאות תווית רבות או חריגות קיצוניות, AdaBoost מסוגל ללמוד את הנתונים באופן הדוק מבלי להתאים את עצמו יתר על המידה.
חסרונות
- רגישות לרעש וחריגות – אחת המגבלות הבולטות של AdaBoost היא הרגישות שלו לדוגמאות בעייתיות בנתוני האימון. מכיוון שהאלגוריתם מגדיל בהדרגה את המשקל של דוגמאות שקשה לסווגן, דוגמאות עם תווית שגויה או נתונים חריגים (Outliers) עלולות לקבל משקל הולך וגדל ולהשפיע לרעה על המודל הסופי.[7] במצב של רעש כבד, AdaBoost עלול "להתאמץ" יותר מדי להתאים את עצמו לחריגים ובכך לפגוע בביצועי ההכללה. אלגוריתמים חלופיים כמו Random Forest נחשבים חסינים יותר לרעש בהקשר זה.[8]
- צורך בלומד חלש "טוב מספיק" – AdaBoost דורש שכל מסווג חלש יהיה מעט טוב מניחוש (שגיאה נמוכה מ-50%). במקרים שבהם הלומד החלש לא מסוגל להגיע לביצועים כאלה, האלגוריתם עלול להיכשל או לא לתרום לשיפור (למשל, אם לומד חלש מחזיר ביצועים גרועים, המשקל שלו עלול לצאת שלילי או שהאלגוריתם יעצור). לכן AdaBoost מתאים בעיקר ללומדים חלשים בעלי יכולת אבחנה מינימלית. במצבים של מידע דל מאוד או מאפיינים שלא נושאים אות שימושי, ייתכן ש-Boosting לא יביא לתועלת.[6]
- חישוביות וזמן ריצה – בניגוד לשיטות כמו Bagging (דוגמת יער אקראי) שבהן מודלים שונים ניתנים לאימון במקביל, ב-AdaBoost האימון הוא סדרתי (סבבים תלויים זה בזה). משמעות הדבר היא שמשך האימון עשוי להיות ארוך, במיוחד אם נדרשים סבבים רבים או אם הלומד החלש עצמו איטי. עבור מערכי נתונים גדולים מאוד, AdaBoost עלול להיות כבד חישובית לעומת שיטות קביצה (ensemble) מקבילות אחרות. בנוסף, עם התקדמות האלגוריתם והוספת מסווגים, גם זמן הסיווג (בעת שימוש במודל) מתארך, שכן יש לבצע חיזוי של כל המסווגים החלשים ולשלבם.[6]
יישומים בעולם האמיתי
האלגוריתם AdaBoost הוא שיטה גמישה ורב-שימושית הנמצאת במגוון יישומים בתחומי עיבוד נתונים, ראייה ממוחשבת, אבטחת מידע ועוד. להלן מספר תחומים בולטים בהם נעשה בו שימוש:[9]
זיהוי פנים ועיבוד תמונה
אחד היישומים הידועים ביותר של שיטת הבוסטינג הוא במסגרת מערכת זיהוי הפנים של Viola-Jones. אלגוריתם זה, שפותח בשנת 2001, השתמש בטכניקת למידה מגבירה כדי לבחור מאפייני תמונה פשוטים (כגון Haar features) ולשלבם לרצף של מסווגים חזקים המאורגנים במבנה מדורג (cascade), מה שאפשר זיהוי מהיר של פנים בתמונות. המנגנון שימש הן לבחירת התכונות המבדילות ביותר והן להרכבתן למסווג סופי יעיל, ובכך איפשר זיהוי פנים בזמן אמת – פריצת דרך בתחום הראייה הממוחשבת. מעבר לזיהוי פנים, טכניקות מבוססות הגברת מסווגים יושמו גם בזיהוי עצמים כללי, מעקב אחר אובייקטים בווידאו ושיפור איכות תמונה.
עיבוד שפה טבעית וסינון ספאם
בתחום עיבוד שפה הטבעית משלבים לעיתים Boosting במשימות סיווג טקסט. דוגמה נפוצה היא מסנני דואר זבל, שבהם האלגוריתם מאומן על מאפייני טקסט כגון מילות מפתח, תדירויות ושדות מטא-דאטה של ההודעה כדי להבחין בין דואר לגיטימי לספאם. שילוב של רבים מהמאפיינים הללו באמצעות שיטת ההגברה משפר את יכולת הזיהוי של ספאם בהשוואה לכל כלל בודד. גם במשימות כמו ניתוח סנטימנט (קביעת עמדה חיובית/שלילית מטקסט) נעשה שימוש באלגוריתם ככלי המשלב מאות חלוקות פשוטות (למשל נוכחות מילים מסוימות) לכדי מסווג סופי חזק. היכולת של שיטת ההגברה האדפטיבית להתאים את עצמה לדוגמאות קשות לסיווג (כגון ביטויים אירוניים או נדירים) מועילה במיוחד בתחומים אלו.
גילוי הונאות ואנומליות
בתחום אבטחת המידע והפיננסים האלגוריתם מיושם במערכות זיהוי הונאות וזיהוי אנומליות. למשל, בזיהוי הונאות בכרטיסי אשראי פותחו מערכות המשלבות מספר מסווגים חלשים (הבוחנים דפוסי רכישה, מיקום, סכומים וכדומה) כדי לאתר עסקאות חשודות. שיטת ההעצמה מתאימה במיוחד למשימה זו, משום שהיא יכולה להגביר את הרגישות למקרים חריגים (כגון עסקאות הונאה נדירות) תוך שמירה על שיעור התרעות שווא נמוך. באופן דומה, גם בזיהוי פריצות לרשת או תנועה זדונית (Intrusion Detection) נעשה שימוש באלגוריתמים מבוססי למידת חיזוק, בהם המערכת לומדת דפוסי תעבורה תקינים ברשת ומזהה סטיות מהם המעידות על פעילות זדונית. שילוב של גלאים חלשים שונים (כגון בדיקת כתובות IP, חריגות בפרוטוקול ורצפי פקודות חשודים) באמצעות שיטת הבוסטינג מאפשר לקבל מנגנון איתור רב-שכבתי בעל דיוק גבוה.
רפואה וביואינפורמטיקה
גם בתחום הרפואי נעשה שימוש נרחב באלגוריתם למשל במערכות אבחון רפואי מבוססות למידת מכונה. במחקרים שונים יושמה הטכניקה לשילוב מספר בדיקות או סימפטומים פשוטים (כל אחד בעל כוח ניבוי חלש) לכדי החלטה אינטגרטיבית לגבי נוכחות מחלה או סיכון רפואי. לדוגמה, בניתוח צילומי רנטגן או MRI לזיהוי נגעים, שיטת הלמידה מסוגלת לשלב מאפייני תמונה רבים כדי לזהות ממצאים חריגים בצורה מדויקת יותר. דוגמה נוספת היא חיזוי התפרצות מחלות באמצעות שילוב של מדדים קליניים, תוצאות מעבדה וסימנים חיוניים – כל אחד מהם בפני עצמו אינו מספיק, אך שילובם באמצעות מודל ההעצמה מספק חיזוי אמין. בנוסף, תחום הביואינפורמטיקה (כגון סיווג גנים או חיזוי מבנה חלבונים) אימץ גם הוא אלגוריתמים מבוססי בוסטינג, כאשר ישנם אינספור מאפיינים ביולוגיים חלשים שיש לשקלל יחדיו.
השוואה עם אלגוריתמים אחרים
Boosting מול Bagging (יער אקראי)
AdaBoost שייך למשפחת אלגוריתמי ה-Boosting, שבהם המסווגים הבסיסיים מאומנים באופן סדרתי (טורי) תוך שימוש בתוצאות קודמיהם. זאת בניגוד למשפחת ה-Bagging (כגון יער אקראי)[10], שבה מודלים מרובים מאומנים במקביל על דגימות אקראיות של הנתונים. בשתי הגישות משלבים מספר מודלים חלשים לכדי מודל חזק[8], אך האופן שבו הדבר מתבצע שונה: AdaBoost משנה באופן אדפטיבי את משקלי הדוגמאות כדי להתמקד במקרים קשים בכל סבב, בעוד שביער אקראי כל עץ מקבל משקל שווה, והעצים שונים זה מזה בשל דגימת נתונים ומאפיינים שונה בכל עץ.[8][10]
יער אקראי מסתמך על הפחתת שונות (variance) על ידי ממוצע של מודלים לא תלויים יחסית, בעוד Boosting מכוון להפחתת הטיה (bias) באופן סדרתי – כל מודל מתקן את קודמו.[10] כתוצאה מכך, AdaBoost נוטה להתאים את עצמו חזק לנתוני האימון ועלול להיות רגיש יותר לרעש, בעוד שיער אקראי עקב אופיו הממוצע יותר חסין לרעש ולחריגות. מצד שני, AdaBoost לעיתים קרובות מגיע לדיוק גבוה יותר על האימון ויכול להתמקד גם במקרים חריגים, בעוד שיער אקראי עשוי "לדלל" את השפעתם של מקרים נדירים.[8]
עוד הבדל פרקטי הוא שיער אקראי יכול לנצל עיבוד מקבילי (מאחר שכל עץ נבנה באופן עצמאי) ובדרך כלל דורש פחות כוונון של היפר-פרמטרים, בעוד AdaBoost הוא תהליך טורי שקשה יותר להאיץ בחומרה מקבילית. בסופו של דבר, שתי השיטות פופולריות ומשלימות זו את זו: יערות אקראיים טובים ביציבות ובמניעת הישררות יתר (overfitting), ואילו Boosting (לרבות AdaBoost) מצטיין בהגעה לביצועי שיא כאשר הנתונים נקיים מרעש או לאחר טיוב זהיר.[8][10]
AdaBoost מול אלגוריתמי Boosting מודרניים
AdaBoost היה אחת הגרסאות הראשונות והבסיסיות של Boosting. אחריו פותחו וריאנטים ושיפורים רבים. חיזוק גרדיאנט היא מסגרת כללית שבה boosting מוגדר כבעיה של אופטימיזציה נומרית: במקום לעדכן משקלי דגימות באופן אקספוננציאלי כל מודל חדש מותאם לטעויות (residuals) שהמודל המשולב הנוכחי עדיין עושה, תוך שימוש במתודולוגיית Gradient descent על פונקציית עלות כללית.
יתרון הגישה הזו הוא שניתן לבחור פונקציית loss שונה (למשל לוגיסטית, ריבועית וכו'), מה שנותן גמישות רבה – למשל, חיזוק גרדיאנט מיושם לא רק לסיווג בינארי אלא גם לרגרסיה, לסיווג רב-מחלקות ועוד. הוא מאפשר שימוש בלומדים חלשים מעט יותר מורכבים (כמו עצים בעלי עומק של 4–8 רמות במקום "עצים טיפשים" בני רמה אחת הנפוצים ב-AdaBoost), והוא כולל מנגנונים להפחתת הישררות יתר כמו רגולריזציה (חיזוק מדורג, קיצוץ ערכי עלים, ועוד).
השוואה לשיטות למידה אחרות
AdaBoost משתייך לשיטות האנסמבל, ולכן שונה בגישתו ממסווגים "בודדים" כמו עצי החלטה עמוקים, מכונת וקטורים תומכים (SVM) או רשתות עצביות. בהשוואה לעץ החלטה גדול, AdaBoost לרוב יבנה מספר רב של עצים קטנים (או מסווגים פשוטים אחרים), ולכן עשוי ללכוד דפוסים באופן שונה – לעיתים מדויק יותר עבור פרטים אך אולי פחות "גלובלי" מאשר עץ עמוק אחד.[8]
בהשוואה לרשת עצבית, AdaBoost אינו דורש הגדרת שכבות והיפר-פרמטרים רבים, אך רשתות יכולות לנצל טוב יותר כמויות נתונים גדולות במיוחד וללמוד ייצוגים מורכבים, בעוד AdaBoost מסתמך על מאפיינים קיימים ולומד רק משקלים על גביהם.[8][11]
אחד היתרונות של AdaBoost על פני מודלים כמו SVM הוא בפשטות העדכון – אין צורך בפתרון בעיה קמורה גלובלית מורכבת, אלא רק בחישובים סגורים בכל סבב – וכן בכך שקל לשלב אותו עם אלגוריתמים קיימים (למשל, לקחת סיווגים חלשים קיימים ולשפרם דרך Boosting). מצד שני, בבעיות עם מרחב מאפיינים עצום או רציף מאוד, מודלים כמו SVM עם גרעין או רשתות עמוקות עשויים לתפוס מבנים לא-ליניאריים באופן יעיל יותר מאשר צירוף של רבים מאוד של חלוקים ליניאריים.[8]
הערות שוליים
- ^ 1.0 1.1 Gödel Prize - 2003, https://eatcs.org/
- ↑ Freund, Yoav; Schapire, Robert E. (1995), A desicion-theoretic generalization of on-line learning and an application to boosting, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 23–37, doi:10.1007/3-540-59119-2_166, ISBN 978-3-540-59119-1, נבדק ב-2022-06-24
- ↑ Hastie, Trevor; Rosset, Saharon; Zhu, Ji; Zou, Hui (2009). "Multi-class AdaBoost". Statistics and Its Interface. 2 (3): 349–360. doi:10.4310/sii.2009.v2.n3.a8. ISSN 1938-7989.
- ↑ Wyner, Abraham J.; Olson, Matthew; Bleich, Justin; Mease, David (2017). "Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers". Journal of Machine Learning Research. 18 (48): 1–33. נבדק ב-17 במרץ 2022.
{{cite journal}}: (עזרה) - ^ 5.0 5.1 5.2 Yoav Freund Robert E. Schapire, A Short Introduction to Boosting
- ^ 6.0 6.1 6.2 6.3 Mohit Uniyal, AdaBoost Algorithm in Machine Learning, Applied AI Blog, 2024-10-11 (באנגלית אמריקאית)
- ↑ Is there any formal explanation for the sensitivity of AdaBoost to outliers?, Data Science Stack Exchange (באנגלית)
- ^ 8.0 8.1 8.2 8.3 8.4 8.5 8.6 8.7 Changjun Lee, CJL & Lab - Understanding the AdaBoost, changjunlee.com, 2023-03-29 (באנגלית)
- ↑ Mohit Uniyal, AdaBoost Algorithm in Machine Learning, Applied AI Blog, 2024-10-11 (באנגלית אמריקאית)
- ^ 10.0 10.1 10.2 10.3 Differences between Random Forest and AdaBoost, GeeksforGeeks, 2022-05-15 (באנגלית אמריקאית)
- ↑ Vihar Kurama, A Guide to AdaBoost: Boosting To Save The Day, www.digitalocean.com, October 21, 2024 (באנגלית)
אלגוריתם AdaBoost40655803Q2823869