一種結(jié)合路徑信息和嵌入模型的知識(shí)推理方法

陳海旭，周 強(qiáng)，2，劉學(xué)軍

1(南京工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京211816)

2(南京鍋爐壓力容器檢驗(yàn)研究院，南京211816)

1 引 言

大規(guī)模知識(shí)圖譜如 Freebase［1］，WordNet［2］，可以看作是由不同類型的實(shí)體作為頂點(diǎn)，實(shí)體之間的各種關(guān)系作為邊的有向圖.這些知識(shí)圖譜通常包含數(shù)十億的事實(shí).每個(gè)事實(shí)都被表示為三元組(頭實(shí)體、關(guān)系、尾實(shí)體)，簡寫為(h，r，t)的形式.但是，這些與客觀世界相比，這些知識(shí)圖譜的覆蓋范圍還遠(yuǎn)遠(yuǎn)不足［3］.因此，知識(shí)圖譜的補(bǔ)全，即知識(shí)推理成為知識(shí)圖譜研究的一個(gè)重要的部分.

近年來，將知識(shí)圖譜的實(shí)體和關(guān)系投影到多維向量空間來學(xué)習(xí)實(shí)體和關(guān)系的潛在屬性的方法，已經(jīng)引起了廣泛的關(guān)注.與以往工作相比，這些知識(shí)嵌入模型具有復(fù)雜度低、可重用性高等優(yōu)點(diǎn).這類方法的典型TransE［4］，是一個(gè)經(jīng)典的基于神經(jīng)網(wǎng)絡(luò)的模型通過優(yōu)化基于邊界的損失函數(shù)將實(shí)體和關(guān)系表示為向量，將關(guān)系視作頭實(shí)體向量到尾實(shí)體向量的平移，并使用 S(h，r，t)來評(píng)價(jià)三元組存在的合理性.TransH［5］和TransR［6］是TransE 的代表性變體，這些變體從多個(gè)方面考慮實(shí)體，不同的關(guān)系可能強(qiáng)調(diào)不同的方面.但是，隨著對TransE的改進(jìn)和算法性能的提高，算法的復(fù)雜度也隨之增大.

最近的研究中，在嵌入模型的基礎(chǔ)上引入了路徑推理算法PRA［7，8］，它將實(shí)體間的多步關(guān)系路徑表示為低維向量空間中的向量，從而將兩種方法相結(jié)合，在嵌入模型的基礎(chǔ)考慮了關(guān)系路徑的隱含信息，極大地提高了知識(shí)推理的效果.PTransE［9］、RTransE［10］和 RPE［11］是其中的典型，這些算法的評(píng)分函數(shù)分為兩部分，一部分是嵌入模型的評(píng)分函數(shù)，即TransE 或TransE 的變體，另一部分是基于路徑的推理，通過綜合考慮目標(biāo)實(shí)體對之間的相關(guān)路徑來進(jìn)行三元組評(píng)分.然而，這些算法都是通過對各路徑的得分求加權(quán)平均值的方法來綜合考慮路徑信息(權(quán)重為關(guān)系路徑的可靠性)，任意一條路徑的評(píng)分只能對最終結(jié)果有著正面或者負(fù)面的影響，而不能對最終結(jié)果有著決定性的作用.這對于“推理”這個(gè)任務(wù)來說是不合理的，因?yàn)槿绻腥我庖粋€(gè)條件可以完全確定推理的結(jié)果，就不需要再考慮其他條件.如圖1 所示，可以通過a這條路徑可以完全確定 a這個(gè)結(jié)果，這時(shí)候顯然就不需要考慮a，c 之間的其他路徑了.如果將這條路徑和a，c 之間的其他路徑一起納入考量，進(jìn)行加權(quán)平均值計(jì)算，結(jié)果很有可能是不確定的，而這顯然是不合理的.

圖1 路徑推理示例Fig.1 Example of path knowledge reasoning

本文結(jié)合嵌入模型和路徑推理算法提出了一種新的知識(shí)推理算法，該方法在綜合考慮路徑信息的基礎(chǔ)上，當(dāng)某一路徑能夠完全證明目標(biāo)關(guān)系存在的時(shí)候，能讓該路徑的評(píng)分對最終結(jié)果起決定性的作用.

2 相關(guān)工作

第一個(gè)嵌入模型是 TransE，其靈感來源于［12］.TransE 為每一個(gè)三元組定義了一個(gè)得分函數(shù) S(h，r，t)=h+r－t ，三元組(h，r，t)的得分越低(即越接近0)，其存在的可能性就越高，相反，三元組的得分越高，其存在的可能性就越低.TransE模型比較簡單，參數(shù)相對較少，可以用于大型知識(shí)圖譜的學(xué)習(xí)和推理，從而完善知識(shí)圖譜.TransE 模型在解決一對多、多對一和多對多的關(guān)系時(shí)，表現(xiàn)并不好.

為了解決這個(gè)問題，TransM［13］為每個(gè)關(guān)系計(jì)算出一個(gè)權(quán)值wr，然后在TransE 的模型上乘以這個(gè)關(guān)系權(quán)值，以此改變TransE 中針對一對多和多對一關(guān)系性能較差的缺點(diǎn)，其得分函數(shù)為 S(h，r，t)=Wrh+r－t.TransH［14］將實(shí)體投影到由關(guān)系確定的超平面上，其得分函數(shù)為 S (h，r，t)=考慮到實(shí)體和關(guān)系的差異，將實(shí)體和關(guān)系分別嵌入到不同的向量空間，在計(jì)算時(shí)實(shí)體空間的實(shí)體向量通過投影和轉(zhuǎn)換到相應(yīng)關(guān)系空間進(jìn)行運(yùn)算，其得分函數(shù)為 S(h，r，t)=hMr+r－tMr.除此之外，比較典型的嵌入模型還有 TransD［16］，KG2E［17］，TransG［18］，TransA［19，20］等.

基于路徑的知識(shí)方法，是根據(jù)知識(shí)圖譜的圖結(jié)構(gòu)特征進(jìn)行推理，路徑排列算法(Path Ranking Algorithm，PRA)［7，8］是其中的典型，其評(píng)價(jià)函數(shù)可以表示為 S(h，r，t)=xΘT，x 為關(guān)系r 對應(yīng)的路徑特征向量，如果h，t 之間存在某路徑，則x 中與該路徑對應(yīng)的元素的值為1，反之為0.Θ 是與x 相對應(yīng)的權(quán)重向量，其值可以通過極大似然估計(jì)來求得.

(Path-basedTransE)PTransE 是嵌入模型的基礎(chǔ)上引入路徑推理，進(jìn)一步挖掘知識(shí)圖譜中路徑的隱含信息，從而提高了推理效果.RPE，PaSKoGE［23］和 PRESCAL［21］都是在 PTransE的基礎(chǔ)上改造而成，如果將 PTransE 視作 PRA+TransE，則RPE=PRA+TransR，PaSKoGE=PRA+TransA，PRESCAL=PRA+RESCAL［22］.基本思路并沒有變化，RPE 和 PaSKoGE只是引入了TransR 和TransA 的理念做了些小小的改動(dòng)，PRESCAL 也只是在PTransE 的基礎(chǔ)上替換了實(shí)體和關(guān)系表達(dá)的方式.這幾種方式有一個(gè)共同的弊端，即在路徑推理的部分，只是簡單的通過求加權(quán)平均值的方式得到最后的評(píng)分，忽視了在路徑推理中單一路徑起決定性作用的情況，這無疑是不合理的.

本文針對上述問題提出了一種 PSTransE 算法，對PTransE 做出了較大改進(jìn)，使得在知識(shí)推理的時(shí)候，在綜合考慮相關(guān)路徑信息的同時(shí)，能夠凸顯出某些對推理結(jié)果支持度高的路徑的決定性作用.

3 基于路徑相似度和嵌入模型的知識(shí)推理

3.1 模型構(gòu)建

首先，考慮一個(gè)這樣的概率問題，A 地和B 地之間有多條路徑，每條路徑可能暢通也可能阻塞，其概率不同，求某人能夠從A 地到達(dá)B 地的概率.解決該問題的方法很簡單，只要A B 兩地之間有任意一條路徑暢通，那么就能夠從A 地到達(dá)B 地，因此先反向求出A B 兩地之間所有路徑都阻塞的概率，用1 減去該值即可得到某人能夠從A 地到達(dá)B 地的概率.根據(jù)這樣的思路提出了公式(1)，該方法的基本思路是如果實(shí)體對h，r 之間有任意一條路徑能夠證明它們之間存在關(guān)系 r，則認(rèn)為三元組(h，r，t)存在.根據(jù)公式(1)，如果某條推理結(jié)果支持度為100%，即P(r|p)=1，則可以確定S(h，r，t)=1 而不受其他路徑的影響.

這里P(h，t)表示從 h 開始到達(dá) t 的所有路徑的集合，R(r)和R(p)分別表示具有關(guān)系r 的實(shí)體對的集合和具有路徑p 的實(shí)體對的集合，P(r|p)=|R(p)∩R(r)|/|R(p)|表示由路徑p 推理出關(guān)系r 的概率.先反向求出由所有路徑都不能推導(dǎo)出關(guān)系r 的概率，再用1 減去它，從而得到能夠通過路徑推導(dǎo)出關(guān)系r 的概率.

然而，這種方式需要對知識(shí)圖譜進(jìn)行遍歷，在大規(guī)模知識(shí)圖譜中，這種操作會(huì)帶來極大的開銷，在實(shí)際操作中很顯然是不可行的.因此決定首先將實(shí)體和關(guān)系嵌入到向量空間，然后用關(guān)系和路徑的向量的余弦相似度來代替P(r|p)，得到公式(2).

這里sim(p，r)表示由路徑p 和關(guān)系r 的向量的余弦相似度.根據(jù)PTransE 的原理，如果路徑p 和關(guān)系r 的向量的距離越近(即它們的相似度越高)，則由路徑p 推理出關(guān)系r 可能性就越高，即sim(p，r)和P(r|p)是正相關(guān)的.可以通過訓(xùn)練使 sim(p，r)≈P(r|p).因此，從理論上來說，用 sim(p，r)來替代P(r|p)是可行的.

但是，余弦相似度的計(jì)算公式對其自變量求導(dǎo)數(shù)值為0，這對數(shù)據(jù)集的訓(xùn)練是不利的，因此決定用 tanh 函數(shù)將的值映射到區(qū)間［0，1］內(nèi)來代替余弦相似度，令 sim，然后通過訓(xùn)練使 sim(p，r)≈P(r|p).

關(guān)于這個(gè)問題，陸九淵心學(xué)認(rèn)為，心即是理。即，他認(rèn)為“本心”與宇宙天理是同一的、完全一致的。雖然“本心”不等于人的全部內(nèi)心，但“本心”是存在于每一個(gè)各色人等的內(nèi)心中的。陸九淵說：“人皆有是心，心皆具是理。”[3]所以在陸九淵看來，權(quán)威不在外，而在內(nèi)。他說：“人孰無心，道不外索。”[3]

之后，需要再加入TransE 的部分，因?yàn)椴⒉皇敲恳粚?shí)體之間都有路徑，而且三元組自身所包含的隱含信息也是有重要意義的.當(dāng)然，為了和路徑推理部分保持一致，這里TransE 部分將變形為 sim(h+r，t).

最后，加入?yún)?shù)μ∈(0，1)調(diào)節(jié)TransE 變體和路徑推理兩種方式的權(quán)重，從而得到最終的評(píng)價(jià)函數(shù):

3.2 損失函數(shù)

延續(xù)了 TransE 系列模型的損失函數(shù)的構(gòu)建方式，對PSTransE 構(gòu)造了基于邊界的損失函數(shù):

其中:

L(h，r，t)是對三元組的約束，L(p，r)是對路徑和關(guān)系對的約束，L(P)是通過約束使得 sim(p，r)≈P(r|p).［x］+=max(0，x)，γ 是邊界值，使正實(shí)例和負(fù)實(shí)例分開.S 是知識(shí)圖譜在正確三元組的集合，S－={(h'，r，t)∪(h，r'，t)∪(h，r，t')}是錯(cuò)誤三元組的集合，通過隨機(jī)替換一個(gè)三元組的h，r，t之一獲得.

本文采用隨機(jī)梯度下降(SGD)方法來最優(yōu)化損失函數(shù).正三元組(知識(shí)圖中的三元組)被隨機(jī)多次遍歷.當(dāng)訪問一個(gè)正三元組(h，r，t)時(shí)，通過用知識(shí)圖中的其他實(shí)體或關(guān)系替換(h，r，t)的三個(gè)分量中的一個(gè)，隨機(jī)構(gòu)造一個(gè)負(fù)三元組(h'，r'，t').此外，和 TransE 系列模型一樣，對 h，r，t 的向量的范數(shù)添加約束 h2≤1，r2≤1，t2≤1.

算法具體步驟如算法1 所示.

3.3 路徑選擇

大規(guī)模知識(shí)圖譜中，每一個(gè)實(shí)體對之間存在著大量路徑，將所有路徑都納入計(jì)算無疑是不切實(shí)際的.為了提高計(jì)算效率，我們只選擇長度不超過3 的路徑.另外，并非所有路徑都對當(dāng)前推理有用，因此采用文獻(xiàn)［9］中提出的路徑約束資源分配算法(path-constraint resource allocation algorithm，PCRA)來計(jì)算路徑的可靠性，只選擇可靠性超過0.01 的路徑.

4 實(shí) 驗(yàn)

我們采用 Freebase 的子集 DB15k［4］和 WordNet 的子集WN18［4］作為實(shí)驗(yàn)的數(shù)據(jù)集來測試我們的PSTransE 模型.表1 為這兩個(gè)數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù).此次實(shí)驗(yàn)將通過實(shí)體預(yù)測(Entity Prediction)和關(guān)系預(yù)測(Relation Prediction)兩個(gè)任務(wù)來評(píng)價(jià)我們的模型，并與其他模型做出對比.

表1 數(shù)據(jù)集統(tǒng)計(jì)信息Table 1 Data sets statistics

實(shí)體預(yù)測和關(guān)系預(yù)測是鏈接預(yù)測(Link Prediction)的子任務(wù)，目標(biāo)是預(yù)測一個(gè)缺失三元組缺失的部分，顧名思義，實(shí)體預(yù)測的目標(biāo)是預(yù)測缺失的實(shí)體，關(guān)系預(yù)測的目標(biāo)是預(yù)測缺失的關(guān)系，二者都是知識(shí)推理的重要內(nèi)容.

4.1 實(shí)體預(yù)測

實(shí)體預(yù)測是預(yù)測三元組＜?，r，t＞或＜h，r，?＞中缺失的實(shí)體，測試的方法如下:

1)從測試數(shù)據(jù)集中取出一個(gè)測試三元組＜h，r，t＞.

2)數(shù)據(jù)集中所有實(shí)體分別替換頭實(shí)體(這里示例為頭實(shí)體預(yù)測，在尾實(shí)體預(yù)測中替換的是尾實(shí)體)，構(gòu)造三元組＜e1，r，t＞，＜e2，r，t＞，＜e3，r，t＞…＜en，r，t＞，其中 e1，e2，e3…en∈E，n 為數(shù)據(jù)集中實(shí)體的數(shù)量.

3)對構(gòu)造出的三元組用評(píng)分函數(shù)分別計(jì)算出對應(yīng)的評(píng)分，將構(gòu)造出的三元組按照可靠性從高到低排列(在TransE中評(píng)分取值范圍是［0，+∞)，評(píng)分越低越好，在這一步中需要按評(píng)分從低到高排列;而在本文中，評(píng)分取值范圍是［0，1］，評(píng)分越高越好，在這一步中需要按評(píng)分從高到低排列)，記錄測試三元組＜h，r，t＞的排名.

4)重復(fù)1)2)3)，直到測試集中所有三元組都測試完成.

評(píng)價(jià)指標(biāo)有兩個(gè)，分別是 mean rank 和 hits@10.mean rank 是測試數(shù)據(jù)集中所有測試三元組排名的平均值，hits@10是測試數(shù)據(jù)集中三元組排名達(dá)到前10 的概率.一種好的鏈接預(yù)測方法，應(yīng)當(dāng)具有較低的mean rank 和較高的hits@10.

另外，應(yīng)該注意到，如果一個(gè)在測試過程中構(gòu)造的三元組在知識(shí)圖譜中存在，即該三元組實(shí)際上是正確的，那么將它排在測試三元組＜h，r，t＞之前也是合理的.為了消除這個(gè)問題的影響，測試過程中在對每一個(gè)測試三元組的排名之前，將這些已經(jīng)存在于訓(xùn)練集、驗(yàn)證集和測試集中的正確三元組剔除(不包括測試目標(biāo)＜h，r，t＞).我們將經(jīng)過這樣處理的結(jié)果成為“Filter”，而未經(jīng)上述處理的結(jié)果成為“Raw”，毫無疑問，“Filter”的評(píng)價(jià)結(jié)果比“Raw”更重要.

為了使的PSTransE 模型的效果達(dá)到最佳，設(shè)置SGD 的學(xué)習(xí)率 λ=0.001，邊界值 γ=0.2，表示維度 d=100，權(quán)重參數(shù) μ=0.8.實(shí)驗(yàn)結(jié)果如表2 所示.作為對照的有 TransE［4］，TransH［5］，TransR［6］，PTransE［9］等模型.PTransE 求得路徑向量的方式有三種:關(guān)系向量求和(ADD)，關(guān)系向量求乘積(MUL)和通過循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)，但是后兩種的效果并不好，這里只選取了PTransE(ADD)的結(jié)果作為對照.另外，由于有些模型只給出了在數(shù)據(jù)集FB15k 上的實(shí)驗(yàn)結(jié)果，這里也只顯示了FB15k 上的實(shí)驗(yàn)結(jié)果作為對照.

表2 在FB15k 上實(shí)體預(yù)測結(jié)果Table 2 Evaluation results of entity prediction on FB15k

表3 關(guān)系預(yù)測結(jié)果Table 3 Evaluation results of relation prediction

正如表3 所示，PSTransE 表現(xiàn)出了比其他作為對照的模型更好的效果.PSTransE 在mean rank(raw)上表現(xiàn)略差，但是在mean rank(filter)上表現(xiàn)是最好的.這是因?yàn)榕判虻臅r(shí)候一些正確三元組的干擾，而filter 這個(gè)過程正是為了避免這些干擾才做的.作為對照的方法中，相對于考慮步長不超過2 的PTransE 表現(xiàn)最佳.而與該方法相比，PSTransE 在 mean rank上提高了25.9%，在 hits@10 上提高了 0.8%.由此可見，我們的方法是有優(yōu)勢的.

4.2 關(guān)系預(yù)測

關(guān)系預(yù)測的方法與實(shí)體預(yù)測類似，只不過將替換的目標(biāo)從實(shí)體改為關(guān)系.由于知識(shí)圖譜中關(guān)系數(shù)量較少，hits@10 難以比較不同方法的優(yōu)劣，在這里用hits@1 來代替hits@10.

如表3 所示，在兩個(gè)數(shù)據(jù)集上，我們的方法都表現(xiàn)出了比對照方法更好的效果.在FB15k 上相對于表現(xiàn)最好的方法提升了不超過1%，但是在WN18 上提升了11.9%.這大概是因?yàn)閃N18 具有更多的實(shí)體，我們通過構(gòu)建實(shí)體對來查找路徑得到的路徑也就更多，而我們的方法在路徑推理的部分是更合理的.

5 結(jié) 論

本文根據(jù)PTransE 在考慮路徑信息的時(shí)候通過簡單的加權(quán)平均值方法而忽略了單一路徑在推理時(shí)有可能起決定性作用的缺點(diǎn)，提出了一種新的方法PSTransE，該方法在考慮實(shí)體之間多條路徑信息的同時(shí)，強(qiáng)調(diào)了對推理結(jié)果高支持度的路徑的作用，使得在某條路徑對推理結(jié)果支持度為100%的情況下，能夠直接確定推理結(jié)果而無需考慮其他路徑.實(shí)驗(yàn)表明，我們的方法比起PTransE 來說具有更好的效果.

基于 PTransE 的其他方法(如 RPE，PaSKoGE 等)和PSTransE 并不沖突，這些方法對PTransE 做出的改進(jìn)，完全可以應(yīng)用到PSTransE 上去.這對性能的提升和對計(jì)算開銷的影響將是我們進(jìn)一步研究的內(nèi)容.