斯坦福机器学习课程 第十周 (1)大数据集梯度下降

处理大数据的学习算法

视频地址

在接下来的几节中,我们会讲大规模的机器学习(就是用来处理大数据的算法)。如果我们看近5到10年的机器学习的历史,我们会发现现在的学习算法比5年前的好很多,其中的原因之一就是我们现在拥有很多可以训练算法的数据。

在机器学习领域有一种说法是:

  • “It`s not who has the best algorithm that wins. It`s who has the most data.”

  • “谁的数据最多,谁才能笑到最后。”

因此,我们更期望在大的数据集上做训练。

但训练大的数据集也有它自己的问题,特别是计算量的问题。

假设我们的训练集的大小$m=100,000,000$。

这对于现代的数据集其实是很现实的。比如对于美国的人口普查数据集来说美国有3亿人口,我们通常都能得到上亿条的数据。

如果我们看一下很受欢迎的网站的浏览量,我们也很容易得到上亿条的记录。

假设我们要训练一个线性回归模型或者是逻辑回归模型,这是梯度下降的规则:

当你在计算梯度下降的时候,这里的$m$是一个上亿的值时,你需要通过计算上亿个数的导数项的和来计算仅仅一步的梯度下降。

在接下来的内容中,我们会介绍如何优化这个算法,或者换一个更高效率的算法。

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

当然,在我们训练一个上亿条数据的模型之前,我们还应该问自己为什么不用几千条数据呢?也许我们可以随机从上亿条的数据集里选个一千条的子集,然后用我们的算法计算。

在我们投入精力和开发软件来训练大数据的模型之前,我们往往会在一个比较小的数据集上来验证算法是否合适。

我们通常的方法是画出学习曲线,如果你画了学习曲线而且你的训练目标看上去像这样:

$J_{train}(\theta)$是训练集上的代价函数,$J_{cv}(\theta)$是验证集上的代价函数。从图像中可以看出来,这个算法看起来像是处于高方差的状态。因此,我们需要增加训练集。

相比之下,如果你画出的学习曲线是这样的:

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

而这个过程中,我们应该花时间在添加基础设施来改进算法,而不是用多于一千条数据来建模,因为改进算法会更加有效果。

所以在大规模的机器学习中,我们喜欢找到合理的计算量的方法或高效率的计算量的方法来处理大的数据集。

随机梯度下降

视频地址

对于线性回归、逻辑回归、神经网络等等很多机器学习算法,其实现都是通过得出某个代价函数或者某个最优化的目标来实现的,然后使用梯度下降这样的方法来求得代价函数的最小值。当我们的训练集较大时,梯度下降算法则显得计算量非常大。

在本节,我想介绍一种跟普通梯度下降不同的方法:随机梯度下降(stochastic gradient descent)。用这种方法我们可以将算法运用到较大训练集的情况中。

梯度下降回顾

关于随机梯度下降我们这里虽然是以梯度下降为例,但其思想也可以应用于其他的学习算法中。

首先来复习一下之前学过的线性回归模型,我们的假设函数如下:

$$
h_{\theta}(x)=
\sum_{j=0}^n\theta_jx_j
$$

代价函数如下:

$$
J_{train}(\theta)=
\frac{1}{2m}
\sum_{i=1}^m
(h_\theta(x^{(i)})-y^{(i)})^2
$$

如果我们的参数是一个二维向量,只有$\theta_1$和$\theta_2$,那么它在三维空间中的代价函数图形如下:

我们的梯度下降内部循环执行的操作如下:

通过反复的更新$\theta_j$,我们的代价函数会逐渐找到局部最优解。

这是梯度下降执行过程中,轮廓图观察到的迭代轨迹的变化情况:

可以看到其沿着梯度下降方向快速的收敛到了全局最小。

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

随机梯度下降原理

由于批量梯度下降算法在大量数据的情况下,运算量巨大,并不适用。因此这里我们介绍一种能快速处理大量数据的梯度下降算法:随机梯度下降(stochastic gradient descent)

随机梯度下降的代价函数如下:

$$
cost(\theta,(x^{(i)},y^{(i)}))
=\frac{1}{2}
(h_\theta(x^{(i)})-y^{(i)})^2
\\
J_{train}(\theta)=
\frac{1}{m}
\sum_{i=1}^m
cost(\theta,(x^{(i)},y^{(i)}))
$$

随机梯度下降算法中,我们的步骤如下:

  • 1.将所有数据打乱。
  • 2.重复执行梯度下降计算,注意,这里每一次计算$\theta_j$不是遍历全部的训练集$m$,而是从$m$个训练集里取出1个样本来计算。所以每次梯度下降的计算只需要一个样本代入计算。这一点是和批量梯度下降最大的不同:

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

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

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

最后还有一个细节点,在随机梯度下降的过程中,我们定义了一个外层循环,那么这个外层循环应该定义为多少次呢?

那么这个外层循环设置为多少是合适的呢?

这取决于你样本的数量。一般情况下一次就够了,最多10次是比较典型的。所以我们通常循环执行1到10次。

例如对于300,000,000个美国公民的样本数据来说,如果我们循环执行3次,这里的总计算量就是$3 × 300000000 = 900000000$次。

这就是随机梯度下降算法的全部。

小批量梯度下降

视频地址

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

小批量梯度下降概念

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

举个例子来说明:

假如我们有1000个训练样本$m=1000$,用小批量规模$b=10$的小批量梯度下降算法来处理,我们梯度下降的过程如下:

我们每次梯度下降的过程中,都去取10个样本来计算梯度下降的更新。

这就是小批量梯度下降算法。它也比批量梯度下降快很多。

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

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

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

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

随机梯度下降的收敛

视频地址

现在你已经知道了随机梯度下降算法,但是当你运行这个算法时,你如何确保调试过程已经完成并且能正常收敛呢? 还有,同样重要的是你怎样调整随机梯度下降中学习速率$α$的值?在本节中,我们会谈到一些方法来处理这些问题,确保它能收敛以及选择合适的学习速率$α$。

随机梯度下降的收敛

在批量梯度下降的算法中,我们确定梯度下降已经收敛的一个标准方法是画出最优化的代价函数$J_{train}(\theta)$。

$$
J_{train}(\theta)=
\frac{1}{2m}
\sum_{i=1}^m
(h_{\theta}(x^{(i)})-y^{(i)})^2
$$

我们要确保代价函数在每一次的迭代中都是下降的。当训练集比较小的时候,计算这个求和是比较方便的,因此我们不难完成。但当你的训练集非常大的时候,这种求和就不方便了,因此我们引入随机梯度下降,每次只考虑一个样本,不需要时不时的扫描一遍全部的训练集。

具体来说,对于随机梯度下降算法,为了检查算法是否收敛,我们可以进行下面的工作:

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

$$
cost(\theta,(x^{(i)},y^{(i)}))=
\frac{1}{2}
(h_{\theta}(x^{(i)})-y^{(i)})^2
$$

在每次迭代之后都去更新$\theta$,每个样本迭代一次。

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

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

例子

下面是几幅画出来的图的例子:

学习率大小对收敛的影响

假如你已经画出了最后1000组样本的cost函数的平均值,由于它们都只是1000组样本的平均值,因此它们看起来有一点嘈杂,cost的值不会在每一个迭代中都下降,你可能会得到一种这样的图像:

由于每次都是在一小部分的样本(1000个)上去求平均值,因此看起来是有噪声的。如果你得到像这样的图,那么你应该判断这个算法的代价值是在下降的,并且后来趋于平缓,这基本说明你的算法已经收敛了。

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

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

每次计算代价函数的最小样本数对收敛的影响

假如你还是运行随机梯度下降,对1000组样本取cost函数的平均值并且画出图像,那么可能得到的图形如下:

如果你把这个数1000提高到5000组样本,那么可能你会得到一条更平滑的曲线:

通过在5000个样本中求平均值,你会得到比刚才1000组样本更平滑的曲线。这是你增大平均的训练样本数的情形。当然增大它的缺点就是现在每5000个样本才能得到一个数据点,因此你所得到的关于学习算法表现的反馈,就显得有一些“延迟”。

代价函数不再收敛的情况

有时候你运行梯度下降可能也会得到这样的图像:

如果出现这种情况,可能你的代价函数就没有在减小了。如果你对这种情况时,也用更大量的样本进行平均,你很可能会观察到红线所示的情况:

能看得出,实际上代价函数是在下降的只不过蓝线用来平均的样本数量太小了,并且蓝线太嘈杂你看不出来代价函数的趋势确实是下降的。所以可能用5000组样本来平均比用1000组样本来平均更能看出趋势。

当然,即使是使用一个较大的样本数量,你还是可能会发现这条学习曲线还是比较平坦的。如果是这样的话,那可能就更肯定地说明,由于某种原因导致算法确实没怎么学习好。这时你就需要调整学习速率,或者改变特征变量,或者改变其他的什么。

代价函数发散时

如果你画出曲线是这样一种上升的情况时:

这是一个很明显的告诉你算法正在发散的信号。那么你要做的事,就是用一个更小一点的学习速率$α$。

使用可变的学习率$α$

我们已经知道,当运行随机梯度下降时算法会从某个点开始,然后曲折地逼近最小值,但它不会真的收敛,而是一直在最小值附近徘徊:

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

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

所以一种典型的设置$α$的值的方法是让

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

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

但由于确定这两个常数需要更多的工作量,并且我们通常也对能够很接近全局最小值的参数已经很满意了,因此在随机梯度下降中我们很少采用逐渐减小$α$的值的方法。你看到更多的还是让$α$的值为常数。

坚持原创技术分享,您的支持将鼓励我继续创作!