机器学习:随机梯度下降法

在感知机学习算法中,我们得到损失函数$L(w,b)$后,对于误分类点集合M,对损失函数$L(w,b)$分别关于$w$和$b$的梯度求梯度得到:

根据上面的梯度,我们可以得到$w$和$b$的更新公式:

但是在实际在使用的时候,并不会把$\sum$带入进去,而采用的是下面的式子进行迭代更新的(见统计学习方法第28页):

即在实际训练的时候,我们随机初始化$w$和$b$,然后选取训练集中的一个点,如果该点属于误分类点(所以损失函数前会多一个负号),即$y_i(wx_i+b)\leq 0$,按照上面的进行权重和偏置的更新。

那为什么在更新的时候不要前面的$\sum$求和呢?

这个问题在Deep Learning, Perceptron, Backpropagation第26:38分有相应的解答,主要的区别使用梯度下降的类型不一样,梯度下降按使用训练样本的数目不一样可以一分为Batch gradient descent(批量梯度下降)、Stochastic gradient descent(SGD, 随机梯度下降)以及Mini-batch gradient descent(小型批量梯度下降)三种方式,批量梯度下降和随机梯度下降的差异如下(摘自An overview of gradient descent optimization algorithms):

Batch gradient descent performs redundant computations for large datasets, as it recomputes gradients for similar examples before each parameter update. SGD does away with this redundancy by performing one update at a time. It is therefore usually much faster and can also be used to learn online.

随机梯度下降主要考虑到批量梯度下降会在每次迭代的时候会重复样本的梯度,在数据量小的情况下还ok,但是,在“大数据”背景下的今天,显然批量梯度计算复杂度会大很多。那么为什么可以用随机梯度下降来代替批量梯度下降呢?我们可以回到上面那个提到的视频中找到相应的解释:

Though the sigma that it gives you the correct direction but you can show that stochastic gradient descent all most of the time it gives you a good direction. You know it may happen that using only one point you go wrong for in one iteration, but over all you go to the right direction generally and it’s faster.

也就是对于一次一个样本点的迭代,它可能不会给出正确的(逼近最优解)的方向,但是从整体上来讲,它还是会给出正确的方向。这就好比奔向同一个目的地的过程中,大部队走阳光大道和一个人单枪匹马抄小道,大部队虽然一直都在想着目的地的方向直行,但因为装备辎重多而行进(计算)的速度慢,而一个人单枪匹马虽然并不是总是向着目的地的方向行进,但最后的目的地却还是最终相同的目的地。

所以,上面的感知机在迭代更新的时候,每次训练使用的样本只有1个,属于SGD优化方法。

comments powered by Disqus