גידול צומח של החלטות

כמו כל המודלים המפוקחים של למידת מכונה, עצי החלטות עוברים אימון כדי להסביר בצורה הטובה ביותר קבוצה של דוגמאות אימון. האימון האופטימלי של עץ החלטות הוא בעיה קשה מסוג NP. לכן, האימון מתבצע בדרך כלל באמצעות שיטות ניתוח ותכנון (heuristics) – אלגוריתם למידה קל ליצירה שמספק עץ החלטות לא אופטימלי, אבל קרוב לאופטימלי.

רוב האלגוריתמים המשמשים לאימון של עצי החלטות פועלים לפי אסטרטגיית 'חלוקה ושליטה' תאוותנית. האלגוריתם מתחיל ביצירת צומת יחיד (השורש) וממשיך ביצירת עץ ההחלטות באופן חזרה (recursive) וחמדני.

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

לדוגמה, במערך הנתונים Palmer Penguins (שמשמש לדוגמאות קוד בהמשך הקורס), רוב הפינגווינים מהמין Adelie ו-Chinstrap הם באורך מקור של יותר מ-16 מ"מ, בעוד שרוב הפינגווינים מהמין Gentoo הם באורך מקור קטן יותר. לכן, התנאי bill_length_mm ≥ 16 מניב תחזיות כמעט מושלמות לגבי פינגווינים מהמין Gentoo, אבל לא מצליח להבדיל בין פינגווינים מהמין Adelie לבין פינגווינים מהמין Chinstrap. סביר להניח שהאלגוריתם יבחר את התנאי הזה.

איור 7. השלב הראשון בגידול עץ.

 

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

האלגוריתם פועל באופן הבא:

הערה: לא תצטרכו לכתוב את האלגוריתם הזה, אלא אם אתם מטמיעים ספריית יער החלטות משלכם.

def train_decision_tree(training_examples):
  root = create_root() # Create a decision tree with a single empty root.
  grow_tree(root, training_examples) # Grow the root node.
  return root

def grow_tree(node, examples):
  condition = find_best_condition(examples) # Find the best condition.

  if condition is None:
    # No satisfying conditions were found, therefore the grow of the branch stops.
    set_leaf_prediction(node, examples)
    return

  # Create two childrens for the node.
  positive_child, negative_child = split_node(node, condition)

  # List the training examples used by each children.
  negative_examples = [example for example in examples if not condition(example)]
  positive_examples = [example for example in examples if condition(example)]

  # Continue the growth of the children.
  grow_tree(negative_child, negative_examples)
  grow_tree(positive_child, positive_examples)

נרחיב על השלבים של אימון של עץ החלטות ספציפי.

שלב 1: יוצרים עץ:

שלב 2: מגדילים את הצומת מס' 1. התנאי 'x1 ≥ 1' נמצא. נוצרים שני צומתי צאצא:

שלב 3: מגדילים את הצומת מס' 2. לא נמצאו תנאים שעומדים בדרישות. לכן, הופכים את הצומת לעלעל:

שלב 4: מגדילים את הצומת מס' 3. התנאי "x2 ≥ 0.5" נמצא. נוצרים שני צמתים צאצאים.

יש שיטות אחרות להרחבת עצי החלטות. חלופה פופולרית היא לבצע אופטימיזציה של הצמתים ברמת המערכת הגלובלית במקום להשתמש באסטרטגיית 'פיצול ושליטה'.

קוד YDF

ב-YDF, עצי ההחלטות גדלים באמצעות האלגוריתם 'חלוקה ושליטה' שמתואר למעלה כברירת מחדל. לחלופין, אפשר להפעיל את האפשרות 'צמיחה גלובלית' באמצעות הפרמטר growing_strategy="BEST_FIRST_GLOBAL". פרטים נוספים זמינים במסמכי התיעוד.

בהתאם למספר ולסוג של מאפייני הקלט, מספר התנאים האפשריים בצומת נתון יכול להיות עצום, ובדרך כלל אינסופי. לדוגמה, בהינתן תנאי סף של $\mathrm{feature}_i \geq t$, השילוב של כל ערכי הסף האפשריים עבור $t \in \mathbb{R}$ הוא אינסופי.

התהליך שאחראי למציאת התנאי הטוב ביותר נקרא מחלץ. מכיוון שהם צריכים לבדוק הרבה תנאים אפשריים, חלוקות הן צוואר בקבוק בתהליך האימון של עץ החלטות.

הציון שמקבל מקסימום מהמחלוק תלוי במשימה. לדוגמה:

• רווח מידע ו-Gini (שניהם מפורטים בהמשך) הם מדדים נפוצים לסיווג.
• טעות ריבועית ממוצעת משמשת לרוב לרגרסיה.

יש הרבה אלגוריתמים של מחלקים, לכל אחד מהם תמיכה משתנה בנושאים הבאים:

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

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

קוד YDF

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