2. 国防科学技术大学 计算机学院, 长沙 410073
2. College of Computer, National University of Defense Technology, Changsha Hunan 410073, China
在大数据时代，数据已经成为重要的资源。面对海量的数据，如何实现有效的处理和分析非常重要。机器学习理论旨在设计一些让计算机自动“学习”的算法，使得计算机能够从数据中自动获得规律，并利用规律对未知数据进行预测。常见的机器学习算法可分为有监督学习、无监督学习、半监督学习算法等几类，例如回归分析和统计分类等属于典型的有监督学习算法，聚类等类属于无监督学习算法。机器学习理论对数据处理具有黑盒特点，具有普遍的适应性，被广泛应用于数据挖掘、计算机视觉、自然语言处理等领域。
典型的机器学习系统涉及样本集和模型参数数据。样本是指机器学习系统处理的单个数据项，一般是一个多属性的记录，可用x=(x1,x2,…,xp)表示，其中p是样本的特征维度，xi表示样本x的单个特征值。样本集是所有单个样本组成的集合，常作为机器学习系统的输入数据。模型是指机器学习系统通过样本集学习到的知识的表示，它由算法逻辑和一些必要的参数组成。模型参数一般可表示为向量或矩阵，参数个数和维度由具体的机器学习算法、样本特征维度等决定。机器学习系统的目标是通过优化参数，使得模型尽量反映样本的规律，同时利用模型对新样本进行预测。例如，通常有监督的机器学习的优化目标函数可表示为式(1) ，其中xi,yi为第i个样本，θ为模型参数。
| $\mathop {\arg \max }\limits_\theta = L\left( {\left\{ {{\mathit{\boldsymbol{x}}_i},{\mathit{\boldsymbol{y}}_i}} \right\}_{i = 1}^N;\mathit{\boldsymbol{\theta }}} \right) + \mathit{\Omega }\left( \mathit{\boldsymbol{\theta }} \right)$ | (1) |
机器学习系统一般通过迭代训练方式优化模型参数。算法1为机器学习参数训练过程，每轮迭代以样本集和上轮迭代的模型参数为输入，通过优化算法计算出新的模型参数。迭代训练通常需要多次进行，直到模型满足收敛条件。在机器学习系统中，样本集和模型通常独立存储，迭代训练一般以样本为中心，由模型提供参数。每轮迭代的参数交互过程如图 1所示，可分为三个步骤：1) 从模型中获取参数；2) 用样本集训练新的参数；3) 将训练结果更新至模型。
|
图 1 机器学习系统体系结构 Figure 1 Machine learning system architecture |
算法1 机器学习参数训练。
输入：样本集D。
输出：模型参数θ。
1) for t = 1 to T：
2) Do Things
3) θt+1=g(θt,Δfθ(D))
4) Do Other Things
面对大规模的机器学习任务，单机系统因其存储和计算能力限制无法胜任，于是，人们使用分布式系统进行加速。分布式机器学习系统基于机器学习的并行算法实现，虽然算法确保了系统运行结果正确性，但是系统在设计和实现上普遍面临以下三方面问题：
1) 大规模的样本集。随着互联网的快速发展，数据的产生量以指数速度增长，每天将有大量的新数据涌现。在大规模的机器学习任务中，所需要处理的样本集规模往往非常庞大。例如，著名网络爬虫Clueweb 2012所包含网页数量超过7亿，其存储高达27 TB的文本数据，图片分享网站Flickr、Instagram处理图片数量高达百亿级别，图片存储量达到TB级别[1]。大规模的样本集给分布式机器学习系统带来巨大存储和计算压力。
2) 大规模的模型。在大型的机器学习任务中，如主题模型、人工神经网络等机器学习算法模型规模非常庞大。例如，用于新闻分析的主题模型，其参数数量可达到百万级别[2]；用于图像处理的Google Brain，其参数规模可达10亿级别[3]。如何存储大量的模型参数，高效地进行参数训练，是当前分布式机器学习系统所面临的主要挑战之一。
3) 大量的网络通信。在分布式机器学习系统中，样本训练节点和模型参数存储节点间的参数交互产生网络通信，当模型参数众多、参数更新频繁时，集群节点网络通信量非常庞大，甚至严重影响系统运行效率。
对于大规模问题，分布式并行处理通常是有效的解决方法。依据样本集和模型的存储方式，分布式机器学习系统可分为数据并行、模型并行、数据并行+模型并行三种体系结构。本文接下来从分布式机器学习系统的体系结构、网络通信及同步方式等方面介绍当前系统应对以上三方面挑战的方法。
数据并行 数据并行体系结构图 2所示，样本集被分散在集群各个节点上，每个节点负责训练自己拥有的那部分样本数据，节点通过网络从模型端获取训练所需要的参数，训练完毕后通过网络将结果更新至模型。
|
图 2 数据并行体系结构 Figure 2 Data parallel architecture |
分布式文件系统为数据并行提供有效支持，如Hadoop文件系统(Hadoop File System,HDFS)和分布式弹性数据集(Resilient Distributed Dataset,RDD)为用户透明提供样本集分布式存储功能，提供良好的可靠性和扩展性，为构建其上的机器学习系统带来便利。Mahout[4]是基于Hadoop的分布式机器学习框架，使用HDFS存储样本集数据。Spark ML[5]是构建在Spark之上的机器学习组件，使用RDD管理样本集数据。对于没有分布式文件系统支持的机器学习系统，通常难以实现样本集自动分布，难以确保数据可靠性和实现可扩展性。微软的分布式机器学习框架(Distributed Machine Learning Toolkit,DMLT)没有分布式文件系统直接支持，它需要用户预先将样本集划分为多个文件，分布在集群各个节点上。
把计算往数据迁移实现分布式训练。数据并行将训练任务往样本集迁移，确保计算时样本数据的本地性。例如Mahout和Spark ML的任务调度器通常将任务分配给拥有数据的节点，充分利用数据本地性[4-5]。对于DMLT等没有任务调度器支持的分布式机器学习系统，用户程序须确保训练进程与样本数据处于同一节点，实现“计算往数据迁移”。
模型并行 数据并行体系结构在模型端处存在存储和访问瓶颈，仅能适用于K-means、线性回归等模型较小的机器学习应用。为了应对大规模模型，人们提出如图 3所示的模型并行体系结构。模型并行将模型参数分布存储于集群之中，各节点以网络或共享文件系统方式访问样本集。由于样本集端限制，模型并行适合构建模型参数量巨大而样本集规模较小的机器学习系统。
|
图 3 模型并行体系结构 Figure 3 Model parallel architecture |
数据并行+模型并行 数据并行+模型并行系统结构如图 4所示，与数据并行或模型并行不同，它的样本集与模型都分布于集群之中，两类节点之间通过网络通信。数据并行+模型并行适应于大规模的样本集和大量模型参数场景，是当今大型分布式机器学习系统的主流结构。谷歌的主题模型系统PLDA+采用数据并行+模型并行结构，它使用MPI进程管理模型分布式存储，响应来自训练进程的参数请求和更新消息[6]。Li等[7-8]使用参数服务器存储模型参数，参数服务器对外提供了统一的参数访问接口，提供高吞吐的参数请求和更新能力，实现良好的扩展性和容错性。
|
图 4 “数据并行+模型并行”体系结构 Figure 4 Data parallel + model parallel architecture |
网络通信 在“数据并行+模型并行”系统结构中，样本集和模型参数的分布式存储使得样本训练节点向参数存储节点的参数获取和更新操作分散于集群之中，避免了单机网络访问瓶颈。为了减少网络通信量，Petuum、PLDA+在样本训练节点建立参数本地缓存，相同的参数多次请求和更新被作用到本地缓存中，必要时再更新至模型[1, 6]。参数本地缓存有效地控制参数传输粒度，大幅减少网络的使用量。LightLDA使用稀疏向量方式传递参数，有效减少了网络通信量[2]。
同步方式 机器学习同步方式包含整体同步方式(Bulk Synchronous Parallel algorithm,BSP)[9]、弱同步方式(Stale Synchronous Parallel algorithm,SSP)[10]和异步并行方式(Asynchronous algorithm)等几类。BSP同步方式确保训练阶段各训练节点的模型参数一致性，但它需要同步等待，牺牲了迭代速度。SSP同步方式放宽了模型一致性约束，减少了同步等待时间。基于Hadoop和Spark的分布式机器学习系统采用BSP同步方式，Petuum机器学习平台采用SSP同步方式[1]。
另外，在机器学习系统中，为了减少训练过程中的计算量，抽取少量样本参与训练的随机优化方法被广泛使用，例如随机梯度下降方法等[11]，Online LDA使用online variational bayes优化方法[12]。
当今，分布式机器学习应用十分广泛，了解现有系统的设计思路和实现策略对于设计高效、易于扩展的分布式机器学习系统有着深远的意义。然而，由于机器学习算法众多、框架各异，要对各类型的算法框架作一个大而全的分析与考量并不实际。基于此，本文将以文本主题聚类模型这一拥有大规模样本集、大规模模型和大量的网络通信的典型机器学习算法为例，从样本集、模型和网络通信量三方面综合考虑，通过对经典的开源分布式系统进行实验和分析，展现它们的功能特点和存在的问题，以期揭示分布式机器学习系统内在规律和在处理大规模问题所面临的问题，并对设计大型分布式机器学习系统提出建议。
1 文本主题模型Blei等[13]首次提出了隐含狄利克雷分布(Latent Dirichlet Allocation,LDA)，它是一个处理离散数据的概率生成主题模型。例如，LDA可从文档语料库中得出语料库包含的主题，并将文档按主题进行分类。在LDA中，每篇文档被建模为基于K个隐含主题的多项式分布，而每个主题k为基于一个含义W个词的词汇表的多项式分布。在文本建模中，主题的概率清晰地表达了文本中蕴含的主题信息。相对于隐含语义分析(Latent Semantic Analysis,LSA)[14]和概率LSA(probabilistic LSA,pLSA)[15]，LDA实现了主题的隐含层理解，因此，LDA广泛应用于文本分析领域，如社交网络用户的兴趣挖掘、新闻个性推荐等。
与典型的机器学习系统一样，LDA系统涉及两种重要的数据——样本集和模型参数。在LDA中，样本集是经分词和词干化处理的文档集合，通常被表示为词频矩阵。模型描述主题在词上的分布，每个主题拥有一个W维的参数向量，用来统计该主题中每个词出现的次数。为了方便，在逻辑上和实现上通常将模型表示为词-主题矩阵，因而，将样本矩阵和模型矩阵分布式化是LDA分布式化的核心问题。LDA模型现存很多参数估计方法，典型地可归类为吉布斯采样和变分贝叶斯推理两类[16]。接下来介绍三个主流的LDA式开源实现——Spark LDA、PLDA+和LightLDA。
|
表 1 主流开源LDA系统 Table 1 Mainstream open source LDA system |
Spark机器学习组件(Spark Machine Learning,Spark ML)包含LDA的两个并行实现，依据它们的实现特征，本文分别记为GraphX LDA和Online LDA(两者合称为Spark LDA)。GraphX LDA基于Spark图计算框架(Spark GraphX)实现，将文档和词作为图的顶点，文档与词之间的关系作为图的边。GraphX LDA采用Collapsed Gibbs Sampling参数优化方法，其计算复杂度为O(k)，其中k为主题数目[13, 17]。GraphX LDA属于数据“并行+模型并行”体系结构，样本集和模型使用GraphX顶点RDD存储，利用RDD并行机制实现数据并行和模型并行，模型参数的获取和更新依赖GraphX消息通信实现。GraphX LDA在每轮迭代中，每篇文档的每个词需要获取模型参数并产生一个新的局部参数消息，所有参数消息将合并成新的模型。GraphX LDA属于BSP同步模型，实现了最细粒度的参数传输单元。
Online LDA基于Online Variational Bayes优化方法，它属于随机优化算法，每轮迭代时抽取少量文档进行训练，更新模型参数[17]。使用本地矩阵存储模型，参数请求和更新采用Spark的广播机制。Online LDA使用RDD存储样本集，利用RDD并行机制实现数据并行，但是，Online LDA使用Scala矩阵对象存储模型，模型参数请求和更新简单地使用广播和归约方式实现。与GraphX LDA一致，Online LDA也属于BSP同步模型。
谷歌PLDA+使用C++语言开发，其分布式机制由MPI实现。PLDA+同样采用Collapsed Gibbs Sampling优化方法，参数计算复杂度为O(k)，其中k为主题数目[6]。PLDA+属于“数据并行+模型并行”体系结构，它将MPI进程分为文档进程组和模型进程组。文档进程组存储样本集，每个进程从语料库中抽取部分文档作为本地的样本数据进行训练。模型进程组存储模型，每个进程存储部分模型，为文档进程提供参数服务。文档进行训练时与模型进程进行交互以获取和更新模型参数，但各文档进行之间无须同步，因而PLDA+属于异步并行模型(Asynchronous Parallel model)，文档进程不存在同步等待时间。不同于GraphX LDA细粒度的参数传输单元，PLDA+引入了本地参数缓存，对于相同的参数，文档进程只进行一次参数获取和更新，大幅减少参数传输次数。另外，PLDA+采用流水线方式训练文档词汇，前后词汇在参数获取、计算、更新步骤上重叠，减少了文档进程CPU和I/O空闲时间和参数存储空间。
LightLDA[2]同样使用C++语言开发，样本集的分布式机制由MPI进程实现，但与PLDA+不同的是，LightLDA使用参数服务器存储模型，并且使用复杂度为常数的Metropolis-Hasting参数优化方法。LightLDA中每台机器负责训练固定的语料库部分文档，仅需要部分模型参数，Petuum开源框架为LightLDA提供参数服务器功能，参数服务器的模型分区分布在集群训练节点上，通过定期地在训练节点轮转各模型分区，使训练节点以本地方式访问模型参数，极大地减少了网络开销[1-2]。另外，参数服务器使用稀疏向量存储模型参数，随着训练进行，模型参数逐渐趋于极度稀疏化，从而大量减少内存和网络的消耗。LightLDA属于“数据并行+模型并行”体系结构，属于SSP同步方式。
2 实验设计与分析LDA系统在运行时，集群物理资源消耗、模型收敛性能以及系统可扩展性是衡量LDA系统优劣的关键指标，本文依据这些指标为GraphX LDA、Online LDA、PLDA+和LightLDA设计了伪分布式实验和集群分布式实验。
伪分布式实验使用多线程方式在单机上模拟集群分布式。相对于集群分布式，伪分布式忽略机器间的网络通信开销，因而可视为不考虑网络通信延时的分布式系统。Spark的local执行模式为Spark LDA提供伪分布式条件，MPI程序的本地多进程执行模式为PLDA+和LightLDA提供伪分布式条件。伪分布式实验主要考察Spark LDA、PLDA+和LightLDA的内存、CPU消耗和收敛性能指标。实验固定语料库规模和训练参数，测试各系统内存和CPU使用量及系统收敛程度随迭代轮数和训练时间的变化。
集群分布式实验考察各系统应对大规模能力和可扩展性。实验固定语料库规模和集群资源，通过改变主题数目控制模型规模大小，测试GraphX LDA、Online LDA、PLDA+和LightLDA在最佳系统设置下的收敛时间、训练期间的网络通信总量和平均网络利用率。网络通信总量是指系统在训练期间集群各节点网络I/O的数据总量，它真实地反映了LDA系统在训练时的参数传输量。为了使结果更具有意义，实验使用网络通信总量与PUBMED语料库大小的比值衡量网络通信总量大小。平均网络速度是指LDA系统在训练期间集群各节点的平均网络速度，它反映了LDA系统对集群网络的利用率。
2.1 数据集本文实验使用NYTIMES和PUBMED两个语料库，它们的统计信息如表 2所示。
|
|
表 2 样本数据及统计信息 Table 2 Sample data and statistical information |
问题规模 为了衡量LDA系统的问题规模，这里明确一些相关指标：LDA系统的样本集是语料库，语料库加载后通常表示成大小为D*V的词频矩阵，文档数量和词汇数量通常用来衡量样本集规模。LDA系统的模型是一个大小为V*K的词汇-主题矩阵，K为主题数目，因此，文档数量D、词汇数量V和主题数目K是LDA系统所处理问题规模的主要指标。
2.2 实验设置集群分布式实验中各LDA系统运行在拥有20个节点的集群上，每个节点配置为：Intel Xeon E5-1620 4核8线程CPU，48 GB DDR3内存，10 Gb/s以太网，64 b Linux kernel 3.13.0 操作系统。伪分布式实验使用集群中单个节点。
Spark LDA使用Spark ML自带的LDA实现，软件环境为：Spark1.6.1/Scala 2.11.5，Hadoop 2.7.1，Java 1.8.0。PLDA+使用plda+源码包编译(https://storage.googleapis.com/google-code-archive-downloads/v2/code.google.com/plda/plda+_beta.tar.gz)，MPI版本为mpich-3.0.4，编译器为gcc 4.8.2。LightLDA使用LightLDA源码包(https://github.com/Microsoft/lightlda)编译，MPI版本为mpich-3.0.4，编译器为gcc 4.8.2。
Spark LDA和PLDA+和LightLDA的系统参数设置如表 3所示。
|
|
表 3 LDA系统设置 Table 3 LDA system settings |
训练参数 使用NYTIMES语料库作为样本集，LDA参数设置为：狄利克雷参数α=0.1,β=0.01，主题数目K = 100。
伪分布式实验下各LDA系统资源消耗结果如表 4所示，相对于PLDA+和LightLDA，GraphX LDA对系统CPU资源的利用率较低，该现象有两方面的原因：1) Spark使用BSP同步方式，由于各分区任务执行时间长短不一，同步时部分分区CPU空闲。2) Spark shuffle读写磁盘使得CPU利用率下降。在内存方面，Spark LDA的内存使用量大约为PLDA+和LightLDA的2~3倍。PLDA+的流水线训练方式减少了文档进程的参数存储量，LightLDA使用模型参数的稀疏向量存储方式同样也减少了内存消耗。另外，PLDA+、LightLDA基于MPI实现，参数更新通常就地修改(in-place)，而RDD具有保持元素不变特性，RDD更新通常需要写时复制(copy on write)。处理同一问题，Spark通常比MPI耗费更多的内存。
|
|
表 4 各LDA系统资源消耗 Table 4 Resource consumption of each LDA system |
LDA系统通常以模型的似然函数对数(Log LikeliHood,LLH)值衡量系统的收敛状况。为了增加可比性，实验使用收敛程度衡量各系统收敛状况，其计算方法如式(2) 所示。LLH初始为各系统训练前模型的LLH值，LLH收敛为系统收敛后模型的LLH值，LLH当前为当前迭代轮数的LLH值。可见，模型初始状态时的收敛程度值为0，模型收敛状态时的收敛程度值为1。
| $\text{收敛程度}=\frac{LL{{H}_{\text{当前}}}-LL{{H}_{\text{初始}}}}{LL{{H}_{\text{收敛}}}-LL{{H}_{\text{初始}}}}$ | (2) |
伪分布式实验从迭代轮数和训练时间两个角度考察GraphX LDA、Online LDA、PLDA+和LightLDA的收敛程度。从迭代轮数角度出发，忽略各系统的性能差异，单纯从样本集和模型的分布状况、参数传输粒度、同步方式等系统结构角度分析系统收敛性能，对系统结构设计具有重要的指导意义。从训练时间角度出发，可分析系统收敛速度快慢。
各系统收敛程度随迭代轮数变化趋势如图 5所示，GraphX LDA、PLDA+、LightLDA和Online LDA分别需要100、110、380和820轮迭代达到收敛状态。GraphX LDA、PLDA+、LightLDA使用同类的参数估计方法和相同的训练数据，本文从参数更新角度分析它们之间收敛性能差异。假如训练进程实时获取并更新模型参数，在单轮迭代中模型参数发生变化，使得训练进程先后获取同一参数的值不一致。本文用参数最大可能变化次数(MC)衡量训练节点在一轮迭代中获取到参数的一致性，MC值越小，训练节点所获取的参数越“一致”。GraphX LDA采用BSP方式，即MCGraphX = 0。PLDA+通过参数本地缓存使得文档进程训练词汇时只进行一次参数获取和更新，所有文档进程在训练时同时与模型交互，因而在单轮迭代中，模型的每个参数最大变化次数为文档进程数目，MCPLDA+ = 4。LightLDA在单轮迭代中，每篇文档的每个词产生一次参数获取和更新操作，因而LightLDA的参数最大变化次数是PUBMED语料库的词汇平均出现次数L/V，MCLightLDA = 5 231。MCGraphX ＜ MCPLDA+ ＜ MCLightLDA，可见，机器学习并行算法中，训练节点在一轮迭代中获取参数的“一致性”决定该轮迭代的收敛程度，“一致性”越强，收敛程度越高。
|
图 5 LDA系统收敛结构 Figure 5 LDA system convergence structure |
从另一方面考虑，训练节点在一轮迭代中获取参数的“一致性”越强，意味着将参数更新至模型的次数越少，训练节点需要在本地维护参数时间越长，需要的缓存空间相应越大。该理论从另一个方面解释了为什么GraphX LDA内存使用量最大。
Online LDA每轮迭代抽取少量文档进行训练，该随机优化降降低系统内存的使用量，但系统的收敛时间较长。
各系统的收敛程度随训练时间的变化趋势如图 6所示，LightLDA和PLDA+取得了较好的收敛效果。在前述分析中，LightLDA的随迭代轮数的收敛性能没GraphX LDA和PLDA+好，但它引入了参数服务器和复杂度更低的Metropolis-Hasting参数优化算法，大幅缩短单轮迭代时间(如图 7所示)，实现较快的收敛速度。GraphX LDA虽然用较少的迭代轮数达到收敛状态，但其收敛时间却远大于LightLDA和PLDA+，主要原因是GraphX LDA使用最细粒度的参数传输单元，训练期间大量的参数获取和更新操作，导致大量shuffle操作，影响了迭代速度。从图 8可看出，在相同实验规模下，GraphX LDA网络通信量最多。
|
图 6 LDA系统收敛速度 Figure 6 LDA system convergence rate |
|
图 7 LDA系统单轮迭代时间 Figure 7 Single round iteration time of LDA system |
|
图 8 LDA系统网络通信总量 Figure 8 Total network communication of LDA system |
各系统单轮迭代时间随迭代轮数的变化趋势如图 7所示，GraphX LDA经过30轮迭代后，迭代时间迅速增大，最后趋于稳定。通过分析节点状态，发现GraphX LDA运行30轮后，Spark耗尽节点内存，JVM频繁进行垃圾回收以维持系统继续运行，使得迭代时间变长。Online LDA和PLDA+在各轮迭代过程中迭代时间大体保持不变。而LightLDA随着训练进行，模型参数逐渐稀疏化，使得参数获取和更新开销降低，迭代时间逐步降低，当迭代轮数达到50后，LightLDA参数趋于极度稀疏化，迭代时间也趋于恒定。
2.4 集群分布式实验训练参数 使用PUBMED语料库作为样本集，LDA参数设置为：狄利克雷参数α=0.1,β=0.01，主题数目K作为变量，用来控制模型规模。
在集群分布式实验中，主题数目为100时，Online LDA系统出现多个节点内存溢出错误终止。可见，基于单纯数据并行体系结构(没有使用模型并行)的Online LDA不能有效应对大规模模型。当主题数目大于1 000时，GraphX LDA出现多节点内存溢出错误终止。可见，Spark LDA在应对大规模语料库时内存使用量较大，系统容易出现内存溢出错误。
GraphX LDA、PLDA+、LightLDA的网络通信总量随主题数目的变化趋势如图 8所示，GraphX LDA、PLDA+的通信总量随主题数目基本呈线性关系，而LightLDA的通信总量随主题数目基本呈亚线性关系。本文引言已述，典型机器学习系统网络通信主要由模型参数获取和更新产生，LDA系统的模型参数规模与主题数目成正比，因而，GraphX LDA、PLDA+系统的通信总量与主题数目呈线性关系。LightLDA由于使用稀疏方式存储参数，随着迭代训练进行，模型参数趋于稀疏化，使得网络通信量下降，所以它的通信总量与主题数目呈亚线性关系。
在相同主题数目下，GraphX LDA的网络通信总量大约为PLDA+的2.3倍，并且两者的网络通信总量远大于LightLDA。GraphX LDA采用细粒度的参数传输单元(每篇文档每个词)，导致大量网络通信。PLDA+使用本地参数缓存有效减少网络传输量。LightLDA在训练节点上轮转模型分区方式实现模型参数的本地获取，并且使用稀疏方式表示模型参数，大幅度减少了网络通信量。
GraphX LDA、PLDA+、LightLDA的收敛时间随主题数目的变化如图 9所示，各曲线变化趋势与图 8(a)大体相同，网络通信总量是影响系统收敛时间的关键因素。GraphX LDA、PLDA+的收敛时间随主题数目基本呈线性关系，在相同主题数目下，GraphX LDA的收敛时间大约为PLDA+的3倍。LightLDA的收敛时间远少于GraphX LDA、PLDA+，并且随主题数目的增速十分微小，体现了良好的收敛性能和可扩展能力。
|
图 9 LDA系统收敛时间 Figure 9 LDA system convergence time |
GraphX LDA、PLDA+、LightLDA的集群节点平均网络速度随主题数目的变化趋势如图 10所示，PLDA+和LightLDA随着模型增大，对网络的利用率逐步提升，GraphX LDA对集群网络的利用率随着主题数目增大反而下降。2.2节中已述，PLDA+以流水线方式实现参数的计算与通信重叠，主题数目达到1 000时，集群CPU资源耗尽，同时网络利用率也达到上限。GraphX LDA的对象序列化和shuffle读写磁盘成本随着主题数目增大而增大，使得网络利用率下降。
|
图 10 LDA系统平均网络速度 Figure 10 Average network speed of LDA system |
从伪分布式实验和集群分布式实验可以得出，Spark LDA在资源消耗、收敛性能、可扩展能力及应对大规模问题方面不如基于MPI实现的LightLDA与PLDA+好。Spark开销较大的shuffle通信机制和BSP同步方式使得Spark机器学习系统在处理大规模模型和网络通信的任务时，系统资源消耗过多，模型收敛速度过慢。然而，相对于基于MPI的机器学习系统，Spark机器学习系统具有容错性和易用性优势。在集群分布式实验中，中断集群中一个节点的网络服务测试系统容错性，PLDA+、LightLDA均异常终止，而GraphX LDA系统将异常节点的任务迁移至其他节点，使得任务继续执行。另外，Spark机器学习系统具有良好的生态系统，能利用Spark实现从样本集存储、样本预处理、样本训练到模型存储整套训练流程，易用性较好。
3 结语分布式器学习系统面临大规模样本集、大规模模型和大量的网络通信三方面挑战，本文从系统资源消耗、算法收敛性能和系统可扩展性三个方面对三个典型的开源分布式机器学习应用Spark LDA，PLDA+和LightLDA进行实验和分析。本研究发现相对于Spark LDA与PLDA+，LightLDA能更高效处理大规模的语料库，Spark LDA在语料库规模较大时内存使用量和网络通信量太大，容易出现内存溢出错误；PLDA+收敛速度较慢，扩展性及应对大规模问题能力不强。
实验揭示了分布式机器学习系统的一些现象：Spark机器学习系统在处理大规模模型和网络通信量的任务时，由于Spark shuffle机制及基于BSP的同步机制，导致算法迭代周期过长，模型收敛速度较慢，但其在容错性和易用性方面具有优势；参数服务器能有效提升分布式机器学习系统处理大规模模型的能力；集群间频繁且大规模的网络通信对系统运行效率影响较大，通过对模型参数进行本地缓存、用稀疏存储表示能有效降低网络开销，提升运行效率。
实验发现，样本数据的分区策略对系统的收敛性能和资源消耗有一定影响，本课题接下来将深入探究各系统在不同的样本分区策略、不同数量的训练进程下的收敛性能及可扩展性能。
| [1] | XING E P, HO Q, DAI W, et al. Petuum:a new platform for distributed machine learning on big data[J]. IEEE Transactions on Big Data, 2015, 1 (2) : 49-67. doi: 10.1109/TBDATA.2015.2472014 |
| [2] | YUAN J, GAO F, HO Q, et al. LightLDA:big topic models on modest computer clusters[C]//Proceedings of the 24th International Conference on World Wide Web. Republic and Canton of Geneva, Switzerland:International World Wide Web Conferences Steering Committee, 2015:1351-1361. |
| [3] | DEAN J, CORRADO G S, MONGA R, et al. Large scale distributed deep networks[EB/OL].[2016-03-08]. http://robotics.stanford.edu/~ang/papers-tofile/large_deep_networks_nips2012.pdf. |
| [4] | TIWARY C. Learning Apache Mahout[M]. Birmingham, UK: Packt Publishing Limited, 2015 : 5 -23. |
| [5] | MENG X, BRADLEY J, YUVAZ B, et al. MLlib:machine learning in Apache spark[J]. Journal of Machine Learning Research, 2016, 17 (34) : 1-7. |
| [6] | LIU Z, ZHANG Y, CHANG E Y, et al. PLDA+:parallel latent Dirichlet allocation with data placement and pipeline processing[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2 (3) : 389-396. |
| [7] | LI M, ZHOU L, YANG Z, et al. Parameter server for distributed machine learning[EB/OL].[2016-02-03]. http://www-cgi.cs.cmu.edu/~muli/file/ps.pdf. |
| [8] | LI M, ANDERSEN D G, PARK J W, et al. Scaling distributed machine learning with the parameter server[C]//Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA:USENIX Association, 2014:583-598. |
| [9] | GERBESSIOTIS A V, VALIANT L G. Direct bulk-synchronous parallel algorithms[J]. Journal of Parallel and Distributed Computing, 1994, 22 (2) : 251-267. doi: 10.1006/jpdc.1994.1085 |
| [10] | HO Q, CIPAR J, CUI H, et al. More effective distributed ML via a stale synchronous parallel parameter server[J]. Advances in Neural Information Processing Systems, 2013, 2013 : 1223-1231. |
| [11] | BOTTOU L. Large-scale machine learning with stochastic gradient descent[M]//Proceedings of COMPSTAT'2010. Berlin:Springer, 2010:177-186. |
| [12] | HOFFMAN M D, BLEI D M, BACH F. Online learning for latent Dirichlet allocation[EB/OL].[2016-02-11]. http://people.ee.duke.edu/~lcarin/HoffmanBleiBach2010b.pdf. |
| [13] | BLEI D M, NG A Y, JORDAN M I. Latent Dirichlet allocation[J]. Journal of Machine Learning Research, 2003, 3 : 993-1022. |
| [14] | DUMAIS S T. Latent semantic analysis[J]. Annual Review of Information Science and Technology, 2004, 38 (1) : 188-230. |
| [15] | HOFMANN T. Probabilistic latent semantic analysis[C]//Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence. San Francisco, CA:Morgan Kaufmann Publishers, 1999:289-296. |
| [16] | HEINRICH G. Parameter estimation for text analysis[EB/OL].[2016-03-11]. http://xueshu.baidu.com/s?wd=paperuri%3A%2855e8317b50e8bbb9f73d3a216c428eb3%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3DAE05C3DD1ABBF2752A764EA48EAF0497%3Fdoi%3D10.1.1.149.1327%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=885567970698054705. |
| [17] | ASUNCION A, WELLING M, SMYTH P, et al. On smoothing and inference for topic models[C]//Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. Arlington, Virginia:AUAI Press, 2009:27-34. |
| [18] | 石晶, 范猛, 李万龙. 基于LDA模型的主题分析[J]. 自动化学报, 2009, 35 (12) : 1586-1592. ( SHI J, FAN M, LI W L. Topic analysis based on LDA model[J]. Acta Automatica Sinica, 2009, 35 (12) : 1586-1592. ) |