基于擴散方法的分布式隨機變分推斷算法

付維明 秦家虎 朱英達

在大數據時代,數據通常會被分布式地存儲在多個節(jié)點上,例如傳感器網絡[1?3]和分布式數據庫[4]中等,其中每個節(jié)點只擁有部分數據.考慮到單個節(jié)點的存儲容量有限以及保護數據隱私或安全的需求[5?6],通常無法將所有數據都發(fā)送給一個中心節(jié)點,然后利用集中式的方法處理這些數據,因此開發(fā)高效的算法對分布式存儲的數據進行挖掘已成為當前一個重要的研究方向[7?12].

變分貝葉斯(Variational Bayesian,VB)推斷[13]是一種功能強大的數據挖掘技術,被廣泛用于解決實際問題,如識別文檔主題[14?15],對數據進行聚類和密度估計[16]以及預測未知數據[17]等.近年來,研究者們已提出很多分布式的VB 算法[3,18?20],然而在大多數這些算法的每步迭代中,都需要基于整個數據集更新全局參數,這不僅會導致算法計算代價大、效率低,還會導致算法可擴展性差,難以擴展到在線學習或者流數據處理的情況.

隨機變分推斷(Stochastic variational inference,SVI)[15]的提出使得貝葉斯推斷方法在處理海量數據時具有更高的效率和可擴展性.它借用了隨機優(yōu)化的方法,根據基于子樣本的噪聲自然梯度來優(yōu)化目標函數,大大減小了每步迭代時所需的存儲量和計算量.目前已有一些研究者將其擴展為分布式版本,以提高分布式數據的處理效率以及將其應用于分布式數據流的處理[21].具體地,文獻[22]提出了一種有中心的異步分布式SVI 算法,該算法中的中心節(jié)點負責收發(fā)全局參數,其余節(jié)點并行地更新全局參數.值得一提的是,這類有中心的算法往往會存在魯棒性差,鏈路負載不平衡,數據安全性差等缺點.在文獻[11]中,交替方向乘子方法(Alternating direction method of multipliers,ADMM)[23]被用來構造兩種無中心的分布式SVI 算法,克服了有中心的算法的缺點,但它們存在每步迭代中全局參數本地更新所需的計算代價大以及不適用于異步網絡的缺點.

本文以SVI 為核心,借用多智能體一致優(yōu)化問題中的擴散方法[24],發(fā)展了一種新的無中心的分布式SVI 算法,并針對異步網絡提出了一種適應機制.在所提出的算法中,我們利用自然梯度法進行全局參數的本地更新,并選擇對稱雙隨機矩陣作為節(jié)點間參數融合的系數矩陣,減小了本地更新的計算代價.最后,我們在伯努利混合模型(Bernoulli mixture model,BMM)和隱含狄利克雷分布(Latent Dirichlet allocation,LDA)上驗證了所提出的算法的可行性,實驗結果顯示所提出的算法在發(fā)現(xiàn)聚類模式,對初始參數依耐性以及跳出局部最優(yōu)等方面甚至優(yōu)于集中式SVI 算法,這是以往分布式VB 算法所沒有表現(xiàn)出來的.

本文其余部分安排如下:第1 節(jié)介紹集中式SVI 算法;第2 節(jié)介紹本文所提出的分布式SVI算法并給出了一種針對異步網絡的適應機制;第3 節(jié)展示在BMM 和LDA 模型上的實驗結果;第4 節(jié)對本文工作進行總結.

1 隨機變分推斷

1.1 模型介紹

SVI 基本模型包含以下這些量:數據集x={x1,···,xN},局部隱藏變量y={y1,···,yN},全局隱藏變量β以及模型參數α.模型的概率圖如圖1所示,其中黑色圓圈代表固定參數,灰色圓圈代表數據集,白色圓圈代表隱藏變量,箭頭描述了它們之間的依賴關系.具體地,α直接影響β,β直接影響局部變量對 (xn,yn).我們假設全局隱藏變量β的先驗分布屬于指數族分布且具有如下形式:

其中,u(β) 表示自然參數,A(α) 表示歸一化函數;不同局部變量對 (xn,yn) 之間相互獨立且其分布也屬于指數族分布,具體形式如下:

圖1 本文考慮的模型的概率圖表示Fig.1 The graphic model considered in this paper

其中f(xn,yn) 表示自然充分統(tǒng)計量;此外,還假設上述兩個指數族分布滿足共軛條件關系[25],以使后驗分布與先驗分布的形式相同.我們的目標是根據觀測到的數據集來估計局部隱藏變量的分布,即其后驗分布p(y,β|x).

1.2 平均場變分推斷

平均場變分推斷是一種用一個可以因式分解的變分分布去近似后驗分布的方法.在上一節(jié)介紹的模型基礎上,我們可以用變分分布q(y,β) 來近似p(y,β|x),并假設該變分分布滿足以下條件:

其中,λ和φ={φ1,φ2,···,φN} 是變分參數.此時需要最小化q(y,β)和p(y,β|x) 之間的Kullback-Leibler (KL)散度來讓q(y,β) 逼近p(y,β|x),這等價于最大化

其中,Eq[·]表示在分布q(y,β) 下的期望函數,L(λ,φ)是對數證據 lnp(x) 的一個下界,被稱為Evidence lower bound (ELBO)[15].基于q(y,β)) 可分解的假設,最大化L(λ,φ) 可以利用坐標上升法[26]通過交替更新λ和φ來實現(xiàn).下文討論的SVI 以上述平均場變分推斷方法為基礎.

如果我們固定φ,則可以把L(λ,φ) 看成是λ的函數,此時需要求解常用的方法是對其求(歐氏)梯度,但是用歐氏距離表征不同λ之間的遠近關系是不合理的,這是因為λ為變分參數,我們所關心的是不同的λ所刻畫的分布q(y,β) 之間的差異,此時可以引入自然梯度[15],它表示的是函數在黎曼空間上的梯度.通過對L(λ,φ)關于φ求自然梯度,可以將平均場變分推斷推廣到隨機優(yōu)化的版本,即隨機變分推斷.具體地,我們定義如下的隨機函數

其中,I是均勻取值于{1,···,N}的隨機變量.易知LI(λ)的期望等于L(λ),因此每次均勻地選取一個數據點n時,Ln(λ) 給出了L(λ) 的一個無偏估計.根據隨機優(yōu)化理論,集中式SVI 的過程由下面兩步構成:

1) 均勻地隨機選取一個數據點n,并計算當前最優(yōu)的局部變分參數

2) 通過

更新全局變分參數λ.

上述SVI 算法一次迭代只采樣一個數據點,其也可以被直接擴展成一次采樣一個數據批量(Batch)的版本,詳見文獻[15].

2 基于擴散方法的分布式SVI 算法

2.1 問題描述

我們考慮一個由J個節(jié)點組成的分布式網絡,其中每個節(jié)點i存儲包含Ni個數據項的數據集xi={xi1,···,xiNi},于是整個網絡上存儲的完整數據集為x={x1,···,xJ},總數據項數為假設網絡的通訊拓撲是一個無向圖G=(V,E),其中V={1,···,J}是節(jié)點集合,E ?V ×V是邊集合,(i,j)∈E表明信息可以在節(jié)點i和節(jié)點j之間直接傳輸,記節(jié)點i的鄰居集合為Bi={j ∈V:(j,i)∈E}.此外,我們還假設G是連通的,即對存在至少一條路徑連接節(jié)點i和節(jié)點j.

如果記節(jié)點i的局部隱藏變量為yi={yi1,···,yiNi},記對應的局部變分參數為φi={φi1,···,φiNi},則ELBO 可以寫為

2.2 算法設計

我們借用多智能體一致優(yōu)化問題中的擴散方法來發(fā)展分布式SVI 算法.擴散方法的基本思想是交替執(zhí)行本地更新和節(jié)點間參數融合兩個步驟,從而使所有節(jié)點的參數收斂到所希望的全局最優(yōu)值或者局部最優(yōu)值.

對于節(jié)點i,如果定義其局部ELBO 為

注意本地更新只能使每個節(jié)點的全局變分參數獨立地收斂到各自的局部ELBO 的局部最優(yōu)值,我們還要保證每個節(jié)點學得的全局變分參數收斂到一致,即||λi-λj||→0,由于我們已經假設拓撲圖是連通的,因此只要使||λi-λj||→0,?(i,j)∈E就可以保證所有節(jié)點的全局變分參數都收斂到一致.為此,根據擴散方法,我們在每次本地更新之后,將每個節(jié)點的當前全局變分參數發(fā)送給其鄰居節(jié)點,然后將當前的全局變分參數與從鄰居節(jié)點接受到的全局變分參數進行融合.上述過程可以由下面公式描述:

其中,pij是融合系數,我們采用如下的定義

事實上,如上定義的 [pij]是一個對稱隨機矩陣.當迭代次數很大的時候,ρt變得很小,則有分布式SVI 算法退化成由式(15)描述的平均一致性協(xié)同過程,所以將收斂到所有節(jié)點初始參數值的平均值.這樣使得訓練結果不會對任何節(jié)點的數據分布有偏向性.

2.3 針對異步網絡的適應機制

上節(jié)所述的分布式SVI 算法默認是同步執(zhí)行的,即所有節(jié)點在每個迭代步同步地執(zhí)行本地更新和參數融合兩個步驟.但是所有節(jié)點同步執(zhí)行需要使用時間同步協(xié)議去估計和補償時序偏移,這會帶來額外的通信負載.此外,執(zhí)行快的節(jié)點需要等待執(zhí)行慢的節(jié)點,這會大大降低算法的執(zhí)行速度.為此我們設計了一種機制使所提出的分布式SVI算法適應異步通信網絡.具體地,每個節(jié)點額外開辟一塊存儲區(qū)域將鄰居節(jié)點發(fā)送過來的存儲起來.在每個參數融合步中,如果在等待一定的時間后收到了來自鄰居節(jié)點發(fā)送過來的則更新存儲區(qū)域中的的值,然后,用更新后的進行本地參數更新;否則,直接用存儲區(qū)域的值進行本地參數更新.這樣一來,既可以使所提出的分布式算法以異步方式執(zhí)行,又盡可能地保證了算法的性能.

3 實驗

這一節(jié)我們將所提出的分布式SVI 算法(我們稱之為異步分布式SVI)應用于BMM 模型和LDA主題模型,并在不同的數據集上測試其性能.并且將其與集中式SVI 算法和dSVB 算法[3]進行對比,其中dSVB 算法被我們以同樣的方式擴展成隨機的版本以方便比較.

3.1 伯努利混合模型

我們考慮具有K個成分的混合多變量伯努利模型.該模型的全局隱藏變量包括:每個成分k的全局隱藏變量βk,其維度等于數據維度,每個維度的值表示該維度的數據值屬于“0”的概率,以及成分的混合概率π={π1,···,πK},其中隱藏變量的先驗分布形式如下:

其中,α=[α]K,a和b是固定的超參數,在BMM模型上的實驗中,我們均設置α=a=b=1.

我們將混合多變量伯努利模型應用到MNIST 數據集上.在預處理中,每張圖的每個像素根據其像素值被設為0 或者1,然后每張圖被展開成28 × 28=784 維的向量.我們隨機生成包含50 個節(jié)點,166 條邊的無向連通網絡,其拓撲結構如圖2所示,并將訓練數據平均分給50 個節(jié)點,每個節(jié)點包含1 200 條數據(整個MNIST 訓練集包含60 000條數據).實驗中,設置K=40,并設置全局隱藏變量的先驗分布為均勻分布.

圖2 通信網絡拓撲圖Fig.2 The topology of the communication network

圖3 展示了所提出的異步分布式SVI 算法在κ=0.5,τ=10下,每份數據分6 個批次訓練200 個epoch 得到的聚類中心 (由每個成分k的全局隱藏變量βk的期望所定義的向量對應的圖片) 和相同設置下集中式SVI 算法得到的聚類中心.由圖3 可知,異步分布式SVI 算法可以充分找到所有潛在的聚類模式,而集中式SVI 則往往不能充分找出所有的聚類模式.

在相同設置下多次運行三種算法得到的所有節(jié)點估計的ELBO 的平均值以及相校平均值的偏差演化曲線如圖4 所示,可以看到異步分布式SVI 算法相比集中式SVI 算法能夠收斂到更好的值,并且多次運行得到的結果之間的誤差更小,表現(xiàn)更加穩(wěn)定.此外,異步執(zhí)行的方式破壞了dSVB 算法的收斂性,而異步分布式SVI 算法對異步網絡具有良好的適應性.

圖3 異步分布式SVI 算法和集中式SVI 算法得到的聚類中心Fig.3 Cluster centers obtained by the asynchronous distributed SVI and the centralized SVI

為了研究超參數κ和τ對所提出的分布式SVI算法表現(xiàn)的影響,我們在(κ=0.5,τ=1),(κ=0.5,τ=10),(κ=0.5,τ=100),(κ=0.75,τ=10),(κ=1,τ=10)幾組參數下進行實驗,所得到的所有節(jié)點ELBO 的平均值的演化曲線見圖5,可以看到在不同的 (κ,τ) 設置下所提出的異步分布式SVI 均優(yōu)于集中式SVI.

3.2 LDA 主題模型

LDA 主題模型是文檔集的概率模型,它使用隱藏變量對重復出現(xiàn)的單詞使用模式進行編碼,由于這些模式在主題上趨于一致,因此被稱為“主題模型”.其已經被應用于很多領域,例如構建大型文檔庫的主題導航或者輔助文檔分類.LDA 模型的貝葉斯網絡結構如圖6 所示,其中變量的說明見表1.

圖4 異步分布式SVI 算法、dSVB 算法、集中式SVI 算法的ELBO 的平均值和偏差演化Fig.4 The evolution of the means and deviations of the ELBO for the asynchronous distributed SVI,the dSVB,and the centralized SVI

我們首先在New York Times 和Wikipedia 兩個數據集上驗證異步分布式算法在LDA 模型上的性能.首先我們生成一個包含5 個節(jié)點7 條邊的網絡,將每個數據集的文檔隨機分配給各個節(jié)點.在實驗中我們設置K=5,并以文檔集的生成概率的對數作為評價指標.

圖7 展示了在α=0.2,η=0.2,κ=0.5,τ=10,訓練epoch 取40,分布式算法中每個節(jié)點的批大小取10,集中式算法的批大小取50 的設置下,異步分布式SVI,集中式SVI 和dSVB 以異步方式分別在兩個數據集上運行多次得到的lnp(w)的演化曲線,可見異步分布式SVI 算法表現(xiàn)優(yōu)于另外兩種算法.不同參數設置下異步分布式SVI 和集中式SVI 在New York Times 數據集上收斂時的lnp(w)見表2,可見不同設置下異步分布式SVI 的表現(xiàn)均優(yōu)于集中式SVI.

圖5 不同 (κ,τ) 設置下異步分布式SVI 和集中式SVI 的ELBO 的平均值演化Fig.5 The evolution of the means of the ELBO for the asynchronous distributed SVI and the centralized SVI under different settings of (κ,τ)

圖6 LDA 模型的貝葉斯網絡結構圖Fig.6 The Bayesian graphic model of LDA

圖7 異步分布式SVI、集中式SVI 和dSVB 在兩個數據集上的表現(xiàn)Fig.7 Performance of the asynchronous distributed SVI,the centralized SVI,and the dSVB on the two data sets

表1 LDA 模型變量Table 1 Variables in LDA model

表2 不同參數設置下異步分布式SVI 和集中式SVI 收斂的值Table 2 The convergent values of the asynchronous distributed SVI and the centralized SVI under different parameter settings

然后我們在復旦大學中文文本分類數據集上測試所提出的異步分布式SVI 算法.該數據集來自復旦大學計算機信息與技術系國際數據庫中心自然語言處理小組,其由分屬20 個類別的9 804 篇文檔構成,其中20 個類別的標簽分別為Art、Literature、Education、Philosophy、History、Space、Energy、Electronics、Communication、Computer、Mine、Transport、Environment、Agriculture、Economy、Law、Medical、Military、Politics 和Sports.在預處理步驟中,我們首先去除了文本中的數字和英文并用語言技術平臺(Language technology plantform,LTP)的分詞模型對文本進行分詞處理.為了減小訓練的數據量,我們只讀取每個類別的前100 篇文檔進行訓練.圖8 展示了在K=20,α=0.2,η=0.2,κ=0.5,τ=10,分布式算法Batch size(批大小)取2,集中式算法batch size 取100 的設置下,異步分布式SVI 和集中式SVI 分別在復旦大學中文文本分類數據集上運行多次得到的lnp(w)的演化曲線,可以看到異步分布式SVI 收斂速度慢于集中式SVI,但是最終得到的 lnp(w) 值優(yōu)于集中式SVI.

圖8 異步分布式SVI 和集中式SVI 在復旦大學中文文本分類數據集上的表現(xiàn)Fig.8 Performance of the asynchronous distributed SVI and the centralized SVI on the Chinese text classification data set of Fudan University

圖9 展示了在表3 所示的超參數組合設置下異步分布式SVI 和集中式SVI 在復旦大學中文文本分類數據集上訓練100 個epoch 得到的 lnp(w) 的值的對比,其中橫坐標為集中式SVI 得到的lnp(w)的值,縱坐標為對應超參數設置下異步分布式SVI 得到的 lnp(w) 的值.可以看到大部分數據點都位于左上方,表明大部分情況下異步分布式SVI都優(yōu)于集中式SVI.并且注意到當batch size 取1 時異步分布式SVI 表現(xiàn)最差,在(κ=0.5,τ=1,batchsize=1)的設置下其表現(xiàn)不如集中式SVI.我們認為這是由于當batch size 太小時,分布式SVI的收斂速度過慢造成的.

圖9 不同超參數設置下異步分布式SVI 和集中式SVI 在復旦大學中文文本分類數據集上表現(xiàn)Fig.9 Performance of the asynchronous distributed SVI and the centralized SVI on the Chinese text classification data set of Fudan University under different hyperparameter settings

表3 超參數取值表Table 3 The values of hyperparameters

4 結論

本文針對無中心的分布式網絡,基于擴散方法提出了一種新穎的分布式SVI 算法,其中采用自然梯度法進行本地更新以及采用對稱雙隨機矩陣作為信息融合系數,并且為其設計了一種針對異步網絡的適應機制.然后將其應用于BMM 和LDA 主題模型.在不同數據集上的實驗均表明所提出的算法確實適用于異步分布式網絡,而且其在發(fā)現(xiàn)聚類模式和對抗淺的局部最優(yōu)方面的表現(xiàn)優(yōu)于集中式SVI算法.