1. 前言
實體和關係抽取是信息抽取領域的的重要研究問題。如圖1所示，其輸入是非結構化文本，輸出則是識別出的實體及其對應的語義關係。其中，實體與關係之間、以及關係與關係之間都存在著很強的關聯性。例如，Live_In關係往往對應著 Person 和 Location兩種實體，反之亦然。Live_In關係（對應實體「John」 和實體 「California」） 可以由Live_In關係（對應實體 「John」 和實體 「Los Angeles」） 和 Loc_In關係（對應實體 「Los Angeles「 和實體 「California」）推理出來。
以往的很多工作都是採用串聯的方式來解決這兩個任務，也就是說先識別出實體，然後再在實體識別的基礎上識別出對應的關係，這種方法的一個主要問題就是所謂的錯誤傳播，還有就是其不能很好的利用實體和關係之間的關聯性。所以，目前的一個比較主流的研究思路就是採用聯合抽取的方法。對於聯合抽取方法，一個很重要的點就是如何充分的建模實體和關係以及關係與關係之間緊密的關聯性。
聯合抽取方法可以細分為基於統計的方法和基於神經網絡的方法。基於統計的方法的性能嚴重依賴於複雜的特徵工程，而且很難利用全局的特徵。基於神經網絡的方法則可以自動學習非局部的特徵，在聯合抽取任務上取得了更好的實驗結果。但是，目前大部分的基於神經網絡的方法僅僅是通過參數共享的方式來實現聯合抽取，其導致實體和關係以及關係和關係之間的聯繫不能被很好的利用。（Zheng et al., 2017）是第一種將實體識別和關係抽取兩個任務轉化成一個任務來做的基於神經網絡的方法。其通過設計一個標籤體系，從而將聯合抽取問題轉化成一個序列標註問題。這種序列標註方法的一個主要問題是如果一個實體同時和另外兩個實體有關係，其只能識別出其中的一個關係。還有一個問題是，其並不能顯示的建模實體與關係以及關係與關係之間的聯繫。
基於以上觀察，我們通過設計一套轉化規則，將實體識別和關係抽取聯合任務轉化為一個有向圖的生成問題，並使用基於轉移的方法來直接生成該有向圖。如圖1所示，與傳統的句法任務不同，我們的輸出結構中每個節點可能含有多個或零個父節點。因此，我們提出了一種新的轉移系統，通過遞增的融合實體信息及其相應的關係信息，我們的方法不僅可以對實體和關係之間的關聯性進行建模，而且還可以很好的表示關係之間的關聯性。
圖1 實體和關係抽取（綠色表示實體弧，藍色表示關係弧）
這項工作的主要貢獻總結如下：
我們通過設計一套轉化規則，將實體識別和關係抽取聯合任務轉化為一個有向圖的生成問題，
基於有向圖的特點, 我們設計了一套轉移系統來生成該有向圖。另外，為了更好的建模關係和關係之間的依賴性，我們設計了一個特殊的遞歸神經網絡。
2. 模型介紹2.1 轉化策略在我們定義的有向圖中，圖中的節點對應於輸入句子中的單詞。 有向弧分為兩類：
表示實體內部結構的實體弧;
表示實體之間關係的關係弧，其中父節點表示關係對應的第一個實體，子節點表示關係對應的第二個實體。
為了處理一個實體有多種關係的情況，有向圖中的每個節點可以有多個父節點，這與傳統的依存句法樹等句法任務有所區別。如圖1所示，其中輸入句子包含：1）三個實體，它們被轉換成具有實體標籤的相應的綠色有向弧；和2）三個關係，它們被轉換成具有關係標籤的相應的藍色有向弧。另外，與最終結果無關的其他詞語沒有相應的弧線。
2.2 轉移系統為了生成該有向圖，我們採用了一種基於轉移的方法，這個方法主要受arc-eager算法（Choi and McCallum, 2013）的啟發。我們主要設計了兩類轉移動作：1）實體生成動作，用於生成實體弧; 2）關係生成動作，用於生成對應的關係弧。
在狀態表示上，我們使用元組(σ,δ,e,β,R, E)來表示每個時刻的狀態，其中σ是一個保存已生成實體的棧，δ是一個保存被從σ臨時彈出，但是之後會被重新壓入σ的實體的棧，e是用來存儲正在被處理的部分實體塊，β是一個包含未處理詞的緩衝區。R用來保存已經生成的關係弧。E用來保存已經生成的實體弧。我們使用索引分別表示單詞和實體。A用於存儲操作歷史記錄。
表1 轉移過程（∗表示一個實體）
表1給出了具體的動作集合定義。前七個動作用於生成關係弧，最後三個動作用於生成實體弧。其中，動作添加一個從到的標籤為的關係弧，並將從σ中彈出。動作在到之間添加一個帶標籤的關係弧，並將δ和中的所有實體壓入σ。NO-SHIFT 動作將δ和中的所有實體壓入σ。NO-REDUCE 動作從σ中彈出ei。動作從到之間添加一個帶標籤的關係弧，並將移動到δ的前端。動作從到添加一個標籤的關係弧，並將移動到δ的前端。NO-PASS 動作只是將移動到δ的前端。表示從到的標籤為到關係弧。和表明分別是的父節點和祖先節點。另外，當β的頂部元素是單詞時，所有關係動作都將被禁止。O-DELETE從β中彈出wj。GEN-SHIFT將wj從β移動到e。GEN-NER(y) 彈出e頂部的所有元素，創建一個「塊」，用標籤y標記這個塊，將這個塊的表示壓入β中，生成的實體被添加到E。當β的頂部元素是實體時，所有實體動作都將被禁止。另外，如表 2所示，每個動作都需要滿足一定的先決條件，以確保生成的實體和關係有向圖的合理性。
表2 轉移操作的先決條件
表 3顯示了圖1中的輸入句子所對應的動作執行序列。初始狀態是([ ],[ ],[ ],[1,…,n],∅,∅),，而終止狀態是(σ,δ,[ ],[ ],R,E)。
表3 圖1中的實體和關係圖的轉換序列
2.3 搜索算法基於上述轉換系統，我們的解碼器為每個給定句子預測其最佳動作序列。系統初始化時，把輸入句子以相反的順序壓入β中，這樣第一個單詞就在β的頂部。σ，δ，e和A每個都包含一個空棧標記。在每一步預測中，系統通過計算模型狀態的表示（由β，σ，δ，e和A決定）來預測要執行的動作。無論其他狀態如何，當β和e都為空（空棧符號除外）時，解碼完成。
圖2 表3中模型狀態6地表示
（h（*）表示每個令牌的Bi-LSTM表示，e（*）表示實體及其關係的組成）
如圖2所示，t 時刻的模型狀態mt 被定義為：
其中W是要學習的參數矩陣，st是σ的表示形式，bt是β的表示形式，pt是δ的表示形式，et是e的表示形式，at是A的表示形式，d是一個偏置項。
模型狀態mt用於計算t時刻選取動作的概率：
其中gz表示轉換動作z的列向量，qz是動作z對應的偏置項。集合A(S, B)表示在當前狀態下可以採取的合理操作的集合。給定輸入句子，任何合理的動作序列z的概率可以表示為：
後我們可以得到
因此，實體識別和關係抽取聯合任務就被集成到我們的轉移系統中。在測試的時候，我們的算法貪心的選擇最大概率的動作，直到滿足終止狀態條件。
3. 實驗我們使用公開數據集 NYT 作為我們的數據集。我們採用標準的Precision（Prec），Recall（Rec）和F1-score來評估模型性能。跟（Zheng et al., 2017）一致，計算最終F1-score時，不考慮實體類型的標籤。也就是說，當關係類型及其對應的兩個實體的邊界都正確時，該關係被認為是正確的。跟（Zheng et al., 2017）一樣，我們從測試集中隨機抽樣10%作為開發集，並將其餘數據用作測試集。
表4 在NYT上與以前最先進的方法進行比較
（第一部分（從第1行到第3行）是管道方法，第2部分（第4行到第6行）是聯合提取方法，第3部分（第7行到第9行）是端到端方法。）
我們將我們的方法跟之前的串聯方法，聯合方法等進行對比。結果如表4所示，我們的基於圖的方法獲得了最高的F1-score，另外，模型的準確率也是最高的。為了驗證各個模塊的性能，我們做了消融實驗。結果如表5所示,我們發現在初始化β時候採用的雙向lstm表示，以及針對關係之間的聯繫而設計的遞歸遞歸神經網絡對性能提升有很重要的影響。更多具體的實驗分析可以參考我們的英文原文。
表5 NYT上的消融測試
4. 結論針對實體識別和信息抽取聯合任務，我們通過設計一套轉化規則，將實體識別和關係抽取聯合任務轉化為一個有向圖的生成問題。基於有向圖的特點, 我們設計了一套轉移系統來生成該有向圖。我們的方法能夠很好的表示和利用實體和關係以及關係與關係之間的關聯性，在NYT數據上取得了不錯的結果。
本期責任編輯： 趙森棟
本期編輯： 賴勇魁
「哈工大SCIR」公眾號
主編：車萬翔
副主編： 張偉男，丁效
責任編輯： 張偉男，丁效，趙森棟，劉一佳
編輯： 李家琦，趙得志，趙懷鵬，吳洋，劉元興，蔡碧波，孫卓，賴勇魁
長按下圖並點擊 「識別圖中二維碼」，即可關注哈爾濱工業大學社會計算與信息檢索研究中心微信公共號：」哈工大SCIR」 。