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

学习大数据集

获取高性能的机器学习系统途径是采用低偏差的学习算法，并用大数据进行训练。从下面的图中可以明确，只要使用大数据对算法进行训练，它的效果似乎会更好：

从这样的结果可以得出，在机器学习中，决定因素往往不是最好的算法而是谁的训练数据最多。

但是大数据集有它自己的特殊的问题，即计算问题。假设有一亿个训练样本，想要训练一个线性回归模型或一个逻辑回归模型，然后用梯度下降进行更新：$\theta_j=\theta_j-\alpha\frac1m\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)}$θj​=θj​−αm1​∑i=1m​(hθ​(x(i))−y(i))xj(i)​，当 $m$m 等于一亿时，计算的代价太大了。

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

---

随机梯度下降

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

假设函数与代价函数如下：
$h_\theta(x)=\sum_{j=0}^n\theta_jx_j \\ J_{train}(\theta)=\frac1{2m}\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)^2$hθ​(x)=j=0∑n​θj​xj​Jtrain​(θ)=2m1​i=1∑m​(hθ​(x(i))−y(i))2

梯度下降的公式如下：
$\theta_j=\theta_j-\alpha\frac1m\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)}$θj​=θj​−αm1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​

那么当训练集很大时，用这样的梯度下降的更新，将会非常慢，花费的代价太大，下面来看一下更高效的算法，可以更好地处理大型数据集。

定义代价函数为一个单一训练实例的代价：
$cost\left(\theta,(x^{(i)},y^{(i)})\right)=\frac12\left(h_\theta(x^{(i)})-y^{(i)}\right)^2 \\ J_{train}(\theta)=\frac1{m}\sum_{i=1}^mcost\left(\theta,(x^{(i)},y^{(i)})\right)$cost(θ,(x(i),y(i)))=21​(hθ​(x(i))−y(i))2Jtrain​(θ)=m1​i=1∑m​cost(θ,(x(i),y(i)))

随机梯度下降算法为：首先对训练集随机“洗牌”，然后：
$\theta_j=\theta_j-\alpha\frac1m\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)}$θj​=θj​−αm1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​

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

总的来看，参数是朝着全局最小化的方向移动的，整个过程还是以随机迂回的路径朝着全局最小值前进，相比于普通梯度下降（红色的曲线），随机梯度下降的收敛形式是不同的，它所做的是连续不断在某个区域中朝着全局最小值方向徘徊。

---

Mini-Batch 梯度下降

总结一下：

• 普通梯度下降：每次迭代都要用到所有的m个样本
• 随机梯度下降：每次迭代只需用到一个样本
• Mini-Batch 梯度下降：介于上述两者之间，每次迭代会使用 $b$b 个样本（$b$b 是称为 Mini-Batch 大小的参数，通常 $b$b 的范围2-100）

例如：假设 $b=10$b=10，得到10个样本为：$(x^{(i)},y^{(i)}),\dots,(x^{(i+9)},y^{(i+9)})$(x(i),y(i)),…,(x(i+9),y(i+9))，然后进行梯度更新：

Mini-Batch 梯度下降算法的缺点之一是要计算参数 $b$b 的大小时，可能需要花费些时间，不过如果有优秀的向量化方法，有时它将比随机梯度下降运行的更快。

---

随机梯度下降收敛

对于随机梯度下降，为了检查算法是否已经收敛，可以进行以下的工作：

• 沿用之前定义的代价函数：
  $cost\left(\theta,(x^{(i)},y^{(i)})\right)=\frac12\left(h_\theta(x^{(i)})-y^{(i)}\right)^2$cost(θ,(x(i),y(i)))=21​(hθ​(x(i))−y(i))2

• 当随机梯度下降法进行学习时，在使用某个样本 $(x^{(i)},y^{(i)})$(x(i),y(i)) 更新参数之前，可以计算出这个训练样本对应的假设表现有多好（即计算出代价函数）

• 为了检查随机梯度下降是否收敛，要做的是每1000次迭代，就画出前一步中所计算出的代价函数，把这前1000个样本的代价函数的平均值画出来，通过观察所画的图，就能检查出随机梯度下降法是否在收敛。

绘制这些平均值与 $x$x 次迭代的次数之间的函数图表：

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

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

随着不断地靠近全局最小值，通过减小学习率，迫使算法收敛而非在最小值附近徘徊。 但是通常我们不需要这样做便能有非常好的效果了，对$\alpha$α 进行调整所耗费的计算通常不值得：

---

在线学习

在线学习机制让我们可以模型化问题

假定你有一个提供运输服务的公司，用户们来向你询问把包裹从A地运到B地的服务，同时假定你有一个网站，让用户们可多次登陆，然后他们告诉你，他们想从哪里寄出包裹，以及包裹要寄到哪里去，也就是出发地与目的地，然后你的网站开出运输包裹的的服务价格。

然后根据你开给用户的这个价格，用户有时会接受这个运输服务，那么这就是个正样本（y=1），有时他们会走掉，然后他们拒绝购买你的运输服务（y=0），所以，让我们假定我们想要一个学习算法来帮助我们，优化我们想给用户开出的价格。

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

在线学习的算法与随机梯度下降算法有些类似，对单一的实例进行学习，而非对一个提前定义的训练集进行循环。$\theta_j=\theta_j-\alpha\frac1m\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)}$θj​=θj​−αm1​∑i=1m​(hθ​(x(i))−y(i))xj(i)​

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

另一个使用在线学习的例子：

一个产品搜索的应用，用一种学习算法来学习，如何反馈给用户好的搜索列表。假设有一个卖手机的店铺，有一个用户界面可以让用户登录你的网站并键入一个搜索条目，例如 “安卓手机、1080p摄像头”，假定店铺中有100种手机，由于网站设计，当用户键入一个搜索命令，会找出10部合适的手机供用户选择。这里想要用一个学习算法帮助我们找到在这100部手机中哪10部手机是应该反馈给用户的。

解决思路：

• 对于每个手机以及给定的用户搜索命令，可以构建特征向量x，这个特征向量可能会表示手机的各种特征，可能是：用户的搜索与这部电话的类似程度有多高、用户搜索命令中有多少词可以与这部手机的名字相配等等
• 估计用户点击某一手机链接的概率，所以将 $y=1$y=1 定义为用户点击了手机的链接，而 $y=0$y=0 是指用户没有点击链接，然后根据特征 $x$x 来预测用户点击特定链接的概率 $p(y=1|x,\theta)$p(y=1∣x,θ)
• 估计任意一个手机的点击率，可以利用这个来给用户展示10个他们最有可能点击的手机

这就是在线学习机制，所使用的这个算法与随机梯度下降算法非常类似，唯一的区别的是，不会使用一个固定的数据集，做的是获取一个用户样本，从那个样本中学习，然后丢弃那个样本并继续下去，而且如果对某一种应用有一个连续的数据流，这样的算法可能会非常值得考虑。

当然，在线学习的一个优点就是，如果有一个变化的用户群，又或者在尝试预测的事情，在缓慢变化，就像用户的品味在缓慢变化，这个在线学习算法，可以慢慢地调试所学习到的假设，将其调节更新到最新的用户行为。

---

减少映射与数据并行

MapReduce的思想：

对于普通梯度下降法来说，假定有训练集如下：
$\begin{bmatrix} (x^{(1)},y^{(1)}) \\ \vdots \\ (x^{(m)},y^{(m)}) \end{bmatrix}$⎣⎢⎡​(x(1),y(1))⋮(x(m),y(m))​⎦⎥⎤​

根据MapReduce的思想，把训练集分割成不同的子集，假设m=400（这里为了方便介绍，实际处理大规模数据m应该是4亿的数量集），有4台机器可以处理数据。

第一台机器用前四分之一的训练集：
$(x^{(1)},y^{(1)}),\dots,(x^{(100)},y^{(100)}) \\ temp_j^{(1)}=\sum_{i=1}^{100}\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)}$(x(1),y(1)),…,(x(100),y(100))tempj(1)​=i=1∑100​(hθ​(x(i))−y(i))xj(i)​

依次类推：
$(x^{(101)},y^{(101)}),\dots,(x^{(200)},y^{(200)}) \\ temp_j^{(2)}=\sum_{i=101}^{200}\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)} \\ (x^{(201)},y^{(201)}),\dots,(x^{(300)},y^{(300)}) \\ temp_j^{(3)}=\sum_{i=201}^{300}\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)} \\ (x^{(301)},y^{(301)}),\dots,(x^{(400)},y^{(400)}) \\ temp_j^{(4)}=\sum_{i=301}^{400}\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(i)}$(x(101),y(101)),…,(x(200),y(200))tempj(2)​=i=101∑200​(hθ​(x(i))−y(i))xj(i)​(x(201),y(201)),…,(x(300),y(300))tempj(3)​=i=201∑300​(hθ​(x(i))−y(i))xj(i)​(x(301),y(301)),…,(x(400),y(400))tempj(4)​=i=301∑400​(hθ​(x(i))−y(i))xj(i)​

现在每个机器做的是四分之一的工作，使得它们能将原来的运行速度提高四倍，它们完成各自的 $temp$temp 计算后，然后把 $temp$temp 发给一个中心服务器去整合结果，最后更新参数：
$\theta_j=\theta_j-\alpha\frac1{400}(temp_j^{(1)}+temp_j^{(2)}+temp_j^{(3)}+temp_j^{(4)})$θj​=θj​−α4001​(tempj(1)​+tempj(2)​+tempj(3)​+tempj(4)​)

如果想把MapReduce的思想应用在某种学习算法上，通过多台电脑并行计算来实现加速，思考：学习算法是否能表示成对训练集的一种求和？

实际上很多学习算法都可以表示成对训练集函数求和，而在大数据集上运行，所消耗的计算量就在于需要对非常大的训练集进行求和，所以只要学习算法可以表示为对训练集的求和，那么就可以用 MapReduce 将学习算法的使用范围扩展到非常大的数据集。

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