號外！又一撥頂會論文乾貨來襲！
據芯君瞭解，本次預講會在學術圈的火爆程度完全超出了主辦方的想象，開放報名的短短几天就全面滿額了，以至於主辦方不得不設定條件篩選參會者。
讀芯君作為本次預講會的活動媒體，將全程跟隨大會，為大家全程紀錄活動中最前沿的觀點，最有價值的成果，並特邀預講會論文報告者聯合為讀者朋友們推出預講會系列組文，向你展示頂會最新論文成果。
ACL 2018
利用簡單約束提升知識圖譜的表示學習
Improving Knowledge Graph Embedding Using Simple Constraints
中國科學院信息工程研究所
Institute of Information Engineering, Chinese Academy of Sciences
【摘要】獲得知識圖譜中實體和關係的向量化表示，即表示學習，是近幾年的一個研究熱點，相關技術可以用於大規模知識推理。早期的模型通過定義元組上的簡單模型實現這個任務，儘管效率高，但是推理精度有限。近期的一些嘗試主要包括在基本模型上利用外部信息以及設計更復雜的元組模型上。在這篇工作中，我們嘗試另一種思路，通過對基本模型施加一些簡單約束來提升表示學習的效果。我們考慮了對實體添加非負性約束，以及對關係添加蘊含性約束，前者可以幫助我們學到更緊湊，更具有可解釋性實體向量；後者將邏輯蘊含結構編碼到關係的分佈式表示中。這些簡單的約束在提升性能的同時，又不會增加基本模型的複雜度。我們在公開數據集FB15K,WN18,DB100K上做了測試，證明這種簡單約束可以顯著提高基本模型的性能，表現甚至比一些更復雜的模型還要好，此外，我們還對實體和關係向量的可解釋性做了一個可視化分析，我們的代碼和數據可以通過https://github.com/iieir-km/ComplEx-NNE_AER獲得。
1 引言
在過去的幾十年中，大規模知識圖譜獲得了巨大的發展，誕生了諸如WordNet, Freebase，GoogleKnowledge Valut這樣的項目。知識圖譜可以形式化地表示為一個三元組集合
，其中
是實體，
是關係。這種結構化的知識表示方式為自然語言處理和信息檢索的諸多下游應用，比如問答，學術檢索，機器閱讀等都提供了豐富的背景知識，具有非常廣闊的應用前景。
近年來，知識圖譜的表示學習受到了大家廣泛的關注，其關鍵思想是獲得實體和關係的向量化表示，這種向量化表示在簡化了操作的同時又保持了圖的內在結構。早期在該方向上的探索主要是單純利用元組數據，並在之上設計簡單的打分模型。這類基本模型雖然高效，但是推理精度有限。近期的一些工作為了進一步提升推理精度，主要有兩種方式，第一種方式是利用外部數據，比如文本，邏輯規則等，但這種方式會依賴於具體的數據，缺乏通用性；第二種是設計更復雜的模型，但這種方式會同時增加計算代價。
在這篇工作中，我們轉而嘗試對基本模型添加一些簡單的約束，特別的，我們對實體添加了非負性約束，對關係添加了近似蘊含性約束。前者要求實體向量處在一個非負的向量空間內，非負性約束在詞向量，矩陣分解的領域已經被廣泛研究過，非負性可以使得我們獲得更加緊湊，更加稀疏的向量表示，使學到的向量更加具有可解釋性。後者可以將邏輯蘊含結構編碼到向量的表示中，在基本模型之上利用邏輯規則在之前已經有過很多研究，與我們非常相似的一篇研究是這篇工作，同樣利用了次序嵌入的方法將邏輯蘊含編碼到向量的表示中，但是這篇工作主要針對實體對進行建模，不能預測未在訓練集中出現過的實體對，同時該方法也只考慮了嚴格的蘊含規則，沒有建模近似性。
我們最終在公開的數據集上測試了方法的性能，在三個數據集上均顯著地超過對比方法，甚至比一些複雜的基於深度網絡的模型還要好。同時我們也對學到的實體和關係向量的可解釋性做了一個可視化分析，證明添加了簡單約束之後，模型具有了更好的可解釋性。
2 相關工作
相關工作關主要有三類：
第一類包含基本表示學習模型，其中有基於位移的模型TransE及其變種，以及基於語義匹配的模型RESCAL及其變種，這些模型都只用到了元組信息。基於這些基本的模型，一些模型利用外部信息來提高表示學習的性能，比如利用關係路徑，利用文本信息等。另外，也有一些模型設計更復雜的打分函數來提高性能，比如在這篇工作中，就採用卷積神經網絡設計打分函數。
第二類與我們相關的工作是利用邏輯規則的模型，但以上大部分工作都需要實例化邏輯規則，在空間和時間上都比較低效；為了避免實例化，採用次序嵌入的方法，但是這篇工作主要針對實體對進行建模，不能預測未在訓練集中出現過的實體對，同時該方法也只考慮了嚴格的蘊含規則，沒有建模近似性；在這篇工作中，則通過對抗網絡來避免實例化。最與我們相近的一篇工作是，但是這篇工作僅僅考慮了等價和逆反的蘊含，沒有推廣到一般的蘊含，同時也不能建模置信度。
第三類與我們相關的工作是非負表示學習，非負性已經在很多領域都被研究過，之前有研究顯示，非負性能夠導致學到的向量的稀疏性，同時也能學到更具有可解釋性的向量表示。在一些詞向量的研究中也表示，施加非負性約束可以學到更加具有可表示性的向量。
3 方法
我們首先介紹用來建模元組的基本模型，然後介紹非負性約束以及近似蘊含性約束，最後給出最終的模型。
3.1 基本模型
我們採用了ComplEx作為基本嵌入模型，這是目前性能最好的基本表示學習模型之一，ComplEx將實體和關係表示為複數向量
，每一個複數向量
,然後定義一個打分函數
對於每一個元組，該打分函數計算一個分數來衡量元組成立的可能性，分數越高，成立的可能性也越高。
3.2 實體非負性約束
實體的非負性約束要求實體向量處在一個非負的空間內，具體的，我們要求
非負實體向量僅僅包含正向的語義，可以更高效地編碼信息，比如對於實體“巴黎”，正向語義僅僅需要編碼“巴黎是法國的首都”,而負向語義則需要編碼“巴黎不是中國的首都，巴黎不是美國的首都，巴黎不是俄羅斯的首都…”，事實上會造成信息冗餘。此外，非負向量還能夠導致稀疏性，這可以使得我們學到更加稀疏的表示，從而獲得更有可解釋性的實體向量。
3.3 關係近似蘊含性約束
除了非負性約束，我們考慮關係的近似蘊含性約束，這裡可以記作
，近似蘊含性約束是說對於兩個關係
，前者可以近似蘊含後者。比如表示我們在知道了某人的出生地（born in）, 以大概率能推斷出這個人的國籍（nationality）。每一條近似蘊含都有一個權重
，代表該蘊含成立的置信度，權重越大，代表置信度越大。這種帶置信度的蘊含約束可以通過規則挖掘系統自動地從元組中挖掘出來。
為了建模近似蘊含約束，我們首先建模蘊含約束，在知識圖譜中，我們可以通過如下的方式建模蘊含
該式子的含義是說，對於的任何實體對
，如果
為真並取得較高的打分，則
總是為真並會取得更高的打分。但是這樣的約束並不利於我們求解，因為需要遍歷所有的實體對，所以我們採用次序嵌入的方式將其改寫，則上面公式的一個充分條件就是
這樣，對與每一條蘊含約束，只涉及兩個關係向量的計算，計算量大大減少。
最後，我們考慮建模蘊含的近似性，這裡引入鬆弛變量建模近似性，可以得到最終的近似蘊含約束如下，以上的具體推導細節，可以參考原論文的附錄部分。
3.4 最終模型
結合基本模型，我們的目標函數可以定義如下：
其中，目標函數中第一項是對元組建模，這裡使用了logistic loss,第二項是近似蘊含約束中的實部的約束，是一個hinge loss，直觀的理解是當
，則視為違反約束，大的越多，違反的程度也越大，如果
,則沒有違反約束，不施加任何懲罰。第三項是一個平方項，用於建模近似蘊含約束的虛部約束，迫使兩個虛部相等，相關的推導細節可以參考原論文。最後一項是
正則，用於防止過擬合。
3.5 複雜度分析
帶非負與蘊含的模型的複雜度是
,其中d是維度，sd是原來ComplEx模型用於建模元組的複雜度；td是近似蘊含約束的複雜度，t是近似蘊含約束的個數，該數目遠遠小於知識圖譜中的元組數目，可以近似認為是一個常數，
是非負性約束帶來的複雜度，其中
是一個mini-batch中中平均的實體個數，可以看到，帶簡單約束的模型與基本模型複雜度同階，是一個很高效的算法。
4 實驗
我們的實驗分為兩個部分，第一部分是鏈接預測實驗，這個在之前很多相關工作中都會做，用來測試表示學習的性能，第二部分是針對實體關係向量可解釋性的可視化分析。
4.1 數據集
我們在三個數據集上做了實驗，分別是WN18,FB15K,DB100k。WN18和FB15K是WordNet是Freebase的一個子集，最早在這篇工作中公佈，DB100K是我們在DBPedia中抽取的的一個子集。各數據集的統計數據如下，其中#Ent,#Rel,#Train/Valid/Test,#Cons分別表示實體數，關係數，訓練/驗證/測試集的元組數目以及近似蘊含約束。
蘊含約束通過規則自動抽取軟件AMIE+獲得，在各數據集上（從上到下，依次是WN18,FB15K,DB100k）的規則樣例如下:
4.2 鏈接預測
鏈接預測任務是給定一個缺失頭實體或尾實體的元組，預測出相應的頭尾實體。在評測中，給定測試元組集合，對於其中每一個元組的頭（尾）實體，將其隨機地替換為除了測試元組之外沒有在知識圖譜中出現過的實體，然後計算這些元組的的打分，獲得對應測試元組的排序r。根據這個排序，計算兩個指標，
是平均倒排值,
,其中
，表示正確元組排進前N的比例。
我們選取的比較方法有三類，第一類是基本模型，這類模型只利用元組信息，同時打分函數也是簡單的，
第二類模型是結合了邏輯規則的模型，
第三類模型是近期取得最好結果的一些比較複雜的模型，包含基於深度神經網絡的模型，以及，是利用了大量的負例來提升性能。
從表中我們可以看到，ComplEx-NNE（添加了實體非負性約束的ComplEx模型）以及ComplEx-NNE+AER（添加了實體非負性和關係蘊含性約束的模型）都能夠明顯地提升ComplEx的性能，其中ComplEx-NNE-AER能顯著好於對比方法，這其中包含了基本模型，利用邏輯規則的模型，以及一些複雜的模型，其中包括的基於深度神經網絡的模型。由此可見，這種簡單的約束在保證計算效率的同時，又能夠顯著提升性能。
4.3 可視化分析
接下來，我們對實體和關係的可解釋性做一個可視化的分析。
4.3.1 實體語義分佈熱圖
我們從四個類別（從上到下依此reptile, wine_region, species, programming_language）中分別隨機選取了30個實體，將這些實體向量堆疊起來（橫軸代表維度），然後繪製熱圖，圖中的顏色越深的地方代表值越大，我們可以從圖中看出，帶約束的模型所學到的向量（左邊），相比不帶約束的模型學到的向量（右邊）更加稀疏；同時，左邊圖中，同一類型的實體，也能夠激活一致地相同的維度，說明有關這些類型的語義也集中在了這些維度：
4.3.2 實體語義純淨度曲線
語義純淨度是指對於一個維度，該維度取值較大的實體都應該儘可能的屬於同一類別，我們用熵來衡量語義純淨度，熵越低，語義純淨度越高。圖中繪製了ComplEx，ComplEx-NNE，ComplEx-NNE-AER每個維度的平均語義純淨度，可以看到ComplEx-NNE，ComplEx-NNE-AER具有更高的語義純淨度。
4.3.3 關係可視化分析
我們選取了三組蘊含關係（每一組兩個，處在上方的關係是蘊含式的左部，下方的是蘊含式的右部）分別是等價，逆反，一般蘊含；等價和逆反是一般蘊含的特例，等價要求對於任意兩個實體對
，存在
，而逆反要求
。而對於他們的充分條件，等價要求兩個關係
滿足
,
，逆反要求滿足
,一般蘊含只需滿足
，詳細證明可參見論文附錄。我們可以看到，圖中的關係對均能滿足上面的約束。
閱讀更多 讀芯術 的文章
