2020.1.2更新
A Re-evaluation of Knowledge Graph Completion Methods
這篇文章評(píng)估了以下幾個(gè)模型的真實(shí)表現(xiàn)，想知道各模型具體evaluation的可以看這篇文章。總結(jié)就是，目前看來最有意義的模型應(yīng)該還是最早的ConvE。
另外ConvE在計(jì)算參數(shù)這一塊有些問題，具體可以看
https://github.com/TimDettmers/ConvE/issues/57
同時(shí)ConvE還有一個(gè)正統(tǒng)的升級(jí)版本(填了future work的坑):
InteractE
至于為什么ConvE能在那么多模型中脫穎而出(像那么多模型聲稱ConvE有缺陷但是還比不上ConvE)，個(gè)人感覺ConvE的本質(zhì)其實(shí)也是將嵌入向量映射到別的空間去表征他，而得益于卷積結(jié)構(gòu)強(qiáng)大的特征提取能力，可以獲得很好的參數(shù)利用率(parameter efficient)。
這個(gè)也可以看看:
https://github.com/irokin/Experiments-Results-for-Link-Prediction
本文旨在比較知識(shí)庫補(bǔ)全(KBC)最近兩年使用到卷積的幾個(gè)模型。
對(duì)于實(shí)驗(yàn)結(jié)果，由于各家都是在自己的文章里吊打別人，所以下面給出paperswithcode的SOTA榜單作為參考:
FB15K-237 Link Prediction
WN18RR Link Prediction
Introduction
ConvE
AAAI 2018
Convolutional 2D Knowledge Graph Embeddings
code
作者認(rèn)為鏈路預(yù)測(link prediction)之前的研究工作都聚焦于淺層快速的模型使其可以應(yīng)用于大型知識(shí)圖譜，但是性能會(huì)受制于淺層的架構(gòu)。這篇文章中作者提出了一個(gè)多層卷積模型ConvE用于鏈路預(yù)測。這篇文章/模型主要的亮點(diǎn)有:
1.提出的ConvE除了實(shí)驗(yàn)結(jié)果好，參數(shù)利用率高（相同表現(xiàn)下參數(shù)是DistMult的八分之一，R-GCN的十七分之一），使用了1-N score使訓(xùn)練和測試加快了三百倍，并且在復(fù)雜的圖結(jié)構(gòu)(含有高入度節(jié)點(diǎn))上效果很好。
2.NLP中使用的CNN都是Con1D(比如Text-CNN)，一維卷積以句子為單位來卷積。本文構(gòu)思了ConV2D的實(shí)現(xiàn)方法，即三元組的得分函數(shù)是由二維卷積獲得。
3.提出(并不是第一個(gè)發(fā)現(xiàn))一些數(shù)據(jù)集比如WN18和FB15k有測試集泄漏(test set leakage)的問題，即測試集中的三元組可以通過翻轉(zhuǎn)訓(xùn)練集中的三元組得到，比如測試集中有(s,hyponym,o) 而訓(xùn)練集中有(o,hypernym,s)。這個(gè)問題的存在導(dǎo)致一些很簡單的模型就可以在某些數(shù)據(jù)集上實(shí)現(xiàn)SOTA。作者構(gòu)造了一個(gè)簡單的inverse model來衡量這個(gè)問題的嚴(yán)重性，還清洗了部分?jǐn)?shù)據(jù)集來解決這個(gè)問題。
ConvKB
NAACL-HLT 2018
A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network
code
本文也是用卷積去處理三元組，與ConvE不同的是ConvKB中三元組被作為三列的矩陣輸入每列為三元組元素的嵌入同時(shí)卷積為Conv1D。作者認(rèn)為ConvE只考慮了局部不同維度的關(guān)系沒有考慮全局相同維度的關(guān)系，所以ConvE無視了transitional特性(我的理解就是ConvE中只對(duì)頭實(shí)體和關(guān)系卷積，而ConvKB對(duì)三個(gè)元素都進(jìn)行了卷積并且由于三元組表現(xiàn)為三列所以卷積時(shí)三列相同維度被一起提取特征)。這篇文章/模型主要的亮點(diǎn)是在WN18RR和FB15K-237上獲得了SOTA的MRR和Hits@10(然鵝paperswithcode的榜單中FB15K-237并沒有錄入,WN18RR排名第九)。
CapsE
NAACL-HIT 2019
A Capsule Network-based Embedding Model for Knowledge Graph Completion and Search Personalization
code
本文的作者和ConvKB是一個(gè)人，Dai Quoc Nguyen，有一個(gè)合作者叫Dat Quoc Nguyen之前差點(diǎn)把這兩人當(dāng)作一個(gè)人了署名縮寫都一樣。這兩人在KBC領(lǐng)域很活躍，不知道是不是親兄弟。
模型在之前ConvKB的基礎(chǔ)上，卷積提取特征圖后加入膠囊網(wǎng)絡(luò)(關(guān)于膠囊網(wǎng)絡(luò)詳見知乎專欄)。這篇文章/模型主要的亮點(diǎn)是
1.第一篇在KBC任務(wù)中加入膠囊網(wǎng)絡(luò)的模型.
2.在WN18RR上獲得了SOTA的MR，F(xiàn)B15k-237上獲得了SOTA的MRR和Hits@10(aperswithcode榜單沒有錄入)。
3.文章也在搜索個(gè)性化(search personalization)的數(shù)據(jù)集中做了嘗試。搜索個(gè)性化就是相同的搜索關(guān)鍵詞，對(duì)不同的用戶返回不同的結(jié)果，抽象為三元組(submitted query,user pro?le,returned document) ，這里就不深入展開了。
4.實(shí)驗(yàn)最后全面對(duì)比了ConvKB和CapsE，CapsE對(duì)many-to-many類型的三元組建模能力很強(qiáng)。
這里注意到WN18RR中存在最多的關(guān)系是hypernym，ConvE中提到的test leakage 問題舉例也就是hypernym和hyponym的轉(zhuǎn)置問題。
Conv-TransE(SACN)
AAAI 2019
End-to-end Structure-Aware Convolutional Networks for Knowledge BaseCompletion
code
本文提出了模型SACN( Structure Aware Convolutional Network)。這篇文章/模型主要的亮點(diǎn)是考慮了圖的結(jié)構(gòu)信息，SACN由編碼器WGCN(weighted graph convolutional network)和解碼器Conv-TransE組成，前者獲得圖的結(jié)構(gòu)信息，后者使得模型可以完成Link Prediction。模型在WN18RR和FB15K-237上獲得了SOTA的HITS@1, HITS@3 and HITS@10，結(jié)果paperswithcode的榜單中沒有記錄。
因?yàn)槭菐讉€(gè)模型的橫向比較，所以這里只解釋Conv-TransE的結(jié)構(gòu)，Conv-TransE是ConvE的改進(jìn)版，decoder沒有采用ConvKB是因?yàn)镃onvKB這種直接輸入完整三元組嵌入進(jìn)行卷積的模式不適合SACN端到端模型。
Scoring Function
ConvE
e，r為實(shí)體和關(guān)系的嵌入，ne為訓(xùn)練集中的實(shí)體數(shù)量nr為關(guān)系數(shù)量，對(duì)應(yīng)的嵌入維度為k和k'(一般k=k'，博客之后也默認(rèn)k=k')。在ConvE的scoring function中，f是非線性激活函數(shù)文章中用的是relu+BN，vec()表示將張量拉平為向量，表示用卷積核進(jìn)行卷積操作。[ ]操作符為對(duì)嵌入e和r進(jìn)行變形拼接(2D reshaping)最后得到一個(gè)矩陣。矩陣的維度為kw x kh ，其中kwkh=2k(注意原文中是k=kwkh，這里應(yīng)該是原文有誤，兩個(gè)向量變形拼接為矩陣后元素個(gè)數(shù)不變)。輸出越大表明這個(gè)三元組越可靠。
可以注意到空間復(fù)雜度上ConvE和DistMult是一樣的，即ConvE可以用更少的嵌入維度獲得和DistMult一樣的效果。
ConvKB
可以和ConvE的圖對(duì)應(yīng)著看，對(duì)于輸入的(h,r,t)三元組，將其轉(zhuǎn)換為三元組元素嵌入vh,vr,vt在列方向上拼接組成的矩陣，用1x3的卷積核進(jìn)行卷積(沒錯(cuò)是Conv1D)。之后將卷積后得到的特征圖(因?yàn)槭荂onv1D所以是向量)拼接起來，和權(quán)重向量w進(jìn)行內(nèi)積。輸出越小表明這個(gè)三元組越可靠(注意ConvKB的損失函數(shù)里沒有負(fù)號(hào))。
CapsE
在ConvKB卷積的步驟之后，添加膠囊網(wǎng)絡(luò)。最后輸出的是d維向量e(d是第二層膠囊網(wǎng)絡(luò)中神經(jīng)元數(shù)量)，這個(gè)向量的模越大表明這個(gè)三元組越可靠。
Conv-TransE(SACN)
M(es,er)，C是通道個(gè)數(shù)k是嵌入維度，M(es,er)是由卷積過后的C個(gè)k維特征圖Mc(es,er)堆疊起來，通道c的單張?zhí)卣鲌DMc(es,er)=[mc(es,er,0),...,mc(es,er,k-1)]，上圖是向量中第n位元素mc(es,er,n)的計(jì)算公式?？雌饋砘ɡ锖诘?，其實(shí)就是卷積操作:wc是通道c，2xk卷積核的參數(shù)，()里的數(shù)代表矩陣wc的第幾位和嵌入向量的第幾位相乘。將拉平后的向量投影至k維。f()非線性激活函數(shù)文章中沒提采用什么，估計(jì)和ConvE配置一樣。
Conv-TransE和ConvE唯一的區(qū)別是Conv-TransE輸入的嵌入向量沒有reshape，下文中看模型架構(gòu)會(huì)更很清晰。
這里卷積時(shí)會(huì)zero-padding。
Model
ConvE
所有實(shí)體與關(guān)系的嵌入可以看作為兩個(gè)矩陣，實(shí)體嵌入，關(guān)系嵌入
，
為圖譜中實(shí)體的數(shù)量(注意不等于ne+nr，因?yàn)橛行?shí)體同時(shí)是頭實(shí)體和尾實(shí)體)，
為圖譜中關(guān)系的數(shù)量。嵌入矩陣的每一行即代表一個(gè)實(shí)體或者一個(gè)關(guān)系的嵌入。
按圖中從左到右我們將步驟分為六步:
1.對(duì)于輸入三元組(es，r，eo)，我們首先查詢嵌入矩陣獲得es和er的嵌入向量(各k維，圖中的話是4維)。
2.變形拼接(2D reshaping)得到kw x kh的矩陣(圖中是4x2)。作者在這層加入了dropout(0.2)，即有兩個(gè)元素置為0(dropout并不會(huì)減少維度只是置0，這里順便貼以下dropout實(shí)現(xiàn)keras的源碼:
sample=np.random.binomial(n=1,p=retain_prob,size=x.shape
x *=sample
x /= retain_prob
)
3.卷積后獲得張量，c是通道數(shù)，即卷積核個(gè)數(shù)。同樣的dropout0.2這樣是直接將兩個(gè)通道置0。按照?qǐng)D中c=8，m=3，n=3(這不是卷積核的大小而是卷積后獲得張量的大小，卷積核大小文中實(shí)驗(yàn)使用的是3x3)。
4.拉平后vec()的行向量。隨后使用全連接映射到k維向量(本文實(shí)驗(yàn)采用的k=200，圖里畫的是列向量但是按照文章里的維度標(biāo)識(shí)應(yīng)該得到的是1xk的行向量)，dropout0.3兩個(gè)元素置0。
5.得到的hidden layer k維向量和目標(biāo)尾實(shí)體eo做內(nèi)積并取對(duì)數(shù)，輸出越大說明三元組(es，r，eo)成立的可能性越大。因?yàn)榫矸e操作占了75%以上的計(jì)算時(shí)間，因此要想加快計(jì)算必須要盡可能減少卷積操作的次數(shù)，所以這里我們一次性讓hidden layer和圖譜中所有實(shí)體做內(nèi)積(圖中12個(gè))，這就是1-N score，區(qū)別于只和一個(gè)做內(nèi)積的1-1 score。這樣得到的便是維的向量。
6.sigmoid后輸出分布。注意雖然輸出的分布包含了所有實(shí)體，但是輸入仍是(es，r)頭實(shí)體和關(guān)系2個(gè)k維向量。
ConvKB
圖中元素嵌入維度k=4，作者認(rèn)為這樣的卷積不但考慮到了全局同一維度的特征，更是transitional特性的體現(xiàn)(可能嵌入向量間相同維度運(yùn)算就是transitional特性?)。
值得注意的是，圖中有3個(gè)卷積核，如果我們只保留一個(gè)卷積核且設(shè)置為[1,1,-1]，那ConvKB就會(huì)變成TransE (h+r-t)，所以作者認(rèn)為可以視為對(duì)TransE的傳承。
CapsE
圖中嵌入維度k=4，卷積核個(gè)數(shù)N=5，第二層膠囊網(wǎng)絡(luò)中神經(jīng)元數(shù)量d=2(第一層膠囊網(wǎng)絡(luò)中神經(jīng)元數(shù)量和卷積核個(gè)數(shù)一致)。
和下面的算法流程對(duì)應(yīng)著看:
卷積后的得到的特征圖矩陣對(duì)應(yīng)流程中的u1，...uk(k為嵌入維度，卷積后特征圖的維度也為k)。對(duì)膠囊網(wǎng)絡(luò)感興趣的也可以看知乎專欄。
Conv-TransE
我們把重點(diǎn)放在Conv-TransE接收到輸入實(shí)體嵌入es和關(guān)系嵌入er開始，其實(shí)和ConvE是一樣的這里從左到右算作三步:
1我們從WGCN層獲得所有實(shí)體和關(guān)系的嵌入矩陣，隨后查詢矩陣獲得es和er的嵌入向量(各k維，圖中的話是4維)。
2.上下堆疊后進(jìn)行卷積(也就是這里和ConvE不一樣，沒有reshape，同時(shí)Conv-TransE中沒有dropout)。按照?qǐng)D中卷積核為2x3，3通道。得到的三個(gè)特征圖疊起來便是Scoring Function中的M(es,er)，矩陣維度3x4。
3.將上一步中的矩陣?yán)保S后做全連接到嵌入維度，之后和ConvE中1-N scoring一樣和所有實(shí)體嵌入向量做內(nèi)積，隨后取對(duì)數(shù)sigmoid函數(shù)后輸出分布。輸出越大說明三元組(es，r，eo)成立的可能性越大。
Loss Function
ConvE
訓(xùn)練時(shí)令，訓(xùn)練時(shí)需要最小化的損失函數(shù)如下:
ti是標(biāo)簽，即(es，r，eo)在訓(xùn)練集中存在為1，不存在為0。1-N時(shí)為維。文章之后提到試過1-0.1N收斂太慢，默認(rèn)的話N=。這里應(yīng)該是直接全部反向傳播沒有做負(fù)采樣。
ConvKB
f()是scoring function，加入了對(duì)權(quán)重向量w的L2正則化。同時(shí)負(fù)樣本采樣是采用了Bernoulli trick(TransH中提出的一種負(fù)例采樣技巧旨在減少產(chǎn)生false negative，當(dāng)然即使產(chǎn)生了也會(huì)被filttered詳見TransE 4.2節(jié))。
CapsE
負(fù)樣本采樣和ConvKB一樣是采用了Bernoulli trick(TransH中提出的一種負(fù)例采樣技巧旨在減少產(chǎn)生false negative
Conv-TransE
文章中沒有提，只提到了同樣。猜測損失函數(shù)和ConvE應(yīng)該是一致的。代碼中確認(rèn)一致bceloss。
Experiments
Datasets and test leakage
WN18是WordNet的子集有18個(gè)關(guān)系和40,943個(gè)實(shí)體。FB15K是Freebase的子集有1,345個(gè)關(guān)系和14,951個(gè)實(shí)體。然而在這兩個(gè)數(shù)據(jù)集中94%以及81%的三元組都有轉(zhuǎn)置關(guān)系，比如測試集中的(feline, hyponym, cat)和訓(xùn)練集中的 (cat, hypernym, feline) ，這樣使得任何模型都可以在這些數(shù)據(jù)集上獲得很好的表現(xiàn)。
WN18RR包括11個(gè)關(guān)系和40,943個(gè)實(shí)體，去除了7個(gè)WN18中存在的轉(zhuǎn)置關(guān)系以及對(duì)應(yīng)的三元組。同樣的還有FB15K-237，保留了237個(gè)關(guān)系14,541個(gè)實(shí)體。
因?yàn)樯厦鎯蓚€(gè)數(shù)據(jù)集包含的都是(實(shí)體,關(guān)系,實(shí)體)類型的三元組，沒有(實(shí)體,屬性,值)這類的三元組，所以Conv-TransE文中從FB24K中抽出了78,334個(gè)屬性相關(guān)三元組包含203種屬性，組成了FB15K-237-Attr數(shù)據(jù)集。該數(shù)據(jù)集在Conv-TransE的實(shí)驗(yàn)中并入了FB15K-237的訓(xùn)練集，使得SACN中WGCN學(xué)習(xí)到了更好的實(shí)體及關(guān)系嵌入最終在FB15K-237的訓(xùn)練集上獲得了更好的結(jié)果(其實(shí)都是0.01的提升感覺有一些自圓其說，下面看圖就知道了)。
這里再貼一下paperswithcode的SOTA榜單:
FB15K-237 Link Prediction
WN18RR Link Prediction
同時(shí)這幾篇文章中的結(jié)果都是在“Filtered” 的數(shù)據(jù)集上，意為在處理過了生成的負(fù)例(詳見TransE 4.2節(jié))。
ConvE
本文中作者構(gòu)建了一個(gè)只識(shí)別轉(zhuǎn)置關(guān)系的模型Inverse Model，訓(xùn)練時(shí)提取出三元組滿足轉(zhuǎn)置的所有關(guān)系r，測試時(shí)給到(s,r1,?)時(shí)模型尋找測試集外是否有三元組(o,r2,s)并且將所有可能的o作為預(yù)測結(jié)果(大致是這樣，感覺文章也沒有講的特別清楚)。
使用Adam優(yōu)化，超參數(shù)設(shè)置為嵌入維度k=200，batch size 128，學(xué)習(xí)率0.001，label smoothing0.1(label smoothing起到抑制過擬合的效果,修改損失函數(shù)中的ti使其平滑不再是0或1)，卷積通道數(shù)文章中沒有給出，代碼中為32通道。
圖中可以看到在新的數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果明顯低了很多，Inverse Model尤其明顯，說明了WN18和FB15k的test leakage 的問題非常嚴(yán)重。同時(shí)可以看到ConvE在FB上的表現(xiàn)更好，因?yàn)镕B圖譜更復(fù)雜節(jié)點(diǎn)有更大的入度，而深層模型更適合對(duì)復(fù)雜圖譜建模。
ConvKB
Adam優(yōu)化，超參數(shù)設(shè)置為嵌入維度k=100，batch size 256，學(xué)習(xí)率5e^-6(約等于0.01)，卷積通道數(shù)50。
作者文中還吐槽了ConvE部分表現(xiàn)沒有TransE好，并且ConvKB優(yōu)于ConvE是因?yàn)閼?yīng)用了transitional特性(然鵝FB15K-237結(jié)果并沒有被paperswithcode記錄,WN18RR排名第九)。
CapsE
Adam優(yōu)化，超參數(shù)設(shè)置為嵌入維度k=100，batch size 128，第二層膠囊網(wǎng)絡(luò)神經(jīng)元個(gè)數(shù)d=10，routing algorithm 迭代次數(shù)m =1，F(xiàn)B15K-237 時(shí)卷積核個(gè)數(shù)N=50，學(xué)習(xí)率1e-4(約等于0.02)，WN18RR 時(shí)卷積核個(gè)數(shù)N=400，學(xué)習(xí)率1e?5(約等于0.007) 。
Conv-TransE
Adam優(yōu)化，超參數(shù)設(shè)置為嵌入維度k=200， 學(xué)習(xí)率0.003，F(xiàn)B15K-237 時(shí)100個(gè)卷積核，WN18RR 時(shí)200個(gè)卷積核。
使用FB15K-237-Attr的提升都是0.01微乎其微。(加入FB15K-237-Attr的目的是為了讓編碼器WGCN學(xué)習(xí)到更多的節(jié)點(diǎn)信息及圖結(jié)構(gòu))
可以看到僅僅使用Conv-TransE就可以獲得不錯(cuò)的結(jié)果。作者還實(shí)驗(yàn)了加入ConvE+FB15K-237-Attr，實(shí)驗(yàn)結(jié)果并沒有獲得提升(FB15K-237-Attr本來就是喂給WGCN的)。
