大数据梯度下降(斯坦福machine learning week 10)

这对于现代的数据集其实是很现实的。比如对于美国的人口普查数据集来说美国有3亿人口，我们通常都能得到上亿条的数据。
如果我们看一下很受欢迎的网站的浏览量，我们也很容易得到上亿条的记录。
假设我们要训练一个线性回归模型或者是逻辑回归模型，这是梯度下降的规则：

当你在计算梯度下降的时候，这里的m是一个上亿的值时，你需要通过计算上亿个数的导数项的和来计算仅仅一步的梯度下降。
所以这就是大数据梯度下降的背景！！！

在这一系列讲大型的机器学习的课程后，我们会知道如何拟合包括上亿数据的线性回归、逻辑回归、神经网络等等的例子。

1 前提或者条件

在我们训练一个上亿条数据的模型之前，我们还应该问自己为什么不用几千条数据呢？也许我们可以随机从上亿条的数据集里选个一千条的子集，然后用我们的算法计算。
我们通常的方法是画出学习曲线，如果你画了学习曲线而且你的训练目标看上去像这样：

$J_{t r a i n} (θ)$ 是训练集上的代价函数， $J_{c v} (θ)$ 是验证集上的代价函数。从图像中可以看出来，这个算法看起来像是处于高方差的状态。因此，我们需要增加训练集。
相比之下，如果你画出的学习曲线是这样的：

这看起来像经典的高偏差学习算法。在这个例子中，我们可以看出来，数据量增长到一定程度之后，算法并不会好很多。因此我们没必要花费精力来扩大算法的规模。当然，如果你遇到了这种情况，一个很自然的方法是多加一些特征；或者在你的神经网络里加一些隐藏的单元等等。通过这些操作，你的算法的表现会越来越趋于第一种情况的图形

2 大数据梯度下降方法

2.1 批量梯度下降（batch gradient descent）

梯度下降在大量数据的情况下，每一次的梯度下降的计算量就变得非常大，因为需要对所有的训练样本求和。因此，这种在每次迭代中对所有数据都进行计算的梯度下降算法也被称为批量梯度下降(batch gradient descent)。
回忆一下：

假设函数如下：
$h_{θ} (x) = \sum_{j = 0}^{n} θ_{j} x_{j}$
代价函数如下：
$J_{t r a i n} (θ) = \frac{1}{2 m} \sum_{i = 1}^{m} (h_{θ} (x^{(i)}) - y^{(i)})^{2}$
基本流程：

关于详细梯度下降
因此接下来这里我们介绍一种能快速处理大量数据的梯度下降算法：随机梯度下降(stochastic gradient descent)。

2.2 随机梯度下降（stochastic gradient descent简称SGD）

随机梯度下降过程中，在每一次梯度下降的迭代执行前，我们都去用当前的随机样本 $(x^{(i)}, y^{(i)})$ 来计算当前的关于 $θ$ 的cost函数：

c o s t (θ, (x^{(i)}, y^{(i)})) = \frac{1}{2} (h_{θ} (x^{(i)}) - y^{(i)})^{2}

在每次迭代之后都去更新

θ

，每个样本迭代一次。
随机梯度下降的代价函数如下：

c o s t (θ, (x^{(i)}, y^{(i)})) = \frac{1}{2} (h_{θ} (x^{(i)}) - y^{(i)})^{2} J_{t r a i n} (θ) = \frac{1}{m} \sum_{i = 1}^{m} c o s t (θ, (x^{(i)}, y^{(i)}))

随机梯度下降算法中，我们的步骤如下：

1.将所有数据打乱。
2.重复执行梯度下降计算，注意，这里每一次计算θj不是遍历全部的训练集m，而是从m个训练集里取出1个样本来计算。所以每次梯度下降的计算只需要一个样本代入计算。

随机梯度下降过程中，相比于批量梯度下降，会更曲折一些，但每一次的迭代都会更快，因为我们不需要对所有样本求和，每一次只需要保证拟合一个样本即可：
图片描述

实际上，你运行随机梯度下降和批量梯度下降这两种算法的收敛形式是不同的，你会发现随机梯度下降最终会在靠近全局最小值的区域内徘徊，而不是直接逼近全局最小值并停留在那里。但实际上这并没有太大问题，只要参数最终移动到某个非常靠近全局最小值的区域内，这也会得到一个较为不错的假设。这对于目前绝大部分实际应用的目的来说，已经足够了。

由于随机梯度下降每一次的梯度下降计算只需要计算单个样本，而不是像批量梯度下降那样每次计算全部样本，所以随机梯度下降的下降过程会很快。

那么这个外层循环设置为多少是合适的呢？
图片描述

这取决于你样本的数量。一般情况下一次就够了，最多10次是比较典型的。所以我们通常循环执行1到10次。但是这里如果数据集够大的话，其实没有必要再repeat了，因为现在的更新应该能到收敛了，差不多也用不到判断收敛条件了（我是这么感觉的，不知道对不对）

2.3 小批量梯度下降

在之前我们讨论了随机梯度下降以及它是怎样比批量梯度下降更快的。在本节，让我们讨论基于这些方法的另一种变形，叫做小批量梯度下降这种算法有时候甚至比随机梯度下降还要快一点。

在批量梯度下降中每次迭代我们都要用所有的m个样本；然而在随机梯度下降中每次迭代我们只用一个样本；小批量梯度下降的做法介于它们之间。准确地说在这种方法中我们每次迭代使用b个样本，b是一个叫做“小批量规模”的参数。
举个例子来说明：

假如我们有1000个训练样本m=1000，用小批量规模b=10的小批量梯度下降算法来处理，我们梯度下降的过程如下：
图片描述

2.4 小批量梯度下降vs随机梯度下降

那么小批量梯度下降算法和随机梯度下降算法相比，有什么优势呢？

答案是向量化。具体来说，小批量梯度下降算法比随机梯度下降算法更好的原因在于前者每次梯度下降过程中，批量处理的数据可以用一种更向量化的方法来实现，允许你部分并行计算10个样本的和，而随机梯度下降算法每次只去计算一个样本，没有太多的并行计算。

小批量梯度下降算法相比随机梯度下降算法的一个缺点，是有额外的参数bb。因此你需要一些时间来调试小批量bb的大小。但是如果你有一个好的向量化实现，这种方式会比随机梯度下降更快一些。

2.5 随机梯度下降的收敛

如何确保调试过程已经完成并且能正常收敛呢？还有，同样重要的是你怎样调整随机梯度下降中学习速率α的值？在本节中，我们会谈到一些方法来处理这些问题，确保它能收敛以及选择合适的学习速率α。
随机梯度下降过程中，在每一次梯度下降的迭代执行前，我们都去用当前的随机样本 $(x^{(i)}, y^{(i)})$ 来计算当前的关于 $θ$ 的cost函数：

c o s t (θ, (x^{(i)}, y^{(i)})) = \frac{1}{2} (h_{θ} (x^{(i)}) - y^{(i)})^{2}

在每次迭代之后都去更新

θ

，每个样本迭代一次。
最后为了检查随机梯度下降的收敛性，我们要做的是每1000次迭代，我们可以画出前一步中计算出的cost函数。

我们把这些cost函数画出来，并对算法处理的最后1000个样本的cost值求平均值。如果你这样做的话它会很有效地帮你估计出你的算法在最后1000个样本上的表现。所以，我们不需要时不时地计算J_{train}，那样的话需要所有的训练样本。

举例：
假如你已经画出了最后1000组样本的cost函数的平均值，由于它们都只是1000组样本的平均值，因此它们看起来有一点嘈杂，cost的值不会在每一个迭代中都下降（蓝色线）：
图片描述

如果你想试试更小的学习速率，那么你很有可能看到的是算法的学习变得更慢了，因此代价函数的下降也变慢了，但同时由于你使用了更小的学习速率，你很有可能会让算法收敛到一个好一点的解。上图中红色的曲线代表随机梯度下降使用一个更小的学习速率。

出现这种情况是因为随机梯度下降不是直接收敛到全局最小值，而是在局部最小附近反复振荡，所以使用一个更小的学习速率，最终的振荡就会更小。有时候这一点小的区别可以忽略，但有时候一点小的区别你就会得到更好一点的参数。

两种不正常的情况

1000样本画出蓝色线，增加到5000会编程红色的线，但是代价函数是在下降的只不过蓝线用来平均的样本数量太小了，并且蓝线太嘈杂你看不出来代价函数的趋势确实是下降的。
如果是这样的话，那可能就更肯定地说明，由于某种原因导致算法确实没怎么学习好。这时你就需要调整学习速率，或者改变特征变量，或者改变其他的什么。
这是一个很明显的告诉你算法正在发散的信号。那么你要做的事，就是用一个更小一点的学习速率α。

使用可变的学习率α
我们已经知道，当运行随机梯度下降时算法会从某个点开始，然后曲折地逼近最小值，但它不会真的收敛，而是一直在最小值附近徘徊:
图片描述

因此你最终得到的参数，实际上只是接近全局最小值，而不是真正的全局最小值。

在大多数随机梯度下降法的典型应用中，学习速率α一般是保持不变的。因此你最终得到的结果一般来说是上图这个样子的。如果你想让随机梯度下降确实收敛到全局最小值，你可以随时间的变化减小学习速率α的值。

α = \frac{常 数 1}{迭 代 次 数 + 常 数 2}

常数1和常数2是两个额外的参数，你需要选择一下才能得到较好的表现。但很多人不愿意用这个办法的原因是你最后会把时间花在确定常数1和常数2上，这让算法显得更繁琐。但如果你能调整得到比较好的参数的话，你会得到的图形是随着迭代的增加，在最小值附近震荡的范围越来越小，最终几乎靠近全局最小的地方：
图片描述