Κατηφόρα: Gradient Descent και τα δύο βήματα που όλοι παραλείπουν

Ξαναδιατυπωμένο ώστε αυτό το κεφάλαιο να στέκεται μόνο του: τα οκτώ εξαρτήματα από τον ιμάντα μεταφοράς του Κεφαλαίου 1, αλλά με διαφορετική ερώτηση. Όχι αποδοχή ή απόρριψη — αυτό επιστρέφει αργότερα — αλλά πρόβλεψη του βάρους ενός εξαρτήματος από το πλάτος του.

import numpy as np

WIDTH  = np.array([18.0, 19.5, 20.2, 21.0, 24.0, 25.5, 23.0, 26.0])
WEIGHT = np.array([47.0, 52.0, 49.0, 55.0, 61.0, 66.0, 70.0, 58.0])

x = WIDTH  - WIDTH.mean()      # 22.15 mm
y = WEIGHT - WEIGHT.mean()     # 57.25 g

Οι μετρήσεις είναι κεντραρισμένες, ακριβώς όπως στο Κεφάλαιο 1 και για έναν λόγο που θα επιστρέψει με τόκο πριν τελειώσει αυτό το κεφάλαιο. Το μοντέλο είναι μια ευθεία, $\hat{y} = a x + b$, και η απώλεια είναι το μέσο τετραγωνικό σφάλμα που παρήγαγε το προηγούμενο κεφάλαιο:

Δύο παράμετροι. Γιατί να μην δοκιμάσουμε απλώς πολλές τιμές; Ας το κάνουμε στ’ αλήθεια — ένα πλέγμα από $a = 0$ έως $5$ και από $b = -5$ έως $5$, με βήμα $0.01$:

grid 501 x 1001 = 501,501 evaluations in 3.67 s
  best found: a = 2.1000, b = -0.0000, L = 24.592450

Μισό εκατομμύριο αξιολογήσεις για να καρφώσουμε δύο αριθμούς στα δύο δεκαδικά ψηφία — και αυτό το δευτερόλεπτο είναι χρόνος τοίχου σε ένα μηχάνημα, άρα μια επανάληψη μπορεί να πέσει οπουδήποτε από τρία έως έξι· το πλήθος αξιολογήσεων και το ελάχιστο είναι το κομμάτι που αναπαράγεται. Το gradient descent, στο τέλος αυτού του κεφαλαίου, βρίσκει τέσσερα δεκαδικά ψηφία σε οκτώ βήματα και την πλήρη float64 απάντηση σε τριάντα έξι.

Αλλά η ταχύτητα δεν είναι το επιχείρημα, και αυτό είναι το σημείο που κρίνει όλο το μάθημα. Η αναζήτηση σε πλέγμα κοστίζει $k^P$ αξιολογήσεις για $P$ παραμέτρους με $k$ τιμές η καθεμία. Με χίλιες τιμές ανά άξονα:

Η τρίτη σειρά δεν είναι μεγάλος αριθμός, είναι χωρίς νόημα — υπάρχουν περίπου $10^{80}$ άτομα στο παρατηρήσιμο σύμπαν. Η αναζήτηση δεν γίνεται απλώς πιο αργή όσο μεγαλώνουν τα μοντέλα· παύει να υπάρχει. Όλα όσα ακολουθούν υπάρχουν εξαιτίας αυτού του πίνακα.

Κρατήστε το $b = 0$ σταθερό για μια στιγμή, ώστε να υπάρχει μία παράμετρος και μία καμπύλη, δηλαδή η εικόνα με την οποία σας άφησε το προηγούμενο κεφάλαιο. Πάρτε ένα σημείο πάνω της, $a = 1$, και ρωτήστε: αν μετακινήσω ελαφρά το $a$ κατά μια μικρή ποσότητα $h$, πόσο μετακινείται η απώλεια ανά μονάδα μετακίνησης;

Αυτός ο λόγος είναι άνοδος προς οριζόντια μετατόπιση — η κλίση της ευθείας που περνά από δύο σημεία της καμπύλης. Καθώς το $h$ μικραίνει, τα δύο σημεία γλιστρούν το ένα προς το άλλο και η ευθεία γίνεται εφαπτομένη. Η κλίση της είναι η παράγωγος $L'(a)$: ο ρυθμός με τον οποίο αλλάζει η απώλεια ανά μονάδα αλλαγής στο $a$. Δεν είναι προσέγγιση κάποιου πράγματος και δεν είναι μια απειροελάχιστη ποσότητα. Είναι όριο συνηθισμένων λόγων.

Αξίζει να το τρέξουμε, γιατί οι αριθμοί λένε κάτι που ο ορισμός δεν λέει:

def loss1(a):
    return np.mean((a * x - y) ** 2)

for h in [1.0, 1e-2, 1e-4, 1e-6, 1e-8, 1e-10, 1e-12, 1e-14]:
    q = (loss1(1.0 + h) - loss1(1.0)) / h
    print(f"h = {h:<8.0e}   slope estimate = {q:.10f}   error = {abs(q + 16.385):.3e}")

h = 1e+00      slope estimate = -8.9400000000    error = 7.445e+00
h = 1e-02      slope estimate = -16.3105500000   error = 7.445e-02
h = 1e-04      slope estimate = -16.3842555001   error = 7.445e-04
h = 1e-06      slope estimate = -16.3849925556   error = 7.444e-06
h = 1e-08      slope estimate = -16.3850003787   error = 3.787e-07
h = 1e-10      slope estimate = -16.3850444324   error = 4.443e-05
h = 1e-12      slope estimate = -16.3851154866   error = 1.155e-04
h = 1e-14      slope estimate = -17.0530256582   error = 6.680e-01

Δύο πράγματα συμβαίνουν εδώ και και τα δύο στηρίζουν όλο το βάρος.

Το σφάλμα δεν είναι αόριστα ανάλογο του $h$ — είναι ακριβώς $7.445\,h$. Διαιρέστε το $h$ με εκατό, και το σφάλμα διαιρείται με εκατό, κάθε φορά στα τέσσερα σημαντικά ψηφία. Αυτή η σταθερά δεν είναι διακόσμηση: είναι το μισό της δεύτερης παραγώγου της απώλειας και είναι η πρώτη εμφάνιση μιας ιδέας που θα έρθει σε δύο ενότητες — ότι μια καμπύλη κοντά σε ένα σημείο μοιάζει με ευθεία συν μια διόρθωση ανάλογη του $h^2$.

Και μετά το μοτίβο σπάει. Κάτω από $h = 10^{-8}$ η εκτίμηση γίνεται χειρότερη, και στο $10^{-14}$ είναι λάθος στο δεύτερο ψηφίο. Δεν συνέβη τίποτα μαθηματικό· συνέβη το κουτί κινητής υποδιαστολής του προηγούμενου κεφαλαίου. Τα $L(a+h)$ και $L(a)$ συμφωνούν στα πρώτα δέκα ψηφία τους, η αφαίρεσή τους καταστρέφει αυτά τα ψηφία, και η διαίρεση των υπολειμμάτων με έναν μικροσκοπικό αριθμό μεγεθύνει ό,τι έμεινε. Υπάρχει ένα καλύτερο $h$ — εδώ γύρω στο $10^{-8}$, περίπου η τετραγωνική ρίζα του machine epsilon — και το να πάτε μικρότερα δεν είναι πιο προσεκτικό, είναι λιγότερο. Θυμηθείτε το· μια συνάρτηση στο τέλος αυτού του κεφαλαίου εξαρτάται από αυτό.

Η ακριβής κλίση, από λογισμό αντί για μέτρηση, είναι $-16.385$. Άρα μπορούμε να σταματήσουμε να μετράμε και να αρχίσουμε να παράγουμε.

Εδώ είναι η ιδέα πάνω στην οποία χτίζεται το υπόλοιπο μάθημα, ειπωμένη μία φορά, καθαρά.

Το να συνθέσετε δύο συναρτήσεις σημαίνει να τροφοδοτήσετε τη μία μέσα στην άλλη: $(f \circ g)(x) = f(g(x))$. Τίποτα περισσότερο.

Ένα βαθύ δίκτυο δεν είναι σαν σύνθεση. Είναι σύνθεση. Ένα επίπεδο είναι συνάρτηση· το στοίβαγμα επιπέδων είναι σύνθεση συναρτήσεων· το «βάθος» είναι ο αριθμός των συναρτήσεων στην αλυσίδα. Όταν το Κεφάλαιο 5 χτίζει ένα δίκτυο, χτίζει $f_4 \circ f_3 \circ f_2 \circ f_1$ και τίποτα άλλο. Αυτό σημαίνει ότι ο μοναδικός πιο σημαντικός κανόνας του λογισμού, για τους σκοπούς μας, είναι εκείνος που παραγωγίζει μια σύνθεση:

Οι ρυθμοί πολλαπλασιάζονται. Αν το $g$ αλλάζει τρεις φορές πιο γρήγορα από το $x$, και το $f$ αλλάζει δύο φορές πιο γρήγορα από το $g$, τότε το $f$ αλλάζει έξι φορές πιο γρήγορα από το $x$. Αυτό είναι όλο το περιεχόμενο, και είναι ο λόγος που ένα σήμα που περνά προς τα πίσω μέσα από δέκα επίπεδα πολλαπλασιάζεται με δέκα αριθμούς — γι’ αυτό το Κεφάλαιο 6 αφιερώνει μια ενότητα στο τι συμβαίνει όταν όλοι αυτοί οι αριθμοί είναι λίγο μικρότεροι από ένα.

Χρησιμοποιήστε το στην απώλειά μας. Γράψτε το υπόλοιπο $r_i = a x_i + b - y_i$, ώστε $L = \frac{1}{n}\sum r_i^2$. Κάθε $r_i$ εξαρτάται από το $a$ μέσω της εσωτερικής συνάρτησης $a x_i$, της οποίας η παράγωγος είναι $x_i$. Κανόνας αλυσίδας, όρο προς όρο:

Αυτά τα καλλιγραφικά σύμβολα $\partial$ δηλώνουν μια μερική παράγωγο: παραγωγίζετε ως προς μία μεταβλητή και αντιμετωπίζετε κάθε άλλη ως σταθερά. Δεν συμβαίνει κάτι νέο — είναι το ίδιο όριο όπως πριν, παρμένο κατά μήκος ενός άξονα. Συλλέξτε τις μερικές παραγώγους σε ένα διάνυσμα και έχετε το gradient:

Στο σημείο $(a, b) = (1, 4)$ αυτό το διάνυσμα είναι $(-16.385,\ 8.0)$. Δύο αριθμοί. Το ερώτημα είναι τι σημαίνουν, και αυτό είναι το πρώτο βήμα που όλοι παραλείπουν.

Το gradient είναι ένα διάνυσμα κλίσεων κατά μήκος των αξόνων. Αυτό είναι όλο που έχουμε αποδείξει. Δεν είναι προφανές — δεν πρέπει να είναι προφανές — ότι η συναρμολόγησή τους σε ένα διάνυσμα παράγει κάτι που δείχνει προς κάποια συγκεκριμένη κατεύθυνση.

Ορίστε λοιπόν αυτό που πραγματικά θέλουμε. Διαλέξτε ένα μοναδιαίο διάνυσμα $\mathbf{u}$, μια κατεύθυνση. Η κατευθυντική παράγωγος είναι ο ρυθμός με τον οποίο αλλάζει η απώλεια καθώς περπατάτε προς τα εκεί:

Ο κανόνας της αλυσίδας το μετατρέπει σε κάτι υπολογίσιμο. Περπατώντας κατά μήκος του $\mathbf{u}$, το $a$ αλλάζει με ρυθμό $u_1$ και το $b$ με ρυθμό $u_2$, και οι συνεισφορές αθροίζονται:

Ο ρυθμός μεταβολής σε οποιαδήποτε κατεύθυνση είναι το εσωτερικό γινόμενο του gradient με αυτή την κατεύθυνση. Και τώρα η κορύφωση, που είναι μία γραμμή γεωμετρίας. Γράφοντας το εσωτερικό γινόμενο με τη γωνία $\phi$ ανάμεσα στα διανύσματα,

αφού το $\mathbf{u}$ έχει μήκος 1. Το μόνο πράγμα που ελέγχετε είναι το $\cos\phi$, το οποίο είναι μέγιστο στο $\phi = 0$ και ελάχιστο σε μισή στροφή, $\phi = 180$ μοίρες. Άρα:

• Η πιο απότομη άνοδος είναι κατά μήκος του ίδιου του $\nabla L$, και η κλίση εκεί είναι ακριβώς $\lVert \nabla L \rVert$.
• Η πιο απότομη κάθοδος είναι κατά μήκος του $-\nabla L$, και η κλίση εκεί είναι $-\lVert \nabla L \rVert$.
• Κάθετα στο gradient, η απώλεια δεν αλλάζει καθόλου. Γι’ αυτό οι γραμμές ενός χάρτη ισοϋψών τέμνουν το gradient σε ορθές γωνίες.

Αυτό είναι το σύμβολο μείον. Όχι σύμβαση, όχι αντιστροφή πρόσημου που διάλεξε κάποιος: η κατεύθυνση της ταχύτερης μείωσης είναι το αρνητικό gradient επειδή το $\cos\phi$ ελαχιστοποιείται στη μισή στροφή, και για κανέναν άλλο λόγο.

Αφού αυτό είναι ισχυρισμός για όλες τις κατευθύνσεις, δοκιμάστε τον σε όλες τις κατευθύνσεις. Δειγματοληπτήστε 3.600 από αυτές, μία ανά δέκατο της μοίρας, και μετρήστε καθεμία με μια μικρή μετατόπιση:

theta = np.array([1.0, 4.0])
g = grad(theta)
print("gradient      ", g)
print("its length    ", np.linalg.norm(g))
print("its angle     ", np.degrees(np.arctan2(g[1], g[0])) % 360, "degrees")

best = max(
    ((loss(theta + 1e-6 * u) - loss(theta - 1e-6 * u)) / 2e-6, np.degrees(ang))
    for ang, u in (
        (a, np.array([np.cos(a), np.sin(a)])) for a in np.arange(3600) * 2 * np.pi / 3600
    )
)
print("steepest slope", best[0], "at", best[1], "degrees")

gradient       [-16.385   8.   ]
its length     18.23371122399386
its angle      153.97598928042032 degrees
steepest slope 18.233709624837502 at 154.0 degrees

Μια αναζήτηση που δεν ξέρει τίποτα για gradients, σε 3.600 κατευθύνσεις, βρίσκει την πιο απότομη άνοδο στις 154,0 μοίρες — την ίδια την κατεύθυνση του gradient, μέσα στην ανάλυση 0,1 μοίρας της αναζήτησης. Και η κλίση που βρίσκει εκεί, 18,2337, είναι το μήκος του gradient στα έξι ψηφία. Το θεώρημα δεν είναι μια ιστορία για το τι σημαίνουν τα gradients· είναι ένα μετρήσιμο γεγονός, και αυτή είναι η μέτρηση.

Τώρα το δεύτερο βήμα που παραλείπεται. Ξέρουμε προς τα πού είναι η κατηφόρα. Δεν συνεπάγεται ότι το να περπατήσουμε προς τα εκεί μειώνει την απώλεια, επειδή η «κατηφόρα» είναι δήλωση για μια απειροελάχιστη μετατόπιση και ένα βήμα δεν είναι απειροελάχιστο.

Η γέφυρα είναι η γραμμικοποίηση. Κοντά σε ένα σημείο, μια ομαλή συνάρτηση είναι η εφαπτομένη της συν μια διόρθωση:

Αυτό είναι το ανάπτυγμα Taylor πρώτης τάξης. Το απορριπτόμενο $O(\lVert\boldsymbol{\delta}\rVert^2)$ είναι η καμπυλότητα — ο ίδιος όρος που έκανε την εκτίμηση του πίνακα κλίσεων λανθασμένη κατά ακριβώς $7.445\,h$. Βάλτε μέσα το βήμα που σκοπεύουμε να κάνουμε, $\boldsymbol{\delta} = -\eta \nabla L$:

Η απώλεια πέφτει κατά $\eta \lVert \nabla L \rVert^2$. Κάθε μέρος αυτού είναι μη αρνητικό, άρα η υπόσχεση είναι πραγματική — για αρκετά μικρό $\eta$, επειδή ο παραλειπόμενος όρος μεγαλώνει σαν $\eta^2$ και τελικά την καταπίνει. Αυτή είναι όλη η θεωρία. Εδώ είναι η υπόσχεση να τηρείται και μετά να σπάει:

eta = 0.2       promised    66.49364500   delivered   -16.01619240   ratio -0.240868
eta = 0.1       promised    33.24682250   delivered    12.61936315   ratio  0.379566
eta = 0.01      promised     3.32468225   delivered     3.11840766   ratio  0.937957
eta = 0.001     promised     0.33246822   delivered     0.33040548   ratio  0.993796
eta = 0.0001    promised     0.03324682   delivered     0.03322620   ratio  0.999380
eta = 1e-05     promised     0.00332468   delivered     0.00332448   ratio  0.999938

Διαβάστε το από κάτω. Καθώς το $\eta$ μικραίνει, η πραγματική πτώση συγκλίνει στην υποσχεμένη — λόγος 0,99938, μετά 0,99994 — δηλαδή το θεώρημα Taylor είναι σωστό. Διαβάστε το από πάνω και στο $\eta = 0.2$ η πραγματική «πτώση» είναι αρνητικό δεκαέξι. Το βήμα πήγε προς την κατηφόρα και η απώλεια ανέβηκε.

Άρα ο κανόνας ενημέρωσης είναι

και συνοδεύεται από μια συνθήκη που κανείς δεν δηλώνει: ότι το $\eta$ είναι αρκετά μικρό. Αρκετά μικρό σε σχέση με τι, ακριβώς, είναι η επόμενη ενότητα.

Ξεκινήστε με την απλούστερη κοιλάδα που υπάρχει, $f(x) = x^2$, όπου $f'(x) = 2x$. Ένα βήμα gradient descent είναι

Η θέση πολλαπλασιάζεται με $(1 - 2\eta)$ σε κάθε βήμα. Αυτό είναι γεωμετρική ακολουθία, και οι γεωμετρικές ακολουθίες έχουν ακριβώς έναν κανόνα: μικραίνουν όταν ο πολλαπλασιαστής είναι μικρότερος από 1 σε απόλυτη τιμή και μεγαλώνουν αλλιώς. Άρα $\lvert 1 - 2\eta \rvert < 1$, δηλαδή $0 < \eta < 1$.

Το όριο είναι ακριβώς στο $\eta = 1$. Όχι «γύρω στο 1», όχι «το 1 είναι συνήθως πολύ μεγάλο». Στο $\eta = 1$ ο πολλαπλασιαστής είναι $-1$ και το σημείο αναπηδά για πάντα μεταξύ $x$ και $-x$, χωρίς ούτε να πλησιάζει ούτε να ξεφεύγει. Κάτω από αυτό, συγκλίνει· πάνω από αυτό, αποκλίνει. Το διάστημα χωρίζεται ξανά στο $\eta = 0.5$, όπου ο πολλαπλασιαστής αλλάζει πρόσημο: κάτω από εκεί η προσέγγιση είναι μονότονη, πάνω από εκεί το σημείο υπερπηδά και εναλλάσσει πλευρές, και ακριβώς στο $0.5$ ο πολλαπλασιαστής είναι 0 και ένα μόνο βήμα προσγειώνεται στο ελάχιστο.

Τέσσερα καθεστώτα, από τέσσερις γραμμές άλγεβρας. Πηγαίνετε να περάσετε τα όρια μόνοι σας:

Και τώρα το ενδιαφέρον:

Τώρα ο γενικός κανόνας, που βγαίνει από το ίδιο επιχείρημα. Ο πολλαπλασιαστής $1 - 2\eta$ ήταν στην πραγματικότητα $1 - \eta f''$, και κοντά σε ένα ελάχιστο μια απώλεια πολλών παραμέτρων έχει έναν τέτοιο αριθμό ανά κατεύθυνση — τις ιδιοτιμές του πίνακα δεύτερων παραγώγων. Κάθε κατεύθυνση πρέπει να είναι σταθερή ταυτόχρονα, άρα η οροφή ορίζεται από τη μεγαλύτερη:

Για $f(x) = x^2$, $f'' = 2$, οροφή 1, που είναι αυτό που μόλις παράξαμε. Για τον ιμάντα μας, ο πίνακας δεύτερων παραγώγων είναι $\frac{2}{n} A^{\top} A$ με $A$ τον δίστηλο πίνακα εισόδων, και οι ιδιοτιμές του είναι 2 και 14,89, άρα η οροφή είναι $2 / 14.89 = 0.13432$. Αυτό είναι μια πρόβλεψη με πέντε σημαντικά ψηφία. Δοκιμάστε την:

lr=0.1343    -> L =      24.5924
lr=0.13431   -> L =      24.5924
lr=0.13432   -> L =       4707.8       BLEW UP
lr=0.13433   -> L =  4.00452e+16       BLEW UP
lr=0.1344    -> L = 1.18229e+107       BLEW UP

Πέντε δεκαδικά ψηφία συμφωνίας ανάμεσα σε μια γραμμή γραμμικής άλγεβρας και εκατό χιλιάδες επαναλήψεις ενός βρόχου for.

Και εδώ επιστρέφει το Κεφάλαιο 1. Όλα τα παραπάνω χρησιμοποίησαν τις κεντραρισμένες μετρήσεις. Τρέξτε τον ίδιο ακριβώς κώδικα στα ωμά χιλιοστά και γραμμάρια και οι ιδιοτιμές είναι 0,0298 και 998,1 αντί για 2 και 14,89. Η οροφή καταρρέει από 0,134 σε 0,002004 — εξίσου ακριβώς, συγκλίνοντας στο lr=0.002003 και εκρήγνυται στο lr=0.002004.

Χειρότερος από την οροφή είναι ο λόγος ανάμεσα στις ιδιοτιμές. Ο αριθμός κατάστασης μετρά πόσο μακριά από στρογγυλή είναι η κοιλάδα: μια μακριά, λεπτή τάφρος επιβάλλει έναν ρυθμό αρκετά μικρό για τα απότομα τοιχώματα, και μετά ο πυθμένας της τάφρου περπατιέται με το ίδιο σύρσιμο. Ο δικός μας πηγαίνει από 7,44 κεντραρισμένος σε 33.452 ωμός. Με τον καλύτερο ρυθμό που μπορεί να πάρει κάθε εκδοχή:

Ίδια δεδομένα, ίδιος κώδικας, ίδια απάντηση στο τέλος — και οκτώ χιλιάδες φορές περισσότερη δουλειά, επειδή κανείς δεν αφαίρεσε έναν μέσο όρο. Στο Κεφάλαιο 1 η ίδια παράλειψη κόστισε στον perceptron έναν παράγοντα έξι χιλιάδων σε εποχές, και η διάγνωση εκεί ήταν γεωμετρική: τα δεδομένα αιωρούνταν μακριά από την αρχή. Είναι η ίδια γεωμετρία εδώ με κοστούμι βελτιστοποίησης, και γι’ αυτό η κανονικοποίηση εισόδων δεν είναι συμβουλή υγιεινής αλλά αριθμητική.¹

Τίποτα από τα παραπάνω δεν χρειάστηκε βιβλιοθήκη. Εδώ είναι ολόκληρος ο optimiser.

def loss(theta):
    a, b = theta
    return np.mean((a * x + b - y) ** 2)


def grad(theta):
    a, b = theta
    residual = a * x + b - y
    return np.array([np.mean(2 * residual * x), np.mean(2 * residual)])


def descend(theta, lr, steps):
    theta = np.array(theta, dtype=float)
    for _ in range(steps):
        theta = theta - lr * grad(theta)   
    return theta


theta = descend([0.0, 0.0], lr=0.05, steps=60)
print(theta, loss(theta))

[ 2.10040296e+00 -2.76445533e-15] 24.592448791134984

Η κλειστή λύση ελαχίστων τετραγώνων για αυτά τα οκτώ σημεία είναι $a = 2.100403$, $b = 0$, με απώλεια $24.592449$. Ο βρόχος τη βρήκε στα οκτώ σημαντικά ψηφία χωρίς να γνωρίζει ότι υπάρχει κλειστή μορφή — κάτι που έχει σημασία, επειδή από το Κεφάλαιο 5 και μετά δεν θα υπάρχει.

Η τροχιά, επειδή το νόημα είναι να τη δείτε:

   0 a=0.000000 b=0.000000 L=57.437500
   1 a=1.563750 b=0.000000 L=26.736582
   2 a=1.963288 b=-0.000000 L=24.732418
   5 a=2.098116 b=-0.000000 L=24.592488
  10 a=2.100400 b=-0.000000 L=24.592449
  60 a=2.100403 b=-0.000000 L=24.592449

Το μεγαλύτερο μέρος της απόστασης καλύπτεται στα πρώτα δύο βήματα, επειδή το gradient είναι μεγαλύτερο όταν είστε πιο μακριά από τον πάτο και μικραίνει όσο πλησιάζετε. Το gradient descent επιβραδύνει αυτόματα κοντά σε ένα ελάχιστο. Αυτό είναι χαρακτηριστικό και είναι επίσης, στο Κεφάλαιο 6, πρόβλημα.

Το επιχείρημα μέχρι τώρα έχει μια τρύπα. Το βήμα σταματά όταν $\nabla L = \mathbf{0}$, και εμείς το αποκαλούσαμε «το ελάχιστο». Ένα σημείο με μηδενικό gradient είναι ένα κρίσιμο σημείο, και το να είναι ελάχιστο είναι μόνο ένας από τους τρόπους να είναι τέτοιο:

• ένα τοπικό ελάχιστο: ανηφόρα προς κάθε κατεύθυνση, αλλά πιθανώς όχι το χαμηλότερο τέτοιο σημείο οπουδήποτε·
• ένα τοπικό μέγιστο: κατηφόρα προς κάθε κατεύθυνση·
• ένα σαγματικό σημείο: ανηφόρα σε κάποιες κατευθύνσεις και κατηφόρα σε άλλες. Η επιφάνεια $f(x,y) = x^2 - y^2$ έχει $\nabla f = (2x, -2y)$, που είναι μηδέν στην αρχή, όπου η συνάρτηση είναι ελάχιστο κατά μήκος του άξονα $x$ και μέγιστο κατά μήκος του άξονα $y$ ταυτόχρονα.

Το gradient descent δεν μπορεί να τα ξεχωρίσει, επειδή κοιτάζει πάντα μόνο το gradient, και το gradient είναι μηδέν και στα τρία.

Η ευθεία μας έχει ένα κρίσιμο σημείο και είναι η απάντηση — μια απώλεια τετραγωνικού σφάλματος πάνω σε γραμμικό μοντέλο είναι κυρτή, ένα μόνο μπολ, και η κάθοδος σε αυτή δεν μπορεί να αποτύχει να βρει το ολικό ελάχιστο. Αυτή η ιδιότητα δεν επιβιώνει την επαφή με αυτό το μάθημα. Η απώλεια ενός νευρωνικού δικτύου δεν είναι κυρτή, και από το Κεφάλαιο 5 και μετά «το ελάχιστο» δεν είναι κάτι που υπάρχει: υπάρχουν πολλά, διαφορετικού βάθους, και το ποιο θα πάρετε εξαρτάται από το πού ξεκινήσατε. Αυτό είναι μία πρόταση και παραμένει μία πρόταση, επειδή η θεωρία είναι μεγάλη και η πρακτική συνέπεια μικρή.

Μπορείτε να δείτε όλη τη συνέπεια σε μία καμπύλη. Πάρτε $f(x) = \tfrac{x^4}{4} - \tfrac{x^2}{2} + \tfrac{x}{10}$, που έχει δύο κοιλάδες διαφορετικού βάθους:

   x =  -1.046681   f(x) =  -0.352386   minimum
   x =   0.101031   f(x) =   0.005026   maximum
   x =   0.945649   f(x) =  -0.152639   minimum

Η προσγείωση στη ρηχή κοιλάδα είναι 56,7% χειρότερη σε απώλεια, και ο αλγόριθμος δεν έχει τρόπο να το ξέρει, επειδή μέσα από μια κοιλάδα κάθε κατεύθυνση είναι ανηφόρα. Δεν υπάρχει επιδιόρθωση γι’ αυτό στο gradient descent και δεν έρχεται καμία. Αυτό που υπάρχει, στην πράξη, είναι το εύρημα ότι έχει πολύ μικρότερη σημασία από όσο υποδηλώνει αυτή η εικόνα — στις πολύ υψηλές διαστάσεις ενός πραγματικού δικτύου, τα περισσότερα κρίσιμα σημεία αποδεικνύονται σάγματα αντί για παγίδες,² και το Κεφάλαιο 5 μετρά πόσο συχνά κολλάει πραγματικά ένα μικρό δίκτυο.

Ένα πράγμα στο grad παραπάνω πρέπει να σας ενοχλεί: αθροίζει πάνω σε ολόκληρο το dataset για κάθε βήμα. Οκτώ εξαρτήματα δεν είναι τίποτα. Ένα εκατομμύριο είναι ένα εκατομμύριο υπολογισμοί gradient για να μετακινηθούν οι παράμετροι μία φορά.

Η διέξοδος είναι ότι το gradient είναι ένας μέσος όρος, και ένας μέσος όρος μπορεί να εκτιμηθεί από ένα δείγμα. Υπολογίστε το σε μια τυχαία χούφτα — ένα minibatch — και κάντε βήμα πάνω σε αυτό. Η εκτίμηση είναι θορυβώδης· είναι επίσης αμερόληπτη, και εκατοντάδες φθηνά θορυβώδη βήματα νικούν ένα ακριβό ακριβές. Σε εκατό χιλιάδες συνθετικά εξαρτήματα, μετρώντας gradients ανά παράδειγμα αντί για βήματα:

Διακόσιες δεκαεννέα φορές λιγότερη αριθμητική για να φτάσουμε στο ίδιο σημείο. Και το άκρο — ένα παράδειγμα τη φορά, η αρχική στοχαστική προσέγγιση των Robbins και Monro³ — δεν είναι ο νικητής: είναι πέντε φορές χειρότερο από batches των 32, επειδή 32 παραδείγματα κοστίζουν σχεδόν τίποτα περισσότερο από ένα σε hardware που πολλαπλασιάζει πίνακες, ενώ ο θόρυβος πέφτει με την τετραγωνική ρίζα του μεγέθους batch. Αυτός ο συμβιβασμός είναι ο λόγος που κάθε script εκπαίδευσης που θα διαβάσετε ποτέ έχει ένα batch_size μέσα του.

Momentum είναι η άλλη φθηνή διόρθωση, και στοχεύει ευθέως στην τάφρο. Σε μια κακοσχηματισμένη κοιλάδα τα βήματα ζιγκ-ζαγκάρουν κατά μήκος της στενής κατεύθυνσης ενώ σέρνονται κατά μήκος της μακριάς. Το momentum κρατά έναν κυλιόμενο μέσο όρο των προηγούμενων gradients, ώστε οι ταλαντούμενες συνιστώσες να ακυρώνονται και η συνεπής να συσσωρεύεται:⁴

Δύο επιπλέον γραμμές. Στον ωμό μη κεντραρισμένο ιμάντα — αριθμός κατάστασης 33.452, η χειρότερη περίπτωση που έχουμε — με τον καλύτερο ρυθμό που μπορεί να πάρει η απλή κάθοδος:

momentum beta=0.0   ->    79,513 steps to 1%
momentum beta=0.9   ->     1,609 steps to 1%
momentum beta=0.99  ->       461 steps to 1%

Παράγοντας 172 για δύο γραμμές κώδικα. Το Κεφάλαιο 6 το μετατρέπει σε Adam· ο μηχανισμός είναι ήδη εδώ.

Κάθε gradient σε αυτό το κεφάλαιο παράχθηκε με το χέρι και επομένως θα μπορούσε να είναι λάθος. Η λύση είναι ο πίνακας κλίσεων από την αρχή: μετρήστε την παράγωγο αριθμητικά και συγκρίνετε. Χρησιμοποιήστε την κεντρική διαφορά, $\frac{L(\theta+h) - L(\theta-h)}{2h}$, που ακυρώνει τον κύριο όρο σφάλματος και είναι πολύ πιο ακριβής για το ίδιο $h$.

def numeric_grad(f, theta, h=1e-5):
    theta = np.asarray(theta, dtype=float)
    out = np.zeros_like(theta)
    for i in range(theta.size):
        bump = np.zeros_like(theta)
        bump[i] = h
        out[i] = (f(theta + bump) - f(theta - bump)) / (2 * h)     
    return out


def gradcheck(f, df, theta, h=1e-5):
    analytic = np.asarray(df(theta), dtype=float)
    numeric = numeric_grad(f, theta, h)
    return np.max(np.abs(analytic - numeric) / np.maximum(1e-8, np.abs(analytic) + np.abs(numeric)))

Η σχετική μορφή της σύγκρισης έχει σημασία: μια απόλυτη διαφορά $10^{-4}$ είναι καταστροφή σε gradient μεγέθους $10^{-3}$ και άσχετη σε ένα μεγέθους $10^{6}$.

relative error: 1.8929136036763527e-11
with 2 dropped: 0.33333333331650744

Η πρώτη γραμμή είναι το gradient που παράχθηκε με το χέρι παραπάνω. Η δεύτερη είναι η ίδια συνάρτηση με τον παράγοντα 2 παραλειμμένο από μία συνιστώσα — ένα typo ενός χαρακτήρα — και ο έλεγχος το πιάνει αμέσως. Οτιδήποτε κάτω από περίπου $10^{-7}$ είναι συμφωνία· οτιδήποτε πάνω από $10^{-4}$ είναι bug. Κρατήστε αυτή τη συνάρτηση: το Κεφάλαιο 5 τη χρησιμοποιεί για να debugάρει μια μηχανή αυτόματης διαφοροποίησης, και είναι ο μόνος λόγος που ένα λάθος gradient μπορεί να βρεθεί überhaupt.

Όλα σε αυτό το κεφάλαιο στηρίχθηκαν σε μία υπόθεση που δεν δηλώθηκε ποτέ: ότι μπορείτε να γράψετε κάτω το $\partial L / \partial \theta$.

Για μια ευθεία με δύο παραμέτρους, αυτό ήταν μία γραμμή άλγεβρας. Σταματά να είναι σχεδόν αμέσως. Ζητήστε από ένα σύστημα συμβολικής άλγεβρας την παράγωγο της απώλειας ενός δικτύου ως προς ένα μόνο βάρος πρώτου επιπέδου, για ένα μόνο παράδειγμα, και μετρήστε την αριθμητική στην απάντηση:

Η τρίτη σειρά είναι ένα δίκτυο με 57 παραμέτρους — ένα δίκτυο τόσο μικρό που θα ήταν υποσημείωση στο Κεφάλαιο 6 — και το να γράψετε το gradient του με το χέρι σημαίνει περίπου 97.869 πράξεις για ένα παράδειγμα εκπαίδευσης. Δεν υπάρχει συμβολισμός που να το σώζει αυτό. Αυτό που το σώζει είναι η παρατήρηση ότι ο κανόνας της αλυσίδας εφαρμοσμένος σε μια σύνθεση έχει τεράστια δομή, ότι οι ίδιες ενδιάμεσες ποσότητες εμφανίζονται ξανά και ξανά, και ότι ο υπολογισμός τους με τη σωστή σειρά δίνει όλες τις παραγώγους με περίπου το κόστος ενός forward pass. Αυτό είναι το Κεφάλαιο 5.

Αλλά υπάρχει πρώτα ένα μικρότερο πρόβλημα, και περιμένει αμέσως.

Έχουμε τώρα μια μηχανή που θα κυλήσει προς τα κάτω σε οποιαδήποτε διαφορίσιμη απώλεια. Στρέψτε τη στην αρχική ερώτηση του ιμάντα — αποδοχή ή απόρριψη, στόχος 1 ή 0 — βάλτε ένα sigmoid στην έξοδο ώστε να προβλέπει πιθανότητα, και ελαχιστοποιήστε το τετραγωνικό σφάλμα. Θα τρέξει. Θα κινηθεί επίσης ελάχιστα όταν κάνει το πιο λάθος, και το gradient λέει γιατί:

Ένα μοντέλο που είναι με αυτοπεποίθηση, καταστροφικά λάθος — προβλέποντας 0,0000454 όταν η απάντηση είναι 1 — παράγει gradient τετραγωνικού σφάλματος $9 \times 10^{-5}$. Δεν έχει ιδέα ότι βρίσκεται σε μπελάδες. Η άλλη στήλη, από μια απώλεια που δεν έχουμε ακόμη παράξει, αναφέρει 1,0: μέγιστη επείγουσα ανάγκη, ακριβώς εκεί όπου αξίζει.

Αυτό εγείρει το ερώτημα με το οποίο ανοίγει το επόμενο κεφάλαιο. Το προηγούμενο κεφάλαιο είπε ότι μια απώλεια είναι μια υπόθεση για τον θόρυβο, και το τετραγωνικό σφάλμα υποθέτει Gaussian θόρυβο. Τι μοντέλο θορύβου έχει μια απάντηση ναι-ή-όχι — και ποια απώλεια βγαίνει όταν τρέξετε την ίδια παραγωγή πάνω του;

Η μέθοδος είναι παλαιότερη από όλα αυτά: ο Cauchy την περιέγραψε σε ένα σημείωμα προς την Académie des Sciences το 1847, ως έναν τρόπο επίλυσης συστημάτων εξισώσεων περπατώντας προς τα κάτω πάνω στο άθροισμα των τετραγώνων των υπολοίπων τους. Αξίζει επίσης να διαβαστεί μαζί με αυτό το κεφάλαιο το An overview of gradient descent optimization algorithms του Sebastian Ruder (arXiv:1609.04747), που καλύπτει το momentum μέχρι τον Adam σε δεκατέσσερις ευανάγνωστες σελίδες· το κεφάλαιο 3 των Nocedal και Wright, Numerical Optimization (2η έκδ., Springer, 2006), του οποίου το θεώρημα 3.3 δίνει τον ρυθμό σύγκλισης της steepest descent σε ένα τετραγωνικό ως συνάρτηση του αριθμού κατάστασης — είναι η θεωρία πίσω από το γιατί το conditioning αποφασίζει το πλήθος βημάτων, αν και αντιμετωπίζει line search αντί για την οροφή σταθερού βήματος $2/\lambda_{\max}$ που μετρήθηκε παραπάνω, ή οι §5.8 και §7.1 των Deisenroth, Faisal και Ong, Mathematics for Machine Learning, για το ίδιο έδαφος με λιγότερη μηχανή· η §6.1 του Prince, Understanding Deep Learning, και η §4.3 των Goodfellow, Bengio και Courville, Deep Learning· το Dive into Deep Learning §12.1–12.3, που έχει την ανάλυση minibatch με περισσότερες μετρήσεις από όσες χωράνε εδώ· και το κεφάλαιο 4 του Géron, Hands-On Machine Learning (3η έκδ.), η πιο πρακτική αντιμετώπιση του ρυθμού μάθησης ως κάτι που ρυθμίζετε αντί να παράγετε. Οι σημειώσεις MIT 6.390 βάζουν το gradient descent πριν από την ταξινόμηση, όπως κάνει αυτό το μάθημα και για τον ίδιο λόγο.