梯度下降法

梯度下降法（Gradient descent）是一个一阶最优化算法，通常也称最速下降法。要使用梯度下降法找到一个函数的局部极小值，必须向函数上当前点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索。如果相反地向梯度正方向迭代进行搜索，则会接近函数的局部极大值点，这个过程被称为梯度上升法。

描述

梯度下降法基于以下的观察：如果实值函数 $F(x)$在点$a$处可微且有定义，那么函数$F(x)$在$a$点沿着梯度相反的方向$-\nabla F(a)$下降最快。

因而，如果$b=a-\gamma \nabla F(a)$ ，对于$\gamma >0$为一个够小数值时成立，那么$F(a)\geq F(b)$ 。

考虑到这一点，我们可以从函数$F$代码局部极小值的初始估计$x_0$出发，并考虑如下序列$x_0, x_1, x_2, \ldots$使得$x_{n+1}=x_n - \gamma_n\nabla F(x_n), n\geq 0$ ，因此可得到$F(x_0)\ge F(x_1) \ge F(x_2) \ge \cdots$ 。

如果顺利的话序列$(x_n)$收敛到期望的极值。每次的迭代步长$\gamma$可以改变。

下面的图片示例了这一过程，这里假设$F$定义在平面上，并且函数图像是一个碗形。蓝色的曲线是等高线，即函数$F$为常数的集合构成的曲线。红色的箭头指向该点梯度的反方向。需要注意的是，某一点处的梯度方向与通过该点的等高线垂直。沿着梯度下降方向，将最终到达碗底，即函数$F$值最小的点。

梯度下降法处理一些复杂的非线性函数会出现问题，例如Rosenbrock函数$f(x, y) =(1-x)^2 + 100(y-x^2)^2$ 。其最小值在$(x,y)=(1,1)$处，数值为$f(x,y)=0$。但是此函数具有狭窄弯曲的山谷，最小值$(x,y)=(1,1)$就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢。利用梯度下降法求解需要很多次的迭代。

梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的缺点包括：

• 靠近极小值时速度减慢。
• 直线搜索可能会产生一些问题。
• 可能会“之字型”地下降。

Batch Gradient Descent

在优化目标函数的时候，Batch Gradient Descent(BGD)是先计算整个数据集上的梯度，然后再进行更新操作。对于参数$\theta$来说，每更新一次其中的某一位权重$\theta_j$，BGD都需要遍历整个数据集。

对于目标函数$h_θ(x)$用公式来表示就是$θ_j:=θ_j+\alpha \sum_{i=1}^m(y^i−h_θ(x^i))x_j^i$

其中的$(y^i−h_θ(x^i))x^i_j$其实就是对于训练样例$x^i$的$j$属性的梯度，$m$是训练集的大小。从上式中可以看到，BGD是对整个数据集进行扫描，然后计算整体梯度($\sum$求和过程)，再进行更新。其实，这才是真正的梯度.

BGD的优点在于对于凸问题，它是能够保证收敛到全局最优点的。而缺点就是，计算量很大，计算每一位的权重都要遍历整个数据集，这代价未免太大了，计算量是无法接受的。随之而来的另外一个缺点就是BGD是无法进行online训练的，它必须要知道全部的训练集的情况下才能进行训练，这对于一些线上系统也是一个问题。

Stochastic Gradient Descent

SGD是对BGD的一个改进方案，改变之处在更新时不需要遍历整个数据集，而是每一个实例都进行更新。具体公式$θ_j:=θ_j+α(y^i−h_θ(x^i))x^i_j$

比较上式和BGD的公式，我们可以发现区别就在省略了求和过程$\sum$，也就是说更新权重的时候，不需要计算整体的梯度，而是仅仅依靠当前实例的梯度进行更新。

如此改变之后，速度明显提高了很多，但是这也是有风险的。由于进行频繁的梯度更新，很有可能直接跳过了最优点。因此，SGD实际上是无法保证收敛到全局最优点的，而且不是那么的稳定。

Mini-Batch Gradient Descent

而Mini-Batch是对上述两种策略的一种中和，它的基本思想就是从整个训练集上选取一个子集，对这个自己进行BGD的更新。具体公式可以表示为:$θ_j:=θ_j+α\sum_{i=1}^n(y^i−h_θ(x^i))x^i_j$

与BGD的式子相比，会发现唯一的区别在于求和时的项数不一样，此处的$n$不再是训练集的大小，而是一个小于或等于$m$的数，通常范围在于32-256（一般取2的整数幂）。

简单来说，先把大小为$m$的训练集分为大小为$n$的$m_n$个子集（一般最后一个batch的样本个数小于$n$），每次读入一个子集进行梯度计算，更新权重。

相比SGD来说，它更加稳定；相比BGD来说，它计算量较小。

总结

参考

梯度下降法wiki

三种梯度下降法

最优化方法：梯度下降