机器学习算法实现的演化

问题导读：

1.目前可用的有几种机器学习工具？

2.怎样利用机器学习工具进行实时分析？

3.什么是迭代式机器学习算法 ？

下面将会对机器学习算法的不同的实现范式进行讲解，既有来自文献中的，也有来自开源社区里的。首先，这里列出了目前可用的三代机器学习工具。

• 传统的机器学习和数据分析的工具，包括SAS，IBM的SPSS，Weka以及R语言。它们可以在小数据集上进行深度分析——工具所运行的节点的内存可以容纳得下的数据集。
• 第二代机器学习工具，包括Mahout，Pentaho，以及RapidMiner。它们可以对大数据进行我称之为粗浅的分析。基于Hadoop之上进行 的传统机器学习工具的规模化的尝试，包括Revolution Analytics的成果(RHadoop)以及Hadoop上的SAS，都可以归到第二代工具里面。
• 第三代工具，比如Spark, Twister，HaLoop，Hama以及GraphLab。它们可以对大数据进行深度的分析。传统供应商最近的一些尝试包括SAS的内存分析，也属于这一类。
  

第一代机器学习工具/范式

       由于第一代工具拥有大量的机器学习算法，因此它们适合进行深度的分析。然而，由于可扩展性的限制，它们并不都能在大数据集上进行工作——比如TB或者PB 级的数据（受限于这些工具本质上是非分布式的）。也就是说，它们可以进行垂直扩展（你可以提高工具运行的节点的处理能力），但无法进行水平扩展（它们并非 都能在集群上运行）。第一代工具的供应商通过建立Hadoop连接器以及提供集群选项来解决这些局限性——这意味着它们在努力对R或者SAS这样的工具进 行重新设计以便可以进行水平扩展。这些都应该归入第二代和第三代工具，下面我们将会介绍到。

第二代机器学习工具/范式

       第二代工具（现在我们可以把传统的机器学习工具比如SAS这些称之为第一代工具了）比如 Mahout（http://mahout.apache.org），Rapidminer以及Pentaho，它们通过在开源的MapReduce产品 ——Hadoop之上实现相关算法，提供了扩展到大数据集上的能力。这些工具仍在快速完善并且是开源的（尤其是Mahout）。Mahout拥有一系列的 聚类及分类的算法，以及一个相当不错的推荐算法（Konstan和Riedl，2012）。因此它可以进行大数据的处理，现在在生产环境上已经有大量的使 用案例，主要用于推荐系统。

       我在一个线上系统中也使用Mahout来实现了一个金融领域的推荐算法，发现它确是可扩展的，尽管并不是一点问题没有（我还修 改了相当一部分代码）。关于Mahou的一项评测发现它只实现了机器学习算法中的很小的一个子集——只有25个算法是达到了生产质量的，8到9个在 Hadoop之上可用，这意味着能在大数据集上进行扩展。这些算法包括线性回归，线性支持向量机，K-means聚类算法，等等。它通过并行训练，提供了 顺序逻辑回归的一个快速的实现。然而，正如别人指出的（比如Quora.com），它没有实现非线性支持向量机以及多变项逻辑回归（这也称为离散选择模 型）。

       毕竟来说，本书并不是要为了抨击Mahout的。不过我认为有些机器学习算法的确是很难在Hadoop上实现，比如支持向量机的核函数以及共轭梯度法 （CGD，值得注意的是Mahout实现了一个随机梯度下降）。这一点别人也同样指出了，比方说可以看一下Srirama教授的一篇论文（Srirama 等人，2012年）。这里详细地比较了Hadoop和Twister MR（Ekanayake等，2010年）在诸如共轭梯度法等迭代式算法上的不同，它指出，Hadoop上的开销非常明显。我所说的迭代式是指什么？一组执行特定计算的实体，在等待邻居或者其它实体的返回结果，然后再进行下一轮迭代。CGD是迭代式算法的最佳范例——每个CGD都可以分解成daxpy,ddot，matmul等原语。

       我会分别解释这三种原语都是什么：daxpy操作将向量x与常量k相乘，然后再和另一个向量y进行相加；ddot会计算两个向量x,y的点积;matmul将矩阵与向量相乘，然后返回另一个向量。这意味着每个操作对应一个MapReduce操作，一次迭代会有6个MR操作，最终一次CG运算会有100个MR操作，以及数GB的数据交互，尽管这只是很小的矩阵。事实上，准备每次迭代的开销（包括从HDFS加载数据到内存的开销）比迭代运算本身的都大，这导致Hadoop上的MR会出现性能下降。相反，Twister会区分静态数据和可变数据，使得数据可以在MR迭代过程中常驻内存，同时还有一个合并阶段来收集reduce阶段输出的结果，因此性能有明显的提升。

       第二代工具还有一些是传统工具基于Hadoop上进行的扩展。这类可供选择的有Revolution Analytics的产品，它是在Hadoop上对R语言进行了扩展，以及在Hadoop上实现R语言程序的一个可扩展的运行时环境（Venkataraman等
，2012）。SAS的内存分析，作为SAS的高性能分析工具包中的一部分，是传统工具在Hadoop集群上进行规模化的另一个尝试。然而，最近发布的版本不仅能在Hadoop上运行，同时也支持Greenplum/Teradata，这应该算作是第三代机器学习的方法。另一个有趣的产品是一家叫Concurrent Systems的初创公司实现的，它提供了一个预测模型标记语言（Predictive Modeling Markup Language，PMML）在Hadoop上的运行环境。PMML的模型有点类似XML，使得模型可以存储在描述性语言的文件中。传统工具比如 R以及SAS都可以将模型保存在PMML文件里。Hadoop上的运行环境使得它们可以将这些模型文件存储到一个Hadoop集群上，因此它们也属于第二代工具/范式。

第三代机器学习工具/范式

       Hadoop自身的局限性以及它不太适合某类应用程序，这促进研究人员提出了新的替代方案。第三代工具主要是尝试超越Hadoop来进行不同维度的分析。我将会根据三种维度来讨论不同的实现方案，分别是机器学习算法，实时分析以及图像处理。

1. 迭代式机器学习算法

       伯克利大学的研究人员提出了一种替代方案：Spark（Zaharia等，2010年）——也就是说，在大数据领域，Spark被视为是替换Hadoop的下一代数据处理的解决方案。Spark有别于Hadoop的关键思想在于它的内存计算，这使得数据可以在不同的迭代和交互间缓存在内存里。研发Spark的主要原因是，常用的MR方法，只适用于那些可以表示成无环数据流的应用程序，并不适用于其它程序，比如那些在迭代中需要重用工作集的应用。因此他们提出了这种新的集群计算的方法，它不仅能提供和MR类似的保证性和容错性，并且能同时支持迭代式及非迭代式应用。伯克利的研究人员提出了一套技术方案叫作BDAS，它可以在集群的不同节点间运行数据分析的任务。


       BDAS中最底层的组件叫做Mesos，这是个集群管理器，它会进行任务分配以及集群任务的资源管理。第二个组件是基于Mesos构建的Tachyon文件系统 。Tachyon提供了一个分布式文件系统的抽象以及在集群间进行文件操作的接口。在实际的实施方案中，作为运算工具的Spark，是基于Tachyon和Mesos来实现的，尽管不用Tachyon，甚至是不用Mesos也可以实现。而在Spark基础上实现的Shark，则提供了集群层面的结构化查询 语言的抽象——这和Hive在Hadoop之上提供的抽象是一样的。Zacharia等人在他们的文章中对Spark进行了探索，这是实现机器学习算法的重要组成部分。


       HaLoop（Bu等人，2010）也扩展了Hadoop来实现机器学习算法——它不仅为迭代式应用的表示提供了一层编程抽象，同时还使用了缓存的概念来 进行迭代间的数据共享，以及对定点进行校验，从而提高了效率。Twister( http://iterativemapreduce.org )是类似HaLoop的一个产品。


2. 实时分析


       实时分析是超越Hadoop考虑的第二个维度。来自Twitter的Storm（感觉原文说反了）是这一领域的最有力的竞争者。Storm是一个可扩展的复杂事件处理引擎，它使得基于事件流的实时复杂运算成为了可能。一个Storm集群的组件包括：
              Spout，用于从不同的数据源中读取数据。有HDFS类型的spout，Kafka类型的spout，以及TCP流的spout。
              Bolt，它用于数据处理。它们在流上进行运算。基于流的机器学习算法通常都在这里运行。
              拓扑，这是具体应用特定的spout和bolt的一个整合——拓扑运行于集群的节点上。

       在实践中，一个架构如果同时包含了Kafka（来自LinkedIn的一个分布式队列系统）集群来作为高速的数据提取器，以及Storm集群来进行处理或 者分析，它的表现会非常不错，Kafka spout用来快速地从Kafka集群中读取数据。Kafka集群将事件存储在队列中。由于Storm集群正忙于进行机器学习，因此这么做是很有必要 的。本书的后续章节将会对这个架构进行详细的介绍，以及在Storm集群中运行机器学习算法所需的步骤。Storm也被拿来跟实时计算领域的其它竞争者进 行比较，包括Yahoo的S4以及Typesafe的Akka。

顶顶顶顶顶顶顶顶顶顶顶顶