Надолу по склона: 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, и с причина, която ще се върне с лихва преди краят на тази глава. Model-ът е права, $\hat{y} = a x + b$, а loss-ът е mean squared error, който предишната глава изведе:

Два параметъра. Защо просто да не пробваме много стойности? Нека наистина го направим — grid от $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

Половин милион оценки, за да фиксираме две числа до два знака след десетичната запетая — и тази секунда е wall clock на една машина, така че при повторно пускане може да излезе някъде между три и шест; броят оценки и минимумът са частта, която се възпроизвежда. Gradient descent, в края на тази глава, достига четири знака след десетичната запетая за осем стъпки и пълния float64 отговор за трийсет и шест.

Но скоростта не е аргументът, и това е точката, която определя целия курс. Grid search струва $k^P$ оценки за $P$ параметъра при $k$ стойности за всеки. С хиляда стойности по всяка ос:

Третият ред не е голямо число, а безсмислено — има приблизително $10^{80}$ атома в наблюдаемата Вселена. Търсенето не става по-бавно, когато models растат; то спира да съществува. Всичко, което следва, съществува заради тази таблица.

Фиксирайте $b = 0$ за момент, така че да има един параметър и една крива — картината, с която ви остави последната глава. Вземете точка върху нея, $a = 1$, и попитайте: ако побутна $a$ с малко количество $h$, с колко се измества loss-ът на единица побутване?

Това отношение е rise over run — наклонът на правата линия през две точки на кривата. Когато $h$ намалява, двете точки се плъзгат една към друга и линията става допирателна. Нейният наклон е производната $L'(a)$: скоростта, с която loss-ът се променя на единица промяна в $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$ на сто, грешката се дели на сто, до четири значещи цифри всеки път. Тази константа не е украса: тя е половината от втората производна на loss-а и е първата поява на идея, която идва след две секции — че една крива близо до точка изглежда като права плюс корекция, пропорционална на $h^2$.

А после моделът се чупи. Под $h = 10^{-8}$ оценката става по-лоша, а при $10^{-14}$ е грешна още във втората цифра. Нищо математическо не се случи; случи се floating-point кутията от миналата глава. $L(a+h)$ и $L(a)$ съвпадат в първите си десет цифри, изваждането им унищожава тези цифри, а деленето на останките на миниатюрно число усилва това, което е останало. Има най-добро $h$ — тук около $10^{-8}$, приблизително квадратният корен на machine epsilon — и да отидете по-малко не е по-внимателно, а по-невнимателно. Запомнете това; функция в края на тази глава зависи от него.

Точният наклон, от calculus, а не от измерване, е $-16.385$. Така че можем да спрем да измерваме и да започнем да извеждаме.

Ето идеята, върху която е построен останалият курс, казана веднъж, ясно.

Да композирате две функции означава да подадете едната в другата: $(f \circ g)(x) = f(g(x))$. Нищо повече.

Дълбоката мрежа не е като композиция. Тя е композиция. Layer е функция; подреждането на layers е композирането им; „дълбочина“ е броят функции във веригата. Когато Глава 5 изгражда мрежа, тя изгражда $f_4 \circ f_3 \circ f_2 \circ f_1$ и нищо друго. Което означава, че единственото най-важно правило на calculus, за нашите цели, е онова, което диференцира композиция:

Скоростите се умножават. Ако $g$ се променя три пъти по-бързо от $x$, а $f$ се променя два пъти по-бързо от $g$, тогава $f$ се променя шест пъти по-бързо от $x$. Това е цялото съдържание и затова сигнал, който минава назад през десет layers, се умножава по десет числа — поради което Глава 6 отделя секция на това какво се случва, когато всички тези числа са малко по-малки от едно.

Използвайте го върху нашия loss. Запишете residual-а $r_i = a x_i + b - y_i$, така че $L = \frac{1}{n}\sum r_i^2$. Всяко $r_i$ зависи от $a$ чрез вътрешната функция $a x_i$, чиято производна е $x_i$. Chain rule, член по член:

Тези къдрави символи $\partial$ означават частна производна: диференцирате спрямо една променлива и третирате всяка друга като константа. Нищо ново не се случва — това е същата граница като преди, взета по една ос. Съберете частните производни във вектор и имате градиента:

В точката $(a, b) = (1, 4)$ този вектор е $(-16.385,\ 8.0)$. Две числа. Въпросът е какво означават, и това е първата стъпка, която всички пропускат.

Градиентът е вектор от наклони по осите. Това е всичко, което сме доказали. Не е очевидно — и не бива да е очевидно — че сглобяването им във вектор произвежда нещо, което сочи в някаква конкретна посока.

Затова дефинирайте нещото, което всъщност искаме. Изберете unit vector $\mathbf{u}$, посока. Directional derivative е скоростта, с която loss-ът се променя, докато вървите натам:

Chain rule превръща това в нещо изчислимо. Ходенето по $\mathbf{u}$ променя $a$ със скорост $u_1$ и $b$ със скорост $u_2$, а приносите се събират:

Скоростта на промяна в която и да е посока е dot product на градиента с тази посока. А сега punchline-ът, който е един ред геометрия. Записвайки dot product-а с ъгъла $\phi$ между векторите,

понеже $\mathbf{u}$ има дължина 1. Единственото, което контролирате, е $\cos\phi$, което е най-голямо при $\phi = 0$ и най-малко при половин оборот, $\phi = 180$ градуса. Значи:

• Най-стръмното изкачване е по самия $\nabla L$, а наклонът там е точно $\lVert \nabla L \rVert$.
• Най-стръмното спускане е по $-\nabla L$, а наклонът там е $-\lVert \nabla L \rVert$.
• Перпендикулярно на градиента loss-ът изобщо не се променя. Затова линиите на contour map пресичат градиента под прав ъгъл.

Това е знакът минус. Не конвенция, не обръщане на знак, което някой е избрал: посоката на най-бързо намаляване е отрицателният градиент, защото $\cos\phi$ се минимизира при половин оборот, и по никаква друга причина.

Тъй като това е твърдение за всички посоки, тествайте го срещу всички посоки. Sample-нете 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

Търсене, което не знае нищо за градиенти, сред 3,600 посоки намира най-стръмното си изкачване при 154.0 градуса — собствената посока на градиента, в рамките на 0.1-градусовата resolution на търсенето. А наклонът, който намира там, 18.2337, е дължината на градиента до шест цифри. Теоремата не е история за това какво означават градиентите; тя е измерим факт, и това е измерването.

Сега втората пропусната стъпка. Знаем накъде е надолу. От това не следва, че ходенето натам намалява loss-а, защото „надолу“ е твърдение за безкрайно малко побутване, а стъпката не е безкрайно малка.

Мостът е линеаризация. Близо до точка гладка функция е нейната допирателна плюс корекция:

Това е Taylor expansion от първи ред. Изхвърленото $O(\lVert\boldsymbol{\delta}\rVert^2)$ е кривината — същият член, който направи оценката в таблицата с наклони грешна с точно $7.445\,h$. Поставете стъпката, която възнамеряваме да направим, $\boldsymbol{\delta} = -\eta \nabla L$:

Loss-ът пада с $\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$ намалява, доставеният спад converges към обещания — ratio 0.99938, после 0.99994 — което е Taylor's theorem в действие. Четете отгоре и при $\eta = 0.2$ доставеният „спад“ е минус шестнайсет. Стъпката тръгна надолу, а loss-ът се качи.

Значи правилото за update е

и идва с условие, което никой не казва: $\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$ завинаги, без да се приближава и без да избяга. Под него — converge; над него — diverge. Интервалът се разделя отново при $\eta = 0.5$, където множителят сменя знак: под това приближаването е монотонно, над него точката overshoots и редува страни, а точно при $0.5$ множителят е 0 и една-единствена стъпка попада в минимума.

Четири режима от четири реда алгебра. Отидете и прекосете границите сами:

А сега интересният случай:

Сега общото правило, което изпада от същия аргумент. Множителят $1 - 2\eta$ всъщност беше $1 - \eta f''$, а близо до минимум multi-parameter loss има по едно такова число за всяка посока — eigenvalues на матрицата на вторите производни. Всяка посока трябва да е стабилна едновременно, така че таванът се задава от най-голямата:

За $f(x) = x^2$, $f'' = 2$, таван 1, което е точно това, което изведохме. За нашата лента матрицата на вторите производни е $\frac{2}{n} A^{\top} A$ с $A$ като двуколонната матрица на inputs, а eigenvalues са 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

Пет знака след десетичната запетая съвпадение между един ред linear algebra и сто хиляди iterations на for loop.

И ето къде Глава 1 се връща. Всичко по-горе използваше центрираните измервания. Пуснете идентичния code върху сурови милиметри и грамове и eigenvalues са 0.0298 и 998.1 вместо 2 и 14.89. Таванът се срива от 0.134 до 0.002004 — също толкова точно, converging при lr=0.002003 и взривявайки се при lr=0.002004.

По-лошо от тавана е отношението между eigenvalues. Condition number измерва колко далеч от кръгла е долината: дълъг тънък ров налага скорост, достатъчно малка за стръмните стени, а после дъното на рова се изминава със същото пълзене. Нашият отива от 7.44 центриран до 33,452 суров. С най-добрата скорост, която всяка версия може да поеме:

Същите данни, същият code, същият отговор накрая — и осем хиляди пъти повече работа, защото никой не е извадил средната стойност. В Глава 1 същият пропуск струва на perceptron фактор шест хиляди в epochs, а диагнозата там беше геометрична: данните плаваха далеч от началото. Това е същата геометрия тук, преоблечена като оптимизация, и затова input normalisation не е хигиенен съвет, а аритметика.¹

Нищо по-горе не се нуждаеше от library. Ето целия 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

Closed-form least-squares отговорът за тези осем точки е $a = 2.100403$, $b = 0$, с loss $24.592449$. Loop-ът го намери до осем значещи цифри, без да знае, че closed form съществува — което има значение, защото от Глава 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 descent се забавя автоматично близо до минимум. Това е feature и също така, в Глава 6, проблем.

Аргументът дотук има дупка. Стъпката спира, когато $\nabla L = \mathbf{0}$, а ние наричахме това „минимума“. Точка с нулев градиент е критична точка, а да бъде минимум е само един от начините да бъде такава:

• локален минимум: нагоре във всяка посока, но възможно не най-ниската такава точка изобщо;
• локален максимум: надолу във всяка посока;
• седлова точка: нагоре в някои посоки и надолу в други. Повърхността $f(x,y) = x^2 - y^2$ има $\nabla f = (2x, -2y)$, което е нула в началото, където функцията е минимум по оста $x$ и максимум по оста $y$ едновременно.

Gradient descent не може да ги различи, защото винаги гледа само градиента, а градиентът е нула и при трите.

Нашата права има една критична точка и тя е отговорът — squared-error loss върху линеен model е convex, една-единствена купа, и descent върху него не може да не намери глобалния минимум. Това свойство не оцелява при срещата с този курс. Loss-ът на neural network не е convex, и от Глава 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% по-лошо като loss, а алгоритъмът няма как да знае, защото отвътре на долина всяка посока е нагоре. Няма поправка за това в gradient descent и такава няма да дойде. Това, което има на практика, е откритието, че то има далеч по-малко значение, отколкото тази картина подсказва — във много високите измерения на реална мрежа повечето критични точки се оказват седла, а не капани,² и Глава 5 измерва колко често една малка мрежа наистина засяда.

Едно нещо за grad по-горе трябва да ви притесни: то сумира върху целия dataset за всяка стъпка. Осем части са нищо. Един милион е един милион gradient computations, за да преместите параметрите веднъж.

Изходът е, че градиентът е средна стойност, а средна стойност може да се оцени от sample. Изчислете го върху случайна шепа — minibatch — и направете стъпка по него. Оценката е шумна; тя е и unbiased, а стотици евтини шумни стъпки побеждават една скъпа точна. Върху сто хиляди synthetic части, броейки per-example gradients вместо стъпки:

Двеста и деветнайсет пъти по-малко аритметика, за да стигнете до същото място. А крайността — по един пример наведнъж, оригиналната stochastic approximation на Robbins и Monro³ — не е победителят: тя е пет пъти по-лоша от batch-ове по 32, защото 32 примера струват почти нищо повече от един върху hardware, който умножава матрици, докато шумът спада с квадратния корен от batch size. Този trade-off е причината всеки training script, който някога ще прочетете, да има batch_size в него.

Momentum е другата евтина поправка и е насочена право към рова. В зле conditioned долина стъпките правят зигзаг през тясната посока, докато пълзят по дългата. Momentum държи running average на минали градиенти, така че осцилиращите компоненти се cancel-ват, а постоянната се натрупва:⁴

Два допълнителни реда. Върху суровата нецентрирана лента — condition number 33,452, най-лошият случай, който имаме — при най-добрата скорост, която plain descent може да поеме:

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 за два реда code. Глава 6 превръща това в Adam; механизмът вече е тук.

Всеки градиент в тази глава беше изведен на ръка и следователно може да е грешен. Поправката е таблицата с наклони от началото: измерете производната числено и сравнете. Използвайте central difference, $\frac{L(\theta+h) - L(\theta-h)}{2h}$, която cancel-ва водещия член на грешката и е много по-точна за същото $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}$ е катастрофа при градиент с размер $10^{-3}$ и е irrelevant при такъв с размер $10^{6}$.

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

Първият ред е ръчно изведеният градиент по-горе. Вторият е същата функция с изпуснат фактор 2 в един компонент — typo от един-единствен символ — и проверката го хваща веднага. Всичко под около $10^{-7}$ е съвпадение; всичко над $10^{-4}$ е bug. Запазете тази функция: Глава 5 я използва, за да debug-ва automatic differentiation engine, и тя е единствената причина грешен градиент изобщо да може да бъде намерен.

Всичко в тази глава се опираше на едно предположение, което никога не беше изречено: че можете да запишете $\partial L / \partial \theta$.

За права с два параметъра това беше един ред алгебра. Почти веднага спира да бъде такъв. Попитайте symbolic algebra system за производната на loss-а на мрежа спрямо един-единствен first-layer weight, за един-единствен пример, и пребройте аритметиката в отговора:

Третият ред е мрежа с 57 параметъра — мрежа толкова малка, че би била бележка под линия в Глава 6 — а изписването на нейния градиент на ръка означава около 97,869 операции за един training example. Няма notation, която да спаси това. Спасението е наблюдението, че chain rule, приложен към композиция, има огромна структура, че едни и същи междинни величини се появяват отново и отново, и че изчисляването им в правилния ред дава всички производни за приблизително цената на един forward pass. Това е Глава 5.

Но първо има по-малък проблем и той чака веднага.

Сега имаме машина, която ще се търкаля надолу по всеки differentiable loss. Насочете я към първоначалния въпрос за лентата — приеми или отхвърли, target, който е 1 или 0 — сложете sigmoid на output-а, за да предсказва вероятност, и минимизирайте squared error. Тя ще тръгне. Но и почти няма да се движи, когато греши най-много, и градиентът казва защо:

Model, който е уверено, катастрофално грешен — предсказва 0.0000454, когато отговорът е 1 — произвежда squared-error gradient от $9 \times 10^{-5}$. Той няма представа, че е в беда. Другата колона, от loss, който още не сме извели, отчита 1.0: максимална спешност, точно там, където е заслужена.

Което повдига въпроса, с който започва следващата глава. Последната глава каза, че loss е предположение за шума, а squared error предполага Gaussian noise. Какъв noise model има отговор „да“ или „не“ — и какъв loss излиза, когато приложите същото извеждане върху него?

Методът е по-стар от всички тях: Cauchy го описва в бележка до Académie des Sciences през 1847 г. като начин за решаване на системи от уравнения чрез ходене надолу по сумата от квадратите на residual-ите им. Също си струва да прочетете заедно с тази глава: An overview of gradient descent optimization algorithms на Sebastian Ruder (arXiv:1609.04747), който покрива momentum до Adam в четиринайсет четивни страници; глава 3 от Numerical Optimization на Nocedal и Wright (2nd ed., Springer, 2006), чиято theorem 3.3 дава convergence rate на steepest descent върху quadratic чрез condition number — това е теорията зад причината conditioning да определя броя стъпки, макар да разглежда line search, а не fixed-step тавана $2/\lambda_{\max}$, измерен по-горе; или §5.8 и §7.1 от Mathematics for Machine Learning на Deisenroth, Faisal и Ong за същата територия с по-малко machinery; §6.1 от Understanding Deep Learning на Prince и §4.3 от Deep Learning на Goodfellow, Bengio и Courville; Dive into Deep Learning §12.1–12.3, където има minibatch analysis с повече измервания, отколкото има място тук; и глава 4 от Hands-On Machine Learning на Géron (3rd ed.), най-практичното разглеждане на learning rate като нещо, което tune-вате, вместо да извеждате. Бележките на MIT 6.390 поставят gradient descent преди classification, както прави този курс, и по същата причина.