参考链接： 机器学习生命周期
引自:http://www.ccf.org.cn/c/2017-08-16/603621.shtml
Angel: a new large-scale machine learning system
ANGEL：一个新型的分布式机器学习系统
阅读量：
36
崔斌,余乐乐
收藏本文
PDF在线浏览
下载本文
混合并行分布式机器学习异构感知SGD算法
引言
当前，人工智能在多个领域的强势崛起，让人们领略到人工智能技术的巨大潜力。在未来，人工智能技术还将会改变包括金融、医疗、通信、教育、交通、能源在内的所有行业[1]。现阶段的人工智能主要依赖机器学习技术和大数据，通过对海量数据进行抽象表示和建模，来帮助人们做出判断和决策。
机器学习模型的求解方法大致分为两类。频率派方法将模型求解定义为一个优化问题，往往使用梯度下降(Gradient Descent)方法进行求解；贝叶斯学派的模型计算则通常使用蒙特卡罗(Monte Carlo)随机抽样方法对模型参数进行估计。而这两类方法在目前的机器学习系统(Spark[2]，Petuum[4]，TensorFlow[5])中，都没能得到良好的支持。Spark由于缺乏对共享参数的高效更新和同步操作，因而在面临高维度的模型时性能下降；Petuum缺乏对数据的高效管理，其设计的模型求解算法没有考虑生产环境中的异构信息；TensorFlow则忽略了数据的稀疏性，缺乏对分布式的有效支持。
因此，我们开发了一个新型的分布式机器学习系统——Angel[6,7]。它采用混合并行的方式加速蒙特卡罗随机抽样方法的收敛速度，并通过感知真实环境中的异构信息来提升分布式随机梯度下降算法(SGD)的收敛速度。
Angel系统概述
当计算节点数目增加时，已有的参数服务器系统都无法展现出良好的扩展性，因为它们只支持单独的并行策略。数据并行可以提供较好的扩展性，但由于不同计算节点之间会产生模型的更新冲突，因而降低了算法的收敛速度；模型并行通过对不同的节点计算进行调度，避免了不同的节点对同一个维度的模型进行更新，加快了算法的收敛速度，但每次迭代都需要进行全局同步操作，造成一定的性能损失。为了解决这个问题，Angel将数据并行与模型并行有效地结合起来，支持混合并行策略来加速机器学习算法的收敛速度，这样可以同时利用数据并行方法的高扩展性和模型并行方法的收敛速度，达到更好的训练性能。混合并行方法在常用的贝叶斯模型（如话题模型）中能够得到较大的性能提升。
真实的生产环境往往存在资源竞争，导致不同计算节点的计算速度不同，从而产生掉队者问题。为了降低掉队者节点对机器学习算法收敛速度造成的影响，我们设计了异构感知随机梯度下降算法DYNSGD(Dynamic Learning Rate SGD)，根据节点的运行速度动态地调整节点的学习率。对于掉队者节点，给它设置一个较小的权重，从而降低其对全局收敛速度的影响，加快对优化问题的求解速度。我们通过理论证明了DYNSGD算法比已有的分布式随机梯度下降算法具有更快的收敛速度。
目前，Angel已经应用于具有大数据大规模挑战的机器学习任务上，包括广告推荐、特征抽取和文本挖掘等等。Angel支持多种常用的机器学习算法，包括使用梯度下降求解的逻辑回归(Logistic Regression, LR)、线性回归(Linear Regression, LR)、支持向量机(SVM)、K-平均算法(KMeans)、矩阵分解(MF)、树模型(GBDT)以及使用蒙特卡罗抽样求解的话题模型(LDA)。我们使用多种机器学习模型将Angel和Petuum、Spark、TensorFlow以及XGBoost[8]在真实的集群环境中进行了详尽的实验对比，证明Angel在多种机器学习算法上都可以获得更好的性能。
Angel系统架构与算法设计
Angel的系统设计架构如图1所示，主要包括四个组件：客户端(Client)、主控节点(Master)、计算节点(Worker)和存储节点(Server)。
图1 Angel系统架构
1. 客户端：任务启动的入口。用户通过使用Angel的API接口编写程序（目前Angel支持的语言包括Java和Scala），通过客户端将任务提交到YARN[3]。客户端包含用户对于任务的配置信息和模型参数的定义，以及模型同步协议的选择。
2. 主控节点：由YARN启动的进程，用来管理Angel任务的生命周期，包括向YARN资源管理器申请资源，启动计算节点和存储节点，停止任务等等。除此之外，主控节点上维护了数据分区、模型分区、任务时钟以及存储节点的SNAPSHOT信息，掌控任务的运行状态，并通过WEB界面向用户进行展示，方便用户观测任务的进行和调试。主控节点定时将全局信息写入分布式文件系统HDFS中，用于在错误发生时进行任务恢复。
3. 存储节点：作为模型参数的分布式内存存储系统，向所有计算节点维护一份全局的模型参数。在任务提交阶段或任务运行阶段，模型矩阵通过划分形成多个模型分区，每个存储节点维护一个或者多个分区。存储节点上支持存储各种类型的模型矩阵，包括稠密、稀疏、浮点或整型，用于满足各种机器学习算法的需求。模型参数记录了机器学习算法的收敛进程，因此存储节点会定时将模型参数写入HDFS，用于错误恢复。
4. 计算节点：用于计算任务的进程。每个计算节点通过从HDFS读取训练数据，并且从存储节点上读取模型参数来进行模型训练。当计算节点完成一轮算法的计算时，将模型的更新发送到存储节点上进行模型同步。计算节点中提供了三种数据存储的方式，用于保证任务可以在不同资源条件下完成训练。
这四种节点构成了Angel系统的组成架构，其中客户端和主控节点只有一个，而计算节点和存储节点的个数可由用户根据任务的数据量和模型复杂程度自行设置。
混合并行
贝叶斯模型的求解方法常常使用马尔可夫蒙特卡罗(MCMC)随机采用方法来对模型的后验分布进行估计。常用的MCMC方法（如吉布斯采样）是串行的方法，其分布式的变种目前有两种，即数据并行和模型并行。
我们以贝叶斯模型中常用的话题模型(LDA)[10]为例来描述这两种并行方式（见图2）。话题模型中词-话题(word-topic)模型矩阵需要在多个计算节点中共享。在数据并行中，每个计算节点维护一份独立的模型矩阵，每个节点独立进行运算，节点之间没有太多等待和约束，因而可以获得较高的并行度，但同时也造成了模型更新冲突，降低了算法的收敛速度；模型并行则加强了计算节点之间的约束，保证同一个时刻不同的计算节点在更新不同的模型维度，由此避免了模型更新冲突，加速了收敛，但同时带来了调度的同步开销。
图2 数据并行与模型并行
因此，Angel采用了混合并行的策略，将计算节点划分成多个节点组，在组内做模型并行，在组间做数据并行，在减少参数更新冲突的同时，获得较高的并发度，使得机器学习算法可以扩展到大规模的集群之中。
组间数据并行：Angel根据计算节点的数目，将数据自动划分并分配到各个节点组中，每个节点组根据自己的训练数据进行参数的更新和计算。组间数据并行确保Angel可以获得较高的并发度。
组内模型并行：Angel将多个计算节点组成一个节点组，在节点组内选取一个协调节点，用于调度节点组内计算节点之间的执行方式。在同一个时间分片，不同节点可以并行更新不同维度的模型，避免在进行模型更新时产生冲突，从而加速模型算法的收敛速度。
异构感知随机梯度下降算法DYNSGD
梯度下降方法是求解优化问题的常用方法，而SGD算法由于具有快速的收敛速度和较小的内存消耗，是目前主流的分布式机器学习模型求解方法。为了降低SGD算法在分布式环境中的等待时间，目前的参数服务器系统提出了有限异步协议随机梯度下降算法(Stale Synchronous Parallel SGD, SSPSGD)[9]。但是SSPSGD算法的问题在于它没有考虑在异构环境下计算节点产生的更新具有滞后性，而直接将计算节点的更新累加到全局的模型参数，当全局参数已经接近最优点时，来自掉队者的更新将会导致全局参数远离最优点。在异构环境中，由于节点之间的性能差异较大，该问题将会更加严重从而导致算法不收敛。
因此我们提出了DYNSGD算法，给每一个计算节点的更新赋予一个staleness值，该staleness值定义了一个更新相对于全局参数的滞后程度。一般来说，越慢的计算节点产生的更新的staleness值越大。为了减少慢节点产生的更新对全局参数造成的影响，DYNSGD算法给每个更新赋予不同的学习率，对于慢节点产生的更新，其学习率会较小，对于快节点的更新，其学习率则会较大。
图3给出了DYNSGD算法的一个例子，u1、u2、u3都是从同一个全局参数副本计算得到的更新，当u1被计算节点推送到参数服务器时，其staleness=1，则学习率为1；当u2到达时，其staleness=2，因为已经有一个更新到达了，这时我们需要将u2的学习率设为1/2，因为u1已经被累加到全局参数上了，所以需要将u1的更新进行修正；当u3到达时，其staleness=3，学习率为1/3，这时我们需要修正u1和u2的更新。
与SSPSGD算法相比，DYNSGD算法避免了直接将更新累加到全局参数上，通过对不同延迟的更新使用不同的学习率，从而减少了延迟更新对收敛带来的影响。
图3 DYNSGD算法示例
参数同步、数据管理与容错
在参数获取时，Angel通过流式的方式获取模型矩阵的参数，这样可以将计算操作和网络操作重合起来，降低网络延迟；同时，由于训练数据往往具有稀疏性，每个计算节点上可能需要的参数只是全部参数的一部分，Angel利用这种数据稀疏性对每个计算节点建立维度索引，减少获取参数时的网络开销。此外，Angel采用异步执行的方式进行参数的更新操作，将梯度计算与参数更新操作并行化，减少参数更新的开销。
在对大规模数据进行训练的过程中，训练数据的清洗和存储是一个很大的开销。Angel可以自动地对训练数据进行划分，根据计算节点的数目将训练自动地划分成多个均衡的分区，从而避免由于负载不均衡造成的掉队者问题。Angel还可以对训练数据进行自动化管理，将训练数据存储在内存、磁盘或在内存和磁盘中进行混合存储。灵活的存储方式可以供用户自由选择，从而减少了计算节点的内存开销。
Angel还提供了对主控节点、存储节点和计算节点的高效容错机制，从而保证在错误发生时任务可以继续运行。由于客户端负载很低，并不影响任务的进行，Angel没有对客户端的错误进行处理。
实验对比
我们使用真实的数据集在腾讯公司的集群环境中进行了测试，并对四种算法进行了对比，包括逻辑回归(LR)、矩阵分解(MF)、GBDT、KMeans和话题模型(LDA)。其中LR、MF、GBDT和KMeans都使用SGD进行求解，而LDA使用MCMC进行求解。我们对比的系统包括Spark，Petuum和TensorFlow，在GBDT算法的对比中，我们将Angel跟XGBoost进行了对比。
实验中使用的数据集信息如表1所示。我们使用了公开的数据集，包括Kdd2010、Netflix和PubMED；还使用了腾讯公司业务中真实的数据集Gender，用于进行用户性别的预测。
表1 实验使用的数据集信息
逻辑回归：在LR算法上，Angel具有比其他三个系统更快的收敛速度（见图4）。Spark需要在每轮迭代时进行模型参数的广播和汇总，严重影响了性能；Petuum采用了SSPSGD算法，需要在一次迭代中间进行多次的模型同步才能保证模型收敛，多余的模型同步操作影响了性能；TensorFlow对张量(tensor)大小的限制，也需要在一次迭代过程中进行多次模型同步。
图4 逻辑回归
KMeans：我们在PubMED和Kdd2010这两个数据集上对KMeans算法进行测试，计算Spark、Petuum和Angel达到同一个目标值的时间（见图5）。在PubMED数据集上，Angel比Petuum更快，并且比Spark快2倍；在Kdd2010数据集上，Angel的性能是Spark的8倍左右，而Petuum，由于只能将参数矩阵按照行进行划分，因而无法完成对高维度数据集的计算。
图5 KMeans
GBDT：图6给出了在GBDT算法上的性能对比。由于Angel对GBDT进行了针对性的优化[12]，从而在高维的数据上性能更优。由于XGBoost使用了AllReduce的方式来进行参数的汇集操作，因而当特征的数目增加时，性能也会下降。当特征数是50K时，Angel的性能是XGBoost的1.11倍；当特征数是330K时，Angel的性能是XGBoost的2.55倍。同时，Angel的性能还是Spark的4.8~21倍。
图6 GBDT
矩阵分解：在矩阵分解模型上，我们使用交叉最小二乘法(Alternative Least Squares, ALS)来进行求解。图7给出Spark，Petuum和Angel在该算法上的性能对比，可以看出Angel的性能是Petuum的4倍，是Spark的1.3倍。
图7 矩阵分解
话题模型：图8给出了在话题模型上Petuum和Angel的性能对比。我们设定话题的个数为1000。达到同样的目标值时Angel的性能是Petuum的5倍左右，这是由于Angel对LDA会根据文本信息选择最好的采样器[11]，并且采用了混合并行的策略，而Petuum只有模型并行。对于PubMED数据集，Spark会因为产生太多的网络通信而导致性能特别差。
图8 话题模型
实际应用
目前Angel已经在腾讯公司的推荐业务和数据分析业务中得到了实际的应用，使用范围包括视频推荐，兴趣构建和广告推荐等。
视频推荐：在腾讯视频的业务中，需要向用户推荐他可能喜欢的视频。通常使用的算法是逻辑回归。对于一个新的用户请求，我们通过逻辑回归模型计算出该用户对不同视频喜欢的概率，从而向他推荐他可能喜欢的视频。在实际的推荐业务中，我们使用Angel对1.7亿条训练样本进行逻辑回归的模型训练，模型维度达到2600万。相比于Spark，Angel的性能提升了10倍左右。
微信文章推送：微信的朋友圈和公众号有很多文章，我们会尝试帮助用户对文章进行筛选，给用户推荐并推送该用户可能喜欢的文章。我们采用L1正则化的逻辑回归进行微信文章的推荐工作，使用ADMM(Alternating Direction Method of Multipliers)逻辑回归算法对1亿条样本进行模型训练，模型维度达到1000万。相比于Spark，Angel的性能可以提升12倍。
用户兴趣构建：为了提升对用户的推荐效果，我们会使用话题模型来构建出用户的兴趣，并给物品打上标签。在实际业务中，对379万个物品和5亿个用户的数据进行训练，用户行为总数达到200亿，模型的维度达到40亿。相比于Spark，Angel的性能提升了8倍。
总结与展望
本文介绍了一个新型的分布式机器学习系统——Angel，用于对大规模的机器学习任务进行模型求解。Angel使用混合并行加速了MCMC算法的收敛速度，提出了异构感知的DYNSGD算法加速了分布式SGD算法的速度，因此Angel可以在大部分机器学习模型上获得良好的模型求解性能。目前Angel已经全面开源1，并且打造出强大的参数服务器能力来扩展Spark进行大规模模型的训练，建立了Spark-on-Angel系统。
之后我们会重点加强深度学习和在线学习的研制工作。利用Angel的高维模型训练能力，为深度学习系统和流式处理系统提供分布式的功能并且提高其分布式模型训练的性能。■
注释：
1 https://github.com/Tencent/angel
参考文献：
[1] 李航.对于AI，我们应该期待什么？[J].中国计算机学会通讯, 2016,12(11): 50-54.
[2] Zaharia M, Chowdhury M, Franklin M J, et al. Spark: cluster computing with working sets[C]//Proceedings of the 2nd USENIX conference on Hot topics in cloud computing. USENIX Association, 2010:10-10.
[3] Vavilapalli V K, Murthy A C, Douglas C, et al. Apache Hadoop YARN: yet another resource negotiator[C]//Proceedings of the 4th annual Symposium on Cloud Computing. ACM Press, 2013:5.
[4] Xing E P, Ho Q, Dai W, et al. Petuum: A New Platform for Distributed Machine Learning on Big Data[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2015: 1335-1344.
[5] Abadi M, Barham P, Chen J, et al. TensorFlow: a system for large-scale machine learning[C]//Proceedings of the 12th USENIX conference on Operating Systems Design and Implementation. USENIX Association, 2016: 265-283.
[6] Jiang J, Cui B, Zhang C, et al. Heterogeneity-aware Distributed Parameter Servers[C]//Proceedings of the 2017 ACM International Conference on Management of Data. ACM Press, 2017:463-478.
[7] Jiang J, Yu L, Jiang J, et al. Angel: A New Large-scale Machine Learning System[C]. NSR’2017.
[8] Chen T, Guestrin C. XGBoost: A Scalable Tree Boosting System[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2016: 785-794.
[9] Ho Q, Cipar J, Cui H, et al. More effective distributed ml via a stale synchronous parallel parameter server[C]//Advances in Neural Information Process Systems. 2013: 1223-1231.
[10] Blei D M, Ng A Y, Jordan M I. Latent Dirichlet Allocation[J]. The Journal of Machine Learning Research, 2003(3): 993-1022.
[11] Yu L, Zhang C, Shao Y, et al. LDA*: A Robust and Large-scale Topic Modeling System[J]. Proceedings of the VLDB Endowment, 2017(10):11.
[12] Jiang J, Jiang J, Cui B, et al. TencentBoost: A Gradient Boosting Tree System with Parameter Server[C]//Proceedings of 2017 IEEE 33rd International Conference on Data Engineering. IEEE, 2017.
