XGBoost

XGBoost היא ספריית תוכנה קוד פתוח המספקת מסגרת נירמול (regularizing) וחיזוק גרדיאנט לשפות: C ++, Java,Python, ג'וליה, Perl, וסקאלה. XGBoost עובדת על לינוקס, Windows, ו- macOS. מתוך תיאור הפרויקט, היא שואפת לספק "ספרייה להגברת הדרגתיות ניתנת להרחבה, ניידת ומבוזרת (GBM, GBRT, GBDT). XGBoost פועל על מכונה בודדת, כמו גם על מסגרות עיבוד מבוזרות Apache Hadoop, Apache Spark, Apache Flink ו- Dask.

הספרייה זכתה לפופולריות רבה ותשומת לב בתור האלגוריתם המועדף עבור צוותים מנצחים רבים של תחרויות למידת מכונה.

היסטוריה

XGBoost התחילה כפרויקט מחקר של טיאנקי צ'ן כחלק מקבוצת ה-Distributed (Deep) Machine Learning Community (או DMLC). בתחילה, כיישום מסוף שניתן להגדיר באמצעות קובץ תצורה של libsvm. הוא התפרסם בחוגי התחרות ב-ML לאחר השימוש בו בפתרון המנצח של אתגר למידת המכונה של Higgs. זמן קצר לאחר מכן, חבילות Python ו-R נבנו, ול-XGBoost יש כעת הטמעת חבילות עבור Java, Scala, Julia, Perl ושפות אחרות. זה הביא את הספרייה למפתחים נוספים ותרם לפופולריות שלה בקרב קהילת Kaggle, שם היא שימשה למספר רב של תחרויות.

עד מהרה הוא שולב עם מספר חבילות אחרות מה שהופך אותו קל יותר לשימוש בקהילות שלהם. כעת הוא שולב עם scikit-learn עבור משתמשי Python ועם חבילת caret עבור משתמשי R. ניתן לשלב אותו גם במסגרות Data Flow כמו Apache Spark, Apache Hadoop ו- Apache Flink באמצעות ה-Rabit המופשט ו-XGBoost4J. ספריית XGBoost זמינה גם ב- OpenCL עבור FPGAs. יישום יעיל וניתן להרחבה של XGBoost פורסם על ידי Tianqi Chen ו-Carlos Guestrin.

מאפיינים

תכונות בולטות של XGBoost שמבדילות אותו מאלגוריתמים אחרים של Gradient boosting כוללות:

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

אלגוריתם

בשונה מאלגוריתם מסוג חיזוק גרדיאנט (gradient boosting) שפועל כדעיכת גרדיאנט, ‏XGBoost עובד כ"ניוטון-רפסון" במרחב הפונקציונלי. שערוך טיילור מסדר שני משמש בתור פונקציית ההפסד כדי לקשר למתודת ניוטון-רפסון.

אלגוריתם גנרי של XGBoost, עם נתוני קלט: $\{(x_{i},y_{i})\}_{i=1}^{N}$, פונקציית הפסד: $L(y,F(x))$, מספר "לומדים חלשים": $M$, וקצב למידה: $\alpha$.

1. מודל ראשוני עם ערך 0:

   ${\hat {f}}_{(0)}(x)={\underset {\theta }{\arg \min }}\sum _{i=1}^{N}L(y_{i},\theta ).$

2. עבור m = 1 עד M:
   1. חישוב הגרדיאנטים וההסיאנים:

      ${\hat {g}}_{m}(x_{i})=\left[{\frac {\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}}\right]_{f(x)={\hat {f}}_{(m-1)}(x)}.$

      ${\hat {h}}_{m}(x_{i})=\left[{\frac {\partial ^{2}L(y_{i},f(x_{i}))}{\partial f(x_{i})^{2}}}\right]_{f(x)={\hat {f}}_{(m-1)}(x)}.$

   2. התאמת לומד בסיסי (או לומד חלש, כמו עץ) בעזרת נתוני האימון $\displaystyle \{x_{i},-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}\}_{i=1}^{N}$ על ידי פתירת בעיית האופטימיזציה שלהלן:

      ${\hat {\phi }}_{m}={\underset {\phi \in \mathbf {\Phi } }{\arg \min }}\sum _{i=1}^{N}{\frac {1}{2}}{\hat {h}}_{m}(x_{i})\left[-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}-\phi (x_{i})\right]^{2}.$

      ${\hat {f}}_{m}(x)=\alpha {\hat {\phi }}_{m}(x).$

   3. עדכון המודל:

      ${\hat {f}}_{(m)}(x)={\hat {f}}_{(m-1)}(x)+{\hat {f}}_{m}(x).$

3. פלט ${\hat {f}}(x)={\hat {f}}_{(M)}(x)=\sum _{m=0}^{M}{\hat {f}}_{m}(x).$

פרסים

• פרס ג'ון צ'יימברס (2016)
• פרס פיזיקת אנרגיה גבוהה פוגשת למידה חישובית (HEP meets ML) (2016)

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34617561XGBoost