梯度下降和拟牛顿

Posted by ZhY on April 27, 2017

梯度下降

在[线性回归][1]中,我们分析了梯度下降算法,但是仍然存在一些问题。在梯度下降过程中,我们无法确定学习率的取值。

首先分析固定学习率,在学习率固定的情况下,往往收敛的比较慢,效果并不理想。

因此我们考虑学习率设置应该尽量在斜率大的地方用小学习率,而在斜率小的地方用大学习率。

由于在梯度下降过程中,,因此我们可以将其看做关于的函数

由于梯度下降是寻找最小的,因此在给定情况下,应寻找最小的,即:

则局部最小值满足

可以采用二次差值线性搜索等方法进行迭代寻找。

牛顿法

将梯度下降的式子变为即为牛顿法。

牛顿法相当于对于一阶导数进行了一些修正,具有二次收敛性,但是初始点必须尽量靠近极值点,否则可能不收敛。而且若目标函数的Hessian矩阵无法保持正定或者是奇异的,则牛顿法会出现问题。

修正牛顿方向

(1)令搜索方向改为:

(2)用正定矩阵替代Hessian矩阵

拟牛顿法

由于Hessian矩阵求逆比较复杂,因此选用一些近似的矩阵来代替Hessian矩阵。所以产生了BFGS算法以及LBFGS算法