机器学习笔记 Week10 大规模机器学习

学习笔记(Machine Learning) Week10

全部笔记PDF版:http://vdisk.weibo.com/s/J4rRX/1373287206

Week10 由两部分内容构成:

  1. 大规模机器学习
  2. 应用示例:图像文字识别

1大规模机器学习(Large Scale Machine Learning)

1.1大型数据集的学习

如果我们有一个低偏倚的模型,增加数据集的规模可以帮助你获得更好的结果。

我们应该怎样应对一个有100万条记录的训练集?

以线性回归模型为例,每一次梯度下降迭代,我们都需要计算训练集的误差的平方和,如果我们的学习算法需要有20次迭代,这便已经是非常大的计算代价。

首先应该做的事是去检查一个这么大规模的训练集是否真的必要,也许我们只用1000个训练集也能获得较好的效果,我们可以绘制学习曲线来帮助判断。

QQ截图20130707122133

1.2随机梯度下降法(Stochastic Gradient Descent)

如果我们一定需要一个大规模的训练集,我们可以尝试使用随机梯度下降法来代替批量梯度下降法。

在随机梯度下降法中,我们定义代价函数为一个单一训练实例的代价:

111

随机梯度下降算法为:

首先对训练集随机“洗牌”,然后:

QQ截图20130707122750

随机梯度下降算法在每一次计算之后便更新参数Θ,而不需要首先将所有的训练集求和,在梯度下降算法还没有完成一次迭代时,随机梯度下降算法便已经走出了很远。但是这样的算法存在的问题是,不是每一步都是朝着“正确”的方向迈出的。因此算法虽然会逐渐走向全局最小值的位置,但是可能无法站到那个最小值的那一点,而是在最小值点附近徘徊。

QQ截图20130707142745

1.3微型批量梯度下降(Mini-Batch Gradient Descent)

微型批量梯度下降算法是介于批量梯度下降算法和随机梯度下降算法之间的算法,每计算常数b次训练实例,便更新一次参数Θ。

QQ截图20130707123915

通常我们会令b在2-100之间。这样做的好处在于,我们可以用向量化的方式来循环b个训练实例,如果我们用的线性代数函数库比较好,能够支持平行处理,那么算法的总体表现将不受影响(与随机梯度下降相同)。

1.4随机梯度下降收敛(Stochastic Descent Convergence)

现在我们介绍随机梯度下降算法的调试,以及学习率α的选取。

在批量梯度下降中,我们可以令代价函数J为迭代次数的函数,绘制图表,根据图表来判断梯度下降是否收敛。但是,在大规模的训练集的情况下,这是不现实的,因为计算代价太大了。

在随机梯度下降中,我们在每一次更新Θ之前都计算一次代价,然后每X次迭代后,求出这X次对训练实例计算代价的平均值,然后绘制这些平均值与X次迭代的次数之间的函数图表。

QQ截图20130707140843

当我们绘制这样的图表时,可能会得到一个颠簸不平但是不会明显减少的函数图像(如上面左下图中蓝线所示)。我们可以增加X来使得函数更加平缓,也许便能看出下降的趋势了(如上面左下图中红线所示);或者可能函数图表仍然是颠簸不平且不下降的(如洋红色线所示),那么我们的模型本身可能存在一些错误。

如果我们得到的曲线如上面右下方所示,不断地上升,那么我们可能会需要选择一个较小的学习率α。

我们也可以令学习率随着迭代次数的增加而减小,例如令:

iter1

随着我们不断地靠近全局最小值,通过减小学习率,我们迫使算法收敛而非在最小值附近徘徊。

但是通常我们不需要这样做便能有非常好的效果了,对α进行调整所耗费的计算通常不值得。

QQ截图20130707142753

1.5在线学习(Online Learning)

在线学习算法指的是对数据流而非离线的静态数据集的学习。许多在线网站都有持续不断的用户流,对于每一个用户,网站希望能在不将数据存储到数据库中便顺利地进行算法学习。

假使我们正在经营一家物流公司,每当一个用户询问从地点A至地点B的快递费用时,我们给用户一个报价,该用户可能选择接受(y=1)或不接受(y=0)。

现在,我们希望构建一个模型,来预测用户接受报价使用我们的物流服务的可能性。因此报价是我们的一个特征,其他特征为距离,起始地点,目标地点以及特定的用户数据。模型的输出是p(y=1)。

在线学习的算法与随机梯度下降算法有些类似,我们对单一的实例进行学习,而非对一个提前定义的训练集进行循环。

QQ截图20130707144101

一旦对一个数据的学习完成了,我们便可以丢弃该数据,不需要再存储它了。这种方式的好处在于,我们的算法可以很好的适应用户的倾向性,算法可以针对用户的当前行为不断地更新模型以适应该用户。

每次交互事件并不只产生一个数据集,例如,我们一次给用户提供3个物流选项,用户选择第2项,我们实际上可以获得3个新的训练实例,因而我们的算法可以一次从3个实例中学习并更新模型。

1.6映射化简和数据并行(Map Reduce and Data Parallelism)

映射化简和数据并行对于大规模机器学习问题而言是非常重要的概念。之前提到,如果我们用批量梯度下降算法来求解大规模数据集的最优解,我们需要对整个训练集进行循环,计算偏导数和代价,再求和,计算代价非常大。如果我们能够将我们的数据集分配给不多台计算机,让每一台计算机处理数据集的一个子集,然后我们将计所的结果汇总在求和。这样的方法叫做映射简化。

具体而言,如果任何学习算法能够表达为,对训练集的函数的求和,那么便能将这个任务分配给多台太计算机(或者同一台计算机的不同CPU核心),以达到加速处理的目的。

例如,我们有400个训练实例,我们可以将批量梯度下降的求和任务分配给4台计算机进行处理:

QQ截图20130707145513

很多高级的线性代数函数库已经能够利用多核CPU的多个核心来平行地处理矩阵运算,这也是算法的向量化实现如此重要的缘故(比调用循环快)。

课程地址:https://class.coursera.org/ml-003/class/index

Leave a Reply

Your email address will not be published. Required fields are marked *