第十八章 大规模机器学习
该系列文章为，观看“吴恩达机器学习”系列视频的学习笔记。虽然每个视频都很简单，但不得不说每一句都非常的简洁扼要，浅显易懂。非常适合我这样的小白入门。
18.1 学习大数据集
我们为什么要用这么大的数据集了？
在机器学习中，通常情况下，决定因素往往不是最好的算法，而是谁的训练数据最多
大数据学习有其特有的问题。具体来说，是计算问题。 如果我们有一个低方差的模型，增加数据集的规模可以帮助你获得更好的结果。我们应该怎样应对一个有1亿条记录的训练集？
以线性回归模型为例，每一次梯度下降迭代，我们都需要计算训练集的误差的平方和，如果我们的学习算法需要有20次迭代，这便已经是非常大的计算代价。
首先应该做的事是去检查一个这么大规模的训练集是否真的必要，也许我们只用1000个训练集也能获得较好的效果，我们可以绘制学习曲线来帮助判断。
左图为“高偏差”图形，增加训练数据，可以提高算法。右图为“高方差”图形，增加训练集，对算法的提高并没有很大的帮助。
因此，在大规模的机器学习中，我们喜欢找出合理的计算方法或高效的计算方法，来处理庞大的数据集。在接下来的几节视频中，我们将了解两个主要方法。第一个称为“随机梯度下降法”，第二个为“Mini-Batch梯度下降法”。
18.2 随机梯度下降
当我们的数据集很大时，梯度下降算法的计算量会变得非常大。这里我们将讨论对普通梯度下降算法的改进，称之为“随机梯度下降法”。这将使我们的算法能应用于更大的训练集中。
假设你正在使用梯度下降法来训练一个线性回归模型
随机梯度下降的思想是一种常见的思想，它也同时应用于其他算法。比如，逻辑回归、线性回归，神经网络或者其他基于梯度下降的对应特定训练集的算法。
“批量”梯度下降法。“批量”这个词指的是，我们每次都要同时考虑所有的训练样本，我们称之为，一批训练样本。
在随机梯度下降法中，我们定义代价函数为一个单一训练实例的代价：
随机梯度下降法：
- 随机打乱所有数据。随机的意思是，将所有m个训练样本重新随机排列。这是标准的数据预处理过程
- 随机梯度下降的主要算法
所以，随机梯度下降算法实际上就是遍历所有的训练样本。首先是我的第一组训练样本(x^(1), y^(1))。现在我们只看第一个样本，此时我们只对第一个训练样本的代价函数进行梯度下降操作。换句话说，我们只关注第一个训练样本，然后把参数稍微修改一下，使其对第一个训练样本拟合更好一点。完成一个内层循环后，然后继续进行第二个训练样本，这里我们做的就是在参数空间中进行另外一小步，也是将参数稍微修改一下，使它对第二个样本拟合得更好一点。以此类推。。。直到完成所有的训练集。 从这个角度分析随机梯度下降算法，我们能更好的理解为什么一开始要随机打乱数据。这保证了我们在遍历训练集时，对训练样本的访问是以随机顺序排列的。不管你的数据是否已经随机排列过，或是一开始就按某种奇怪的顺序排列的。实际上，这一步能让随机梯度下降在收敛时能够更快一点，为了保险起见，通常情况下最好还是先把所有数据随机打乱一下。因为你可能不知道数据是否已经随机排列过，但对于随机梯度下降的更重要的一点是与批量梯度下降不同。随机梯度下降不需要对全部m个样本求和来得到梯度项。
随机梯度下降算法在每一次计算之后便更新参数 θ ，而不需要首先将所有的训练集求和，在梯度下降算法还没有完成一次迭代时，随机梯度下降算法便已经走出了很远。但是这样的算法存在的问题是，不是每一步都是朝着”正确”的方向迈出的。因此算法虽然会逐渐走向全局最小值的位置，但是可能无法站到那个最小值的那一点，而是在最小值点附近徘徊。
实际上，当你运行随机梯度下降时，和批量梯度下降相比收敛的形式是不同的。随机梯度下降所做的就是连续不断地在某个区域中朝着全局最小值的方向徘徊，而不是直接达到全局最小值。这在实际中其实完全可行，只要参数最终能移动到靠近全局最小值的区域内。所以，只要参数最后能够非常接近全局最小值，我们就能得到一个很好的假设。 因此，通常我们用随机梯度下降法能得到一个很接近全局最小值的参数。
最后一点细节，在随机梯度下降法中，我们有一个外层循环（Repeat 这一层），它决定了内层循环的执行次数。那么这个外层循环的次数应该是多少了？这取决于训练集的大小，通常一次就够了，最多到10次，但那是特殊情况。如果我们有一个非常大的数据集，很可能当你仅遍历一次你的训练集时，你就能得到一个非常好的假设函数。 通常来说，外循环 1 - 10 次都是非常合理的。但这还是取决于你的训练样本的大小。
18.3 Mini-Batch 梯度下降
“批量”梯度下降算法中，每次迭代，我们都要用到所有的m个样本。 “随机”梯度下降算法中，每次迭代，我们只需要使用一个样本。 “Mini-Batch”梯度下降算法，则是介于两者之间。具体来说，这个算法，每次迭代，都会使用 b 个样本。总共的循环次数为 m / b，这样才能遍历所有的训练样本。
外层循环的（Repeat）的次数为 m / i。m：样本数、i ：一次内循环的样本数。 这里 b 是一个称为“mini-batch 大小”的参数。通常会选择 b 的值为 b = 10，同时 b 的取值范围为 2 ~ 100 。 这样做的好处在于，我们可以用向量化的方式来循环 b个训练实例，如果我们用的线性代数函数库比较好，能够支持平行处理，那么算法的总体表现将不受影响（与随机梯度下降相同）。
与“批量”梯度下降相比，它的运行过程会更快。
“Mini-Batch”梯度下降法 VS “随机”梯度下降法
- 在向量化过程中，特别的，Mini-Batch梯度下降算法可能会比随机梯度下降算法更好。仅当你有一个好的向量化方式，能使你的向量化累加部分可以并行计算（在多次Repeat过程中时，这个累加操作是每次Repeat过程的内循环，并行计算的单位是这个内循环累加计算）。 但，如果是“随机”梯度下降法的话，每次仅编译一个样本，很明显一次仅遍历一个样本不会有很多的并行计算。至少，有很少的并行计算。
- Mini-Batch梯度下降算法的缺点之一是，当有一个额外的参数b时，你需要确定 Mini-Batch 的大小，这可能需要费些时间。不过，如果你有优秀的向量化方法，有时它将比随机梯度下降运行的更快。
18.4 随机梯度下降收敛
现在我们介绍随机梯度下降算法的调试以确保算法正确收敛，以及学习率 α 的选取。
收敛检测：
“批量”梯度下降法，通过绘制“假设函数每次迭代的下降”函数来判断算法是否收敛。
当“随机”梯度下降算法对训练集进行扫描时，在我们使用某个样本(x^(i), y^(i))来更新 θ 之前。让我们来计算出这个样本假设的表现有多好（即，计算 cost函数），我要在更新 θ 前来完成这一步。 最后，为了检查随机梯度下降是否收敛，我们要做的是每1000次迭代，我们就画出这1000步的每前一步中所计算出的cost的平均值。这样做能有效帮你估计出你的算法在前1000个样本上，表现有多好。
- 示例一
?该图可以说明，该“随机”梯度下降算法已经收敛了（蓝线），并在箭头指向的地方，差不多就收敛了。 当我们使用更小的 学习速率α 时，可能得到红色的线。因为学习速率更小了，所以下降的更慢了，但也得到了一个很好的收敛结果。这是因为，随机梯度下降算法不是直接收敛到全局最小值，而是在一个范围内反复震荡，最后逐渐接近全局最小值。所以，如果使用一个更小的学习速率，最后这种震荡就会更小。 但，两个曲线的（蓝色和红色）的这点区别，有时候是会被忽略的，有时候会选择使用更小的学习速率。
- 示例二
蓝色曲线为 一次 1000 个样本的图形；红色曲线为 一次 5000 个样本的图形 你会发现，使用一次 5000 个样本的曲线 比 一次1000 个样本的曲线 更平滑，这就是如果你增大训练样本的数量所得到的情形。当然，它的缺点是，每隔5000个样本你才能得到一个数据点，因此你得到的有关与算法表现有多好的反馈就显得有一些延迟。
- 示例三
蓝色曲线为 一次 1000 个样本的图形；红色曲线为 一次 5000 个样本的图形 如果出现?这种情况，（蓝线）看起来你的代价函数，完全没有在减小，看起来算法没有在进行学习，因为曲线整体看起来是平的，代价函数的值好像没有下降。但，如果你增加 每次Mini-Batch样本的数量，那么可能会观察到红色线的情况。能看出，实际上代价函数是在下降的，只不过蓝线求均值的样本太少了，所以包含了太多的噪声。导致你，看不出函数实际上是趋向于减少的。这种情况下，每次5000个样本比每次1000个样本要好。 当然，如果我们用更多的样本来求均值，得到的确实 粉色的学习曲线。即使你使用了更大数量的样本，曲线还是很平坦，那就代表算法不知道出于何种原因没有进行学习。这个时候，就需要调整学习速率，或调整特征，或者调整算法的其他东西。
- 示例四
如果，你得到?这样的曲线。这种情况，就是计算发散的信号，这时你要做的就是，用一个更小的学习速率α。
最后还需要说一下，关于学习速率的问题。
在大多数的，随机梯度下降的典型应用中，学习速率α 一般是一个不变的常数。因此你最终会得到?这样的一个结果（即，随机梯度下降算法虽然会逐渐走向全局最小值的位置，但是可能无法站到那个最小值的那一点，而是在最小值点附近徘徊。）
如果，你想让随机梯度下降更好地收敛到全局最小值，你可以做的就是让学习速率α 的值随时间变化逐渐减小。所以，一种典型的方法就是，让 α 等于：
iterationNumber 指的是，你运行随机梯度下降的迭代次数，实际上，就是你已经计算的训练样本数量；而 const 1 和 const 2 是算法的两个额外的参数。你同样需要选择合适的值，才能得到较好的表现。
但是通常我们不需要这样做便能有非常好的效果了，对α进行调整所耗费的计算通常不值得。但如果你能很好地调整这些参数，最后得到的图像，你的算法还是会在最小值附近震荡，但它会更接近最小值。因为这时，你减小了学习速率，那么这个震荡也会越来越小，直到收敛到非常靠近全局最小的地方：
18.5 在线学习
在这个视频中，讨论一种新的大规模的机器学习机制，叫做在线学习机制。在线学习机制让我们可以模型化问题。
今天，许多大型网站或者许多大型网络公司，使用不同版本的在线学习机制算法，从大批的涌入又离开网站的用户身上进行学习。特别要提及的是，如果你有一个由连续的用户流引发的连续的数据流，进入你的网站，你能做的是使用一个在线学习机制，从数据流中学习用户的偏好，然后使用这些信息来优化一些关于网站的决策。
假定你有一个提供运输服务的公司，用户们来向你询问把包裹从A地运到B地的服务，同时假定你有一个网站，让用户们可多次登陆，然后他们告诉你，他们想从哪里寄出包裹，以及包裹要寄到哪里去，也就是出发地与目的地，然后你的网站开出运输包裹的的服务价格。比如，我会收取
20之类的，然后根据你开给用户的这个价格，用户有时会接受这个运输服务，那么这就是个正样本，有时他们会走掉，然后他们拒绝购买你的运输服务，所以，让我们假定我们想要一个学习算法来帮助我们，优化我们想给用户开出的价格。
在线学习算法指的是对数据流而非离线的静态数据集的学习，一个算法来从中学习的时候来模型化问题。许多在线网站都有持续不断的用户流，对于每一个用户，网站希望能在不将数据存储到数据库中便顺利地进行算法学习。
- 举个例子
假使我们正在经营一家物流公司，每当一个用户询问从地点A至地点B的快递费用时，我们给用户一个报价，该用户可能选择接受（y=1）或不接受（y=0）。 现在，我们希望构建一个模型，来预测用户接受报价使用我们的物流服务的可能性。因此报价 是我们的一个特征，其他特征为距离，起始地点，目标地点以及特定的用户数据。模型的输出是:p(y=1)。
我们用logistic回归，或者神经网络，或者其他一些类似的算法一些类似的算法。但现在我们先来考虑用logistic回归。 在线学习的算法与随机梯度下降算法有些类似，我们对单一的实例进行学习，而非对一个提前定义的训练集进行循环。
一旦对一个数据的学习完成了，我们便可以丢弃该数据，不需要再存储它了。这种方式的好处在于，我们的算法可以很好的适应用户的倾向性，算法可以针对用户的当前行为不断地更新模型以适应该用户。
如果你真的有一个大型网站，网站有连续的用户流，那么这种在线学习算法就非常适用。因为，你相当于可以免费获取数据，如果你有如此多的数据。可以获取的数据可以说是无限的，那么或许就真的没必要多次使用一个样本。当然，如果我们只有少量的用户，那么就最好不要用这种在线学习算法。而是把所有的数据，保存在一个固定的数据集里。然后对这个数据集使用某种算法，但是如果你有连续的数据流，那么在线学习算法会非常有效。
每次交互事件并不只产生一个数据集，例如，我们一次给用户提供3个物流选项，用户选择2项，我们实际上可以获得3个新的训练实例，因而我们的算法可以一次从3个实例中学习并更新模型。
- 另一个例子：
这是一个产品搜索的应用。我们想要使用一种学习算法来学习如何反馈给用户好的搜索列表。
特征 x 包括了，手机的特征，以及用户搜索的关键字与手机名称的匹配程度，或与手机描述的匹配程度等。 这个也叫做，点击率预测学习问题。即，CTR（点击率的缩写）。用户点击某个你提供给他链接的概率。
- 其他例子： Other examples: Choosing special offers to show user；customized selection of new articles；product recommendation；...
这些问题中的任何一个都可以被归类到标准的，拥有一个固定的样本集的机器学习问题中。或许，你可以运行一个你自己的网站，尝试运行几天，然后保存一个数据集，一个固定的数据集，然后对其运行一个学习算法。但是这些是实际的问题，在这些问题里，你会看到大公司会获取如此多的数据，真的没有必要来保存一个固定的数据集，取而代之的是你可以使用一个在线学习算法来连续的学习，从这些用户不断产生的数据中来学习。这就是在线学习机制，然后就像我们所看到的，我们所使用的这个算法与随机梯度下降算法非常类似，唯一的区别的是，我们不会使用一个固定的数据集，我们会做的是获取一个用户样本，从那个样本中学习，然后丢弃那个样本并继续下去，而且如果你对某一种应用有一个连续的数据流，这样的算法可能会非常值得考虑。当然，在线学习的一个优点就是，如果你有一个变化的用户群，又或者你在尝试预测的事情，在缓慢变化，就像你的用户的品味在缓慢变化，这个在线学习算法，可以慢慢地调试你所学习到的假设，将其调节更新到最新的用户行为。
18.6 减少映射与数据并行
映射化简和数据并行对于大规模机器学习问题而言是非常重要的概念。之前提到，如果我们用批量梯度下降算法来求解大规模数据集的最优解，我们需要对整个训练集进行循环，计算偏导数和代价，再求和，计算代价非常大。如果我们能够将我们的数据集分配给不多台计算机，让每一台计算机处理数据集的一个子集，然后我们将计所的结果汇总在求和。这样的方法叫做映射简化。
具体而言，如果任何学习算法能够表达为，对训练集的函数的求和，那么便能将这个任务分配给多台计算机（或者同一台计算机的不同CPU 核心），以达到加速处理的目的。
例如，我们有400个训练实例，我们可以将批量梯度下降的求和任务分配给4台计算机进行处理：
很多高级的线性代数函数库已经能够利用多核CPU的多个核心来并行地处理矩阵运算，这也是算法的向量化实现如此重要的缘故（比调用循环快）。
如果你想把 MapReduce 应用在某种学习算法上，通过多台电脑并行计算，来实现加速。你需要考虑一个关键问题，你的学习算法是否可以表示成对训练集的一种求和。实际上，很多学习算法，都可以表示成对训练集的函数求和。而在大数据集上运行所消耗的计算就在于需要对非常大的训练集进行求和。所以，只要你的学习算法可以表示为对训练集的求和，或者学习算法的主要工作可以表示成对训练集的求和，那么就可以用 MapReduce。
最后再提一点，目前我们只讨论了运用MapReduce算法在多台电脑上并行计算，可能是计算机集群中的多台电脑，或者数据中心中的多台电脑。但是有时，你可以在单机上进行 MapReduce 计算，通过利用电脑的多处理核心，多CPU。使用单机多CPU执行 MapReduce 于 使用 多电脑执行 MapReduce 相比，少了网络传输的损耗（时间损耗）