Anytime learning of anycost Classifiers

מסגרת כל-זמן עבור מיון באמצעות עץ-החלטות היכול בצע החלטות מדויקות בתוך מסגרת תקציבית הדוקה של הוצאות על בדיקות. 

סיכום עיקרי המאמר

1 הקדמה 

כמה דוגמאות לקביעת קריטריון מיון בלמידת מכונה במסגרת עלות מוגדרת: 

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

דורשים את היכולת לחזות את הבאות. 

הצעה לייעול:

Anytime algorithm: יותר משאבים משפרים את איכות התפוקה. מכאן, שבאופן דומה, ניתן לייצר:

 anycost classifier: ממיין שעלויות טעויות החישוב שלו פוחתות כאשר הקצאת המשאבים לבדיקות עולה. 

כיצד לייצר “ממיין כל-מחיר”? 

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

ניתן להמיר את עצי החלטה בקלות ל”ממיין כל-מחיר”. כמה דוגמאות אחרונות ללומדי עץ החלטה שמטרתם למזער את העלות הכוללת במהלך המיון—עלות הבדיקות והטעויות בחישוב:

ICET, DTMA, ו-ACT (האלגוריתם של כותבי המאמר).

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

דוגמא לממיינים היודעים להחליט אילו בדיקות לבחור: בתגובה למקרה מפורט חלקית, “ממיין אקטיבי” יודע לפרוט איזו בדיקה יש לבצע הלאה (Greiner et al. 2002). עם זאת, האתגר הוא, שמיון מסוג זה יכול לפעול רק כאשר הממיין מוגבל למספר קבוע של בדיקות המוגדר לפני הלמידה. 

התמודדות עם האתגר:  TATA (Tree-classification AT Anycost) – מסגרת חדשה עבור למידה ומיון עם משאבים מוגבלים. TATA הוא אלגוריתם כל-זמן שיכול לעשות שימוש בזמן למידה נוסף על מנת לייצר ממייני כל-מחיר היכולים לנצל משאבים נוספים בזמן המיון. TATA יכול לקחת את התקציב כפרמטר, או להמשיך במיון עד הפרעה. הערכות ניסיוניות רבות מראות כי TATA מבצע טוב יותר מאלטרנטיבות קיימות ומציג התנהגות כל-זמן וכל-מחיר טובה. 

2 למידה ומיון במשאבים מוגבלים 

למידה ביישומים מערבת כמה סוגים של עלויות. בשלב הלמידה עלויות קשורות לרכישת ערכי-מאפיינים.

עלויות למידה:

קודם כל איסוף מידע, לאחר מכן מודל למידה. המשאבים הדרושים הם זיכרון וזמן חישוב.

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

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

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

עלויות מיון: 

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

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

למידת כל-זמן, מיון כל-מחיר: 

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

למידת contract ומיון pre-contract.   (CLPC)

למידת  contract, מיון contract. (CLCC)

למידה מופרעת (interruptible), מיון pre-contract . (ILPC)

למידה מופרעת, מיון contract. (ILCC)

למידת contract , מיון מופרע (CLIC)

למידת מופרעת, מיון מופרע (ILIC) 

המסגרת החדשה שהמאמר יציג, הנקראת TATA, יכולה לתפקד תחת כל אחד מהתרחישים הנ”ל. 

3 מסגרת ה- TATA 

על מנת לפעול תחת כל התרחישים הנ”ל,  מסגרת ה TATA אמורה לאפשר חיבור עם כל אלגוריתם כל-זמן. 

עצי מיון:pre-contract  

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

על מנת לשפר את עצי כל-מחיר הוצגו האלגוריתמים הבאים: LSID 3  היכול להחליף מהירות חישוב עבור עצים קטנים ומדויקים יותר, ו-ACT היכול לנצל זמן למידה עודף על מנת לייצר עצים יעילים יותר מבחינת עלות. למרות זאת, אף אחד מהשניים לא יכול לייצר עצים המתפקדים תחת תקציבי מיון, ולכן לא רלוונטיים כאן. 

למידת כל-זמן של עצי pre-contract:

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

אלגוריתם TATA pre-contract: 

המטרה של האלגוריתם TATA שונה מזו של אלגוריתם כמו הACT. מטרת הTATA היא מזעור עלויות הטעיות בחישוב בהינתן מגבלות על עלויות הבדיקה. 

בעוד ש ACT  מאמץ את גישת TDIDT, TATA מאמץ את גישת TDIDT$–מה שמבטיח 1) שעץ שהמיון לא יסטה מהעלות המקסימלית, ו 2)  את הסינון של כמה מהתכונות תוך כדי שמירה על זמן ההערכה, שיכול להיות יקר. גם TATA  וגם ACT דוגמים את מרחבי התת-עצים תחת כל צומת על מנת להעריך את התועלת שלהם. אולם ב TATA נרצה להטות את הדגימה לעבר עצים מדויקים המתאימים לתקציב עלויות הבדיקה שלנו. ב-ACT ישנה העדפה לעצים שסך כל עלותם היא הנמוכה ביותר. ב TATA כל העצים הנדגמים מתאימים לתקציב שהוגדר. 

למידה ניתנת-להפרעה (interruptible) של ממייני pre-contract: 

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

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

גישה זו הביאה לשיפור האיטרציה (iteration) יכולה לחול גם על  המרה של pre-contract-TATA  לאלגוריתם ניתן להפרעה. התועלת השולית של בניית העץ לוקחת בחשבון גם את צפי עלות הטעויות בחישוב וגם את צפי המשאבים הדרושים לתהליך הבנייה. התוצר הממיין מתוכנן לפעול תחת תקציב העלות הנתון מראש. 

ממיינים לומדי-contract: 

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

רפרטואר של עצים: 

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

הצעת המחברים היא לבנות רפרטואר באמצעות ה pre-contract-TATA של אוסף עצים κ, כאשר כל אחד עם ערך מגבלה שונה. ההבדל בין ממיין רפרטואר לבין אנסמבלים המשלבים תחזיות ממספר עצים, הוא שההחלטה הסופית של הרפרטואר נשענת על עץ אחד בלבד. 

למידת רפרטואר עם מרווחי עלויות לא-אחידים: 

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

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

למידת ממיינים ניתנים להפרעה: 

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

יצירת רפרטוארים עבור מיון ניתן-להפרעה: 

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

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

קביעת גודל רפרטוארים ניתנים-להפרעה: 

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

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

הנחות לבדיקות חוזרות: 

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

סיכום מרכיבי ה TATA: 

המחברים הציגו שלושה מרכיבים שונים של TATA עבור שלושה תרחישי מיון שונים. Pre-contract-TATA מאפשר את פעולת עצי החלטה לומדים היכולים לפעול תחת תקציב מיון קבוע מראש. Contract-TATA מאפשר בניית רפרטואר של עצי pre-contract, כל אחד מהם עם תקציב מיון שונה. בעת מיון מקרה חדש, הממיין בוחר את העץ המתאים ביותר למשאבים הזמינים ומשתמש בו עבור מיון. בדומה ל contract-TATA, interruptible-TATA בונה רפרטואר של עצי pre-contract. אולם בעת מיון הוא חוקר את העצים ברפרטואר לפי הסדר (מתחיל בעלות הנמוכה ביותר). כאשר מופרע, הוא מחזיר את ההחלטה שנעשתה על ידי העץ האחרון שנחקר באופן מלא. בעוד ששני המקרים עושים שימוש ב pre-contract-TATA  על מנת לבנות רפרטוארים, התחשבותם בגודל הרפרטואר ובתקציבי העצים משתנה בהתאם להבדל באופן בו נעשה שימוש בממיינים. עבור כל אחד משלושת המרכיבים, המחברים הציגו לומד contract כל-זמן, ואת הצעדים שיש לנקוט בעת הפרעתו. 

4 הערכה ניסיונית 

המחברים ערכו מספר ניסויים לבדוק את הביצוע וההתנהגות של TATA  בשלושה סט-אפים שונים: pre-contract, contract, interruptible. המחברים יישמו את השיטה האוטומטית שלהם שהוצגה בעבר, שיטה להקצאת עלויות בדיקה אצל תכונות של datasets קיימים. 

מיון pre-contract:

המחברים ערכו השוואה בין pre-contract-TATA לממיינים pre-contract  אחרים. לאחר מכן נבדקה התנהגות הכול-זמן של TATA. 

סט הניסויים הראשון השווה בין

 C4.5, EG2, EG2$, TATA (r = 0) = C4.5$, and TATA (r = 5). 

אחד ההבדלים החשובים בין TATA  ל ACT, ICET ו-DTMC הוא שהאחרונים דורשים שגורם ההחלפה (tradeoff) בין עלות טעויות החישוב ועלות הבדיקה יהיה ידוע מראש. 

לפי תוצאות הניסוי, TATA (r = 5) הוא בעל הביצועים הטובים ביותר.  

השוואה בין TATA (r = 5)  ל- TATA (r = 0) מראה בבירור שהראשון יותר טוב. הוא דוגם את תתי-העצים האפשריים של כל מועמד ומבסס את ההחלטה שלו על איכות העצים הנדגמים. יתרון זה בה עם מחיר: משתמש בהרבה יותר משאבי למידה. 

TATA גם מייצר עצי כל-מחיר טובים, וגם מתפקד כאלגוריתם שיכול להחליף משאבי למידה עבור ייצור של עצים יותר טובים. 

הניסוי השני של המחברים בוחן התנהגות כל-זמן של TATA  על ידי בחינת ערכי r שונים. התוצאות הראו שכל גרסאות הTATA  טובות יותר מה C4.5. ככל שערך ה- r  עולה, כך גם היתרון של TATA עולה. 

מיון contract: 

בסט-אפים של contract  ו- interruptible, TATA  פועל בעזרת רפרטואר. בשבי לבחון את התנהגות כל-מחיר של TATA בסטאפ contract המחברים בנו 3 רפרטוארים בגודל 16. הראשון הוגדר בr = 0  לייצר את העצים, השני והשלישי ב r = 3. 

מיון הדוגמאות נעשה באמצעות הרפרטוארים. הביצוע הדומיננטי הוא בבירור של TATA (r = 3). 

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

מיון interruptible:

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

נבנו שלושה רפרטוארים: 

רפרטואר של 3 TATA (r = 0)

רפרטואר של 3 TATA (r = 3)

רפרטואר של 16 TATA (r = 3)

לפי התוצאות, הביצוע הטוב ביותר הגיע מ .TATA (r = 3) במקרים מסוימים, עדיף היה ליצור רפרטוארים קטנים יותר בעוד שעבור מקרים אחרים רפרטוארים גדולים יותר הניבו תוצאות יותר טובות. 

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

5 מחקרים קשורים

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

Yang et al. (2007): תכננו מעריכי הסתברות ממוצעת כל-זמן (AAPE), על מנת לנצל משאבי חישוב נוספים במהלך מיון. 

Ueno et al (2006): הראו כיצד להמיר מייני שכן קרוב (nearest neighbor) לממייני כל-זמן. 

מחקרים נוספים שבחנו עלויות בדיקה וטעויות חישוב: Nunez 1991, Norton 1989, Tan and Schlimmer 1989, Breiman et al 1984, Pazzani et al 1994 ועוד רבים אחרים. אולם שיטות אלו לא מתחשבות בעלויות הבדיקה ולכן מתאימות בעיקר עבור אזורים בהם עלויות בדיקה לא מהוות מגבלה. 

בנוסף, נעשו מאמצים בקרבת זמן פרסום המאמר לפתח לומדי-עץ שלוקחים בחשבון גם עלויות בדיקה וגם עלויות טעויות בחישוב. יתר על כן, עשה ניסיון לפתח לומדי-עץ היודעים לחפש אחר העץ שימזער את סכום עלויות הבדיקה וטעויות החישוב—כמו DTMC, ICET. (Ling et al 2004, Sheng et al 2006, Turney 1995). עם זאת שיטות אלו לא תוכננו על מנת לייצר עצי כל-מחיר שיכולים לנצל תקציבי מיון. 

Greiner et al ו Farhangfar et al (2008) ביצעו ניתוח היבטים תיאורטיים של ממיינים לומדים רגישים לעלות.    

Lizotte et al (2007) בחנו את בעיית למידת התקציב, הכוללת את השגת ערכי התכונות של כל דוגמא בה נעשה שימוש באימון האלגוריתם. בנוסף, Kuhn et al (2007) הציגו אלגוריתמים היכולים לפעול בסטאפ למידת-תקציב. 

Kapoor and Greiner (2005) הציגו מסגרת למידה מתוקצבת הפועלת תחת תקציב הדוק לרכישת ערך מאפיינים במהלך למידה, וכמו כן מייצרת ממיין עם תקציב מיון מוגבל. 

Biglic and Getoor (2007) התמודדו עם הבעיה של בחירת מאפיין תת-סט המערב עלויות. לפי המחברים המטרה שלהם היא למזער את סכום עלות רכישת המידע ועלות הטעויות בחישוב. 

Nijssen and Fromont (2007) הציגו אלגוריתם מדויק (DL8) למציאת עץ-החלטה שיודע להשתמש בדירוג הפונקציה תחת גודל, עומק, דיוק ומגבלות-עלה. 

6 סיכום

לפי המחברים, אנו רואים כיצד טכניקות למידת מכונה הופכות להיות יותר ויותר פופולאריות ביאפליקציות שונות, הכוללות הגבלות בתקציב המיון. יישומים אלו כוללים גילוי כשלי חומרה, דיאגנוזה רפואית, זיהוי ספאם, תנועת רשת ועוד. במאמר שלהם, המחברים הציגו שלושה תרחישים אפשריים למיון כל-מחיר. Pre-contract, בו העלות המרבית ידועה מראש ללומד; contract, בו עלות זו ידועה לאחר בניית המודל אבל לפני התחלת פעולת המיון; ו- interruptible, בו מגבלת העלות לא ידועה הן ללומד והן לממיין. התרומה של מאמר זה היא הTATA, שתוכנן לפעול בסביבות אלו. 

Key words: decision trees, cost sensitive learning, resource bounded reasoning, anytime algorithms.