Почему метод Ньютона не широко используется в машинном обучении?

Это то, что беспокоило меня какое-то время, и я не смог найти удовлетворительных ответов в Интернете, так что вот так:

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

Градиентный спуск максимизирует функцию, используя знание ее производной. Метод Ньютона, алгоритм поиска корня, максимизирует функцию, используя знание ее второй производной. Это может быть быстрее, когда вторая производная известна, и ее легко вычислить (алгоритм Ньютона-Рафсона используется в логистической регрессии). Однако аналитическое выражение для второй производной часто является сложным или неразрешимым, требующим большого количества вычислений. Численные методы для вычисления второй производной также требуют большого количества вычислений - если для вычисления первой производной требуются значений, для второй производной требуется .N $N$$N^2$

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

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

• Использование линейного поиска с условиями Вулфа или использование или доверительные регионы предотвращают схождение в седловые точки. Надлежащая реализация градиентного спуска должна делать то же самое. В статье, на которую ссылается Cam.Davidson. Ответ Пилона указывает на проблемы с «методом Ньютона» при наличии седловых точек, но исправление, которое они защищают, также является методом Ньютона.

• Использование метода Ньютона не требует построения всего (плотного) гессиана; Вы можете применить инверсию гессиана к вектору с помощью итерационных методов, которые используют только произведения матрицы на вектор (например, методы Крылова, такие как сопряженный градиент). См., Например, метод доверительной области CG-Steihaug.

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

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

• Кроме того, вычисления переходят от «много много дешевых шагов» к «нескольким дорогостоящим шагам», открывая больше возможностей для параллелизма на уровне подшагов (линейной алгебры).

Для справочной информации об этих концепциях я рекомендую книгу «Численная оптимизация» Носедала и Райта.

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

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

Действительно, отношение числа седловых точек к локальным минимумам увеличивается экспоненциально с размерностью N.

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

Сочетание двух причин:

• Метод Ньютона притягивает к седловым точкам;
• Седловые точки распространены в машинном обучении или фактически при любой многопараметрической оптимизации.

$$f=x^2-y^2$$

$$\mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{H}f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n)$$

$$\mathbf{H}= \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$$

$$\mathbf{H}= \begin{bmatrix} 2 & 0 \\[2.2ex] 0 & -2 \end{bmatrix}$$

$$[\mathbf{H} f]^{-1}= \begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix}$$

$$\nabla f=\begin{bmatrix} 2x \\[2.2ex] -2y \end{bmatrix}$$

$$\mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_{n+1} = \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n -\begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix} \begin{bmatrix} 2x_n \\[2.2ex] -2y_n \end{bmatrix}= \mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_n - \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n = \begin{bmatrix} 0 \\[2.2ex] 0 \end{bmatrix}$$

$x=0,y=0$

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

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

$H$$O(N^2)$$N$$g$$O(N)$$H^{-1} g$$O(N^3)$вычислить. Поэтому, хотя вычисление гессиана обходится дорого, его инвертирование или решение наименьших квадратов часто бывает еще хуже. (Если у вас есть разреженные функции, асимптотика выглядит лучше, но другие методы также работают лучше, поэтому разреженность не делает Ньютона относительно более привлекательным.)

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

• $H^{-1}$ , глядя на то, как изменился градиент за последние несколько шагов.

• $O(N^2)$ приблизительного обратного гессиана. BFGS с ограниченной памятью (L-BFGS) вычисляет направление следующего шага как приблизительное обратное значение гессиана, умноженное на градиент, но требует только сохранения нескольких последних обновлений градиента; он явно не хранит приблизительный обратный гессиан.

• Когда вы вообще не хотите иметь дело с аппроксимирующими вторыми производными, градиентный спуск привлекателен, потому что он использует только информацию первого порядка. Градиентный спуск неявно аппроксимирует обратный гессиан, поскольку скорость обучения умножается на единичную матрицу. Лично я редко использую градиентный спуск: L-BFGS так же легко реализовать, поскольку для него требуется только указать целевую функцию и градиент; оно имеет лучшее обратное гессенское приближение, чем градиентный спуск; и потому что градиентный спуск требует настройки скорости обучения.

• Иногда у вас есть очень большое количество наблюдений (точек данных), но вы можете почти так же извлечь уроки из меньшего количества наблюдений. В этом случае вы можете использовать «пакетные методы», такие как стохастический градиентный спуск, которые циклически используют подмножества наблюдений.

Направление градиентного спуска вычисляется дешевле, и поиск линии в этом направлении является более надежным и устойчивым источником продвижения к оптимальному. Короче говоря, градиентный спуск относительно надежен.

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

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

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

Между градиентным спуском и методом Ньютона есть такие методы, как алгоритм Левенберга – Марквардта (LMA), хотя я видел, что имена немного запутались. Суть заключается в том, чтобы использовать поиск, основанный на градиентном спуске, когда все хаотично и запутанно, а затем переключаться на поиск, основанный на методе Ньютона, когда все становится более линейным и надежным.

$Hd = g$

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

Часто ищется улучшение, а не точное решение, и в этом случае дополнительные затраты на методы, подобные Ньютону или Ньютону, не оправданы.

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

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

Существует много трудностей, связанных с использованием метода Ньютона для SGD, особенно:

• ей нужна матрица Гессе - как ее оценить, например, по шумным градиентам с достаточной точностью при разумных затратах?

• полный гессиан слишком дорог - нам нужно некоторое ограничение, например, для подпространства (какое подпространство?),

• $H^{-1}$$\lambda=0$

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

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

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