知識圖譜的皇冠：知識圖譜推理的前世今生
作者資訊：費斌傑，熵簡科技創始人兼CEO，長期深耕金融資管數據科技一線，對數據中台、知識圖譜的技術實踐和產業應用有深入理解，曾就職於嘉實基金，畢業於清華大學五道口金融學院、清華大學工業工程系。
導讀：業界和學界對知識圖譜的關注主要集中於兩大領域，分別是知識圖譜的構建和知識圖譜的應用。
前者聚焦於通過對結構化、非結構化數據的整合，實現統一形式的數據存儲；後者則著眼於通過演算法對海量知識圖譜數據進行學習與挖掘，從而推理出新的知識，服務於具體行業應用。知識圖譜推理在其中發揮了重要作用，被譽為知識圖譜領域的皇冠。
本文聚焦於知識推理的理論研究和產業實踐，剖析知識圖譜推理的前世今生以及最近研究進展，以饗讀者。
一、演繹推理與歸納推理
推理，是運用已知的知識來得出未知的知識的過程。按推理方式的不同，可以分為兩大類別，分別是演繹推理（Deductive Reasoning）、歸納推理（Abductive Reasoning）。
演繹推理指的是根據嚴格的邏輯關係，從給定的假設下，得出必然成立的結論。最常見的演繹推理形式有20多種，這裡舉例說明：
-
肯定前件論：如果今天是周末，那麼我們不上班；今天是周六，所以推理得出我們不上班
-
否定後件論：如果今天是周末，那麼我們不上班；今天我來上班了，所以推理得出今天不是周末
-
三段論：如果今天是周末，那麼我們不上班；如果我們不上班，那麼早上可以睡懶覺；所以推斷出如果今天是周末，我們早上就可以睡懶覺
-
二難論：如果是周六，那麼我打球；如果是周日，那麼我看書；假設我不知道今天具體是周幾，但是我知道今天肯定是周末，要麼是周六要麼是周日，那麼可以推斷出今天我要麼打球要麼看書
-
德摩根定律：p與q取否等價於非p或非q；p或q取否定等價於非p與非q
除此之外，還有換位率、排中律、吸收率等等。
圖：常見演繹推理形式列舉
與此相對，歸納推理是指基於已有的部分觀察結果，從而推斷出一般化結論的過程。歸納推理不能確保推理結果的完全準確，而演繹推理可以。
歸納推理有四種推理方向：
-
泛化歸納：把對個體的觀察得出的結論推廣到整體
-
簡單歸納：把對整體的統計結論應用於個體
-
溯因歸納：根據觀察的結果和現有知識來推斷最有可能的原因
-
類比歸納：根據對一個樣本的觀察來預測另一個相似樣本的結果
歸納推理的集大成者就是著名的貝葉斯推理，其核心思想是：不只通過觀察最新一次的實驗結果來定概率，而是把這作為一次證據（似然概率），來修正歷史的先驗概率，從而得出一個新的後驗概率，如此往複，不斷逼近真實概率。
常見的演繹推理方法有基於描述邏輯的推理、和基於邏輯編程的推理。常見的歸納推理方法有基於圖結構的推理、基於規則學習的推理、基於表示學習的推理。下面我們分別展開討論。
二、基於描述邏輯的推理
描述邏輯（Description Logic），簡稱DL，是一種用於知識表示的邏輯語言，和知識推理的形式化工具。
一個DL系統包含四個組成部分，分別是描述語言、Tbox、Abox、以及基於Tbox和Abox上的推理機制。其中Tbox（Terminology Box）是關於概念和關係的斷言，Abox（Assertion Box）是關於個體實例的斷言。
圖：描述邏輯組成架構
通過Tbox和Abox，我們可以把知識庫中複雜的實體關係推理問題轉化為一致性的校驗問題，從而簡化推理實現過程。
舉個例子，「蘋果 ∩ 綠色 = 酸澀」這屬於概念斷言，放在Tbox中；「我手裡現在有10隻蘋果，其中3隻是綠色的「，這屬於實體斷言，放在Abox中。基於Tbox和Abox，我們可以推理出我手中的蘋果里有3隻是酸澀的，7隻是甘甜的，這屬於推理系統。
基於描述邏輯的推理體系中，常見的是基於表運算（Tableaux）的推理，經常被用於檢測描述邏輯知識庫的一致性。
Tableaux演算法的核心思想是如果我要證明一個推理是正確的，那我只要列出所有可能存在反例，並且一一駁斥就好了，即只要不存在反例那麼推理就是正確的，所謂歸結反駁。
Tableaux其實就是一棵公式樹，它會根據前提（Premises）和否定結論（Negated Conclusion）來不斷迭代創建新的分支，對公式進行逐級分解，當所有分支都關閉後，Tableaux演算法就會被終止。
圖：Tableaux演算法示意
目前已經有不少公開的基於表計算的推理系統，如曼徹斯特大學研發的FaCT++、美國Franz公司研發的Racer、馬里蘭大學研發的Pellet、牛津大學研發的HermiT，其中HermiT實現了Hypertableaux的超表運算技術，進一步提高了Tableaux演算法的運算效率。
三、基於邏輯編程的推理
基於邏輯編程的推理方法的主要載體是Datalog語言。Datalog發源於Prolog語言，後者是一門非常與眾不同的程式語言，它不是用來開發軟體的，而是專門用來解決邏輯問題的。
Prolog的全稱是Programming of Logic，就是邏輯編程的含義。只需要我們給出規則和事實，它就會自動分析其中的邏輯關係，並且允許用戶通過查詢的方式來完成複雜的邏輯運算。Prolog語言在早期人工智慧研究中有著非常廣泛的應用，主要用於專家系統的構建。
Datalog是一種基於Prolog並且適應於知識庫的改進型語言，是一種受限的Prolog語言，可以看做是Prolog語言的一個子集，它的好處是能夠方便的與大型資料庫進行交互，是一種完全的聲明式語言，便於撰寫規則和實現推理。
目前最常用的Datalog工具包括德國吉森大學研發的DLV（Datalog with Disjunction）、由波茨坦大學研發的Clingo、由牛津大學研發的RDFox等。
四、基於圖結構的推理
基於圖結構推理的典型演算法是PRA（Path Ranking Algorithm），它利用了實體與實體之間的路徑作為特徵，從而對鏈接路徑進行統計推理。
PRA演算法的原理比較明了，假設一張圖譜中有三類實體：員工實體、公司實體、行業實體。假設小明是熵簡科技的員工，熵簡科技是金融科技領域的公司，那麼小明是金融科技領域的從業者。同事小紅是啟明星辰的員工，啟明星辰是資訊安全領域的公司，那麼小紅是資訊安全領域的從業者。
通過統計可以發現，「供職於」、「是某某領域的公司」這兩種關係組成的路徑與「是某某領域的從業者」在圖譜中經常出現，而且與員工實體、公司實體、行業實體具體是誰沒有關係，因此能夠得出一種重要的推理關係。
看似這是一個非常簡單的直覺化的結論，但是常識恰恰是機器所不具備的能力。PRA演算法能夠通過對海量知識的學習，讓機器從統計意義上掌握常識，從而進行有效的知識推理。
五、基於規則學習的推理
基於規則學習推理的代表演算法是AMIE演算法，其強調通過自動化的規則學習方法，快速有效的從大規模知識圖譜中學習出置信度較高的規則，並且應用於推理任務。
這裡的重點在於如何對機器學習出的規則進行有效性評估，有三類方法，分別是支援度評估、置信度評估、規則頭覆蓋度評估，這裡以支援度為例進行說明。一個規則的支援度等於在整個知識圖譜中滿足規則主體和規則頭的實例總個數。一個規則的支援度越高，說明在該知識圖譜中存在很多符合這條規則的實例，因此從統計意義上來看，這更可能是一條準確的規則。
AMIE演算法的全稱是基於不完備知識庫的關聯規則挖掘演算法（Association Rule Mining under Incomplete Evidence）。由於在大規模知識圖譜中對所有可能的規則進行遍歷及評估是不可行的方法，因此如何對空間進行有效的搜索成為了規則學習任務中的重中之重。
AMIE演算法通過不斷向規則中添加三類挖掘運算元（Mining Operators）的方法來拓展規則主體部分，保留支援度高於閾值的候選閉式規則，這三類挖掘運算元分別是懸掛邊、實例邊、閉合邊。
· 懸掛邊指的是邊的一端是一個未出現過的變數、另一端是在規則中已出現過的變數或變數；
· 實例邊指的是邊的一端是規則中已經出現過的元素，另一端是一個實例化的實體；
· 閉合邊指的是連接兩個已經存在於規則中的元素，一旦完成閉合邊的添加，規則的構建就算是完成了。
六、基於表示學習的推理
基於圖結構的推理和基於規則學習的推理都對推理所需的特徵進行了顯示定義，而基於表示學習的推理則通過將符號表示映射到向量空間進行數值表示，利用演算法在學習知識表示的過程中自動捕捉知識推理所需的特徵。
基於表示學習的推理受到NLP領域中關於詞向量研究的啟發，例如大家熟知的vec(King) – vec(Queen) = vec(man) – vec(woman)，人們發現詞向量具有空間平移性的特徵。基於此，人們提出了基於表示學習的推理演算法，主要有TransE、TransH、TransR、TransD等演算法。這類方法的特點在於能夠有效減少維度災難問題，同時可以捕捉實體和關係之間的隱性關聯，計算效率較高。
TransE是這一系列演算法的鼻祖，全稱是Translating Embeddings for Modeling Multi-relational Data。其核心思想在於使得Head向量和Relation向量的和能夠儘可能靠近Tail向量。
實踐表明TransE是一種簡單高效的知識圖譜表示學習方法，能夠自動且較好的捕捉推理特徵，無需人工設計，非常適合於大規模複雜的知識圖譜推理任務。
然而Trans也存在瓶頸，按關係頭尾實體個數比例劃分，知識圖譜中的關係可以分為四類：1對1、1對N、N對1、N對N。TransE能夠有效捕捉1對1的關係，但對於另外三類情況則無法有效識別。
基於此，人們進一步提出了TransH演算法，全稱是Knowledge Graph Embedding by Translating on Hyperplanes。其核心思想是將關係解釋為超平面上的轉換操作，每個關係都表示為兩個向量，分別是超平面上的範數向量和超平面上的平移向量。
如果說TransH通過引入超平面有效提升了TransE表達非1對1關係的能力，那麼TransR則是通過拆分實體向量表示空間和關係向量表示空間的方式來提升TransE的表示能力。
例如（中國，包含，上海市），這裡的關係是包含；（小明，是朋友，小紅）的關係是朋友，這兩種關係截然不同，把它們放在同一個向量空間中進行表示是不合理的。
為了解決這個問題，TransR演算法在兩個不同的空間，即實體空間和多個關係空間中對實體和關係進行建模，並在對應的關係空間中進行轉換。
TransR有效增強了表示學習的表達能力，但它也有不足之處，其中最明顯的問題在於TransR為每個關係引入了一個映射矩陣，使得其參數數量遠大於TransE和TransH，因此難以應用於大規模知識圖譜。
為解決這個問題，人們進一步提出了TransD演算法。TransD的核心思想在於用一個實體相關的向量與一個關係相關的向量的外積來動態的求解出映射矩陣。通過動態計算映射矩陣，TransD不僅可以顯著降低參數數量，而且增強了全局捕捉能力。
反過來看，TransE模型是TransR模型中的一個特例，當關係和實體的向量表示維度相等，且所有投影向量都設置為0時，TransR就退化為TransE。
七、結語
知識推理是一門古老的學科，從亞里士多德在《前分析篇》中闡述的經典三段論開始（亞里士多德是人；人都會死；所以亞里士多德會死），人們就對知識推理進行了理論探索與實踐。
隨著近年來技術的飛速發展，越來越多的知識圖譜自動化構建方法被學界和業界提了出來，比如通過演算法對海量文本進行三元組提取，使得大規模知識圖譜的構建成為了可能。但這類知識圖譜的資訊準確度和冗餘度都稍遜於通過專家知識進行人工搭建的知識圖譜。
在這種自動化構建的大規模知識圖譜上進行知識推理時，知識的不精確性以及巨大的數據規模對於演繹推理來說是巨大的挑戰，而歸納推理則可以發揮更大的價值。
近年來，知識圖譜領域學術界和產業界的互動越發緊密，隨著開源工具Jena、JBoss的推出與普及，知識圖譜推理將對現代企業知識圖譜應用起到愈發重要的作用。
