Введение в онлайн-обучение

О чём раздел про онлайн-обучение, кому и зачем его читать?

Во многих случаях обучение ML-модели ― это однократный процесс, после которого она не меняется и только используется для предсказания. А что, если к нам постоянно поступает новая информация и мы должны её учитывать? Тогда модель должна уметь обновляться при поступлении нового объекта или батча объектов. Грубо говоря, этим и занимается онлайн-оптимизация. Можно заметить, что обновление модели на батче объектов проходит и в процессе стохастической оптимизации, ― и это сходство не случайно.

Оказывается, что все известные вам методы стохастической оптимизации первого порядка ― такие как SGD, AdaGrad, Adam, AMSgrad и другие ― являются в первую очередь алгоритмами онлайн-обучения. Чтобы в этом убедиться, достаточно открыть эти статьи и увидеть, для какой задачи выводятся гарантии на сходимость. Постановка задачи онлайн-обучения является одновременно математически простой и очень общей, соединяя три больших темы:

«Классическое» онлайн обучение.
Стохастическую оптимизацию на фиксированном датасете. Мы покажем, что любой алгоритм онлайн обучения можно переформулировать, как алгоритм стохастической оптимизации; при этом из гарантий на сходимость, полученных для онлайн обучения, автоматически будет следовать сходимость на фиксированном датасете.
Adversarial обучение.

Данный текст является в первую очередь систематизирующим. Мы постараемся достичь следующих целей:

Подведем единую математическую базу, необходимую для вдумчивого чтения статей по оптимизации. Это будет полезно ML-теоретикам.
Покажем, как исторически развивались методы оптимизации, как из одного метода получался другой, какие проблемы они решали и ― главное ― актуальны ли эти проблемы сейчас.
Разберём все «именные» методы оптимизации на набор базовых концепций и покажем, как вы можете самостоятельно их сочетать, создавая оптимальный метод для решения своей задачи. Спойлер: базовых концепций намного меньше, чем наименований методов. Эти знания будут полезны ML-инженерам.
Пройдемся по относительно нишевым темам, таким как разреженные методы регуляризации и , и рассмотрим наилучшие методы оптимизации для них. Такие методы невозможно получить в стандартной постановке стохастической оптимизации. Эти знания будут полезны ML-инженерам, занимающимся рекомендательными системами.

В параграфе «Введение в онлайн-обучение», которую вы читаете сейчас, вы познакомитесь с общей постановкой задачи онлайн-обучения, а также с семейством алгоритмов Follow the Regularized Leader (FTRL), которое включает в себя все методы первого порядка. Кроме того, вы узнаете, как сводить задачи стохастической оптимизации к задачам онлайн-обучения и увидите, что этот переход позволяет строить более эффективные методы стохастической оптимизации, особенно для разреженных регуляризаторов вроде .

В параграфе «Адаптивный FTRL» вы узнаете, как улучшить сходимость алгоритмов стохастической оптимизации с помощью регуляризаторов и каковы гарантии сходимости для регуляризованных задач. Это позволит вывести AdaGrad как наилучший адаптивный метод для онлайн-оптимизации.

В параграфе «Регуляризация в онлайн-обучении» мы снова поговорим о регуляризации, но на этот раз речь пойдёт о регуляризаторах, которые накладывают на решение определённые органичения, например, разреженность. Вы сможете с новой стороны взглянуть на разреживающие свойства -регуляризаторов. Кроме того, мы получим не достижимые с помощью обычных SGD/AdaGrad результаты для разреженных и регуляризаторов.

В параграфе «Стохастическая оптимизация в Deep Learning» мы перейдём к методам оптимизации в глубоких нейросетях. Вас ждёт краткий исторический обзор и мотивация появления двух важных модификаций AdaGrad ― Adam и RMSprop. Мы покажем, что эти методы ломаются вокруг критических точек, и поговорим о том, как починить это и достичь более точной сходимости (этого эффекта можно достичь либо прямой модификацией алгоритмов (AMSgrad и RAdam), либо косвенно с помощью Learning Rate Scheduler'ов).

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

Постановка задачи

Литература. Отсюда и далее, пока явно не скажем о переходе на другие источники информации, используется материал из книги Shai Shalev-Shwartz Online Learning and Online
Convex Optimization

Онлайн-обучение ― это процесс предсказания ответов на последовательность вопросов с учётом знания (возможно, неполного) о предыдущих правильных ответах.

Представим себе следующую игру (назовём её игра (1)). На каждом раунде игры мы:

Получаем ― частичную информацию о текущем «вопросе»;
Выбираем модель , которой будем делать прогноз;
Прогнозируем ;
Получаем истинный ответ ;
Получаем обратную связь-лосс . Лоссы обычно имеют семантику функции ошибки: больше ― хуже, меньше ― лучше.

Цель любого алгоритма онлайн обучения ― минимизация суммарной ошибки прогнозов для любого количества раундов .

Пока рассмотрим интуитивный пример: линейная регрессия (обозначения взяты из параграфа про линейные модели). Пусть у нас уже сыграны раунды и есть выборка данных и ответов .

Получаем новый . В данном случае просто получаем и пока не используем;
Выбираем модель , которая наилучшим образом объясняет всю предыдущую имеющуюся выборку (алгоритм обучения можем выбирать любой, какой нам нравится);
Прогнозируем ;
Получаем правильный ответ ;
Считаем loss ;

Действуя таким образом, мы делаем интуитивное предположение, что ответы как-то зависят от наших и что эту зависимость мы можем выучить из предыдущей выборки, улучшив прогноз на новых объектах.

Предположения

Теория онлайн обучения выгодно отличается от классической теории статистического обучения довольно расслабленными и гораздо более простыми (с точки зрения математических формулировок) условиями. Мы не делаем предположений о некой статистической зависимости между , . Зависимость может быть детерминированной, стохастической или даже adversarial:

Детерминированная: в самом начала игры делается выбор детерминированной зависимости
Стохастическая: может быть реализациями случайной величины, зависящей от
Adversarial: мы играем против активного противника, который может на каждом раунде игры по своему усмотрению менять зависимость и/или подбирать , имея на руках в том числе текущий ответ , не доступный алгоритму онлайн-обучения

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

Поведение алгоритма на шаге T

Начнем с введения метрики качества алгоритма на некотором раунде игры , а затем расширим ее на все раунды игры.

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

Чтобы такого не случалось, мы предположим, что все ответы на шаге должны быть сгенерированы некоторым отображением , где ― пространство возможных решений, известное и онлайн-алгоритму, и противнику.

С учетом введенного ограничения на поведение противника, введем понятие regret:

Regret ― это метрика того, насколько онлайн алгоритм работает хуже, чем некоторая фиксированная модель-бейзлайн h (regret переводится как «сожаление»: насколько мы пожалели о том, что взяли онлайн алгоритм, а не модель h). Поскольку мы работаем в adversarial случае, то логично сравнивать наш онлайн алгоритм с сильнейшим возможным противником, а именно: противник всегда выбирает не «некоторую», а наилучшую модель-бейзлайн :

Поведение алгоритма на всей последовательности раундов игры

Вспомним, что вообще-то мы играем игру с бесконечным числом раундов. В таком случае, естественно будет анализировать поведение ряда . Здесь хочется еще раз подчеркнуть, в чем заключается adversarial поведение: на каждом шаге t maxRegret будет иметь свою наилучшую модель в бейзлайне:

Качество онлайн алгоритма на протяжении всей игры

Когда мы говорим про adversarial setting и игру с противником, мы хотим не просто как-то минимизировать кумулятивный , но еще и хотим быть не хуже нашего противника. Потребуем, чтобы

Такое условие означает, что regret должен расти медленнее чем линейно (в таком случае говорят, что алгоритм имеет сублинейный regret).

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

Асимптотика , очевидно, приводит к намного лучшей сходимости. Но достичь этого не всегда возможно. Стандартной асимптотикой regret в большинстве используемых на практике алгоритмов является , для этой асимптотики условия на задачу наименее жесткие. Все рассматриваемые нами ниже алгоритмы будут иметь асимптотику и отличаться в основном константами в оценках (но, конечно, отличия в константах при оценке Regret часто приводят к существенно разному поведению на практике). Любые более мощные асимптотики требуют условий, которые крайне редко выполняются в практических задачах

Online to batch conversion

В данном обзоре мы будем анализировать методы, которые гораздо чаще используются для оптимизации в классической постановке: есть фиксированный датасет , модель с обучаемыми параметрами и функция потерь , задача ― найти минимум функции

Если представить, что все наши ― независимые одинаково распределенные случайные величины, то можно считать, что на самом деле мы оптимизируем

Такую постановку задачи часто называть батчевой (англ. batch). Это означает, что мы можем использовать два класса методов оптимизации:

методы, которые на каждом шаге смотрят сразу на всю выборку (например, градиентный спуск или метод Ньютона);
методы, которые на каждом шаге смотрят на случайное подмножество данных в надежде, что, итерируясь по таким подмножествам, мы сможем соптимизировать матожидание (например, SGD). Такие методы называют стохастическими.

Существует специальный класс методов анализа сходимости, называемый online to batch conversion. Они позволяют адаптировать алгоритм онлайн-обучения к постановке задачи стохастической оптимизации на фиксированном датасете; при этом оценка на regret транслируется в асимптотику сходимости стохастической оптимизации. Математически строгий вывод этих методов обычно довольно громоздкий и не дарит более глубокого понимания идей в современных стохастических методах, это чисто технические выкладки, поэтому мы здесь ограничимся интуитивным описанием. Строгий вывод можно найти, например, в упомянутой выше книге Shai Shalev-Schwartz.

Процесс стохастической оптимизации на фиксированном датасете можно представить в виде задачи онлайн обучения, если вытянуть все эпохи (проходы по датасетам) в единую последовательность. Мы получим задачу онлайн обучения, в которой сэмплируются из фиксированного множества . Строго говоря, тут сэмлпирование двухстадийное:

Берем исходное множество функций
Сэмплируем из него без возвращения, пока множество не станет пустым
Как только оно стало пустым ― заново заполняем его

Таким образом, деление на "эпохи" отчетливо видно и в вытянутой последовательности.

Легко видеть, что эта задача является корректной задачей онлайн обучения. Тут мы активно пользуемся тем, что постановка задачи онлайн обучения математически простая и очень общая. Из корректности данной задачи следует, что все алгоритмы онлайн обучения будут иметь на такой последовательности сублинейный regret.

Следующим шагом давайте взглянем на regret в момент смены эпохи. Обозначим за ―число эпох, тогда:

Из сходимости последовательности следует сходимость любой ее подпоследовательности, а значит, последовательность regret'ов в моменты смены эпох тоже ведет себя сублинейно:

Последнее слагаемое уже выглядит практически как постановка задачи стохастической оптимизации на фиксированном датасете! Интуиция на данный момент подсказывает нам, что разрыв между решениями, даваемыми онлайн обучением, и точным решением задачи батч-оптимизации, будет постепенно сокращаться.

В этот момент интуицию можно выключать―остаются только строгие технические выкладки по ссылкам выше.

Выпуклая онлайн-оптимизация

Выпуклая оптимизация играет центральную роль в анализе алгоритмов онлайн-обучения и позволяет получать эффективные алгоритмы. Вот примеры задач, в которых она хорошо работает:

Линейная оптимизация;
Expert Advice problem;
Линейная/логистическая регрессия.

Для задач, возникающих в глубинном обучении, мы поступим согласно рекомендациям ведущих ученых: возьмем теоретически обоснованный алгоритм выпуклой оптимизации, воткнем в нейросеть и помолимся, чтобы он сохранил свои хорошие свойства. С методами первого порядка, как правило, работает (а здесь мы будем рассматривать только такие методы)

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

Выбираем параметрическую модель ;
Получаем извне выпуклую функцию потерь ;
Считаем в точке и получаем наш loss .

Первое упрощение состоит в том, что прогноз и бейзлайн мы теперь берём не из абстрактного функционального множества , а из некоторого параметризованного семейства. Говоря «модель », мы имеем в виду «модель, заданная параметрами ». Скажем, для линейной регрессии это может быть вектор весов и bias. Regret будет записываться следующим образом:

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

Обратите внимание: если вы попробуете себе представить онлайн алгоритм на практике, то, как правило, частичная информация о функции перед выбором вам доступна. Например, рассмотрим рекомендательную систему с онлайн-дообучаемой ранжирующей моделью:

Пользователь пришел, мы сразу пошли в базу данных за его историей покупок и получили признаковое описание (возможно частичное) ;
С учётом этого признакового описания мы выбираем модель и с её помощью оцениваем релевантность товаров этому пользователю;
Смотрим, что купил пользователь и купил ли, это даёт нам .

Тем не менее, в этом параграфе мы будем считать, что частичной информации нет, потому что хотим разрабатывать наиболее общий фреймворк, а не ad-hoc алгоритмы, использующие конкретный вид этой частичной информации. Если даже для какой-то узкой проблемы можно сформулировать специфический алгоритм, учитывающий частичную информацию, с высокой вероятностью он не будет работать значимо лучше стандартного решения. Если знаете контрпримеры ― напишите, добавим сюда для полноты.

Follow the Leader

Предположим, что мы провели шагов игры (2) и теперь выбираем модель (как условились, без информации о ). Наиболее естественным выбором будет алгоритм, минимизирующий ошибку на всех предыдущих раундах

Такой алгоритм называется Follow The Leader (FTL), потому что мы идем вплотную за наилучшим возможным алгоритмом-бейзлайном в regret (лидером), который учитывает ещё и информацию с -го шага:

К сожалению, для алгоритма в таком виде есть важные примеры выпуклых задач, когда он не работает. Допустим, наши функции потерь линейны . Вам может показаться, что линейная функция не особенно похожа на функцию потерь, но, забегая вперед, именно такие функции потерь встретятся дальше при изучении градиентных онлайн-алгоритмов ().

Рассмотрим одномерную задачу , , . Пусть

Алгоритм FTL выглядит так:

Такие осциллирующие суммы коэффициентов будут заставлять FTL выбирать наихудшее возможное решение в каждом раунде. Функция потерь в каждом раунде будет равна , а кумулятивная функция потерь примет вид . При этом кумулятивная функция потерь константного решения будет равна 0. Получаем линейный regret относительно бейзлайна , алгоритм не сходится.

Follow The Regularized Leader

Чтобы стабилизировать алгоритм, мы добавим регуляризаторы, и назовем получившийся алгоритм Follow The Regularized Leader (FTRL):

Упражнение. Проверьте, что в примере из предыдущего параграфа добавление регуляризатора стабилизирует осцилляцию решения .

Добавка должна быть выпуклой и неотрицательной. При этом различный выбор будет приводить к различным алгоритмам и различным оценкам на regret.

Первое, что приходит в голову ― это регуляризатор . Он даёт алгоритм

Adaptive FTRL

Следующая идея―сделать регуляризатор зависящим от данных (то есть от ) и своим на каждом раунде T:

Забегая вперед―все современные градиентные алгоритмы Adam, RMSProp, AdaGrad и т.д. попадают в это семейство data-dependent регуляризаторов и работают значительно эффективнее любых алгоритмов с константными регуляризаторами .

Обратите внимание: регуляризаторы являются частью алгоритма FTRL, они не входят в формулу для regret, которая по-прежнему имеет вид

Таким образом, мы не изменили постановку решаемой нами задачи, изменили лишь метод ее решения.

Обратите внимание: введение регуляризаторов влияет только на онлайн-алгоритм и выбор . Бейзлайны выбираются как и раньше:

Линеаризация и вычислительно эффективный FTRL

Рассмотрим пример с логистической регрессией и константным регуляризатором:

Классический пример использования онлайн логистической регрессии ― предсказание CTR в рекламе. Миллионы запросов в секунду => миллионы решений этой оптимизационной задачи в секунду (если разбивать на батчи ― тысячи, но сути это не меняет). Успех онлайн-алгоритма в таких задачах определяется его вычислительной эффективностью, как по памяти, так и по скорости. Увы, с этим у нашего алгоритма не всё так хорошо:

Скорость: аналитически задача не решается => FAIL
Память: нужно хранить все предыдущие запросы , => FAIL

Здесь нам на помощь приходит линеаризация задачи. Если фунции выпуклые (вниз) и гладкие (на негладкие посмотрим позже), то они удовлетворяют основному свойству выпуклых функций

Разложим все функции в точках :

Просуммируем от 1 до

Теперь обозначим и рассмотрим выпуклую линейную задачу онлайн обучения с функцией потерь . Regret для нее выглядит как

Неравенство выше позволяет нам оценить regret исходной задачи через regret линеаризованной:

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

Посмотрим, будет ли линеаризованный алгоритм вычислительно эффективнее. Посмотрим на линеаризацию задачи с data-depedent регуляризатором:

Линейные задачи имеют аналитическое решение для широкого спектра . Собственно, это и есть основное, что нужно помнить на практике ― выбирать регуляризатор так, чтобы эта задача решалась аналитически. Мы рассмотрим простейший случай :

Справа дифференцируемая функция, так что мы можем найти , приравняв к нулю градиент:

где ― это сумма векторов, которую не нужно пересчитывать заново на каждом шаге, а можно инкрементально обновлять. Благодаря этому нам больше не нужно помнить все предыдущие объекты выборки, достаточно хранить лишь некоторую статистику.

Готово, мы построили наш первый вычислительно эффективный алгоритм онлайн обучения! В дальнейшем мы займемся тем, чтобы найти наилучший вычислительно эффективный алгоритм.

Обратите внимание: теперь вы понимете, почему пример с линейной функцией потерь был так важен: линейные функции соответствуют линеаризованному regret. При этом, как мы уже выяснили, без регуляризатора такие линеаризованные задачи нестабильны.

Обратите внимание: если переписать немного формулу для , мы получим:

Таким образом, формулы FTRL c константным регуляризатором эквивалентны формулам обычного стохастического градиентного спуска. Забегая вперед, скажем, что различия в формулах градиентного спуска и FTRL будут только в разделе Composite objective FTRL. В этих отличиях и будет заключаться преимущество FTRL перед привычным SGD.

Обратите внимание: концепции FTRL и gradient descent в литературе часто называют lazy (ленивая) и greedy (жадная) соответственно.

Gradient descent жадный, потому что алгоритм для обновления использует только текущий и текущий градиент . Всё, что было на предыдущих шагах, алгоритм забывает.

FTRL ленивый, потому что алгоритм в явном виде сохраняет всю информацию с начала обучения и рассчитывает , исходя из всей истории , и только после этого применяет все регуляризаторы. Подробнее мы расскажем об этом в разделе «Сравнение Composite Objective FTRL-Proximal и Adaptive Gradient Descent».

Субдифференциал и субградиентные методы

Выше мы рассматривали гладкие функции . Гладкость ― сильное ограничение, и оно на самом деле необязательно, можно ослабить условие, если использовать субградиенты.

Когда мы переходили от исходной задачи к линеаризованной, мы использовали основное свойство гладких выпуклых функций

Гладкость обеспечивает существование для всех . Но нам ведь не нужно, чтобы существовал именно градиент функции. Нам достаточно, чтобы существовал какой-то вектор , для которого выполнено неравенство

И в этом помогают следующие два понятия.

Субдифференциалом функции в точке называется множество

Субградиентом функции в точке называется любой элемент множества .

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

Примеры. Для гладких функций субдифференциал состоит из одной точки: градиента функции, а субградиент равен градиенту. В качестве примера функции с нетривиальным субградиентом рассмотрим функцию , где ― скаляр. Субградиент в точке ― это можество

Легко видеть, что $\partial_0\vert x\vert $ ― это отрезок .

Замечание. На практике субдифференциал используют не так часто. Оптимизационные задачи с популярными негладкими регуляризаторами решают «в лоб», без перехода к субградиентной оценке, например, с помощью проксимальных методов.

Обратите внимание. В литературе очень часто используется термин Online Mirror Descent. Mirror descent ― это оптимизационная процедура вида

в которой ― дополнительный негладкий регуляризатор (например, тот же ), который мы как раз таки не заменяем на субградиентную оценку, а вместо этого оптимизируем всё «в лоб». Заметьте, что эти формулы идентичны формулам Proximal Gradient Descent. Если у нас нет регуляризатора , то формулы эквивалентны обычному gradient descent.

Как вы увидите дальше, Mirror Descent ― это частный случай общего фреймворка, который мы описываем.

Субградиентные методы оптимизации.

Почти все градиентные методы оптимизации обобщаются на негладкие функции. Модифицируется необходимое и достаточное условие минимума для выпуклых функций: точка является минимумом, если субдифференциал содержит ноль: . Очевидно, это прямое обобщение условия для гладких функций, где субдифференциал состоит только из градиента функции.

15.1. Введение в онлайн-обучение