梯度下降、牛顿、拟牛顿原理

梯度下降

牛顿法

为Hesse矩阵

参数更新的方程：

每一次迭代的更新方向都是当前点的牛顿方向，步长固定为1。每一次都需要计算一阶导数以及Hesse矩阵的逆矩阵，对于高维特征而言，求逆矩阵的计算量巨大且耗时。

拟牛顿法

牛顿法中的Hesse矩阵在稠密时求逆计算量大，也有可能没有逆（Hesse矩阵非正定）。拟牛顿法提出，用不含二阶导数的矩阵替代牛顿法中的，然后沿搜索方向 做一维搜索。根据不同的构造方法有不同的拟牛顿法。

拟牛顿法

梯度下降优缺点

优点：

方法简单，每次迭代时工作量较小即使选择的初始点不好，也能保证算法收敛

缺点：

在极小值点收敛得很慢收敛速度与变量尺度关系很大关于小的扰动是不稳定的，而小的扰动在计算中容易产生

牛顿法、随机梯度下降算法和直接梯度下降算法的区别

为了便于理解，这里我们将使用只含有一个特征的线性回归来展开。此时线性回归的假设函数为：

批量梯度下降法：

批量梯度下降法是最原始的形式，它是指在每一次迭代时使用所有样本来进行梯度的更新。

求导：更新：

随机梯度下降法：

随机梯度下降法不同于批量梯度下降，随机梯度下降是每次迭代使用一个样本来对参数进行更新。使得训练速度加快。

对于一个样本的目标函数为：

求导：

更新：

随机梯度下降和梯度下降的比较

批量梯度下降：

是最小化所有样本的损失函数，最终得到全局最优解。由于每次更新参数需要重新训练一次全部的样本，代价比较大，适用于小规模样本训练的情况。

随机梯度下降：

每一次迭代得到的损失函数不是最优化每个样本的损失函数，但是大体是向着全局最优，最终的结果往往是在最优解的附近。当目标函数是凸函数的时候，结果一定是全局最优解。适合大规模样本训练的情况。

牛顿法和梯度下降法的比较

1.牛顿法：是通过求解目标函数的一阶导数为0时的参数，进而求出目标函数最小值时的参数。

收敛速度很快。海森矩阵的逆在迭代过程中不断减小，可以起到逐步减小步长的效果。缺点：海森矩阵的逆计算复杂，代价比较大，因此有了拟牛顿法。

2.梯度下降法：是通过梯度方向和步长，直接求解目标函数的最小值时的参数。

越接近最优值时，步长应该不断减小，否则会在最优值附近来回震荡。