Алгоритмы оптимизации в машинном обучении
Коши против Ньютона
В статье речь пойдет об алгоритмах оптимизации, которые интересно применять в задачах машинного обучения. Алгоритмы ньютоновского типа — это наиболее продвинутый класс алгоритмов оптимизации по сравнению с популярным классом градиентных спусков. Но именно варианты градиентного алгоритма нашли широкое распространение в машинном обучении. Дело в том, что градиентные алгоритмы относятся к так называемым алгоритмам типа Коши и имеют всего лишь линейную скорость сходимости. Огюстеном Коши был предложен один из первых вариантов алгоритма градиентного спуска — метод наискорейшего спуска (он же метод Коши). В нем используется итерационная процедура, в которой альфа k-ое — размер шага оценивается с помощью одномерной линейной оптимизации, а направление s(.) выбирается исходя из оценки градиента в k-ой точке.
В теории давно известны более эффективные и быстрые оптимизирующие алгоритмы с квадратичной скоростью сходимости, такие как алгоритм Ньютона или метод Гаусса — Ньютона. Однако с их применением в ML есть некоторые проблемы.
Для простоты, рассмотрим вариант градиентного алгоритма с фиксированным шагом, демонстрирующий линейную оптимизацию. Этот алгоритм является основой для работы любой нейросети. Его преимущество заключается в надежности пошаговой оптимизации и гарантированной сходимости к локальной точке оптимума. Использование этого достаточно простого, но надежного алгоритма свидетельствует о том, что мы все еще находимся на ранней стадии применения теории оптимизации в машинном обучении.
Дело в том, что градиентный метод применяет знания о первых производных и относится к методам первого порядка. В то же время в теории оптимизации уже давно разработаны и существуют более эффективные методы поиска оптимальных решений. Задачи обучения таких нейронных сетей, как рекуррентные (RNN), сетей с несколькими скрытыми слоями (DNN) или сверточных сетей (CNN), сводятся к поиску их весовых коэффициентов. Как правило, в роли оптимизационного алгоритма выступает один из вариантов градиентного алгоритма. Варианты можно видеть на рисунке.
Таким образом, можно утверждать, что все современные системы машинного обучения основаны на семействе градиентных алгоритмов с пошаговой оптимизацией или пошаговым линейным поиском решения. Как ни странно, сейчас мы не применяем быстрые поисковые процедуры с нелинейной скоростью сходимости.
Альтернативой градиентному алгоритму является метод Ньютона или его вариант — модифицированный метод Ньютона. Данные методы относятся к методам второго порядка, обладают квадратичной сходимостью и используют вторые производные. Благодаря этому увеличивается скорость сходимости, достигается более общая стратегия поиска и ускоряется машинное обучение.
На простейшей задаче оптимизации функции, зависящей от двух параметров [x,y], можно сравнить скорости сходимости и устойчивость указанных алгоритмов .
Рассмотрим пример мультимодальной функции с несколькими локальными минимумами, задаваемой выражением:
Это известная в теории оптимизации функция Химельблау. Она имеет четыре расположенных рядом локальных минимума, один центральный локальный максимум и четыре седловины.
Функция интересна с точки зрения поиска оптимальных точек и тестирования алгоритмов обучения или оптимизации. Код для построения графика функции Химмельблау выглядит так:
Проблема поиска оптимальных коэффициентов (оптимального решения целевой функции) для нейронной сети состоит в том, что современные задачи имеют большие размерности N > 1000. Ситуацию усложняют неоднородные, “сырые” тренировочные данные, приводящие к зашумлению поверхности целевой функции. Например, добавление в функцию Химмельблау шума с нормальным распределением с параметрами M=0 и sigma =20 приводит к существенному искажению поверхности. Это является причиной нарушения работы численного алгоритма и появления ошибок при оценке коэффициентов нейронной сети.
Практика показывает, что современные варианты градиентного алгоритма с адаптивной настройкой шага, ограничениями, штрафными функциями и регуляризацией позволяют настроить весовые коэффициенты сети достаточно точно.
Давайте разберемся, почему более простой вариант градиентного метода работает не эффективно и требует стольких усложнений. Построим графики сходимости градиентного алгоритма и метода Ньютона к оптимальной точке для приведенной функции Химмельблау .
Код градиентного алгоритма с логированием поиска представлен ниже.
Переменные w_history —это значения аргументов, f_history — значения функции, eps_history_f —норма расстояния между значениями функций, eps_history_xy — норма расстояний между значениями аргумента. Эти наборы переменных сохранены в стеки при помощи np.stack(). Они позволяют проанализировать сходимость градиентного алгоритма к оптимальному решению f(x*,y*) для функции Химмельблау f(x,y). Сходимость к оптимальному решению может быть выражена пределом.
Таким же образом в машинном обучении градиентный алгоритм минимизирует целевую функцию ошибки J(.) от вектора параметров тета. Он подгоняет гипотезу h к тренировочным данным data.
Давайте представим графики сходимости, полученные для функции f(x,y) и аргументов [x,y].
Графики демонстрируют сходимость градиентного алгоритма за ~200 итераций. Для сравнения, метод Ньютона сходится всего за ~20 итераций. Сам алгоритм представлен ниже.
Градиентный метод медленно сползает к одной из оптимальных точек с координатами [3, 2]. Метод Ньютона, наоборот, скачет по поверхности целевой функции в направлении того же оптимума.
Почему бы не использовать методы второго порядка в машинном обучении? Ведь именно они позволяют применять более общую стратегию поиска. Дело в том, что несмотря на свою эффективность методы второго порядка являются менее стабильным. Они дают ряд выбросов в процессе адаптации. При использовании зашумленных целевых функций в реальных ситуациях обучение нейронных сетей будет проходить еще с большим числом выбросов.
Оптимизацию зашумленной функции Химмельблау, где зашумлено и значение функции, и значение первого градиента гауссовским белым шумом с параметрами (М=0 и sigma =5), можно наблюдать ниже.
Графики сходимости к точке локального минимума для зашумленной функции показывают, что медленный градиентный алгоритм выглядит более предпочтительно, чем быстрый “ньютон”!
Метод Ньютона успевает подстраиваться к шумовым дрожаниям функции, что негативно сказывается на оценке оптимальных значений [x,y] (зеленые графики на рисунке ниже). При этом, градиентный способ дает достаточно точную усредненную оценку аргументов (красные графики для[x,y] ниже).
Таким образом, выделить более надежный и быстрый алгоритм при оптимизации функции стоимости J для нейронной сети довольно сложно. Инженеры обычно выбирают медленный, но надежный пошаговый градиентный алгоритм с рядом модификаций называемый Adam[1] или другую его версию Nadam[2]. Поскольку реальные данные сильно зашумлены и не однородны, свойство медленной сходимости градиентного алгоритма оказывается весьма кстати. Полный код программы с комментариями и множеством параметров для сравнения алгоритма Коши (базовый алгоритм градиентного спуска) и Ньютона можно найти по ссылке:
