בקצרה:הפצה לאחור של השגיאה (Backpropagation; Rumelhart, Hinton & Williams, 1986) היא הדרך לחשב את הגרדיאנט של פונקציית השגיאה של רשת נוירונים ביחס לכל המשקלים וההטיות שלה, כדי לבצע צעד של ירידה תלולה ביותר. החישוב הוא רקורסיה שמתחילה בשכבת הפלט, [math]\displaystyle{ \frac{\partial E}{\partial y^{n}_i}=y^{n}_i-d_i }[/math], ובכל צעד עוברת שכבה אחת אחורה בעזרת כלל השרשרת: מהנגזרות לפי הפלט של שכבה מחשבים את הנגזרות לפי הפלט של השכבה הקודמת. לכן השיטה נקראת הפצת השגיאה לאחור. בניסוי על ספרות כתובות ביד (MNIST), רשת 784–64–10 עם סיגמואיד, במעבר אחד על הנתונים, מגיעה ל־95.24% סיווג נכון.
מבוסס על המאמר:Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323(6088), 533–536. DOI: 10.1038/323533a0.
הסיפור הבסיסי
יש לנו רשת של [math]\displaystyle{ n }[/math] שכבות, ולכל קלט יש פלט רצוי. נרצה לבצע צעד בכיוון הירידה התלולה ביותר על פונקציית השגיאה, כדי לתקן את כל המשקלים. לשם כך צריך את הגרדיאנט של פונקציית השגיאה ביחס לכל מטריצת משקלים. מיד נתאר כיצד מחשבים אותו ברקורסיה, שכבה אחר שכבה, מהפלט אחורה. לכן השיטה נקראת הפצת השגיאה לאחור.
הרשת
הגדרה 1השכבות
נניח שיש לנו [math]\displaystyle{ n }[/math] שכבות, וכל שכבה מכילה וקטור כניסה ווקטור יציאה בגדלים זהים. נסמן את גודל הווקטור של השכבה ה־[math]\displaystyle{ k }[/math] ב־[math]\displaystyle{ i_k }[/math]. את וקטור הכניסה נסמן [math]\displaystyle{ x^{k}\in\mathbb R^{i_k} }[/math], ואת הרכיב ה־[math]\displaystyle{ i }[/math] שלו נסמן [math]\displaystyle{ x^{k}_i }[/math]. את וקטור היציאה נסמן [math]\displaystyle{ y^{k}\in\mathbb R^{i_k} }[/math], ואת הרכיב ה־[math]\displaystyle{ i }[/math] שלו נסמן [math]\displaystyle{ y^{k}_i }[/math].
הגדרה 2פונקציית הסיגמואיד; הפלט של שכבה
לכל [math]\displaystyle{ k\ge2 }[/math] ולכל [math]\displaystyle{ 1\le i\le i_k }[/math] הפלט מוגדר להיות פונקציה של הקלט:
השכבה הראשונה יוצאת דופן: [math]\displaystyle{ x^{1} }[/math] הוא וקטור הקלט של רשת הנוירונים כולה, והפלט שלו שווה לקלט, [math]\displaystyle{ y^{1}=x^{1} }[/math]. הפלט של השכבה האחרונה, [math]\displaystyle{ y^{n} }[/math], הוא הפלט של הרשת כולה.
איור 1. רשת עם [math]\displaystyle{ n=3 }[/math] שכבות, [math]\displaystyle{ i_1=4 }[/math], [math]\displaystyle{ i_2=3 }[/math], [math]\displaystyle{ i_3=2 }[/math]. כל חבל הוא משקל [math]\displaystyle{ w^{k}_{ij} }[/math], מהרכיב [math]\displaystyle{ y^{k}_j }[/math] אל הרכיב [math]\displaystyle{ x^{k+1}_i }[/math]. החבלים שיוצאים מהאריח 1 שבתחתית השכבה ה־[math]\displaystyle{ k }[/math] הם ההטיות [math]\displaystyle{ b^{k}_i }[/math]: הטיה היא משקל של קלט שערכו תמיד 1. עובי החבל הוא [math]\displaystyle{ |w| }[/math]: חבל בהיר למשקל חיובי, וכהה לשלילי. המשקלים נבחרו באקראי ועוגלו לספרה אחת: [math]\displaystyle{ W^{1}=\left(\begin{smallmatrix}-0.6&0.4&0.4&0.8\\-0.8&-0.6&-0.8&-0.7\\0.6&-0.9&0.1&-0.7\end{smallmatrix}\right) }[/math], [math]\displaystyle{ b^{1}=(-0.5,-0.2,0.8) }[/math], [math]\displaystyle{ W^{2}=\left(\begin{smallmatrix}0.3&-1.2&-0.5\\-0.8&0.9&0.7\end{smallmatrix}\right) }[/math], [math]\displaystyle{ b^{2}=(0.7,0.8) }[/math].
השגיאה והעדכון
הגדרה 5פונקציית השגיאה
לכל קלט יהיה לנו פלט רצוי [math]\displaystyle{ d\in\mathbb R^{i_n} }[/math], ונגדיר את השגיאה עבור הקלט [math]\displaystyle{ x^{1} }[/math] להיות
בהינתן [math]\displaystyle{ x^{1} }[/math] ו־[math]\displaystyle{ d }[/math] קבועים, נרצה לבצע צעד בכיוון הירידה התלולה ביותר על פונקציית השגיאה, כדי לתקן את כל המשקלים.
הגדרה 6הגרדיאנטים
לכל [math]\displaystyle{ 1\le k\le n-1 }[/math] נגדיר את מטריצת הגרדיאנט [math]\displaystyle{ \nabla_{W^{k}}E\in\mathbb R^{i_{k+1}\times i_k} }[/math] על ידי
כאשר [math]\displaystyle{ \eta }[/math] הוא פרמטר המבטא את קצב השינוי.
הפצה לאחור
עבור [math]\displaystyle{ 1\le k\le n-1 }[/math], ובהינתן [math]\displaystyle{ i,j }[/math] כך ש־[math]\displaystyle{ 1\le i\le i_{k+1} }[/math] ו־[math]\displaystyle{ 1\le j\le i_k }[/math], אנחנו רוצים לחשב את [math]\displaystyle{ \frac{\partial E}{\partial w^{k}_{ij}} }[/math] ואת [math]\displaystyle{ \frac{\partial E}{\partial b^{k}_i} }[/math]. כלומר, את הנגזרת החלקית של פונקציית השגיאה לפי האיבר במקום [math]\displaystyle{ ij }[/math] במטריצת המשקלים [math]\displaystyle{ W^{k} }[/math], או לפי הרכיב ה־[math]\displaystyle{ i }[/math] של וקטור ההטיה [math]\displaystyle{ b^{k} }[/math]. המשפט הבא נותן את כולן ברקורסיה.
(א) לכל [math]\displaystyle{ 1\le i\le i_{k+1} }[/math] ולכל [math]\displaystyle{ 1\le j\le i_k }[/math] מתקיים [math]\displaystyle{ \frac{\partial E}{\partial w^{k}_{ij}}=\frac{\partial E}{\partial x^{k+1}_i}\cdot y^{k}_j }[/math], וכן [math]\displaystyle{ \frac{\partial E}{\partial b^{k}_i}=\frac{\partial E}{\partial x^{k+1}_i} }[/math];
(ב) לכל [math]\displaystyle{ 1\le i\le i_{k+1} }[/math] מתקיים [math]\displaystyle{ \frac{\partial E}{\partial x^{k+1}_i}=\frac{\partial E}{\partial y^{k+1}_i}\cdot y^{k+1}_i\,(1-y^{k+1}_i) }[/math];
(ג) לכל [math]\displaystyle{ 1\le i\le i_k }[/math] מתקיים [math]\displaystyle{ \frac{\partial E}{\partial y^{k}_i}=\sum_{q=1}^{i_{k+1}}\frac{\partial E}{\partial x^{k+1}_q}\cdot w^{k}_{qi} }[/math];
(ד) תנאי ההתחלה של הרקורסיה: לכל [math]\displaystyle{ 1\le i\le i_n }[/math] מתקיים [math]\displaystyle{ \frac{\partial E}{\partial y^{n}_i}=y^{n}_i-d_i }[/math].
במילים: בהינתן כל הנגזרות של פונקציית השגיאה ביחס לפלט של שכבה, אפשר לחשב את הנגזרות ביחס לפלט של השכבה הקודמת לה. כאמור, זו בדיוק הפצת השגיאה לאחור.
מסקנה 9
יהי [math]\displaystyle{ 1\le k\le n-1 }[/math]. אזי לכל [math]\displaystyle{ 1\le i\le i_{k+1} }[/math] ולכל [math]\displaystyle{ 1\le j\le i_k }[/math] מתקיים
לכל קלט [math]\displaystyle{ x^{1} }[/math] עם פלט רצוי [math]\displaystyle{ d }[/math]:
מעבר קדימה.[math]\displaystyle{ y^{1}=x^{1} }[/math]. לכל [math]\displaystyle{ k=1,\dots,n-1 }[/math] מחשבים [math]\displaystyle{ x^{k+1}=W^{k}y^{k}+b^{k} }[/math], ואת [math]\displaystyle{ y^{k+1}_i=\sigma(x^{k+1}_i) }[/math] לכל [math]\displaystyle{ i }[/math] (הגדרות 2 ו־4).
תנאי ההתחלה.[math]\displaystyle{ \frac{\partial E}{\partial y^{n}_i}=y^{n}_i-d_i }[/math] לכל [math]\displaystyle{ i }[/math] (משפט 8(ד)).
מעבר אחורה. לכל [math]\displaystyle{ k=n-1,n-2,\dots,1 }[/math]: מחשבים את [math]\displaystyle{ \frac{\partial E}{\partial x^{k+1}_i} }[/math] לפי (ב), את [math]\displaystyle{ \nabla_{W^{k}}E }[/math] ואת [math]\displaystyle{ \nabla_{b^{k}}E }[/math] לפי (א), ואת [math]\displaystyle{ \frac{\partial E}{\partial y^{k}_i} }[/math] לפי (ג), שמשמש בצעד הבא.
עדכון.[math]\displaystyle{ W^{k}\leftarrow W^{k}-\eta\,\nabla_{W^{k}}E }[/math] ו־[math]\displaystyle{ b^{k}\leftarrow b^{k}-\eta\,\nabla_{b^{k}}E }[/math] לכל [math]\displaystyle{ k }[/math] (שיטה 7).
שני האיורים הבאים מריצים את האלגוריתם על הרשת שבאיור 1, עם הקלט [math]\displaystyle{ x^{1}=(1,0,1,1) }[/math] והפלט הרצוי [math]\displaystyle{ d=(1,0) }[/math].
איור 2. מעבר קדימה. בכל נוירון כתוב הפלט שלו [math]\displaystyle{ y^{k}_i }[/math], והוא זוהר לפיו: [math]\displaystyle{ y^{2}=(0.52,\,0.08,\,0.69) }[/math] ו־[math]\displaystyle{ y^{3}=(0.60,\,0.72) }[/math]. הרשת טועה בשני הרכיבים, והשגיאה היא [math]\displaystyle{ E=\tfrac12\|y^{3}-d\|^{2}=0.336 }[/math]. החבלים שיוצאים מ־[math]\displaystyle{ y^{1}_2=0 }[/math] דהויים: הם אינם תורמים דבר ל־[math]\displaystyle{ x^{2} }[/math].איור 3. מעבר אחורה, בטורקיז. התגים שבין הפלט לפלט הרצוי הם תנאי ההתחלה [math]\displaystyle{ \partial E/\partial y^{3}_i=y^{3}_i-d_i }[/math] (משפט 8(ד)), כאן [math]\displaystyle{ -0.40 }[/math] ו־[math]\displaystyle{ +0.72 }[/math]. בכל נוירון כתוב [math]\displaystyle{ \partial E/\partial x^{k}_i }[/math]: בשכבה 3 לפי (ב), ובשכבה 2 לפי (ג) ואז (ב). למשל, לפי (ג), [math]\displaystyle{ \partial E/\partial y^{2}_1=-0.095\cdot0.3+0.145\cdot(-0.8)\approx-0.145 }[/math], ולכן לפי (ב) [math]\displaystyle{ \partial E/\partial x^{2}_1\approx-0.145\cdot0.52\cdot0.48\approx-0.036 }[/math]. עובי כל חבל הוא [math]\displaystyle{ |\partial E/\partial w^{k}_{ij}| }[/math] לפי (א), בהיר לחיובי וכהה לשלילי. החבלים שיוצאים מ־[math]\displaystyle{ y^{1}_2=0 }[/math] דקים ודהויים, כי הגרדיאנט שלהם הוא אפס בדיוק: [math]\displaystyle{ \partial E/\partial w^{1}_{i2}=(\partial E/\partial x^{2}_i)\cdot y^{1}_2=0 }[/math]. החבל העבה ביותר הוא ההטיה [math]\displaystyle{ b^{2}_2 }[/math], שהגרדיאנט שלה הוא [math]\displaystyle{ \partial E/\partial x^{3}_2=0.145 }[/math]. כל המספרים חושבו לפי המשפט ונבדקו מול הפרש סופי.
ובכן, היכן המשתנים [math]\displaystyle{ w^{k}_{ij} }[/math] ו־[math]\displaystyle{ b^{k}_i }[/math] מופיעים בנוסחת השגיאה? כיוון ש־[math]\displaystyle{ x^{k+1}=W^{k}y^{k}+b^{k} }[/math], הרכיב ה־[math]\displaystyle{ i }[/math] של וקטור הקלט של השכבה ה־[math]\displaystyle{ (k+1) }[/math] הוא
הנוסחה הראשונה היא הצבה של (ב) ב־(א), והשנייה היא הצבה של (ב) ב־(ג) של משפט 8, כפי שנעשה בהוכחתו.
הניסוי: ספרות כתובות ביד
▶ נסו בעצמכם: בדף הניסוי הרשת המאומנת רצה בדפדפן, על ספרה שאתם מציירים, ומראה גם את 64 הנוירונים החבויים. כל הפרטים, הקוד והחומרה מתועדים במסמך הניסוי.
הקוד מממש את הדף הזה כלשונו: [math]\displaystyle{ n=3 }[/math] שכבות עם סיגמואיד בכל שכבה [math]\displaystyle{ k\ge2 }[/math], גם בפלט (הגדרה 2), השגיאה [math]\displaystyle{ E=\frac12\|y^{n}-d\|^{2} }[/math] (הגדרה 5), הרקורסיה של משפט 8 בדיוק בסדר שבו היא מנוסחת, ועדכון של המשקלים אחרי כל קלט בנפרד (שיטה 7). הלמידה היא מעבר אחד על 60,000 ספרות האימון של MNIST (LeCun, Cortes & Burges; ברישיון CC BY-SA 3.0), בסדר שבו הן נתונות: בלי מיני־batch, בלי מומנטום, בלי softmax, בלי ערבוב ובלי מעברים חוזרים.
מה הדף משאיר פתוח, ומה בחרנו. הקלט [math]\displaystyle{ x^{1} }[/math] הוא 784 הבהירויות מחולקות ב־255, כך שהוא ב־[math]\displaystyle{ [0,1]^{784} }[/math]. הפלט הרצוי [math]\displaystyle{ d\in\mathbb R^{10} }[/math] הוא וקטור עם 1 במקום הספרה הנכונה ו־0 בשאר, והסיווג הוא לפי הרכיב הגדול ביותר של [math]\displaystyle{ y^{3} }[/math]. ההתחלה: רכיבי [math]\displaystyle{ W^{k} }[/math] אחידים ב־[math]\displaystyle{ [-r,r] }[/math] עם [math]\displaystyle{ r=1/\sqrt{i_k} }[/math], וההטיות אפס.
זמן. 7 שניות למעבר אחד על מעבד של מחשב נייד, ב־NumPy.
איור 4. הרשת לאורך המעבר היחיד: השגיאה הממוצעת [math]\displaystyle{ E }[/math] (ירוק, ציר שמאל) ודיוק הסיווג על תמונות הבדיקה (תכלת, ציר ימין). אחרי 1,000 קלטים הדיוק הוא 66.5%, אחרי 10,000 הוא 91.2%, אחרי 30,000 הוא 93.0%, ובסוף 95.24%. השגיאה הממוצעת יורדת מ־0.306 באלף הקלטים הראשונים ל־0.037 בעשרת האלפים האחרונים.
התוצאות. הרשת מסווגת נכון 95.24% מתמונות הבדיקה (476 טעויות מתוך 10,000), לעומת 95.34% מתמונות האימון. הספרה הקלה ביותר היא 1 (99.0%), והקשה ביותר היא 2 (92.2%).
[math]\displaystyle{ H=16 }[/math]
[math]\displaystyle{ H=64 }[/math]
[math]\displaystyle{ H=128 }[/math]
דיוק ([math]\displaystyle{ \eta=0.5 }[/math])
90.6%
95.2%
95.4%
[math]\displaystyle{ \eta=0.1 }[/math]
[math]\displaystyle{ \eta=0.5 }[/math]
[math]\displaystyle{ \eta=2 }[/math]
דיוק ([math]\displaystyle{ H=64 }[/math])
93.5%
95.2%
88.9%
[math]\displaystyle{ H }[/math] הוא מספר הנוירונים בשכבה החבויה. עם [math]\displaystyle{ \eta=0.1 }[/math] הרשת לומדת לאט יותר (38.7% אחרי 1,000 קלטים, לעומת 66.5%), ועם [math]\displaystyle{ \eta=2 }[/math] הצעדים גדולים מדי, מדלגים מעל המינימום, והדיוק נתקע.
איור 5. הייצוג שנלמד: 16 מתוך 64 השורות של המטריצה [math]\displaystyle{ W^{1} }[/math], כל אחת מסודרת בחזרה כתמונה [math]\displaystyle{ 28\times28 }[/math] (לבן חיובי, שחור שלילי). כל שורה היא "מבחן" שהרשת למדה להפעיל על התמונה. במקום הקשרים האקראיים של הפרספטרון, כאן המשקלים של השכבה הראשונה נקבעו על ידי ההפצה לאחור, ורואים בהם קווים וקשתות של ספרות.
מה נדרש כדי שהפשוט יעבוד
הדף אינו אומר מה הם המשקלים בתחילת הלמידה, ובאיזה קנה מידה נתון הקלט. שתי הבחירות האלה אינן שיפור של האלגוריתם, אבל בלעדיהן הוא אינו עובד:
משקלים התחלתיים אפס: הדיוק אחרי מעבר שלם הוא 30.8%. הסיבה היא סימטריה: כאשר כל השורות של [math]\displaystyle{ W^{1} }[/math] שוות, כל נוירוני השכבה החבויה מחשבים אותו [math]\displaystyle{ y^{2}_i }[/math], ולפי משפט 8 מקבלים אותו [math]\displaystyle{ \frac{\partial E}{\partial x^{2}_i} }[/math] ולכן אותו עדכון. הם נשארים זהים לנצח, והרשת כולה שקולה לרשת עם נוירון חבוי אחד. אתחול אקראי קטן שובר את השוויון, וזה כל תפקידו.
קלט בבהירויות 0 עד 255 במקום ב־[math]\displaystyle{ [0,1] }[/math]: הדיוק הוא 11.7%, כמו ניחוש. [math]\displaystyle{ x^{2}=W^{1}x^{1}+b^{1} }[/math] יוצא בגודל של מאות, הסיגמואיד רווי, [math]\displaystyle{ y^{2}_i }[/math] הוא כמעט בדיוק 0 או 1, והגורם [math]\displaystyle{ y^{2}_i(1-y^{2}_i) }[/math] שבמשפט 8(ב) מאפס את הגרדיאנט. הרשת אינה יכולה ללמוד, כי הנגזרת שהיא מחשבת היא אפס.
מה לא עשינו: מעברים חוזרים. כניסוי צד חזרנו על קבוצת האימון, באותו סדר, עוד ארבע פעמים: אחרי חמישה מעברים הדיוק הוא 96.39%, כלומר 1.1 נקודות יותר ממעבר אחד, בזמן גדול פי 5.
מה למדנו
הרקורסיה של משפט 8, מיושמת מילה במילה עם סיגמואיד בפלט ושגיאה ריבועית, במעבר אחד על הנתונים, מגיעה ל־95.24% על ספרות כתובות ביד. זה בערך 4 נקודות יותר מהפרספטרון עם 3,000 נוירונים אקראיים, עם 50,890 פרמטרים בלבד.
הרשת לומדת גם את הייצוג: השורות של [math]\displaystyle{ W^{1} }[/math] אינן אקראיות, אלא תבניות של ספרות.
שני דברים שהדף שותק עליהם הם הכרחיים: אתחול אקראי (בלעדיו 30.8%) וקלט בקנה מידה קטן (בלעדיו 11.7%). שניהם נובעים ישירות ממשפט 8, ולא מניסיון.
[math]\displaystyle{ \eta }[/math] הוא פשרה: קטן מדי ואיטי, גדול מדי ומדלג. [math]\displaystyle{ H }[/math] גדול יותר משפר מעט, ועולה הרבה בזמן.
העדכון אחרי כל קלט הוא הגרסה של 1986. המימוש המודרני מעבד קבוצות של קלטים בבת אחת, ומשתמש ב־softmax ובאנטרופיה צולבת בפלט. זה מהיר פי עשרות ונותן אחוז או שניים יותר, אבל המתמטיקה של ההפצה לאחור זהה.
ראו גם
פרספטרון: הרשת עם השכבה האקראית, שבה רק השכבה האחרונה נלמדת
