牛顿法可以用于求解方程的根和无约束最优化问题。其背后的数学原理分别对应的是一阶泰勒展开和二阶泰勒展开。
回顾泰勒公式展开:
f(x)=f(x0)+f′(x0)(x−x0)+12f′′(x0)(x−x0)2+O((x−x0)3)f(x)= f(x_0)+f'(x_0)(x-x_0)+{1 \over 2}f''(x_0)(x-x0)^2+O((x-x_0)^3) f(x)=f(x0)+f′(x0)(x−x0)+21f′′(x0)(x−x0)2+O((x−x0)3)
牛顿法求解方程的根
假设我们要求f(x)f(x)f(x)的实数根,也就是解方程f(x)=0f(x)=0f(x)=0,也就是求f(x)f(x)f(x)与xxx轴的交点。
将f(x)f(x)f(x)在x0x_0x0处一阶泰勒展开,并令其等于0
f(x0)+f′(x0)(x−x0)=0(1)\tag{1}f(x_0)+f'(x_0)(x-x_0)=0f(x0)+f′(x0)(x−x0)=0(1)
可以发现,(1)式其实是一条直线。也就是f(x)f(x)f(x)在x=x0x=x_0x=x0处的切线方程。我们求出切线方程与xxx轴的交点xa=x0−f(x0)f′(x0)x_a=x_0-{f(x_0) \over f'(x_0)}xa=x0−f′(x0)f(x0)
在上图中,蓝色的点为f(x)=0f(x)=0f(x)=0的根,黑色的点是xax_axa,我们继续求出f(x)f(x)f(x)在x=xax=x_ax=xa处的切线方程与xxx轴的交点xb=xa−f(xa)f′(xa)x_b=x_a-{f(x_a) \over f'(x_a)}xb=xa−f′(xa)f(xa)。
就这样依次迭代,我们发现每次求出的f(x)f(x)f(x)的切线方程与xxx轴的交点都更接近于f(x)f(x)f(x)真实的根
下图第50次迭代就收敛了,就可以将x50x_{50}x50作为方程f(x)=0f(x)=0f(x)=0的解。
所以在一阶牛顿法中,迭代公式是xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-{f(x_n) \over f'(x_n)}xn+1=xn−f′(xn)f(xn)
牛顿法求解最优化问题
在机器学习中,有很多问题最后都转化为优化问题来解决,通常就是求损失函数的极值问题。在数学中,极值问题通常是令一阶导数为零,也就是求f(x)f(x)f(x)的极值点。这种情况就是求f′(x)=0f'(x)=0f′(x)=0的根。
将f(x)f(x)f(x)在x=x0x=x_0x=x0处二阶泰勒展开。
f(x)=f(x0)+f′(x0)(x−x0)+12f′′(x0)(x−x0)2+O((x−x0)3)(2)\tag{2} f(x)= f(x_0)+f'(x_0)(x-x_0)+{1 \over 2}f''(x_0)(x-x0)^2+O((x-x_0)^3) f(x)=f(x0)+f′(x0)(x−x0)+21f′′(x0)(x−x0)2+O((x−x0)3)(2)
忽略高阶项,对(2)式求导并令其为0
f′(x)=f′(x0)+f′′(x0)(x−x0)=0f'(x)=f'(x_0)+f''(x_0)(x-x_0)=0 f′(x)=f′(x0)+f′′(x0)(x−x0)=0
求得其迭代公式为xn+1=xn−f′(x0)f′′(x0)x_{n+1}=x_{n}-{f'(x_0) \over f''(x_0)}xn+1=xn−f′′(x0)f′(x0)
由于梯度下降法只用到了一阶导数,而牛顿法用到了二阶导数,所以牛顿法收敛更快。
牛顿法与Hessian矩阵
以上推导只针对了单变量的问题,对于多变量的情况,牛顿法的迭代公式变成:
用到了一阶偏导数和二阶偏导数,分别对应雅可比矩阵和海塞矩阵。
JJJ表示雅克比矩阵,对应一阶偏导数:
HHH表示Hessian矩阵,对应二阶偏导数:
多变量的牛顿法由于引入了Hessian矩阵,增加了复杂性,特别是当
Hessian 矩阵非正定(非凸)导致无法收敛;Hessian 矩阵维度过大带来巨大的计算量。
针对这个问题,在 牛顿法无法有效执行的情况下,提出了很多改进方法,比如 拟牛顿法(Quasi-Newton Methods)可以看作是牛顿法的近似。
拟牛顿法 只需要用到一阶导数,不需要计算Hessian矩阵 以及逆矩阵,因此能够更快收敛,关于拟牛顿法之后学习了再更新。 总体来讲,拟牛顿法 都是用来解决 牛顿法 本身的 复杂计算、难以收敛、局部最小值等问题。
参考:/linolzhang/article/details/60151623
/p/46536960