大规模机器学习

我们基本讨论了应用中的机器学习算法，但是生产中要跟大数据结合，对于大数据我们如何处理呢？

前面我们讨论过，在机器学习中并不是谁有最好的算法谁就能赢，而是谁拥有更多的数据谁才会赢。我们在前面的博客
称之为”算法虽好，数据决胜！”
所以，如果我们能有办法获得大量数据的话，我们就希望能够利用这样大量的数据来训练我们的模型。

不过，当数据集变得很大的时候就会遇到计算量的问题。
比如，我们的训练集由1亿个样本组成，但实际上现在非常多的企业都有这样规模的数据，如BAT。一个小型的商业路由
器公司，都可以有数以亿计的设备数据；而如果是一家做在线广告的公司，它的每一个流量都能被设计成一个样本，所
以构建一个在线广告系统的CTR预估模型，其训练样本达到一亿其实并不困难。

假设我们想要实用这一亿个样本来训练一个线性回归模型，或者也可能是一个逻辑回归模型。我们的梯度下降更新规则如
上图。式子中的m就是1亿，因为我们的训练集的规模就是一亿，所以为了计算这些导数和单步梯度下降，我们需要对这
些一亿个数值进行求和。所以，迭代一次，我们就需要至少一亿次的计算，这个代价是非常巨大的。

如何优化？

在实际应用中，我们常常做的就是从大规模数据集中抽取一小部分数据比如几万个样本来尝试机器学习，画学习曲线，如
上图，通过判断bias或者variance问题对简单模型进行判断以及确定后续优化步骤。

为什么用随机梯度下降？

对于很多机器学习算法， 包括线性回归、逻辑回归、神经网络等等。算法的实现都是通过得出某个代价函数或者某个最
优化的目标来实现的。然后使用梯度下降这样的方法来求得代价函数的最小值。  当我们的训练集较大时，梯度下降算法
则显得计算量太大。随机梯度下降-----可以将算法运用到较大的训练集的情况中。

假设，我们要使用梯度下降算法来训练一个线性回归模型。  代价函数在特征只有二维的情况下，如上图，大概是碗型
的平面。梯度下降算法就是，不断地去迭代，每次我们都朝着能将代价函数变小的方向改变我们的参数θ。

如上图，当m很大的时候，红框中微分项的计算量就会非常大，因为需要对所有m个训练样本进行求和，假如m的值是
1亿。这种一次迭代更新就需要对全体样本进行求和的算法，我们称之为”批量梯度下降”---Batch gradient descent，这
里的”批量”指的就是我们每次迭代更新都需要考虑所有的训练样本。如果数据集再大一些，可能我们的内存装不下这些
数据。

随机梯度下降

上图左侧是批量梯度下降，右侧是随机梯度下降。
比较，  

把随机梯度下降的算法写成上图右侧公式。

相较于批量梯度下降，随机梯度下降不需要对所有m个训练样本求和来得到梯度项，而是只需要单个训练样本求出这
个梯度项。所以，现在不用遍历完一次完整的训练集才进行一次迭代更新，我们现在只需要一次关注一个训练样本，
基于一个样本，我们就已经开始一点点把参数朝着全局最优解的方向进行修改了。

1、第一步是打乱数据；
2、第二步是算法的关键，它的逻辑是，每看到一个样本，就使用它来对模型参数进行更新。

算法是如何更新参数θ的呢？
当使用批量梯度下降的时候，需要考虑所有的训练样本，批量梯度下降的收敛过程会倾向于一条近似的直线，一直找
到全局最小值。
在随机梯度下降中，每一次迭代都会很快，因为我们不需要对所有的训练样本进行求和，每次迭代只需要保证对一个
训练样本拟合好就行了。
所以，如果从一个点开始进行随机梯度下降的话，第一次迭代，可能会让参数朝着这个方向移动，第二次迭代，我们
朝一个错误的方向行进了一点，第三次迭代我们又尽力让参数修改到拟合第三组训练样本，又向正确的方向移动了一
点，然后我们再考虑第四个、第五个等等，一直做同样的事情。
在随机梯度下降的过程中，一般而言，参数是朝着全局最小值点的方向被更新的，但并不是每次迭代都是如此，所以
它的迭代看上去会有一些随机性，整个收敛的过程有一些迂回。
而实际上，随机梯度下降和批量梯度下降，最终收敛的点一般都不会一样，因为随机梯度下降即使在全局最小值点附
近，它仍然是看到一个样本就更新一次，不会像批量梯度下降那样考虑整体的情况，所以它会一直在全局最小值点附
近打转，而不会直接逼近全局最小值点，并且停留在那里。
只要参数最终落在全局最小值点的比较小的区域内，我们一般也会得到一个挺不错的模型。所以，通常我们使用随机
梯度下降，也能得到很接近全局最小值的参数。

在随机梯度下降中，我们这里有一个外层的循环，如上图。它决定了我们内层循环的执行次数，实际上就是我们需要
遍历整个训练集几次。  那么，外层循环究竟应该执行多少次呢？因为这里，我们不会计算当前的损失函数 J，因为计
算损失函数 J也会有计算量上的问题，所以，相较于之前我们检查两次迭代间的J的差值，对于应用于大规模数据的随
机梯度下降算法，我们一般是限定外层循环的次数。如果数据量特别大，比如上亿了，可能遍历一次训练集就可以了，
而一般情况下可能遍历10次以内就差不多了。另外，这个外层循环，在机器学习领域也有一个特有的英文名字，叫
”epoch”，遍历一次叫一个epoch，两次叫两个epoch。因为在深度学习领域，对数据量有非常大的需求，所以做深度学
习的人更经常使用这个术语。

小批量梯度下降

前面我们讨论了随机梯度下降，它相较于最开始我们讨论的批量梯度下降在运行速度上要快非常多。现在，我们要讨论
结合这两种思想的另一种梯度下降，叫做小批量梯度下降，英文称为mini-batch gradient descent，这种算法有时候甚至
比随机梯度下降还要快一些。

在批量梯度下降中，我们会使用整个训练集中的所有m个样本来进行每一次的迭代；而随机梯度下降，我们每一次迭代
只使用1个样本；

小批量梯度下降，则介于两者之间。具体而言，小批量梯度下降算法在每一次参数迭代时，使用b个样本。而这里的b就
被称为小批量的大小。所以，它的想法就是，我们每次迭代，既不是用全部的样本，也不仅仅使用一个样本，而是使用
b个样本。 这其实有点像批量梯度下降，只是我们每次使用的样本数要远小于整个训练集。

b的典型的大小是10，也就是每次迭代模型的参数时使用10个样本。不过，一般而言，2~100都是挺常见的小批量大小。

那么，我们把小批量梯度下降的这种想法正式地写一下，那就是，我们从训练集中拿b个样本，比如10个

表达成上述公式。

为了简化下标，假设设置了小批量的大小是10，整个训练集的样本数m是1000。那么，我们要做的就是使用这样的for循
环，每十个一组，所以我们的i的取值下标就是1，11，21，31等等。然后我们就使用这10个样本来更新模型中的所有参
数θj。
因此，我们每使用10个样本就可以对模型的参数更新一次。

小批量梯度下降和随机梯度下降有什么不同呢？
小批量梯度下降只有在具备良好向量化实现的基础上，才会在性能上要比随机梯度下降要好。如果我们有一个良好实现
的向量化的梯度下降，那么这个小批量样本的计算可以部分地实现并行计算。也就是说，如果我们有一个很好的向量化
的实现以后，数值计算的库有时候能够帮助我们采用并行的方式来计算这里的微分项。而如果我们使用随机梯度下降，
每次只使用一个样本的话，我们就没有什么余地来应用并行计算。

小批量梯度下降的一个劣势是，我们在这里引入了一个新的超参，也就是小批量的大小 b。我们需要花时间来决定这个
b的取值应该是怎样的。这个超参b，对整个训练而言影响并不会很大，b=10一般都会运行得不错，当然，b=2~100的话
其实也都没什么问题。

随机梯度下降的收敛

现在我们已经讨论完了随机梯度下降。不过当我们运行随机梯度下降算法的时候，我们如何确保它是否真的是正确地运
行呢？还有同样重要的是，我们应该如何调整随机梯度下降中的学习率α呢？

在批量下降算法中，我们确定它正确收敛的标准方法是画出最优化的代价函数关于迭代次数的变化，保证代价函数的值
在每一次的迭代中都是减小的。当训练集比较小的时候，很容易验证。当我们的训练集特别大的时候，比如拥有 1 亿个
训练样本的时候，我们不希望总是定时地暂停算法来计算一下整体的代价函数的值。而随机梯度下降的最重要的不同点
就是，每次只根据一个样本来更新模型的参数，而不需要每次扫描整个超大的训练集。所以，对于这种超大规模的训练
集，我们既然使用了随机梯度下降，那么就不可能再使用需要扫描整个训练集才能得到的数值。

检查随机梯度算法是否收敛

在随机梯度下降算法中，在我们使用一个样本对θ进行更新之前，我们可以算出这个样本对应的cost函数的值，表达了在
使用了前i-1个样本训练出来的模型对于我们这个第i个样本的拟合能力。
为了检查梯度下降的收敛性，我们要做的是每1000次迭代，我们可以画出最近1000个样本的cost变化。这样我们就可以
看出算法在最近1000个样本上的表现是怎样的。所以，我们不需要耗费时间和算力时不时地去计算整个训练集上的代价
函数，随机梯度下降的这种收敛校验显然在大数据集上更加高效，通过观察每1000次迭代的样本代价变化，就可以检查
出随机梯度下降是否在收敛。
如下图，

增大批量的数目，比如从计算1000个样本的损失函数平均值，到计算5000个，会使得损失函数曲线更平滑。

通过上图，我们了解到在判断随机梯度下降是否收敛时可能遇到的各种情况，以及相应的解决方案：如果曲线看起来
噪声太大，或者总是上下振动，那么可以尝试增加采样间隔，这样就可以使得曲线变得更加平滑，更加便于观察趋势；
而如果我们发现损失函数在不断变大，那就换一个小一点的学习率α。

学习率α

我们已经知道，当运行随机梯度下降的时候，算法会从某个点开始，然后曲折地去逼近最小值，但它并不会真的收敛
到最小值点，而是在最小值附近徘徊。因此，最终我们得到的参数实际上只是接近全局最小值，而不是真正的全局最
小值。

在大多数随机梯度下降算法的典型实现中，学习率α都是保持不变的。如果想让随机梯度下降确实收敛到全局最小值，
我们可以随着时间的变化减小学习率α的值。那么，一种典型的设置α的方法是，让α等于某个常数1，除以迭代次数加
上某个常数2。这里的迭代次数指的是运行随机梯度下降的迭代次数，其实也就是我们扫描的训练样本的数量。而常数
1和常数2则是两个额外需要我们稍微选择的参数。这种方法的令很多人诟病的一点其实也就是对于常数1和常数2的挑
选上，这使得在应用算法时，需要调整的参数又变多了，而这对于应用者而言并不是一件好事。  不过，如果我们设置
的这两个常数合理的话，我们可能得到的迭代路径可能就会变好。

我们的算法会在最小值附近振荡，但当它越来越靠近最小值的时候，由于我们减小了学习率，因此这个振荡也会越来
越小，直到落到几乎靠近全局最小的地方。随着算法的运行，迭代次数会越来越大，那么我们的学习率也就会越来越
小，所以我们每次迭代的时候对参数θ的修改就会越来越小，直到最终收敛到全局最小值。
所以，随着迭代的进行，不断减小α，最终会使我们得到一个更好一些的模型。不过由于选择这两个常数本身也需要很
多工作量，而且我们可能一般对接近全局最小值点的解已经足够满意了，因此在实践中，我们在随机梯度下降种，其
实不太会采用这种逐渐减小α的方法。

在线学习

在线学习机制，让我们可以在连续的数据流上训练模型，而不是事前就得到所有的训练数据离线地训练好模型，然后在
线地进行预测。这种方式可以使得线上的数据更快地反馈到线上应用，而不必等待收集好数据以后离线训练完模型以后
再进行应用部署。
在当下，许多大型互联网公司都在使用各种各样的在线学习算法从海量的实时在线数据来对模型进行训练。比如百度，
它的搜索算法早在多年前就已经开始使用在线学习来对排序模型进行训练了，也就是说，正常用户的每次搜索和点击都
会形成训练样本，几乎实时地传递到模型训练侧，在非常短的时间内就能被应用到模型的训练中，这样就使得线上的模
型一直处于动态更新中，可以高效地对用户的行为进行学习。

举例：
现在我们假设我们开了一家物流公司。用户通过我们的网站或者app来询价，比如把一个包裹从A地邮寄到B地，而且
我们假设我们做的生意可能是面向商家的，这样我们的用户就相对比较稳定，他们会经常访问我们的网站，然后输入
发货地和收货地，我们的系统会根据这些信息来告知用户邮费大约是多少钱。基于这个邮递费用，用户可能有时候会
选择我们的邮递服务，这样就得到了一个正样本；有时候他们可能就直接离开而不选择我们的服务，那么相应地就产
生了一个负样本。所以，让我们假设我们想要一个学习算法来帮助我们优化提供给用户的价格。

我们假定通过一些渠道获取到了用户的一些特征，也有发货地和收获地的信息，同时也有我们的定价。那么我们想要
做的就是，在什么样的情况下，特别是我们给出的定价是怎样的时候，用户会更可能选择我们的邮递服务。所以，如
果我们能有一个模型估算在特定条件下用户选择我们邮递服务的概率的话，那么我们就可以尝试调整定价来提高用户
在我们这里下单的概率。当然，在这个基础上，我们再乘以定价，我们也可以计算出我们营收的期望，这样我们就不
会出现单纯为了提高成单率而无限制地降低费用，进而导致亏损的情况。

如果我们可以利用在线学习的话，我们就可以更快地将最新的样本传递给模型，尽快地对价格进行调整以获取更大的
收益。那么，为了对这个概率进行建模，我们最自然的想法就是使用逻辑回归。

在线学习要做什么呢？
1、repeat forever；
2、(x,y)不带上标，表示我们的训练集不是一个固定的训练集；
3、对于样本，我们立刻使用，使用完就不会再用了，因为如果真的是大型网站的话，只要有流量，相当于就不断会
有训练样本，所以也就没必要对样本进行重复学习；
4、当前这个例子是用于学习各个用户的价格偏好，比如经济环境如果变差了，用户对价格可能就更敏感。

举例：
另一个例子，主要关于在线购物网站的商品搜索。这里，我们想要根据用户的搜索关键词来返回更好的商品列表。
比如，用户输入了这样一个关键词：“安卓 手机 1080p 摄像头”。
假如我们这个网站有几千种手机，我们需要向用户返回跟他关键词最相关的前100种。那么，我们可能会需要一个
在线学习算法来帮助我们找到在几千种手机中，哪100种应该被提供给搜索这个关键词的用户。

对于这种大数量级的实时数据，可能在线学习能够更好地及时将数据应用到线上，快速地调整模型效果。

所以，这就是所谓的在线学习了。它跟随机梯度下降非常相似，唯一的区别在于我们不会使用一个固定的数据集，
而是遇到一个样本就使用，然后就将它丢弃。所以，如果我们处于一个时刻都有大量数据的环境下，使用在线学习
算法可能是个不错的尝试。

在线学习的一个挑战在于，我们需要能够高效、实时或者近实时地进行反作弊，也就是把作弊流量或者样本直接丢
弃，不提供给模型训练，否则模型可能会因为作弊数据产生问题。所以，在实施在线学习的时候，最好有办法能够
至少过滤掉明显的作弊数据。

mapraduce和并行处理

前面我们讨论的算法都是基于单台计算机实现的。不过在数据量超大的情况下，单台计算机已经无法满足了，不管
是存储能力还是计算能力，对于海量的数据，想要在单台计算机上训练一个机器学习模型几乎是难以实现的，因为
对于现代的一个工业级的数据集，很容易就能到达TB级，而单台计算机即使能够存储下它也无法高效地对它进行多
轮迭代应用机器学习算法。

这时候就需要并行的集群式计算。引用大数据的Map-Reduce框架是一种思路。

我们来讨论map-reduce如何应用到海量数据上。
我们现在假设要拟合一个线性回归模型或者逻辑回归模型。
首先，还是从批量梯度下降开始，如上图公式一，批量梯度下降算法。我们假定样本集的大小只有400[m=400]，在
实际问题中，m有可能是4亿，如果m很大的话，这个式子的计算量显然会很大。
map reduce会怎么做呢？
首先，我们在这里把我们的训练样本都列出来，map-reduce的思想是将这个训练集切分成多个小块，如上图，现在
我们假设有四台计算机可以用来并行算法。

每一台计算机分别迭代一部分数据。

所以，整个过程实际上跟原来的批量梯度下降是等价的，只不过我们现在是在四台计算机上完成的迭代工作。

我们有一些训练样本，如果我们想要使用四台计算机并行地运行机器学习算法，那么我们就可以将训练集切分成四
等分，然后把它们分别分配给四台计算机，那么每台计算机就对被分配到的1/4样本集进行运算，其实对我们而言大
多数时候是求和计算。最后，等四部分计算完毕，再将所有的数据汇总到某一个计算机上进行汇总计算。只有400
个样本，所以求和也只是i=1到i=400，而由于现在我们有了四台计算机可以同时进行一部分的计算工作，因此原来
需要一台计算机完成的工作现在由四台计算机完成，所以理论上最多我们可以相较于原来一台计算机要快4倍。当然，
在实际中我们不可能得到这么多的加速效果，因为计算机之间存在网络延迟，数据需要来回传输等因素，所以实际上
我们得到的加速效果总是要小于4倍的，不过不管怎么说，这种分布式并行化的工作总会使得我们的整体加速效果要
好不少。而且，它的好处在于，只要拥有足够的计算机，我们几乎可以处理任意大量的数据集，训练我们的模型。

那么使用map reduce来进行大规模机器学习看上去是很好的一种解决方案，唯一的问题在于，是否学习算法能够表达
成求和的形式呢？

事实上，大量的机器学习算法都可以表达成求和的形式。很多学习算法之所以对于大规模数据更加耗时，主要还是在于
计算对大量数据的某些求和运算上，所以这些算法都可以表示为对训练集的某种形式的求和形式。那么，只要学习算法
的主要工作可以表达成求和形式的话，应用map reduce计算框架就显得非常容易了。

多核计算机也是可以使用mapraduce的思想的。

生产环境中，我们可以从sklearn的机器学习库中找算法支持单台计算机上的多核并行化；spark的MLLib支持我们利用
计算机集群来对大规模海量数据运行机器学习算法。