翟社平，郭 琳，高 山，段宏宇，李兆兆，馬 越

1(西安郵電大學 計算機學院，西安 710121)2(西安郵電大學 經(jīng)濟與管理學院，西安 710121)

1 引 言

自Web概念誕生以來，人類先后歷經(jīng)了Doc Web、Social Web、Data Web時期，目前處在Web 2.5階段，隨后將朝著Intelligent Web、Social Machine(Meme Web)的方向發(fā)展，最終達到物聯(lián)網(wǎng)與互聯(lián)網(wǎng)相結(jié)合的萬物互聯(lián)階段(Web 5.0)*http：//blog.memect.cn/?p=3475.2017-06-21/2017-07-06.Web技術(shù)發(fā)展的同時也導致互聯(lián)網(wǎng)的信息過載，這些多源異構(gòu)數(shù)據(jù)及知識的爆發(fā)式涌現(xiàn)，給用戶對所需知識的準確快速定位帶來困難.知識圖譜[1](KG，Knowledge Graph)是圖形結(jié)構(gòu)的知識庫，具有強大的語義表達處理能力和圖結(jié)構(gòu)化展示的優(yōu)勢，可以對海量網(wǎng)絡信息進行合理有序的歸并整理.然而，在Web的迭代更新中仍然夾雜著大量冗余、錯誤以及丟失的數(shù)據(jù)信息.2014年，Linking Open Data云社區(qū)項目提供了1091個互聯(lián)的KG，共包括8×106個實體、188×106個鏈接關(guān)系，目前實體及其關(guān)系仍呈迅猛增長趨勢.盡管如此，在Google Knowledge Vault的核心項目FreeBase中，71%的人沒有“出生地”描述信息，75%的人缺失“國籍”屬性.這對KG的構(gòu)建補全工作產(chǎn)生了負面影響.

針對上述問題，文獻[2，3]提出了TransE模型，該模型利用詞向量在空間中平移不變特性，通過將高維連續(xù)的實體間關(guān)系向低維空間嵌入進行推理預測，從而補全KG.文獻[4]提出一種可擴展的啟發(fā)式框架—基于張量因子分解的隨機語義張量集合(RSTE，Random Semantic Tensor Ensemble)，通過采集KG中語義張量形成集合，進行因式分解來執(zhí)行鏈接預測.文獻[5]基于遞歸神經(jīng)網(wǎng)絡(RNN，Recurrent Neural Network)使用路徑排列算法對KG路徑進行預測推理.文獻[6]將FreeBase15K和WordNet18兩個網(wǎng)絡規(guī)模語料庫結(jié)合建立了特征觀測模型實現(xiàn)預測推理.雖然大多數(shù)模型方法對KG的補全研究工作做出了貢獻，但是在數(shù)據(jù)量急劇增長的Web環(huán)境下仍然顯現(xiàn)出實時更新性差、錯誤信息干擾度高、推理預測準確率低等問題.

本文在對現(xiàn)有KG網(wǎng)絡鏈接預測模型方法進行深入對比分析的基礎上，提出了一種基于貝葉斯推理的KG補全方法.該方法將貝葉斯推理理論與潛在因子模型相結(jié)合實現(xiàn)鏈接預測，通過計算節(jié)點間關(guān)系置信度判斷關(guān)系的可靠性，發(fā)現(xiàn)實體間潛在的關(guān)系預測未來關(guān)系網(wǎng)絡.并對KG的節(jié)點附加注釋信息，利用本體庫的構(gòu)建推理規(guī)則進行KG的預測補全，在信息過載的情況下實時更新圖譜，同時在預測精確度提升和時間開銷減少方面有很好的表現(xiàn).

2 相關(guān)概念

2.1 知識圖譜

KG是以語義Web知識架構(gòu)為基礎發(fā)展而來，本質(zhì)上為語義網(wǎng).KG是知識的一種結(jié)構(gòu)化圖解表示，它由節(jié)點和弧線組成，節(jié)點用于表示實體、概念和情況等，弧線用于表示節(jié)點間的關(guān)系.KG的通用表達方式是一個三元組，即(head，label，tail)，簡記為(h，l，t)，其中head與tail分別表示三元組中的頭實體和尾實體，兩個實體之間的關(guān)系用label做標記，h、t屬于實體集合E(Entities)，l屬于關(guān)系集合R(Relationships)[7]，一個簡單KG示例如圖1所示.

圖1 知識圖譜示例Fig.1 Knowledge graph example

2.2 實體描述語句

資源描述框架(RDF，Resource Description Framework)是語義Web的基本數(shù)據(jù)模型，用來描述Web資源，這里的Web資源與知識圖譜中的實體相對應，RDF語句則采用(主語，謂詞，賓語)的三元組形式.例如將圖1表述成RDF語句如下：

(Bird，rdfs：subClassOf，Animal)；

(Penguin，rdfs：subClassOf，Bird)；

(Tweety，rdf：type，Penguin)；(Tweety，rdf：colour，grey)；

……

而RDF模式(RDFS，Resource Description Framework Schema)則提供了將Web對象組織成層次的建模原語，包括類、屬性、子類、子屬性關(guān)系、定義域(domain)和值域(range)約束.

2.3 貝葉斯網(wǎng)絡鏈接預測

(1)

貝葉斯網(wǎng)絡形式上是一個有向無環(huán)圖(DAG，Directed Acyclic Graph)，節(jié)點表示隨機變量，節(jié)點間的有向邊表示條件依存關(guān)系，箭頭由父節(jié)點指向子節(jié)點.BN將圖形理論的表達和計算能力與概率論有機的結(jié)合，使得其在處理不確定性問題上具有靈活的依賴性拓撲結(jié)構(gòu)，易于理解和解釋、有明顯的語義以及能有效的進行多元信息融合等優(yōu)勢.BN使用概率推理中的先驗概率與后驗概率的方法對不確定問題進行定量的推理預測.

3 方法模型構(gòu)建

3.1 貝葉斯?jié)撛谝蜃幽Ｐ?/h3>

對于一個知識圖譜G，定義實體集εG={h|?(h，l，t)∈G}∪{l|?(h，l，t)∈G}，關(guān)系集RG={l|?(h，l，t)∈G}，知識圖譜中顯式的三元組集合SG=εG×RG×εG，潛在因子用向量ex∈Rk表示，x∈εG表示知識圖譜中的實體，k∈N是一個用戶自定義的超參數(shù).G中實體間有關(guān)系的三元組為可觀測三元組，隱含關(guān)系的三元組集合為SG/G.由于知識圖譜與貝葉斯網(wǎng)絡結(jié)構(gòu)上具有極高的相似性，在對貝葉斯網(wǎng)絡結(jié)構(gòu)的學習過程中所采用的基于打分—搜索算法的基礎上進行改進，提出針對模型中潛在因子的發(fā)現(xiàn)預測算法.該方法的核心思想是對所有的εG與RG中的元素全排列組合，采用潛在因子的發(fā)現(xiàn)算法發(fā)現(xiàn)新的實體關(guān)系，通過對知識圖譜實體添加注釋信息進行屬性判斷并使用概率推理打分函數(shù)確定是否新增關(guān)系邊.貝葉斯?jié)撛谝蜃幽Ｐ褪纠鐖D2所示，以圖書實體為例的屬性矩陣(注釋信息)的添加內(nèi)容如表1所示.

圖2 貝葉斯?jié)撛谝蜃幽Ｐ虵ig.2 Bayesian potential factors model

表1 圖書實體注釋信息Table 1 Book entity comment information

3.2 潛在因子發(fā)現(xiàn)算法

潛在因子發(fā)現(xiàn)算法經(jīng)RDF語句對知識圖譜進行描述，使用RDFS蘊含模式進行推理，同時并行使用BN理論進行概率加強推理，最終依據(jù)打分函數(shù)綜合兩者的推理結(jié)果打分，進而對弧線的增、刪、改做出判定.其中RDFS蘊含模式*http://www.w3.org/TR/REC-rdf-syntax,1999-02-22.定義了一組邏輯蘊含規(guī)則，用于從給定的RDF圖中通過演繹推理出新的正確的RDF語句，從模式中抽取與值域、定義域相關(guān)的蘊含推理規(guī)則，如表2所示.

表2 RDF蘊含推理規(guī)則Table 2 RDF entailment regime

表2表明，如果謂詞aaa有值域(定義域)xxx，實體yyy是謂詞aaa的主語(賓語)，則yyy的類型將歸屬于xxx.由于RDF語句也通過三元組的形式表達，RDF圖與知識圖譜同屬于語義網(wǎng)范疇，故關(guān)于值域、定義域的RDF蘊含規(guī)則同樣適用于知識圖譜推理預測.值域定義域的內(nèi)容來自于KG的實體或采用深度信念網(wǎng)絡(DBN，Deep Belief Nets)方法[8]對數(shù)據(jù)集中實體關(guān)系數(shù)據(jù)的自動抽取，以實現(xiàn)注釋信息對KG推理提供充分證據(jù).其中，深度置信網(wǎng)絡是一種典型的深度學習模型，由多層受限玻爾茲曼機(RBM，Restricted Boltzmann Machine)網(wǎng)絡組成，采用無監(jiān)督的學習進行模型訓練，具有優(yōu)良的特征提取能力.

(2)

添加注釋信息后對潛在鏈接關(guān)系的正確預測概率是

(3)

式(3)括號內(nèi)參數(shù)表示在屬性矩陣存在的條件下三元組的個數(shù).由貝葉斯公式(1)可知，W′與W″存在如式(4)的關(guān)系，

(4)

對推理結(jié)果進行定量分析時，本文在搜索—打分函數(shù)[9]基礎之上進行改進，提出利用貝葉斯打分函數(shù)對實體間依賴程度打分判定.對于初始KG的實體及其關(guān)系抽象為變量集合Y={Y1，Y2，…，Yn}，變量對應的取值數(shù)據(jù)集合D={y1,y2,…,yn}，將初始G結(jié)構(gòu)G0賦值給最佳網(wǎng)絡結(jié)構(gòu)Gk后使用貝葉斯打分函數(shù)式(5)對節(jié)點間依賴程度打分.

(5)

式(5)中Gs是KG更新過程中的一種中間狀態(tài)結(jié)構(gòu)，接下來在Gs收斂的條件下迭代改變Gk-1的節(jié)點間關(guān)系鏈接，得到新的KG網(wǎng)絡結(jié)構(gòu)，再利用貝葉斯打分函數(shù)尋找正確的網(wǎng)絡關(guān)系Gk，并將更新后的KG賦給Gk，算法描述見表3.

表3 潛在因子發(fā)現(xiàn)算法Table 3 Potential factors discovery algorithm

4 實驗分析

4.1 實驗環(huán)境及數(shù)據(jù)

本實驗平臺的硬件環(huán)境為Intel(R)Core(TM)i3-4160 CPU @3.60 GHz處理器，8GB物理內(nèi)存；軟件環(huán)境是Ubuntu操作系統(tǒng)+gcc 4.3.0編譯器以及64位Windows 7操作系統(tǒng)+集成開發(fā)環(huán)境My Eclipse；知識圖譜的存儲使用Neo4j圖形數(shù)據(jù)庫，使用面向?qū)ο蟮恼Z言C++及Java編寫程序.

表4 實驗數(shù)據(jù)集Table 4 Experimental dataset

知識圖譜構(gòu)建使用如表4所示實驗數(shù)據(jù)集.其中Wikidata是一個可以自由協(xié)作編輯的多語言百科知識庫，它將維基百科等項目中結(jié)構(gòu)化知識進行抽取、存儲、關(guān)聯(lián)，Wikidata中的每個實體存在多個不同語言的標簽、別名、描述、以及聲明(statement).DBpedia是一個大規(guī)模的多語言百科知識圖譜，可視為是維基百科的結(jié)構(gòu)化版本.DBpedia使用固定的模式對維基百科中的實體信息進行抽取，包括abstract、infobox、category和pagelink等信息.Zhishi.me是涵蓋三大中文百科全書(百度百科、互動百科和維基百科)的中文鏈接開放數(shù)據(jù)[10].

4.2 實驗結(jié)果與可視化展示

4.2.1 算法測試

為了全面測試算法的準確度與高效性，本文選用3種常見的知識圖譜鏈路預測模型算法TransE(Translating Embedding)算法、Rescal算法、RSTE(Random Semantic Tensor Ensemble)算法與本文提出的貝葉斯?jié)撛谝蜃幽Ｐ头椒ㄟM行橫向?qū)Ρ葘嶒灧治?

TransE模型[2]是一種基于轉(zhuǎn)換推理方法的能量模型，用于低維實體的嵌入學習.模型通過不斷調(diào)整頭實體嵌入向量與關(guān)系向量的方向，使二者矢量和與尾實體向量近似相等.調(diào)整過程中的能量用一個距離函數(shù)d(h+l，t)(d可以是歐幾里得距離或者是曼哈頓距離)表示.Rescal算法[11]可被看作是一個集體矩陣的分解方法.該算法對每一個知識圖譜張量的正面切片進行分解，并利用稀疏線性代數(shù)計算推理技術(shù)減小內(nèi)存開銷.RSTE[4]是基于張量因式分解的可擴展使能集合框架.該方法通過從知識圖譜中抽取形如Xk=ARkAT(A是一個n×r的矩陣，Rk是一個r×r的不對稱矩陣.r為分解等級，是用戶定義的參數(shù))的張量對KG進行表示，并通過張量因式分解集合進行鏈接預測.本文選擇準確率(Precision)、召回率(Recall)作為算法鏈接預測準確性的評價指標，準確率、召回率定義如(6)、(7)式.

(6)

(7)

(6)、(7)式中，假設測試結(jié)果數(shù)據(jù)集中三元組關(guān)系分為兩類，正確的類(簡稱為正類)和錯誤的類(簡稱為負類).TP表示算法將正類推理預測成正類的數(shù)目，F(xiàn)N表示正類推理預測為負類的數(shù)目，F(xiàn)P表示負類推理預測為正類的數(shù)目.

圖3 算法運行總時間Fig.3 Algorithm running total time

圖4 算法準確率—召回率曲線橫向比較結(jié)果Fig.4 Accuracy-recall rate curve of algorithms horizontal comparison results

圖3顯示了橫向測試實驗中獲得最佳結(jié)果的四種算法的運行時間開銷，實驗數(shù)據(jù)集經(jīng)過訓練、評估與三元組測試等步驟進行篩選，且四種算法均保證在統(tǒng)一實驗環(huán)境下進行.通過數(shù)據(jù)分析可得，數(shù)據(jù)集規(guī)模不同，算法的運行時間有差異.若單從Zhishi.me數(shù)據(jù)集來看，本文算法比TransE方法測試時間減少了55.6%，比Rescal方法減少了49.1%，比RSTE方法減少了5%.由圖4可以清楚地看到，由于本文算法在預測推理時采用RDF蘊含推理與貝葉斯理論綜合的加強推理方式，使得推理準確率較高.其中，若召回率取值固定在0.4，本文算法的精確度就開始展現(xiàn)出優(yōu)勢.隨著召回率的增加，精確率總體呈遞減趨勢，但遠高于另外三種算法.

4.2.2 模型方法實例分析及可視化展示

對圖書類實體及關(guān)系屬性采用DBN方法進行部分知識抽取，而后經(jīng)知識融合、知識存儲、知識推理、可視化展現(xiàn)的步驟得到如圖5所示的知識圖譜片斷，實驗的可視化分析工具采用基于Javascript的圖表庫Echarts，它兼容當前絕大部分瀏覽器，底層依賴輕量級的Canvas類庫ZRender，提供直觀、生動、可交互、可高度個性化定制的數(shù)據(jù)可視化圖表.

圖5 本文構(gòu)建的知識圖譜片斷Fig.5 Fragment of KG proposed by this paper

圖5中的實體為書籍名稱B(Book)，其余均為實體屬性也即注釋信息，作者A(Author)、出版商P(Publishers)、書籍類型T(Type)、讀者U(User).注釋信息的種類在圖數(shù)據(jù)庫Neoj4容量可承載范圍內(nèi)可任意添加，注釋信息越多，則推理預測精確度越高.對于圖5所示知識圖譜，實驗隨機刪除50%的現(xiàn)有鏈接，以此為樣本測試本文提出的基于貝葉斯推理的知識圖譜鏈接預測算法.通過測試驗證，推理預測得到的知識圖譜片斷與初始KG進行比較并統(tǒng)計計算出預測準確率為82.4%.

5 總結(jié)與展望

本文針對知識網(wǎng)絡中結(jié)構(gòu)不完整、邊緣或?qū)傩詳?shù)據(jù)丟失以及潛在關(guān)系三元組發(fā)掘效率低下的問題，提出了一種基于貝葉斯推理的潛在因子的發(fā)現(xiàn)算法.此算法結(jié)合RDF蘊含推理規(guī)則與貝葉斯概率推理，通過計算節(jié)點間關(guān)系置信度來判斷關(guān)系的可靠性，發(fā)現(xiàn)實體間潛在的關(guān)系預測未來關(guān)系網(wǎng)絡，使得知識圖譜在動態(tài)數(shù)據(jù)環(huán)境下能夠?qū)崟r更新.通過三種鏈接預測算法與潛在因子的發(fā)現(xiàn)算法橫向?qū)Ρ确治鰷y試，實驗結(jié)果表明，基于貝葉斯推理的潛在因子的發(fā)現(xiàn)算法具有較高的準確率及較少的時間開銷.知識圖譜作為語義搜索的關(guān)鍵技術(shù)，它的不斷完善將有助于搜索引擎智能化的發(fā)展.由于本論文提出的方法在實驗數(shù)據(jù)規(guī)模上還沒有達到真正意義上的海量且數(shù)據(jù)預測效率還有上升的空間，下一步的工作，是將鏈接預測算法深度嵌入至KG中進行擴大數(shù)據(jù)集的搜索引擎效率測試并不斷完善算法.

：

[1] Liu Qiao，Li Yang，Duan Hong，et al.A survey of knowledge graph construction technology[J].Computer Research and Development，2016，53(3)：582-600.

[2] Bordes A，Usunier N，Garcia-Duran A，et al.Translating embeddings for modeling multi-relational data[J].Advances in Neural Information Processing Systems，2013，112(9)：2787-2795.

[3] Nickel M，Tresp V，Kriegel H P，et al.A three-way model for collective learning on multi-relational data[C].International Conference on Machine Learning，Bellevue，Washington，USA，2011：809-816.

[4] Yi T，Luu A T，Brauer F，et al.Random semantic tensor ensemble for scalable knowledge graph link prediction[C].Tenth ACM International Conference on Web Search & Data Mining.Shanghai，China，2017：751-760.

[5] Neelakantan A，Roth B，Mccallum A，et al.Compositional vector space models for knowledge base completion[J].Computer Science，2015，43(2)：1-16.

[6] Toutanova K，Chen D.Observed versus latent features for knowledge base and text inference[C].The Workshop on Continuous Vector Space MODELS & Their Compositionality，2015.

[7] Xu Zeng-lin，Sheng Yong-pan，He Li-rong，et al.A survey of knowledge graphs[J].Journal of University of Electronic Science and Technology of China，2016，45(4)：589-606.

[8] Chen Yu，Zheng De-quan，Zhao Tie-jun.The research of Chinese entity classification based on deep belief nets methods[J].Intelligent Computer and Applications，2014，35(2)：29-31.

[9] Dong Li-yan.Research on Bayesian network application[D].Changchun：Jilin University，2007.

[10] Qi Gui-lin，Gao Huan，Wu Tian-xing.Research progress on knowledge graph[J].Technology Intelligence Engineering，2017，3(1)：4-25.

[11] Nickel M，Tresp V，Kriegel H P.A three-way model for collective learning on multi-relational data[C].International Conference on Machine Learning，Belleevue，Washington，USA，2011：809-816.

附中文參考文獻：

[1] 劉 嶠，李 楊，段 宏，等.知識圖譜構(gòu)建技術(shù)綜述[J].計算機研究與發(fā)展，2016，53(3)：582-600.

[7] 徐增林，盛泳潘，賀麗榮，等.知識圖譜技術(shù)綜述[J].電子科技大學學報，2016，45(4)：589-606.

[8] 陳 宇，鄭德權(quán)，趙鐵軍.基于Deep Belief Nets 方法的中文名實體分類研究[J].智能計算機與應用，2014，35(2)：29-31.

[9] 董立巖.貝葉斯網(wǎng)絡應用基礎研究[D].長春：吉林大學，2007.

[10] 漆桂林，高 桓，吳天星.知識圖譜研究進展[J].情報工程，2017，3(1)：4-25.