2020.1.2更新
A Re-evaluation of Knowledge Graph Completion Methods
這篇文章評(píng)估了以下幾個(gè)模型的真實(shí)表現(xiàn)移盆，想知道各模型具體evaluation的可以看這篇文章揪罕√殖停總結(jié)就是坚踩，目前看來(lái)最有意義的模型應(yīng)該還是最早的ConvE注服。
另外ConvE在計(jì)算參數(shù)這一塊有些問(wèn)題庇楞，具體可以看
https://github.com/TimDettmers/ConvE/issues/57
同時(shí)ConvE還有一個(gè)正統(tǒng)的升級(jí)版本(填了future work的坑):
InteractE
至于為什么ConvE能在那么多模型中脫穎而出(像那么多模型聲稱ConvE有缺陷但是還比不上ConvE)捏卓，個(gè)人感覺(jué)ConvE的本質(zhì)其實(shí)也是將嵌入向量映射到別的空間去表征他极祸，而得益于卷積結(jié)構(gòu)強(qiáng)大的特征提取能力，可以獲得很好的參數(shù)利用率(parameter efficient)怠晴。
這個(gè)也可以看看:
https://github.com/irokin/Experiments-Results-for-Link-Prediction
本文旨在比較知識(shí)庫(kù)補(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ù)測(cè)(link prediction)之前的研究工作都聚焦于淺層快速的模型使其可以應(yīng)用于大型知識(shí)圖譜稿械，但是性能會(huì)受制于淺層的架構(gòu)。這篇文章中作者提出了一個(gè)多層卷積模型ConvE用于鏈路預(yù)測(cè)冲粤。這篇文章/模型主要的亮點(diǎn)有:
1.提出的ConvE除了實(shí)驗(yàn)結(jié)果好美莫，參數(shù)利用率高（相同表現(xiàn)下參數(shù)是DistMult的八分之一页眯，R-GCN的十七分之一），使用了1-N score使訓(xùn)練和測(cè)試加快了三百倍厢呵，并且在復(fù)雜的圖結(jié)構(gòu)(含有高入度節(jié)點(diǎn))上效果很好窝撵。
2.NLP中使用的CNN都是Con1D(比如Text-CNN)夭禽，一維卷積以句子為單位來(lái)卷積鲫凶。本文構(gòu)思了ConV2D的實(shí)現(xiàn)方法猾瘸，即三元組的得分函數(shù)是由二維卷積獲得宛徊。
3.提出(并不是第一個(gè)發(fā)現(xiàn))一些數(shù)據(jù)集比如WN18和FB15k有測(cè)試集泄漏(test set leakage)的問(wèn)題，即測(cè)試集中的三元組可以通過(guò)翻轉(zhuǎn)訓(xùn)練集中的三元組得到描扯，比如測(cè)試集中有(s,hyponym,o) 而訓(xùn)練集中有(o,hypernym,s)映九。這個(gè)問(wèn)題的存在導(dǎo)致一些很簡(jiǎn)單的模型就可以在某些數(shù)據(jù)集上實(shí)現(xiàn)SOTA鳍悠。作者構(gòu)造了一個(gè)簡(jiǎn)單的inverse model來(lái)衡量這個(gè)問(wèn)題的嚴(yán)重性哩都，還清洗了部分?jǐn)?shù)據(jù)集來(lái)解決這個(gè)問(wèn)題魁兼。
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)系沒(méi)有考慮全局相同維度的關(guān)系咐汞，所以ConvE無(wú)視了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并沒(méi)有錄入,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ò)詳見(jiàn)知乎專欄)热芹。這篇文章/模型主要的亮點(diǎn)是
1.第一篇在KBC任務(wù)中加入膠囊網(wǎng)絡(luò)的模型.
2.在WN18RR上獲得了SOTA的MR贱傀，F(xiàn)B15k-237上獲得了SOTA的MRR和Hits@10(aperswithcode榜單沒(méi)有錄入)。
3.文章也在搜索個(gè)性化(search personalization)的數(shù)據(jù)集中做了嘗試伊脓。搜索個(gè)性化就是相同的搜索關(guān)鍵詞府寒，對(duì)不同的用戶返回不同的結(jié)果，抽象為三元組(submitted query,user pro?le,returned document) 报腔，這里就不深入展開(kāi)了株搔。
4.實(shí)驗(yàn)最后全面對(duì)比了ConvKB和CapsE，CapsE對(duì)many-to-many類型的三元組建模能力很強(qiáng)纯蛾。
這里注意到WN18RR中存在最多的關(guān)系是hypernym纤房，ConvE中提到的test leakage 問(wèn)題舉例也就是hypernym和hyponym的轉(zhuǎn)置問(wè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的榜單中沒(méi)有記錄。
因?yàn)槭菐讉€(gè)模型的橫向比較蛾派，所以這里只解釋Conv-TransE的結(jié)構(gòu)俄认，Conv-TransE是ConvE的改進(jìn)版，decoder沒(méi)有采用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)行卷積(沒(méi)錯(cuò)是Conv1D)豌研。之后將卷積后得到的特征圖(因?yàn)槭荂onv1D所以是向量)拼接起來(lái)妹田，和權(quán)重向量w進(jìn)行內(nèi)積。輸出越小表明這個(gè)三元組越可靠(注意ConvKB的損失函數(shù)里沒(méi)有負(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)是由卷積過(guò)后的C個(gè)k維特征圖Mc(es,er)堆疊起來(lái)房铭，通道c的單張?zhí)卣鲌DMc(es,er)=[mc(es,er,0),...,mc(es,er,k-1)]驻龟，上圖是向量中第n位元素mc(es,er,n)的計(jì)算公式「追耍看起來(lái)花里胡哨的翁狐，其實(shí)就是卷積操作:wc是通道c，2xk卷積核的參數(shù)凌蔬，()里的數(shù)代表矩陣wc的第幾位和嵌入向量的第幾位相乘露懒。將拉平后的向量投影至k維。f()非線性激活函數(shù)文章中沒(méi)提采用什么砂心，估計(jì)和ConvE配置一樣懈词。
Conv-TransE和ConvE唯一的區(qū)別是Conv-TransE輸入的嵌入向量沒(méi)有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ù)，輸出越大說(shuō)明三元組(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開(kāi)始分瘦，其實(shí)和ConvE是一樣的這里從左到右算作三步:
1我們從WGCN層獲得所有實(shí)體和關(guān)系的嵌入矩陣，隨后查詢矩陣獲得es和er的嵌入向量(各k維琉苇，圖中的話是4維)嘲玫。
2.上下堆疊后進(jìn)行卷積(也就是這里和ConvE不一樣，沒(méi)有reshape并扇，同時(shí)Conv-TransE中沒(méi)有dropout)去团。按照?qǐng)D中卷積核為2x3，3通道。得到的三個(gè)特征圖疊起來(lái)便是Scoring Function中的M(es,er)土陪，矩陣維度3x4昼汗。
3.將上一步中的矩陣?yán)保S后做全連接到嵌入維度旺坠，之后和ConvE中1-N scoring一樣和所有實(shí)體嵌入向量做內(nèi)積乔遮，隨后取對(duì)數(shù)sigmoid函數(shù)后輸出分布。輸出越大說(shuō)明三元組(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í)為維改抡。文章之后提到試過(guò)1-0.1N收斂太慢，默認(rèn)的話N=系瓢。這里應(yīng)該是直接全部反向傳播沒(méi)有做負(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詳見(jiàn)TransE 4.2節(jié))。
CapsE
負(fù)樣本采樣和ConvKB一樣是采用了Bernoulli trick(TransH中提出的一種負(fù)例采樣技巧旨在減少產(chǎn)生false negative
Conv-TransE
文章中沒(méi)有提藐窄，只提到了同樣酬土。猜測(cè)損失函數(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)系，比如測(cè)試集中的(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í)體)類型的三元組专甩，沒(méi)有(實(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的提升感覺(jué)有一些自圓其說(shuō)，下面看圖就知道了)种樱。
這里再貼一下paperswithcode的SOTA榜單:
FB15K-237 Link Prediction
WN18RR Link Prediction
同時(shí)這幾篇文章中的結(jié)果都是在“Filtered” 的數(shù)據(jù)集上蒙袍，意為在處理過(guò)了生成的負(fù)例(詳見(jiàn)TransE 4.2節(jié))。
ConvE
本文中作者構(gòu)建了一個(gè)只識(shí)別轉(zhuǎn)置關(guān)系的模型Inverse Model嫩挤，訓(xùn)練時(shí)提取出三元組滿足轉(zhuǎn)置的所有關(guān)系r害幅，測(cè)試時(shí)給到(s,r1,?)時(shí)模型尋找測(cè)試集外是否有三元組(o,r2,s)并且將所有可能的o作為預(yù)測(cè)結(jié)果(大致是這樣，感覺(jué)文章也沒(méi)有講的特別清楚)岂昭。
使用Adam優(yōu)化以现，超參數(shù)設(shè)置為嵌入維度k=200，batch size 128约啊，學(xué)習(xí)率0.001邑遏，label smoothing0.1(label smoothing起到抑制過(guò)擬合的效果,修改損失函數(shù)中的ti使其平滑不再是0或1)，卷積通道數(shù)文章中沒(méi)有給出恰矩，代碼中為32通道记盒。
圖中可以看到在新的數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果明顯低了很多，Inverse Model尤其明顯枢里，說(shuō)明了WN18和FB15k的test leakage 的問(wèn)題非常嚴(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)沒(méi)有TransE好嚼沿，并且ConvKB優(yōu)于ConvE是因?yàn)閼?yīng)用了transitional特性(然鵝FB15K-237結(jié)果并沒(méi)有被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é)果并沒(méi)有獲得提升(FB15K-237-Attr本來(lái)就是喂給WGCN的)猿规。
