Градиентный спуск

Перед вами горы к югу от Алматы — тридцать с лишним километров от окраин города до главного хребта; высоты — из радарной съёмки NASA с борта шаттла Endeavour в 2000 году. Нажмите на карту в любом месте, и оттуда покатится точка. Она не видит карты целиком: на каждом шаге она знает только уклон у себя под ногами и делает шаг туда, где склон круче всего уходит вниз. Это и есть градиентный спуск — способ, которым ищут минимум функции, когда формулы для ответа нет.

Первая точка стартует с пика Большой Алматинский, с высоты 3620 метров, и до города не доходит: на высоте 1271 метр, в долине, она начинает прыгать на месте. Попробуйте другие шаги. Осторожный шаг застревает ещё выше, на 1654 метрах, огромный хаотично перескакивает через хребты, а точка с инерцией спускается почти до равнины — до 749 метров. Нажмите «Дождь»: из полутора сотен капель за край карты уходит полтора десятка, остальные застревают. Почему так и что с этим делают — ниже.

Идея

Пусть функция f зависит от нескольких чисел — здесь от двух координат точки, а у нейросети от миллиардов весов. Её градиент ∇f — вектор из частных производных: насколько быстро растёт f, если чуть сдвинуться по каждой координате. Он смотрит в сторону самого крутого подъёма, и его длина равна крутизне.

Если не знаешь, где минимум, но умеешь мерить склон под ногами, — шагай против градиента: x ← x − η∇f(x). Небольшой шаг в эту сторону всегда уменьшает функцию, а повторяя шаги, точка сползает в яму.

Почему уменьшает: при маленьком шаге функция почти линейна, f(x − η∇f) ≈ f(x) − η·|∇f|², и вычитаемое положительно, пока градиент не ноль. Число η — длина шага; в сцене это «метров пути на единицу уклона», так что на склоне крутизной 0,5 при η = 300 точка проходит 150 метров. Длина шага сама меняется вместе с крутизной: на крутом склоне точка мчится, на пологом ползёт, а там, где ровно, останавливается.

Спуск находит не самый низкий, а ближайший минимум — точку, где градиент обратился в ноль. На гладкой выпуклой функции, вроде суммы квадратов промахов линейной регрессии, это одно и то же. На горах — нет.

Откуда берётся градиент

Высоты в сцене — таблица: 201 × 201 точка через каждые 163–167 метров. Между узлами высоту достраивают по четырём соседям: вдоль северной стороны клетки — прямая, вдоль южной — другая, а между ними — третья. Такая функция называется билинейной, и её производные пишутся одной строкой. Листинг ниже делает ровно это, и сцена считает так же.

Когда функция задана формулой, производные выводят по правилам анализа. У нейросети формула — длинная цепочка простых действий, и градиент по всем весам сразу находит обратное распространение: проход по цепочке от конца к началу стоит лишь в несколько раз дороже, чем само вычисление функции. А вот посчитать градиент «в лоб», сдвигая каждую переменную по очереди, стоит d + 1 вычисление функции на шаг: для двух координат это пустяк, для миллиарда весов — неподъёмно.

Шаг

Вся настройка спуска — одно число η, и оно решает всё. Листинг пускает точку с трёх мест четырьмя способами и печатает, где она остановилась:

Big Almaty Peak, 3620 m
  step   30                 stuck at 1654 m after 2391 steps
  step  300                 stuck at 1271 m after 729 steps
  step 3000                 stuck at 802 m after 430 steps
  step  300, momentum 0.9   stuck at 749 m after 547 steps

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

Есть и точная граница. Вблизи минимума любая гладкая функция похожа на чашу, и у чаши есть наибольшая кривизна L — крутизна изгиба в самом крутом направлении. Если η > 2/L, каждый шаг перелетает дно и попадает на противоположный склон выше, чем был: спуск разлетается. Доказательство для чаши с осями вдоль координат есть в «Царице наук», а для повёрнутой чаши — в первой задаче статьи.

Овраг

Хуже всего спуску в овраге: стенки крутые, дно пологое. Шаг, безопасный для стенок, на дне слишком мал, и точка мечется от стенки к стенке, медленно сползая вдоль. В сцене это видно в долинах: путь становится пилой. Насколько это плохо, говорит отношение наибольшей кривизны к наименьшей — число обусловленности κ = L/μ. На функции (x² + κy²)/2 с лучшим постоянным шагом 2/(1 + κ) спуску нужно примерно κ шагов на каждое уменьшение ошибки в e² ≈ 7,4 раза, а до точности 10⁻⁶ при κ = 100 — 709 шагов. Вытяните овраг в сто раз — шагов станет в сто раз больше.

Тяжёлый шарик

Настоящий шарик в овраге ведёт себя умнее точки: он разгоняется вдоль дна, а метания поперёк гасит собственная инерция. В 1964 году Борис Поляк предложил дать спуску то же самое — скорость, которая помнит прошлые шаги:

Это метод тяжёлого шарика, в машинном обучении его зовут momentum. При β = 0 это обычный спуск. При β = 0,9 там, где градиент много шагов подряд смотрит в одну сторону, скорость накапливается почти в 1/(1 − β) = 10 раз; там, где он меняет знак через шаг — поперёк оврага, — соседние толчки гасят друг друга.

Для квадратичной функции Поляк нашёл лучшие параметры: η = 4/(√L + √μ)², β = ((√L − √μ)/(√L + √μ))². С ними число шагов растёт не как κ, а как √κ:

 kappa   plain  momentum  ratio
    10      71        27    2.6
   100     709        95    7.5
  1000    7082       321   22.1
 10000   70811      1074   65.9

При κ = 10 000 — 1074 шага вместо 70 811. Заметьте, что шаг η у шарика больше, чем 2/L: без инерции с таким шагом спуск разлетелся бы, а с ней — нет.

Ямы

Вернитесь к горам и нажмите «Дождь». Капли застревают в ямах — местах, где градиент со всех сторон смотрит вверх. На настоящем рельефе их сотни: котловина Большого Алматинского озера, неровности дна долин, крыши и деревья города, которые радар снимал вместе с землёй. Вода в такой яме поднималась бы, пока не перельётся через край, и стекала бы дальше. Спуск так не умеет: он видит только склон под ногами, а в яме склон со всех сторон ведёт обратно.

Отсюда все обычные средства. Запускают спуск много раз из разных мест и берут лучший результат. Добавляют инерцию: шарик с разгону проскакивает мелкие ямки, но может проскочить и нужную. Добавляют шум — об этом ниже. Есть и задачи, где ям нет вовсе: у выпуклой функции, как сумма квадратов промахов, единственный минимум, и спуск находит его из любой точки. При обучении нейросетей функция не выпуклая, но, по наблюдениям Яна Дофена и соавторов (2014), в пространствах из миллионов переменных точки с нулевым градиентом чаще оказываются сёдлами — по одним направлениям вниз, по другим вверх, — чем ямами, и мешают спуску в основном пологие плато вокруг таких сёдел.

Код

Первый листинг — спуск по настоящему рельефу. Высоты лежат на сервере, где исполняется код, той же сеткой, что в сцене. Функция height_and_slope — билинейная высота и её градиент, descend — сам спуск с инерцией (при β = 0 — без неё).

Когда остановиться? У гладкой функции — когда градиент почти ноль. У рельефа из клеток это не работает: в яме точка с большим шагом вечно прыгает со стенки на стенку, и градиент у неё под ногами не убывает. Поэтому листинг сравнивает среднее положение за последние сто шагов со средним положением двумя сотнями шагов раньше. Если они почти совпали, точка топчется на месте. Медленное сползание по дну оврага так не выглядит: среднее положение у него смещается.

Второй листинг — овраг (x² + κy²)/2 из виджета выше: обычный спуск с лучшим постоянным шагом против шарика Поляка, и что бывает с шагом больше 2/L.

Сколько это стоит

Шаг стоит одного вычисления градиента: для формулы с d переменными это обычно O(d) действий, для нейросети — примерно как два-три прохода по ней. Память — O(d): точка, градиент и, для шарика, скорость.

Число шагов зависит от функции. Для гладкой функции с одной чашей-минимумом (сильно выпуклой) и постоянного шага ошибка убывает в геометрической прогрессии со знаменателем около 1 − 2/κ, и до точности ε нужно O(κ·log(1/ε)) шагов. Шарик Поляка на квадратичной функции и метод Нестерова на любой гладкой сильно выпуклой дают O(√κ·log(1/ε)). Если функция выпукла, но чаша вырождается, гарантия слабее: ошибка убывает как 1/k у обычного спуска и как 1/k² у метода Нестерова. Для невыпуклых функций гарантируют только одно — что спуск дойдёт до точки, где градиент мал; будет ли это дно, седло или яма на полпути, теория не обещает.

Отсюда главный практический совет, который не про шаг, а про данные: сделать овраг круглее. В задачах вроде регрессии для этого сдвигают столбцы к нулю и выравнивают их масштаб. В первой задаче статьи видно, как сильно это меняет κ на настоящих данных: для прямой через среднегодовые температуры Алматы — с 2,6·10¹⁰ до 602.

Шум вместо точности

Функция потерь нейросети — сумма промахов по миллионам примеров, и честный градиент требует пройти по всем. Вместо этого берут случайную пачку из нескольких десятков примеров и считают градиент по ней: он неточен, зато в тысячи раз дешевле. Это стохастический градиентный спуск. Его корни — в работе Герберта Роббинса и Саттона Монро 1951 года о стохастической аппроксимации: там доказано, что шум не мешает дойти до цели, если шаг уменьшать — так, чтобы сумма шагов была бесконечной, а сумма их квадратов конечной.

Шум и сам бывает полезен: он сбрасывает точку с плато и выталкивает из мелких ям — так же, как огромный шаг в сцене, только мягче. Популярный сегодня метод Adam (Дидерик Кингма и Джимми Ба, 2014) добавляет к инерции ещё одну мысль: подбирать длину шага отдельно для каждой переменной, по тому, насколько сильно и часто менялся её градиент. Овраг, вытянутый вдоль одной из осей, такой метод почти выравнивает.

История

Метод предложил Огюстен Луи Коши в трёхстраничной заметке 1847 года в «Comptes rendus» Академии наук. Ему нужно было вычислять орбиты небесных тел: шесть неизвестных элементов орбиты из системы уравнений движения. Коши свёл систему к поиску минимума суммы квадратов невязок и предложил идти к нему маленькими шагами против градиента. Обещанное в заметке продолжение с подробностями так и не вышло.

Инерцию добавил Борис Поляк в 1964 году, ускорение с гарантией нашёл Юрий Нестеров в 1983-м. А когда в 1980-х научились быстро считать градиент нейросети обратным распространением, спуск стал главным способом обучения моделей: сегодня нейросети обучают почти исключительно его вариантами.

Задачи

В первой задаче нужно заранее, не делая ни одного шага, сказать, какой шаг безопасен: овраг повёрнут, и граница из «Царицы наук» не подходит. Во второй спуск идёт по функции с изломами — сумме расстояний до мест, — и шаг подбирается сам.