Machine Leaning

Mar

2021

מהו Variational AutoEncoders?

מיועד ל- מטיבי לכת (כתבה מאוד טכנית)

נכתב על ידי avraham raviv

כדי להבין היטב את אופן הפעולה של Variational Autoencoders (VAE), נדבר מעט על הורדת מימדים, לאחר מכן נסביר מהו Autoencoders, כיצד הוא עובד ומה החסרונות שלו, ומשם נעבור ל-VAE.

Dimensionality Reduction

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

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

תהליך האימון הוא דו שלבי: דאטה $x\in R^{n}$ עובר דרך encoder, ולאחריו מתקבל $e(x)\in R^{m}$ , כאשר $m<n$ לאחר מכן התוצאה מוכנסת ל-decoder בכדי להחזיר אותה למימד המקורי, ולבסוף מתקבל $d(e(x)) \in R^{^{n}}$ אם לאחר התהליך מתקיים $x=d(e(x))$ אז למעשה לא נאבד שום מידע בתהליך, אך אם לעומת זאת $x\neq d(e(x))$ אז מידע מסוים אבד עקב הורדת המימד ולא היה ניתן לשחזר אותו במלואו בפענוח. באופן אינטואיטיבי, אם אנו מצליחים לשחזר את הקלט המקורי מהייצוג של במימד נמוך בדיוק טוב מספיק, כנראה שהייצוג במימד נמוך הצליח להפיק את הפיצ’רים המשמעותיים של הדאטה המקורי.

איור 1. ארכיטקטורת encoder ו-decoder.

כאמור, המטרה העיקרית של השיטות להורדת מימד הינה לקבל ייצוג לטנטי איכותי עד כמה שניתן. הדרך לעשות זאת היא לאמן את זוג ה-encoder-decoder השומרים על מקסימום מידע בעת הקידוד, וממילא מביאים למינימום את שגיאת שחזור בעת הפענוח. אם נסמן בהתאמה E ו-D את כל הזוגות של encoder-decoder האפשריים, ניתן לנסח את בעיית הורדת המימד באופן הבא:

$(e^{*},d^{*})=\underset{(e,d)\in ExD}{argmin}\epsilon (x,d(e(x)))$

כאשר $\epsilon (x,d(e(x)))$ הוא שגיאת השחזור שבין הדאטה המקורי לבין הדאטה המשוחזר.

אחת השיטות השימושיות להורדת מימד שאפשר להסתכל עליה בצורה הזו היא Principal Components Analysis (PCA). בשיטה זו מטילים (בצורה לינארית) דאטה ממימד n למימד m על ידי מציאת בסיס אורתוגונלי במרחב ה-m מימדי בו המרחק האוקלידי בין הדאטה המקורי לדאטה המשוחזר מהייצוג החדש הוא מינימלי.

איור 2. דוגמא להורדת מימד בשיטת PCA.

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

Autoencoders (AE)

ניתן לקחת את המבנה של ה- encoder-decoder המתואר בפרק הקודם ולהשתמש ברשת נוירונים עבור בניית הייצוג החדש ועבור השחזור. מבנה זה נקרא Autoencoder:

איור 3. Autoencoder – שימוש ברשתות נוירונים עבור הורדת המימד והשחזור.

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

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

איור 4. דוגמא לשימוש ב-Autoencoder.

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

Variational AutoEncoders (VAE)

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

כדי להתמודד עם בעיה זו, ניתן להשתמש ב-Variational AutoEncoders (VAE). בשונה מ-AE שלוקח דאטה ובונה לו ייצוג ממימד נמוך, VAE קובע התפלגות פריורית למרחב הלטנטי z – למשל התפלגות נורמלית עם תוחלת 0 ומטריצת II covariance. בהינתן התפלגות זו, ה-encoder מאמן רשת המקבלת דאטה x ומוציאה פרמטרים של התפלגות פוסטריורית z|x , מתוך מטרה למזער כמה שניתן את ההפרש בין ההתפלגויות z ו- z|x . לאחר מכן דוגמים וקטורים מההתפלגות הפוסטריורית z|x (הנתונה על ידי הפרמטרים המחושבים ב-encoder), ומעבירים אותם דרך ה-decoder כדי לייצר פרמטרים של ההתפלגות z|x . חשוב להבהיר שאם הדאטה המקורי הוא תמונה המורכבת מאוסף של פיקסלים, אזי במוצא יתקבל x|z לכל פיקסל בנפרד ומההתפלגות הזו דוגמים נקודה והיא תהיה ערך הפיקסל בתמונה המשוחזרת. באופן הזה, הלמידה דואגת לא רק להורדת המימד, אלא גם להתפלגות המושרית על המרחב הלטנטי. כאשר ההתפלגות המותנית במוצא x|z טובה, קרי קרובה להתפלגות המקורית של x, ניתן בעזרתה גם ליצור דוגמאות חדשות, ובעצם מתקבל מודל גנרטיבי. כאמור, ה-encoder מנסה לייצג את הדאטה המקורי באמצעות התפלגות במימד נמוך יותר, למשל התפלגות נורמלית עם תוחלת ומטריצת covariance: $z\sim p(z|x)=N(\mu _{z},\sigma _{x})$

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

איור 5. ארכיטקטורה של VAE.

לאחר שהוצג המבנה הכללי של VAE, ניתן לתאר את תהליך הלמידה, ולשם כך נפריד בשלב זה בין שני החלקים של ה-VAE. ה-encoder מאמן רשת שמקבלת דוגמאות מסט האימון, ומנסה להפיק מהן פרמטרים של התפלגות הקרובים כמה שניתן להתפלגות פריורית , שכאמור נקבעה מראש. מההתפלגות הנלמדת הזו דוגמים וקטורים חדשים ומעבירים ל-decoder. ה- decoderמבצע את הפעולה ההפוכה – לוקח וקטור שנדגם מהמרחב הלטנטי , ומייצר באמצעותו דוגמא חדשה הדומה לדאטה המקורי. תהליך האימון יהיה כזה שימזער את השגיאה של שני חלקי ה-VAE – גם שבמוצא יהיה כמה שיותר קרוב ל- המקורי, וגם ההתפלגות תהיה כמה שיותר קרובה להתפלגות הפריורית z. נתאר באופן פורמלי את בעיית האופטימיזציה ש-VAE מנסה לפתור. נסמן את הווקטורים של המרחב הלטנטי ב-z, את הפרמטרים של ה-decoder ב- $\theta$ , ואת הפרמטרים של ה-encoder ב- $\lambda$ . כדי למצוא את הפרמטרים האופטימליים של שתי הרשתות, נרצה להביא למקסימום את $p(\widehat{x}=x;\theta)$ , כלומר למקסם את הנראות המרבית של סט האימון תחת $\theta$ . כיוון שפונקציית log מונוטונית, נוכל לקחת את לוג ההסתברות:

$L(\theta)=log(p(x;\theta ))$

אם נביא למקסימום את הביטוי הזה, נקבל את ה- $\theta$ האופטימלי. כיוון שלא ניתן לחשב במפורש את $p(x;\theta )$ , יש להשתמש בקירוב. נניח וה -encoder הוא בעל התפלגות מסוימת $q(z;\lambda )$ (מה ההסתברות לקבל את z בהינתן x בכניסה). כעת ניתן לחלק ולהכפיל את $L(\theta )$ ב – $q(z;\lambda )$ :

$log[p(x;\theta )]=log \underset{z}{\Sigma}p(x,z;\theta )=log\underset{z}{\Sigma}q(z;\lambda )\frac{p(x,z;\theta)}{q(z;\lambda)}\geqslant \underset{z}{\Sigma}q(z;\lambda)log\frac{p(x,z_{i};\theta)}{q(z;\lambda)}$

כאשר אי השוויון האחרון נובע מאי-שוויון ינסן, והביטוי שמימין לאי השיוויון נקרא Evidence Lower BOund $ELBO(\theta,\lambda)$ . ניתן להוכיח שההפרש בין ה-ELBO לבין הערך שלפני הקירוב הוא המרחק בין שתי ההתפלגויות $p(z|x),q(z)$ , והוא נקרא Kullback–Leibler divergence ומסומן ב- $D_{KL}$ :

$log[p(x;\theta)]=ELBO(\theta,\lambda)+D_{KL}(q(z;\lambda)||p(z|x;\theta))$

אם שתי ההתפלגויות זהות, אזי מרחק $D_{KL}$ ביניהן הוא 0 ומתקבל שוויון: $log[p(x;\theta)]=ELBO(\theta,\lambda)$ . כזכור, אנחנו מחפשים למקסם את פונקציית המחיר $log[p(x;\theta)]$ , וכעת בעזרת הקירוב ניתן לרשום:

$L(\theta)=log[p(x;\theta)]\geqslant ELBO(\theta,\lambda)$

$\rightarrow \theta_{ML}=arg\underset{\theta}{max}L(\theta)=arg\underset{\theta}{max}\underset{\lambda}{max}ELBO(\theta,\lambda)$

כעת ניתן בעזרת שיטת GD למצוא את האופטימום של הביטוי, וממנו להפיק את הפרמטרים האופטימליים של ה-encoder ושל ה-decoder. נפתח יותר את ה- $ELBO(\theta,\lambda)$ עבור VAE, ביחס לשתי התפלגויות: $p(x|z;\theta)$ – ההסתברות ש-decoder עם סט פרמטרים $\theta$ יוציא x בהינתן z. $q(z|x;\lambda)$ – ההסתברות ש-encoder עם סט פרמטרים $\lambda$ יוציא את $z_{i}$ בהינתן x בכניסה לפי הגדרה:

$ELBO(\theta, \lambda)=\underset{z}{\Sigma}q(z|x;\lambda)log[p(x,z;\theta)]-\underset{z}{\Sigma}q(z|x;\lambda)log[q(z|x;\lambda)$

את הביטוי $log[p(x,z;\theta)]$ ניתן לפתוח לפי בייס:

$p(x,z)=p(x|z)\cdot p(z)$

$={\underset{z }{\sum}}q(z|x;\lambda)(log[p(x|z;\theta)]+log[p(z;\theta))])-{\underset{z }{\sum}}q(z|x;\lambda)log[q(z|x;\lambda)]$

$={\underset{z }{\sum}}q(z|x;\lambda)(log[p(x|z;\theta)]-{\underset{z }{\sum}}q(z|x;\lambda)(log[q(z|x;\lambda)]-log[p(z;\theta)])$

$={\underset{z }{\sum}}q(z|x;\lambda)(log[p(x|z;\theta)]-{\underset{z }{\sum}}q(z|x;\lambda)\frac{log[q(z|x;\lambda]}{log[p(z;\theta]}])$

הביטוי השני לפי הגדרה שווה ל- $D_{KL}(q(z|x;\lambda)||p(z;\theta))$ , לכן מתקבל:

$=\underset{z}{\sum}q(z|x;\lambda)log[p(x|z;\theta)]-D_{KL}(q(z|x;\lambda)||p(z))$

הביטוי הראשון הוא בדיוק התוחלת של $log[p(x|z;\theta)]$ . תחת ההנחה ש-z מתפלג נורמלית, ניתן לרשום:

$=E_{q(z|x;\lambda)}logN(x;\mu_{\theta}(z),\sigma_{\theta}(z))-D_{kl}(N(\mu_{\lambda}(x),\sigma_{\lambda}(x))||N(0,I)))$

כדי לחשב את התוחלת ניתן פשוט לדגום דוגמאות מההתפלגות $z|x\sim N(\mu_{\theta}(x),\sigma_{\theta}(x)))$ ולקבל:

$E_{q(z|x;\lambda)}logN(x;\mu_{\theta}(z),\sigma_\theta(z))\approx logN(x;\mu_{\theta}(z),\sigma_{\theta}(z))$

ועבור הביטוי השני יש נוסחה סגורה:

$D_{KL}(N(\mu,\sigma^{2})||N(0,I))=\frac{1}{2}(\mu^2+\sigma^2-log \sigma^2)$

כעת משיש בידינו נוסחה לחישוב פונקציית המחיר, נוכל לבצע את תהליך הלמידה. יש לשים לב שפונקציית המחיר המקורית הייתה תלויה רק ב- $\theta$ , , אך באופן שפיתחנו אותה היא למעשה דואגת גם למזעור ההפרש בין הכניסה למוצא, וגם למזעור ההפרש בין ההתפלגות הפריורית z לבין ההתפלגות z|x שבמוצא ה-encoder.

איור 6. תהליך הלמידה של VAE.

כאשר נתון סט דוגמאות , ניתן להעביר כל דוגמא $x_{t}$ ב-encoder ולקבל עבורה את $\mu _{\lambda },\sigma _{\lambda }$ . לאחר מכן דוגמים וקטור לטנטי z מההתפלגות עם פרמטרים, מעבירים אותו ב-decoder ומקבלים את $\inline \mu _{\theta},\sigma _{\theta}$ . לאחר התהליך ניתן להציב את הפרמטרים המתקבלים ב-ELBO ולחשב את ה-Loss. ניתן לשים לב שה-ELBO מורכב משני איברים – האיבר הראשון מחשב את היחס בין הדוגמא שבכניסה לבין ההתפלגות שמתקבלת במוצא, והאיבר השני מבצע רגולריזציה להתפלגות הפריורית במרחב הלטנטי. הרגולריזציה גורמת לכך שההתפלגות במרחב הלטנטי z|x תהיה קרובה עד כמה שניתן להתפלגות הפריורית z. אם ההתפלגות במרחב הלטנטי קרובה להתפלגות הפריורית, אז ניתן בעזרת ה-decoder ליצור דוגמאות חדשות, ובמובן הזה ה-VAE הוא מודל גנרטיבי.

הדגימה של z מההתפלגות במרחב הלטנטי יוצרת קושי בחישוב הגרדיאנט של ה-ELBO, לכן בדרך כלל מבצעים Reparameterization trick – דוגמים $z_{0}$ מהתפלגות נורמלית סטנדרטית, ואז כדי לקבל את z משתמשים בפרמטרים של ה-encoder:

$z=z_{0}\sigma _{\lambda}(x)+\mu _{\lambda }(x)$

.forward-backwardבגישה הזו כל התהליך נהיה דטרמיניסטי – מגרילים מראש $z_{0}$ ואז רק נשאר לחשב באופן סכמתי את ה

Reference:

https://towardsdatascience.com/understanding-variational-autoencoders-vaes-f70510919f73

Sep

2020

אלגוריתם Reinforce – Vanilla Policy Gradients

מיועד ל- מטיבי לכת (כתבה מאוד טכנית)

נכתב על ידי תמיר נווה

כשמתפרסם מאמר ב Science בתחום שלי (Machine Leaning) זה משהו מיוחד כי זה לא קורה כל יום.

אתם מוזמנים לקרוא על איך OpenAI מביאים מודל לשחק את המשחק הרב משתתפים “תפוס את הדגל” ברמת מיומנות אנושית ואולי יותר מעניין מזה איך מאמנים מודל לגרום לסוכנים שמשחקים מחבואים לשתף בינהם פעולה באופן יצירתי:

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

לא הצלחתי למצוא תירגום טוב למונח: גראדיאנטים של מדיניות (אשמח לעזרה…)

אבל Policy Gradient הינה גישה אלגוריתמית לפתירת בעיות Reinforcement Learning שנגזרו ממנה אלגוריתמים רבים כגון: Actor Critic, A2C, A3C, TRPO, PPO, SAC ועוד ועוד…

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

רקע קצר על למידה באמצעות חיזוקים (Reinforcement Learning)

יש סוכן (Agent) שחי בסביבה דינאמית (Environment) ויש לו סט של פעולות (Actions) שהוא יכול לעשות בסביבה. הפעולות שלו עשויות לשנות את המצב (State) של הסביבה, ועל כל פעולה שלו הוא עשוי לקבל פידבק מהסביבה שנקרא תגמול (Reward) שיכול להיות חיובי או שלילי. מטרתינו למצוא את המדיניות (Policy) שהינו אלגוריתם שמחליט בעבור הסוכן איך לפעול בסביבה (איזו פעולה לבחור בכל רגע) באופן כזה שיביא למקסימום ההחזר (Return) שזה סך כל התגמולים שמקבל הסוכן.

השפה המתמטית לתיאור בעיה זו היא תהליך החלטות מרקובי MDP=Markov Decision Process:

מקור: https://he.wikipedia.org/wiki/%D7%AA%D7%94%D7%9C%D7%99%D7%9A_%D7%94%D7%97%D7%9C%D7%98%D7%94_%D7%9E%D7%A8%D7%A7%D7%95%D7%91%D7%99

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

עידן הלמידה העמוקה חולל מהפיכה גם בתחום ה Reinforcement Learning במובן הזה שרשת נוירונים עמוקה מהווה את המדיניות (Policy), ז”א מקבל כקלט את ה State ומחזירה את הפעולה (Action) הרצוייה.

כעת חלק הכיפי,

פורמליזם מתמטי לתיאור הבעיה

בכל נקודת זמן t יש לנו מצב, פעולה ותגמול:

ומאחורי הקלעים קיימת פונקציית הסתברות המעברים בין המצבים:

שמשמעותה: מה ההסתברות שאם התחלנו במצב St והסוכן בחר לבצע פעולה At הסביבה עברה למצב St+1.

למשל אם הסוכן שלנו הוא רכב, המצב שלנו הוא מיקומו במרחב (x,y) והפעולה היא לקחת הגה ימינה, מה ההסתברות שהרכב יעבור למצב (x+5,y). אז בהסתברות גבוהה זה יקרה. אבל לא תמיד זה יקרה כי אולי יש שמן על הכביש והפעולה הביאה את הרכב למצב אחר (x+500,y).

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

מסלול (Trajectory) סופי הינו וקטור של השלשות הבאות:

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

כל אחד מהאלמנטים במסלול 𝜏 הינו וקטור אקראי, וההסתברות לקבל מסלול שלם הינה:

ההסתברות לקבל מסלול 𝜏 היא מכפלת ההסתברות להיות במצב הראשון S1 כפול

ההסתברות לבחור פעולה A1 כפול ההסתברות לעבור למצב S2 כפול ההסתברות לבחור פעולה A2 וכו’…

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

פונקציית המטרה שלנו J שאותה נאפטם (ז”א נשאף למצוא לה מקסימום) הינה התוחלת של סכום התגמולים:

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

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

נשים לב ש כולל בתוכו למעשה גם את על אף שהסימון אינו מייצג זאת.

מדוע לא פשוט לאמן מודל עם פונקציית מטרה?

התחום Reinforcement Learning אומנם יושב תחת המטריה הרחבה של עולם ה Machine Learning אבל הוא אינו Supervised Learning וגם אינו Unsupervised Learning כי זה לא שיש לנו Ground Truth של אילו החלטות היה הסוכן אמור לבחור בכל צעד שלו, אבל מצד שני גם לא יהיה נכון לומר שלא קיים ברשותינו מידע לגבי מה נכון ומה לא כי יש לנו את התגמולים. ולכן זה מן תחום כלאיים בין Supervised לבין Unsupervised.

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

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

כידוע בלמידה עמוקה משתמשים ב Gradient Descent (או בשיכלולים שלו) כדי לאמן את המודל:

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

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

אז מה עושים בכל זאת ?

מכיוון שלכל f(x) מתקיים:

נוכל להשתמש בזה לטובתינו:

ולקבל:

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

נשים לב שההסתברות לקבלת מסלול תלויה ב θ אבל סך התגמולים אינו תלוי ב θ עבור מסלול מסויים 𝜏.

הטריק הזה שהוסיף לנו log עזר לנו להמנע מנגזרת של מכפלות.

נזכור שההסתברות לקבל מסלול היא מכפלת ההסתברויות של המעברים בתוך המסלול:

וכשמפעילים על מכפלות אלו לוג זה הופך לסכומי הסתברויות:

ואז הגרדיאנט שלנו לפי θ נהיה פשוט יותר כי כל מה שלא תלוי בו מתאפס:

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

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

כאשר i רץ על פני כל ה trajectories שהקלטנו ו t הוא האינדקס בכל trajectory.

פירוש לתוצאה:

המרכיב השמאלי בביטוי הוא ה Maximum Likelihood של ההסתברות ז”א הוא מבטא איך לעדכן את המשקולות כדי שבסבירות גבוהה יותר הסוכן יעבור את המסלולים שאגרנו.

הביטוי כולו מבטא איך לעדכן את משקולות הרשת כך שתגדיל את ההסתברות לקבל את המסלולים שאגרנו שהיו להם תגמולים מצטברים גבוהים ותקטין את ההסתברות לקבל את מסלולים להם היו תגמולים מצטברים נמוכים.

צעד אחרון לפני מימוש

אז אפילו שיש נוסחה שימושית מפורשת לקח לי לא מעט זמן להבין קודים לדוגמא המממשים Vanilla Policy Gradient (אלגוריתם Reinforce), ורק בזכות הקורס של ברקלי הבנתי שאם מניחים התפלגות נורמלית למדיניות ומשתמשים בפרדיקציה של הרשת fלהיות וקטור התוחלות:

אז עידכון המשקולות נהיה בפועל:

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

לשם הפשטות נתעלם ממטריצת הקוואריאנס ומהחצי המופיע בביטוי. (נניח שמטריצת הקוואריאנס הינה מטריצת היחידה וממילא החצי נבלע ב Learning Rate):

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

וכעת כשמסתכלים על מימושים הכל נראה ברור יותר… לא כך ?