分布式机器学习（一）：前言(转)

从毕业加入Google开始做分布式机器学习，到后来转战腾讯广告业务，至今已经七年了。我 
想说说我见到的故事和我自己的实践经历。这段经历给我的感觉是：虽然在验证一个新的并 
行算法的正确性的时候，我们可以利用现有框架，尽量快速实现，但是任何一个有价值的机 
器学习思路，都值得拥有自己独特的架构。所以重点在有一个分布式操作系统，方便大家开 
发自己需要的架构（框架），来支持相应的算法。如果你关注大数据，听完我说的故事，应 
该会有感触。 

大数据和分布式机器学习特点 
说故事之前，先提纲挈领的描述一下我们要解决的问题的特点。我见过的有价值的大规模机 
器学习系统，基本都有三个特点： 

可扩展。可扩展的意思是“投入更多的机器，能处理更大的数据”。而传统的并行计算要的 
是：“投入更多机器，数据大小不变，计算速度更快”。这是我认识中“大数据”和传统并 
行计算研究目标不同的地方。如果只是求速度快，那么multicore和GPU会比分布式机器学习 
的ROI更高。有一个框架（比如MPI或者MapReduce或者自己设计的），支持fault 
recovery。Fault recovery是可扩展的基础。现代机群系统都是很多用户公用的，其中任何 
一个进程都有可能被更高优先级的进程preempted。一个job涉及数千个进程（task 
processes），十分钟里一个进程都不挂的概率很小。而如果一个进程挂了，其他进程都得 
重启，那么整个计算任务可能永远都不能完成。 

数学模型要根据架构和数据做修改。这里有两个原因：因为大数据基本都是长尾分布的，而 
papers里的模型基本都假设数据是指数分布的（想想用SVD做component analysis其实假设 
了Gaussian distributed，latent Dirichlet allocation假设了multimonial 
distribution。）。真正能处理大数据的数学模型，都需要能更好的描述长尾数据。否则， 
模型训练就是忽视长尾，而只关注从“大头”数据部分挖掘“主流”patterns了。很多机器 
学习算法（比如MCMC）都不适合并行化。所以往往需要根据模型的特点做一些算法的调整。 
有时候会是approximation。比如AD-LDA算法是一种并行Gibbs sampling算法，但是只针对 
LDA模型有效，对其他大部分模型都不收敛，甚至对LDA的很多改进模型也不收敛。 

引入更多机器的首要目的不是提升性能，而是能处理更大的数据。用更多的机器，处理同样 
大小的数据，期待speedup提高——这是传统并行计算要解决的问题——是multicore、 
SMP、MPP、GPU还是Beowolf cluster上得分布式计算不重要。在大数据情况下，困难点在问 
题规模大，数据量大。此时，引入更多机器，是期待能处理更大数据，总时间消耗可以不变 
甚至慢一点。分布式计算把数据和计算都分不到多台机器上，在存储、I/O、通信和计算上 
都要消除瓶颈。 

上述三个特点，会在实践中要求“一个有价值的算法值得也应该有自己独特的框架”。 

概念 
在开始说故事之前，先正名几个概念：Message Passing和MapReduce是两个有名的并行程序 
编程范式（paradigm），也就是说，并行程序应该怎么写都有规范了——只需要在预先提供 
的框架（framework）程序里插入一些代码，就能得到自己的并行程序。Message Passing范 
式的一个框架叫做MPI。MapReduce范式的框架也叫MapReduce。而MPICH2和Apache Hadoop分 
别是这MPI和MapReduce两个框架的实现（implementations）。另一个本文会涉及的 
MapReduce实现是我用C++写的MapReduce Lite。后面还会提到BSP范式，它的一个著名的实 
现是Google Pregel。 

MPI这个框架很灵活，对程序结构几乎没有太多约束，以至于大家有时把MPI称为一组接口 
（interface）——MPI的I就是interface的意思。 

这里，MPICH2和Hadoop都是很大的系统——除了实现框架（允许程序员方便的编程），还实 
现了资源管理和分配，以及资源调度的功能。这些功能在Google的系统里是分布式操作系统 
负责的，而Google MapReduce和Pregel都是在分布式操作系统基础上开发的，框架本身的代 
码量少很多，并且逻辑清晰易于维护。当然Hadoop已经意识到这个问题，现在有了YARN操作 
系统。（YARN是一个仿照UC Berkeley AMPLab的Mesos做的系统。关于这个“模仿”，又有 
另一个故事。）