Перейти к основному содержимому

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

Метод оптимизации Ньютона (Newton's optimization method) позволяет ускорить метод градиентного спуска за счёт использования информации не только о градиенте, но и о матрице вторых производных, называемой матрицей Гессе (Hessian):

∇2L(w)=(∂L(w)∂w1∂w1⋯∂L(w)∂w1∂wD⋯⋯⋯∂L(w)∂wD∂w1⋯∂L(w)∂wD∂wD)∈RD×D\nabla^2 L(\mathbf{w})=\begin{pmatrix} \frac{\partial L(\mathbf{w})}{\partial w_1 \partial w_1} & \cdots & \frac{\partial L(\mathbf{w})}{\partial w_1 \partial w_D} \\ \cdots & \cdots & \cdots \\ \frac{\partial L(\mathbf{w})}{\partial w_D \partial w_1} & \cdots & \frac{\partial L(\mathbf{w})}{\partial w_D \partial w_D} \end{pmatrix} \in \mathbb{R}^{D \times D}

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

Метод Ньютона выглядит следующим образом:

инициализируем настраиваемые веса w\mathbf{w} случайно

пока не выполнено условие остановки:

             w:=w−[∇w2L(w)]−1∇wL(w)\mathbf{w}:=\mathbf{w}-[\nabla_{\mathbf{w}}^2 L(\mathbf{w})]^{-1}\nabla_{\mathbf{w}}L(\mathbf{w})

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

Геометрически метод Ньютона в каждой точке строит параболу (в многомерном пространстве - параболоид), после чего смещает оценку весов в точку минимума этой параболы:

Newton-convergence.png

Детально об условиях сходимости метода Ньютона можно прочитать здесь.

Достоинства и недостатки метода​

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

  • необходимость хранить в памяти матрицу Гессе, размера D×DD\times D, а DD обычно велико при большом числе признаков и при использовании таких перепараметризованных моделей, как нейросети;

  • необходимость обращать матрицу Гессе на каждой итерации, что имеет вычислительную сложность O(D3)O(D^3).

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

Обоснование метода Ньютона​

Рассмотрим минимизацию дважды дифференцируемой функции потерь L(w)→min⁡wL(\mathbf{w})\to\min_{\mathbf{w}}

Пусть w∗=arg⁡min⁡wL(w)\mathbf{w}^{*}=\arg\min_{\mathbf{w}}L(\mathbf{w})

Тогда ∇L(w∗)=0\nabla L(\mathbf{w}^{*})=\mathbf{0}

Разложение Тейлора ∇L(w)\nabla L(\mathbf{w}) относительно w\mathbf{w} в точке w∗\mathbf{w}^{*}:

∇L(w∗)=0=∇L(w)+∇2L(w)(w∗−w)+o(∥w−w∗∥),\nabla L(\mathbf{w}^{*})=0=\nabla L(\mathbf{w})+\nabla^{2}L(\mathbf{w})(\mathbf{w}^{*}-\mathbf{w})+o(\left\lVert \mathbf{w}-\mathbf{w}^{*}\right\rVert ),

откуда

w∗−w=−[∇2L(w)]−1∇L(w)+o(∥w−w∗∥)\mathbf{w}^{*}-\mathbf{w}=-\left[\nabla^{2}L(\mathbf{w})\right]^{-1}\nabla L(\mathbf{w})+o(\left\lVert \mathbf{w}-\mathbf{w}^{*}\right\rVert )

Получаем итоговое правило обновления весов, чтобы (приближённо!) переместиться в точку минимума:

w:=w−[∇2L(w)]−1∇L(w)\mathbf{w} := \mathbf{w}-\left[\nabla^{2}L(\mathbf{w})\right]^{-1}\nabla L(\mathbf{w})

При минимизации квадратичной функции погрешности o(∥w−w∗∥)o(\left\lVert \mathbf{w}-\mathbf{w}^{*}\right\rVert ), её квадратичная аппроксимация будет точной, поэтому метод Ньютона сойдётся за один шаг.