אײַזיק מאיר דיק איז געװען אַ משכיל, און דערצו אײנער פון די ערשטע צו דערציען דאָס פאָלק אין ײדיש דװקא. דיקס לײענערס זײנען צום מערסטענס געװען װײַבער; פארשטײט זיך אז דער שרײַבער האָט זיך פֿאַרנומען מיט דער געזעלשאַפטליכער ראָלע און דעם גורל פון אַ װײַב.

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

עס זײַנען דאָ פאָרט עטלעכע װיכטיקע חילוקים.

סײַ ר׳ צדוקס װײַב און סײַ תרצה זײַנען קלוג און פרום און גוטע בעל־הביתטעס, נאָר ר׳ צדוקס װײַב האָט נישט קײן נאָמען און זאָגט נישט קײן װאָרט אין דער גאַנצער מעשה, בעת תרצה איז פאָרגעשטעלט געװאָרן מיט איר נאָמען, רעדט אַ סך, און בכלל זעט אױס װי אַ מענש, אַ באַזונדערע פּערזענלעכקײַט. זײ בײדע הײסן ״אשת חיל״, נאָר תרצה זיצט מיט איר מײדן אין שטוב, שפינט און װעבט, בעת ר׳ צדוקס װײַב פֿאַרנעמט זיך מיט ר׳ צדוקס געשעפֿט, אין װאָס פאַרשטײט זי ״פֿיל בעסער אַלס ער״.
װען ר׳ צדוק באַזוכט דעם רבֿ, פאָלגט אים זײַן װײַב שװײַגנדיק, און איז אַ פנים מסכים זאָל ער גײן אװעק קײן פרעמדע לענדער. תרצה פרוּװט, להװדיל, צו אָפּרעדן אליעםן, איר חתן, פֿון דער רײַזע, װײנט און זאָגט צו צו װאַרטן אויף אים ביז ״אירע גרויע האָר״.

בײדע װײַבער װאַרטן לאַנגע יאָרן אויף זײערע מענער, נאָר זײער געטרײַשאַפט איז אױך פאַרשײדענע. באװוּסט װערנדיק װעגן ר׳ צדוקס טױט, באַװײנט אים זײַן װײַב אַ גאַנץ יאָר, אָבער נאָך דעם איז זי ממשיך מיט איר לעבן: פירט די געשעפטן, האָט אַ חתונה און אַ קינד. װען ר׳ צדוקס װײַב טרעפט איר פאַרפאַלענעם מאַן אויף איר זונס ברית, צום אָנהײב דערקענט זי אים נישט אפילו. פון דעסטװעגן בלײַבט תרצה געטרײַ צו זײן טױטן חתן ביסן סוף, דערקענט אים אויף דער רגע און שטאַרבט מיט איר קאָף אױף זײַן ברוסט.

װאָס קען זײַן די סיבה פון אַזאַ שאַרפֿן חילוק? ס׳איז מעגלעך אַז אײַזיק־מאיר דיקס קוקװינקל אויף דער ראָלע פון אַ װײַב איז מיט די יאָרן געביטן געװאָרן, און תרצה איז נײנטער צו דעם אייראָפעישן ידעאל, בעת ר׳ צדוקס װײַב איז מער אלט־צײַטיק. עס קען זײַן דאָך אויך אַ טיפֿע סיבה. אײַזיק מאיר דיק האָט מסתמא געלײענט ספּורי מעשיות פון רבי נחמן דער בראַסלעװער, און אפשר האָבן זײ אויף אים א השפעה געהאַט. ס׳דאכט זיך אז תרצה איז ניט קײן װײַבס פאָרטרעט נאָר אַ משל, און דער פירוש איז, װי געװײנטלעך, די טרױעריקע געשיכטע פון ײִדישן פאָלק. אויב די דאָזיקע סברה איז ריכטיק, עס װערט גאָר גרינגער מפרש צו זײן די מעשה, איר קלאָרע ענלעכקײַט מיט שיר השירים, און דעם אומבאַפרײַטן און אומגליקלעכן פאַרשױן ־ תרצה.

אין זײַן עסיי רעדט פרץ װעגן נױטן און צרות פון ידישער ליטעראטור. עס איז נישט פשוט צו נאכפאָלגן פרצן געדאנקן, װי געװײנטלעך, סײַ צוליב זײַן באזונדערער שפראך און סטיל, סײַ צוליב דעם װאס די טעמע איז דעמאָלט געװען נײ, און א סך באגריפן האָבן נאָך נישט באקומן זײערע באשטימטע װערטער. אַנשטאָט צו פאָרלעגן חידושים, פאַרשאַרפנט פרץ די װערטער-נױט, ניצנדיק די זעלבע װערטער אין עטלעכע פאַרשײדענע באַטײטן. אײן מונסטער איז דאָס װאָרט ״ײִּדיש ״.

אַ פנים איז ײִדיש אַ שפראַך, די שפראַך פון אײראָפעישע ײדן. נאָר מיט דאָזיקן פּירוש אַלײן איז עס אומעגלעך צו פֿארשטײן א צאָל זאַצן, אײן מונסטער איז: ״נישט נאָר אױף ײִדיש, ײִדיש מוז געשאַפן װערן״. דאס ערשטע ״ײִדיש״ איז די שפראך, אָבער דאָס צװײטע איז אװדאי עפעס אַנדערש.

װעלכע באַטײַטן, אַחוץ פון ״שפראַך״, טראָגט בײַ פרצן דאָס װאָרט ״ײִדיש״? אײן ענטפער געפינט זיך בײַם סוףֿ פֿון דעם ערשטן קאַפּיטעל: ״נישט אײראָפּע פֿעלט אונדז… ײִדיש פֿעלט, עיברי פֿעלט…״ ס׳טײַטש, ײִדיש איז דאָס זעלבע, אָדער כמעט דאָס זעלבע, װי עיברי ־ דער ײִדישער חינוך, די פֿאָלקס־טראַדיציע. און אין אמת העלפֿט דער דאָזיקער באַטײַט פֿון ״ײדיש״ פֿארשטײן עטלעכע געדאַנקן, למשל, ״ײִדיש מוז זײַן דער שטאנדפּונקט, פֿון װעלכען דאָס קינסלער־פּראָבלעם װערט באַטראַכט״ ־ דאָ ״ײִדישער חינוך״ טױגט גאָר בעסער פֿון ״שפּראַך״.

עס איז דאָך קלאָר אַז עס זײַנען דאָ אױך אנדערע באַטײַטן: אַפילו דער ערשטער מונסטער קען מען נישט פאַרשטײן אױב דאָס צװײטע ״ײדיש״ איז בלױז ״חינוך״. װאָס נאָך דען? אינעם דריטן קאַַפּיטעל קומט פֿאָר ״אײגנאַרט״: אַ זאַמלונג פֿון גײַסטיקע װערטן, באַזונדערע פאַרן ײִדישן פֿאָלק. מיט ״ײִדיש״ װי ״אײגנאַרט״ אױך לײענט און פֿארשטײט מען פּרצן אַ סך בעסער.

װאָלט די װערטער־נױט געװען די אײנציקע סיבה צו באַניצן אײן װאָרט פאַר דרײַ (און אפשר מער װי דרײַ) פֿאַרשײדענע באַגריפן, פּרץ װאָלט נישט געװען אײנער פֿון די גרעסטער ײִדישע שרײַבערס און דענקערס. עס איז דאָ נאָך עפּעס צו צוגעבען צו אונזערן פּירוש. אינעם פֿינפֿטן קאַפּיטעל זעט מען דאָס װאָרט ״ײדישקײַט״, װאָס איז ״נישט קײן שטײנדיק װאַסער״, דער היפוך פֿון ״אַ פֿאָלק אָן ליטעראַטור״. דאַכט זיך אַז די אלע באַטײַטן פֿון ״ײִדיש״ צונױפֿקומנדיק װערן ײדישקײַט: און די ציל איז צו פֿאַראײניקן זײ. ײדישקײַט איז דאָס װאָס פעלט אונדזער ליטעראַטור, און זי קען געקראָגן װערן נאָר װען ײִדיש װי אַ שפראך, ײִדיש װי אַ פֿאָלקס־טראַדיציע און ײִדיש װי אַ זאַמלונגן פֿון גײַטסיקע װערטן קומען צונױף.

שני הארועים הראשונים בחיי אחרי שעליתי היו פורים ויום פתוח לתארים מתקדמים במחלקה למדעי המחשב של אוניברסיטת בן גוריון בנגב. אני במחלקה כבר יותר מארבע שנים. כמעט מהיום הראשון אני מעורב, בהנחיית פרופ’ שמעוני, במחקר של 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 בבעיות ״נוחות לשיטה״, שבהן למדידה יש מחיר קבוע וכל הרווח מתקבל מהבחירה הסופית. מן הסתם ניתן לגשת גם לסוג בעיות עם רווח מצטבר ־ בבעיות אלה אנחנו מרוויחים לא רק מהפעולה האחרונה, אלא גם מכל הפעולות. [דוגמה יפה לרווח מצטבר היא התנהגות רציונלית במבחן, כשצריך להחליט מתי לעבור משאלה לשאלה אפילו אם לא פתרנו עד הסוף.] אולם המודל דורש שינוי, וכנראה יהיה גם מורכב יותר.

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

קשה

• לשכנע בניפנוף ידיים: יכולת הניפנוף עם גבס מוגבלת
• לסחוט משחת שיניים מהשפופרת ־־־ המברשת לא מסכימה לשכב על הגב בשלווה
• להכין חביתה!!!