机器学习 学习笔记（4）牛顿法 拟牛顿法

牛顿法

考虑无约束最优化问题

其中

为目标函数的极小点。

假设f(x)有二阶连续偏导数，若第k次迭代值为

，则可将f(x)在

附近进行二阶泰勒展开：

这里

是f(x)的梯度向量在点

的值，

是f(x)的海塞矩阵:

在点

的值，函数f(x)有极值的必要条件是在极值点处一阶导数为0，即梯度向量为0.特别是当

是正定矩阵时，函数f(x)的极值为极小值。

牛顿法利用极小点的必要条件

，每次迭代从

开始，求目标函数的极小点，作为第k+1次迭代值

，具体地，假设

满足

，则有

（解释为：当x接近于xk时，

，则

,可以得出：

牛顿法步骤如下：

输入：目标函数f(x)，梯度

，海塞矩阵H(x)，精度要求

输出：f(x)的极小值点

（1）取初始点

，置k=0

（2）计算

（3）若

，则停止计算，得近似解

（4）计算

，并求

：

（5）置

（6）置k=k+1，转（2）

拟牛顿法

牛顿法计算海塞矩阵的逆矩阵开销太多，拟牛顿法用一个近似的矩阵代替海塞矩阵的逆矩阵。

满足条件

记

，

，则

，或

拟牛顿法将

作为

的近似

DFP（Davidon-Fletcher-Powell）算法：

DFP选择

的方法是，假设每一步迭代中矩阵

是由

加上两个附加项构成的，即

，

和

是待定矩阵，这时

，为了使得

满足拟牛顿条件，可以使得

和

满足条件：

，

，当

，

时，满足上述条件，则可以得到

。如果初始

是正定的，那么迭代过程中的每个矩阵

都是正定的。

DFP算法步骤如下：

输入：目标函数f(x)，梯度

，精度要求

输出：f(x)的极小值点

（1）选定初始点

，取

为正定矩阵，置k=0

（2）计算

，若

，则停止计算，得近似解

，否则转（3）

（3）置

（4）一维搜索：求

使得

（5）置

（6）计算

，若

，则停止计算，的近似解

，否则，按照

计算

（7）置k=k+1，转（3）

BFGS(Broyden-Fletcher-Goldfarb-Shanno)算法

BFGS算法是最流行的拟牛顿算法，可以考虑用

逼近海塞矩阵的逆矩阵

，也可以考虑用

逼近海塞矩阵H。这时候，相应的拟牛顿条件是

，则迭代公式

，则

，

和

满足

，

，最终得到

的迭代公式

BFGS算法步骤为：

输入：目标函数f(x)，梯度

，精度要求

输出：f(x)的极小值点

（1）选定初始点

，取

为正定矩阵，置k=0

（2）计算

，若

，则停止计算，得近似解

，否则转（3）

（3）由

，求出

（4）一维搜索，求

使得

（5）置

（6）计算

，若

，则停止计算，的近似解

，否则，按照

计算

（7）置k=k+1，转（3）

关于牛顿法和梯度下降法的效率对比：

　　从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）

　　根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

参考：

1. 《机器学习》
2. 《统计学习方法》
3. 常见的几种最优化方法（梯度下降法、牛顿法、拟牛顿法、共轭梯度法等）