Ложка супа и тяжёлый шар

Вся кастрюля, одна капля или ложка

В уроке 13 шаг спуска выглядел просто: посчитать градиент ошибки и сдвинуть веса против него. Только ошибка сети — это среднее по всем примерам training set:

Значит, и градиент — среднее \(N\) градиентов. Один честный шаг требует прогнать через сеть все примеры: при \(N = 50\,000\) это пятьдесят тысяч forward и backward pass ради одного маленького сдвига весов. Профессор говорит об этом коротко (лекция 2, слайд 27): считать по всем точкам — "unpractical".

Попробовать суп можно тремя способами. Они отличаются только тем, по скольким примерам усредняют градиент перед каждым шагом.

Batch gradient descent — вся кастрюля. Градиент точный, но на каждый шаг уходит весь датасет.

Stochastic gradient descent (SGD) — одна капля: шаг по одному случайно выбранному примеру. Ключевые слова профессора (лекция 2, слайд 28): unbiased, но high variance.

Mini-batch gradient descent — ложка: среднее по \(M\) случайным примерам, \(M \lt N\). На том же слайде про него сказано: "good trade off variance-computation".

Что значат unbiased и variance, разберём в следующем разделе. Сначала — сколько шагов даёт каждый способ. Для этого нужны два слова.

Откуда 1563: \(50\,000 / 32 = 1562.5\). Это 1562 полных mini-batch и один «хвост» из 16 примеров. Хвост — тоже обновление, поэтому округляют вверх.

Рисунок 1 — это весь алгоритм из листинга 9 конспекта. В начале каждой эпохи датасет перемешивают, режут на куски по \(M\) примеров и для каждого куска делают одно обновление: веса сдвигаются против градиента, посчитанного только по этому куску.

Перемешивание — то самое «размешать суп». Если примеры лежат по порядку (сначала все кошки, потом все собаки), ложка из верхнего слоя расскажет только про кошек.

И ещё один термин из конспекта. Среднюю ошибку по датасету \(E(\vb{w})\) там называют empirical risk. Она стоит на месте величины, которую хочется минимизировать на самом деле, — true risk, ожидаемой ошибки на любом примере из распределения данных \(D\):

Посчитать true risk нельзя: \(D\) неизвестно, есть только \(N\) примеров из него. Поэтому математическое ожидание заменяют средним по этим примерам — и минимизируют его.

Почему ложке можно верить

Градиент по mini-batch — это среднее по случайной выборке. Про такие средние ты всё знаешь из Applied Statistics: выборочное среднее в среднем попадает в истинное, а его стандартная ошибка равна \(\sigma / \sqrt{n}\). Перенесём это на градиент за четыре шага.

1. Оценка по mini-batch — среднее \(M\) градиентов отдельных примеров. Обозначим её \(\vb{g}_{MB}\) (буква \(g\) здесь от слова gradient, это не выход сети):

   \[ \vb{g}_{MB} = \frac{1}{M}\sum_{n \in \text{mini-batch}} \nabla E(\vb{x}_n, \vb{w}) \]

2. Примеры в mini-batch выбраны случайно. Поэтому каждое слагаемое в среднем равно среднему по всему датасету, то есть полному градиенту:

   \[ \E\bigl[\vb{g}_{MB}\bigr] = \nabla E(\vb{w}) \]

   Оценка несмещённая (unbiased): она ошибается, но не систематически.

3. Градиенты отдельных примеров разбросаны вокруг полного. Пусть дисперсия одной их компоненты равна \(\sigma^2\). У среднего \(M\) независимых слагаемых дисперсия в \(M\) раз меньше:

   \[ \operatorname{Var}\bigl[g_{MB}\bigr] = \frac{\sigma^2}{M} \]

4. Типичная ошибка оценки — корень из дисперсии:

   \[ \text{шум оценки} = \frac{\sigma}{\sqrt{M}} \]

   Это та самая стандартная ошибка среднего. Mini-batch в 100 раз больше стоит в 100 раз дороже, а шум уменьшает в \(\sqrt{100} = 10\) раз.

В разделе конспекта про mini-batch слов unbiased и variance нет: там градиент просто «noisy». На слайде они есть (лекция 2, слайд 28), и на экзамене отвечать нужно именно ими.

Что из этого следует

Большой mini-batch покупает точность по невыгодному курсу: от \(M = 32\) к \(M = 3200\) шаг дорожает в 100 раз, а шум падает только в 10. Слишком маленький тоже плох: простаивает GPU, а статистики batch normalization из урока 26 считаются по горстке примеров и шумят. Поэтому обычно начинают с \(M\) = 32, 64 или 128.

Шум не исчезает у минимума. Полный градиент там равен нулю, а градиенты отдельных примеров — нет: каждому примеру хочется сдвинуть веса в свою сторону. Поэтому спуск с постоянным \(\eta\) не останавливается, а дрожит в «шумовом шаре». Шар тем больше, чем больше \(\eta\) и чем меньше \(M\).

Отсюда связь двух ручек: размах дрожания определяется отношением \(\eta / M\). Увеличив mini-batch в \(k\) раз, обычно увеличивают в \(k\) раз и \(\eta\) — это называют linear scaling rule.

У шума есть и польза — о ней стр. 196 конспекта. Случайные толчки помогают спуску выбраться из мелкого локального минимума и не застрять на плато, где точный градиент почти нулевой. И они мешают сети подогнать веса под каждый пример в отдельности: шум работает как regularizer.

Расписание: длинные шаги в начале, короткие в конце

В виджете клубок у минимума сжимался, стоило уменьшить \(\eta\). Но маленький \(\eta\) с самого начала — это медленный спуск, который легко вязнет на плато. А слишком большой, как в уроке 13, качается или расходится. Выход напрашивается: менять \(\eta\) по ходу обучения. Сначала идти широким шагом, чтобы быстро спуститься со склона, потом укорачивать шаг, чтобы перестать прыгать через ручей на дне.

В конспекте четыре расписания, формулы (81)–(84). Везде \(\eta_0\) — стартовое значение, \(t\) — номер эпохи.

Step decay — лестница: каждые \(s\) эпох шаг умножается на число \(\mathrm{drop}\), например на 0.5.

Exponential decay — плавное убывание: за каждую эпоху шаг уменьшается в одно и то же число раз.

1/t decay — убывание медленнее экспоненты; классическое правило из теории stochastic approximation. Его смысл: шаги убывают достаточно медленно, чтобы в сумме пройти любое расстояние до минимума, и достаточно быстро, чтобы шум к концу затих.

Cosine annealing — половинка косинуса: медленно в начале, быстро в середине, снова медленно к концу, и ровно ноль на последней эпохе \(T\).

Warm-up — обратная идея для самого начала: первые \(T_w\) эпох шаг не убывает, а линейно растёт от нуля до значения из расписания.

Зачем: в первые шаги веса случайные, градиенты большие, а у Adam (о нём ниже) ещё не накоплена статистика. Широкий шаг в этот момент может забросить сеть туда, откуда она долго выбирается. В коде warm-up нередко считают не в эпохах, а в iterations: формула та же, только \(t\) — номер обновления. В конспекте warm-up не разобран; на стр. 199 упомянуты только warm restarts, а это другое.

Тяжёлый шар: momentum

Расписание решает, какой длины шаг. Но есть беда, которую длиной шага не вылечить, — овраг (ravine): поверхность ошибки, крутая в одном направлении и пологая в другом.

Возьмём самый простой овраг — вытянутую чашу:

Поперёк оврага, по \(w_2\), кривизна равна 10; вдоль, по \(w_1\), — всего 0.2. На параболе с кривизной \(c\) спуск расходится при \(\eta \gt 2/c\) (так было в уроке 13), поэтому предел \(\eta \lt 0.2\) диктует крутая стенка. А вдоль дна один шаг проходит долю \(0.2\,\eta\) оставшегося пути: даже при \(\eta = 0.18\) это меньше 4 %.

Получается вилка. Большой \(\eta\) — зигзаг от стенки к стенке. Маленький \(\eta\) — зигзага нет, но вдоль дна спуск ползёт. Один общий шаг не подходит обоим направлениям.

Momentum даёт весам инерцию. Вместо шага по текущему градиенту заводят скорость \(\vb{v}\), которая помнит прошлые шаги:

Если развернуть рекурсию, скорость окажется суммой всех прошлых градиентов с убывающими весами:

Вдоль дна оврага все градиенты смотрят в одну сторону и складываются. При постоянном градиенте \(g\) с \(\eta\,g = 0.01\) и \(\alpha = 0.9\) сдвиги растут: 0.010, 0.019, 0.027, …, 0.065 на десятом шаге — и стремятся к пределу

в десять раз больше обычного шага. Поперёк оврага шар перелетает дно, градиент меняет знак, и его вклады в скорость гасят друг друга: качания затухают.

Шар не идеален: он тяжёлый и не умеет тормозить. Он раскачивается и может проскочить минимум. Поэтому с momentum берут \(\eta\) поменьше — скорость всё равно накопится.

У профессора momentum записан иначе, чем в конспекте. Формула стоит на двух слайдах: лекция 2, слайд 24, и лекция 3, слайд 38 (в углу напечатано 39). Второй называется "Recall about Backpropagation" и повторяет первый. Ошибка \(E(w)\) на обоих записана суммой квадратов без \(1/N\): постоянный множитель просто уходит в \(\eta\). Сравни:

Nesterov accelerated gradient: сначала прыжок, потом поправка

Слайд 38 лекции 3 заканчивается репликой в облачке:"Several variations exists beside these two ...". These two — обычный шаг спуска и momentum. Первая вариация стоит на следующем слайде (лекция 3, слайд 39; в углу напечатано 40): "Nesterov Accelerated gradient: make a jump as momentum, then adjust".

Тяжёлый шар решает, куда катиться, глядя под ноги на старте: градиент он меряет в точке \(w^k\), и к этому шагу прибавляется инерция. Nesterov accelerated gradient (NAG) меняет порядок. Сначала шар делает прыжок, который инерция всё равно заставит его сделать. Потом смотрит под ноги уже на новом месте и поправляет шаг.

Первая строка — прыжок (jump): то самое слагаемое с \(\alpha\) из формулы momentum, только сделанное отдельным ходом. Вторая — поправка (adjust): обычный шаг по градиенту, но градиент взят не в \(w^k\), а в точке после прыжка.

На рис. 4 видно, что это даёт. Прыжок вынес шар на противоположный склон. Градиент, взятый на старте, про этот склон ничего не знает и толкает шар дальше. Градиент, взятый после прыжка, уже смотрит назад и тормозит шар на этом же шаге, а не на следующем. Поэтому Nesterov меньше раскачивается и реже проскакивает минимум.

Теперь оба метода можно поставить рядом. Собери две строки Nesterov в одну и сравни с momentum:

Отличие в одном месте: в точке, где взят градиент при \(\eta\). У momentum порядок слагаемых не важен, оба посчитаны до того, как веса сдвинулись. У Nesterov важен: пока прыжок не сделан, нет точки для второго градиента.

В учебниках Nesterov записывают через скорость, как momentum в (85)–(86). Меняется одно: аргумент градиента.

Разница между столбцами та же, что у momentum: слайд берёт в прыжок один последний градиент, учебник — всю накопленную скорость. Слова в первом столбце взяты из подписи к картинке на слайде: "brown vector = jump, red vector = correction, green vector = accumulated gradient". Синие стрелки там — "standard momentum": короткий шаг по градиенту в текущей точке и за ним длинный прыжок.

На овраге с рис. 3 разница заметна сразу, если посчитать оба метода в записи через скорость. При тех же \(\eta = 0.05\) и \(\alpha = 0.9\) momentum перелетает дно до \(w_2 = -0.84\), Nesterov — только до \(-0.20\). Ошибка уходит ниже 0.01 насовсем на шаге 60 у momentum и на шаге 47 у Nesterov.

Свой шаг каждому весу: adaptive learning rates

Momentum и Nesterov оставляют один \(\eta\) на все веса. Вторая идея — дать каждому весу свой масштаб шага. Зачем это сети, видно из урока 24: градиенты в первых слоях бывают на порядки меньше, чем в последних, и \(\eta\), подходящий одним, не подходит другим.

У профессора этому отведён слайд "Adaptive Learning Rates" (лекция 3, слайд 40; в углу напечатано 41). Довод занимает четыре строки:

• "Neurons in each layer learn differently" — нейроны разных слоёв учатся по-разному;
• "Gradient magnitudes vary across layers" — величина градиента от слоя к слою разная;
• "Early layers get "vanishing gradients"" — до первых слоёв градиент доходит ослабленным;
• "Should ideally use separate adaptive learning rates" — в идеале шаг должен быть у каждого свой и подстраиваться сам.

Ниже на слайде список "Several algorithm proposed" из пяти имён: Rprop, AdaGrad, RMSprop, AdaDelta, Adam. Конспект разбирает только два из них — RMSprop (там он пишется RMSProp) и Adam. Пройдём все пять по порядку: каждый следующий чинит слабое место предыдущего.

Обозначим градиент по mini-batch на шаге \(k\) буквой \(\vb{g}_k\) (в конспекте \(g_t\); с выходом сети \(g(\vb{x}_n|\vb{w})\) не путать). Квадрат, корень и деление ниже выполняются отдельно для каждого веса.

Rprop (resilient propagation; Riedmiller и Braun, 1993) берёт от градиента только знак. У каждого веса свой размер шага \(\Delta\): вес сдвигается на \(\Delta\) против знака своего градиента. Если знак тот же, что на прошлом шаге, \(\Delta\) растёт (обычно в 1.2 раза). Если знак сменился — уменьшается вдвое.

Оврага Rprop не боится: величина градиента ему безразлична. Но ему нужен точный градиент по всему датасету. Представь вес, у которого девять mini-batch подряд дают градиент \(+0.1\), а десятый даёт \(-0.9\). В сумме ноль: вес должен стоять на месте. Rprop же девять раз сдвинет его в одну сторону, с каждым разом дальше: знак не меняется, и \(\Delta\) растёт. Десятый шаг вернёт лишь малую часть пути. Вес уедет.

AdaGrad (adaptive gradient; Duchi, Hazan и Singer, 2011) с mini-batch работает. Он копит для каждого веса сумму квадратов всех его прошлых градиентов и делит шаг на корень из этой суммы:

Вес с крупными градиентами получает маленький шаг, вес с мелкими — большой. Слабое место: сумма только растёт. При постоянном градиенте шаги идут так: \(\eta,\ \eta/\sqrt{2},\ \eta/\sqrt{3},\ \dots\) На сотом шаге остаётся десятая часть. Рано или поздно обучение замирает.

RMSprop (Tieleman и Hinton, 2012) заменяет сумму скользящим средним: старые квадраты понемногу забываются, и знаменатель перестаёт расти. Для каждого веса он помнит скользящее среднее квадратов его градиента и делит шаг на корень из этого среднего:

Вес с крупными градиентами делится на большое число, вес с мелкими — на маленькое. В итоге оба шагают примерно на \(\eta\).

На слайде про RMSprop сказано коротко: "SGD + Rprop". Это идея Rprop, переделанная под mini-batch. Rprop делит градиент на его собственный модуль, и остаётся знак. RMSprop делит на корень из среднего квадрата за последние шаги (root mean square — отсюда название), поэтому у соседних mini-batch делитель почти один и тот же. Проверь на примере с девятью \(+0.1\) и одним \(-0.9\). Корень из среднего квадрата за эти десять шагов:

Делим на него каждый градиент и складываем десять сдвигов:

Девять маленьких шагов и один большой гасят друг друга. Вес остаётся на месте, как и должен.

AdaDelta (Zeiler, 2012) появился в том же году и лечит AdaGrad тем же способом — скользящим средним квадратов градиента. И идёт на шаг дальше: вместо общего \(\eta\) он ставит корень из скользящего среднего квадратов прошлых сдвигов того же веса. Подбирать \(\eta\) руками не нужно.

Adam (adaptive moment estimation; Kingma и Ba, 2014) складывает обе идеи урока: скользящее среднее самих градиентов \(\vb{m}\) — как скорость в momentum — и скользящее среднее их квадратов \(\vb{v}\) — как \(\vb{s}\) в RMSprop. Коротко: Adam — это RMSprop плюс momentum.

Зачем шляпки, конспект не объясняет. Причина в старте с нуля: \(\vb{m}\) и \(\vb{v}\) начинают с нулевых значений, и первые средние занижены. Посмотрим на самый первый шаг для одного веса.

1. Приходит первый градиент \(g_1\). Средние стартовали с нуля, поэтому от него остаётся малая доля:

   \[ m_1 = 0.1\,g_1, \qquad v_1 = 0.001\,g_1^2 \]

2. Обе величины занижены: настоящее «среднее» по единственному градиенту равно \(g_1\), а не десятой его части. Делим на \(1 - \beta^{1}\) — поправка возвращает правильный масштаб:

   \[ \hat m_1 = \frac{0.1\,g_1}{1 - 0.9} = g_1 \] \[ \hat v_1 = \frac{0.001\,g_1^2}{1 - 0.999} = g_1^2 \]

3. Подставляем в шаг. Корень из квадрата — модуль:

   \[ \Delta w = -\eta\,\frac{g_1}{\abs{g_1} + \varepsilon} \approx -\eta \cdot \sign(g_1) \]

   Длина первого шага равна \(\eta\) и от величины градиента не зависит: при \(\eta = 0.001\) шаг будет 0.001 и для \(g_1 = 10\), и для \(g_1 = 0.001\).

4. Без поправки отношение получилось бы другим:

   \[ \frac{m_1}{\sqrt{v_1}} = \frac{0.1\,\abs{g_1}}{\sqrt{0.001}\,\abs{g_1}} \approx 3.16 \]

   Первый шаг был бы втрое длиннее задуманного. Дальше знаменатель \(1 - \beta^{\,k}\) стремится к единице, и поправка сама выключается. Для \(v\) с \(\beta_2 = 0.999\) на это уходит порядка тысячи шагов.

Первый шаг Adam по каждому весу равен \(\eta\) — каким бы ни был градиент.

Теперь вся семья в одной таблице. Читай её сверху вниз как цепочку: Rprop и AdaGrad — два предка, RMSprop берёт у первого идею и чинит второй, AdaDelta убирает \(\eta\), Adam добавляет momentum.

А вот как тот же список напечатан на слайде, дословно:

• "Resilient Propagation (Rprop – Riedmiller and Braun 1993)"
• "Adaptive Gradient (AdaGrad – Duchi et al. 2010)"
• "RMSprop (SGD + Rprop – Teileman and Hinton 2012)"
• "AdaDelta (Zeiler et at. 2012)"
• "Adam (Kingma and Ba, 2012)"

Слайд "Learning Rate Matters": шесть методов на двух картах

Лекция 3 заканчивается картинкой (лекция 3, слайд 41; в углу напечатано 42). На ней два кадра с одной и той же легендой из шести строк: SGD, Momentum, NAG, Adagrad, Adadelta, Rmsprop. NAG — это Nesterov accelerated gradient. Adam в легенде нет.

Слева — карта линий уровня ошибки, как в виджете выше, только рельеф сложнее: узкие долины с поворотом. Чёрная точка — общий старт, звезда — минимум. Справа — седло, saddle point из урока 13: вдоль одного направления поверхность поднимается, вдоль другого падает. Красная точка — старт, выше перевала.

В PDF оба кадра неподвижны: все шесть методов ещё стоят на старте. На странице CS231n из списка в конце урока те же две картинки движутся. Происходит на них вот что.

В долине Momentum и NAG разгоняются и проскакивают мимо, как шар на рис. 3. NAG возвращается на курс раньше: он берёт градиент после прыжка. Adagrad, Adadelta и RMSprop почти сразу поворачивают к минимуму, потому что каждый вес у них идёт своим шагом. SGD идёт в верную сторону, но медленнее всех.

На седле дорога от старта ведёт вниз, прямо к перевалу. SGD доходит до него и застревает надолго: градиент там почти нулевой, а шаг SGD пропорционален градиенту. Momentum и NAG тоже задерживаются, но в итоге скатываются. Adagrad, Adadelta и RMSprop уходят вниз быстро: маленький градиент они делят на его же маленький масштаб, и сдвиг получается обычного размера. Рис. 5 повторяет этот кадр на самом простом седле.

Название слайда — его вывод. От того, как метод распоряжается шагом, зависит, выберется ли он из трудного места и как быстро. Один \(\eta\) на все веса — слабое место обычного спуска. Momentum и NAG правят направление шага, adaptive learning rates — его масштаб у каждого веса. Левый кадр можно повторить в виджете выше: там тот же сюжет на овраге и ещё Adam, которого на слайде нет.

Schedule — не optimizer

Теперь всё можно разложить по полкам. В уроке было три разные ручки, и они не заменяют друг друга.

Ручки комбинируют. Adam сам содержит momentum, а поверх него обычно ставят ещё и расписание: Adam делит шаг между весами, расписание управляет общим \(\eta\). Так и написано на стр. 199 конспекта.

С чего начинать на практике? Стр. 199 конспекта советует Adam: он быстро приспосабливается, спокойно переносит шумные градиенты и хорошо работает с mini-batch. Обычное стартовое значение для него — \(\eta = 0.001\).

Карта главы 3 и весь рецепт

Вернёмся к кастрюле. Черпак в 100 раз больше ложки надёжнее только в 10 раз, потому что ошибка среднего падает как \(1/\sqrt{M}\). Поэтому сети учат ложками: много дешёвых, слегка неточных шагов вместо одного дорогого точного. Неточность лечат расписанием: к концу шаг укорачивают, и дрожание затихает. А тяжёлый шар — это momentum: в овраге, где обычный спуск мечется или ползёт, шар копит скорость вдоль дна.

Это был последний инструмент главы 3. Вся глава отвечает на три вопроса — посмотри, как по ним раскладываются одиннадцать уроков.

И тот же материал в том порядке, в котором им пользуются. Это рецепт обучения сети целиком:

1. Раздели данные на training, validation и test set (урок 18); если данных мало — cross-validation (урок 19).
2. Выбери архитектуру и выходной слой под задачу (урок 11); в скрытых слоях — ReLU (урок 24).
3. Задай начальные веса: He для ReLU, Xavier для tanh (урок 25); между линейным слоем и активацией поставь batch normalization (урок 26).
4. Возьми error function из maximum likelihood (урок 15) и добавь регуляризацию: weight decay (урок 22), dropout (урок 23).
5. Обучай по mini-batch: градиент считает backpropagation (урок 14), шаг делает Adam или SGD с momentum, \(\eta\) идёт по расписанию (этот урок).
6. Следи за ошибкой на validation set и остановись вовремя: early stopping (урок 20).
7. Подбери hyperparameters — \(\eta\), \(M\), силу регуляризации — по validation, а не по test (урок 21).
8. Один раз, в самом конце, измерь ошибку на test set. Это и есть честная оценка generalization (уроки 17 и 18).

Каждая строка — готовый вопрос вида «why do we…?». Если на любой из них получается ответить двумя-тремя предложениями по-английски, глава 3 у тебя в руках.