העוגה והדובדבן – ללמוד לפעול באמצעות חיזוי העתיד

השבוע חברת DeepMind (מבית גוגל) סגרה מעגל אחרי שהשחקן הממוחשב אלפא-גו הביס את אלוף העולם בגו 3-0. המשחק העתיק גו הוא האוורסט של המשחקים, משחק מורכב ביותר ששחקנים אנושיים שמשחקים בו מסבירים את מהלכיהם כנובעים מ"אינטואיציה" ולא מאנליזה מדוייקת. שיטות קודמות של AI (למשל זו שניצחה את קספרוב בשחמט) לא היו מורכבות מספיק בשביל לנצח בני אדם בגו. נדרשה לשם כך רשת ניורונים, "אינטואיציה" מלאכותית אם תרצו. אחרי הניצחון השבוע דיפ מיינד הודיעו שהם מוציאים את אלפא גו לגמלאות – המשימה הושלמה.  זהו, אין יותר מה לעשות איתו.

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

go_lee_sedol

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

אלפא-גו אומן לעשות דבר אחד, והוא – לנצח בגו. הבעייה שהמתכנתים של אלפא-גו התמודדו איתה היא הבעייה המרכזית בתחום שנקרא  Reinforcement Learning (או RL).  בכל שלב במשחק, כשמגיע תורו של אלפא-גו, הוא צריך לבצע הכרעה בין מספר סופי של אפשרויות (בעיקר איפה לשים את האבן שלו על הלוח).  הצרה היא שאחרי שאלפא-גו שם את האבן שלו במקום כלשהו על הלוח, למתכנתים אין מושג אם זו היתה החלטה טובה.  בשביל לדעת אם זו היתה החלטה טובה הם צריכים לחכות עד לסוף המשחק ואז הם מקבלים בסך הכל ביט אחד של אינפורמציה – 1 אם אלפא-גו ניצח, ו-0 אם הפסיד.  הביט הזה, כשהוא 1, אומר לאלפא-גו 'קבל ח"ח', אבל לא מפרט אלו מההחלטות שאלפא-גו קיבל במהלך הדרך היו החלטות חשובות שתרמו לניצחונו.

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

זו מציאות הרבה יותר מאתגרת מהמציאות שבדרך-כלל אנחנו מתמקדים בה בבינה מלאכותית, שנקראת Supervised Learning (או SL). בסיווג תמונה, למשל, כשאנחנו מבקשים מהמחשב להסתכל על תמונה ולומר מה יש בה (למשל הסיכוי שמופיע בה כלב והסיכוי שמופיע בה חתול), המחשב פולט את תשובתו (נגיד 90% חתול ו-10% כלב) ומיד אנחנו יודעים כמה קרוב הוא היה לתשובה הנכונה (100% חתול). במקרה של רשת ניורונים, זו בדיוק הנקודה שבה אנחנו מחשבים את הנגזרת על הפרמטרים של המודל ומעדכנים אותם כך שבפעם הבאה המחשב ייתן תשובה עוד יותר מדוייקת (אולי 94% חתול ו-6% כלב).  

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

כדי לפצות על דלילות האינפורמציה הזו, אנחנו נאלצים ללקט אותה באמצעות הרבה משחקים, ולכן אין פלא שכמעט כל העבודות שנעשות היום על Reinforecment Learning עושות זאת בתחום משחקי המחשב. זוכרים את כל משחקי האטארי ששיחקנו פעם? הם זוכים לעדנה מחודשת כחומר גלם לאימון אלגוריתמים.  DeepMind בנו תשתית שמאפשרת למחשב לשחק בהם בקצב מואץ של מליוני פעמים ביום(!), ובצורה כזו הם מאמנים אותו עד שהוא מגיע לרמה על-אנושית (במקרה של גו אלפא-גו שיחק נגד עצמו). חברת OpenAI אף הגדילה לעשות והקימה "חדר כושר" הפתוח לכלל ציבור השחקנים הממוחשבים.

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

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

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

עשינו פה בעצם טריק שבו השתמשנו בדאטה שלנו (המידע החושי שמגיע כל רגע) להיות ה"אמת" של עצמו. כל רגע הוא מטרת החיזוי של הרגע הקודם. אנחנו גם לא צריכים לעבוד עכשיו קשה ולתייג מיליוני תמונות. עברנו מסביבה של Supervised Learning לסביבה עשירה באינפורמציה של Predictive Learning (או Unsupervised Learning).  ככה המוח מצליח לקבל מספיק אינפורמציה כדי לבנות מודל כללי של "איך העולם עובד".  עם המודל הכללי הזה אנחנו מסוגלים לאפיין הרבה בעיות קטנות וממוקדות יותר ולגשת אליהן כשכעת אנחנו זקוקים להרבה פחות אינפורמציה נוספת (כמו ב-SL ו-RL) כדי להתמקצע בהן, משום שאת ה-heavy lifting כבר עשינו במידול הכללי של העולם.

לכן אלגוריתם הלמידה האולטימטיבי הוא אלגוריתם שיצליח להשתמש בכל רבדי האינפורמציה השונים.  יאן לקון (Yann Lecun), אחד מהאבות המייסדים של רשתות הניורונים של היום, ממשיל את תהליך הלימוד בבינה מלאכותית לעוגת קצפת. העוגה עצמה היא ה-Predictive Learning, שבה האלגוריתם מתכוונן על סמך מיליוני ביטים לכל דוגמית קלט. מעליה יש את הקצפת, ה-Supervised Learning, שבה בני אדם מוסיפים עוד כמה עשרות ביטים של "אינפורמציה חיצונית" לכל דוגמית, ומעל יש את הדובדבן שבקצפת, הוא ה-Reinforcement Learning, שבו ביטים בודדים שניתנים מדי פעם כ"חיזוק חיובי" הם כל מה שמכוון את האלגוריתם. "אנחנו יודעים להכין את הקצפת ואת הדובדבן", אומר לקון, "אבל עדיין לא יודעים איך להכין את העוגה".

נסיון לחזות את הפריימים הבאים.

מודל שחוזה פריימים עתידיים (משמאל, החל מפריים 11). עדיין בחיתוליו. מקור: הונגלאק לי

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

דום

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

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

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

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

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

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

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

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

ביצועים של שלושה שחקנים ממוחשבים במגוון מטרות

ביצועים של שלושה שחקנים ממוחשבים במגוון מטרות. המספריים שבסוגריים מייצגים את משקלות המדדים (הריגות, בריאות, תחמושת). השחקן בטור (a) אומן באמצעות מטרה קבועה (1, 0.5, 0.5). השחקנים ב-(b) ו-(c) אומנו עם מטרות אקראיות מתחלפות (ב-b משקלות חיוביים בלבד וב-c איפשרו גם שליליים). ירוק: ביצועי המנצח בתחרות ה"פציפיסטית". צהוב: ביצועי שחקן (b) על מטרה (1, 0.5, 0.5) טובים כמו אלו של (a) שהתאמן רק עליה. מקור: קולטון ודוסוביצקי, המירקורים שלי.

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

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

לקריאה נוספת:

[1] Alexey Dosovitskiy and Vladlen Koltun. Learning to Act by Predicting the Future. ICLR 2017.

[2] Mnih et. al. Playing Atari with Deep Reinforcement Learning. Deep Mind, 2013.

[3] פוסט של אנדריי קארפאתי על למידת חיזוקים: Deep Reinforcement Learning: Pong from Pixels.

[4] פוסט נוסף של קארפאתי על אלפא-גו, ולמה האלגוריתם בבסיסו לא יעזור לנו לבנות רובוט AI.

[5] Ruben Villegas, Honglack Lee et. al. Learning to Generate Long-term Future via Hierarchical Prediction. ICML 2017.

גילוי נאות: אני מכיר אישית את ולאדלן קולטון (וגם את הונגלאק לי) מסטנפורד, וקולטון אף היה המנחה שלי לסימסטר אחד או שניים.

מודעות פרסומת
פוסט זה פורסם בקטגוריה deep learning, Uncategorized. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

תגובה אחת על העוגה והדובדבן – ללמוד לפעול באמצעות חיזוי העתיד

  1. נ הגיב:

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

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת /  לשנות )

תמונת גוגל

אתה מגיב באמצעות חשבון Google שלך. לצאת מהמערכת /  לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת /  לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת /  לשנות )

מתחבר ל-%s