461
綜述 | 知識圖譜向量化表示
前言
知識圖譜主要的目標是用來描述真實世界中間存在的各種實體和概念，以及它們之間的關聯關係。知識圖譜常被應用於以下幾個方麵：（1）搜索（2）聊天機器人和問答係統。近年來一部分學者嚐試將知識圖譜引入到推薦係統中，並且取得了不錯的結果。本文選擇了八篇知識圖譜向量表示的論文進行介紹。
Translating embeddings for modeling multi-relational data
Bordes A, Usunier N, Weston J, et al. NIPS. 2013.
寫作動機
之前像 single layer model 以及 NTN 等傳統方法，存在著訓練複雜和不易拓展等問題。本文提出了一種將實體與關係嵌入到低維向量空間中的簡單模型 TransE。該模型已經成為了知識圖譜向量化表示的 baseline，並衍生出不同的變體。
模型
△ 目標函數
△ 算法流程
正如目標函數所述，算法核心是令正例的 h+r-l 趨近於 0，而負例的 h+r-l 趨近於無窮大，這裏的 d 表示 L1 或 L2 範式， \gamma 表示邊際距離。整個 TransE 模型的訓練過程比較簡單，首先對頭尾節點以及關係進行初始化，然後每對一個正例取一個負例樣本（本文負例選取方式為固定中間的 relation，頭尾節點任意替換一個），然後利用 hinge loss function 盡可能使正例和負例分開，最後采用 SGD 方法更新參數。
Knowledge Graph Embedding by Translating on Hyperplanes
Wang Z, Zhang J, Feng J, et al. AAAI. 2014.
寫作動機
雖然 TransE 模型具有訓練速度快、易於實現等優點，但是它不能夠解決多對一和一對多關係的問題。以多對一關係為例，固定 r 和 t，TransE 模型為了滿足三角閉包關係，訓練出來的頭節點的向量會很相似。而本文提出一種將頭尾節點映射到關係平麵的 TransH 模型，能夠很好地解決這一問題。
以下圖為例，對於多對一關係，TransH 不在嚴格要求 h+r-l=0，而是隻需要保證頭結點和尾節點在關係平麵上的投影在一條直線上即可，因此能夠得到圖中頭結點向量（紅線）正確的表示。
模型
本文的模型其實比較簡單，首先通過上述公式 1 分別將 head 和 tail 節點映射到關係 r 所對應的平麵，之後整個訓練方式同 TransE 一致。雖然 TransH 比 TransE 增加了一步向量轉換，但其實整體參數隻增加了 wr 一項，整體的算法效率還是很高的。
此外，不同於 TransE 模型隨機替換 head 和 tail 節點作為負例的方法，本文分別賦給頭結點和尾節點一個采樣概率，具體計算公式計算如下：
即對於多對一的關係，替換尾節點，對於一對多的關係，替換頭節點。
Learning Entity and Relation Embeddings for Knowledge Graph Completion
Lin Y, Liu Z, Zhu X, et al. AAAI. 2015.
寫作動機
TransE 和 TransH 都假設實體和關係嵌入在相同的空間中。然而，一個實體是多種屬性的綜合體，不同關係對應實體的不同屬性，即頭尾節點和關係可能不在一個向量空間中。為了解決這個問題，本文提出了一種新的方法 TransR。
模型
TransR 的基本思想如上圖所示。對於每個元組（h，r，t），首先將實體空間內的實體通過 Mr矩陣投影到關係 r 所在的空間內，得到 hr 和 tr ，然後使 hr+t≈tr。特定的關係投影（彩色的圓圈表示）能夠使得頭/尾實體在這個關係下靠近彼此，使得不具有此關係（彩色的三角形表示）的實體彼此遠離。
此外，僅僅通過單個的關係向量還不足以建立從頭實體到尾實體的所有轉移，即對於同一條關係 r 來講，r 具有多種語義上的表示。本文提出對不同的頭尾實體進行聚類和並且學習到關係在不同聚類簇的表示。作者這裏首先利用 TransE 預訓練（h，r，t）三元組，並且對 t-h（也就是關係 r）進行聚類，這樣對於關係 r 來講，頭尾節點會被分到相應的簇中，並且利用下麵的公式進行訓練，該方法也被稱為 CTransR。
Learning Entity and Relation Embeddings for Knowledge Graph Completion
Lin Y, Liu Z, Zhu X, et al. AAAI. 2015.
寫作動機
之前的 TransE、TransH 和 TransR 都認為每種關係隻對應一種語義表示，而在實際情況中，關係r可能代表不同的含義。如下圖所示，對於關係 location 來講，它既可以表示山脈-國家之間的關係，又可以表示為地區-國家之間的關係，因此本文提出一種基於動態矩陣的 TransD 模型來解決這一問題。
模型
TransD 模型同 CTransR 模型一樣，都是為了解決關係的多種語義表示。相比較 CTransR 采用聚類的方式，TransD 提出一種動態變化矩陣的方法。具體公式如下圖所示：
對於（h'，r'，t'）兩個實體和一種關係來講，它們分別有兩種表示，一種是構建映射矩陣的表示（hp，rp，tp），另外一種是自身的語義表示（h，r，t）。h 和 t 的動態轉移矩陣分別由其自身的映射矩陣和關係r的映射矩陣所決定，而不是像 TransR 一樣映射矩陣隻和關係 r 相關。
此外，該模型的一個亮點在於它將 TransR 的矩陣運算轉換成了向量間的運算，運算速度會大幅提升，具體公式如下：
TransA: An Adaptive Approach for Knowledge Graph Embedding
Xiao H, Huang M, Hao Y, et al. Computer Science. 2015.
寫作動機
TransE 從根本上講是一種歐式距離的計算，其圖形對應的是一個圓，從下圖可知藍色部分為正例，紅色部分為負例，TransE 模型劃分錯了七個點。而本文提出了一種基於馬氏距離的 TransA 模型，其 PCA 降維圖形對應的是一個橢圓，該模型隻分錯了三個點。
此外，之前的方法將等價對待向量中的每一維，但實際上各個維度的重要性是不同的，隻有一些維度是有效的，而某些維度被認為是噪音，會降低效果。
如下圖 2 所示，對於關係 haspart 而言，TransE 模型根據歐氏距離計算方法生成了像 Room-has-Goniff 這樣的三元組，而正確的結果卻是 Room-has-Wall。我們對 x，y 軸進行分解，發現 Room 在 x 軸上距離 Wall 更為相近，因此我們可以認為該圖在 x 軸維度上更加重要。TransA 模型通過引入加權矩陣，賦給每一維度權重。
模型
其實 TransA 模型總體來看比較簡單，相比較 TransE 模型，本文引入了 Wr 矩陣為不同維度的向量進行加權，並利用 LDL 方法對 Wr 進行分解，Dr 是一個對角陣，對角線上的元素表示不同維度上的權重。本篇文章的一個亮點在於通過圖像來描述不同的損失度量函數，給人直觀的感覺。
TransG: A Generative Mixture Model for Knowledge Graph Embedding
Xiao H, Huang M, Zhu X. TransG. ACL. 2016.
寫作動機
本文提出的 TransG 模型同 CTransR、TransD 一致，都是為了解決關係的多種語義表達問題。作者首先做了一個比較有意思的實驗，首先對預訓練好的 t-h 進行聚類（也就是關係 r），發現對於每種關係 r 來講，會得到不同的簇。從現實意義來看也不難理解，對於關係 Country，我們可以聚類得到美國、歐洲和其他國家這三個簇，表示電影所屬的不同國家。
模型
TransG 利用貝葉斯非參數混合模型對一個關係生成多個表示，其實 TransG 的本質同 CTransR 一致，都是利用聚類方法生成 r 的不同種表示。不同點在於 CTransR 利用預訓練的 TransE 向量進行聚類，而 TransG 采用邊訓練邊聚類的方法。具體公式如下：
M 表示聚類的數目，πr,m 表示關係 r 的第 m 中表示的權重。
Knowledge Graph Completion with Adaptive Sparse Transfer Matrix
Ji G, Liu K, He S, et al. AAAI. 2016.
寫作動機
Knowledge Graph 中麵臨的兩個主要問題，分別是 heterogeneous（異構性）和 unbalanced（不平衡性）。
異構性表示知識圖譜中關係所連接的節點數目差異較大，不平衡性表示關係所連接的頭尾節點數目不同。如果隻用一個模型處理所有關係的話可能會導致對簡單關係過擬合，對複雜關係欠擬合。本文提出兩種模型 Transparse (share) 和 Transparse (separate) 分別解決這兩個問題。
模型
Transparse 模型本質是 TransR 模型的擴展，區別在於對於那些複雜的關係令其轉移矩陣稠密，而對於簡單的關係令其轉移矩陣稀疏。這個稀疏程度由 θr 控製，具體計算公式如下：
θmin 表示 0-1 之間的一個控製變量，Nr 表示關係 r 連接實體對的數量，Nr* 表示其中連接的最大值，同理 表示關係 r 連接的頭\尾實體數，
表示其中的最大值。
share 和separate 的區別在於 separate 模型為 head 和 tail 提供了兩種不同的轉移矩陣，而 share 模型 head 和 tail 的轉移矩陣相同，具體公式如下所述：
該篇文章的亮點在於針對知識圖譜存在的異構性和不平衡性問題，作者分別提出兩種不同的模型來解決，但缺陷是作者並沒有將這兩種模型進行融合，最後在 triplet classification 和 link prediction 上的結果並沒有比 TransD 提升很多。
Locally Adaptive Translation for Knowledge Graph Embedding
Jia Y, Wang Y, Lin H, et al. AAAI, 2016.
寫作動機
之前所有模型的 margin 都是固定不變的，但局部不同的 margin 是否能夠提升模型的效果呢？作者為了證明，首先做了一組實驗，將 FB15K 分成兩個子集，在不同數據集上分別得到達到最優效果的 margin，發現局部最優的 margin 不盡相同。
從理論來講，Margin 變大，更多的數據被訓練，容易導致過擬合。相反，margin 越小，容易欠擬合。所以也證明了 margin 對最終結果的影響。
模型
本文將 margin 分為 entity 和 relation 兩部分，並利用線性插值進行組合。實體部分的 margin 應保證內層圓包含更多的正例，外層圓的外部應盡可能是負例。對於 relation 部分，本文利用 relation 的長度，即 L2 範式來衡量相似度關係。具體公式如下圖所示：
Rh,r 是除了關係 r 之外的所有關係的集合，它使得所有與關係 r 不相近的關係遠離 r。本篇文章比較巧妙地利用局部 margin 的方式，在 link prediction 和 triple classification 結果上有了明顯提升。
最後用一張圖表總結下這 8 篇論文的 9 種模型。
原文發布時間為：2017-10-25
本文作者 : 竇洪健
本文來自雲棲社區合作夥伴“PaperWeekly”，了解相關信息可以關注“PaperWeekly”微信公眾號
最後更新：2017-10-26 11:04:46