Обзор и сравнение различных алгоритмов спуска

Основные требования для понимания этой статьи

  • Линейная алгебра
  • Многопараметрическое исчисление
  • Основная идея выпуклых функций

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

  • Метод Ньютона
  • Крутой спуск
  • Градиентный спуск

Подробнее об этих алгоритмах вы можете узнать из учебника Convex Optimization: Part 3. В этой статье мы в основном сосредоточимся на квадратичных / полиномиальных функциях.

Предположение о наших функциях

Мы всегда предполагаем, что функции, с которыми мы имеем дело, вместе с их производными непрерывны (т.е. f ∈ C¹). В случае метода Ньютона нам также нужно предположить, что вторые производные непрерывны. (т.е. f ∈ C²). Последнее предположение, которое мы делаем, состоит в том, что функции, которые мы пытаемся минимизировать, являются выпуклыми. Таким образом, если наш алгоритм сходится к точке (обычно известной как локальный минимум), то мы гарантируем, что это глобальный оптимизатор.

Метод Ньютона

Алгоритм для функции одной переменной

x_n = starting point
x_n1 = x_n - (f'(x_n)/f''(x_n))
while (f(x_n) != f(x_n1)):
  x_n = x_n1 
  x_n1 = x_n - (f'(x_n)/f''(x_n))

Идея метода Ньютона заключается в том, что минимизируемая функция f аппроксимируется локально квадратичной функцией. Затем мы находим точный минимум этой квадратичной функции и устанавливаем следующую точку. Затем повторяем процедуру.

Случай для функций с несколькими переменными

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

Предполагая, что x∈ ℝn, имеем:

x_n = starting_point
x_n1 = x_n - inverse(hessian_matrix) (gradient(x_n))
while (f(x_n) != f(x_n1)):
  x_n = x_n1
  x_n1 = x_n - inverse(hessian_matrix) (gradient(x_n))

где gradient(x_n) - вектор градиента в точке x_n, а hessian_matrix - это гессианская симметричная матрица размера n × n, элементы которой состоят из вторых производных в точке x_n.
Как мы все знаем, инвертирование матрицы обходится дорого (O (n³)), поэтому этот метод обычно не используется.

Градиентный спуск

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

alpha = small_constant
x_n = starting_point
x_n1 = x_n - alpha * gradient(x_n)
while (f(x_n) != f(x_n1)): # May take a long time to converge
  x_n = x_n1
  x_n1 = x_n - alpha * gradient(x_n)

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

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

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

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

Крутой спуск

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

x_n = starting_point
alpha_k = get_optimizer(f(x_n - alpha * gradient(x_n)))
x_n1 = x_n - alpha_n * gradient(x_n)
while (f(x_n) != f(x_n1)):
  x_n = x_n1 
  alpha_k = get_optimizer(f(x_n - alpha * gradient(x_n)))
  x_n1 = x_n - alpha_n * gradient(x_n)

где x_n и x_n1 - входные векторы в ℝn, gradient - градиент f в x_n, а alpha_k таков, что:

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

Частный случай квадратичных функций.

Рассмотрим квадрат функции потерь ошибок:

где I - единичная матрица, а y = Qw + b
Для простоты мы рассмотрите только поиск оптимального значения веса w (предположим, что b является постоянным). Подставив y и все упростив, мы получим следующее:

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

Упрощая описанный выше беспорядок и подставляя градиент f в двух точках, мы получаем следующее для αk

Теперь у нас есть конкретное значение αk в случае квадратичных функций.

Анализ сходимости квадратичных функций

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

На приведенном выше рисунке обратите внимание, что изменение направления перпендикулярно на каждой итерации. После 3–4 итераций мы замечаем, что изменение производных практически незначительно.

Почему не используется самый крутой спуск?

Так почему же этот алгоритм не используется так часто? Это явно избавляет от необходимости настраивать гиперпараметр и гарантированно сводится к локальному минимуму. Проблема здесь в том, что на каждой итерации нам нужно оптимизировать alpha_k, что немного дорого, учитывая, что мы должны делать это на каждом этапе.

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

Сравнение градиентного спуска и крутого спуска

Мы проведем сравнение градиентного спуска и наискорейшего спуска и проанализируем их временную сложность. Сначала мы сравним время между двумя алгоритмами. Мы создадим квадратичную функцию f: ℝ²⁰⁰⁰ → ℝ (которая включает матрицу 2000 × 2000). Затем мы оптимизируем функцию и ограничим количество итераций до 1000. Затем мы сравним затраченное время и то, насколько близко значение x_n к оптимизатору между двумя алгоритмами.

Давайте сначала посмотрим на самый крутой спуск:

0   Diff: 117727672.56583363 alpha value: 8.032725864804974e-06 
100 Diff: 9264.791000127792 alpha value: 1.0176428564615889e-05 
200 Diff: 1641.154644548893 alpha value: 1.0236993350903281e-05 
300 Diff: 590.5089467763901 alpha value: 1.0254560482036439e-05 
400 Diff: 279.2355946302414 alpha value: 1.0263893422517941e-05 
500 Diff: 155.43169915676117 alpha value: 1.0270028681773919e-05 
600 Diff: 96.61812579631805 alpha value: 1.0274280663010468e-05 
700 Diff: 64.87719237804413 alpha value: 1.027728512597358e-05 
800 Diff: 46.03102707862854 alpha value: 1.0279461929697766e-05 
900 Diff: 34.00975978374481 alpha value: 1.0281092917213468e-05 
Optimizer found with x = [-1.68825261  5.31853629 -3.45322318 ...  1.59365232 -2.85114689   5.04026352] and f(x)=-511573479.5792374 in 1000 iterations
Total time taken: 1min 28s

Вот результат градиентного спуска с альфа = 0,000001.

0   Diff: 26206321.312622845 alpha value: 1e-06 
100 Diff: 112613.38076114655 alpha value: 1e-06 
200 Diff: 21639.659786581993 alpha value: 1e-06 
300 Diff: 7891.810685873032 alpha value: 1e-06 
400 Diff: 3793.90934664011 alpha value: 1e-06 
500 Diff: 2143.767760157585 alpha value: 1e-06 
600 Diff: 1348.4947955012321 alpha value: 1e-06 
700 Diff: 914.9099299907684 alpha value: 1e-06 
800 Diff: 655.9336211681366 alpha value: 1e-06 
900 Diff: 490.05882585048676 alpha value: 1e-06 
Optimizer found with x = [-1.80862488  4.66644055 -3.08228401 ...  2.46891076 -2.57581774   5.34672724] and f(x)=-511336392.26658595 in 1000 iterations
Total time taken: 1min 16s

Как видите, градиентный спуск имеет тенденцию быть быстрее, хотя и не намного (секунды или минуты). Но что более важно, хотя значение α не было выбрано в качестве лучшего параметра при градиентном спуске, при самом крутом спуске шаги намного лучше, чем при градиентном спуске. В приведенном выше примере разница между f (xprev) и f (xcurr) в 900-м для градиента спуск был 450. Эта разница была пройдена намного раньше при наискорейшем спуске (примерно между итерациями 300 и 400).

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

0   Diff: 118618752.30065191 alpha value: 8.569151292666038e-06 
100 Diff: 8281.239207088947 alpha value: 1.1021416896567156e-05 
200 Diff: 1463.1741587519646 alpha value: 1.1087402059869253e-05 
300 Diff: 526.3014997839928 alpha value: 1.1106776689082503e-05 Optimizer found with x = [-1.33362899  5.89337889 -3.31827817 ...  1.77032789 -2.86779156   4.56444743] and f(x)=-511526291.3367646 in 400 iterations
Time taken: 35.8s

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

Вот пример, где у нас есть квадратичная функция от ³⁰ → ℝ. С 10 ступенями самый крутой спуск сгенерирован f(x) = -62434.18. В пределах 1000 шагов сгенерирован градиентный спуск f(x) = -61596.84. Всего за 10 шагов самый крутой спуск уменьшится до значения f ниже, чем у градиентного спуска за 1000 шагов!

Имейте в виду, что сказанное выше работает действительно хорошо только потому, что мы имеем дело с квадратичными функциями. В общем, становится трудно найти значение αk на каждой итерации. Оптимизация g (α) не всегда приводит к нахождению конкретного значения αk. Обычно мы используем итерационные алгоритмы, чтобы минимизировать такие функции. В этом случае все становится утомительно и намного медленнее по сравнению с градиентным спуском. Поэтому крутые спуски не так популярны.

Заключение

В заключение мы изучили три типа алгоритмов:

Метод Ньютона

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

Градиентный спуск

Градиентный спуск - наиболее распространенный алгоритм оптимизации. Это очень быстро, потому что самое дорогое, что нужно сделать на каждом этапе, - это просто вычислить производную. Тем не менее, он включает в себя «угадывание» или «настройку» гиперпараметра, который говорит вам, как далеко вы должны зайти на каждом этапе.

Крутой спуск

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

Записную версию этой статьи можно найти здесь.