Случайные эволюционные стратегии в машинном обучении
Нейронные сети учатся совсем не так как люди. Оптимизация нейронной сети — на самом деле градиентный спуск по некоторой функции потерь $inline$E (\theta)$inline$, где переменными являются веса слоёв $inline$\theta$inline$. Это очень мощный подход к подстройке системы, который применяется также в физике, экономике и многих других областях. На данный момент предложено немало конкретных методов градиентного спуска, но все они предполагают, что градиент $inline$E (\theta)$inline$ хорошо себя ведёт: нет обрывов, где он скачкообразно возрастает, или плато, где он обращается в ноль. С первой проблемой можно разобраться при помощи gradient clipping, но вторая заставляет тщательно подумать. Кусочно-линейную или дискретную функцию нетривиально ограничить более приятной функцией
- во многих областях reinforcement learning (далее RL)
- в VAE с дискретными латентными переменными
- в GAN с дискретными генераторами
Как поступать в таких ситуациях? 
Под катом много формул и гифок.
Около пяти лет назад началипоявляться статьи, исследующие другой подход к обучению: вместо сглаживания целевой функции, давайте в таких случаях приближённо считать градиент. Определённым образом сэмплируя значения $inline$E (\theta)$inline$, можно предположить, куда следует двигаться, даже если в текущей точке производная ровно ноль. Не то чтобы подходы с сэмплированием были особо новы — Монте-Карло уже много времени дружит с нейронными сетями —, но недавно были получены новые интересные результаты.
За основу этой статьи были взяты записи в блоге Ferenc Huszár.
Random Evolution Strategy (ES)
Начнём с самого простого подхода, который вновь обрёл популярность после статьи OpenAI в 2017. Замечу, что у эволюционных стратегий не слишком удачное имя, связанное с развитием этого семейства алгоритмов. С генетическими алгоритмами ES связаны очень отдалённо — лишь случайным изменением параметров. Гораздо продуктивнее думать о ES, как о методе оценки градиента при помощи сэмплирования. Мы сэмплируем из нормального распределения $inline$\mathbb{N}(0, \sigma)$inline$ несколько векторов пертурбаций $inline$\epsilon$inline$, берём матожидание от получившихся значений целевой функции, и считаем, что
$$display$$\frac{\delta}{\delta\theta}E (\theta) \approx \frac{1}{\sigma^2} \mathbb{E}_{\epsilon \sim \mathbb{N}(0, \sigma)} [\epsilon E (\theta + \epsilon) ] $$display$$
Идея довольно проста. При стандартном градиентном спуске мы на каждом шаге смотрим наклон поверхности, на которой находимся, и двигаемся в сторону наибольшего уклона. В ES мы «обстреливаем» близлежащую окрестность точками, куда мы можем предположительно двинуться, и перемещаемся в сторону, куда попало больше всего точек с наибольшей разницей высот (причём, чем дальше точка, тем больший ей придаётся вес).
Доказательство тоже несложное. Предположим, что на самом деле функцию потерь можно разложить в ряд Тейлора в $inline$\theta$inline$:
$$display$$ E (\theta + \epsilon) = E (\theta) + E'(\theta)\epsilon + \frac{E''(\theta)\epsilon^2}{2} + O (\epsilon^3)$$display$$
Умножим обе стороны на $inline$\epsilon$inline$:
$$display$$ E (\theta + \epsilon)\epsilon = E (\theta)\epsilon + E'(\theta)\epsilon^2 + \frac{E''(\theta)\epsilon^3}{2} + O (\epsilon^4)$$display$$
Отбросим $inline$O (\epsilon^4)$inline$ и возьмём матожидание от обоих сторон:
$$display$$ \mathbb{E}_{\epsilon \sim \mathbb{N}(0, \sigma)}[E (\theta + \epsilon)\epsilon] = \mathbb{E}_{\epsilon \sim \mathbb{N}(0, \sigma)}[E (\theta)\epsilon + E'(\theta)\epsilon^2 + \frac{E''(\theta)\epsilon^3}{2}]$$display$$
Но нормальное распределение симметрично: $inline$\mathbb{E}_{\epsilon \sim \mathbb{N}(0, \sigma)}[\epsilon] = 0$inline$, $inline$\mathbb{E}_{\epsilon \sim \mathbb{N}(0, \sigma)}[\epsilon^2] = \sigma^2$inline$, $inline$\mathbb{E}_{\epsilon \sim \mathbb{N}(0, \sigma)}[\epsilon^3] = 0$inline$:
$$display$$ \mathbb{E}_{\epsilon \sim \mathbb{N}(0, \sigma)}[E (\theta + \epsilon)\epsilon] = E'(\theta)\sigma^2$$display$$
Поделим на $inline$\sigma^2$inline$ и получим исходное утверждение.
В случае кусочно-ступенчатой функции получившаяся оценка $inline$\frac{\delta}{\delta\theta}E (\theta)$inline$ будет представлять градиент сглаженной функции без надобности вычислять конкретные значения этой функции в каждой точке; в статье даны более строгие утверждения. Также в случае, когда функция потерь зависит от дискретных параметров $inline$x$inline$ (т.е. $inline$E (\theta) = \mathbb{E}_{x}E (\theta, x)$inline$), можно показать что оценка остаётся справедливой, так как при доказательстве можно поменять местами порядок взятия матожидания
$$display$$ \mathbb{E}_{\epsilon}\epsilon E (\theta + \epsilon) = \mathbb{E}_{\epsilon}\epsilon \mathbb{E}_{x} E (\theta + \epsilon, x) = \mathbb{E}_{x} \mathbb{E}_{\epsilon} \epsilon E (\theta + \epsilon, x)$$display$$
Что часто невозможно для обычного SGD.
Посмотрим на функцию, сглаженную при помощи сэмплирования из $inline$\mathbb{N}(0, \sigma)$inline$. Ещё раз: в действительности нет смысла считать $inline$E (\theta)$inline$, нам нужны лишь производные. Однако, подобные визуализации помогают понять, по какому ландшафту реально производится градиентный спуск. Итак, зелёный график — исходная функция, синий — как она выглядит для алгоритма оптимизации после оценки градиента сэмплированием:
$inline$\sigma = 0.35$inline$: 
$inline$\sigma = 0.2$inline$: 
$inline$\sigma = 0.1$inline$: 
Чем больше сигма распределения, тем меньше проявляет себя локальная структура функции. При слишком большом размахе сэмплирования алгоритму оптимизации не видны узкие минимумы и ложбины, по которым можно перейти из одного хорошего состояния в другое. При слишком малом — градиентный спуск может так и не стартовать, если точка инициализации была выбрана неудачно.
Больше графиков: 
Градиентный спуск автоматически находит самый устойчивый минимум на середине плато и «туннелирует» сквозь резкий пик.
Достоинства такого подхода по сравнению с обычным градиентным спуском:
- Как уже упоминалось, $inline$E (\theta)$inline$ не обязана быть дифференцируемой. В то же время, никто не запрещает применять ES даже когда можно честно посчитать градиент.
- ES тривиально параллелится. Хоть и существуют параллельные версии SGD, они требуют пересылать веса $inline$\theta_i$inline$ между нодами-рабочими или нодами и центральным сервером. Это очень затратно, когда слоёв много. В случае эволюционных стратегий каждая из рабочих станций может считать свой набор $inline$E_i = E (\theta + \epsilon_i)$inline$. Переслать $inline$E_i$inline$ довольно просто — обычно это просто скаляры. $inline$\epsilon_i$inline$ пересылать так же сложно как и $inline$\theta$inline$, однако делать этого нет надобности: если всем нодам известен алгоритм сэмплирования случайных чисел и seed генератора, они могут симулировать $inline$\epsilon_i$inline$друг друга! Производительность такой системы увеличивается почти что линейно при масштабировании, что делает распределенную версию ES просто невероятно быстрой, когда доступно большое число станций для проведения обучения. OpenAI рапортует об обучении MuJoCo за 10 минут на 80 машинах с 1440 CPU.
- Сэмплирование $inline$\theta$inline$ вносит шум в вычисление градиента, что делает обучение более устойчивым. Сравните с dropout’ом при обучении нейронных сетей обычным образом.
- ES не зависит от frame-skip при RL (см. например здесь) — одним гиперпараметром меньше.
- Также утверждается, что эволюционные стратегии позволяют проводить обучение легче, чем обычный SGD, когда между действием в RL и положительным откликом может пройти большое количество времени, и в шумных условиях, когда непонятно, какое изменение помогло улучшить результат (меньше проявляет себя ситуация, когда сеть в начале обучения долго не может понять, что нужно делать в виртуальном окружении и лишь дёргается на месте).
Какие же недостатки?
- Графики в статье OpenAI выглядят не так уж чтобы лучезарно. Обучение при помощи ES занимает в 2–10 раз больше эпох, чем обучение при помощи TRPO. Авторы защищаются тем, что когда доступно большое число рабочих машин затраченное реальное время оказывается в 20–60 раз меньше (хоть каждое обновление приносит меньше пользы, мы можем делать их гораздо чаще). Здорово, конечно, но где бы ещё взять 80 рабочих нод. Плюс, как будто бы итоговые результаты немного хуже. Наверное, можно «добить» сеть более точным алгоритмом?
- Шум в градиентах — палка о двух концах. Даже при одномерной оптимизации они оказываются слегка нестабильными (см. шум на синих кривых на графиках выше), что уж там говорить, когда $inline$\theta$inline$ очень многомерный. Пока что непонятно, насколько серьёзную проблему это представляет, и что с этим можно сделать, кроме как увеличить размер выборки сэмплирования.
- Неизвестно, можно ли эффективно применить ES в обычном обучении с учителем. OpenAI честно сообщает, что на обычном MNIST ES может быть в 1000 (!) раз медленнее, чем обычная оптимизация.
Вариации ES
Дополнительное положительное качество эволюционных стратегий — что они лишь подсказывают нам, как считать производную, а не заставляют переписывать алгоритм обратного распространения ошибки начисто. Всё, что можно применить к backprop-SGD, можно применить и к ES: импульс Нестерова, Adam-подобные алгоритмы, batch normalization. Есть несколько специфичных дополнительных приёмов, но пока что нужно больше исследований, при каких обстоятельствах они работают:
- ES позволяет оценивать не только первую, но и вторую производную $inline$E (\theta)$inline$. Чтобы получить формулу достаточно расписать ряд Тейлора в доказательстве выше до пятого члена, а не до третьего и отнять от него полученную формулу для первой производной. Впрочем, похоже, что делать это стоит лишь из научного любопытства, так как оценка получается ужасно нестабильной, а Adam и так позволяет эмулировать действие второй производной в алгоритме.
- Не обязательно использовать нормальное распределение. Очевидные претенденты — распределение Лапласа и t-распределение, но можно придумать и более экзотические варианты.
- Не обязательно сэмплировать лишь вокруг текущего $inline$\theta$inline$. Если запоминать предысторию движения по пространству параметров, можно сэмплировать веса вокруг точки немного по направлению движения.
- Во время обучения можно периодически перепрыгивать не по направлению градиента, а просто в точку с наименьшим $inline$E (\theta + \epsilon_i)$inline$. С одной стороны, это дестабилизирует обучение ещё больше, с другой стороны, такой подход хорошо работает в сильно нелинейных случаях с большим количеством локальных минимумов и седловых точек.
- Статья Uber от декабря 2017 предлагает novelty reward seeking evolution strategies (NSR-ES): в формулы обновления весов добавляется дополнительный член, поощряющий новые стратегии поведения. Идея внедрения разнообразия в reinforcement learning не нова, очевидно, что её попытаются приткнуть и сюда. Получившиеся алгоритмы обучения дают заметно более хорошие результаты на некоторых играх датасета Atari.
- Также есть статья, утверждающая, что необязательно пересылать результаты со всех нод всем остальным нодам: прореженный граф общения между рабочими станциями не только быстрее работает, но и выдаёт более хорошие результаты (!). По свей видимости, общение не со всеми собратьями по обучению работает как дополнительная регуляризация наподобие dropout’а.
См. также эту статью, дополнительно размышляющую о разнице поведения ES и TRPO в ландшафтах параметров разного типа, эту статью, более подробно описывающую взаимоотношения между ES и SGD, эту статью, доказывающее внеземное происхождение египетских пирамид, и эту статью, сравнивающую ES от OpenAI с более старой классической ES.
Variational optimisation (VO)
Хм, но почему ни слова не сказано про изменение $inline$\sigma$inline$ во время обучения? Было бы логично уменьшать его, ведь чем дольше идёт обучение, тем ближе мы к желаемому результату, следовательно нужно больше обращать внимание на локальный ландшафт $inline$E (\theta)$inline$. Вот только как именно менять среднеквадратичное отклонение? Не хочется изобретать какую-то хитрую схему…
Оказывается, всё уже придумано! Evolution strategies — это частный случай вариационной оптимизации для фиксированного $inline$\sigma$inline$.
Вариационная оптимизация зиждется на вспомогательном утверждении о вариационном ограничении сверху: глобальный минимум функции $inline$E (\theta)$inline$ не может быть меньше, чем среднее по значениям $inline$E (\theta_i)$inline$, как бы мы эти $inline$\theta_i$inline$ ни сэмплировали:
$$display$$\min_{\theta} E (\theta) \leq \min_{\eta} \mathbb{E}_{\theta \sim p (\theta|\eta)} [E (\theta)] = \min_{\eta} J (\eta, E) $$display$$
Где $inline$J (\eta, E)$inline$ — вариационный функционал, глобальный минимум которого совпадает с глобальным минимумом $inline$E$inline$. Заметьте, что теперь минимизация идёт не по исходным параметрам $inline$\theta$inline$, а по параметрам распределения, из которого мы семплировали эти параметры — $inline$\eta$inline$. Кроме того, обратите внимание, что даже если $inline$E$inline$ была недифференцируема, $inline$J$inline$ дифференцируема, если дифференцируемо распределение $inline$ p (\theta|\eta)$inline$, и производную можно выразить как:
$$display$$ \frac{\delta}{\delta\eta} \mathbb{E}_{\theta \sim p (\theta|\eta)}[E (\theta)] = \frac{\delta}{\delta\eta} \int p (\theta|\eta) E (\theta) d\theta $$display$$
$$display$$ = \int \frac{\delta}{\delta\eta} p (\theta|\eta) E (\theta) d\theta $$display$$
$$display$$ = \int p (\theta|\eta) E (\theta) \frac{\delta}{\delta\eta} \log{p (\theta|\eta)} d\theta $$display$$
$$display$$ = \mathbb{E}_{\theta \sim p (\theta|\eta)} E (\theta) \frac{\delta}{\delta\eta} \log{p (\theta|\eta)} $$display$$
Если $inline$ p (\theta|\eta)$inline$ — распределение Гаусса с фиксированной дисперсией, из этой формулы легко получить формулу для ES. Но что если $inline$\sigma$inline$ не фиксирована? Тогда на каждый вес в $inline$\theta$inline$ у нас получается два параметра в $inline$\eta$inline$: центр и среднеквадратичное отклонение соответствующей гауссианы. Размерность задачи увеличивается вдвое! Проще всего показать на одномерном примере. Вот вид сверху на получившийся после преобразования ландшафт для функции из предыдущей секции: 
И спуск по нему: 
Его значения в точке $inline$(\mu, \sigma)$inline$ соответствуют средним по значениям, сэмплированным из точки $inline$\mu = x$inline$ при помощи нормального распределения со среднеквадратичным отклонением $inline$\sigma$inline$. Отметим, что
- Снова: в реальной жизни нет смысла считать считать эту функцию. Как и в случае ES нам нужен только градиент.
- Теперь мы минимизируем $inline$(\mu, \sigma)$inline$, а не $inline$x$inline$.
- Чем меньше $inline$\sigma$inline$, тем больше сечение $inline$J$inline$ напоминает исходную функцию $inline$E$inline$
- Глобальный минимум $inline$J$inline$ достигается при $inline$\mu = 0, \sigma \rightarrow 0$inline$. В конечном итоге нам понадобится только $inline$\mu$inline$, а $inline$\sigma$inline$ можно отбросить.
- В глобальный минимум одномерной функции довольно сложно попасть — он огорожен высокими стенками. Однако если начать из точки с большим $inline$\sigma$inline$, сделать это становится гораздо проще, так как чем больше сглаживание, тем сильнее сечение функции напоминает обычную квадратичную функцию.
- Тем не менее, лучше воспользоваться Adam, чтобы попасть в узкую ложбину минимума.
Какие преимущества даёт введение вариационной оптимизации? Оказывается, из-за того что в ES был фиксированный $inline$\sigma$inline$, его формула могла вести нас в сторону субоптимальных минимумов: чем больше $inline$\sigma$inline$, тем менее на ландшафте сглаженной функции заметны глубокие, но узкие минимумы.
Так как в VO $inline$\sigma$inline$ перменный, у нас есть хотя бы шанс попасть в настоящий глобальный минимум.
Недостатки очевидны: даже в самом простом случае размерность задачи увеличивается вдвое, что уж говорить про случай, когда мы хотим иметь по $inline$\sigma_i$inline$ на каждое направление. Градиенты становятся ещё более нестабильными.
Вспомните график выше со «стенкой» посередине. VO ощущает её ещё меньше: 
(бывшая стенка — это маленькая штучка снизу посередине)
Хоть сходимость в глобальный минимум не гарантирована даже для простых случаев, у нас больше шансов попасть хоть куда-нибудь при неидеальной инициализации: 
Или даже выбраться из участка плохой пространственной инициализации: 
Заключение
Статья в OpenAI принесла в вариационную оптимизацию трюк с общим seed’ом генераторов случайных чисел различных нод. Но пока что (кажется?) нет статей, в которых оценивается реальное ускорение от него. Сдаётся мне, в ближайшем будущем, мы их увидим. Если они будут обнадёживающи, и если ES и VO будут распространены на обучение с учителем, быть может, нас ждёт смена парадигмы в машинном обучении.
Скачать код, с помощью которого были построены визуализации, можно здесь. Посмотреть на другие визуализации и узнать про связь вышеописанных методов с генетическими алгоритмами, Natural Evolution Strategies и Covariance-Matrix Adaptation Evolution Strategy (CMA-ES) можно здесь. Пишите в комментариях, если кому-то интересно посмотреть, как поведут себя ES и VO на какой-то определённой функции. Спасибо за внимание!
