批量梯度下降和随机梯度下降

批量梯度下降(Batch Gradient Decent)

批量梯度下降的思路是:对于要优化的目标参数,比如$\theta$,在迭代的第$i$步,计算出误差函数的梯度$\nabla_i$,然后沿着负梯度下降某个步长$\alpha$,更新$\theta_{i+1}:=\theta_i - \alpha\nabla_i$,进行下一次迭代。$\alpha$可以随$i$变化,也可以保持不变。
批量梯度下降的过程如下:
$\text{Repeat until convergence}$
$\{$
$\theta:=\theta - \alpha\nabla$
$\}$
批量梯度下降存在一个问题:在每一次迭代中,都需要整个数据集才能计算出梯度。如果数据集大小$m$非常大,则梯度下降法便会运行得很慢。

随机梯度下降(Stochastic Gradient Decent)

随机梯度下降可以克服这个问题,同时仍可以得到一个比较优的解。它的思路是:每次只使用一个样本来确定梯度,循环$m$次,就可以得到一个十分逼近最优解的值。
随机梯度下降的过程如下:
$\text{For $j=1$ to $m$}$
$\{$
$\theta:=\theta - \alpha\nabla_j$
$\}$
其中$\nabla_j$表示用第$j$个样本计算出来的梯度。当然,随机梯度下降不是完美的。它比批量梯度下降收缩得快,但却不太容易收敛到最优值,而是在最优值附近振动$\star$。然而,在许多实际应用中,这个逼近的最优值已经足够。

$\star$ 如果在算法运行过程中逐渐将步长$\alpha$减小至$0$,则可能使结果收敛到最优,而不是在最优解附近振动。

以线性回归为例

数学记号

$m$————————-样本数量
$n$————————–特征数量
$x^{(i)},y^{(i)}$————–第$i$个样本
$x^{(i)}_j$———————-第$i$个样本中第$j$个特征分量
$\theta_j$————————第$j$个参数
$h_{\theta}(x)$——————预测函数

批量梯度下降

$\text{Repeat until convergence}$
$\{$
$\theta_j:=\theta_j - \alpha\sum_{i=1}^m\left(y^{(i)}-h_{\theta}(x^{(i)})\right)x_j^{(i)}\qquad\qquad \text{(for every $j$)}$
$\}$

随机梯度下降

$\text{For $j=1$ to $m$}$
$\{$
$\theta_j:=\theta_j - \alpha\left(y^{(i)}-h_{\theta}(x^{(i)})\right)x_j^{(i)}\qquad\qquad \text{(for every $j$)}$
$\}$

参考资料

  1. 斯坦福大学机器学习公开课
  2. 随机梯度下降(Stochastic gradient descent)和 批量梯度下降(Batch gradient descent )的公式对比、实现对比
  3. CS229 Lecture notes