大规模机器学习

如果我们有一个低方差的模型，增加数据集的规模可以帮助你获得更好的结果。我们应该怎样应对一个有 100 万条记录的训练集？以 Linear Regression 为例，如果每一次 gradient descent 都要计算训练集的误差的平方和，即便需要 20 次迭代，这也已经是一个非常大的计算代价了。

# 1. 随机梯度下降法

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

在随机梯度下降（Stochastic Gradient Descent）中，我们定义 cost function 为单一训练实例的代价：

Stochastic gradient descent

Randomly shuffle(reorder) training examples.
Repeat { for { (for every ) } }

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

# 2. Mini-batch Gradient Descent

对比一下三种 gradient descent：

Batch gradient descent: Use all examples in each iteration.
Stochastic gradient descent: Use 1 example in each iteration.
Mini-batch gradient descent: Use examples in each iteration.

Mini-batch Gradient Descent

Say .

Repeat { for { (for every ) } }

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

# 3. 随机梯度下降的收敛

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

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

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

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

我们也可以令 learning rate 随着迭代次数的增加而减小，例如令：

但这样会又引入了两个额外的超参数需要去调：const1 和 const2。

# 4. Online Learning

本节讨论一种新的大规模的机器学习机制，叫做在线学习（Online Learning）机制。

如果你有一个由连续的用户流引发的连续的数据流，进入你的网站，你能做的是使用一个在线学习机制，从数据流中学习用户的偏好，然后使用这些信息来优化一些关于网站的决策。

假定你有一个提供运输服务的公司，用户们来向你询问把包裹从 A 地运到 B 地的服务，同时假定你有一个网站，让用户们可多次登陆，然后他们告诉你，他们想从哪里寄出包裹，以及包裹要寄到哪里去，也就是出发地与目的地，然后你的网站开出运输包裹的的服务价格。比如，我会收取 $50 来运输你的包裹，我会收取 $20 之类的，然后根据你开给用户的这个价格，用户有时会接受这个运输服务，那么这就是个正样本，有时他们会走掉，然后他们拒绝购买你的运输服务，所以，让我们假定我们想要一个学习算法来帮助我们，优化我们想给用户开出的价格。

在线学习算法指的是对数据流而非离线的静态数据集的学习。假使我们正在经营一家物流公司，每当一个用户询问从地点 A 至地点 B 的快递费用时，我们给用户一个报价，该用户可能选择接受（y=1）或不接受（y=0）。现在，我们希望构建一个模型，来预测用户接受报价使用我们的物流服务的可能性。因此“报价”是我们的一个特征，其他特征有距离、起始地点、目标地点以及特定的用户数据。模型的输出是：。

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

对于上面的例子，feature 蕴含了用户的一些属性，比如 origin / destination 等，我们希望通过学习来优化价格：

Online Learning Algorithm

Repeat forever { Get corresponding to user. Update using : }