נגזרות בלילה
21/08/2019
בשנים האחרונות, בעקבות הפופולריות הגואה של למידת מכונה ובעיקר טכנולוגית "למידה עמוקה" [1], מהנדסים וחוקרים רבים חוזרים לעסוק בנושאים שלא נגעו בהם שנים רבות, כמו נגזרות. אלגוריתם מרכזי שעושה שימוש בנגזרות, וממומש לעיתים גם בחומרה נקרא Gradient-Descent. אנו מזמינים אתכם לקחת אוויר ולחזור לעולם הנגזרות ושימושיהן, באמצעות משל דמיוני על ניווט לילי.
נדמיין את עצמנו בטיול שטח לילי, נוסעים במכונית בערפל, ולא רואים ממטר. אנו צריכים לרדת לתחתיתו של עמק, לנקודה הנמוכה שבו, אולם לא יודעים את מיקומה. ה-GPS מראה רק קואורדינטות מיקום בקו אווירי. מה לעשות? הצעה: נרד מהמכונית, נגשש באפלה ונמצא את הכיוון שבו שיפוע הירידה הוא הגדול ביותר (נניח למשל: מערב). כעת, נקבע נקודה מסוימת, לא רחוקה מדי בכיוון זה (למשל: 100 מטר מערבה), נתכנת את אפליקציית הניווט, ונורה לנהג הרכב לנסוע לשם. כשנגיע לנקודה זו, נרד מהמכונית, נגשש שוב באפילה למצוא את הכיוון בו הירידה הכי תלולה (למשל: דרום מערב), נקבע שוב נקודת עצירה בכיוון, נורה לנהג לנסוע לשם וחוזר חלילה. אם תוואי השטח הוא בעל עקמומית חלקה ולא מזמן הפתעות, נגיע לבסוף למקום שבו בכל כיוון אליו נגשש, נגלה רק עליות. מכאן נוכל להסיק שהגענו לתחתית, לנקודה הנמוכה ביותר בסביבה.
במציאות, זו לא הדרך המועדפת לניווט: כנראה שלא ניסע 100 מטר בין נקודות העצירה, אלא נגיב מיידית בהתאם לתוואי הדרך. בנוסף, כיוון שלפני כדור הארץ אין תמיד עקמומיות חלקה יש סיכוי רב להפתעות לא נעימות בנסיעה עיוורת, כמו למשל בורות, מבנים או מצוקים. אולם לצורך המחשת האנלוגיה, נשתמש בשיטה המוצעת: נקבע בכל שלב את נקודת העצירה הבאה על המפה, ונורה לנהג הרכב לדלג אליה.
כיצד כדאי לקבוע את המרחק (בקו אווירי) בין שתי עצירות? אם נעשה עצירות קרובות מדי, אנו עלולים לבלות את כל הלילה בגישוש בחשיכה. לעומת זאת, אם המרחק גדול מדי, אנו עלולים לפספס את תחתית העמק, למצוא את עצמנו בצידו השני , ואז נצטרך לחזור. מה כדאי לעשות?
שיטה מוצעת: נקבע את גודל הצעד המחושב (כלומר: מרחק אווירי בין שתי עצירות) כתלות בשיפוע הירידה. כאשר השיפוע גדול, ניתן לשער שאנו עדיין רחוקים מהתחתית, לכן כדאי לעשות צעד גדול, ולחסוך זמן. לעומת זאת, כאשר השיפוע קטן, זה סימן שאנו קרבים לפלאטו, ולכן כדאי לעשות רק צעדים קטנים עד שנגיע מספיק קרוב לתחתית (שבה השיפוע נהייה קרוב לאפס, ולכן גם גודל הצעד המחושב נהייה קטן מאוד) ואז נעצור.
ניתן להשתמש בסיפור זה כאנלוגיה לשיטת האופטימיזציה המתמטית [2] Gradient-Descent, שמטרתה למצוא מינימום לפונקציה רבת משתנים. לשם כך, נחליף את תיאור פני השטח שבסיפור (שהוא למעשה פונקציה עם שני משתנים X, Y שהם למשל קואורדינטות אורך ורוחב) בפונקציה כללית רב-ממדית שאנו מחפשים את המינימום שלה. אם היינו חיים בעולם חד-מימד (או באנלוגיה: היינו נוסעים כל הזמן בכיוון קבוע למשל מערב) את שלב הגישוש למציאת שיפוע הירידה המקסימלי, היינו מחליפים במציאת הנגזרת של פונקציית פני השטח (למי שלא למד או כבר שכח: הנגזרת של פונקציה בנקודה נתונה היא שיפוע המשיק לה בנקודה זו), והנגזרת הייתה מתקרבת לאפס ככל שהיינו מתקרבים לנקודת המינימום.
אך המשטח בדוגמה שלנו הוא דו-מימדי, ולכן בכל נקודה ניתן להעביר אינסוף משיקים בכל כיוון אפשרי, כך שמושג הנגזרת כבר אינו מועיל לנו. הפתרון טמון בכלי מתמטי שנקרא וקטור הגרדיאנט, והוא מהווה הכללה של מושג הנגזרת לפונקציות מרובות משתנים. במקום להעביר ישר המשיק למשטח בנקודה כלשהי, נעביר מישור המשיק למשטח בנקודה זאת. בניגוד לישרים משיקים (שיש אינסוף כאלו בכל נקודה), מישור משיק יש רק אחד ווקטור הגרדיאנט ניצב למישור זה, כך שהיטלו על מישור המפה מראה לנו על כיוון העליה התלול ביותר.
בדומה לאנלוגיה, באלגוריתם זה קופצים מנקודה לנקודה הבאה הנמצאת בכיוון השלילי של הגרדיאנט ( "כיוון הירידה") במרחק היחסי לגודל הגרדיאנט. הקפיצות הללו נמשכות עד שמגיעים מספיק קרוב למינימום הפונקציה שבה הגרדיאנט מתאפס ("תחתית העמק"). אם היינו יודעים לחשב מראש באיזו נקודה הגרדיאנט מתאפס, היינו קופצים ישירות לאותה נקודה, אולם בניגוד לתרגילי מתמטיקה בתיכון, לרוב לא ניתן למצוא בדרך אלגברית מתי הגרדיאנט מתאפס, ולכן אנו נאלצים להתקדם לאט על פני השטח בשיטה שתיארנו.
Gradient-Descent היא אחת השיטות המתמטיות הפשוטות המשמשת לצרכי אופטימיזציה. בפוסט קודם [3] הסברנו על חשיבות אופטימיזציות בהרבה תחומים בחיים, וסיפרנו גם כיצד משתמשים באלגוריתם ב"למידה עמוקה" [1] .
לאלגוריתם זה יש מספר בעיות. לעיתים, לפונקציה המתארת את פני השטח באנלוגיה יש כמה עליות ומורדות וכתוצאה מכך אנו יכולים למצוא את עצמנו מגיעים לואדי קטן, ומסיקים בטעות שהגענו לתחתית העמק. בעיה זו של קיום מינימום מקומי לעומת גלובלי מצריכה לעיתים שימוש בשיטות מתקדמות יותר, כמו למשל "אלגוריתמים אבולוציוניים" [3].
בעייה אחרת, היא בעיית הפלאטו. דמיינו את עצמכם נוסעים בלילה על רמה גבוהה, מחפשים את הירידה לעמק. בכל מקום בו אתם עוצרים, אתם מגלים שהשיפוע הוא אפסי ואין לכם קצה חוט לאן להמשיך. אתם ממשיכים מתוסכלים בשיטוט חסר מטרה, עד שלפתע בזמן שאתם יורדים מהרכב כדי לגשש ולקבוע את נקודת העצירה הבאה, אתם מרגישים שאתם מדרדרים בפתאומיות לתהום....
בעיות כאלו, של שימוש בפונקציות עם נגזרת קרובה לאפס ("פלאטו") או שימוש בפונקציה לא גזירה ("שינוי פתאומי") יכולות לשבש את תהליך האופטימיזציה. המהנדסים שבונים את הפונקציות הללו, עמלים קשות כדי למנוע את הבעיות ולשכלל את האלגוריתמים הרבה מעבר למה שתואר כאן, כדי שיוכלו להתמודד גם עם מקרים מורכבים ומגוונים יותר.
-------------------------------------------------------------------------------------------------------------------------
[3] קישור לפוסט קודם על אלגוריתמים אבולוציוניים
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
