В первом эпизоде этой серии мы рассмотрели самые фундаментальные концепции в области машинного онлайн-обучения: мы увидели, как можно описать онлайн-обучение как игру между двумя игроками под названием Ученик и среда, и мы поняли, когда мы можем сказать, что Ученик выигрывает игру.
Как мы уже видели, для минимизации сожалений требуется алгоритм, гарантирующий сублинейный рост этой величины по отношению к общему количеству шагов обучения.
В этом эпизоде мы представляем онлайн-градиентный спуск (OGD), онлайн-версию важной вехи в машинном обучении и оптимизации, которой является алгоритм градиентного спуска. OGD очень похож на стохастический градиентный спуск, но разница в том, что он позволяет использовать другую дифференцируемую функцию потерь на каждой итерации.
Затем мы сделаем еще один шаг и адаптируемся к использованию выпуклых недифференцируемых функций потерь, получив алгоритм онлайн-субградиентного спуска (OSD).
Градиенты, выпуклость, субградиенты
Мы собираемся определить некоторые фундаментальные концепции для алгоритмов, которые мы намерены обсудить в дальнейшем.
Пусть f будет общей вещественной многомерной и действительнозначной функцией, определенной на множестве X.
Как известно, f называется дифференцируемой в точке x, если производная функции по каждой из независимых переменных существует в x. Функция глобально дифференцируема, если она дифференцируема по x для каждого x в X.
Градиент f по x - это вектор частных производных по каждой независимой переменной в точке x.
Еще одно важное понятие — выпуклость. Функция выпукла, если для двух точек x и y в ее области определения отрезок, соединяющий x и y, больше или равен f в каждой точке между x и y. Или, что то же самое, f является выпуклым, если его эпиграф (область над его графиком) является выпуклым множеством (множеством, которое полностью содержит каждый сегмент, крайние точки которого принадлежат множеству).
Примечательно, что если f дифференцируема в точке x, внутренней по отношению к области, то для каждого y в области выполняется это неравенство:
где оператор, указанный в угловых скобках, является внутренним произведением.
Не каждая функция, которую мы хотим использовать, глобально дифференцируема, например, некоторые функции потерь, обычно используемые в машинном обучении (например, потеря шарнира). По этой причине полезно обобщить понятие градиента таким образом, что для каждой точки, в которой функция дифференцируема, обобщенный градиент соответствует обычному градиенту, и в каждой точке недифференцируемости мы по-прежнему имеем подобный объект который мы можем использовать вместо градиента.
Если f выпукло, субградиентом f в точке x в X является любой действительный d-мерный вектор g, который соответствует:
для каждого y в X.
Онлайн градиентный спуск
Теперь мы готовы сформулировать алгоритм OGD для Learner.
где каждая эта является реальной положительной величиной. На последнем шаге мы использовали проекцию над W, определяемую следующим образом:
Эта операция необходима, поскольку движение от x в направлении, противоположном градиенту g, не является операцией, сохраняющей принадлежность к W вообще. Итак, мы берем перенесенную точку и находим в W ближайшую точку относительно L2-нормы.
Учитывая выпуклость функций потерь, названную D диаметром W (максимальное расстояние между любыми двумя точками в нем) и добавив некоторые дополнительные второстепенные гипотезы, можно доказать, что сожаление удовлетворяет следующей верхней границе.
Как вы можете заметить, L2-норма градиента присутствует в последнем члене. Поскольку нам нужна стратегия для фиксирования параметров eta, мы можем просто взять фиксированное значение. Предположим, что норма всех градиентов ограничена сверху положительной величиной L.
Простой расчет дает оптимальное значение эта.
Подстановкой получаем оценку сожаления
который, как мы и хотели, является сублинейным по T.
Субградиентный спуск онлайн
Алгоритм OSD точно следует той же структуре OGD, за исключением того факта, что обновление выполняется с использованием субградиента каждой функции потерь вместо градиента, с учетом того факта, что функция может быть недифференцируемой в данной точке. Если это так, обновление будет таким же, как если бы мы использовали OGD.
Границы сожаления, которые мы видели ранее для OGD, все еще сохраняются при переходе от использования градиентов к использованию субградиентов.
Выводы
В этом посте мы рассмотрели онлайн-градиентный спуск и онлайн-субградиентный спуск, два важных онлайн-алгоритма выпуклой оптимизации. Мы также дали некоторые границы сожаления, которые гарантируют эти алгоритмы. В следующем посте мы перейдем к другому интересному алгоритму онлайн-обучения, Экспоненциальному градиенту, и выведем его как частный случай в классе алгоритмов, называемых онлайн-зеркальным спуском.
Рекомендации
- Орабона, Ф. (2019). Современное введение в онлайн-обучение. ArXiv, абс/1912.13213.
- Шалев-Шварц, С. (2012). Онлайн-обучение и выпуклая онлайн-оптимизация. Найдено. Тенденции Маха. Учись., 4, 107–194.
- Зинкевич, М.А. (2003). Выпуклое онлайн-программирование и обобщенный бесконечно малый градиентный подъем. ICML.
- Гордон, Г.Дж. (1999). Границы сожаления для задач предсказания. КОЛТ 99.
