大规模机器学习

现在的机器学习比以前运行的更好，是因为现在我们有着极其庞大的数据集来训练我们的算法。

学习大数据集

我们已经知道一种获得高性能机器学习模型的途径是采用低偏差的学习算法并用大数据进行训练。

这是一个对易混淆单词分类的例子，只要用大量数据进行训练，效果就看起来非常好。
但是大数据机器学习有其问题——计算问题。

当m是一亿的时候，我们要对一亿项进行求和来演算单步梯度下降。
那么为什么m不可以是1000呢？因此，我们在进行实际开发软件之前，要检查m是1000的效果是不是和m=1000000000的效果一样。
我们通过之前介绍的绘制学习曲线可以来解决这个问题。

左边的模型是由于高偏差，需要增加更多的训练集；而右边的模型是由于高方差，即使增加m，也不会有多大的提升，因此在对右边的模型改进时应该通过增加特征的方法而不是增加训练集。

随机梯度下降

我们来回顾一下线性回归的内容：

其中$h_{\theta}(x)$是假设函数，$J_{train}(\theta)$是代价函数。我们重复Repeat中的内容对$\theta_j$进行更新。
当m=300000000时，更新时需要对m项进行求和，计算量是非常大的（这种梯度下降又被称为Batch gradient descent）。

随机梯度下降在运行时不需要考虑所有的训练样本，只需要考虑一个训练样本。

两边的$J_{train}$是一样的。
随机梯度下降的过程：
第一步：随机打乱所有数据（为了让随机梯度下降收敛的更快）
第二步：

对每个参数$\theta_j$进行修正，通过每一个随机打乱后的样本。重复这个过程直到收敛。
外层循环Repeat通常一次就够了，最多十次，所以只要在1-10之间就可以了。

随机梯度下降和批量梯度下降收敛的形式是不同的。图中品红色是随机梯度下降，红色是批量梯度下降。随机梯度下降可能会使得参数$\theta_j$往偏离全局最小值的方向走，但是最终还是会走回全局最小值的区域，并且在区域内不断的徘徊，不会完全收敛。所以他的曲线是弯弯折折的，不是直接达到全局最小值。

Mini-batch梯度下降

有时甚至比随机梯度下降要快。
Mini-batch梯度下降在一次迭代中使用b个训练样本（批量使用m个，随机使用1个）。

通过合适的向量化方式，可以部分使用好的数值代数库，然后对b个样本并行进行梯度计算。这样它可以比随机梯度下降运行的更快。

随机梯度下降收敛

如何确定随机梯度下降已经收敛到合适的位置？
怎样调整其中的学习速率$\alpha$？

回顾批量梯度下降，我们确认已经收敛的方法是绘制优化代价函数。

当m很大的时候，我们不会期望每次停下程序来计算$J_{train}(\theta)$的值，因为每次计算需要对m项进行求和。

对于随机梯度下降，我们可以这样做：

在运行梯度下降时，在更新$\theta$的值之前，我们计算cost。（更新之前计算cost的原因是：如果更新之后再计算，那么cost的值就会变得很小）。
最后为了检查是否收敛，我们要做的是，每1000次迭代，我们就绘制所计算出的前1000个cost函数值的平均值画出来。

下面是几种绘制代价曲线的情况：

使用更小的$\alpha$，梯度下降收敛的速度变慢，但是或许可以收敛到一个更好的位置。（红色线）原因是随机梯度下降不是直接收敛到最小值，而是在一个范围内振荡，直到逐渐接近全局最小值。

将1000提高到5000，可以得到更平滑的线（红色线）。缺点是获得梯度下降是否收敛的信息会有延迟。

看起来蓝线似乎没有下降，但是如果增加1000到5000，你可能得到红色线，其实是有下降的，只是求均值的样本太少了，所以包含了太多的噪声，导致看不出来函数实际上是趋向于减少的。
但是如果即使提高了样本数量，得到了品红色曲线，曲线还是很平坦。这代表算法不知由于什么原因没有进行学习。这时就需要调整学习速率或调整特征或者调整算法的其他东西。

我们会发现蓝线在上升，这是算法发散的信号，这时需要做得是使用更小的学习速率$\alpha$。

关于学习速率
如果想让算法更好的收敛到全局最小值，我们可以逐渐的减小$\alpha$。
使用这种方法，最后在全局最小值附近的振荡幅度变小，更接近于全局最小值。

在线学习

一种新的大规模机器学习机制。
适用于连续数据流，如网站产生的数据。
效果：适应变化的用户偏好。
下面是一个例子：快递价格

不再使用带上标的样本，而是使用(x,y)，用一个样本丢弃一个。

下面是另一个例子：反馈商品搜索列表

Map-reduce和数据并行

很多机器学习算法过于庞大不能单机运行。
Map-reduce的思想可以让你应对随机梯度下降解决不了的规模更大的问题。
[Jeffrey Dean and Sanjay Ghemawat]

假设400个样本，根据Map-reduce思想，我们将样本划分为不同的子集。
比如图中我们分成四个子集，通过四台机器分别计算求和temp。最后将这四个temp发送到中心服务器，中心服务器将会整合这些结果，再更新参数$\theta_j$。

Map-reduce示意图：

只要学习算法可以表示成一系列的求和或者表示成在训练集上对函数的求和形式，就可以使用Map-reduce技巧来并行化学习算法。

另：多核计算机也可以实现Map-reduce。
另：有些线性代数库已经实现了并行，所以只需要较好的向量化就可以实现让库为你进行并行计算。
另：有Map-reduce的开源实现Hadoop