机器学习（七）

处理大数据集的算法

大数据集学习有其特有的问题，具体来说是计算问题。
下面将讲述两个主要方法用来处理庞大的数据集，第一个称为随机梯度下降，第二个是减少映射。
对于很多机器学习的算法，例如线性回归，逻辑回归和神经网络。我们推导算法的方法是提出一个代价函数，或是提出一个优化目标，然后用梯度下降算法求代价函数的最小值，但当我们的训练集很大时，梯度下降算法的计算量会变得非常大。故对普通的梯度下降算法进行改进，称之为随机梯度下降算法，这将使我们的算法能应用于更大的训练集中。

• 假设你在使用梯度下降法来训练一个线性回归模型

  • 批量梯度下降算法：
    我们每次都要同时考虑所有的训练样本，我们称之为一批训练样本。
    J t r a i n ( θ ) = 1 2 m ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 R e p e a t { θ j : = θ j − α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) f o r      e v e r y    j = 0 , . . . , n } J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2 \\ Repeat \{ \\ \theta_j:=\theta_j - \alpha\frac{1}{m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\\ for\;\;every \;j=0,...,n\\ \} Jtrain​(θ)=2m1​i=1∑m​(hθ​(x(i))−y(i))2Repeat{θj​:=θj​−αm1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​foreveryj=0,...,n}

  • 随机梯度下降算法：
    为了更好的描述随机梯度下降算法，我们用另一种形式把代价函数写出来，我们将代价函数定义为
    $$cost(\theta ,(x^{(i)},y^{(i)}))=\frac{1}{2}(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$$
    $$J_{train}(\theta )=\frac{1}{m}\sum _{i=1}^{m}cost(\theta ,(x^{(i)},y^{(ib)}))$$
    梯度下降第一步是随机打乱所有数据，接下来对所有训练样本进行遍历。然后进行如下更新
    
    在随机梯度下降算法中，我们有一个外层循环，它决定了内循环的执行次数，所以，外层循环应该执行多少次却决于训练集的大小，通常一次就够了，最多到10次，但那是特殊情况。

• 总结：批量梯度下降算法中，每次迭代，我们都要用到所有的m个样本，而在随机梯度下降算法中，每次迭代我们只需使用一个样本。-

• Mini-batch梯度下降算法则是介于两者之间，具体来说，这个算法每次迭代会使用b个样本，这里b是一个称为mini-batch大小的参数，通常会选择b的值为10，同时b的取值范围为b=2到b=100。它的思想是，既不一次只用1个样本，也不一次使用m个样本，而是一次用b个样本。
  

随机梯度下降收敛

下面讲述如何确保调试过程已经完成，并且已收敛到合适的位置。
以及怎样调整随机梯度下降中的学习速率$\alpha$的值。

• 回顾之前的批量梯度下降算法，确保梯度下降已收敛的一个标准方法就是绘制优化代价函数，这是一个关于迭代次数的函数，我们要确保这个代价函数在每一次迭代中，都是下降的。当训练集比较小的时候，这很容易，因为我们可以迅速算出和值。但是当训练集非常大的时候，你不会希望定期暂停你的算法，来计算这个式子，因为要求出这个式子就得遍历整个训练集。
  $$J_{train}(\theta )=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$$
• 而随机梯度下降算法是，每次只考虑一个单独的样本，每次都能让算法前进一点儿，而不需要时不时地在算法运行过程中扫描一遍整个训练集来计算出整个训练集的代价函数。
  因此对于随机梯度下降算法，为了检查算法是否收敛，我们可以进行下面的工作：
  让我们沿用之前定义的cost函数，这个关于单个训练样本的函数
  $$cost(\theta ,(x^{(i)},y^{(i)}))=\frac{1}{2}(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$$
  当随机下降法进行学习时，在我们对某一个样本进行训练前，在随机梯度下降中，我们要关注某样本$(x^{(i)},y^{(i)})$，然后对这个样本做一次小小的更新，然后再到下一个样本$(x^{(i+1)},y^{(i+1)})$，以此类推，这就是随机梯度下降的做法。
  当随机梯度下降法对训练集进行扫描时，在我们使用某个样本$(x^{(i)},y^{(i)})$来更新$\theta$之前，让我们来计算出这个训练样本假设的表现有多好，我要在更新$\theta$前来完成这一步。
  因为如果我们用这个样本更新了$\theta$的话，再让它在该训练样本上进行预测，其表现就比当前样本更好了。最后为了检查随机梯度下降是否收敛，我们要做的是，每1000次迭代，我们就画出前一步中所计算出的cost函数，我们把这些前1000个样本的cost函数的平均值画出来。如果这样做的话，它会有效地帮你估计出你的算法在前1000个样本上表现有多好，所以比起之前需要时不时地计算$j_{train}$，那样就得遍历所有的样本，而随机梯度下降法的这个步骤只用在$\theta$之前计算这些cost函数，并不需要太大的的计算量。通过观察所画的图就能知道随机梯度下降是否在收敛。
  • 假设你已经画出来前1000组样本的cost函数平均值，由于它们只是1000组样本的平均值，因此看起来会有很多噪声，它可能不是每一步迭代都在下降，假如你得到下图，那么这是一个不错的下降过程，可以看出代价函数的值在下降，然后从这个点开始图像变得平缓。
    通过这幅图像，可以得知，你的学习算法已经收敛了，如果你尝试用一个更小的学习速率，那么你可能看到算法的学习变得更慢了，所以代价函数下降也变缓了，但由于使用了更小的学习率（红色曲线），最后可能会让算法收敛到一个更好的结果。
  • 假如你运行随机梯度下降对1000组样本取cost函数平均值并且画出图像，那么这可能是另一种可能出现的情况。看起来算法大概已经收敛了，如果你把这个1000组样本提高到要去计算5000组样本的均值，那么你可能会得到一条更平滑的曲线（红色曲线），求出均值以后你会发现5000组样本比起1000组样本得到的曲线更为平滑。这就是如果你增大训练样本的数量所得到的情形，当然它的缺点是，每隔5000个样本你才能得到一个数据点，因此你得到算法表现有多好的反馈会有些迟。
  • 有时候会得到下面这种图形，如果出现这种情况，看起来你的代价函数完全没有在减小，看起来算法没有进行学习，因为曲线整体看起来是平的，代价函数的值好像没有下降，但如果这时你增加训练样本组数来对更多的样本进行求均值，那么很可能会观察到红线所示的情况，能看出实际上代价函数是在下降的，只不过蓝线求均值的样本太少了所以包含了太多的噪声导致你看不出函数实际上是趋于减少的。如果我们用更多的样本来求均值，却得到了像粉线这样的曲线，即使你使用了更大数量的样本，曲线还是很平坦，如果得到这样的结果。那就代表算法不知道出于何种原因没有进行学习，那么这时就需要调整学习速率或调整特征，或者调整算法的其他东西。
    
  • 最后，你可能会遇到一条这样的曲线，你会发现曲线是这样的，它看起来是在上升的，这种情况就是算法发散的信号，这时你要做的就是用一个更小的学习率$\alpha$
    
• 当运行随机梯度下降时，算法会从某个点开始，然后曲折地达到最小值，但它不会完全收敛，而是在最小值附近一直徘徊，因此你最终得到的参数只是一个全局最小值的接近值，而不是真正的全局最小值。在大多数多数随机梯度下降法的典型应用中，学习速率$\alpha$一般是一个不变的常数，因此你最终会得到这样的结果。
  如果你想让随机梯度下降更好地收敛到全局最小值，你可以做的就是让学习速率$\alpha$的值随时间变化逐渐减小，所以，一种典型的方法就是设置$\alpha$的值，让$\alpha =\frac{常数1}{迭代次数+常数2}$
  上述办法很少使用，因为确定两个常数的值需要额外的工作，即使不使用上述办法，得到的结果也足够让人满意了。

在线学习机制

在线学习机制让我们可以模型化一些问题。
就是我们有一波连续的数据流想要用算法从中学习的这类问题。
如今有许多大型网站或者许多大型网络公司使用不同版本的在线学习机制算法，从大批涌入网站的用户身上进行学习，特别是，如果你有一个由不断进入的网站的用户流所产生的连续的数据流，你就可以使用在线学习机制从数据流中学习用户的偏好，然后使用这些信息来优化关于网站的决策。

• 举例：快递公司邮费定价
• 举例：产品搜索，反馈给用户好的搜索列表。
• 在线学习机制与随机梯度下降算法的区别在于，我们不会使用一个固定的数据集，而是一个用户样本，从那个样本中学习，然后丢弃那个样本，继续处理下一个，而且如果你的某一种应用有一个连续的数据流。这样的算法可能会非常值得考虑。
• 在线学习有一个优点就是，如果你有一个变化的用户群，又或者，你在尝试预测的事情，在缓慢变化，例如用户的品味在慢慢变化，在线学习算法可以慢慢地调试你所学习到的假设，将其调节更新到最新的用户行为。

MapReduce

很多机器学习过于庞大以至于不能单机运行，有时候可能数据太多了，你不想把所有数据都在一台电脑上跑一遍，无论你在这台电脑上使用了什么算法。
下面将介绍MapReduce，这个方法可以应用在大规模机器学习上。

• MapReduce的思想来自于研究员Jeff Dean和Sanjay Ghemawat。假定我们有训练集，用一个方框表示数据对(x,y)，它从$(x^{(1)},y^{(1)})$开始一直到400（这里假设m=400），即$(x^{(m)},y^{(m)})$。于是我的训练集有400个样本，根据MapReduce思想，我把训练集分割成不同的子集，这个例子中，我假定有4台电脑或者4台机器并行，处理训练集数据，因此我把数据分成4份。如果你有10台或者100台机器，你可以把你的训练集分为10份或者100份。四台机器中的第一台要做的就是用前四分之一的训练集，也就是前100个训练样本，然后计算出$tem{p}_j^{(1)}$，第二台机器处理第101~200个训练样本，然后计算出$tem{p}_j^{(2)}$，依次类推。每台机器只需要做四分之一的工作，这使得它们将运算速度提高到原来的四倍。
  最后，完成这些计算后，我将这些temp变量重新放在一起，就是把这些变量发送给一个中心服务器，中心服务器会整合这些结果，尤其是它将更新我的参数${\theta }_j$
• 如果想在某种算法上使用MapReduce，通过多台电脑并行计算来实现加速，你需要思考一个关键问题，你的学习算法是否可以表示成对训练集的一种求和。
  实际上很多学习算法都可以表示成对训练集的函数求和，而在大数据集上运行，所消耗的计算量就在于需要对非常大的训练集进行求和，所以只要你的学习算法可以表示为对训练集的求和或者学习算法的主要工作可以表示成对训练集的求和那么就可以用MapReduce将你的学习算法适用范围扩大到大数据集。
• 有时也可以在单机上进行MapReduce计算，因为现在很多电脑可以有多个处理核心，多个CPU，CPU又有多个核心。如果你有一个很大的数据集，然后比如你有一个四核的电脑，就是四个计算核心，那么即使在单机上，你也可以把训练集分成多份，然后把训练集发送给多个核心，在一台机器中完成。只需要用一个台式或者一个机器用MapReduce方法分摊工作。这里是一台机器中多个核心的并行，好处是不同担心网络延迟问题。

照片OCR

展示一个复杂的机器学习系统是如何被组合起来的。
介绍机器学习流水线有关的概念以及如何分配资源，来对下一步计划做出决定。这既适用于自己开发一个复杂的机器学习应用，也可以适用于一个开发团队，共同开发机器学习应用。
最后我想通过介绍照片OCR问题来告诉你机器学习中许多有用的想法和概念，其中之一就是如何将机器学习应用到计算机视觉问题中，而另外一个就是人工数据合成的概念。
虽然现在照片OCR对于扫描文档来说已经是一个比较简单的问题了，但对于数码文档来说，现在还是一个很难的机器学习问题。

• 照片OCR全称为照片光学字符识别，照片OCR问题注重的问题是如何让计算机读出图中的文字信息，它有如下几个步骤：
  1. 首先，给定某图片，它将图像扫描一遍，然后找出图片中的文字信息。
  2. 完成第一步，成功找出这些文字以后，它将重点关注这些文字区域，并对区域中的文字进行识别。
  3. 当它正确读出这些文字以后，它会将这些文字内容显示并记录下来。
• 为了实现照片OCR：
  Step1:扫描图像，并找出有文字的图像区域。
  Step2：进行文字分离，识别出单词，并且将其分割成一个个独立的字符的区域。
  Step3：用分类器对这些可见的字符进行识别，
• 实际上有一些照片OCR系统会做一些更复杂的事情，比如最后会进行拼写校正。举个例子，假如你的字符分割和分类系统告诉你它识别的字符是“C1eaning”，然后一些拼写修正系统就会告诉你这应该是单词"Cleaning"。

滑动窗口分类器
这里省略细节。

人工数据合成

人工数据合成只适用于特定问题，经常需要思考改进并且深入了解它。

• 人工数据合成主要有两种形式，第一种实际上是自己创造数据，即从0开始创造新数据；第二种是，我们已经有小的标签训练集，然后以某种方式扩充训练集，就是将较小的训练集转化为一个较大的训练集。这里举例字体识别和语音识别（加噪声但不要乱加无意义的噪声）。
  除此之外还提到了众包。

上限分析

即ceiling analysis，当你自己或你跟你的团队，在设计某个机器学习系统工作流时，这种方式通常能提供一个很有价值的信号，很好地指导你，你的工作流中哪一部分最值得你花时间去研究。

• 以照片OCR为例，通过分析模块你可以知道提升每个模块的潜在效果如何，或者说如果一个模块近乎完美时，系统性能能增益多少。
  
• 又举了个人脸识别的例子。

机器学习课程总结

• 监督学习算法：线性回归、逻辑回归、 神经网络以及支持向量机
• 无监督学习算法：K-均值聚类算法，主成分分析法来进行降维，以及异常检测算法（这个算法有时也可以用一些带标签的数据来对算法进行评估）
• 特定应用和话题：推荐系统、大规模机器学习系统、MapReduce、滑动窗口分类器
• 一些构建机器学习系统的建议：什么东西使得机器学习算法工作或是不工作、方差和偏差、如何使用正则化来解决一些方差问题、如何决定下一步应该做什么（如何在开发系统过程中合理分配时间）、学习算法的评价方法（召回率、F1 Score）、实践方面的评测方法（训练集，交叉验证集和测试集）、如何调试算法（确保学习算法能够正常工作）、诊断方法（学习曲线、误差分析、上限分析）