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

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

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

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

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

זה אחד מהמקומות שבהם כתיבה פורמלית מסייעת להבין על מה מדובר. אם \( x \) מסמן אסטרטגיה כלשהי של אליס מתוך קבוצת אסטרטגיות \( X \) ו-\( y \) אסטרטגיה כלשהי של בוב מתוך קבוצת אסטרטגיות \( Y \), אז \( \pi:X\times Y\to\mathbb{R} \) היא “פונקצית הרווח” של אליס: \( \pi\left(x,y\right) \) הוא הרווח של אליס מהמשחק אם היא נוקטת ב-\( x \) ובוב נוקט ב-\( y \) (וכזכור, מספר זה מתאר גם את ההפסד של בוב. שיכול להיות גם הרווח של בוב. ואז הוא ההפסד של אליס. לא מבלבל בכלל).

ניקח לדוגמה את משחק הזוג-או-פרט שדיברתי עליו לא מזמן. במשחק הזה האסטרטגיה היא בסך הכל מספר האצבעות שמוציאים. אם נניח שמוציאים בין 0 ל-5 אצבעות, שניצחון במשחק מסומן על ידי רווח בגודל 1, ושאליס היא השחקן של “זוג”, אז \( \pi \) היא פונקציה \( \pi:\left\{ 0,1,\dots,5\right\} ^{2}\to\mathbb{R} \) שמקיימת למשל \( \pi\left(2,2\right)=1 \) ו-\( \pi\left(3,2\right)=-1 \). כשמדברים על שחמט הסיטואציה מורכבת הרבה יותר, מבחינת איך שכל אסטרטגיה נראית, כי כל אסטרטגיה מכילה הוראות מהצורה “אם הגעת לפוזיציה כזו של הלוח, פעל כך…” (וזה אפילו מורכב עוד יותר, כי גם לאופן ההגעה לפוזיציה יש חשיבות, כי למשל טמון בו מידע מי כבר ביצע הצרחות, כמה מהלכים ללא תזוזת/הכאת רגלי בוצעו, וכדומה). עדיין, קבוצת הפלטים האפשריים של הפונקציה תהיה או 1, או מינוס 1, או 0 (שבא לציין תיקו), ומרגע שכל שחקן החליט מה האסטרטגיה שלו (לפני שהמשחק התחיל!), כל מה שנותר לעשות הוא לשבת ו”להריץ” את המשחק ולראות מה קרה כדי לחשב את \( \pi \). אז אדגיש שוב - לא משנים אסטרטגיות “במהלך” המשחק, על בסיס מידע שצץ במהלך המשחק - האסטרטגיה מראש מתייחסת לכל מידע שעשוי לצוץ במהלך המשחק.

אם המשחק עצמו הוא סופי באופיו (משחק סופי של בחירות, ובכל שלב ניתן לבחור רק במספר סופי של אפשרויות) אז גם מספר האסטרטגיות האפשריות בו יהיה סופי. אני רוצה לדבר רק על הסיטואציה הזו, כי אם המשחק אינו סופי כל מה שאגיד הוא פשוט שגוי. השאלה שמעניינת אותנו כאן היא זו - בהינתן משחק, כמה אליס מסוגלת להרוויח בו ללא תלות במעשיו של בוב? הרי אליס אינה יכולה לדעת איזו אסטרטגיה בוב יבחר, ולהתחיל לנתח אילו אסטרטגיות “סביר” שהוא יבחר כבר יגרור אותנו לניתוחים מסובכים למדי - לכן הבעיה הראשונה שיש לפתור היא את שאלת הרווח-ללא-תלות-בבוב. אחרי שנגמור איתה אפשר יהיה לעבור לדברים מסובכים יותר (אך לא נזדקק להם כאן, ולכן לא אדבר עליהם).לכל אסטרטגיה \( x\in X \) שאליס נוקטת בה, יש לבוב מגוון אסטרטגיות \( y\in Y \) שהוא יכול לנקוט בהן. אחת מהאסטרטגיות הללו - נאמר, \( y_{0} \) - היא הגרועה ביותר מבחינת אליס, במובן זה שהרווח שאליס תקבל אם בוב ישחק את \( y_{0} \) (בהינתן שאליס שיחקה את \( x \)) הוא המינימלי: \( \pi\left(x,y_{0}\right)\le\pi\left(x,y\right) \) לכל \( y\in Y \). מכיוון שלאליס אין שליטה על מעשיו של בוב ומכיוון שהיא רוצה לדבר על הרווח הגדול ביותר שהיא תוכל לקבל בלי תלות במעשיו של בוב, \( \pi\left(x,y_{0}\right) \) הוא בדיוק הרווח הזה. סימון קצת יותר פשוט לכל זה הוא \( \min_{y}\pi\left(x,y\right) \): המינימום על פני כל הערכים של \( \pi\left(x,y\right) \) כאשר אנחנו משאירים את \( x \) קבוע ומשנים את \( y \).

אם כן, מה הרווח הגדול ביותר שאליס מסוגלת לקבל במשחק ללא תלות במעשיו של בוב? אם לכל \( x \) נקבע לנו ערך \( \min_{y}\pi\left(x,y\right) \) שאותו \( x \) מביא, אנחנו נרצה את ה-\( x \) שעבורו הרווח הזה מקסימלי - ואז נסמן את התוצאה כ-\( \max_{x}\min_{y}\pi\left(x,y\right) \).

מן העבר השני, המצב אצל בוב הפוך. מכיוון שהוא מעוניין להרוויח כמה שיותר במשחק, הוא מעוניין לקבל ערך קטן ככל האפשר של \( \pi\left(x,y\right) \). לכן הרווח האופטימלי של בוב הוא \( \min_{y}\max_{x}\pi\left(x,y\right) \). אם תצליחו להצדיק לעצמכם את הנוסחה הזו - כנראה שהבנתם את מה שהלך כאן עד כה.

מה המקסמין של אליס במשחק זוג או פרט? לכל \( x \) שלה קיים \( y \) של בוב כך ש-\( \pi\left(x,y\right)=-1 \), ולכן קל לראות שהערך הזה הוא מינוס 1. בדומה, הערך עבור בוב הוא 1. כלומר, אף אחד משני השחקנים לא מסוגל להבטיח לעצמו משהו שאיננו תבוסה מחפירה. זה מלמד אותנו שני דברים: ראשית, שתמיד מתקיים \( \min_{y}\max_{x}\pi\left(x,y\right)\le\max_{x}\min_{y}\pi\left(x,y\right) \) (נסו להוכיח זאת לעצמכם) ושנית - שבינתיים כל הסיפור עם המקסמין והמינמקס לא ממש שיפר משמעותית את מה שאפשר לומר על המשחק.

לכן השלב הבא הוא להכניס הסתברות לתמונה. עד כה דיברנו רק על אסטרטגיות “טהורות”, שחובה עלינו לבחור באחת מהן, וזהו. אבל למה, בעצם? האם מי שמשחק זוג או פרט לא מבצע הגרלה כלשהי כדי להחליט באיזו אסטרטגיה לנקוט, אפילו אם באופן בלתי מודע? האם שחקן שחמט משחק תמיד באותו האופן? במציאות כל אחד מאיתנו נוקט בתערובת של אסטרטגיות טהורות, כשהבחירה מה לעשות היא הסתברותית. אם כן, מבלי להיכנס יותר מדי לפרטים הטכניים, הרעיון הוא שאנחנו מרחיבים את מאגר האסטרטגיות שלנו, כך שכל אסטרטגיה כעת מייצגת ראשית כל הגרלה על פי התפלגות כלשהי של אחת מהאסטרטגיות ה”טהורות”, ואז משחק על פי האסטרטגיה שנבחרה. כדי לא לסבך את החיים עדיין אשתמש ב-\( x \) וב-\( X \) כדי לתאר אסטרטגיות “מעורבות” שכאלה. את מושג הרווח - \( \pi\left(x,y\right) \) - צריך גם כן לתקן קצת כדי שיתאר את הרווח שמתקבל בתוחלת (כלומר, מה יקרה בממוצע אם נשחק הרבה משחקים עם אותה אסטרטגיה מעורבת).

ועכשיו נכנס לתמונה משפט המינימקס: אם האסטרטגיות המותרות במשחק הן מעורבות, אז מתקיים \( \min_{y}\max_{x}\pi\left(x,y\right)=\max_{x}\min_{y}\pi\left(x,y\right) \). כלומר, אם אפשר להגריל אסטרטגיות, הדבר הטוב ביותר שאליס יכולה להבטיח לעצמה הוא בדיוק הדבר הטוב ביותר שבוב יכול להבטיח לעצמו. במשחק הזוג או פרט קל לראות שהדבר הזה הוא בדיוק 0 (שמשמעותו המעשית היא שכשמשחקים הרבה משחקים, בוב ואליס ינצחו בערך אותה כמות פעמים, אם שניהם משתמשים באסטרטגיה המעורבת האופטימלית שעליה דיברתי בפוסט המתאים).

אלא שיש עוד דרך להציג את המשפט - דרך מעט יותר מעניינת, לטעמי, וכזו ששופכת אור על עניין החזאים שלנו. לצורך כך, שאלה פשוטה: האם הטענה “לכל \( y \) קיים \( x \) כך שמתקיים \( P\left(x,y\right) \)” כש-\( P \) זו איזו שהיא תכונה של \( x,y \) (שמתקיימת או שאינה מתקיימת) גוררת את הטענה “קיים \( x \) כך שלכל \( y \) מתקיים \( P\left(x,y\right) \)”? עצרו וחשבו על כך רגע. נסו דוגמאות קונקרטיות של \( P \), וחזרו לקרוא עם המסקנה.

ובכן? התשובה היא - כמובן שלא! נניח ש-\( P\left(x,y\right) \) פירושו \( x<y \) (כש-\( x,y \) שניהם מספרים טבעיים, למשל). אז “לכל \( y \) קיים \( x \) כך ש-\( y<x \)” היא טענה שנכונה באופן טריוויאלי - בהינתן \( y \), ניקח את \( x \) להיות \( y+1 \). לכל מספר קיים מספר שגדול ממנו. לעומת זאת, “קיים \( x \) כך שלכל \( y \) מתקיים \( y<x \)” היא בבירור לא טענה נכונה - לא קיים מספר טבעי \( x \) שגדול מכל המספרים הטבעיים. הטענה השניה היא חזקה הרבה יותר, במובן זה שהיא מבטיחה קיום של \( x \) ספציפי שטוב לכל \( y \), להבדיל מהטענה הראשונה שלכל \( y \) קיים \( x \) ספציפי עבורו. לסטודנטים לחדו”א מביניכם שמתקשים בהבנת המושג של רציפות במידה שווה (מושג שגרם לי קשיים רבים בשעתו): רציפות “רגילה” היא טענה מהסוג הראשון, ורציפות במידה שווה היא טענה מן הסוג השני.

אז מה הקשר למשפט המינימקס? שמשפט המינימקס הוא דוגמה לסיטואציה שבה טענה מהסוג הראשון כן גוררת טענה מהסוג השני! במקרה הזה \( x,y \) הן אסטרטגיות ו-\( P\left(x,y\right) \) היא (למשל) התכונה “\( \pi\left(x,y\right) \) הוא לפחות הרווח האופטימלי של אליס”. הרי ברור שלכל \( y \) של בוב קיים \( x \) של אליס כך שהרווח של אליס הוא לפחות הרווח האופטימלי שלה - אחרת, אם יש \( y \) שעבורו אין לאליס מענה הולם, בוב ישחק את \( y \) הזה ואז אליס תהיה חייבת לקבל רווח שהוא נמוך מהרווח האופטימלי שלה - סתירה להגדרתו של הרווח האופטימלי (כזכור - הרווח הגדול ביותר שאליס יכולה לקבל בלי תלות בבוב).

אם כן, השאלה היא למה קיים לאליס \( x \) בודד שעבורו לכל \( y \) של בוב, \( \pi\left(x,y\right) \) הוא לפחות הרווח האופטימלי של אליס. נניח לרגע שלא קיים כזה - מה זה אומר? שלכל \( x \) של אליס, קיים \( y \) של בוב כך ש-\( \pi\left(x,y\right) \) קטן מהרווח האופטימלי של אליס. אבל זה אומר שהרווח האופטימלי של בוב הוא קטן מהרווח האופטימלי של אליס (זכרו - עבור בוב, קטן יותר זה טוב יותר) וזו סתירה לטענה של משפט המינימקס לפיו הם שווים. מסקנה - קיים לאליס \( x \) שעבורו לא משנה איזה \( y \) בוב יבחר, הרווח של אליס יהיה לפחות \( \pi\left(x,y\right) \).

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

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

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

אלא שהמשחק הזה אינו סימטרי כלל ועיקר. התפקיד של מוריד הגשם הוא להוריד גשם, והתפקיד של החזאי הוא לחזות איך מוריד הגשם יתנהג. מכאן נובע שאם החזאי יודע “מראש” מה האסטרטגיה המעורבת שמוריד הגשם בחר, החזאי מסוגל לתת תחזיות מדוייקות מאוד, כאלו שיעברו את המבחן בקלות (שוב - נימוק של זה דורש קצת פורמליסטיקה ועבודה טכנית, אבל הרעיון ברור). במילים אחרות - לכל \( y \) של מוריד הגשם, קיים \( x \) של החזאי כך ש-\( \pi\left(x,y\right)\ge1 \) - זהו בדיוק ה-\( x \) ש”תפור” לאסטרטגיה \( y \) של מוריד הגשם.

אבל עכשיו נכנס משפט המינימקס לתמונה… אם לכל \( y \) קיים \( x \) כך ש-\( \pi\left(x,y\right)\ge1 \), אז נובע מכך שקיים \( x \) כך שלכל \( y \) מתקיים \( \pi\left(x,y\right)\ge1 \). כלומר - יש לחזאי אסטרטגיה \( x \) שמבטיחה לו נצחון במשחק, בלי תלות במעשיו של מוריד הגשם! כל מה שהחזאי צריך לעשות הוא לדווח על התחזיות על פי \( x \), ואין זה משנה בכלל איך מוריד הגשם יתנהג, החזאי ינצח!

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