腾讯LDA.docx

腾讯LDA.docx

《腾讯LDA.docx》由会员分享，可在线阅读，更多相关《腾讯LDA.docx（12页珍藏版）》请在冰点文库上搜索。

腾讯LDA

2.1主题模型的“三个过程”

主题模型一般包含了三个重要的过程：

生成过程、训练过程以及在线推断。

生成过程定义了模型的假设以及具体的物理含义，训练过程定义了怎样由训练数据学习得出模型，在线推断定义了怎样应用模型。

下面分别进行简要介绍。

一般来说，主题模型是一种生成模型（生成模型可以直观的理解为给定模型，可以生成训练样本）。

给定模型，其生成过程如图11：

▪模型有2个主题，主题1关于银行（主要的词为loan、bank、money等），主题2关于河流（主要的词为river、stream、bank等）。

▪文档1内容100%关于主题1，主题向量为<1.0,0.0>，文档中每一个词的生成过程如下：

以100%的概率选择主题1，再从主题1中以一定的概率挑选词。

▪文档2内容50%关于主题1，50%关于主题2，主题向量为<0.5,0.5>，文档中每一个词的生成过程如下：

以均等的概率选择主题1和2，再从选中的主题中以一定的概率挑选词。

▪文档3内容100%关于主题2，主题向量为<0.0,1.0>，文档中每一个词的生成过程如下：

以100%的概率选择主题2，再从主题2中以一定的概率挑选词。

图11主题模型的生成过程[9]

现实的情况是我们没有模型，只有海量的互联网文档数据，此时我们希望有机器学习算法可以自动的从训练文档数据中归纳出主题模型（如图12），即得到每个主题在词表上的具体分布。

通常来说，训练过程还会得到一个副产品——每篇训练文档的主题向量。

图12主题模型的训练过程[9]

有了主题模型，给定新的文档，通过在线推断，我们就可以得到文档的主题向量（如图13）。

图5、6、7给出了一些具体的例子。

图13主题模型的在线推断

三个过程中，训练过程是难点，后文将进行重点介绍。

2.2LDA模型及其训练算法

LDA（LatentDirichletAllocation）[10]作为一种重要的主题模型，自发表以来就引起了学术界和产业界的极大关注，相关论文层出不穷。

LDA的训练算法也多种多样，下面以吉布斯采样[11,12]为例，进行简要介绍。

图14LDA训练过程

跳过复杂的数学推导，基于吉布斯采样的LDA训练过程如图14所示（每个词用w表示，每个词对应的主题用z表示，图中节点z的不同颜色表示不同的主题）：

▪Step1:

初始时，随机的给训练语料中的每一个词w赋值一个主题z，并统计两个频率计数矩阵：

Doc-Topic计数矩阵Ntd，描述每个文档中的主题频率分布；Word-Topic计数矩阵Nwt，表示每个主题下词的频率分布。

如图15所示，两个矩阵分别对应于图中的边上的频率计数。

▪Step2:

遍历训练语料，按照概率重新采样其中每一个词w对应的主题z，同步更新Nwt和Ntd。

▪Step3:

重复step2，直到Nwt收敛。

Step2中重新采样词w对应主题z时，采样公式为

P（z=t|w,∗）=N¬wt+βN¬t+βV⋅N¬td+αtLd–1+∑tαt∝N¬wt+βN¬t+βV（N¬td+αt）

（1）

其中αt和β是超参数，分别表示对Ntd和Nwt中的频率计数进行概率平滑；V为词表大小，Ld表示文档d长度，Nwt表示训练语料中主题t中词w的出现次数，Nt表示训练语料中主题t的出现次数，Ntd表示文档d中主题t的出现次数，上角标¬表示剔除当前采样词w的影响（比如N¬td表示减去当前采样词对应的主题后，文档d中主题t的出现次数）。

图15文档d1中词w主题重新采样

事实上，以上对文档d中词w的主题z进行重新采样的公式有非常明确的物理意义，表示P（w|z）P（z|d），可以如图15直观的表示为一个“路径选择”的过程：

▪对当前文档d中的当前词w（图15中黑体表示），词w的“旧”主题z给出了d-z-w的一条路径（图15

（1）虚线）；

▪剔除词w对应的“旧”主题z，更新在Nwt和Ntd中的计数（图15

（1）在旧路径对应的两条边上做“-1”操作）；

▪计算d-z-w的每一条可能路径的概率，d-z-w路径的概率等于d-z和z-w两部分路径概率的乘积即P（z|d）P（w|z），P（z|d）和Ntd有关，P（w|z）和Nwt有关（图15

（1））；

▪依据概率对d-z-w路径进行采样，得到词w的“新”主题z（图15

（2）虚线）；

▪增加词w对应的“新”主题z，更新在Nwt和Ntd中的计数（图15

（2）在新路径对应的两条边上做“+1”操作）。

图16单机版LDA训练过程

在训练模型时，为了包含尽可能多的隐含语义（主题）同时保证效果，通常会使用海量的训练语料。

这些互联网原始文档语料经过切词、停用词过滤、文档过滤（长度）等预处理步骤后（通常会分块进行存储），就可以作为LDA训练器的输入了。

图14描述的LDA训练过程，在更大范围的训练语料上来看，如图16所示：

▪训练语料数据块中会保存文档中的词和对应的主题（W,T），以及文档对应的主题直方图Ntd；

▪训练器内存中保存一份Nwt；

▪训练器依次加载训练语料数据块，并对其中的所有词W的主题T进行采样，采样的同时会更新Nwt、Ntd和文档中词W的主题T；

▪采样完成一个数据块后，训练器将更新后的（W,T）和Ntd序列化到磁盘上，供下一个迭代加载采样；

▪所有迭代结束，Nwt收敛，训练器根据Nwt计算出模型并输出。

基于吉布斯采样的LDA在线推断过程与训练过程（图14）类似：

给定文档，采样更新其中每一个词w对应的主题z（采样公式同上，采样过程中可以保持模型Nwt不变）；重复上述过程，直到文档主题直方图Ntd收敛，使用αt对其进行简单平滑即为文档主题向量。

三、十亿文档、百万词汇、百万主题？

从上一个小节的算法描述中，我们可以看到LDA的训练算法貌似并不复杂，主要的工作就是在维护两个频率计数矩阵Nwt和Ntd。

然而在这个时代，我们要面对的是互联网的海量数据，想象一下，如果在图15中，左边的文档节点是十亿、中间的主题个数是百万、右边不同的词的个数也是百万，我们将需要处理一张多大的图！

！

！

在实际应用中，我们希望使用更多的数据训练更大的模型，这包含了两重意思：

▪ “更多的数据”，我们希望训练器能处理海量的训练数据，因为更多的数据蕴含着更加丰富的隐含语义，同时模型也更加准确，效果更好。

上一小节提到单机版LDA训练器显然是处理不了海量数据的，使用它训练模型，我们估计要等到天荒地老了。

▪“更大的模型”，我们希望训练器能归纳出更多更具体更长尾的隐含语义，比如一百万主题。

抛开标准LDA算法本身的问题，更大的模型意味着矩阵Nwt规模更大。

Nwt的大小为VxK，V表示词表大小，K表示主题个数。

取V=1,000,000且K=1,000,000，Nwt需要消耗3000G以上内存（假设int型密集存储，因为模型随机初始化并不稀疏），显然单机内存是无法满足需求的，必须对模型进行切分。

下面分别从数据并行和模型并行两个方面来介绍怎样解决上述两个问题。

“数据并行”和“模型并行“是Google大神JeffDean在深度学习训练系统DistBelief[13]中新提出的两个概念，尽管Peacock系统开发的时候，DistBelief还没有真正对外公布。

随着深度学习的持续升温，大家现在已经逐渐熟悉了这两个形象的名词，此处请允许我们借用一下这两个概念。

3.1数据并行——处理更多的数据

“数据并行”通俗的理解：

通过多任务（每个任务都包含一份完整的模型）并行的处理数据训练模型，任务之间的模型或同步或异步的进行融合。

借用王益[3]的说法，“如果一个算法可以做数据并行，很可能就是可扩展的了”。

幸运的是，DavidNewman团队发现基于吉布斯采样的LDA训练算法可以“数据并行”，并给这个算法取了一个名字叫AD-LDA[14]。

注意，AD-LDA算法是吉布斯采样的近似算法，因为严格的吉布斯采样要求串行采样，不能并行。

直观的理解就是语料中前一个词w1采样更新后的Nwt和Nt应该应用于后一个词w2的采样，而不是w1和w2的采样都基于相同状态的Nwt和Nt。

AD-LDA算法会使得LDA的训练收敛速度变慢，但在多几轮迭代后，AD-LDA算法可以收敛到与串行吉布斯采样相同的点。

图17AD-LDA算法

图17给出了AD-LDA算法的示意图：

▪假设我们有三个可执行单元，每个都启动一个采样任务，每个任务中都有一个完整的“本地”模型LNwt；

▪任务并行的处理训练语料数据块（W,T）和Ntd，更新模型LNwt，同时序列化更新后的训练语料数据块（W,T）和Ntd到磁盘；

▪在迭代结束或任务处理训练语料数据块过程中，任务之间或同步或异步的融合模型。

模型融合的方式可以类似MPI中的AllReduce，也可以借助全局的参数服务器GNwt。

AD-LDA算法的整个过程和MapReduce的执行过程非常一致，所以早期有非常多的团队使用MapReduce来实现AD-LDA算法[5]：

▪MapReduce的一个Job进行AD-LDA算法的一个迭代；

▪训练语料数据块（W,T）和Ntd作为Job输入，Mapper加载上个迭代生成的GNwt作为LNwt，对数据块中的词进行主题采样；

▪Reducer融合各个LNwt，生成下一个迭代需要加载的GNwt。

因为MapReduce使用磁盘进行数据交换，同时整个训练任务需要调度几百个Jobs，所以基于MapReduce的AD-LDA实现是非常低效的。

3.2模型并行——训练更大的模型

上文提到，训练大模型时，Nwt太大而无法整体放入任务的内存，直观的解决方法如图18所示，将Nwt沿词的维度进行分片，每个采样任务只加载一个模型分片N（i）wt。

相应的，语料数据块也需要做对应的词维度切分，因为单个任务i只能采样N（i）wt包含的词w。

细心的童鞋可能已经发现，图18所示的模型并行方式在Ntd上采用了类似AD-LDA算法的近似，LNtd间的融合与LNwt间的融合类似，相应的算法也会减缓收敛（因为Nwt是所有训练语料上的聚合结果，而Ntd只和具体文档d有关，后者变化比前者更加“快速”， Ntd的并行近似采样更加“危险”，很容易造成训练不收敛）。

图18模型并行1

有没有办法不进行Ntd的并行近似采样，同时保持上述的模型切片方式呢？

Peacock系统设计了图19所示的并行采样方式：

加载了不同N（i）wt切片的任务并行的沿对角线方向对训练语料数据块（W,T）进行采样，一条对角线采样完成后，依次进行下一条对角线。

这样在对同一个文档的不同数据块间的词进行采样时，仍然保持了“串行性”，应用了之前数据块中的词对Ntd的更新。

图19的模型并行采样方式收敛性同AD-LDA是一致的。

图19模型并行2

3.3大规模主题模型训练系统Peacock

为了“利用更多的数据训练更大的模型”，Peacock系统结合了上述的“数据并行”和“模型并行”（图20）：

▪多组“模型并行”任务之间采用“数据并行”的方式工作，“模型并行”任务组内部，依然保持图19所示的并行采样方式；

▪在迭代结束或任务处理训练语料数据块过程中，不同“模型并行”任务组之间或同步或异步的融合模型分片LNiwt。

模型融合的方式可以类似MPI中的AllReduce，也可以借助全局的参数服务器GNiwt。

图20Peacock中的数据并行和模型并行

同上一小节“模型并行”的分析类似，Peacock系统的采样方式收敛性同AD-LDA是一致的。

MaxWelling团队提出的Async-LDA[6]证明了异步融合LNiwt方式的收敛性。

当Peacock采用异步方式融合LNiwt时，相当于同时结合了AD-LDA和Async-LDA算法，实践证明收敛性是没有问题的。

当然，Peacock系统在具体实现上除了上述的主要设计思想，还有很多的实用技巧，比如：

▪数据传输和文档采样之间的流水线。

▪图19所示的模型并行方式在每条对角线并行采样结束后都需要同步，怎样去掉这种同步？

▪怎样的模型Nwt分片方式，能尽可能的保证采样服务器之间的负载均衡？

▪我们是否需要每个迭代都重采样所有词的主题？

▪怎样快速的计算对数似然度？

▪怎样将模型的超参数αt和β优化融入Peacock系统？

▪除了标准的吉布斯采样，是否有更加快速的采样算法？

▪主题数K从100到1,000,000，系统的内部数据结构都保持不变么？

在我们的论文[15]中，部分的解答了上述问题，更详细的Peacock解密请关注我们的博客“火光摇曳”[16]^_^。

参考文献

▪[1]GregLinden,BrentSmith,andJeremyYork. ARecommendations:

Item-to-ItemCollaborativeFiltering.IEEEInternetComputing,2003.

▪[2]SimonFunk. NetflixUpdate:

TryThisatHome. http:

//sifter.org/~simon/journal/20061211.html.

▪[3] 分布式机器学习的故事. http:

//cxwangyi.github.io/2014/01/20/distributed-machine-learning/.

▪[4] LinkedIn高级分析师王益:

 大数据时代的理想主义和现实主义（图灵访谈）. 

▪[5] PLDAandPLDA+. 

▪[6]ArthurAsuncion,PadhraicSmyth,andMaxWelling. AsynchronousDistributedLearningofTopicModels.NIPS’2008.

▪[7] Yahoo_LDA. 

▪[8] MALLET. http:

//mallet.cs.umass.edu/.

▪[9]MarkSteyvers,andTomGriffiths. Probabilistictopicmodels.InT.Landauer,DMcNamara,S.Dennis,andW.Kintsch（eds）,LatentSemanticAnalysis:

ARoadtoMeaning.LaurenceErlbaum,2006.

▪[10]D.Blei,A.Ng,andM.Jordan. LatentDirichletallocation. JMLR’2003.

▪[11]ThomasL.Griffiths,andMarkSteyvers. Findingscientifictopics.PNAS’2004.

▪[12]GregorHeinrich. Parameterestimationfortextanalysis. TechnicalReport,2009.

▪[13]JeffreyDean,GregS.Corrado,RajatMonga,KaiChen,MatthieuDevin,QuocV.Le,MarkZ.Mao,Marc’AurelioRanzato,AndrewSenior,PaulTucker,KeYang,AndrewY.Ng. LargeScaleDistributedDeepNetworks. NIPS’2012.

▪[14]DavidNewman,ArthurAsuncion,PadhraicSmyth,andMaxWelling.DistributedAlgorithmsforTopicModels. JMLR’2009.

▪[15]YiWang,XueminZhao,ZhenlongSun,HaoYan,LifengWang,ZhihuiJin,LiubinWang,YangGao,ChingLaw,andJiaZeng. Peacock:

LearningLong-TailTopicFeaturesforIndustrialApplications. TIST’2015.

▪[16] 火光摇曳.