בבניה

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

מצגת

בינה מלאכותית

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

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

יוריסטיקות

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

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

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

METAREASONING

אם ההחלטה הבסיסית היא לאיזה כיוון ללכת בחיפוש, אזי החלטת־meta היא באילו חישובים לנקוט כדי להחליט באיזה כיוון ללכת. rational metareasoning עוסק בשיטות מסודרות של קבלת החלטות-meta כאלה. לעתים קרובות בmetareasoning משתמשים במושג ״ערך מידע״.מה זה ״ערך מידע״ של הפעלת יוריסטיקה? יוריסטיקה משפיעה על בחירת כיוון חיפוש, ותוחלת השיפור בתוצאת האלגוריתם הנובע מהמידע שהיוריסטיקה מספקת הוא ״ערך מידע״. למשל, לו היינו מסתובבים באקראיות, היינו אוספים 8 שקלים בממוצע, אבל אם נחשב את היוריסטיקה, עשוים להגיע ל13 שקלים: אזי ערך המידע של היוריסטיקה הוא 5 שקלים.

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

בעית בחירה

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

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

בנדיט מרובה ידיים

במדעי המחשב מקובל לנתח בעיות, ככל שהן מורכבות, בעזרת מודלים מפושטים אך תופסים את המאפיינים החשובים ביותר. אחד המודלים המוצלחים עבור בעיית הבחירה הוא ״בנדיט מרובה ידיים״ (multi-armed bandit ־ MAB). כמו בקזינו, יש לנו מכונה, שאם מושכים את הידית שלה, היא פולטת כסף, לפעמים יותר, לפעמים פחות, לפעמים בכלל לא. למכונות אלו נהגו לתת צורה של בן־אדם עם מראה אכזרי, מכאן השם. לבנדיט שלנו יש שיפור ־־ יותר מזרוע (ידית) אחת, וזרועות שונות מביאות כמות כסף שונה (אבל איננו יודעים מהו טיב של כל זרוע).

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

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

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

חיפוש מונטה־קרלו בעצים

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

UCT

איך לפזר דגימות כדי למקסם את הסיכוי להצליח? כל קודקוד בעץ החיפוש הוא מופע של בנדיט מרובה־ידיים: יש לבחור באחת מן הצלעות היוצאות על סמך תוצאות הדגימות. רעיון טבעי הוא להפעיל אלגוריתם לבנדיטים בכל קודקוד במסלול לעלה. רעיון זה יושם באלגוריתם UCT, ולUCT הייתה הצלחה רבה בכמה תחומים: ראשית כל, במשחק Go. אולם, UCT מבוסס על ניחוש ולאו על חישוב ערך מידע של הדגימות. metareasoning נותן שיפור משמעותי: אלגוריתם דומה לUCT אבל מבוסס על קירוב (גס!) של ערך מידע מנצח בGo את UCT ב65% מהמשחקים.

הוקרה בין־לאומית

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

1. David Tolpin, Solomon Eyal Shimony: Rational Deployment of CSP Heuristics. IJCAI 2011: 680-686
2. David Tolpin, Solomon Eyal Shimony. Semimyopic measurement selection for optimization under uncertainty. IEEE Transactions on Systems, Man, and Cybernetics, Part B, Part B, 42(2):565–579, 2012
3. David Tolpin, Solomon Eyal Shimony. MCTS Based on Simple Regret. AAAI-2012. To appear.
4. David Tolpin, Solomon Eyal Shimony. VOI-aware MCTS. ECAI-2012. To appear.
5. Nicholas Hay, Stuart Russell, Solomon Eyal Shimony, David Tolpin. Selecting Computations: Theory and Applications. UAI-2012. To appear.

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

אתגרים לעתיד

הסק־על במחקר

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

הארנק לא תמיד נאבד מתחת לפנס

עד עכשיו אנחנו ניסינו (והצלחנו) להפעיל rational metareasoning בבעיות ״נוחות לשיטה״, שבהן למדידה יש מחיר קבוע וכל הרווח מתקבל מהבחירה הסופית. מן הסתם ניתן לגשת גם לסוג בעיות עם רווח מצטבר ־ בבעיות אלה אנחנו מרוויחים לא רק מהפעולה האחרונה, אלא גם מכל הפעולות. [דוגמה יפה לרווח מצטבר היא התנהגות רציונלית במבחן, כשצריך להחליט מתי לעבור משאלה לשאלה אפילו אם לא פתרנו עד הסוף.] אולם המודל דורש שינוי, וכנראה יהיה גם מורכב יותר.