基于LDA 模型的稀疏消息傳遞算法

屠雄剛 陳 軍 楊 璐 嚴(yán)建峰

（1.浙江工業(yè)職業(yè)技術(shù)學(xué)院設(shè)計與藝術(shù)學(xué)院 紹興 312000 2.蘇州大學(xué)計算機科學(xué)與技術(shù)學(xué)院 蘇州 215006 3.蘇州大學(xué)江蘇省計算機信息處理技術(shù)重點實驗室 蘇州 215006）

1 引言

潛在狄利克雷分配（Latent Dirichlet Allocation,LDA）[1]是識別大規(guī)模文本集或語料庫中潛在主題信息的概率主題模型，它能夠?qū)卧~空間中的文檔變換到主題空間，得到文檔在低維空間中的表達。LDA 假定每篇文檔是主題的一個概率組合，而主題是單詞表中單詞的多項分布。文檔-主題分布可以看作是文檔在主題空間的表示，能夠被用來分類以及檢索，而主題在單詞的分布能被用來表示主題的意義。然而這樣的LDA 模型不能直接控制推理參數(shù)的后驗稀疏度。

在文本模型中語義空間的稀疏表示具有實際的應(yīng)用價值，通常每篇文檔或每個單詞只有幾個突出的主題意義，而不是在每個主題上都有非0 的值。單詞的主題分布越稀疏就能越清晰的反映出單詞的主題意義，在模型參數(shù)估計和推理的過程中增加稀疏限定可以提高模型的精度。稀疏主題編碼（Sparse Topical Coding，STC）[2]是發(fā)現(xiàn)大規(guī)模文本集隱藏表示的非概率主題模型，與概率主題模型不同，STC松弛了混合比例和最大似然函數(shù)的標(biāo)準(zhǔn)化限定，使用稀疏規(guī)則化的方法直接控制推斷表示的稀疏性，無縫地結(jié)合凸誤差函數(shù)到監(jiān)督學(xué)習(xí)中，有效地學(xué)習(xí)半監(jiān)督結(jié)構(gòu)化的條件下降算法。稀疏編碼的潛在狄利克雷分配（SCLDA）[3]是一個加入稀疏限定的基于連續(xù)特征的主題模型，假定連續(xù)單詞的概率分布是拉普拉斯分布，該分布的參數(shù)依賴于主題，使用期望最大化（Expectation Maximization,EM）算法估計模型參數(shù)，該模型在計算機視覺問題中取得了不錯的效果。稀疏隱藏語義分析（Sparse Latent Semantic Analysis,SLSA）[4]在L1范數(shù)約束的條件下產(chǎn)生了一個稀疏投影矩陣。與傳統(tǒng)的LSA 相比，SLSA 緊緊選擇每個主題的少數(shù)幾個單詞，提高了主題-單詞分布的可解釋性，在內(nèi)存和效率上也有相應(yīng)改進。變分貝葉斯（Variational Bayes，VB）[1]、塌陷吉布斯采樣法（Collapsed Gibbs Sampling，GS）[5]以及消息傳遞算法（Belief Propagation，BP）[6]是LDA 的三種近似推理算法。BP 算法把計算全局積分的過程分散到各個節(jié)點的信息傳遞，而各個節(jié)點和鄰近節(jié)點交互信息，它在效率和準(zhǔn)確率上都明顯優(yōu)于VB 和GS 算法。本文的研究是在消息傳遞算法的基礎(chǔ)上進行的。

LDA 模型的先驗參數(shù)可以在一定程度上控制文檔-主題分布和主題-單詞分布的稀疏度，然而因概率主題模型的標(biāo)準(zhǔn)化操作而很難獲得稀疏的主題表示。稀疏非負(fù)矩陣分解[7]提供了一個在原來算法基礎(chǔ)上獲得向量稀疏表示的基本框架。本文在前人研究的基礎(chǔ)上，提出了稀疏限定的消息傳遞算法（sparseBP），用基于L1范數(shù)和L2范數(shù)的方法度量向量的稀疏度，在算法的迭代過程中投影單詞在主題上的概率分布到稀疏空間，從而得到特定稀疏度的單詞在主題上的分布。本文也探索了sparseBP 的聚類性能，并把sparseBP 看作是一種降維算法，把文檔在主題上的分布作為libsvm 分類器的輸入探索文本分類準(zhǔn)確率。

2 消息傳遞算法

消息傳遞（Belief propagation,BP）最初被機器學(xué)習(xí)專家用于樹狀結(jié)構(gòu)的統(tǒng)計推斷，后來這種算法忽略掉它本來對樹狀結(jié)構(gòu)的要求而應(yīng)用與帶環(huán)的模型。文獻[1]在馬爾科夫隨機場的框架下證明了在主題模型意義下LDA 是一種特殊的因子圖，并提出用消息傳遞算法近似求解LDA 模型。本文中用到的符號見表1。

表1 符號標(biāo)簽Tab.1 Symbol labels

圖1 基于因子圖的消息傳遞Fig.1 Message passing based on factor graph

這里 -w 表示除了單詞w 以外的所有單詞，-d表示除了文檔d 以外的所有文檔。信息更新式（1）取決于除了當(dāng)前信息μw,d以外的所有其他鄰接信息μ-(w,d)。文檔-主題分布θ 和主題-單詞分布φ 的計算公式為

信息更新過程將通過迭代公式（1），直到信息收斂于一個固定的點。算法的執(zhí)行過程如圖2 所示，算法的迭代過程分為兩個步驟，第一步更新每個單詞的主題分布μw,d,第二步用更新的消息μw,d估計參數(shù)dθ 和wφ 。

圖2 消息傳遞算法Fig.2 Message passing algorithm

3 稀疏消息傳遞算法

本節(jié)首先描述稀疏度的概念，然后介紹如何把稀疏度結(jié)合進LDA 模型的消息傳遞中，最后介紹算法具體執(zhí)行過程。

3.1 稀疏度

向量稀疏度的度量可以用向量中0 元素的數(shù)目與向量維度的比值來計算。對于大部分元素取值接近與0 而只有幾個有意義的非0 值的向量會有一個較低的稀疏度，然而在實際應(yīng)用中，這樣的向量被認(rèn)為有一個較高的稀疏度。本文使用基于L1_norm和L2_norm的稀疏度度量方式[7]

其中K 表示μ 的維度，當(dāng)向量μ 只有一個非0的元素時稀疏度為1，當(dāng)向量μ 的所有元素都相等時稀疏度為0。

3.2 稀疏限定的消息傳遞

消息傳遞算法可以看作是對語料庫中的單詞分配標(biāo)簽的過程，通常每個單詞的主題集合只有小部分是活躍的。在消息傳遞算法的迭代過程中對于單詞-文檔矩陣中的非0 元素都需要通過公式1 來得到單詞的主題分布，這個分布往往是很稀疏的。稀疏度隨著迭代次數(shù)的增加而不斷增加。像“l(fā)earning，paper，algorithm”這樣的常用詞往往有一個較低的稀疏度，而像“network neural genetic”這樣的關(guān)鍵詞有較高的稀疏度。主題模型中主題數(shù)目K 通常是啟發(fā)性的設(shè)置或者是通過非參數(shù)的貝葉斯模型學(xué)習(xí)得到，當(dāng)K 初始設(shè)置的數(shù)目比較大時，常用詞和關(guān)鍵詞的主題分布的稀疏度可能有更大的差距。本文中我們固定主題在單詞分布上的稀疏度，每次迭代得到μw,d后把它投影到與它距離最近的稀疏空間中去，而向量的稀疏度可以自由設(shè)定，通常越稀疏的向量越能清晰的反應(yīng)單詞的主題分布。然后整合出LDA 模型的兩個輸出文檔-主題分布和主題-單詞分布。這種增加稀疏度限定的消息傳遞算法稱為稀疏消息傳遞算法（sparseBP），算法的具體執(zhí)行過程如圖3 所示。

圖3 稀疏消息傳遞算法Fig.3 Sparse message transfer algorithm

投影向量到稀疏度為S 的空間的具體操作如算法3 所示，該算法首先投影給定的向量到L1的空間中，然后投影到與之最接近的由L1和L2聯(lián)合限定的空間中。如果投影結(jié)果完全是非負(fù)的，就退出循環(huán)，而如果有負(fù)值，把負(fù)值設(shè)置為0，然后在額外限定的條件下去尋找一個新的點。原則上，算法的迭代次數(shù)和向量的維度是相等的，因為算法的一次迭代過程或者是收斂，或者是增加一個值為0 的元素。而事實上，算法可以收斂的更快。

3.3 復(fù)雜度分析

消息傳遞算法需要存儲單詞的主題概率分布，在存儲和計算方面都要乘以主題數(shù)目K 的倍數(shù)，消息傳遞算法的時間復(fù)雜度 O (KDWdT)，sparseBP 在BP 算法的基礎(chǔ)上增加了投影操作，sparseBP 的時間復(fù)雜度為 O (K2DWdT)。sparseBP 在投影的過程中增加了幾個維度為K 的向量，然而它的空間復(fù)雜度與消息傳遞算法相同，均為 O (K * NNZ)，其中D 是輸入文檔-單詞共現(xiàn)矩陣的列數(shù)，Wd是共現(xiàn)矩陣每一列中非零單元 xw,d≠ 0的個數(shù)，T 是算法的迭代次數(shù)，NNZ 為單詞-文檔共現(xiàn)矩陣中非0 元素的總數(shù)目。

圖4 投影向量到稀疏度為s 的空間的算法Fig.4 projection vector to the sparse degree s of space algorithm

4 實驗分析

本文的實驗在Matlab C/C++MEX 平臺上進行，這個平臺在文獻[8]中已經(jīng)被使用。先驗參數(shù)初始化設(shè)置為 α=2/K， β=0.01，這里K 是主題的數(shù)目，對于所有的算法分別做300 次迭代并運行5 次計算其均值。每篇文檔中單詞的概率分布μw,d的稀疏度S 在0.7～0.9 之間變化時，效果基本一致，這里固定S 為0.8。本文采用標(biāo)準(zhǔn)化互信息來評估文檔聚類的準(zhǔn)確率，并使用常用的聚類方法BP，GS，非負(fù)矩陣分解（Non-negative Matrix Factorization,NMF）[9]，譜聚類（Spectral Clustering,SC）[10]來進行對比。此外，使用消息傳遞算法對文檔-單詞共現(xiàn)矩陣進行降維，并借助于libsvm 測量文本的分類準(zhǔn)確率，使用BP，GS 和NMF 來和sparseBP 進行對比。在評價sparseBP 在文檔聚類和分類中相比其它算法提高的百分比時本文采用的計算公式為：

4.1 數(shù)據(jù)集選擇

本文在英文語料上進行測試，采用CORA[11]和TEUTERS[12]兩個通用的文本數(shù)據(jù)集進行實驗。實驗所用文本數(shù)據(jù)如表1 所示，這里D 是文檔的總數(shù)目，W 是單詞表的大小，N 是文檔中單詞的總數(shù)目，Ave( d) 是文檔的平均長度，classes 是文檔集中文檔的類別數(shù)目。文檔去除了停用詞以及單詞的后綴，采用1-Gram 的表示法，使用單詞在文檔中出現(xiàn)的次數(shù)作為文檔的特征。

表2 數(shù)據(jù)集Tab.2 Data sets

4.2 文檔聚類分析

稀疏消息傳遞算法可以用來做文本聚類，算法得到文檔在主題的分布 θd(k)是文檔在主題上的概率分布，在模型的訓(xùn)練過程中不使用數(shù)據(jù)真實的類別標(biāo)簽，得到 θd(k)后選出每篇文檔最可能的主題，并使用標(biāo)準(zhǔn)化互信息評估算法的聚類準(zhǔn)確率。

4.2.1 聚類評價標(biāo)準(zhǔn)

標(biāo)準(zhǔn)化互信息（Normalized Mutual Information,NMI）[13]是一種被廣泛應(yīng)用的外部聚類評價標(biāo)準(zhǔn)，通過比較數(shù)據(jù)集的聚類結(jié)果和該數(shù)據(jù)集的真實劃分的相似程度來實現(xiàn)，而在聚類過程中不使用文檔的類別標(biāo)簽。NMI 可以在預(yù)測類別和真實類別不同時利用互信息進行評測，NMI 的計算公式為：

式中，hn 是類別為h 的文檔的總數(shù)目，ln 是類別為l的文檔的總數(shù)目，nh,l是同時為類別h 和l 的文檔的總數(shù)目，n 是數(shù)據(jù)集中文檔的總數(shù)目，h 是真實的類別標(biāo)簽，l 是用聚類算法得到的預(yù)測類別標(biāo)簽。NMI 是介于0～1之間的值，當(dāng)聚類標(biāo)簽和外部真實標(biāo)簽完全一致時NMI 值為1，而當(dāng)隨機劃分時NMI值為0，NMI 值越大表示有越好的聚類準(zhǔn)確率。

4.2.2 聚類實驗結(jié)果

圖5 和圖6 分別表示了當(dāng)主題數(shù)目K={50,75,100,125,150}時5 種算法在CORA 和TEUTERS 數(shù)據(jù)集上的NMI。從圖中可以看出，在兩個數(shù)據(jù)集上sparseBP 的NMI 都是最好的，勝過了其它的文本聚類方法，例如，在CORA 數(shù)據(jù)集上，當(dāng)主題數(shù)目為100 時，sparseBP 勝過其它四種方法分別為3.67%，9.68%，32.21%和60.18%。結(jié)果表明稀疏消息傳遞算法提高了文檔聚類的準(zhǔn)確率。

圖5 CORA 數(shù)據(jù)集上的NMI 比較Fig.5 NMI comparison on CORA data sets

圖6 TEUTERS 數(shù)據(jù)集上的NMI 比較Fig.6 NMI comparison on TEUTERS data sets

4.3 文檔分類分析

首先使用sparseBP 把語料庫中的文檔-單詞矩陣投影到隱藏主題空間當(dāng)中得到文擋-主題分布，然后以4：1 的比例隨機劃分低維的文檔特征數(shù)據(jù)為訓(xùn)練集和測試集，最后根據(jù)已知文檔的類別標(biāo)簽使用libsvm 分類器去分類文檔。在使用libsvm 分類時，采用網(wǎng)格搜索法學(xué)習(xí)參數(shù)C 和G。

4.3.1 分類評價標(biāo)準(zhǔn)

準(zhǔn)確率（Accuracy）是評價文本分類結(jié)果優(yōu)劣的一種常用評價標(biāo)準(zhǔn)，其計算公式為：

Accuracy 是介于0%～100%之間的值，越高的類別準(zhǔn)確率暗示基于主題的低維特征具有越好的區(qū)分能力，即在降維的過程中提取到了高質(zhì)量的文檔特征。

4.3.2 分類實驗結(jié)果

圖7 和圖8 分別顯示了當(dāng)主題數(shù)目K={50,75,100,125,150}時5 種算法在CORA 和TEUTERS 數(shù)據(jù)集上的Accuracy。從圖中可以看出sparseBP 總是有最好的分類準(zhǔn)確率，例如，在CORA 數(shù)據(jù)集上，當(dāng)主題數(shù)目為100 時，sparseBP 勝過BP，GS 和NMF分別為3.81%，8.21%和14.03%。在RETURE 數(shù)據(jù)集上，當(dāng)主題數(shù)目為100 時，sparseBP 勝過BP，GS 和NMF 分別為1.83%，1.73%和0.18%。譜聚類不能獲得文檔-主題這樣的分布，于是這里沒有相關(guān)對比結(jié)果。

圖7 CORA 數(shù)據(jù)集上的Accuracy 比較Fig.7 Accuracy comparison on CORA data sets

圖8 TEUTERS 數(shù)據(jù)集上的Accuracy 比較Fig.8 Accuracy comparison on TEUTERS data sets

5 結(jié)束語

本文提出了把稀疏限定加入到消息傳遞算法中，在迭代的過程中將向量投影到稀疏空間中去，同時也探索該方法對文本聚類以及分類準(zhǔn)確率的影響。豐富的實驗結(jié)果表明本文提出的加入基于 L1范數(shù)和L2 范數(shù)的稀疏消息傳遞算法提高了文本的聚類以及分類準(zhǔn)確率。進一步的研究工作將主要圍算法在其它方面的應(yīng)用以及時間效率的因素開展，以便使算法適應(yīng)于更多的應(yīng)用并提高算法的執(zhí)行效率。

[1]David M.Blei,Andrew Ng and Michael Jordan,Latent Dirichlet Allocation[C].Neural Information Processing Systems,2001:601-608.

[2]Jun Zhu and Eric P.Xing.Sparse Topical Coding[C].Uncertainty in Artificial Intelligence,2011:267-286.

[3]Wenjun Zhu,Liqing Zhang and Qianwei Bian.A hierarchical latent topic model based on sparse coding[J].Neuro Computing,2012,76(1):28-35.

[4]Xi Chen,Yanjun Qi,Bing Bai,Qihang Lin and Jaime G.Carbonell.Sparse latent semantic analysis[C].SIAM International Conference on Data Mining,2011:474-485.

[5]Gregor Heinrich.Parameter Estimation for Text Analysis[R]. Fraunhofer IGD,2004.

[6]Jia Zeng,William K.Cheung,Jiming Liu,Learning topic models by belief Propagation[J],IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,33(5):1121-1134.

[7]Patrik O.Hoyer.Non-negative Matrix Factorization with Sparseness Constraints[J].Journal of Machine Learning Research,2004,5(1):1457-1469.

[8]Jia Zeng.A topic modeling toolbox using belief propagation[J],Journal of Machine Learning Research,2012,13(1) 2233-2236.

[9]Daniel D.Lee and H.Sebastian Seung.Algorithms for non-negative matrix factorization[C],Neural Information Processing Systems,2002:556-562.

[10]Ulrike Luxburg.A Tutorial on Spectral Clustering[J].Journal Statistics and Computing,2007,17(4):395-416.

[11]Andrew McCallum,Kamal Nigam,Jason Rennie and Kristie Seymore.Automating the construction of internet portals with machine learning[J].Information Retrieval,2000,3(2):127-163.

[12]Deng Cai,Xiaofei He,Jiawei Han.Document clustering using locality preserving indexing[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(12):1624-1637

[13]Shi Zhong and Joydeep Ghosh.Generative modelbased document clustering:a comparative study[J].Knowledge and Information Systems,2005,8(3):374-384.