梯度下降法及其Python实现

梯度降落法（gradient descent），又名最速降落法（steepest descent）是求解无束缚最优化问题最经常使用的方法，它是1种迭代方法，每步主要的操作是求解目标函数的梯度向量，将当前位置的负梯度方向作为搜索方向（由于在该方向上目标函数降落最快，这也是最速降落法名称的由来）。
梯度降落法特点：越接近目标值，步长越小，降落速度越慢。
直观上来看以下图所示：


这里每个圈代表1个函数梯度，最中心表示函数极值点，每次迭代根据当前位置求得的梯度（用于肯定搜索方向和与步长共同决定前进速度）和步长找到1个新的位置，这样不断迭代终究到达目标函数局部最优点（如果目标函数是凸函数，则到达全局最优点）。


下面我们将通过公式来具体说明梯度降落法
下面这个h(θ)是我们的拟合函数


也能够用向量的情势进行表示：


下面函数是我们需要进行最优化的风险函数，其中的每项都表示在已有的训练集上我们的拟合函数与y之间的残差，计算其平方损失函数作为我们构建的风险函数（参见最小2乘法及其Python实现）


这里我们乘上1/2是为了方便后面求偏导数时结果更加简洁，之所以能乘上1/2是由于乘上这个系数后对求解风险函数最优值没有影响。
我们的目标就是要最小化风险函数，使得我们的拟合函数能够最大程度的对目标函数y进行拟合，即：


后面的具体梯度求解都是围绕这个目标来进行。


批量梯度降落BGD
依照传统的思想，我们需要对上述风险函数中的每一个求其偏导数，得到每一个对应的梯度


这里表示第i个样本点的第j份量，即h(θ)中的


接下来由于我们要最小化风险函数，故依照每一个参数的负梯度方向来更新每个


这里的α表示每步的步长


从上面公式可以注意到，它得到的是1个全局最优解，但是每迭代1步，都要用到训练集所有的数据，如果m很大，那末可想而知这类方法的迭代速度！！所以，这就引入了另外1种方法，随机梯度降落。


随机梯度降落SGD
由于批量梯度降落在训练集很大的情况下迭代速度非常之慢，所以在这类情况下再使用批量梯度降落来求解风险函数的最优化问题是不具有可行性的，在此情况下，提出了——随机梯度降落
我们将上述的风险函数改写成以下情势：


其中，


称为样本点的损失函数


接下来我们对每一个样本的损失函数，对每一个求其偏导数，得到每一个对应的梯度


然后根据每一个参数的负梯度方向来更新每个


与批量梯度降落相比，随机梯度降落每次迭代只用到了1个样本，在样本量很大的情况下，常见的情况是只用到了其中1部份样本数据便可将θ迭代到最优解。因此随机梯度降落比批量梯度降落在计算量上会大大减少。


SGD有1个缺点是，其噪音较BGD要多，使得SGD其实不是每次迭代都向着整体最优化方向。而且SGD由于每次都是使用1个样本进行迭代，因此终究求得的最优解常常不是全局最优解，而只是局部最优解。但是大的整体的方向是向全局最优解的，终究的结果常常是在全局最优解附近。


下面是两种方法的图形展现：



从上述图形可以看出，SGD由于每次都是用1个样本点进行梯度搜索，因此其最优化路径看上去比较盲目（这也是随机梯度降落名字的由来）。


对照其优劣点以下：
批量梯度降落：
优点：全局最优解；易于并行实现；整体迭代次数不多
缺点：当样本数目很多时，训练进程会很慢，每次迭代需要耗费大量的时间。

随机梯度降落：
优点：训练速度快，每次迭代计算量不大
缺点：准确度降落，其实不是全局最优；不容易于并行实现；整体迭代次数比较多。

============ 分割分割 =============
上面我们讲授了甚么是梯度降落法，和如何求解梯度降落，下面我们将通过Python来实现梯度降落法。

注意：这里在选取alpha和epsilon时需要谨慎选择，可能不适的值会致使最后没法收敛。

参考文档：

随机梯度降落（Stochastic gradient descent）和 批量梯度降落（Batch gradient descent ）的公式对照、实现对照