梯度下降法与牛顿法

1. 梯度下降法与牛顿法

 梯度下降和牛顿法的推导均与泰勒公式有关，所以先介绍泰勒展开公式：    基本形式： 
                                                                                   上面这个迭代形式将应用到下面的梯度下降和牛顿法中。
   梯度下降法应用一阶泰勒展开，假设 L (θ)代表损失函数，目标：最小化损失函数，θ是需要更新的模型参数。下面公式中alpha是步长(学习率)，可以直接赋值一个小的数，也可以通过line search。
                                           牛顿法应用二阶泰勒展开，目标：最小化损失函数
                                           g定义为雅克比矩阵，矩阵中各元素对应一阶偏导数   Hessian矩阵中各元素对应二阶偏导数。Hessian矩阵的逆同比于梯度下降法的学习率参数alpha，Hessian的逆在迭代中不断减小，起到逐渐缩小步长的效果。
    1.梯度下降法： 通过梯度方向和步长，直接求解目标函数最小值时的参数。   越接近最优值时，步长应该不断减小，否则会在最优值附近来回震荡。    2.牛顿法：    优点：通过求解目标函数的一阶导数为0时的参数，进而求出目标函数最小值时的参数。收敛速度很快。海森矩阵的逆在迭代过程中不断减小，可以起到逐步减小步长的效果。   缺点：海森矩阵的逆计算复杂，代价比较大，因此有了拟牛顿法。
                                           解决牛顿法计算比较复杂的问题，使用正定矩阵近似Hessian矩阵的逆，简化了运算的复杂度。   常用的拟牛顿算法：DFP算法和BFGS算法

2. 牛顿下降法和梯度下降法基础

 学习机器学习一直是用梯度下降法的，对于牛顿下降法并没有什么了解，但是小学期同学的一个项目用到了牛顿下降法，同时好多大神同学的夏令营之旅问到了牛顿下降法（我等弱鸡疯狂被刷。。。）所以就总结学习一下。
   梯度高等数学都学过，在向量微积分中，标量场的梯度是一个向量场。标量场中某一点上的梯度指向标量场增长最快的方向，梯度的长度是这个最大的变化率。也就是梯度表示数值变化最快的方向，在一元情况下，梯度当然就是斜率，或者导数。在多元的情况下梯度是这样的：
             其实就是计算了φ在三个方向上的微分，表示了在三个方向上的变化量。
   梯度下降法其实就是下面这个式子：
             下一次函数的值为上一次的值在变化最大的方向上移动μ*f ' (x n )。我们知道变化最快可以变大也可以变小那么梯度下降为什么可以保证一定变小呢？
   我们知道梯度方向增加最快，那么梯度方向的反方向是下降最快的，所以在梯度上加负号保证了一定是下降的。例如：f(x)=-3x 它的梯度就是导数-3，在负方向是增加的也就是x减小，函数值增大我们看到上面梯度下降的公式是针对自变量的，那么假设第一步我们处于x=1这个位置，那么下一步可能就在1-0.01*（-3）=1.03，x增大了，最后的函数值减小了，下降了。
   牛顿下降法的递推公式：
             下图是两种方法的图示表示，红色为牛顿下降法，绿色为梯度下降法，从图中直观的感觉是，红色线短，下降速度快。 因为牛顿下降法是用二次曲面去拟合当前的局部曲面，而梯度下降法是用平面去拟合当前的局部曲面，一般用二次曲面拟合的更好，所以一般牛顿算法收敛快。    
                                           
   解释来源于博客：    http://blog.csdn.net/njucp/article/details/50488869    一阶泰勒展式如下表示：   
             
   我们的目的是使得左边的值变小，那是不是应该使得下面的式子变为负值。
             但是如何使得上式一定为负值，简单的方法就是：
                       但是不要忘了以上所有的一切只有在局部成立，也就是说在小范围才成立，那么下式就有很能太大 :
                       得到最终的梯度下降公式。   平面拟合曲面是有于一阶泰勒展开。那么二次曲面拟合曲面的牛顿迭代很显然就是二阶泰勒展开的结果了。考虑一下二阶泰勒：
             同样我们希望左式最小，那么将左式看成是△x的函数，当取合适的△x值时，左边的式子达到极小值，此时导数为0。因此上式对△x进行求导数，得到以下公式：
             所以有：
                       第一种解释是， 牛顿下降法利用了函数的更多的信息，能够更好的拟合局部曲面，所以收敛的速度也会加快。 
   第二种是：   关于梯度下降算法，其中最重要的就是要确定步长μ，它的值严重的影响了梯度下降算法的表现。   接下来考虑如下公式：
             和
                                 由此可见牛顿下降法是梯度下降法的最优情况，因此牛顿下降法的收敛的速度必然更快。
   对于高维数据要计算Hessian 矩阵，关于Hessian 矩阵，很简单，自行百度吧。
   机器学习大多数都有着极高维度的特征以及极多的样本，所以计算Hessian 矩阵需要的时间很长，效率很低。   还有来自知乎大神的关于牛顿法的缺点和优点：    https://www.zhihu.com/question/19723347/answer/28414541 ）
   来源于博客：    http://blog.csdn.net/itplus/article/details/21896453 ，我觉得写的很好。   
                                                                                                                                                                   
   见我的下一篇文章吧2333！