חד גדיא, בכמה זוזי?
07/04/2020
בשנים האחרונות נעשה שימוש נרחב בטכנולוגית "רשתות נוירונים מלאכותיות" [1] לבניית פונקציות המדמות התנהגויות בעולם האמיתי. הפונקציות הן מאוד מורכבות, אולם קיימים טריקים חכמים המבוססים על נושאים במתמטיקה שנלמדים גם בתיכון, המאפשרים לנתח אותן. נדגים חלק מטריקים אלו באמצעות שימוש באנלוגיה שמתאימה לפסח (לפי "חד גדיא").
דמיינו את חברי עמותת "מדע גדול, בקטנה" משחקים משחק אסטרטגיה במחשב. מטרת המשחק היא לגרום לשוחט לשחוט שור בשם "תורא". הצוות פיתח אסטרטגיה מבריקה: נגרום לתורא להתקרב לשוחט כדי לשתות מים משלולית. אולם כדי שיהיו מים בשלולית צריך קודם לגרום לשריפה, שכבאים יבואו לכבותה. כדי לגרום לשריפה, צריך לעצבן את השכנה כדי שתשרוף את המקל של בעלה. כדי לעצבן אותה, נגרום לבעלה להרביץ לכלב שלה במקל. כדי לגרום לבעל להרביץ לכלב, צריך לגרום לכלב לנשוך את החתול (שנקרא לו "שונרא"). כדי שהכלב יכעס וינשוך את שונרא, צריכים לגרום לשונרא לטרוף את הגדי המשפחתי, "גדיא" שמו. מסקנה: כדי להצליח (כלומר לגרום לשחיטה) צריך לגרום לבעל (נקרא לו "אבא") לקנות גדי ולהביאו לביתו. אולם, מה המחיר שצריך לדרוש מאבא עבור הגדי כדי שיהיה סיכוי גבוה לחולל את תגובת השרשרת?
חברי הצוות שיחקו מספר פעמים והחליטו להשתמש בתוצאות להעריך את המחיר האופטימלי של גדי באמצעות מימוש רשת חישובית פשוטה: החברים התיישבו בטור (הערה חשובה: וירטואלית, בזום!), וכל אחד קיבל משימה לייצר פונקציה שתעריך את ההסתברות שיקרה שלב אחד באסטרטגיה שפותחה. כל חבר מקבל נתונים מזה שלפניו, עושה בהם שימוש בחישוביו ומעביר תוצאה קדימה לשכן הבא. המידע מפעפע עד הגיעו לתחילת הטור.
בסוף הטור התיישבה קרן שנתנה הערכה ראשונית למחיר של הגדי, שנסמן ב-x0 (נניח 4 זוזים) והעבירה ליניב. יניב השתמש בפונקציה שפיתח (x1=f1(x0 לחשב את הסיכוי x1 שאבא יקנה גדי כתלות ב-x0 (כלומר, בעלות 4 זוזים), והעביר את התוצאה לאלכס. נזכר שהשלב הבא בתוכנית הוא לגרום לשנורא לטרוף את הגדי המשפחתי, לכן אלכס צריך לחשב את (x2=f2(x1 שזה הסיכוי שהחתול יטרוף את הגדי כתלות בסיכוי x1 שאבא אכן קנה גדי. את התוצאה הוא העביר הלאה לשקד, וכולי. התוצאה הסופית מתקבלת בשלב השביעי (x7) והיא ההסתברות המוערכת להצלחת האסטרטגיה, דהיינו שתבוצע השחיטה. בכתיבה מתמטית: אם נבטא את סיכויי לשחיטה (y=x7) כפונקציה של מחיר גדי (x=x0), נקבל את מה שקרוי במתמטיקה "פונקציה מורכבת" : פונקציה שהיא הרכבה של פונקציות.
y=x7=f7(f6(f5(f4(f3(f2(f1(x))))))) // function composition
הפונקציה נראית מסובכת, אולם מה שמקל את החישוב הוא עבודת הצוות: כל חבר בצוות ("אלמנט ברשת") מבצע רק שלב אחד בחישוב ומעביר הלאה את התוצאות. נניח שעבור x=4 זוזים, התוצאה y (הסיכוי לשחיטה) היא רק 50%.האם ניתן לשפר? למשל, אם נדרוש רק 3 זוזים, אולי הסיכוי לשחיטה יגדל למשל ל-80%? באופן כללי, מה ערכו של x (מחיר גדי) כדי לקבל y מקסימלי ומה ערכו?
מי שלמד פעם אנליזה ודאי יזכר שהפתרון הסטנדרטי לבעייה הוא לחשב את נגזרת הפונקציה ולבדוק עבור איזה ערך x היא מתאפסת. אולם, הפונקציה מאוד מורכבת ולא ניתן לגזור ולמצוא זאת בדרך אלגברית. מה לעשות?
לשם כך, המתמטיקאים שלפו עוד שפן מהכובע: "כלל השרשרת" המוגדר כך: "הנגזרת של פונקציה מורכבת היא מכפלת הנגזרות של הפונקציות המרכיבות אותה". כדי להבהיר זאת נראה דוגמה.
בהתאם לכלל, כדי לחשב את ערך הנגזרת בנקודה x=4 נבקש מכל חבר צוות לחשב בנוסף לערך הפונקציה שהוא אחראי עליה גם את ערך הנגזרת שלה (שהוא בדרך כלל פשוט לחישוב) ולהעביר את התוצאות לשכן שמלפנים. בסוף, נכפיל את כל הנגזרות שנאספו כדי לקבל את הנגזרת הכללית. למשל, יניב יחשב (x1=f1(4 וגם את הנגזרת (f1'(4, ויעביר הלאה. בכתיבה מתמטית:
x0=4, x1=f1(x0), x2=f2(x1)…. y=x7=f7(x6 ) / / function
y’(4) = f1’(x0) * f2’(x1) * f3’(x2) *....f7`(x6) // chain rule
אכן, המבנה של רשת מאפשר גם חישוב פשוט של הנגזרת בכל נקודה שנבחר בשילוב עבודת צוות!
חישוב נגזרת בנקודה x=4 (כלומר, עבור גדי בעלות 4 זוזים) נותן רמז לאן להתקדם כדי למצוא את המקסימום, או ההסתברות הגבוהה ביותר. המטרה היא להגיע לפסגה ("המקסימום של הפונקציה") שבה הנגזרת מתאפסת. למשל, אם נגלה שהנגזרת שלילית עבור 4 זוזים, כנראה אנו במגמת ירידה, וכדאי לפנות אחורה ולחשב את הנגזרת עבור ערך קטן מ-4. כדי לבחור אילו ערכים כדאי לנסות, נעזרים גם באלגוריתם "gradient descent” שכתבנו עליו [2]. אם נעשה זאת, נגלה בודאי שהמחיר האופטימלי של גדי הוא 2 זוזים (דהיינו תרי זוזי).
אכן, השילוב של "כלל השרשרת" עם מבנה רשת מאפשר לפתור בעיות מורכבות, כמו המחיר של "חד גדיא". שיהיה לכולם פסח נפלא!
קישורים:
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
