付維明 秦家虎 朱英達(dá)

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

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

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

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

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

1 隨機變分推斷

1.1 模型介紹

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

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

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

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

1.2 平均場變分推斷

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

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

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

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

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

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

2) 通過

更新全局變分參數(shù)λ.

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

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

2.1 問題描述

我們考慮一個由J個節(jié)點組成的分布式網(wǎng)絡(luò),其中每個節(jié)點i存儲包含Ni個數(shù)據(jù)項的數(shù)據(jù)集xi={xi1,···,xiNi},于是整個網(wǎng)絡(luò)上存儲的完整數(shù)據(jù)集為x={x1,···,xJ},總數(shù)據(jù)項數(shù)為假設(shè)網(wǎng)絡(luò)的通訊拓?fù)涫且粋€無向圖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}.此外,我們還假設(shè)G是連通的,即對存在至少一條路徑連接節(jié)點i和節(jié)點j.

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

2.2 算法設(shè)計

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

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

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

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

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

2.3 針對異步網(wǎng)絡(luò)的適應(yīng)機制

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

3 實驗

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

3.1 伯努利混合模型

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

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

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

圖2 通信網(wǎng)絡(luò)拓?fù)鋱DFig.2 The topology of the communication network

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

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

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

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

3.2 LDA 主題模型

LDA 主題模型是文檔集的概率模型,它使用隱藏變量對重復(fù)出現(xiàn)的單詞使用模式進行編碼,由于這些模式在主題上趨于一致,因此被稱為“主題模型”.其已經(jīng)被應(yīng)用于很多領(lǐng)域,例如構(gòu)建大型文檔庫的主題導(dǎo)航或者輔助文檔分類.LDA 模型的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)如圖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 兩個數(shù)據(jù)集上驗證異步分布式算法在LDA 模型上的性能.首先我們生成一個包含5 個節(jié)點7 條邊的網(wǎng)絡(luò),將每個數(shù)據(jù)集的文檔隨機分配給各個節(jié)點.在實驗中我們設(shè)置K=5,并以文檔集的生成概率的對數(shù)作為評價指標(biāo).

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

圖5 不同 (κ,τ) 設(shè)置下異步分布式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 模型的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.6 The Bayesian graphic model of LDA

圖7 異步分布式SVI、集中式SVI 和dSVB 在兩個數(shù)據(jù)集上的表現(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 不同參數(shù)設(shè)置下異步分布式SVI 和集中式SVI 收斂的值Table 2 The convergent values of the asynchronous distributed SVI and the centralized SVI under different parameter settings

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

圖8 異步分布式SVI 和集中式SVI 在復(fù)旦大學(xué)中文文本分類數(shù)據(jù)集上的表現(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 所示的超參數(shù)組合設(shè)置下異步分布式SVI 和集中式SVI 在復(fù)旦大學(xué)中文文本分類數(shù)據(jù)集上訓(xùn)練100 個epoch 得到的 lnp(w) 的值的對比,其中橫坐標(biāo)為集中式SVI 得到的lnp(w)的值,縱坐標(biāo)為對應(yīng)超參數(shù)設(shè)置下異步分布式SVI 得到的 lnp(w) 的值.可以看到大部分?jǐn)?shù)據(jù)點都位于左上方,表明大部分情況下異步分布式SVI都優(yōu)于集中式SVI.并且注意到當(dāng)batch size 取1 時異步分布式SVI 表現(xiàn)最差,在(κ=0.5,τ=1,batchsize=1)的設(shè)置下其表現(xiàn)不如集中式SVI.我們認(rèn)為這是由于當(dāng)batch size 太小時,分布式SVI的收斂速度過慢造成的.

圖9 不同超參數(shù)設(shè)置下異步分布式SVI 和集中式SVI 在復(fù)旦大學(xué)中文文本分類數(shù)據(jù)集上表現(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 超參數(shù)取值表Table 3 The values of hyperparameters

4 結(jié)論

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