Алгоритмы оптимизации в машинном обучении

Коши против Ньютона

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

Общая итерационная процедура всех градиентных алгоритмов

В теории давно известны более эффективные и быстрые оптимизирующие алгоритмы с квадратичной скоростью сходимости, такие как алгоритм Ньютона или метод Гаусса — Ньютона. Однако с их применением в ML есть некоторые проблемы.

Слева Огюстену Луи Коши - справа Исаак Ньютон (портрет кисти Г. Кнеллера (1689)

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

Градиентный алгоритм, или алгоритм наискорейшего спуска Коши, широко применяется в AI/ML

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

Варианты градиентных алгоритмов в машинном обучении

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

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

Модифицированный метод Ньютона

На простейшей задаче оптимизации функции, зависящей от двух параметров [x,y], можно сравнить скорости сходимости и устойчивость указанных алгоритмов .

Рассмотрим пример мультимодальной функции с несколькими локальными минимумами, задаваемой выражением:

Функция Химмельблау

Это известная в теории оптимизации функция Химельблау. Она имеет четыре расположенных рядом локальных минимума, один центральный локальный максимум и четыре седловины.

График функции Химмельблау от двух переменных

Функция интересна с точки зрения поиска оптимальных точек и тестирования алгоритмов обучения или оптимизации. Код для построения графика функции Химмельблау выглядит так:

Plotting the Himmelblau function

Проблема поиска оптимальных коэффициентов (оптимального решения целевой функции) для нейронной сети состоит в том, что современные задачи имеют большие размерности 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]. Метод Ньютона, наоборот, скачет по поверхности целевой функции в направлении того же оптимума.

Cходимость аргументов [x,y] к оптимальному решению по поверхности целевой функции f(x,y) для различных алгоритмов

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

Оптимизацию зашумленной функции Химмельблау, где зашумлено и значение функции, и значение первого градиента гауссовским белым шумом с параметрами (М=0 и sigma =5), можно наблюдать ниже.

Графики сходимости к точке локального минимума для зашумленной функции показывают, что медленный градиентный алгоритм выглядит более предпочтительно, чем быстрый “ньютон”!

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

Таким образом, выделить более надежный и быстрый алгоритм при оптимизации функции стоимости J для нейронной сети довольно сложно. Инженеры обычно выбирают медленный, но надежный пошаговый градиентный алгоритм с рядом модификаций называемый Adam[1] или другую его версию Nadam[2]. Поскольку реальные данные сильно зашумлены и не однородны, свойство медленной сходимости градиентного алгоритма оказывается весьма кстати. Полный код программы с комментариями и множеством параметров для сравнения алгоритма Коши (базовый алгоритм градиентного спуска) и Ньютона можно найти по ссылке:

Ссылки

  1. https://machinelearningmastery.com/adam-optimization-algorithm-for-deep-learning/
  2. https://medium.com/konvergen/modifying-adam-to-use-nesterov-accelerated-gradients-nesterov-accelerated-adaptive-moment-67154177e1fd

R&D engineer in machine learning and data analysis. Java, C/C++, Python, M and CUDA. HPC, processors architectures and parallel systems.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store