Методы оптимизации нейронных сетей
В подавляющем большинстве источников информации о нейронных сетях под «а теперь давайте обучим нашу сеть» понимается «скормим целевую функцию оптимизатору» лишь с минимальной настройкой скорости обучения. Иногда говорится, что обновлять веса сети можно не только стохастическим градиентным спуском, но безо всякого объяснения, чем же примечательны другие алгоритмы и что означают загадочные и в их параметрах. Даже преподаватели на курсах машинного обучения зачастую не заостряют на этом внимание. Я бы хотел исправить недостаток информации в рунете о различных оптимизаторах, которые могут встретиться вам в современных пакетах машинного обучения. Надеюсь, моя статья будет полезна людям, которые хотят углубить своё понимание машинного обучения или даже изобрести что-то своё.
Под катом много картинок, в том числе анимированных gif.
Статья ориентирована на знакомого с нейронными сетями читателя. Предполагается, что вы уже понимаете суть backpropagation и SGD. Я не буду вдаваться в строгое доказательство сходимости представленных ниже алгоритмов, а наоборот, постараюсь донести их идеи простым языком и показать, что формулы открыты для дальнейших экспериментов. В статье перечислены далеко не все сложности машинного обучения и далеко не все способы их преодолевать.
Зачем нужны ухищрения
Напомню, как выглядят формулы для обычного градиентного спуска:
где — параметры сети, — целевая функция или функция потерь в случае машинного обучения, а — скорость обучения. Выглядит удивительно просто, но много магии сокрыто в — обновить параметры выходного слоя довольно просто, но чтобы добраться до параметров слоёв за ним, приходится проходить через нелинейности, производные от которых вносят свой вклад. Это знакомый вам принцип обратного распространения ошибки — backpropagation.
Явно расписанные формулы для обновления весов где-нибдуь в середине сети выглядят страшненько, ведь каждый нейрон зависит ото всех нейронов, с которымии он связан, а те — ото всех нейронов, с которыми связаны они, и так далее. При этом даже в «игрушечных» нейронных сетях может быть порядка 10 слоёв, а среди сетей, удерживающих олимп классифицирования современных датасетов — намного, намного больше. Каждый вес — переменная в . Такое невероятное количество степеней свободы позволяет строить очень сложные отображения, но приносит исследователям головную боль:
- Застревание в локальных минимумах или седловых точках, коих для функции от переменных может быть очень много.
- Сложный ландшафт целевой функции: плато чередуются с регионами сильной нелинейности. Производная на плато практически равна нулю, а внезапный обрыв, наоборот, может отправить нас слишком далеко.
- Некоторые параметры обновляются значительно реже других, особенно когда в данных встречаются информативные, но редкие признаки, что плохо сказывается на нюансах обобщающего правила сети. С другой стороны, придание слишком большой значимости вообще всем редко встречающимся признакам может привести к переобучению.
- Слишком маленькая скорость обучения заставляет алгоритм сходиться очень долго и застревать в локальных минимумах, слишком большая — «пролетать» узкие глобальные минимумы или вовсе расходиться
Вычислительной математике известны продвинутые алгоритмы второго порядка, которым под силу найти хороший минимум и на сложном ландшафте, но тут удар снова наносит количество весов. Чтобы воспользоваться честным методом второго порядка «в лоб», придётся посчитать гессиан — матрицу производных по каждой паре параметров пары параметров (уже плохо) — а, скажем, для метода Ньютона, ещё и обратную к ней. Приходится изобретать всяческие ухищрения, чтобы справиться с проблемами, оставляя задачу вычислительно подъёмной. Рабочие оптимизаторы второго порядка существуют, но пока что давайте сконцентрируемся на том, что мы можем достигнуть, не рассматривая вторые производные.
Nesterov Accelerated Gradient
Сама по себе идея методов с накоплением импульса до очевидности проста: «Если мы некоторое время движемся в определённом направлении, то, вероятно, нам следует туда двигаться некоторое время и в будущем». Для этого нужно уметь обращаться к недавней истории изменений каждого параметра. Можно хранить последние экземпляров и на каждом шаге по-честному считать среднее, но такой подход занимает слишком много памяти для больших . К счастью, нам и не нужно точное среднее, а лишь оценку, поэтому воспользуемся экспоненциальным скользящим средним.
Чтобы накопить что-нибудь, будем умножать уже накопленное значение на коэффициент сохранения и прибавлять очередную величину, умноженную на . Чем ближе к единице, тем больше окно накопления и сильнее сглаживание — история начинает влиять сильнее, чем каждое очередное . Если c какого-то момента, затухают по геометрической прогрессии, экспоненциально, отсюда и название. Применим экспоненциальное бегущее среднее, чтобы накапливать градиент целевой функции нашей сети:
Где обычно берётся порядка . Обратите внимание, что не пропало, а включилось в ; иногда можно встретить и вариант формулы с явным множителем. Чем меньше , тем больше алгоритм ведёт себя как обычный SGD. Чтобы получить популярную физическую интерпретацию уравнений, представьте как шарик катится по холмистой поверхности. Если в момент под шариком был ненулевой уклон ( ), а затем он попал на плато, он всё равно продолжит катиться по этому плато. Более того, шарик продолжит двигаться пару обновлений в ту же сторону, даже если уклон изменился на противоположный. Тем не менее, на шарик действует вязкое трение и каждую секунду он теряет своей скорости. Вот как выглядит накопленный импульс для разных (здесь и далее по оси X отложены эпохи, а по Y — значение градиента и накопленные значения):
Заметьте, что накопленное в значение может очень сильно превышать значение каждого из . Простое накопление импульса уже даёт хороший результат, но Нестеров идёт дальше и применяет хорошо известную в вычислительной математике идею: заглядывание вперёд по вектору обновления. Раз уж мы всё равно собираемся сместиться на , то давайте посчитаем градиент функции потерь не в точке , а в . Отсюда:
Такое изменение позволяет быстрее «катиться», если в стороне, куда мы направляемся, производная увеличивается, и медленнее, если наоборот. Особенно этого хорошо видно для для графика с синусом.
Заглядывание вперёд может сыграть с нами злую шутку, если установлены слишком большие и : мы заглядываем настолько далеко, что промахиваемся мимо областей с противоположным знаком градиента:
Впрочем, иногда такое поведение может оказаться желательным. Ещё раз обращу ваше внимание на идею — заглядывание вперёд — а не на исполнение. Метод Нестерова (6) — самый очевидный вариант, но не единственный. Например, можно воспользоваться ещё одним приёмом из вычислительной математики — стабилизацией градиента усреднением по нескольким точкам вдоль прямой, по которой мы двигаемся. Скажем, так:
Такой приём может помочь в случае шумных целевых функций.
Мы не будем манипулировать аргументом целевой функции в последующих методах (хотя вам, разумеется, никто не мешает поэкспериментировать). Далее для краткости
Adagrad
Как работают методы с накоплением импульса представляют себе многие. Перейдём же к более интересным алгоритмам оптимизации. Начём со сравнительно простого Adagrad — adaptive gradient.
Некоторые признаки могут быть крайне информативными, но встречаться редко. Экзотическая высокооплачиваемая профессия, причудливое слово в спам-базе — они запросто потонут в шуме всех остальных обновлений. Речь идёт не только о редко встречающихся входных параметрах. Скажем, вам вполне могут встретиться редкие графические узоры, которые и в признак-то превращаются только после прохождения через несколько слоёв свёрточной сети. Хорошо бы уметь обновлять параметры с оглядкой на то, насколько типичный признак они фиксируют. Достичь этого несложно: давайте будем хранить для каждого параметра сети сумму квадратов его обновлений. Она будет выступать в качестве прокси для типичности: если параметр принадлежит цепочке часто активирующихся нейронов, его постоянно дёргают туда-сюда, а значит сумма быстро накапливается. Перепишем формулу обновления вот так:
Где — сумма квадратов обновлений, а — сглаживающий параметр, необходимый, чтобы избежать деления на 0. У часто обновлявшегося в прошлом параметра большая , значит большой знаменатель в (12). Параметр изменившийся всего раз или два обновится в полную силу. берут порядка или для совсем агрессивного обновления, но, как видно из графиков, это играет роль только в начале, ближе к середине обучение начинает перевешивать :
Итак, идея Adagrad в том, чтобы использовать что-нибудь, что бы уменьшало обновления для элементов, которые мы и так часто обновляем. Никто нас не заставляет использовать конкретно эту формулу, поэтому Adagrad иногда называют семейством алгоритмов. Скажем, мы можем убрать корень или накапливать не квадраты обновлений, а их модули, или вовсе заменить множитель на что-нибудь вроде .
(Другое дело, что это требует экспериментов. Если убрать корень, обновления начнут уменьшаться слишком быстро, и алгоритм ухудшится)
Ещё одно достоинство Adagrad — отсутствие необходимости точно подбирать скорость обучения. Достаточно выставить её в меру большой, чтобы обеспечить хороший запас, но не такой громадной, чтобы алгроритм расходился. По сути мы автоматически получаем затухание скорости обучения (learning rate decay).
RMSProp и Adadelta
Недостаток Adagrad в том, что в (12) может увеличиваться сколько угодно, что через некоторое время приводит к слишком маленьким обновлениям и параличу алгоритма. RMSProp и Adadelta призваны исправить этот недостаток.
Модифицируем идею Adagrad: мы всё так же собираемся обновлять меньше веса, которые слишком часто обновляются, но вместо полной суммы обновлений, будем использовать усреднённый по истории квадрат градиента. Снова используем экспоненциально затухающее бегущее среднее (4). Пусть — бегущее среднее в момент
тогда вместо (12) получим
Знаменатель есть корень из среднего квадратов градиентов, отсюда RMSProp — root mean square propagation
Обратите внимание, как восстанавливается скорость обновления на графике с длинными зубцами для разных . Также сравните графики с меандром для Adagrad и RMSProp: в первом случае обновления уменьшаются до нуля, а во втором — выходят на определённый уровень.
Вот и весь RMSProp. Adadelta от него отличается тем, что мы добавляем в числитель (14) стабилизирующий член пропорциональный от . На шаге мы ещё не знаем значение , поэтому обновление параметров происходит в три этапа, а не в два: сначала накапливаем квадрат градиента, затем обновляем , после чего обновляем .
Такое изменение сделано из соображений, что размерности и должны совпадать. Заметьте, что learning rate не имеет размерности, а значит во всех алгоритмах до этого мы складывали размерную величину с безразмерной. Физики в этом месте ужаснутся, а мы пожмём плечами: работает же.
Заметим, что нам нужен ненулевой для первого шага, иначе все последующие , а значит и будут равны нулю. Но эту проблему мы решили ещё раньше, добавив в . Другое дело, что без явного большого мы получим поведение, противоположное Adagrad и RMSProp: мы будем сильнее (до некоторого предела) обновлять веса, которые используются чаще. Ведь теперь чтобы стал значимым, параметр должен накопить большую сумму в числителе дроби.
Вот графики для нулевого начального :
А вот для большого:
Впрочем, похоже, авторы алгоритма и добивались такого эффекта. Для RMSProp и Adadelta, как и для Adagrad не нужно очень точно подбирать скорость обучения — достаточно прикидочного значения. Обычно советуют начать подгон c , a так и оставить . Чем ближе к , тем дольше RMSProp и Adadelta с большим будут сильно обновлять мало используемые веса. Если же и , то Adadelta будет долго «с недоверием» относиться к редко используемым весам. Последнее может привести к параличу алгоритма, а может вызвать намеренно «жадное» поведение, когда алгоритм сначала обновляет нейроны, кодирующие самые лучшие признаки.
Adam — adaptive moment estimation, ещё один оптимизационный алгоритм. Он сочетает в себе и идею накопления движения и идею более слабого обновления весов для типичных признаков. Снова вспомним (4):
От Нестерова Adam отличается тем, что мы накапливаем не , а значения градиента, хотя это чисто косметическое изменение, см. (23). Кроме того, мы хотим знать, как часто градиент изменяется. Авторы алгоритма предложили для этого оценивать ещё и среднюю нецентрированную дисперсию:
Легко заметить, что это уже знакомый нам , так что по сути тут нет отличий от RMSProp.
Важное отличие состоит в начальной калибровке и : они страдают от той же проблемы, что и в RMSProp: если задать нулевое начальное значение, то они будут долго накапливаться, особенно при большом окне накопления ( , ), а какие-то изначальные значения — это ещё два гиперпараметра. Никто не хочет ещё два гиперпараметра, так что мы искусственно увеличиваем и на первых шагах (примерно для и для )
В итоге, правило обновления:
Здесь следует внимательно посмотреть на то, как быстро синхронизировались значения обновлений на первых зубцах графиков с прямоугольниками и на гладкость кривой обновлений на графике с синусом — её мы получили «бесплатно». При рекомендуемом параметре на графике с шипами видно, что резкие всплески градиента не вызывает мгновенного отклика в накопленном значении, поэтому хорошо настроенному Adam не нужен gradient clipping.
Авторы алгоритма выводят (22), разворачивая рекурсивные формулы (20) и (21). Например, для :
Слагаемое близко к при стационарном распределении , что неправда в практически интересующих нас случаях. но мы всё равно переносим скобку с влево. Неформально, можно представить что при у нас бесконечная история одинаковых обновлений:
Когда же мы получаем более близкое к правильному значение , мы заставляем «виртуальную» часть ряда затухать быстрее:
Авторы Adam предлагают в качестве значений по умолчанию и утверждают, что алгоритм выступает лучше или примерно так же, как и все предыдущие алгоритмы на широком наборе датасетов за счёт начальной калибровки. Заметьте, что опять-таки, уравнения (22) не высечены в камне. У нас есть некоторое теоретическое обоснование, почему затухание должно выглядеть именно так, но никто не запрещает поэкспериментировать с формулами калибровки. На мой взгляд, здесь просто напрашивается применить заглядывание вперёд, как в методе Нестерова.
Adamax
Adamax как раз и есть такой эксперимент, предложенный в той же статье. Вместо дисперсии в (21) можно считать инерционный момент распределения градиентов произвольной степени . Это может привести к нестабильности к вычислениям. Однако случай , стремящейся к бесконечности, работает на удивление хорошо.
Заметьте, что вместо используется подходящий по размерности . Кроме того, обратите внимание, чтобы использовать в формулах Adam значение, полученное в (27), требуется извлечь из него корень: . Выведем решающее правило взамен (21), взяв , развернув под корнем при помощи (27):