从随机梯度下降到Mini-Batch

梯度下降法（gradient descent）是最小化目标函数时最容易想到的方法，但是其缺点也很明显：非常的慢。原因在于，在运行梯度下降时，需要遍历整个训练集，才能进行一步梯度下降，为了避免目标函数的振荡，学习率被限制在一个很小的范围内，所以每一步梯度下降参数的增量非常有限，最后的结果就是算法运行起来很慢。

随机梯度下降

一种更快的梯度下降法被称作随机梯度下降（stochastic gradient descent），对原始梯度下降做了一些改进使得算法运行得更快。

设目标函数（cost function）为

$f(\dot{\vec{w}}) = \sum_{i=1}^{m}f_i(\dot{\vec{w}},\vec{x_i},\vec{y_i})$

其中 $\dot{\vec{w}}$ 为权重张量， $(\dot{\vec{x_i}},\dot{\vec{y_i}})$ 为某一个训练样本点。原始梯度下降的权重更新公式为

$\Delta \dot{\vec{w}} = - \alpha \nabla_{\dot{\vec{w}}}f=-\alpha \sum_{i=1}^{m}\nabla_{\dot{\vec{w}}}f_i(\dot{\vec{w}},\vec{x_i},\vec{y_i})$

随机梯度下降的基本原理是用某个随机的 $\nabla_{\dot{\vec{w}}}f_i$ 来替代整个 $\nabla_{\dot{\vec{w}}}f$ ，设为那么原公式就变得简单起来

$\Delta \dot{\vec{w}} = - \alpha \nabla_{\dot{\vec{w}}}f = - \alpha \nabla_{\dot{\vec{w}}}f_{rand}$

也就是说只用计算一个训练样本的梯度就能进行一步梯度更新，效率大大提高。下面一个很自然的问题就是：该算法是否能收敛到最小值（附近）？答案是肯定的。由于

$E(\nabla_{\dot{\vec{w}}}f_{rand}) = E(\nabla_{\dot{\vec{w}}}f)$

那么当学习率 $\alpha$ 取某些值的时候，在期望的意义下是收敛的，更加精细的证明可以看这篇论文。

即便随机梯度下降在期望意义下收敛，但在极小点附近

$\nabla_{\dot{\vec{w}}}f_{rand}(\vec{w^*}) \neq0$

这降低了梯度下降的精度，所以后来衍生了SAG，SVRG，SDCA算法（先在这里挖个坑），根本目的就在于降低训练集方差导致的梯度方差，从而提升精度。

Mini-Batch梯度下降

Mini-Batch梯度下降也叫小批量梯度下降，基本原理是结合了原始的梯度下降（批量梯度）和随机梯度下降的一种折中方案。

具体来说，该算法将训练集分成若干个Mini-Batch（设为n），每个Mini-Batch含有相同的样本数量（设为k），计算过程变为：每遍历一个Mini-Batch更新一次梯度。

$\begin{aligned} for\space i \space from \space 1 \space to \space n&:\\\quad \Delta \dot{\vec{w}} &= - \alpha \nabla_{\dot{\vec{w}}}f=-\alpha \sum_{i=n_1}^{n_k}\nabla_{\dot{\vec{w}}}f_i(\dot{\vec{w}},\vec{x_i},\vec{y_i})\\ \dot{\vec{w}}&=\dot{\vec{w}}- \Delta \dot{\vec{w}}\end{aligned}$

上述过程为遍历一次训练集所进行的梯度更新。显然，当Mini-Batch中batch size设置为1时，就是随机梯度法，当batch-size设置为m（训练集大小）时，就是原始梯度（批量梯度）法。所以Mini-Batch是批量梯度和随机梯度的一种折中方案。在精度和速度上都做了一些取舍。

至此，我们已经学习了随机梯度和Mini-Batch梯度下降，实践中，Mini-Batch梯度要用得更多一些。

最后编辑于：2019.08.11 21:26:15