Backpropagation מאפס: קודם המנוע, אחר כך הרשת

לפני שבונים את המכונה, צריך לסגור שאלה אחת, כי אם התשובה הייתה הפוכה לא היה מה לבנות.

ה־perceptron נכשל ב־XOR כי קו אחד לא יכול להפריד בין ארבע הנקודות. התיקון המתבקש הוא לערום: להעביר את הקלט דרך שכבה ליניארית אחת, ואז דרך עוד אחת. זה עוזר?

לא, וההוכחה היא שתי שורות. שכבה ליניארית היא $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. הזינו אותה לאחרת, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, והציבו:

ההרכבה היא $W\mathbf{x} + \mathbf{b}$ עם $W = W_2W_1$ ו־$\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. ערימה של שכבות ליניאריות היא שכבה ליניארית אחת. עשר כאלה, אלף כאלה: עדיין קו אחד, עדיין לא מסוגל לעשות XOR.

שווה לראות את זה קורה במקום להאמין לזה:

import numpy as np
rng = np.random.default_rng(0)
W1, b1 = rng.normal(size=(3, 2)), rng.normal(size=3)
W2, b2 = rng.normal(size=(1, 3)), rng.normal(size=1)
x = rng.normal(size=2)

two_layers = W2 @ (W1 @ x + b1) + b2
one_layer  = (W2 @ W1) @ x + (W2 @ b1 + b2)
print(two_layers[0], one_layer[0], abs(two_layers[0] - one_layer[0]))

-4.612963371048  -4.612963371048  0.00e+00

לא שווים בקירוב. זהים ביט־לביט, כי זה אותו חשבון מסודר מחדש.

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

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

כלל השרשרת במשתנה יחיד אומר שאם $L$ תלוי ב־$c$ ו־$c$ תלוי ב־$x$, אז $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. נגזרות מוכפלות לאורך שרשרת.

החלק שחשוב כאן הוא מה קורה כשמשתנה מזין יותר מנתיב downstream אחד. אם $x$ משפיע על $L$ דרך $a$ וגם דרך $b$, התרומות מתווספות:

מכפילים לאורך נתיב, מסכמים בין נתיבים. זה כל ה־backpropagation, וכל פרט מימוש בשאר הפרק הזה — כולל ה־+= בקוד וקריאת zero_grad() שמפילה כל מי שכותב את לולאת האימון הראשונה שלו — הוא תוצאה ישירה של המילה השנייה הזאת.

קחו מעגל קונקרטי של חמש פעולות, עם $x = 0.5$ ו־$y = 1.4$:

שימו לב ש־$x$ מופיע שלוש פעמים: ב־$a$, ב־$b$, וישירות ב־$L$. עשו את מעבר ה־backward על הנייר, מימין לשמאל, החל מ־$\frac{dL}{dL} = 1$:

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

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

אז ניצור מספר שזוכר מה יצר אותו.

class Value:
    """A number that remembers where it came from."""

    def __init__(self, data, _children=(), _op=""):
        self.data = data
        self.grad = 0.0
        self._backward = lambda: None
        self._prev = set(_children)      
        self._op = _op

ארבעה שדות. data הוא הערך. grad צובר את $\frac{\partial L}{\partial \text{self}}$. _prev הוא קבוצת ה־Valueים שמהם הוא חושב — הקשתות של הגרף. ו־_backward היא closure שכל פעולה מתקינה: היא יודעת איך לדחוף את ה־gradient של הצומת הזה צעד אחד אחורה אל הקלטים שלו.

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

    def __add__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data + other.data, (self, other), "+")

        def _backward():
            self.grad += out.grad       
            other.grad += out.grad      

        out._backward = _backward
        return out

    def __mul__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data * other.data, (self, other), "*")

        def _backward():
            self.grad += other.data * out.grad   
            other.grad += self.data * out.grad   

        out._backward = _backward
        return out

    def tanh(self):
        t = math.tanh(self.data)
        out = Value(t, (self,), "tanh")

        def _backward():
            self.grad += (1 - t * t) * out.grad

        out._backward = _backward
        return out

    def relu(self):
        out = Value(self.data if self.data > 0 else 0.0, (self,), "relu")

        def _backward():
            self.grad += (1.0 if out.data > 0 else 0.0) * out.grad

        out._backward = _backward
        return out

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

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

ואז הדרייבר, שהוא החלק היחיד עם ידע גלובלי כלשהו:

    def backward(self):
        order, seen = [], set()

        def build(v):
            if v in seen:
                return
            seen.add(v)
            for child in v._prev:
                build(child)
            order.append(v)

        build(self)
        self.grad = 1.0
        for v in reversed(order):       
            v._backward()               

build מייצר סידור טופולוגי של הגרף: כל צומת מופיע אחרי כל הקלטים שלו. הליכה על הרשימה הזאת בסדר הפוך מבטיחה שכאשר קוראים ל־_backward של צומת, ה־gradient שלו עצמו כבר שלם — כל צרכן downstream כבר תרם. טעו בסדר ותדחפו אחורה gradient חצי־גמור, מה שמייצר תשובה שגויה בלי הודעת שגיאה.

x = Value(0.5)
y = Value(1.4)
a = x * y
b = x + y
c = a * b
d = c.tanh()
L = d + x
L.backward()
print(x.grad, y.grad)

forward:  a=0.7000  b=1.9000  c=1.3300  d=0.8692  L=1.3692
backward: dL/dd=1.0000  dL/dc=0.2444  dL/da=0.4644  dL/db=0.1711
          dL/dx=1.8212   dL/dy=0.4033

1.8212. אותו מספר, מתוכנית שסיפרו לה את הכלל של +, את הכלל של *, את הכלל של tanh, ושום דבר על המעגל הזה.

שתי בדיקות בלתי תלויות, כי ״זה תואם למה שגזרתי״ היא בדיקה חלשה כשהאותו אדם עשה את שני הדברים.

גזירה נומרית. מזיזים מעט את הקלט ומודדים. ההפרש הממורכז $\frac{L(x+h) - L(x-h)}{2h}$ מעריך את הנגזרת בלי שום חשבון דיפרנציאלי:

dL/dx:  analytic=1.821202805  numeric=1.821202805  |diff|=1.80e-10
dL/dy:  analytic=0.403269235  numeric=0.403269235  |diff|=7.64e-12

מול PyTorch, שיש לו מנוע autodiff תעשייתי שנכתב בידי אנשים שעושים את זה לפרנסתם:

torch dL/dx=1.821202805316   ours=1.821202805316   |diff|=2.22e-16
torch dL/dy=0.403269234753   ours=0.403269234753   |diff|=1.11e-16

התאמה ברמת $2 \times 10^{-16}$, שהיא machine epsilon עבור float של 64 ביט: שני המנועים מבצעים חשבון זהה. שמרו את הבדיקה הנומרית בכיס — זה הכלי לניפוי באגים במעבר ה־backward של שכבה חדשה, וזו הסיבה שבכלל אפשר למצוא gradient שגוי.

אותו מעגל, קלטים שונים. קבעו $x = 2$ ו־$y = -3$, מה שיוצר $c = 6$:

x=0.5, y=1.4:  dL/dc = 0.244400     three paths into x:  0.6501 + 0.1711 + 1.0000 = 1.8212
x=2.0, y=-3.0: dL/dc = 0.000025     three paths into x:  0.0001 + -0.0001 + 1.0000 = 0.9999

ה־gradient שחוצה את צומת $\tanh$ ירד בפקטור של 9,945. כל מה שנמצא upstream ממנו — ברשת אמיתית, כל שכבה שלפניו — מקבל כמעט כלום. שני הנתיבים דרך המעגל השתתקו; רק החיבור הישיר שעוקף את $\tanh$ עדיין נושא אות.

זו בעיית ה־vanishing gradient, בצומת אחד. ערמו ארבעים שכבות של $\tanh$ והכפילו ארבעים פקטורים כאלה יחד, והשכבות המוקדמות מפסיקות ללמוד לגמרי. זה גם, אגב, טיעון בעד skip connections שאפשר לראות כאן במיניאטורה: הנתיב שעקף את האי־ליניאריות הוא היחיד ששרד.

כל _backward משתמש ב־+=. זה נכון — כך נתיבים מסתכמים. אבל יש לזה תוצאה שתופסת את כולם: gradients מצטברים גם בין קריאות ל־backward(). למנוע אין מושג שהקריאה השנייה שלכם היא צעד אימון חדש ולא עוד נתיב באותו גרף.

לכן לולאת אימון חייבת לנקות אותם:

for step in range(steps):
    ys = [model(x) for x, _ in DATA]
    loss = sum((yp - yt) ** 2 for yp, (_, yt) in zip(ys, DATA))

    for p in model.parameters():   
        p.grad = 0.0

    loss.backward()
    for p in model.parameters():
        p.data -= lr * p.grad

זה optimizer.zero_grad() ב־PyTorch, והעצה הרגילה היא ששכחה שלו שוברת את האימון. אז נמחק את שתי השורות האלה ונראה עד כמה זה שבור. אותם seeds, אותו הכול, 200 צעדים של XOR:

ב־learning rates הקטנים, הגרסה הבאגית מנצחת בכל שורה. היא מתכנסת כשהגרסה הנכונה נתקעת.

זה לא מקרה, ושווה להבין את זה, כי זה מסביר למה הבאג הזה כל כך קשה לתפיסה. אם אף פעם לא מנקים את ה־gradient, אז בצעד $k$ הפרמטר מתעדכן לפי סכום כל gradient שחושב עד כה. ב־loss שממשיך להצביע פחות או יותר לאותו כיוון, הסכום הזה גדל בהתמדה, והאפקט הוא learning rate שעולה מעצמו. ב־$\eta = 0.05$, כשהאלגוריתם הנכון זוחל, גודל הצעד הבורח נראה בדיוק כמו תיקון.

ואז הסתכלו על שלוש השורות התחתונות. ב־$\eta = 0.3$ אותו מנגנון מפרק את המודל — loss 8.0 הוא הציון שמודל שקרס לקבוע $\pm 1$ מקבל — חצי מה־16 שארבע תשובות שגויות באופן מקסימלי היו עולות — — בזמן שהגרסה הנכונה מתכנסת עכשיו נקי.

אז ההצהרה הכנה אינה ״תמיד קראו ל־zero_grad או שהמודל שלכם לא יתאמן״. היא: בלעדיו אתם כבר לא מריצים gradient descent. אתם מריצים משהו שגודל הצעד שלו נסחף כלפי מעלה בקצב שאף אחד לא בחר, והוא ייראה כאילו הוא עובד, לפעמים טוב יותר מהדבר האמיתי, ממש עד שהוא לא — ואז תאשימו את ה־learning rate, את האתחול או את הנתונים. זו הצורה של הבאגים הגרועים ביותר ב־machine learning: הם לא קורסים, הם משנים את האלגוריתם לאלגוריתם אחר שמדי פעם משיג ציון טוב יותר.

כשהמנוע מוכן, רשת נוירונים היא כמעט בלי קוד. נוירון הוא מכפלה פנימית, bias ו־activation; שכבה היא רשימה של נוירונים; רשת היא רשימה של שכבות.

class Neuron:
    def __init__(self, nin):
        self.w = [Value(random.uniform(-1, 1)) for _ in range(nin)]
        self.b = Value(0.0)

    def __call__(self, x):
        act = sum((wi * xi for wi, xi in zip(self.w, x)), self.b)
        return act.tanh()

    def parameters(self):
        return self.w + [self.b]


class Layer:
    def __init__(self, nin, nout):
        self.neurons = [Neuron(nin) for _ in range(nout)]

    def __call__(self, x):
        out = [n(x) for n in self.neurons]
        return out[0] if len(out) == 1 else out

    def parameters(self):
        return [p for n in self.neurons for p in n.parameters()]


class MLP:
    def __init__(self, nin, nouts):
        sizes = [nin] + nouts
        self.layers = [Layer(sizes[i], sizes[i + 1]) for i in range(len(nouts))]

    def __call__(self, x):
        for layer in self.layers:
            x = layer(x)
        return x

    def parameters(self):
        return [p for layer in self.layers for p in layer.parameters()]

אין backward pass בכל זה. אפילו לא שורה אחת. מחלקת Value כבר יודעת איך לגזור כל דבר שהמחלקות האלה במקרה בונות, וזו הנקודה של לכתוב אותה קודם: מנוע autodiff לא יודע שמשתמשים בו לרשת נוירונים.

עכשיו הבעיה מפרק 1. שני קלטים, שתי יחידות חבויות, פלט אחד, תשעה פרמטרים:

step   1: loss 4.156690
step  10: loss 4.005572
step  50: loss 3.996708
step 100: loss 3.510700
step 200: loss 0.038597

[0, 0] -> -0.9081  (target -1)  ok
[0, 1] -> +0.8934  (target +1)  ok
[1, 0] -> +0.8906  (target +1)  ok
[1, 1] -> -0.9207  (target -1)  ok

ארבע מתוך ארבע. הפונקציה שאף perceptron לא יכול לחשב — כפי שהוכחנו בפרק 1 באמצעות ארבעה אי־שוויונים שדרשו ש־$b$ יהיה גם חיובי וגם שלילי — מחושבת באמצעות תשעה מספרים שנמצאו אוטומטית.

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

אחרי אימון ל־loss של 0.001241, הנה המקום שאליו כל קלט נוחת אחרי השכבה החבויה, ומה נוירון הפלט עושה איתו:

הסתכלו על השורה הראשונה והרביעית. הקלטים $(0,0)$ ו־$(1,1)$ הם פינות נגדיות באלכסון של הריבוע — רחוקים זה מזה ככל ששתי נקודות בבעיה הזו יכולות להיות — והשכבה החבויה ממפה אותם אל $(0.82, -0.85)$ ו־$(0.84, -0.86)$. כמעט אותה נקודה. השכבה קיפלה את המישור כך ששתי הפינות הדחויות נוחתות זו על זו, וברגע שהן באותו מקום, קו אחד מפריד בינן לבין השתיים האחרות.

ונוירון הפלט הוא בדיוק הקו הזה. הפרמטרים שנלמדו הם $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, ולכן גבול ההחלטה שלו הוא

שהוא קו ישר — perceptron, אותו אובייקט מפרק 1, ללא שינוי. הוא לא יכול היה לפתור XOR אז והוא לא יכול עכשיו. מה שהשתנה הוא שהוא כבר לא מסתכל על הקלט; הוא מסתכל על מרחב שהשכבה הראשונה בנתה עבורו, שבו הבעיה ניתנת להפרדה ליניארית.

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

יש כאן משפט, ובדרך כלל מצטטים אותו רע.

Cybenko ב־1989 ו־Hornik ב־1991 הוכיחו שרשת feedforward עם שכבה חבויה יחידה ופונקציית activation מתאימה יכולה לקרב כל פונקציה רציפה על קבוצה קומפקטית, לכל דיוק שתרצו, בהינתן מספיק יחידות חבויות.³⁴ זו תוצאה אמיתית וחשובה: היא אומרת שהארכיטקטורה אינה המגבלה.

עכשיו קראו מה הוא משמיט. הוא לא אומר כמה יחידות — החסם יכול להיות אסטרונומי. הוא לא אומר שאפשר למצוא את המשקלים; הוא טוען לקיום, ו־gradient descent מנקודת התחלה אקראית אינו אורקל. והוא לא אומר כלום על התנהגות על נתונים שלא ראיתם, שזה החצי השני של פרק 6.

הפער בין ״קיים״ ל־״ניתן למציאה״ אינו אקדמי. הנה אותה בעיית XOR, 50 אתחולים אקראיים לכל מצב, 1000 צעדים, כשרק גודל השכבה החבויה השתנה:

עם הארכיטקטורה המינימלית שעובדת, ריצה אחת מתוך ארבע אף פעם לא מגיעה לשם — היא מתייצבת בתצורה שהיא לא יכולה לרדת ממנה, בדיוק המינימום המקומי שפרק 3 הראה על משטח חד־ממדי. הוסיפו יחידה אחת והכישלונות כמעט נעלמים, לא כי הרשת נעשתה יותר אקספרסיבית (שתי יחידות כבר מספיקות — 38 ריצות מוכיחות זאת) אלא כי ממדים נוספים נותנים לירידה עוד כיוונים לברוח דרכם.

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

זה אותו לקח כמו משפט ההתכנסות בפרק 1, וזה יהיה אותו לקח בפרק 10 על חוקי scaling, בצורה שהפרק ההוא נותן לו: תחזית של ה־loss אינה תחזית של היכולת שעליה אתם משלמים, והמרחק בין השתיים הוא המקום שבו ההנדסה חיה.

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

הריצו את אותו קוד על dataset אמיתי ומופיעה מערכת חדשה של בעיות, שאף אחת מהן אינה קשורה ל־gradients. ה־loss יורד לזמן מה ואז נעצר. או שהוא יורד על נתוני האימון ועולה על כל השאר. או שהוא לא זז בכלל מהצעד הראשון, והסיבה מתגלה כטווח המשקלים האקראיים הראשוניים. או שהקלט של יחידה אחת נסחף לשלילי בכל דוגמה באפוק השלישי ומאז היא מתה, בשקט, ולוקחת איתה חתיכה מהקיבולת של המודל.

אלה לא כשלים אקזוטיים; הם המצב הרגיל של רשת שזה עתה נכתבה, ואף אחד מהם לא מכריז על עצמו. ה־gradient נכון — בדקתם אותו מול PyTorch עד שש־עשרה ספרות אחרי הנקודה — והמודל עדיין לא לומד.

פרק 6 עוסק בזה: אתחול, נרמול, overfitting ו־regularisation, והרגל האבחון של לשאול איזה מהם קורה לפני שמשנים משהו. זה ההבדל בין רשת שרצה לבין רשת שעובדת.

מחלקת Value בפרק הזה היא צאצאית ישירה של micrograd של Andrej Karpathy, והווידאו שלו The spelled-out intro to neural networks and backpropagation: building micrograd הוא שלוש השעות הטובות ביותר שתוכלו להשקיע בחומר הזה אם תרצו הסבר שני ממישהו אחר. הפוסט שלו מ־2016, Yes you should understand backprop, מציג את הטיעון בעד כתיבת אחד כזה בעצמכם והוא קריאת חובה ב־CS224n של Stanford. ההערות של CS231n על backpropagation (cs231n.github.io/optimization-2) הן הטיפול הקאנוני בדפוסי הזרימה שהוצגו בטבלה למעלה. למתמטיקה כחשבון דיפרנציאלי על גרף ולא כפולקלור של רשתות נוירונים, פרק 5.6 ב־Mathematics for Machine Learning מאת Deisenroth, Faisal ו־Ong ברור במיוחד; והסקירה של Baydin, Pearlmutter, Radul ו־Siskind, Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767), היא הרפרנס לתחום כולו, כולל פשרת forward/reverse שנדונה למעלה.