一種基于LDA 的k話題增量訓練算法

辛 宇，楊 靜，謝志強

（1.哈爾濱工程大學 計算機科學與技術學院，哈爾濱150001；2.哈爾濱理工大學 計算機科學與技術學院，哈爾濱150080）

0 引 言

LDA（Latent dirichlet allocation，LDA）模型是近些年來話題提取的通用模型［1］。目前，話題模型相關的工作大多是對LDA 模型進行修改，或者是將LDA 模型作為整個概率模型的一個部件。在LDA 模型中，假設每個文檔的主題概率分布服從Dirichlet分布，并沒有對不同主題之間相關性進行刻畫。然而，在真實的語料中，不同主題之間存在相關性的現象很普遍［2］。

在面向LDA 模型演化研究方面，2004 年，Blei 等［3］提 出 了 主 題 間 為 樹 結 構 的 層 級（Hierarchical LDA）。在該模型中，樹中的每個節點代表一個主題，該模型還有一個特點是可以從語料中估計出主題的個數，并與使用LDA 模型在不同主題數下重復實驗得到的最佳主題個數一致。Blei等［4－5］于2006年又在層級LDA 的基礎上提出了相關主題模型（Correlated topic model，CTM），與LDA 不同的是，CTM 從對數正態分布中對主題概率分布進行采樣。Li等［6］針對CTM 只考慮兩個主題間關系的不足，提出了PAM 模型（Pachinko allocation model，PAM），該模型的特點是把主題之間的關系表示成一個有向無環圖，其中葉子節點是單詞，可以看成是由所包含的子節點（主題或單詞）構成。之后Mimno等［7］又在PAM 的基礎上提出了層級PAM 模型，該模型可以看成是把層級LDA 和PAM 結合起來，使得PAM 模型中的非葉子節點也具有單詞的概率分布。Wang等［8］向模型中添加了一個作為觀測值的時間隨機變量后得到了主題隨時間變化的主題模型（Topic over time，TOT），該模型認為主題概率分布受到時間信息的影響，且時間變量服從beta分布。

在面向上下文信息分析的話題提取方面，通常主題模型假設單詞序列中的單詞是可交換的，即單詞的順序和模型的訓練結果無關，在考慮當前節點和其他節點的關系時，就破壞了LDA 的可交 換 性 假 設。Griffiths 等［9］認 為 可 以 通 過HMM 來捕捉句法結構信息，通過LDA 來提示語義關系，并將兩者結合在一起提出了HMM－LDA模型。Wallach［10］認為語料庫生成過程中，一個單詞除了依賴于其對應的主題外還與前一個單詞有關，提出超越詞袋（Beyond bag－of－words）的主題模型。張晨逸［11］等人提出利用MB－LDA 進行微博主題挖掘，該模型在挖掘出微博主題的同時還可挖掘出聯系人關注的主題，并將LDA 模型推廣到了社交網絡中。韓曉暉［12］等人提出了一種基于LDA 的低質量回貼檢測方法，利用檢測回貼質量的二元分類性訓練SVM 分類器，以區分出質量回貼。

在面向特定任務研究方面，Blei等［13］針對分類問題提出了有監督LDA 模型（Supervised latent dirichlet allocation，sLDA），該模型將訓練語料中的文檔類別標記為觀測值加入LDA 模型，且類別標號服從一個與文檔主題概率分布有關的正態線性分布。Steyvers等［14］提出作者主題模型（Author topic，AT），認為每個作者有一個主題概率分布。McCallum 等［15］又在AT 模型的基礎上，提出了作者接受者主題模型（Author recipient topic，ART）以判定個人的社會角色。

以上模型的話題個數k 均需預先給定，若要確定最優話題個數k＊則需要循環探測，其復雜度過高。文獻［5］和文獻［7］的實驗表明，當k 的個數超過某一數據時，k＊的選擇開始變得模糊，導致LDA 的最優話題個數選擇方法復雜度高且結果不精確。因此，設計一種高效可行的最優話題個數選擇方法是LDA 研究的關鍵問題。本文針對LDA 模型的最優k 值選取問題，提出LDA 話題增量訓練算法，并通過對真實數據集的實驗分析驗證了本文算法對最優k值選取的有效性和可行性。

1 LDA 模型分析

LDA 模型是以單詞－話題－參數先驗關系構成的3層貝葉斯模型，三者之間的關系表達模型如圖1所示，其中M 為語料庫中的文檔個數，N 為單詞表中的單詞個數，zdn為文檔d中單詞n所屬話題的概率，θd為文檔d中話題zdn分布的先驗參數，α為語料庫中θ的全局先驗參數，β為k×N 單詞 －話題概率矩陣，其中k為話題個數，βi，j ＝p（w ＝j｜z＝i）且βi，＊＝1。根據上述條件概率關系，文檔－單詞的數學模型可表示為：

語料庫－單詞的數學模型可表示為：

圖1 LDA“盤子”模型Fig.1 Plate model of LDA

LDA 的生成模型可假設如下：

（1）p（θ｜α）～Dir（α）。其表達式為：

（2）p（z｜θ）～Multinomial（θ）。

根據式（3）（4），式（2）可表示為：

加入文檔內部估計參數γ和φ，γ為β 的文檔樣本估計值，φ 為文檔內部話題的后驗概率，φi，j＝p（z＝j｜w ＝i）。

假設γ和φ 相互獨立。利用變量β和z 建立文檔內部隱含參數的估計模型如下：變分推理以極大化單詞－話題分布的似然函數p（w｜α，β）為目標，通過在似然函數中加入樣本估計參數γ 和φ，實現對全局參數α 和β 的優化。為此，式（5）的似然函數表達式如下：

2 LDA 變分推理過程

2.1 建立變分似然函數表達式模型

式中：Eq為利用估計參數γ 和φ 計算的期望，由于Dirichlet分布屬于一種指數分布族，根據文獻［1］可知：

變分推理的優化過程即尋找L（γ，φ；α，β）的極值過程。根據式（8）可得：

根據式（9）可得：

2.2 變分推理參數關系模型

式（11）包 含 了（α，β，γ，φ）4 個 參 數，其 中利用拉格朗日乘子法對（α，β，γ，φ）進行優化求值可得到如下結果：

式（12）～（15）分別對（α，β，γ，φ）求零值導數可得到（α，β，γ，φ）的極值關系式如下：

2.3 變分推理運行過程

根據式（16）～（19）變分推理的參數訓練過程分為文檔內部參數循環訓練過程（訓練γ，φ）和語料庫總體參數訓練過程（訓練α，β）。文檔內部參數循環訓練過程是語料庫總體參數過程的子過程。圖2為訓練過程的盤子模型圖，其中黃色箭頭線表示文檔內部參數訓練過程，參數γ，φ 根據式（17）和（19）以α，β 為參數進行循環迭代以優化參數γ，φ；棕色箭頭表示語料庫總體參數訓練過程，在語料庫內所有文檔完成對參數γ，φ 的訓練后，根據式（16）和（18）調整全局參數α，β；藍色箭頭表示LDA 模型的似然函數的計算過程。

圖2 LDA變分推理過程Fig.2 Variational inference process of LDA

3 變分推理優化改進策略

LDA 話題提取存在兩方面問題需要改進：

（1）由于LDA 算法在初始運行時需要人為給定話題個數k（較小的整數），k與最佳話題個數k＊的偏離度決定了LDA 話題發現的質量，若k＜k＊會導致話題訓練的欠擬合，若k＞k＊會導致話題訓練的過擬合，如何選擇k值是LDA 話題發現尚未解決的問題。

（2）LDA 在樣本的訓練過程中缺少對β 中“模糊單詞”（即話題歸屬不確定的單詞）的處理，導致β 矩陣中各話題間的模糊化，并使得后續的訓練結果出現相似的話題結果，影響話題分類的有效性。

為說明以上兩方面問題，本文統計了CNN網站中的50組話題，建立了50個樣本話題，并在每組話題中選擇詞頻最高的5個名詞作為樣本話題詞匯，如表1所示。隨機選擇2～5組樣本話題構成文檔，并以1000個隨機文檔為單位，建立40組語料庫。

表1 CNN 50個話題的概率表Table 1 50－topics Probability Table of CNN

3.1 likelihood值分析

本文對40 組語料庫建立10～70 個話題的LDA 跟蹤運算，所得的likelihood值如圖3所示，其中橫坐標為話題個數，縱坐標為likelihood值。由于本文所建立的40組語料庫是50個話題的混合，因此理想狀態下50個話題的likelihood值應為極值，且50個話題的各每組樣本likelihood值的偏差應該較小。但圖3所示的結果說明LDA算法在話題個數大于40時，出現likelihood值的模糊化，無法根據likelihood值判斷最優話題個數k＊。

圖3 表1數據集likelihood值（話題個數為10～70）Fig.3 Likelihood of the datasets in table 1（the number of topics are 10～70）

3.2 β矩陣分析

本文對第1、8、15、22、29、36 組語料庫LDA訓練后的β 值進行分析，由于表1數據集中屬于同一話題的單詞編號鄰近，因此屬于同一話題的單詞在β 矩陣的位置鄰近，可將β 矩陣元素中的最大值進行聚類以分析LDA 的分類效果。β矩陣的聚類輪廓圖如圖4所示，其中x 軸為話題號，y軸為單詞號。由于表1數據集中各樣本話題單詞無重復，因此理想狀態下β 矩陣聚類輪廓圖的每行每列僅有一個話題聚類簇，從圖4中可直觀看到語料庫中第1、8、15、22組數據的LDA 分析結果較差。

另外，圖4中LDA 算法所挖掘出的編號相鄰的話題相似度較大，且有效識別個數最多為40（語料庫36）。為了提高LDA 的話題精度，降低話題間的相似度，本文提出LDA 話題增量訓練算法，在提高話題分類精度的同時增量挖掘優化話題個數k＊。

圖4 語料庫1，8，15，22的β矩陣分析結果Fig.4 βmatrix of corpus 1，8，15，22

3.3 LDA話題增量訓練算法

變分推理的執行過程中，以文檔內部話題－單詞的后驗概率φ 作為α 和β 訓練的中間變量φi，j＝p（z＝j｜w ＝i），若話題個數為k（k＜k＊，k＊為最優話題個數），必存在某一單詞的話題不確定度較高，即φi，＊的熵值entropy（φi，＊）較大，其中某一單詞wi的熵值表達式為：

entropy（φi，＊）是對單詞wi的不確定性度量，entropy（φi，＊）越大則wi的不確定性越高，當前的k個話題對wi的劃分越不合理。此時，可提取entropy值較大的單詞重新組合為一個新的話題，并復用之前的迭代結果。由于話題的增加需要進行一次語料庫總體參數訓練（增加參數α 和β的維數），為此LDA 話題增量訓練算法對參數α和β 的修改如下：

（1）增加β矩陣的維數。引入熵的閾值參數σ，選擇entropy（φi，＊）大于σ的wi構成新的話題，并將新話題按熵值歸一化，加入β矩陣。

（2）增加α 的維數。以新的β 和α 作為初始參數執行新一次迭代。

在LDA 的執行過程中，迭代次數越高參數β和α 的訓練越充分，為防止LDA 話題增量訓練算法在β和α 尚未充分訓練的條件下進行φ 的熵值選擇，導致LDA 訓練不充分而影響話題發現質量，需要在LDA 迭代過程中加入迭代參數c，每進行c次迭代時執行一次LDA 話題增量訓練算法。

圖5為LDA 話題增量訓練算法的參數訓練過程，其中綠色箭頭為LDA 話題增量訓練算法對α 和β 的增量訓練過程。

具體的算法描述如下：

功能：利用LDA 話題增量訓練算法對訓練最優話題個數k＊

輸入：初始話題個數k

輸出：最優話題個數k＊及語料庫參數α和β

4 實驗分析

4.1 CNN 數據集分析

圖6為語料庫13的LDA 迭代跟蹤過程（語料庫13 共進行57 次迭代），從中可以直觀發現LDA 算法對66～70 號單詞“makeup”話題的識別較差，其原因在于LDA 迭代過程中未能在β矩陣中提取“makeup”話題，使得“makeup”單詞的話題隸屬度相對模糊，影響了β 后序訓練過程中對“makeup”話題的識別。

本文利用大量模擬實驗驗證了LDA 話題增量訓練算法參數的有效范圍分別為σ ＝（0 ～1.6），c＝（3～12），并在4.3節分析了參數σ和c的最優取值問題，圖7為利用本文LDA 話題增量訓練算法（以10為初始k值，σ＝0.3，c＝5）對語料庫13的增量迭代過程，該圖直觀顯示了話題個數從10增量訓練到50的過程中，話題間的獨立逐漸增強，相比于圖6中LDA 話題增量訓練算法更趨于理想狀態。

圖6 語料庫13的LDA迭代跟蹤過程Fig.6 LDA iterative tracking process of corpus 13

圖7 語料庫13的LDA跟蹤過程Fig.7 LDA tracking process of corpus 13

圖8 為40 組語料庫在本文算法下的likelihood值（以10為初始值，σ＝0.3，c＝5），該圖顯示了本文算法的最佳話題發現個數集中在40～50之間。

圖8 表1數據集LDA話題增量訓練算法下的likelihood值Fig.8 Likelihood of the dataset in Table 1by the LDA topic increments training algorithm

4.2 真實數據集對比

在數據集的選擇方面，本文采用有明確文檔分類的數據集，以分析本文算法對話題個數選取的有效性，本文分別選取了自然語言處理中常用的3組數據集，各數據集的介紹如下：

（1）所選擇的數據庫包括第36屆加拿大國會記事錄Aligned Hansards of the 36th Parliament of Canada（AHPC）a卷（共40個議案）和b卷（共40個議案），總單詞量約為1 300 000個。將每個議案的章節作為LDA 分析的“文檔”，由于同一議案趨近于同一話題，因此該數據集的理想話題個數均為40。

（2）蘭卡斯特新聞書籍語料庫The Lancaster Newsbooks Corpus，本文算法取其中25 類（500本書）書籍為數據集，以每本書的摘要作LDA 分析的“文檔”，由于同一類書籍的新聞話題近似，因此該數據集的理想話題個數為25。

（3）路透社經典文檔分類語料庫Reuters 21578 Classic text categorization corpus（共50類），以每本書的摘要作LDA 分析的“文檔”，該數據集已將各文檔進行了分類，因此該數據集的理想話題個數為50。

本文算法對上述數據分別利用LDA 和LDA話題增量訓練算法（σ＝0.3，c＝5）進行40次實驗，其對比結果如圖9所示，其中藍色為LDA 算法的分析結果，紅色為本文算法的分析結果，從結果可直觀判斷本文算法的likelihood 高于LDA算法，驗證了本文算法的話題分類合理性高于LDA 算法。在話題個數識別方面，各組數據的話題個數分別為40、45、23、55，接近于理想話題個數。

圖9 4種語料庫likelihood對比圖Fig.9 Comparison chart of 4corpuses

4.3 參數σ 和c 分析

本文利用LDA 話題增量訓練算法對第36屆加拿大國會記事錄Aligned Hansards of the 36th Parliament of Canada（AHPC）a卷（共40個議案）作為數據集進行200次迭代，每次迭代進行15次實驗，其中參數分別為σ ＝（0.1∶0.1∶1.5），c＝5，每次將話題個數收斂于38～42的結果判定為正確（共有1036次正確分類），其統計直方圖如圖10（a）所示。以AHPC數據集進行200次迭代，每次迭代進行8次實驗，其中參數分別為σ＝0.3，c＝（3∶1∶10），每次將話題個數收斂于38～42 的結果判定為正確（共有966 次正確分類），其統計直方圖如圖10（b）所示。通過圖10（a）與（b）的分析可知：當σ＞1.5時分類的趨于無效，且c 的 最 優 取 值 區 間 為（3，10）。圖11 為AHPC的三維stem 圖，其中LDA 話題增量訓練算法的最優值為σ＝0.45，c＝6。

圖10 AHPC數據集統計直方圖Fig.10 Histogram of AHPC dataset

圖11 AHPC的三維stem 圖Fig.11 3Dstem figure of AHPC

5 結 論

本文利用LDA 話題增量訓練算法，創新采用以單詞－話題概率熵值作為LDA 迭代過程中模糊單詞選擇標準，將所選擇模糊單詞歸入新的話題優化LDA 的迭代過程，以提高話題獨立性為手段提高各單詞的合理化分類；所提出的LDA話題增量訓練算法可在實現LDA 話題分類優化的同時對最優話題個數k 進行增量訓練，最后通過實驗對比驗證了本文算法在話題分類合理度likelihood與k自動選擇方面的優越性，對深入研究話題分類模型具有一定的理論和實際意義。

［1］Blei D M，Ng A Y，Jordan M I.Latent dirichlet allocation［J］.Journal of Machine Learning Research，2003，3：993－1022.

［2］徐戈，王厚峰.自然語言處理中主題模型的發展［J］.計算機學報，2011，34（8）：1423－1436.Xu Ge，Wang Hou－feng.The development of topic models in natural language processing［J］.Chinese Journal of Computers，2011，34（8）：1423－1436.

［3］Blei D M，Griffitchs T L，Jordan M I，et al.Hierarchical topic models and the nested Chinese restaurant process［C］∥Advances in Neural Information Processing Systems 16.Cambridge，MA：MIT Press，2004：17－24.

［4］Blei D M，Lafferty J D.Correlated topic models［C］∥Advances in Neural Information Processing Systems 18.Cambridge，MA：MIT Press，2006.

［5］Blei D，Lafferty J.A correlated topic model of science［J］.Annals of Applied Statistics，2007，1（1）：17－35.

［6］Li W，McCallum A.Pachinko allocation：DAGstructured mixture models of topic correlations［C］∥Proceeding of the ICML.Pittsburgh，Pennsylvania，USA，2006：577－584.

［7］Mimno D，Li W，McCallum A.Mixtures of hierarchical topics with pachinko allocation［C］∥Proceeding of the ICML.Corvllis，Oregon，USA，2007：633－640.

［8］Wang X，McCallum A.Topics over time：a nonmarkov continuous－time model of topical trends［C］∥Proceeding of the Conference on Knowledge Discovery and Data Mining（KDD）.Philadelphia，USA，2006：113－120.

［9］Griffiths T L，Steyvers M，Blei D M，et al.Integrating topics and syntax［C］∥Advances in Neural Information Processing Systems 18.Vancouver，Canada，2004.

［10］Wallach H.Topic modeling：beyond bag－of－words［C］∥Proceeding of the 23rd International Conference on Machine Learning.Pittsburgh，Pennsylvania，2006：977－984.

［11］張晨逸，孫建伶，丁軼群.基于MB－LDA 模型的微博主題挖掘［J］.計算機研究與發展，2011，48（10）：1795－1802.Zhang Chen－yi，Sun Jian－ling，Ding Yi－qun.Topic mining for microblog based on MB－LDA model［J］.Journal of Computer Research and Development，2011，48（10）：1795－1802.

［12］韓曉暉，馬軍，邵海敏，等.一種基于LDA 的Web論壇低質量回貼檢測方法［J］.計算機研究與發展，2012，49（9）：1937－1946.Han Xiao－hui，Ma Jun，Shao Hai－min，et al.An LDA based approach to detect the low－quality reply posts in web forums［J］.Journal of Computer Research and Development，2012，49（9）：1937－1946.

［13］Blei D M，McAuliffe J.Supervised topic models［C］∥Advances in Neural Information Processing Systems（NIPS）.Vancouver，Canada，2008.

［14］Steyvers M，Smyth P，Rosen－Zvi M，et al.Probabilistic author－topic models for information discovery［C］∥Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Seattle，Washington，2004：306－315.

［15］McCallum A，Corrada－Emmanuel A，Wang X.The author recipient－topic model for topic and role discovery in social networks：experiments with enron and academic email［R］.Technical Report UM－CS－2004－096，2004.