大规模机器学习

点击量:158

本文覆盖Coursera Machine Learning Week 10的内容。

大数据集的学习(Learning with large data set)
如果我们回顾过去10年机器学习的发展历史,你会发现现在的学习算法效果比之前要好很多,其中一个重要的原因是现在比以前拥有更多可以供训练的数据。所以有人会说拥有更多的数据比算法更重要:“It’s not who has the best algorithm that wins, it’s who has the most data.”。所以这篇文章会介绍一些在大数据规模下的机器学习技巧。
先回顾一下之前的梯度下降公式:
$$\theta_{j} := \theta_{j} – \alpha\frac{1}{m}\sum_{i=1}^{m}\left ( h_{\theta}\left ( x^{(i)}\right )- y ^{(i)}\right ) x_{j}^{(i)}$$
上面公式中\(m\)的值可能会很大,比如\(m\)等于一个亿,不要以为这个数据量很大,在实际应用中是很常见的。如果还是按照之前的方法进行梯度下降,那么每下降一小步就要累加一次一个亿的数据,计算量必然很大,训练速度也不快。实际上,在训练这一亿条数据之前,我们往往会试着先训练其中的一小部分数据,看看是否能达到满意的效果。具体地,我们通过绘制学习曲线(learning curve)的方式来判断是否需要更多的训练数据。

如果你的学习曲线如左图所示,看上去像是一个经典的高分差学习算法(high-variance learning algorithm)那么就说明需要等多的数据进行训练以提升性能;如果像右边的图像,看上去像是一个经典的高偏差学习算法(high-bias learning algorithm)则表示再多的数据也不能提高效果了。

随机梯度下降(Stochastic gradient descent)
传统的梯度下降算法的一个特点就是每一次梯度下降都要把所有的样本数据累加起来,所以又被称为批量梯度下降算法(batch gradient descent)。当样本数据量变得很大时,批量梯度下降算法就会变得很慢,因为计算量很大。这里我们提出一种被称为随机梯度下降的算法,它能够很好的降低计算量,使得收敛的速度更快。具体算法如下:

  1. 随机打乱样本数据
  2. Repeat {
        for \(i := 1,…,m\) {
            for \(j:=0,…,n\) {
                \(\theta_{j} := \theta_{j} – \alpha(h_{\theta}(x^{(i)} – y^{(i)}))x_{j}^{(i)}\)
                }
            }
    }

这个算法跟之前的批量梯度下降算法最大的不同在于:每一次梯度下降的粒度是每一个样本数据而不是所有的样本数据,这样最终收敛时只需要遍历一遍数据集即可。也因此它的收敛过程和批量梯度下降是不一样的,如下图所示:

从局部来看,随机梯度下降可能是迂回的,但是从整体来看肯定是是向中心全局最小值收敛的。但它并不会直接收敛至全局最小值,而是在全局最小值附近反复震荡。其实,只要参数逼近到足够靠近全局最小值,也会得到一个较为不错的效果。
上文介绍的批量梯度下降每次迭代需要考虑全部的样本数据\(m\),而随机梯度下降则是每次迭代只考虑一个样本,因此我们提出一种介于两者之间的算法:小批量梯度下降算法(min-batch gradient descent),与前两个算法唯一的不同是这个算法的每次迭代考虑\(b\)个样本,b一般在2-100之间。如果你有一个好的向量化的实现,这种方法甚至比随机梯度下降收敛的更快。

随机梯度下降的收敛

  • 如何检查是否收敛?
    在批量梯度下降中,我们会绘制出代价函数:\(J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^{m}\left ( h_{\theta}\left ( x^{(i)}\right )- y ^{(i)}\right )^{2}\)和迭代次数的函数图像,代价函数的值应当是随着迭代次数的增加而逐渐减小的,这样我们才能确信梯度下降是收敛的。这种方法在数据量不大的情况下能工作的很好,但是当数据量太大时会很慢。在检查随机梯度下降算法是否收敛时,我们不用把所有样本数据的代价函数都算出来,而是在每一次迭代过程中,在更新\(\theta\)值之前把每一个样本的代价函数算出来,然后每1000次计算出这1000个样本的代价函数的平均值,再以1000次为单位绘制代价函数和迭代次数的函数图像,从而判断是否正确收敛。
  • 如何调整学习曲率\(\alpha\)?
    一般情况下学习曲率是个固定不变的值,但如果你希望随机梯度下降能够收敛至全局最小值(而不是在附近震荡),那么我们可以在快要收敛的时候降低梯度下降的步长,也就是说减小学习曲率\(\alpha\)的值,这样就能使得算法能够收敛到全局最小值。那么也就是说\(\alpha\)的值要随着迭代次数的增加而减小,因此我们可以使得:\(\alpha = \frac{const1}{iterationNumber + const2}\)来达到这种效果。
  • 在线学习(online learning)
    所谓的在线学习指的是在训练时,采用的样本数据集并不是固定存储好的,而是采集于实时的用户流或者由用户产生的数据流。这样做的一个好处是不用花费额外空间存储数据,数据用完就丢。而且还能根据用户的数据实时动态调整网站策略。一个典型的应用就是购物网站的搜索结果,可以根据用户的点击情况实时调整搜索结果。这种在线学习方法适用于那些有大量访问用户的网站,如果你的网站很小,用户量不大,那么还是建议把这些用户数据存储下来再去训练。

    Map Reduce和数据并行化
    在进行大规模机器学习时我们可以采用map-reduce的技术加快训练速度,map reduce的基本思想是把大数据分割成小数据集到不同的机器上进行计算,算好后再把结果返回给中心机器进行整合。具体地,假如我们有如下的批量梯度下降需要计算:
    $$\theta_{j} := \theta_{j} – \alpha\frac{1}{400}\sum_{i=1}^{400}\left ( h_{\theta}\left ( x^{(i)}\right )- y ^{(i)}\right ) x_{j}^{(i)}$$
    这里为了方便举例,我们假设\(m=400\),而实际上m会很大,比如\(m=400,000,000\)。那这个计算任务如何分解呢?我们把这个任务分为四个小任务分别丢到四台机器上去计算:

  • 机器1:使用数据集:\((x^{(1)},y^{(1)}),…,(x^{(100)},y^{(100)})\),计算:\(temp_{j}^{(1)} = \sum_{i=1}^{100}(h_{\theta}(x^{(i)}-y^{(i)})x_{j}^{(i)}\)
  • 机器2:使用数据集:\((x^{(101)},y^{(101)}),…,(x^{(200)},y^{(200)})\),计算:\(temp_{j}^{(2)} = \sum_{i=101}^{200}(h_{\theta}(x^{(i)}-y^{(i)})x_{j}^{(i)}\)
  • 机器3:使用数据集:\((x^{(201)},y^{(201)}),…,(x^{(300)},y^{(300)})\),计算:\(temp_{j}^{(3)} = \sum_{i=201}^{300}(h_{\theta}(x^{(i)}-y^{(i)})x_{j}^{(i)}\)
  • 机器4:使用数据集:\((x^{(301)},y^{(301)}),…,(x^{(400)},y^{(400)})\),计算:\(temp_{j}^{(4)} = \sum_{i=301}^{400}(h_{\theta}(x^{(i)}-y^{(i)})x_{j}^{(i)}\)
  • 全部算好之后再进行整合:
    $$\theta_{j}:= \theta_{j} – \alpha \frac{1}{400}(temp_{j}^{(1)}+temp_{j}^{(2)}+temp_{j}^{(3)}+temp_{j}^{(4)}) ,\ (j=0,1,…n)$$
    我们不仅可以在不同机器之间使用map reduce,也可以在同一台机器的不同CPU核之间使用,原理是一样的。值得一提的是,某些线性代数的函数库会自动进行多核并行计算,如果你采用了这些函数库,并且你有一个很好的向量化的实现,那么你只要按照标准的向量化的方式实现机器学习算法就行了,并不需要额外考虑多核并行的问题。

    大规模机器学习》上有1条评论

    1. Pingback引用通告: 深度学习-调参和优化(二) | Eric Fan

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注