深度学习基础 - 牛顿法
flyfish
关于优化算法
一个是一阶优化算法(first-order optimization algorithms),如梯度下降,使用梯度信息的优化算法。
另一个是二阶最优化算法(second-order optimization algo-rithms)如牛顿法,使用Hessian矩阵的优化算法。
之前介绍了梯度下降方法,此次介绍的是牛顿法
牛顿法 还有其他名字
牛顿迭代法
Newton’s method
牛顿-拉夫逊方法
Newton-Raphson method
本文用牛顿法来解决损失函数为 f ( x , y ) = x 2 + 9 y 2 f(x,y) = x^{2}+9y^{2} f(x,y)=x2+9y2的情况。
可视化 f ( x , y ) = x 2 + 9 y 2 f(x,y) = x^{2}+9y^{2} f(x,y)=x2+9y2
公式
x t + 1 ← x t − η H t − 1 g t \textbf{x}_{t+1} \leftarrow \textbf{x}_{t} - \eta \textbf{H}_{t}^{-1} \textbf{g}_{t} xt+1←xt−ηHt−1gt
其中
η \eta η为 Learning Rate,
H t = ∇ 2 f ( x t ) \textbf{H}_{t} = \nabla^{2}f(\textbf{x}_{t}) Ht=∇2f(xt)( 称为 Hessian)
g t = ∇ f ( x t ) \textbf{g}_{t}=\nabla f(\textbf{x}_{t}) gt=∇f(xt)( 称为 Gradient)。
首先画出起始点 ( − 4 , 2.5 ) (-4, 2.5) (−4,2.5),如下图
算 g \textbf{g} g和 H − 1 \textbf{H}^{-1} H−1,分别是:
g \textbf{g} g是
g = [ ∂ f ( x , y ) ∂ x ∂ f ( x , y ) ∂ y ] = [ 2 x 18 y ] \textbf{g} = \begin{bmatrix} \dfrac{ \partial f(x,y) }{\partial x} \\[0.3em] \dfrac{\partial f(x,y) } {\partial y} \\[0.3em] \end{bmatrix} = \begin{bmatrix} 2x \\[0.3em] 18y \\[0.3em] \end{bmatrix} g=⎣
⎡∂x∂f(x,y)∂y∂f(x,y)⎦
⎤=[2x18y]
H − 1 \textbf{H}^{-1} H−1是
H − 1 = [ ∂ 2 f ( x , y ) ∂ x 2 ∂ 2 f ( x , y ) ∂ x y ∂ 2 f ( x , y ) ∂ x y ∂ 2 f ( x , y ) ∂ y 2 ] − 1 = [ 2 0 0 18 ] − 1 = [ 1 2 0 0 1 18 ] \textbf{H}^{-1} = \begin{bmatrix} \dfrac{ \partial^{2} f(x,y) }{\partial x^{2}} & \dfrac{ \partial^{2} f(x,y) }{\partial xy} \\[0.3em] \dfrac{ \partial^{2} f(x,y) } {\partial xy} & \dfrac{ \partial^{2} f(x,y) }{\partial y^{2}} \\[0.3em] \end{bmatrix} ^{-1} = \begin{bmatrix} 2 & 0 \\[0.3em] 0 & 18 \\[0.3em]\end{bmatrix} ^{-1} =\begin{bmatrix} \frac{1}{2} & 0 \\[0.3em] 0 & \frac{1}{18} \\[0.3em] \end{bmatrix} H−1=⎣
⎡∂x2∂2f(x,y)∂xy∂2f(x,y)∂xy∂2f(x,y)∂y2∂2f(x,y)⎦
⎤−1=[20018]−1=[2100181]
假如 η = 0.5 \eta = 0.5 η=0.5,代入起始点 ( x 0 , y 0 ) = ( − 4 , 2.5 ) (x_{0},y_{0}) = (-4, 2.5) (x0,y0)=(−4,2.5)、 g \textbf{g} g和 H − 1 \textbf{H}^{-1} H−1到 牛顿法的公式: ¥ x t + 1 ← x t − η H t − 1 g t ¥\textbf{x}_{t+1} \leftarrow \textbf{x}_{t} - \eta \textbf{H}_{t}^{-1} \textbf{g}_{t} ¥xt+1←xt−ηHt−1gt
得:
[ x 1 y 1 ] = [ − 4 2.5 ] − 0.5 [ 1 2 0 0 1 18 ] [ 2 × ( − 4 ) 18 × 2.5 ] = [ − 2 1.25 ] \begin{bmatrix} x_{1} \\[0.3em] y_{1} \\[0.3em] \end{bmatrix} =\begin{bmatrix} -4 \\[0.3em] 2.5 \\[0.3em] \end{bmatrix} - 0.5 \begin{bmatrix} \frac{1}{2} & 0 \\[0.3em] 0 & \frac{1}{18} \\[0.3em] \end{bmatrix} \begin{bmatrix} 2 \times (-4) \\[0.3em] 18 \times 2.5 \\[0.3em] \end{bmatrix} =\begin{bmatrix} -2 \\[0.3em] 1.25 \\[0.3em] \end{bmatrix} [x1y1]=[−42.5]−0.5[2100181][2×(−4)18×2.5]=[−21.25]
更新图上的点, ( x 1 , y 1 ) = ( − 2 , 1.25 ) (x_{1},y_{1}) = (-2, 1.25) (x1,y1)=(−2,1.25),如下图:
再继续,求 ( x 2 , y 2 ) (x_{2},y_{2}) (x2,y2)的值,如下:
[ x 2 y 2 ] = [ − 2 1.25 ] − 0.5 [ 1 2 0 0 1 18 ] [ 2 × ( − 2 ) 18 × 1.25 ] = [ − 1 0.625 ] \begin{bmatrix} x_{2} \\[0.3em] y_{2} \\[0.3em] \end{bmatrix} = \begin{bmatrix} -2 \\[0.3em] 1.25 \\[0.3em] \end{bmatrix} - 0.5 \begin{bmatrix} \frac{1}{2} & 0 \\[0.3em] 0 & \frac{1}{18} \\[0.3em] \end{bmatrix} \begin{bmatrix} 2 \times (-2) \\[0.3em] 18 \times 1.25 \\[0.3em] \end{bmatrix} =\begin{bmatrix} -1 \\[0.3em] 0.625 \\[0.3em] \end{bmatrix} [x2y2]=[−21.25]−0.5[2100181][2×(−2)18×1.25]=[−10.625]
如此计算下去结果是
牛顿法的方向不需要一直折返,可以直接往最小值处走下去 ,整个过程动画展示
部分动画展示
完整动画展示
梯度下降法和牛顿法对比
可视化梯度下降
梯度下降背后的原理
采用梯度下降法的动画展示
可视化 f ( x , y ) = x 2 + 9 y 2 f(x,y) = x^{2}+9y^{2} f(x,y)=x2+9y2的代码
from PIL import Image
from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
plt.figure()
ax = plt.axes(projection="3d")
x = np.arange(-5,5,0.1)
y = np.arange(-3,3,0.1)
X,Y = np.meshgrid(x,y)
Z = X**2+9*Y**2
ax.plot_surface(X,Y,Z,alpha=0.6)
ax.contour(X,Y,Z,zdir="z",offset=-1,cmap="rainbow")
ax.set_xlabel("X")
ax.set_xlim(-6,6)
ax.set_ylabel("Y")
ax.set_ylim(-6,6)
ax.set_zlabel("Z")
plt.figure(figsize=(10, 5))
plt.show()