文章目录

• 随机梯度下降
• 小批量梯度下降
• 在线学习
• 映射约减

随机梯度下降

在前面的梯度下降算法中，我们使用的都是“批量梯度下降”，其公式为
θ j : = θ j − α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) \theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} θj​:=θj​−αm1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​
上面的梯度下降公式每次迭代都会遍历一次所有的数据，这是数学推导必然的结果，但对于海量数据（ m ≥ 1 0 9 m\ge10^9 m≥109），如果每次迭代都要访问所有数据，那么收敛速度肯定会异常缓慢。

而随机梯度下降则是每次只计算一个样本的代价，即
θ j : = θ j − α 1 m ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) \theta_j:=\theta_j-\alpha\frac{1}{m}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} θj​:=θj​−αm1​(hθ​(x(i))−y(i))xj(i)​ 公式中的 i i i每次随机选择，实现的时候可以打乱数组后遍历访问。一般随机遍历整个训练集一次即可，最多不超过十次。

相比于批量梯度下降，随机梯度下降每次只考虑一个样本，所以迭代速度更快，但方向不会稳定的指向最优解，但大方向还是在朝着代价函数值低的位置走，所以呈现出迂回曲折通向最优解的状态，最后在全局最优解附近徘徊。如果想要更接近全局最优解，我们可以让学习速率 α \alpha α随着迭代次数减小，令
α = C 1 迭代次数 + C 2 \alpha=\frac{C_1}{\text{迭代次数}+C_2} α=迭代次数+C2​C1​​随之而来的是又两个需要调整的参数……

要判断随机梯度下降运行是否正常，自然不能像批量梯度下降那样计算完整的代价函数值，我们可以通过 cost \text{cost} cost函数
cost ( θ , ( x ( i ) , y ( i ) ) ) = 1 2 ( h θ ( x ( i ) ) − y ( i ) ) 2 \text{cost}(\theta,(x^{(i)},y^{(i)}))=\frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2 cost(θ,(x(i),y(i)))=21​(hθ​(x(i))−y(i))2来评估收敛情况。在用样本更新 θ \theta θ之前，先计算一下 cost \text{cost} cost函数（之所以在更新前计算是因为用样本更新以后再计算模型对该样本的代价肯定较低，而我们实际上是想考察模型对整个训练集的代价，所以用更新前的模型计算代价更有代表性一些），每过1000次迭代就将平均 cost \text{cost} cost值绘制出来。

这样得到的曲线就会有一些波动，但大体上的趋势仍然和批量机器学习的学习曲线一致。适当地增大求平均值包含的样本数量（如5000），则能得到更平滑的曲线，不过我们得到算法反馈的延迟就更高了。

小批量梯度下降

批量梯度下降是每次迭代访问所有数据；随机梯度下降是每次迭代只访问一组数据；小批量迭代则介于二者之间，每次访问“小批量”的数据，例如每次访问10组或100组，则迭代过程变为
θ j : = θ j − α 1 m ∑ i = k k + b − 1 ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) \theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=k}^{k+b-1}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} θj​:=θj​−αm1​i=k∑k+b−1​(hθ​(x(i))−y(i))xj(i)​ 每次更新完之后 k : = k + b k:=k+b k:=k+b，这样我们就可以以更快的速度遍历一遍训练集，在向量化做的好的情况下甚至都不需要怎么改动随机梯度下降的代码，缺点是又多了一个需要人工调整的参数 b b b。

在线学习

如果有一个持续的数据流，我们不需要将数据保存下来形成一个特定的数据集去训练模型，只需要像随机梯度下降一样，读进来一个数据，用其对模型进行训练，然后丢弃该数据。这样不仅可以很好地利用持续数据流，还能使得模型跟随数据流的变化不断调整。

映射约减

如果数据太多，我们也可以使用多台计算机协作进行机器学习。原理很简单，将梯度下降的求和部分
∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) \sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} i=1∑m​(hθ​(x(i))−y(i))xj(i)​分解为若干子求和分给一系列计算机，每个计算机只负责求和大求和中的一段，最后再交给中央计算机将这个子和合并（多线程同理）。


只要拖慢算法复杂度的主要部分可以分解为一系列可合并的子问题，都可以考虑采用映射约减来加速运算。吴恩达推荐了一个叫做Hadoop的开源系统，可以实现映射约减。