LionKing数据科学专栏

购买普通会员高级会员可以解锁网站精华内容且享受VIP服务的优惠

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏

牛顿法(Newton's method)

牛顿法

牛顿法是一个最优化的常见算法。梯度下降类算法,包括批量梯度下降法、随机梯度下降法、小批量梯度下降法的共同缺点是需要确定学习速率$\alpha$。

对于一个不好的学习速率,收敛速度会很慢,甚至会出现不收敛(overshoot)的情况。

牛顿法利用了函数的二阶梯度信息/海森矩阵,从而加快了每一步的收敛速度。

牛顿法的缺点是计算时需要用到二阶梯度信息以及对海森矩阵求逆,因此每一步需要更多的计算量。

人们更多地使用拟牛顿法,如著名的L-BFGS来加快计算。

一元函数的牛顿法

牛顿法可以用来解决一元方程的求解问题$f(x) = 0$或者解决一元方程的最小化问题$\min f(x)$。

最小化问题等价于求解$g(x) = f'(x) = 0$,因此我们通过一元方程的求解问题来介绍牛顿迭代法。

如图所示,牛顿迭代法可以逐步地接近方程的解并收敛。

牛顿法的几何意义是每次从$x^{(b)}$出发,计算$g$在$(x^{(b)}, g(x^{(b)}))$处的切线与横轴(x-axis)的交点作为$x^{(b + 1)}$。

更新方程为

$$x^{(b + 1)} \leftarrow x^{(b)} - \frac{g(x^{(b)})}{g'(x^{(b)})}$$

对于解方程问题,牛顿迭代法相当于每次将$g$看作其在$x^{(b)}$处的一阶泰勒逼近(Taylor's approximation)$\widetilde{g}$并求解。

对于最小化$f$的问题,牛顿迭代如下:

对于最小化问题,牛顿迭代法相当于每次将$f$看作其在$x{(b)}$处的二阶泰勒逼近$\widetilde{f}$并对其最小化。

实例

Q:给定$y \gt 0$,近似地计算$\sqrt{y}$。

A:该问题是一个非常常见的算法问题,一个标准的解法是使用二分搜索。

而更有效率的算法是使用牛顿迭代求解$g(x) = x^2 - y$。

牛顿迭代方程为$$x^{(b + 1)} = x^{(b)} - \frac{g(x^{(b)})}{g'(x^{(b)})} = x^{(b)} - \frac{x^{(b)2} - y}{2x^{(b)}} = \frac{x^{(b)} + \frac{y}{x^{(b)}}}{2}$$

Q:最小化$f(x) = x^2$

A:牛顿迭代方程为

$$x^{(b + 1)} = x^{(b)} - \frac{f'(x^{(b)})}{f''(x^{(b)})} = x^{(b)} - \frac{2x^{(b)}}{2} = 0$$

牛顿迭代一步就求得了最优解$\hat{x} = 0$。

多元函数的牛顿法

对于多元函数的最小化问题$f: \mathbb{R}^p \rightarrow \mathbb{R}$

可以将一元的牛顿法推广如下:

类似于一元的牛顿迭代,$x^{(b + 1)}$是$f$在$x^{(b)}$处的二阶泰勒逼近的最小值点。

对于线性回归而言,$f$本身是二次函数,因此$f$在$x^{(1)}$出的二阶泰勒逼近就是$f$本身。因此使用牛顿迭代法可以在一个迭代内直接求得最优解$\hat{\beta} = (X^TX)^{-1}X^Ty$。

拟牛顿法(quasi-Newton's method)

牛顿法的优点是收敛速度快,而缺点是牛顿法的计算中需要计算海森矩阵和该矩阵的逆。海森矩阵往往需要较大的计算量,而且一般矩阵的求逆运算时间复杂度是$O(p^3)$。

为了保持收敛速度快的同时,减小每一步迭代的计算量,我们可以将海森矩阵的逆替换为一个近似的矩阵。而该矩阵的计算复杂度远小于原始的海森矩阵求逆。

比较著名的拟牛顿法有DFP和BFGS和L-BFGS。

更多最优化相关问题见本网站论坛最优化版面

更多面试问题见面试真题汇总

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏