分布式潛在狄利克雷分配研究綜述

過云燕，李建中

(哈爾濱工業(yè)大學 海量數據計算研究中心，哈爾濱 150001)

0 引 言

主題模型(Topic Modeling)是一類重要的機器學習(Machine Learning)算法，可以從已有的文檔集合中發(fā)現潛在的混合主題，這是其成為用來推斷知識的無監(jiān)督學習工具[1]。潛在狄利克雷分配(Latent Dirichlet Allocation)作為最重要的主題模型的問題設定，在過去十年的實踐中已經顯示其不可或缺的作用[2]。其假設每個潛在主題是由字典中多個單詞混合組成的，而每個文檔是由多個主題混合組成的，基于這兩個假設，可以通過生成模型生成文檔集。

潛在狄利克雷分配已被廣泛應用于機器學習的多個不同領域，包括信息檢索、文本分析、數據可視化、在線廣告、推薦系統(tǒng)和網絡分析[3]。這些領域不斷收集待處理的數據，引發(fā)了大數據時代的到來，目前數據的增長速度早已遠超硬件能力的增長速度，因此分布式平臺的使用成為大數據訓練的主流解決方案。現有相關綜述匯總的潛在狄利克雷分配的算法研究，停留在解決應用數學問題的階段。分布式潛在狄利克雷算法的設計包含系統(tǒng)工程問題，如設計數據和模型的劃分與聚合、算法復雜性、通信計算平衡性等許多方面，需要對相關研究依據不同方法進行分類綜述。

潛在狄利克雷分配可以通過兩大類算法來求解，分別是馬爾科夫鏈蒙特卡洛(MCMC)和變分推斷(VI)。MCMC算法對一個馬爾可夫鏈進行采樣，并用鏈上的樣本來逼近后驗概率的分布，該樣本是漸近精確的。VI算法試圖找到一個分布族中能夠最小化估計后驗概率和精確后驗概率之間的KL距離的分布，將原來的推理問題轉化為優(yōu)化問題。使用MCMC或者VI在大數據上進行訓練時，每輪對模型的更新都需要對整個數據集進行完整的讀寫和推斷，雖然這種全批策略適合于較小的數據集，但是由于每輪迭代太耗時，性能隨著數據集大小的增長而顯著降低。因此，如何利用分布式系統(tǒng)實現快速訓練和推斷，成為當前重要研究方向。

盡管利用隨機變分推斷算法解決小型和靜態(tài)數據集上的問題已被廣泛和深入的研究。但在實際情況下，數據集通常非常龐大，并且是以流的形式收集的。在現實世界中，在海量流數據上運行機器學習算法，面臨3個挑戰(zhàn)：模型演化、數據動蕩和實時推斷。一系列相關研究闡述了如何分別應對這些新的挑戰(zhàn)。

本文旨在將當前針對分布式系統(tǒng)中高效運行潛在狄利克雷分配算法這一研究方向的現有成果進行歸納整理。

1 潛在狄利克雷分配問題

潛在狄利克雷分配(LDA)是針對文檔的概率生成模型。給定輸入文檔集合D和主題數量K，LDA旨在將每個文檔d表示為主題的混合分布，并將每個主題建模為字典V上的混合分布。此外，LDA還推斷每個文檔中每個單詞的主題分布。

LDA假設了主題和文檔的生成過程。β代表K個主題中詞的混合比例，是一個大小為K×V的矩陣。其中，第k行對應表示了主題K上詞的分布，βk～Dirichlet(η)，表示每一個βk是從擁有對稱參數η的狄利克雷分布中抽取到的。θ是文檔的主題混合比例，是一個大小為D×K的矩陣。第d行的θd對應表示文檔d的主題混合比例，θd～Dirichlet(α)，表示每一個θd是從擁有對稱參數α的狄利克雷分布中抽取到。在生成文檔d中的第n個單詞時，首先根據該文檔的主題分布θd，抽取一個主題作為該詞對應的主題，主題的編號zdn～Multinomial(θd)。再根據該主題的詞的分布βzdn，抽取了這個詞wdn,wdn～Multinomial(βzdn)。整個文檔可以通過重復多次后生成，而整個語料庫可以在重復多次抽取文檔后生成，變量之間的關系在圖1中用水平箭頭表示。

圖1 潛在狄利克雷分配的生成圖模型

2 變分推斷及其分布式算法

2.1 變分推斷

求解LDA問題的目標是對已給定的文檔集合w檢驗后驗條件概率分布p(β,θ,z|w)。由于后驗分布的精確推斷是難以解決的，Blei等人建議使用變分推斷(VI)來找到近似的后驗條件概率分布[4]。

VI引入了一個簡單的可以被完全因子化的分布q(β,θ,z|λ,γ,φ)。引入新添加的變分參數：λ,γ,φ后，q成為了精確后驗條件概率分布的新的近似表示。在圖1中，水平箭頭之間的依賴關系復雜，而新填入的變分參數，帶來的縱向箭頭代表的依賴關系之間相互獨立，替換了原來復雜的依賴關系。

q(βk|λk)是主題k對應的變分概率分布，是主題級別的變分概率分布，q(βk|λk)～Dirichlet(λk)。不需要直接推斷真實的分布p(βk|w,η)，VI選擇了一個分布族q(βk|λk)，選擇其中與之距離最近的一個，作為其近似分布。類似地，文檔級別的變分參數γd和φd，q(θd|γd)～Dirichlet(γd)，并且q(zdn|φdn)～Multinomial(φdn)。

VI的目標是最小化實際分布與近似分布之間的KL距離，這等價于最大化ELBO。ELBO可以通過3個變分參數來表示自變量，優(yōu)化ELBO的過程就是選擇最佳的λ,γ,φ，使之最大化的過程如下：

2.2 隨機變分推斷

盡管變分推斷在模型質量和收斂速度兩方面優(yōu)于馬爾科夫鏈蒙特卡洛，但在處理大規(guī)模數據集時仍然暴露出一些不足之處。使用變分推斷進行訓練時，每輪對模型的更新都需要對整個數據集進行完整的讀取和推斷，稱作全批量處理(full-batch)，這種全批量策略僅適合于較小的數據集。由于每輪迭代太耗時，算法性能隨著數據集的增長而顯著降低。

隨機變分推斷算法，在計算海量數據時具有很好的擴展性[5]。隨機變分推斷的主要思想是在每輪迭代時，不利用整體數據集，而是通過采集數據點作為樣本，在樣本上求得有噪聲的梯度，用以對整個數據集的梯度進行無偏的估計。Online-LDA使用隨機自然梯度上升的優(yōu)化方式，每輪迭代中，都在D中采樣生成小樣本集合，用來優(yōu)化主題級別參數λ，而文檔級別的參數(γ,φ)依然采用坐標上升法進行優(yōu)化。

主題級別參數和文檔級別參數之間有著緊密的關系，互相依賴。λ包含了來自數據集合中文檔級別參數的信息，其質量直接決定了對文檔推斷結果的質量。當使用已經收斂到較優(yōu)值的λ推斷文檔級別的參數時，才能得到更加合理的推斷結果。

Online-LDA與VI-LDA相比，其優(yōu)勢來源于更頻繁地更新λ。頻繁地利用具有正反饋含義的文檔級別參數，會使λ收斂地更快，反之會收斂更慢或最終發(fā)散，無法收斂。基于隨機優(yōu)化的思想，Online-LDA可以快速處理小批量(mini-batch)文檔，以此來近似估計整體數據集的信息。雖然小批量文檔包含一定的數據集信息，但是會存在噪聲。所以小批量的大小有一個折中的選擇，過小的小批量具有較少的語料信息，較大的噪聲，導致模型收斂過慢甚至發(fā)散；而過大的小批量減緩了更新的頻率，產生較弱的正反饋，收斂速率較低。在每一次迭代中采集小批量的文檔作為樣本，而不是單一文檔作為樣本時，Online-LDA可以在單機環(huán)境中快速收斂，比基于變分推斷的潛在狄利克雷分配算法收斂快數倍。

2.3 分布式變分推斷類算法的工作

VI-LDA是解決潛在狄利克雷分配問題的第一個變分推斷算法[2]。在每輪迭代中，其都會為每個文檔和文檔中的每個詞推斷其參數。通過劃分文檔，可以對VI-LDA算法中文檔級別計算過程實現并行計算[6]，在共享內存的多處理器和多核系統(tǒng)中可以實現這一思想；在Map-Reduce框架中擴展VI-LDA的算法為Mr.LDA[7]。在分布式計算框架結構中，Mr.LDA設計Mappers劃分文檔級別的計算，Reducer劃分主題級別的計算。在共享內存的系統(tǒng)中，并行實現VI-LDA算法可以使用塊矩陣劃分策略[8]，其避免了內存訪問的沖突，減少了多線程之間的互鎖時間，提供了基于剩余資源的動態(tài)調度。然而，隨著數據集大小的不斷增加，上述3個工作的內存需求也在增大。Online-LDA用隨機優(yōu)化方法解決了這個問題；DoLDA在MapReduce框架中提出了一種具有文檔級任務劃分的分布式Online-LDA，利用了有限內存和并行計算的優(yōu)勢[9]；Spark-MLlib庫選擇使用DoLDA作為求解潛在狄利克雷分配問題的主要算法，并且對其算法的實現進行了系列優(yōu)化，提供了當前性能最優(yōu)的分布式Online-LDA。Online-LDA理論上同樣可以在參數服務器上實現，但目前對其研究仍是空白。

3 馬爾科夫鏈蒙特卡洛及其分布式算法

3.1 馬爾科夫鏈蒙特卡洛

除了變分推斷以外，潛在狄利克雷分配可以通過另一大類方法來求解，即馬爾科夫鏈蒙特卡洛(MonteCarloMarkovChain)。馬爾科夫鏈蒙特卡洛對一個馬爾可夫鏈進行采樣，并用鏈上的樣本來逼近后驗概率的分布，該樣本是漸近精確的。而變分推斷試圖找到一個分布族中能夠最小化估計后驗概率和精確后驗概率之間的KL-距離的分布，這將原來的推理問題轉化為優(yōu)化問題。

馬爾科夫鏈蒙特卡洛與變分推斷相比有兩個缺點：

(1)雖然馬爾科夫鏈蒙特卡洛和變分推斷在理論上可以漸近地達到相似優(yōu)秀的損失函數，但在經驗上馬爾科夫鏈蒙特卡洛的模型質量并不令人滿意[10]。因為潛在狄利克雷分配假設一個詞屬于多個主題，是一個混合模型，但是馬爾科夫鏈蒙特卡洛技術通常將分配僅僅集中在單一主題上[11]，因此其在海量數據集和復雜模型上表現不佳，變分推斷已被證明更適合于混合模型[4]。

(2)最近的研究工作中多次表明，馬爾科夫鏈蒙特卡洛收斂得比變分推斷慢[12]。例如，在PublicMedicine數據集上，馬爾科夫鏈蒙特卡洛的收斂需要對整體數據集進行成百上千輪訓練，而變分推斷只需要數十輪訪問整體數據集來迭代優(yōu)化模型。因此，馬爾科夫鏈蒙特卡洛的整體性能比變分推斷慢了一個數量級，特別是在較大的數據集上劣勢更為明顯[4]。

3.2 分布式馬爾科夫鏈蒙特卡洛算法的工作

用吉布斯采樣的方法，可以解決潛在狄利克雷分配問題，但采樣器運行代價過高[13]。在此基礎上，另一些工作提出各類采樣器設計方法以簡化計算；利用分布偏斜的特性，僅計算每個采樣計算主題概率的一小部分[14]；利用稀疏結構來實現較低的采樣算法復雜性[15]；減少了子采樣操作的內部迭代所花費的時間[16]；上述方案的混合策略，成為當前運行最快的采樣器[12]。另一方面，在異步系統(tǒng)與參數服務器中對文檔級別的計數矩陣進行劃分，同樣是比較流行的方案。YahooLDA建立了一個基于原則和利用潛在狄利克雷分配固有稀疏性的系統(tǒng)[17]；可以對文件進行分區(qū)，并允許每個采樣器與分布式系統(tǒng)中的中央服務器不斷的通信，這里每個采樣器將差分發(fā)送給中央服務器，并從其接收最新的全局變量值[18]；可以采用非對稱結構來降低通信代價，并采用偏斜的劃分策略來平衡不同服務器的負載[12]。另一些工作在系統(tǒng)中同時并行劃分文檔級計數矩陣和分區(qū)級計數矩陣，由于調度復雜和分區(qū)數量龐大，Peacock的吞吐量通常低于僅僅劃分數據的系統(tǒng)[19]；F+LDA提出了一種游牧分配方案，并利用芬威克樹進行抽樣[8]；在LightLDA中進一步改進其分配方案的同時，使用別名表優(yōu)化采樣[20]；同時可以采用隨機版本吉布斯采樣算法求解潛在狄利克雷分配[21]；可以在GPU計算環(huán)境下實現吉布斯采樣解決潛在狄利克雷分配問題[22]。

3.3 分布式混合類算法的工作

混合類算法的主要思想是在主題級別推理中使用變分推斷的方法，在文檔級別推理中使用馬爾科夫鏈蒙特卡洛的方法。CVB[23]、CVB0[24]和稀疏SVB[25]用吉布斯采樣來推斷文檔級別變量的分布，但是在變分推斷的設定中，條件概率的計算代價十分昂貴，需要數輪的采樣。ESCA存儲文檔級別變量分布的充分統(tǒng)計量(sufficient statistics)，使得內存占用較小[10]。隨機CVB、稀疏SVB和ESCA是混合類算法的隨機版本，該類方法在面向主題級別的參數時，同樣可以設計出Online版本的算法，與Online-LDA類似。同時，文檔級別的劃分方式也被用來加快算法的速度。最小化在GPU上的沖突，可以實現并行CVB[26]。分布式CVB采用異步通信策略[27]，分布式ESCA采用同步通信策略[10]。

4 面向流數據處理的相關工作

4.1 數據貝葉斯

流變分貝葉斯(Streaming Variational Bayes)代表了學習流數據中潛在變量的最新方法[28]。流變分貝葉斯引入了貝葉斯更新，以避免在每輪迭代中大量訪問歷史數據：給定已經訓練過的模型作為先驗知識，以及新生成的、具有相同時間戳的文檔作為觀測數據，就可以使用流變分貝葉斯算法計算出近似的后驗知識；同時，后驗知識對應的矩陣成為當前最新模型。但是，用隨機變分推斷求解潛在狄利克雷分配問題時，需要假定主題分布和數據分布是相對穩(wěn)定的，這意味著其沒有考慮數據動蕩的情況，以及如何保持動蕩數據中的主題一致性。當新生成數據實例上的主題分布與擁有上一個時間戳的數據實例上的主題分布明顯不同時，利用流變分貝葉斯所獲得的先驗知識更接近于被隨機初始化。在這種情況下，每一輪的訓練將不得不建立在非常模糊的草圖主題和一批無法預知其主題分布的數據實例上。因此，流變分貝葉斯無法保持主題一致性，并且等待訓練和推斷的延遲也非常高。

4.2 通用流數據處理平臺

為了在大量的流數據上進行實時推理，一些分布式流處理系統(tǒng)將工作負載分為兩個階段：訓練階段和推理階段[29]。在這種框架中，訓練階段充當了預處理步驟，延遲僅包括推斷時間，因此可以通過分布式計算來進一步加速推斷。該框架的主要局限性在于推理結果完全取決于從歷史數據中提取的主題，而忽略了數據流上存在主題演變的事實。為了獲得高質量的實時推理，主題演變意味著需要在數據流上進行終身學習(持續(xù)學習)。因此，現有的分布式流處理系統(tǒng)中的潛在狄利克雷分配算法，不再是最優(yōu)解。

4.3 動態(tài)主題模型

另一方面，包括動態(tài)主題模型(DynamicTM)在內的一些已有工作，研究了如何在帶有時間戳的小型靜態(tài)歷史數據集上挖掘不斷發(fā)展的主題的問題[30-31]。與經典的潛在狄利克雷分配相比，其通過修改潛在變量之間的因果關系，設計了衍生的主題模型公式。類比經典潛在狄利克雷分配算法的求解推導過程，針對動態(tài)主題模型推導類似的更新函數，用來訓練動態(tài)主題模型。但是，這些算法無法輕量級的部署在真實的流數據場景中，因為處理整個數據集的訓練過程是非常耗時的[31]，并且當數據增加時，該類算法對存儲的需求非常昂貴[30]。

4.4 動態(tài)數據集

在動蕩的數據流上，新數據實例上的主題分布與從整個流中采樣獲得的數據實例上的主題分布是不同的。在這種情況下，已有研究針對流數據上的潛在狄利克雷分配提出了種群變異貝葉斯(PP-LDA)[32]和信任區(qū)域(TR-LDA)[33]，以應對數據動蕩的情況。PP-LDA定義了流數據的總體后驗，需要存儲所有見到過的數據在所有特征上的分布，在實踐中，當數據量和特征數量增加時，這個記錄的大小會成比例增長；TR-LDA使用信任區(qū)域優(yōu)化思想更新模型，該算法要求從整個歷史數據中無偏采集樣本數據實例來迭代優(yōu)化，因此采樣代價會隨著數據流的增長而增加。盡管PP-LDA和TR-LDA具有一定的理論保證，但其都需要昂貴的存儲空間來存儲大量歷史記錄，并且每輪采樣都需要昂貴的讀寫代價。因此都不適合應用在大規(guī)模流數據集上。

5 分布式機器學習平臺

5.1 參數服務器

通常可以將參數服務器視為一種架構，該架構使用分布式內存來維護機器學習中的模型，并支持保持節(jié)點間一致性的靈活的通信控制，提供了諸如pull和push之類的原語，使用戶能夠使用自定義的一致性控制器如：BSP、SSP和ASP同步或異步更新模型的一部分。自提出參數服務器概念以來，其靈活和卓越的性能使其變得非常流行，例如：Li等提出在參數服務器上執(zhí)行小批量隨機梯度下降算法(mini-batchSGD)[18]，Petuum是使用參數服務器架構的通用機器學習系統(tǒng)[34]；也有使用參數服務器實現求解潛在狄利克雷分配算法的工作，例如：YahooLDA在參數服務器之間劃分數據對應的矩陣；LightLDA使用參數服務器劃分并存儲部分主題矩陣。上述系統(tǒng)均屬于基于馬爾科夫鏈蒙特卡洛思想求解潛在狄利克雷分配的算法。

5.2 MapReduce

Spark原生機器學習庫MLlib，基于變分推斷實現VI-LDA算法[35]。為了在大數據集上實現快速收斂，MLlib提供了基于隨機變分推斷實現的OnlineLDA算法，優(yōu)于VI-LDA。同時，Kaoudi構建了一個基于代價的優(yōu)化器，以針對給定的工作量選擇最佳的計劃[36]；Anderson將MPI集成到Spark中，并將工作負載轉移到MPI環(huán)境中[37]。將數據從Spark傳輸到MPI環(huán)境，使用高性能MPI二進制文件進行計算，最后將結果復制回分布式文件系統(tǒng)中以供進一步使用。

5.3 計算和通信的平衡

為了平衡計算和通信，有以下幾方面工作。首先，在給定分布式工作任務的情況下確定要使用的計算節(jié)點數量，使用過多的計算節(jié)點會增加通信代價，而使用過少的計算節(jié)點會增加每個節(jié)點的計算代價。按照這一思路，McSherry認為，分布式計算的性能至少應優(yōu)于單節(jié)點上最優(yōu)實現的性能[38]；Huang使用盡可能少的機器來確保性能和效率[39]。其次，有許多工作建議通過盡可能多地執(zhí)行本地計算來降低通信代價。例如，Grape是當前最優(yōu)的分布式圖形處理系統(tǒng)，其試圖在一臺機器上進行盡可能多的計算，并減少分布式圖形處理中的迭代次數[40]；Gaia是使用參數服務器的地理分布式機器學習系統(tǒng)，試圖盡可能使用局域網間通信而非廣域網間通信來降低通信代價[41]；也有一些工作通過對工作負載進行劃分，以實現更好的負載平衡，從而降低通信代價[42]。

6 結束語

本文首先介紹了狄利克雷分配問題，然后簡要闡述了求解該問題的兩個主流方法：變分推斷和馬爾科夫鏈蒙特卡洛。并且，圍繞兩個方法的經典單機算法，從數據劃分、任務劃分等思路，介紹將其轉化為分布式算法的相關工作。綜合基于變分推斷、基于馬爾科夫蒙特卡洛、基于兩者混合算法的并行工作，可以得出如下結論: 第一，針對馬爾科夫鏈蒙特卡洛類算法的研究豐富，針對變分推斷算法的研究仍為起步階段，而從理論和實踐兩方面表明，變分推斷算法優(yōu)于馬爾科夫鏈蒙特卡洛類算法，更值得被關注和進一步研究。第二，現有研究多集中于共享內存的并行算法設計，而針對不共享內存的分布式計算環(huán)境，如何提升基于隨機思想的變分推斷算法效率問題，具有重要的研究意義。

緊接著，面對流數據處理帶來的新挑戰(zhàn)，本文匯總了分別應對這些挑戰(zhàn)的代表性算法。現有研究開始設計解決方案，以同時應對實時推斷、主題演變、數據動蕩3方面挑戰(zhàn)[43]。

最后，從分布式系統(tǒng)角度，對系統(tǒng)框架設計方案、計算與通信平衡設計方案進行了更深入的討論。將更多計算任務本地化，是減少通信代價的重要思想。參數服務器與 Spark 相比，通信模式具有優(yōu)勢。利用上述兩點特性，提升 Spark 的性能，是值得研究的方向[44]。

綜上所述，分布式潛在狄利克雷分配算法的訓練效率和推斷效果均有提高，但與此同時依然存在著更大的提升空間。