基于非參貝葉斯的網絡文檔鏈接模型研究

黃大君，王大剛，吳 昊

(合肥師范學院 計算機學院，安徽 合肥 230601)

1 概述

文檔鏈接分析在社交網絡、搜索引擎、超鏈接網絡方面有著廣泛的應用。利用預測模型可以將網絡成員指向新朋友，將科學論文指向相關引用，并將網頁指向其他相關頁面。國內外學者在這個領域相繼提出了許多模型，比較具有代表性的模型是Airoldi等人2008年提出的MMSB[1]模型和主題模型[2-3](Laten Dirichlet Allocation,LDA)。主題模型為這個領域奠定了一個理論框架，為文檔之間的相似性引入主題語義層次奠定了基礎。LDA話題模型可以通過推斷的隱藏結構來組成文檔的主題結構。LDA和其他一些話題模型從屬于概率建模領域之下。概率建模領域下生成過程定義了一個在已觀測隨機變量和隱藏隨機變量之上的聯合概率分布，通過使用聯合概率分布來計算給定觀測變量值下的隱藏變量的條件分布。

在LDA模型中，假定文檔看成是在主題上的分布，而主題又看成是在相應單詞上的分布。LDA是一個層次概率模型，主題分布在一個固定的詞匯表上來描述一個文檔的語料庫。在其生成過程中，每個文檔都被賦予一個Dirichlet[4-6]分布的主題比例向量，文檔中的每個單詞都是通過從這些比例繪制主題分配，然后從相應的主題分布中繪制出單詞來繪制的?；贚DA模型的視角，科研人員將該模型的各種變種加以擴展，MMSB模型是應用于社交網絡、超鏈接網絡中的一個典型基本框架，該框架基于LDA的理論基礎框架，定義社區中節點的交互關系與概率生成關系。MMSB模型為了促進節點與社區之間的一對多關系，每個節點都有自己的“混合成員分布”，其中與所有其他節點的關系由其分布向量來表征，這個方法描述了扮演多個角色的對象之間的交互。在MMSB框架下，描述性統計可以揭示網絡數據集隱藏的社區結構。

在這之后的研究中，針對文本挖掘、超鏈接網絡領域中又涌現出很多的具體的概率模型結構。關系主題模型[7](Relational topic model，RTM)由M. BLE于2010年提出用于文檔挖掘的模型，該模型兼顧文檔的屬性信息和鏈接信息，對新文檔可能的鏈接進行預測，針于每一對文件，RTM將其鏈接建模為一個二進制隨機變量，并以其內容為條件，預測它們之間的聯系，并預測其中的文字。RTM是網絡和每節點屬性數據的分層模型。 RTM用于分析鏈接的語料庫，如引用網絡，鏈接的網頁，社交網絡與用戶配置文件，以及地理標記的新聞?！癙airwise Link-LDA”是Nallapati[8]等人2008年提出的模型，它是混合隸屬隨機塊模型的擴展，來建模網絡結構和節點屬性。模型假定每個鏈接都是根據兩個單獨的主題生成的從與鏈接的端點關聯的主題比例向量中選擇，因為潛在的話題和鏈接是在這個模型中獨立繪制的，所以不能保證發現的話題同時代表了話語和鏈接，模型結合了LDA和MMSB(Mixed Membership Stochastic Block )隨機模型的思想，并允許建模任意鏈接結構，提出了一個新的折中方案，它結合了這兩個模型的最佳性質，也明確地模擬了引用文獻和被引用文獻之間的依賴關系。此外，該模型為每個鏈路引入了附加的變化參數，增加了計算復雜度。

以上模型都建立在固定主題數為K的基本假定上，但實際上文檔的主題是很難預先確定的，固定主題的假定與事實是不相符合的。以上模型要么側重利用內容信息預測鏈接信息，要么利用鏈接信息預測內容。在RTM模型中利用主題信息和鏈接共同建模，但建模過程比較復雜，需要假定預測數據的形態分布信息，實際匹配過程往往也很難做到。

本文重點關注網絡文檔鏈接預測和主題分析，假定文檔結構基于混合成員文件模型的基礎，每個文檔都是相關主題上的混合成員分布，都展示了多項分布或主題的潛在混合。最后我們推導出基于M-H[16-23]的推理和估計算法。并利用實驗評估NTM在科學摘要網絡，網絡文件上的預測性能。

2 概率圖模型和生成模型

2.1 非參貝葉斯模型分層Dirichlet過程(HDP)

基于LDA模型的簡單參數設定，模型中的主題和單詞的分布均是簡單的概率分布。HDP 過程是Dirichlet過程混合模型的多層形式，HDP模型相比較LDA 不僅能實現聚類和推斷等功能，而且能夠自動生成聚類數目，比如我們在使用聚類方法k-means時，需要指定k的值(聚成k個簇)；在使用LDA時需要指定主題的數目k，但通過HDP這種非參方法，可以不指定k，而是通過數據學習，自動獲取k值，這樣能夠大大增強算法的魯棒性。HDP是一種非參貝葉斯模型，是隨機過程的應用。HDP從一個隨機測度[22]空間中抽樣，首先以基分布H和Concentration 參數λ構成Dirichlet過程，G0～DP(λ,H)，而后以G0為基分布，以α0為Concentration 參數，對每對數據構造Dirichlet過程混合模型，Gj～DP(α0,G0)。依據該層Dirichlet過程為先驗分布，構造Dirichlet過程混合模型。從Dirichlet過程的定義中很難采樣，通?？梢酝ㄟ^Stick-breaking 過程和Chinese restaurant franchise(CRF)兩種方法進行構造， DP 過程的定義：β|γ～GEM(γ),πj|α0,β～DP(α0,β)

(1)

2.2 關系主題模型(RTM)

在RTM中，每個文檔首先由LDA中的主題生成。 然后將文檔之間的鏈接建模為二進制變量，每對文檔一個。 這些二進制變量分配取決于用于生成每個構成文檔的主題。 由于這種依賴性，文檔的內容在統計上與它們之間的鏈接結構相關。 因此，每個文檔的混合成員都取決于文檔的內容以及鏈接的模式。 反過來，其成員資格相似的文件將更有可能在模型下鏈接。該模型在MMSB塊的基礎上，把文檔的結構和文檔的主題內容結合在一起，共同訓練模型，以達到更好的預測未知文檔的鏈接情況。在RTM模型中，作者使用一般廣義指數分布簇建立主題和分布之間的關系。建立如下關系：yd,d′|zd,zd'∝φ(.|zd,zd',η) 。其中φ定義為鏈接密度函數，該函數根據不同數據集的分布形態分別用正態、指數、對數等概率密度來表達。節點d和d’模如果存在鏈接關系，則yd,d′=1。η用于構造一般指數分布族。模型的概率過程和實際的訓練采樣過程都比較復雜，且實際操作過程中很難根據待預測的未知數據源來確定具體的指數簇分布類型。

3 基于非參貝葉斯的文檔關系模型( NTM)

3.1 NTM模型概率圖和生成模型

HDP是DP過程的兩層形式，本文之所以選擇兩層HDP作為先驗概率分布，考慮到網絡文檔中任意兩個節點共享原子節點，即同一文檔可能屬于不同的文檔集，不同文檔集共享文檔原子節點，所以從HDP模型的第二層采樣，以便文檔能夠共享原子主題。假定分布不再從一個有限的的主題數為K的分布中采樣，從HDP的第二層采樣，進而引入非參假定。為了使得模型能夠針對一般的未知的數據源進行預測，還需要對模型進行一定程度的簡化和假設?；诓蓸拥玫降闹黝}分布向量，計算文檔之間向量的余弦夾角。利用這個相似值作為鏈接文檔之間相似性的基本度量單位，該值大小能夠從語義上表示文檔間的相似性大小的相關關系。該值作為文檔間鏈接的語義關聯依據，我們認為相似度大的文檔之間，鏈接的可能性越大，隨后在概率圖的基礎上，利用貝葉斯關系，通過數據來學習分布參數。

圖1 NTM概率圖模型

此處的{πi}1:n為混合成員分布，網絡中單個文檔可能具有屬于多個文檔集的屬性，如同一個人可以參加多個社區活動，即同時具有屬于多個社區的屬性。其中{πi}1:n的先驗概率分布存在以下關系:

(2)

從隨機側度中采樣出來的{πi}1:n是個K維的Dirichlet向量，反映網絡數據集中的文檔的主題分布，對向量求余弦夾角得到它們之間的相似度，這個值大小與未來兩個文檔間可能存在的鏈接關系存在某種程度的正相關，定義函數f，對f進行二值采樣，利用數據來學習模型。

NTM生成模型表示如下:

β～GEM(γ)

Zd,n|πd～mul(πd)

y|πd,πd′～bernoulli(f)

cos(πd,πd′)∈(0,1)

(3)

3.2 NTM模型的參數采樣

3.2.1 采樣πi

定義轉移概率為獨立鏈方式

經整合后，消元

(4)

3.2.2 采樣

β的先驗p(β/γ)=GEM(γ)， 在文獻[14]中指出，通過增加輔助變量得到：

可以增加接下來的接受率：

其中p(mik=m|Nik,α,βk)∝S(Nik,m)(αβk)m

S(Nik,m)為第一類Stirling 數。

定義:Α(β，β*)=min(1,a)

提議分布采樣獨立鏈方式得到：

(5)

這樣得到采樣β的接受率:

(6)

3.2.3 采樣Ζd,n,Ζd′n

推導出Ζd,n，Ζd′n的適合Gibbs采樣的條件概率。

p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},W,α,β,η,y)=p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},α,β)

p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},W,α,β,η,y)=p(zd,n=k,zd′,n=l|Z{zd,n=k,zd′,n=l},α,β)

*p(Wd,n,Wd′,n|W{Wd,n,Wd′,n},(zd,n=k,zd′,n=l),Z{zd,n=k,zd′,n=l},η}

*p(yd,d'|(zd,n=k,zd′,n=l),Z{zd,n=k,zd′,n=l},α,β,y{yd,d′})

p(Wd,n,Wd′,n|W{Wd,n,Wd′,n},(zd,n=k,zd′,n=l),Z{zd,n=k,zd′,n=l},η}

p(yd,d'|(zd,n=k,zd′,n=l),α,β)

∝p(yd,d'|(πd=k,πd′=l),α,β)

(7)

4 實驗結果與分析

4.1 RTM模型和NTM模型比較

本文采用基于鏈接與文本屬性的數據集CiteSeer來發現和對比UTM和RTM模型的鏈接結果和鏈接質量。CiteSeer數據集由3312種科學出版物組成，分為六類中的一種。 引文網絡由4732個鏈接組成。 數據集中的每個出版物由0/1值單詞向量描述，指示字典中相應單詞的不存在/存在。 該詞典由3703個獨特單詞組成。該目錄包含CiteSeer數據集的選擇。這些論文集由六個類別組成，包括人工智能，數據挖掘 ，數據庫，模式識別等。這些論文的選擇方式使得在最終的語料庫中，每篇論文引用或引用至少另一篇論文。整個語料庫在阻止和刪除停用詞后，留下了3703個獨特單詞的詞匯量。文檔頻率小于10的所有單詞都被刪除。在CiteSeer運行本文的模型和RTM模型，對數據集采用10倍交叉驗證，對其中一個驗證集，運行模型得到圖3和表3的結果。

實驗環是Win7系統，Python 2.7編程環境。采樣過程的提議分布采用獨立鏈的方法，所以必須選擇合適的迭代次數和步長，經過對多次試驗結果的觀察和嘗試，對迭代次數選擇14000，迭代的步長設置為0.5，保證能夠在有限次迭代次數和時間下得到比較好的仿真圖，圖2 是仿真的結果圖。運行MCMC采樣器過程中，一般而言，不希望寬度過窄，因為抽樣效率不高，同時需要很長時間才能探索整個參數空間并顯示典型的隨機游動行為，但也不希望它太大，以至于永遠不會接受跳躍。圖2是RTM模型和NTM模型在似然函數上比較圖，將提案寬度設置為0.5?？梢钥吹絅TM模型收斂的似然值要高于RTM模的似然值。

圖2 RTM模型和NTM模型在似然函數上比較圖

表1 RTM模型和NTM模型鏈接預測表現

在6大類文章類型中，其中10個主題作為模型比較范圍，選擇訓練集中的Dynamic Infinite Mixed-Membership Stochastic Blockmodel文檔，表3的結果是模型測試集上前6個鏈接預測表現，從表1中可以看出UTM模型識別出來的有效文檔是3個，相比RTM模型識別的有效文檔是2個。針對本次發現可以看出，UTM模型能夠準確把握關鍵詞Mixed-membership，能夠在整個文本潛在空間上發現語義關聯。注意觀察RTM的部分結果，給出的建議鏈接是針對文檔題目的字典單詞相似度而非在整個引文數據庫中的結構語義。一般而言，您不希望寬度過窄，因為您的抽樣效率不高，因為需要很長時間才能探索整個參數空間并顯示典型的隨機游動行為，但你也不希望它太大以至于你永遠不會接受跳躍。

4.2 多數據源綜合實驗

用不同的模型在相同的仿真數據集上做出了部分定性和定量的比較分析，在實際網絡實驗數據集中，需要對不同算法在不同數據集上的表現性能做全面的分析，從而判斷算法的優越性。選擇3個真實世界數據集進行基準測試。分別是 Cora、WebKB、PNAS。Cora數據包含來自Cora計算機科學研究論文搜索引擎的摘要，以及相互引用的文檔之間的鏈接。WebKB數據包含來自不同的大學計算機科學系的網頁，網頁上的超鏈接關系標注了網頁文檔間的鏈接。PNAS數據包含來自美國國家科學院院刊的最新摘要，文件之間的鏈接是PNAS內部引用。

表2 數據集的統計摘要

將MMSB，RTM，本文的NTM算法，在三個實際數據集上驗證，其中MMSB，RTM算法利用所給文獻公布的代碼進行仿真，三個數據集上檢查了“和”“的”或“但是”這樣的詞，以及不經常出現的詞被刪除。定向鏈接轉換為無向鏈接，沒有鏈接的文檔被刪除。

表3 各模型性能比較

其中Train err和Test err的值是1000迭代的結果的平均值，發現在迭代過程中，Train err的值隨著發現聚類個數K的值有比較平穩的變化，Test err的值有降低的變化趨勢。 算法在數據集WebKB 上的Train err 的值表現比其它算法較差，原因大概是由于WebKB在數據量較小時，部門之間的相關性表現較差，NTM的相關性發現不能充分有效。而我們的值是前1000次的平均，所以可看到整體表現較差。表3中NTM算法的Test loglikelood 相比其他算法有非常明顯優勢，原因應該是采用了非參的假定，數據根據自身的表現在迭代過程中自動發現聚類的K值，從而對數據集中的數據來說能夠獲得較大的數據似然值的支持，而其它三種算法都是基于固定值的假設，所以實際聚類值與假定的一定存在差距，從而導致較差的Test loglikelood(表中采用的是負對數值)。AUC 值通常小于0.7是比較差的，大于0.9是比較好的結果，從表3的結果來看，NTM在三個數據集上都取得了較好的效果。從訓練誤差，測試誤差，測試用例的對數似然和AUC四個指標上對上述3種模型進行對比分析，從表3中可以看出整體上分析來看，在全部三個數據集上NTM比其它兩個模型都有更好的性能表現。

5 總結

模型在社交網絡和文本關系發現領域有重要的應用價值，本文定義了一個非參數的概率圖模型，將非參數貝葉斯先驗(即DP過程的先驗假定)結合到模型中將允許它靈活地調整主題數量與數據。模型綜合考慮節點的主題和鏈接信息，定義聯合分布，給出了一個MCMC框架的參數推理算法，合成數據集和現實世界數據集實驗證明了我們的方法能夠推斷出隱藏的主題及其數量，相比已有模型能夠更好的進行未知文檔和潛在鏈接結構的預測，提供有關網絡潛在成員結構的新見解。在參數推理中，給出了具體的推理步驟和推理算法。