时态知识图谱补全的方法及其进展
點擊上方藍字關注我們
時態知識圖譜補全的方法及其進展
申宇銘,?杜劍峰
廣東外語外貿大學信息科學與技術學院,廣東 廣州 510420
摘要:時態知識圖譜是將時間信息添加到傳統的知識圖譜而得到的。近年來,時態知識圖譜補全受到了學術界的高度關注,并成為研究熱點之一。總結了目前時態知識圖譜補全的兩大類方法,即基于符號邏輯的方法和基于知識表示學習的方法,比較分析了兩類方法的優缺點,展望了未來時態補全方法的發展方向,還總結了7個用于時態知識圖譜補全的基準數據集和若干代表性模型在基準數據集上的評測結果。
關鍵詞:時態知識圖譜?;?本體?;?表示學習
論文引用格式:
申宇銘, 杜劍峰. 時態知識圖譜補全的方法及其進展[J]. 大數據, 2021, 7(3): 30-41.
SHEN Y M, DU J F. Temporal knowledge graph completion:methods and progress[J]. Big Data Research, 2021, 7(3): 30-41.
1 引言
在人工智能飛速發展的背景下,知識圖譜(knowledge graph)被普遍地認為是人工智能技術和系統中的重要組成部分,在智能搜索、網絡安全、金融風險控制及電子商務等諸多領域得到了廣泛應用。傳統的知識圖譜以(實體,關系,實體)或(實體,屬性,屬性值)三元組集合的方式來表達現實世界的概念、實體、事件及三者之間的關系。比如,三元組(姚明,身高,2.26米)和(姚明,國籍,中國)。2012年5月,谷歌公司發布了谷歌知識圖譜(Google knowledge graph),宣布以此為基礎構建下一代智能化搜索引擎。這是知識圖譜名稱的由來,也標志著大規模知識圖譜在語義搜索中的成功應用。事實上知識圖譜技術淵源已久——從20世紀70年代的專家系統(expert system),到萬維網之父Tim BernersLee提出的語義網(semantic web),再到他后來提出的鏈接數據(linked data),都是知識圖譜的前身。可以說,知識圖譜的升溫是人工智能對數據處理與理解需求逐日增加而導致的必然結果。
時間是自然界中所有實體都具有的重要屬性,不少知識圖譜(如Freebase、Wikidata、DBpedia、YAGO等)具有時間標記的知識。將時間信息引入三元組中所構成的四元組集合稱作時態知識圖譜(temporal knowledge graph)。全球事件知識圖譜和沖突事件知識圖譜都是典型的基于事件的時態知識圖譜。此類知識圖譜不僅包含了事件之間的共指、因果和時序等關系,還描述了事件之間的規律和演化模式,對傳統的知識圖譜補充了時間信息,因而具有更大的應用價值。時態知識圖譜示例如圖1所示。
圖1???時態知識圖譜示例
與傳統的靜態知識圖譜相似,時態知識圖譜中的知識也是不完備的,為了實現最大價值,其需要不斷地消化吸收新數據,以完善知識體系。近年來,時態知識圖譜補全(temporal knowledge graph completion)方法應運而生,受到了學術界的高度關注,并成為研究熱點之一。這類方法基于時態知識圖譜的現有四元組數據,建模預測真實存在的新四元組。這些預測得到的四元組經過驗證后,可被添加到時態知識圖譜中,作為其演化的結果。時態知識圖譜補全的方法在構建大規模知識圖譜、相似度計算、關系抽取,以及基于知識圖譜問答等任務方面展現出巨大的應用潛力。
為了能夠及時追蹤到補全方法在時態知識圖譜上的發展和應用,本文首先給出時態知識圖譜補全的問題定義,回顧代表性的時態知識圖譜補全方法,然后對不同類別的方法進行對比分析,給出可能的結合途徑,最后總結當前時態知識圖譜評測的7個基準數據集,并且給出幾個代表性的補全模型在其中3個基準數據集上的評測結果。
2 問題定義
本節給出時態知識圖譜及其補全過程的定義,并介紹相關的評測任務。
定義2.1 時態知識圖譜。一個時態知識圖譜是一個四元組的集合。形式地說,任意給定實體集合E、關系集合R、有窮時間戳集合T,時態知識圖譜G是笛卡兒積E×R×E×T的一個子集。
比如,事件“2016—2020年期間,特朗普是美國總統”可以表達為四元組(美國,總統,特朗普,[2016,2020])。類似地,事件“拜登于2021年當選美國總統”可以表達為四元組(美國,總統,拜登, 2021)。
定義2.2 時態知識圖譜補全。令E× R×E×T的一個子集W表達現實世界中所有成立的事實,G為W的一個真子集。時態知識圖譜的補全是指:由G出發,推理出不屬于G但是屬于W的事實。
例1 假設W={(a,簽訂合同,b,t1),(a,履行合同,b,t1+1),(a,簽訂合同,c,t2),(a,履行合同,c,t2+1)},且G={(a,簽訂合同,b,t1),(a,履行合同,c,t2+1)},則需要從G出發推理出事實(a,履行合同,b,t1+1)和(a,簽訂合同,c,t2)。
時態知識圖譜的補全評測任務主要有兩個:
● 給定頭實體a、關系r和時間戳t,補全尾實體,即(a,r,?,t);
● 給定尾實體b、關系r和時間戳t,補全頭實體,即(?,r,b,t)。
與傳統的知識圖譜補全問題不同,時態知識圖譜的補全更加強調事實成立的時效性,比如,四元組(特朗普,當選,美國總統,2016)和(特朗普,卸任,美國總統,2015),第一個四元組是真實事實,而第二個四元組是虛假事實,去掉時間戳后,所得的兩個三元組(特朗普,當選,美國總統)和(特朗普,卸任,美國總統)都是真實事實。因此,如何將事實成立的時效性信息融入傳統的補全模型是亟待解決的問題。
3 時態知識圖譜補全方法
目前,依據對符號處理的不同方式,時態知識圖譜的補全方法主要分為兩大類:一類是基于符號邏輯的方法,此類方法通過構建領域本體,運用飽和度技術,推理出隱含存在的真實四元組;另一類是基于知識表示學習(knowledge representation learning)的方法,此類方法將符號映射到實值空間,采用數值運算評估四元組的真實程度。
3.1 基于符號邏輯的方法
基于符號邏輯的時態數據查詢回答(logic-based temporal query answering)方法又分為兩類:一類以領域為中心,另一類以時間為中心。
以領域為中心的方法假定本體的構建語言為描述邏輯,查詢語句為包含時態算子(next-time,previous-time,sincetime,until-time,future-time)和否定聯結詞的一階時態邏輯公式。以此為基礎, Baader F等人分析了基于描述邏輯SHQ本體的時態查詢計算復雜性;Borgwardt S等人提出了基于描述邏輯DL-Lite族和EL本體的時態查詢推理算法,并分析了算法的計算復雜性。
以時間為中心的方法假定本體的構建語言為時態描述邏輯,查詢語句為包含時態算子(next-time,previous-time,sincetime,until-time,future-time)的一階時態邏輯公式。以此為基礎,Artale A等人設計了一種時態描述邏輯語言TQL,其包含past-time和future-time兩個一元時態算子,并在限定時態概念只出現在術語公理左側的情形下,證明了該邏輯語言支持時態查詢的一階重寫。GutiérrezBasulto V等人在限定時態查詢語言為時態原子語句的情形下,證明了時態本體EL-LTL的查詢問題是不可判定的,繼而通過引入若干語法上的限制條件識別出EL-LTL的若干可判定子片段,并證明了在某些子片段上的時態查詢回答是多項式時間可以完成的。Artale A等人全面研究了時態DL-Lite-LTL族下時態查詢的一階重寫問題,較完整地分析了時態查詢問題的計算復雜性。
例2 假設本體只包括一條規則“對所有x,y,t: R(x,y,t)→Q(x,y,t+1)”,其中謂詞R、Q分別表示簽訂合同和履行合同,考慮到例1中集合G={(a,簽訂合同,b,t1),(a,履行合同,c,t2+1)},由上述規則可以推理出隱含事實(a,履行合同,b,t1+1)。對于時態查詢q=(a,履行合同,?,t1+1),隱含的事實 (a,履行合同,b,t1+1) 滿足該時態查詢q。
對比兩類方法,以領域為中心的方法在查詢語言的表達能力上要強于以時間為中心的方法,而以時間為中心的方法在本體的表達能力上要強于以領域為中心的方法。同時,基于符號邏輯的方法在實際應用中難以覆蓋大量真實的四元組,召回率較低,而且構建本體時也要付出較高的人工成本。
3.2 基于知識表示學習的方法
本節先簡要回顧針對傳統知識圖譜的表示學習代表性方法,再以此為基礎,綜述針對時態知識圖譜的表示學習方法。知識表示學習方法的基本原理是將給定的三元組數據映射到低維、高密度的數值空間,通過數值運算評估未知三元組的真實程度。依據三元組評分函數的不同類型,傳統知識圖譜的表示學習方法大致分為3類:第一類是基于平移距離模型的方法,第二類是基于矩陣分解模型的方法,第三類是基于神經網絡模型的方法。
基于平移距離模型的方法根據三元組中頭尾實體表示向量的距離來估計三元組的真實性。Bordes A等人提出了第一個平移距離模型TransE。該模型采用損失函數來估計三元組的真實程度,其中h為頭實體向量,r為關系實體向量,t為尾實體向量,L1和L2分別表示1-范數和2-范數,而真實程度通常可以被定義為損失函數值的相反數。根據最優化目標,真實三元組的損失函數值應該趨向于零,因此TransE不太適用于一對多、多對一或者多對多的關系建模。針對TransE模型的局限性,此后陸續涌現了TransH、TransR、TransD、TransG、RotatE等模型。
基于矩陣分解模型的方法采用形式的評分函數來評估三元組的真實程度,其中是關系依賴的矩陣,h和t分別是頭、尾實體向量。Nickel M等人提出了第一個矩陣分解模型,即RESCAL模型,用于三元組預測。此后,他們又提出了參數更少的全息嵌入(holographic embedding,HolE)模型。Yang B S等人將關系依賴的矩陣看作以實數構成的對角矩陣,提出了DistMult模型。Trouillon T等人使用復數而不是實數構造頭尾實體向量,并將關系依賴的矩陣看作以復數構成的對角矩陣,提出了ComplEx模型。Liu H X等人為關系依賴矩陣引入正態性和可交換性約束來表達類比性質(比如北京與中國的關系類似于巴黎與法國的關系),提出了ANALOGY模型,并證明了該模型是HolE和ComplEx等模型的一般化形式。此后,研究人員還陸續提出了SimplE、Tucker等模型。
基于神經網絡模型的知識表示學習方法采用神經網絡形式的評分函數來評估三元組的真實程度。Bordes A等人提出了語義匹配能量(semantic matching energy,SME)模型,該模型將頭實體與關系的交互模型和尾實體與關系的交互模型作為第一層網絡,再將兩個交互模型的輸出組合起來構成第二層網絡。Socher R等人提出了神經張量網絡(neural tensor network,NTN)模型,該模型采用頭尾實體各自的線性變換模型以及它們之間交互的線性變換模型來構造神經網絡,其中所有線性變換模型都使用不同的關系依賴矩陣。Dong X等人提出了多層感知器(multi-layer perceptron,MLP)模型,該模型采用關系和頭尾實體各自的線性變換模型共3個線性變換模型來構造神經網絡,3個線性變換模型中使用的變換矩陣都不依賴于關系。
除了這3類方法,還有文獻討論了利用知識圖譜外部信息的知識表示學習方法,包括結合實體描述信息的方法、結合實體類型信息的方法、結合關系路徑信息的方法、結合邏輯規則的方法等。更多的傳統知識圖譜的表示學習方法參見參考文獻。
傳統知識圖譜中的知識在大多數情況下只在特定的時間內有效,而一些事實(如演化的事件)往往出現在一個時間序列中。為了對時間序列中的事實進行表示學習,近年來涌現了不少針對時態知識圖譜的補全方法。依據對時間戳的處理方式,這些方法可以大致分為兩類:第一類是時間戳單獨編碼方法,第二類是基于序列學習的方法。
時間戳單獨編碼方法顯式地將時間戳建模為向量、矩陣或平面,再將時間戳的信息直接用于知識圖譜的補全。Jiang T S等人率先提出結合時態信息的知識圖譜補全模型,該模型由兩部分構成,其中一個部分是由TransE獲得關系的表示向量,另一個部分由3種時態一致性約束(先后順序關系、時態不相交性、時態區間有效性)構成。模型通過一個時態演化矩陣來刻畫不同關系之間的時態依賴性,具體地說,任意給定兩個時序依賴關系rk和rl,它們的時序評分函數定義為:,其中矩陣T是一個能夠編碼時序關系對的非對稱矩陣,此評分函數基本思想如圖2所示。
圖2???時態演化矩陣
在圖2中,r1是先于r2的時態關系,根據評分函數有,但是。Dasgupta S S等人結合了模型TransE和TransH的特點,提出了HyTE時態表示學習模型。該模型首先將時間戳建模為關系依賴的超平面,然后利用TransH模型將頭、尾實體投影到該平面,最后利用TransE模型完成知識圖譜的補全工作。Ma Y P等人和Lacroix T等人都將時間戳看作第4個維度,分別擴展了Tucker和ComplEx張量分解模型,再將時間戳的表示向量直接用于四元組真實程度的估計。Jain P等人在Lacroix工作的基礎上,將先后順序關系和循環關系(比如奧運會每隔3年舉辦)的信息增加到評分函數中,用于圖譜的補全。Xu C J等人基于RotatE模型提出了時態旋轉模型,該模型將時間戳建模為旋轉復向量,將實體和關系表示為復向量,通過旋轉復向量與實體表示復向量的內積運算,將時態信息融合到實體的表示向量中,并利用基于距離TransE模型完成知識圖譜的補全。時間戳單獨編碼方法將時間信息看成連通實體與實體、關系與實體及關系與關系的橋梁。
基于序列學習的方法先設計一個序列學習模型,將時態信息融合到實體或關系的表示向量中,再用已有的表示學習模型估計帶有時態信息三元組的真實程度,從而完成時態知識圖譜的補全任務。Garcia-Duran A等人[32]將關系和時間戳的特征(年、月、日)構成一個關系序列,通過一個線性層函數,將關系和時間戳特征映射為同維數的向量,然后把該序列向量輸入一個長短期記憶(long short-term memory,LSTM)網絡進行編碼,學習到融合時間信息的關系表示向量,該具體過程如圖3所示。
圖3???融合時間信息的關系表示向量
在圖3中,關系“bornIn”與日期“1986”經過LSTM模型后形成了融合時間信息的關系表示向量;最后,依據DistMult模型的評分函數或TransE模型的評分函數對三元組(s,pseq, o)完成補全,這里和分別表示頭實體s、尾實體o和關系pseq的表示向量。Goel R等人將實體的表示向量分為靜態和動態兩個部分,并利用SimplE模型完成知識圖譜的補全,其中實體表示向量的靜態部分表達實體在演化過程中固定不變的特征,動態部分則結合正弦激活函數來調控不同時間點狀態的閉合,進而表達演化過程中變化的特征。Wu J P等人利用魯棒性圖卷積神經網絡(robust graph convolutional network, RGCN)模型將不同時間同一實體的鄰居結構化信息進行融合,獲得了該實體的一個序列表示向量,然后將該表示向量序列輸入時態遞歸神經網絡中,獲取該實體融合時態信息的表示向量,最后利用靜態的補全模型完成補全的工作。Jung J等人提出了一種時態圖神經網絡(temporal graph neural network,TGNN)模型。該模型對時態知識圖譜及查詢分別進行預訓練,完成時態信息與實體表示向量的融合,并計算其鄰居的注意力分布,然后利用子圖采樣的方法獲得每個實體及與查詢相關的鄰居的子圖結構,過濾與查詢不相關的實體,再利用圖神經網絡模型,更新子圖上實體的表示向量,并結合基于路徑遍歷的方法更新實體鄰居的注意力分布,最后依據最高概率推理出實體間隱藏的關系。與更新實體或關系的表示向量不同,Xu Y R等人考慮了時態知識圖譜中增加新實體的情況,設計了一種策略遞歸地更新模型參數。Xu C等人考慮了知識圖譜時態演化過程中的不確定性因素,在每個時間點采用高斯分布函數來表達實體和關系的不確定性,再結合時間序列的線性模型來刻畫實體和關系表示向量隨時間演化的趨勢,最后通過計算實體和關系概率分布的距離來完成補全。Han Z等人則將補全的工作從傳統的歐氏空間拓展到黎曼流形(Riemannian manifold)上完成。相對于第一類方法,基于序列學習的方法更加強調不同實體和關系間的歷史關系,即實體或關系之間帶有時間戳的序列之間的交互。
4 兩類方法的比較
基于符號邏輯的方法可以從已有的知識圖譜出發,結合本體中的規則,推理出新的實體間關系;同時,還可以對演化后的知識圖譜進行邏輯一致性檢查,使得推理結果具備透明、可靠及可解釋性強等特點。為了表達時態的知識,這一類方法通常需要引入時態算子來提升本體的表達能力,而表達能力的提升通常會導致如下兩種局限性。
● 不可判定性:即不存在有限時間可終止的算法,使得該算法能夠判定相關的推理問題是否可證。比如,在描述邏輯EL中,引入時態算子到本體中會導致其時態查詢回答是不可判定的。
● 高計算復雜性:比如,在描述邏輯EL中,交查詢的回答是多項式時間的,但引入時態算子到查詢語言后,時態交查詢回答卻是NP難的。
由此可見,基于符號邏輯的方法在推理效率方面難以滿足日益增長的數據需求。
基于知識表示學習的方法將研究對象的語義信息表示為低維稠密的實值向量。在低維向量空間中能夠高效地計算實體和關系的語義關系,顯著地提高推理性能。但是,此類方法的推理過程不透明,推理結果的可解釋性低。此外,大多數表示學習模型的表達能力有限。比如,參考文獻指出數值嵌入模型不能表達本體中的存在規則(existential rule),而這類規則恰好對應于輕量級描述邏輯EL或DL-Lite族的術語或角色公理;進一步地,參考文獻指出,就算表示學習模型能夠區分所有真實的三元組和錯誤的三元組,也不能確保正確區分出本體中的上下位關系。由此可見,基于知識表示學習的推理不能完全替代基于符號邏輯的推理。
從推理的方式來看,基于符號邏輯的推理屬于演繹推理,而基于表示學習的推理屬于不完全歸納推理,兩種推理方式各有各的優缺點,但最終的目的都是將不完備的知識庫(incomplete knowledge base)演化為完備的知識庫(complete knowledge base)。為了發揮兩種推理方式的優勢,未來的知識圖譜補全研究方向可以聚焦于解決表示學習模型無法習得存在規則邏輯的結論的問題。在這一方向上,Du J F等人提出了邏輯背景預完備技術來融入關系特征定義,并提出了區分頭尾實體的投影函數來解決關系表示向量不可區分的問題;進一步地,參考文獻引入了邏輯一致性規則預完備技術,解決了部分排位靠前的三元組與邏輯一致性規則相違背的問題。
5 基準測試數據集
當前,時態知識圖譜補全研究領域有7個基準測試數據集,它們是在Wikidata、YAGO、GDELT和綜合早期危機預警系統(integrated crisis early warning system, ICEWS)4個數據庫上構建的。這7個數據集分別是GDELT-500、ICEWS14、ICEWS05-15、YAGO15k、Wikidata11k、YAGO11k和Wikidata12k,其中YAGO和Wikidata中的事實是基于時間區間的,而GDELT和ICEWS中的事實是基于時間點的。
● GDELT:GDELT數據庫記錄了從1969年至今,每個國家大約100多種語言的新聞媒體中印刷、廣播和We b形式的新聞,并且每隔15 min更新一次數據。GDELT主要包含兩大數據庫,即事件數據庫(event database)和全球知識圖譜 (global knowledge graph)。目前,用于時態知識圖譜補全研究的數據集是GDELT-500。
● ICEWS:ICEWS數據庫涵蓋了100多個數據源以及250個國家和區域的政治事件,并且每天更新一次數據。用于時態知識圖譜補全研究的數據集是ICEWS14和ICEWS05-15。
● Wikidata:Wikidata是維基媒體基金會主持的一個自由的協作式多語言輔助知識庫,旨在為維基百科、維基共享資源以及其他的維基媒體項目提供支持。目前,用于時態知識圖譜補全研究的數據集是Wikidata11k和Wikidata12k。
● YAGO:YAGO是由德國馬克斯·普朗克研究所研制的鏈接數據庫。該數據庫主要集成了Wikipedia、WordNet和GeoNames 3個來源的數據。YAGO將WordNet的詞匯定義與Wikipedia的分類體系進行了融合集成,使得YAGO具有更加豐富的實體分類體系。YAGO還考慮了時間和空間知識,為很多知識條目增加了時間和空間維度的屬性描述。目前,用于時態知識圖譜補全研究的數據集是YAGO11k和YAGO15k。上述7個數據集的統計結果見表1。
表2給出了代表性的補全模型在3個基準數據集ICEWS14、ICEWS05-15和Wikidata11k上的評測結果。表2中上標為*的評測結果來自參考文獻,上標為+的評測結果來自參考文獻,上標為#的評測結果來自參考文獻。其中-表示所在行的模型在所在列的基準數據集上沒有公布評測結果。評測指標MRR表示所有正確答案預測排名的倒數的均值;Hit@k表示正確答案在前k位預測三元組中的百分比。
6 結束語
給定某個時間區間[t0,t1]及其對應的時態知識圖譜G,補全任務是針對某個時刻t (t0≤t≤t1)的推理任務。比如,在例2中,可以由(a,履行合同,c,t2+1)補全出(a,簽訂合同,c,t2)。與補全任務相對的另一個任務是時態知識圖譜的預測任務。即給定某個時間區間[t0,t1]及其對應的時態知識圖譜G,預測出t>t1時刻圖譜G的演化結果。相比而言,時態知識圖譜的預測任務比補全任務更具有挑戰性。限于文章的篇幅,請讀者閱讀參考文獻了解預測任務的解決方案和相關技術。
綜合考慮時態知識圖譜的補全方法不難發現,基于知識表示學習的方法是目前的主流方法。這類方法具有計算效率高和召回率高的特點,但是在表達能力上還存在弱點。因此,未來的研究工作可以關注如下兩個可能的完善方向:①融合本體推理,運用基于符號邏輯的推理彌補知識表示學習在表達能力上的不足,完成知識表示學習模型的精準訓練;②設計表達能力更強的神經網絡模型,用于表達本體中所有可能的規則。
作者簡介
申宇銘(1976-),男,博士,廣東外語外貿大學教授,主要研究方向為知識表示與推理、知識圖譜。主持或參與多項國家自然科學基金和省部級項目。近年來在《計算機學報》《軟件學報》等國內重要期刊,以及國際重要期刊和國際會議上發表論文20余篇。擔任CCKS、AAAI、EMNLP等國內外重要學術會議的程序委員會委員。
杜劍峰(1976-),男,博士,廣東外語外貿大學教授,中國中文信息學會語言與知識計算專業委員會委員,主要研究方向為知識表示與推理、數據挖掘和自然語言處理。在AAAI、WWW、ISWC、CIKM和KAIS等學術會議上發表數十篇文章,獲得多項國家自然科學基金項目資助。擔任JournalofWebSemantics編委,長期擔任CCKS、CSWS、IJCAI、AAAI、ISWC、JIST等學術會議的程序委員會成員,曾擔任CSWS2014程序委員會主席。
聯系我們:
Tel:010-81055448
? ? ? ?010-81055490
? ? ? ?010-81055534
E-mail:bdr@bjxintong.com.cn?
http://www.infocomm-journal.com/bdr
http://www.j-bigdataresearch.com.cn/
轉載、合作:010-81055537
大數據期刊
《大數據(Big Data Research,BDR)》雙月刊是由中華人民共和國工業和信息化部主管,人民郵電出版社主辦,中國計算機學會大數據專家委員會學術指導,北京信通傳媒有限責任公司出版的期刊,已成功入選中國科技核心期刊、中國計算機學會會刊、中國計算機學會推薦中文科技期刊,并被評為2018年、2019年國家哲學社會科學文獻中心學術期刊數據庫“綜合性人文社會科學”學科最受歡迎期刊。
關注《大數據》期刊微信公眾號,獲取更多內容
總結
以上是生活随笔為你收集整理的时态知识图谱补全的方法及其进展的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 网站泄密
- 下一篇: 不再颓废,重新开始,牛客第一题1016.