|
本文内容源自Erix Xing教授16年初的文章[1]，尽管大规模机器学习的手段和方法在业界已经研究多年，也已经形成了不少工业界使用的手段和方法，但这篇文章真正系统地从机器学习算法的本质总结并归纳出如何解决这类问题的原则，并在相应的开源项目上给予工程实现，非常值得阅读和参考。 解决大规模机器学习问题，系统框架需要在容易编程和性能，以及正确性之间取得平衡。传统基于Dataflow的框架如Hadoop/Spark，都是采用BSP，集群所有节点都需要等待执行最慢的完成后才能继续。一些基于图的方案，如GraphLab，则引入了新的问题，比如如何切分机器学习程序，计算调度，还有一致性模型。另一方面，机器学习任务抽象成图并不是很直接，把已有的算法移植到基于图的抽象上需要不少工作，而且，基于图的抽象有时还会导致程序不正确，或者陷入次优化。参数服务器是近年浮现出来的针对机器学习算法的良好抽象，然而单纯的参数服务器还缺乏从头打造机器学习算法的良好编程接口，还不能跟Hadoop/Spark这样的项目相提并论。 绝大多数机器学习算法都可以归结为类似下面的最优化问题： 其中优化目标L包含两部分，一个是损失函数f，用来描述数据如何适应模型，另一部份是一个结构诱导函数，主要用来引入领域知识来给参数施加限制或者惩罚因子。上面这个式子隐藏了解决机器学习问题面临的大数据挑战，比如一个典型的用于图像分类的卷积神经网络，包含数十亿乃至万亿的矩阵型模型参数，而损失函数则呈现出深度递归形式f=f1(f2(f3(...)+...)+...)用来学习类似人类视觉皮层的图像分层表示。图模型，特别是主题模型，经常从数十亿的文档中发现主题，比如从社交媒体中，为了捕捉丰富的语义信息，这也会有数以万亿的参数。 把上面的最优化问题更进一步细化，就变成为找到优化目标L对应的模型参数A而迭代的表达式： A(t) = F(A(t ? 1), ?_L(A(t ? 1), x)) t表示第几轮迭代。在训练中，计算程序反复迭代执行直到收敛条件或者其他停止条件满足。下一次迭代需要的模型参数A(t)从上一次的迭代参数A(t-1)和数据x中产生，用到2个函数：一个是更新函数?，其优化目标(或损失函数)为L，它利用A(t-1)和数据x产生中间结果，另一个是聚合函数F，它用于把中间结果和A(t-1)结合生成A(t)。大部分机器学习算法都可以简化成为这种结构，例如随机梯度下降，坐标下降，MCMC，变分等。 看两个具体例子： 第一个是Lasso。它的最优化表达式可写为： 也可简化写成矩阵表达式 采用坐标下降迭代收敛表达式： 可进一步总结出更新函数?和聚合函数F： 另一个例子是主题模型。它的最优化表达式可写为： 它的参数推导通常借助于变分或者Gibbs取样。以后者为例： 其中-=，+=代表自减，自增操作。更新函数?分为两阶段执行：1) 在所有文档的词上执行上述取样操作；2) 输出A(t)，形式暂略，聚合函数F形式为简单的识别函数(identify function)。 以上两个例子，对于算法不熟悉的可能难以理解，这里仅列出大致的优化结果，其目的在于阐明机器学习算法的通用表达式。有了这些例子，我们为了就可以深入了解机器学习算法的特性，从而总结出执行大规模分布式程序时，跟传统分布式程序的区别。 比如一个传统的MapReduce程序---排序，框架首先把数据x_1,x_2,...,x_n随机分发到M个Mapper，这些Mapper随后把元素哈希成为键值对(h(x_i),x_i)，其中h是order-preserving的，就是说如果x<> 额外的复杂努力，来提供容错，比如基于磁盘的快照，并且跟任务调度结合起来，这里边的工程设计十分复杂。 对于机器学习程序来说，需要对中间结果的错误更加健壮。如果一些参数在?函数执行时没有正确得出，也不妨碍整个程序的收敛性。例如SGD程序，不论深度学习，矩阵分解，还是逻辑回归，都会经常使用。在运行时，比如每次迭代后增加小的随机错误ε，这样A(t)=A(t)+ε，即便如此，收敛仍然能够保证，因为SGD总能向正确的方向更新参数(根据梯度)。机器学习算法的这种特性能够很大的影响分布式框架的设计——系统并不需要完美地确保所有任务无误运行，也无须确保机器之间通信正确，乃至从错误中恢复。当资源有限时(比如机器之间带宽有限)，简易容错设计能够让系统更简单和高效。这是大规模机器学习问题跟传统分布式问题的第一点重要区别。 然而，另一方面，机器学习算法却比传统的MapReduce程序拥有更加复杂的结构依赖，而这些依赖并不能够从优化的目标函数L和更新函数?容易得出。例如在MapReduce排序中，Reducer等待Mapper结束，这种依赖是确定性的，而在Lasso中，似乎从前面更新函数?的表达式里能够得出容易并行的结论，然而实际并非如此，因为第j个模型参数A_j，它的更新实际上可能依赖所有其他A_k，不正确地并行执行可能会影响程序执行的正确性。 上图中展示了数据并行和模型并行的区别。在机器学习中，这两种并行是互补的，同时也是非对称的，意思是：数据并行可以应用到任何对数据采样具备独立同分布假设的机器学习算法中，包含深度学习，Lasso，主题模型等。相比之下，模型并行需要仔细对待，因为模型参数A_j并不总是具备独立同分布假设，例如前边提到的Lasso。下面从更广义的角度来看两者： 在数据并行中，数据x被划分到不同计算节点，如果更新函数?可以表达成对各节点计算结果的和，那么就可以应用数据并行。例如把Lasso改写为数据并行模式： 在模型并行中，模型A被划分到不同计算节点后，还需要引入一个调度函数S，用来限制更新函数?只工作在模型参数的子集上，避免不同节点都来更新相同的参数。把Lasso以模型并行的方式改写： 这里调度函数S_p,(t-1)对于节点p在每次迭代时只更新固定子集的参数。由于每个节点操作的模型参数都会依赖于其他节点的参数，并行更新参数会得出跟顺序更新不同的结果，这会导致更慢地收敛，因此对于调度器来说，不能浪费计算资源去试图并行执行相互依赖的任务，而应寻找到不依赖的子任务让它们并行运行。因此对于调度器来说，应当寻找到依赖成立的边界条件， 再来看个在LDA中通过综合数据并行和模型并行实现大规模主题模型的例子：
在图中，有3个计算节点并行的在每次迭代中只操作一个数据和参数的子集z_1，z_2，z_3，当完成后进行下一次迭代时，更换相应子集，以此类推，实现大规模并行主题模型。 这是大规模机器学习问题和传统分布式问题的第二点重要区别。 第三个重要区别是非均匀性收敛。MapReduce排序把数据分发到不同节点执行，各节点的任务和负载基本上是均衡的，然而对于机器学习问题来说，数十亿，甚至更多的参数能够以不同的迭代数目收敛，有的2-3轮迭代即可，有的则需要上百次。 第四个重要特性在于紧凑更新。例如上面的Lasso和LDA，更新函数?只会涉及到一小部分模型参数，这是由数据的稀疏本质决定的。另一个例子是深度学习，模型参数A是矩阵，更新函数?可以只涉及小的向量结构。在设计大规模机器学习框架时考虑到这种紧凑更新的特性，可以大大减少存储，计算，以及网络的开销。 因此为了能够让机器学习程序高效执行，需要做三件事情： 1 决定如何更好的切分成多个任务，究竟采用数据并行，还是模型并行，或者混合方案。 2 决定如何调度子任务。 3 均衡各节点的负载。 这些问题在传统MapReduce类任务框架里已经解决得很好，但对于机器学习算法来说则是挑战。调度器需要能够很好的判定模型参数依赖的边界条件，这是个算法相关的问题，例如Lasso和LDA的条件就不一样。在获取边界条件之后，需要通过调度来平衡节点负载，传统分布式任务的BSP肯定是无法胜任该工作，因为机器学习任务是一种有限异步(非完全异步)，完全同步等待就会造成大量浪费。在机器学习中，需要一种有限异步的同步原语，称为SSP，SSP的背景材料本号之前在参数服务器的介绍中已经提及，点击原文可以阅读参数服务器的背景材料。 Eric Xing教授在其Petuum系统里完整地提出了解决分布式机器问题的框架，以参数服务器和并行，调度为核心，称之为SAP(Structure Aware Parallelization)，结构感知的并行计算。SAP提供类似MapReduce一样的简易编程抽象接口，所有机器学习程序只需要实现3个函数： 1 schedule，用来确定更新的模型参数以及提供参数依赖检查 2 push，用来执行?更新函数 3 pull，用来执行F聚合函数 其中，push和pull就是参数服务器的原语。根据文献[1]提到的证明，SAP基本上可以做到分布式机器学习算法的理想抽象，据此实现的算法，可以有甚至不止一个数量级的性能提升。在Petuum项目中，Strads调度器就实现了SAP抽象，并应用到若干典型算法，包含Lasso，矩阵分解，还有主题模型等。 那么，Petuum框架和Strads调度器，应用于深度学习时，相比已有的方案有哪些特色呢？Petuum有一个集成Caffe的工作叫做Poseidon，利用SSP和数据并行，Poseidon可以在普通网络组成的GPU集群上实现大规模深度集群，而无须Infiniband和RDMA。更进一步的对比，尤其是和最新版支持分布式训练的Tensorflow，以及MXNet，本号将在接下来给出对比和分析。 [1] Strategies and Principles of Distributed Machine Learning on Big DataEric P. Xing, Qirong Ho, Pengtao Xie, Wei Dai.arXiv:1512.09295 (2015) |
|
|
