高效的關係補全——EMNLP2015 SFE論文研讀

05-09

近期做了一些關於知識推理的工作，主要是進行實體關係補全。目前採用了EMNLP2015這篇paper的實現。論文為Efficient and Expressive Knowledge Base Completion Using Subgraph Feature Extraction. Matt Gardner and Tom Mitchell. EMNLP 2015. (下載點此website)

主要思路

傳統的pra第一步是找到通路，即節點間是否存在路徑，然後再開始隨機遊走計算。

EMNLP2015這篇paper認為第二步計算量大，且在之前的工作中表明，隨機遊走的概率並沒卵用，因此僅僅採用了二值特徵。

作者開源了其實現，代碼在matt-gardner/pra。

Subgraph Feature Extraction

假設有其是節點source和target，先單獨提取能代表source和target的子圖特徵。具體方法為，找尋以source為起點的n步以內的指定類型的到達節點i（中間節點）的路徑。如此將source和target的都找到後，合併其在中間節點i的路徑作為特徵（合併時，target的路徑需要反轉）。這其中如果source或target節點找的路徑經過對方，就直接選取。

有多類方式豐富特徵：

PRA-style features.上面的合併特徵
針對1的Bigram類型的特徵
One side features，即不像PRA那樣必須由source走到target。可以直接將source或target的子圖路徑作為特徵。思想是，假如想要預測一個城市是否是首都，那麼可能根據所有首都城市都擁有較多的運動隊即可標識。
one side features comparisons，具體是指將source和target遊走的子圖中具備相同類型的邊的類型作為特徵。比如奧巴馬娶了米歇爾，那麼「性別」可作為單獨的一條邊抽出來。
Vector space similarity features，向量空間，將邊的類型用向量來表示，應該是邊的embedding。看了下源碼，貌似更low，需要自己指定哪些關係是近似的關係。
Any-Relation features. 是5的更弱的實現，直接認為所有關係是可以近似替換的，那麼一些邊可以用ANYREL來標識，表示任何類型的邊都滿足條件。

源碼還提供了更多的特徵提取方式，未注釋，尚未深究。

負樣本構造

傳統方式：採用PRA未在知識庫中見到的樣例作為負樣本。

作者提出了採用personalized page rank的方式構造，思想是根據source和target的同類型節點計算得到的PPR得分抽樣選取構造。

這倆種方式作者對比了下，發現差距不明顯，只是自己選了PPR這種方式。

特徵描述解釋性

模型最後抽取的路徑特徵解釋。

詳見<Understand features observations · Issue #14 · matt-gardner/pra>

一些類似ANYREL之類標識的可參照論文。

我的工作

因為工作需要，需要復用該演算法。然而原開源僅是為了訓練和測試，所以較難直接使用（原code 訓練和預測是同時進行的，沒有剝離開來）。這裡自己重構了一些模塊，使得每次只需要載入上次訓練的目錄設置，和本次需要預測的環境目錄，即可進行預測輸出。

目前僅對nodepair類型的instance以及模型為LR做了更改，因此只能採用有限方式進行運行。代碼放在sloth2012/pra。預測運行代碼見https://github.com/sloth2012/pra/blob/master/src/test/scala/edu/cmu/ml/rtw/pra/models/PredictWithTrainedModelSpec.scala，主要是需要設置上個訓練模型的experiment_spec上級目錄，以及當前需要預測的數據的experiment_spec上級目錄。