一種改進的實體關系抽取算法
——OptMultiR

延浩然，靳小龍，賈巖濤，程學旗

(1. 中國科學院 計算技術研究所 網絡數據科學與技術重點實驗室，北京 100190; 2. 中國科學院大學 計算機與控制學院，北京 100049)

0 引言

近年來，互聯網技術和應用模式的快速發展在改變人們生活方式的同時也產生了巨大的數據資源[1]。如何從網絡大數據中獲得有價值的知識，并對其進行深入的計算和分析，已成為國內外工業界和學術界研究的熱點。在此背景下，知識圖譜這一概念于2012年5月17日被Google正式提出，其初衷是為了提高搜索引擎的能力，增強用戶的搜索質量以及搜索體驗[2]。目前，隨著智能信息服務應用的不斷發展，知識圖譜已被廣泛應用于智能搜索、智能問答、個性化推薦等領域。其中關系抽取(relation extraction)與實體抽取等技術作為知識圖譜的構建技術，受到了越來越廣泛的關注。

以往的關系抽取算法大多使用全監督學習來實現，雖然全監督學習可以達到極高的準確率和召回率，其缺點也顯而易見： 對于每一條訓練數據，都需要事先進行人工標記。受限于此，全監督的學習方式很難應用到互聯網產生的海量文本中[3]。在此背景下，遠程監督(distant supervision)，也被稱為弱監督(weak supervision)，成為了一種更為高效的學習方式。通過與已有知識庫(如Freebase，Wikipedia等)的鏈接，遠程監督模型會自動尋找知識庫中存在的實體，并將原有文本轉換為以實體對(entity pair)為基本單位的訓練樣本，然后參考知識庫中實體對之間已經存在的關系進行啟發式的抽取。由于省去了人工標注這一費時費力的過程并具有較高的遷移性，能夠啟發式地處理語料文本的遠程監督，目前已經成為了較受歡迎的關系抽取方法。

遠程監督這一概念最早于1999年被Craven和Kumlien提出[4]，當時他們的研究目標是使用酵母蛋白質數據庫作為知識庫，抽取蛋白質與細胞、疾病和藥物之間的二元關系。近年來，遠程監督受到了廣泛的研究和使用。2009年Mintz等人使用Freebase和Wikipedia中的文本作為知識庫，創建了一種新的遠程監督學習框架[5]。他們的假設是： 所有符合一對指定實體對的句子，都表達了這一實體對在知識庫中的對應關系(而這個關系是唯一的)。2010年Riedel等人認為這一假設過于嚴格，他們將其改進為“對于特定實體對的所有句子中，至少有一句表達了知識庫中的對應關系”[6]。把其中每一個句子看作是一個實例，每一個關系的抽取看作是一個標記，以上的學習方式都屬于多實例單標記的遠程監督關系抽取，即每個實體有且只具有一種關系。這顯然是與客觀事實相違背的，例如，“姚明曾是CBA籃球隊上海大鯊魚隊的前任隊員”和“姚明現在是大鯊魚隊的老板”兩句話中，“姚明”和“上海大鯊魚隊”就存在這兩種關系。在此背景下Hoffmann等人于2011年提出了一種多實例多標記算法—MultiR[7]，該模型使用Freebase作為知識庫，紐約時報中的內容作為訓練文本。MultiR假定一對實體對中可以存在多個關系，每一個關于該實體對的提及(一個句子)都有可能表達任意關系，并建立了概率圖模型進行求解。在此以后的遠程監督抽取大多都基于多實例多標記學習這一假設作為基本模型進行求解[8-10]。

然而，MultiR算法還存在著兩個主要的問題。首先在抽取打分的過程中，算法沒有利用待抽取的關系與實體對在知識庫中的已知關系之間存在的聯系，從而導致一些出現次數少的文本特征對抽取結果產生了噪聲干擾，使得算法抽取出的是實體對根本不可能存在某種關系。其次，在概率圖匹配的計算過程中，MultiR使用的貪心算法會受到枚舉順序的影響，且該方法只能求得較優解，無法達到全局最優。

本文針對上述問題，對MultiR算法主要進行了兩點改進：

(1) 考慮到特定實體對存在的關系之間具有一定的聯系，本文提出了關系權重矩陣模型，在模型進行抽取打分的過程中加入關系間的權重影響，通過權重向量去降低個別文本特征帶來的噪聲干擾。使得新的算法不再會抽取出實體對不可能存在的關系。

(2) 針對概率圖匹配中存在的問題，本文采用了基于狀態壓縮的動態規劃算法來代替原有的貪心算法進行求解，新算法可以求得原概率圖匹配問題的最優解，且后續的實驗也證明了該算法在實驗復雜度上的增加僅為常數級。

1 MultiR模型

本節將對MultiR模型及其存在的問題進行簡要闡述。

1.1 模型概述

基于多實例多標記抽取模型的思想，MultiR使用了條件概率模型來定義以上所有待抽取的隨機變量的聯合分布，其抽取模型平面圖如圖1所示。

圖1 MultiR模型示意圖

本質上來說，它訓練了一個從文本特征到關系的參數矩陣。在每一次訓練迭代中，通過對每一個實體對(e1,e2)中的每個句子(提取成文本特征向量)xi抽取出一個隱含變量zi=r∈{r∪None}，代表這個句子表達的關系，通過對所有的zi進行去重統計，得到一個布爾型數組Y′，其中Y′r表示關系r是否被實體對(e1,e2)表達。通過對關系庫中該實體對已知的關系集合Y的對比，MultiR在每一次迭代中對該句子中的文本特征參數進行梯度修正，直至模型收斂。

具體算法實現如下：

initializeparameter verctor Θ←0

fort=1...Tdo

fori=1...ndo

(y′,z′)←arg maxy,zp(y,z|xi;θ)

ify′≠yithen

z*←arg maxzp(z|xi,yi;θ)

Θ←Θ+φ(xi,z*)-φ(xi,z′)

endif

endfor

endfor

ReturnΘ

對算法的進一步解釋：

最外層循環T表示了迭代次數。內層循環變量i枚舉了每一個實體對(e1,e2)，首先計算使用維特比估計的z和y，此處的抽取不使用知識庫中的關系作為先驗知識而全靠特征和關系之間的參數θ進行抽取，將此次的抽取結果z′通過去重轉換為關系向量y′，并與知識庫中該實體對已知存在的關系向量yi進行對比，如果存在偏差就去計算第二種假設以進行修正。在第二種假設的計算中，yi將作為先驗知識，求得的抽取結果記為z*。在本次迭代的最后，模型對θ進行更新，對于z*和z′中存在差異的句子，模型會更新該句子對應的特征向量，使其向z*抽取的關系靠近，并且遠離z′抽取的關系。

1.2 模型存在的問題

1.2.1 抽取過程中產生的噪音

上文中提到，MultiR模型本身只考慮文本特征到關系的映射，并沒有考慮實體對本身或者關系庫本身帶有的額外信息，這是對已知資源的一種浪費。此外，一些出現次數極少的文本特征會對抽取的結果產生比較嚴重的噪聲影響。如果某個文本特征在整個訓練集中僅出現過一次，那么它會被賦予一個特定的關系極大的權重，以至于以后該特征出現的句子會被以極大的概率抽取為這個特點關系。

另外，本文對測試集上抽取錯誤的句子進行了人工分析。通過對這些錯誤抽取的結果進行分析，可以得出如下結論： 有一定數量的句子被抽取出了該實體對幾乎不可能存在的某種關系。例如，“中國政府將向南蘇丹提供500萬美元緊急援助”這個句子中由于存在“美元”“援助”等詞匯，容易被抽取成某個子公司關系或者其他商業性的上下級關系，但實際上“中國”和“南蘇丹”作為兩個國家，不會存在這樣的關系。

1.2.2 條件推論計算問題

條件推論的計算p(z|yi,xi;θ)要求在已知條件下，每一個先驗關系yij都必須被xi中的某個句子抽取到。為了計算該抽取結果，MultiR構建了一個概率圖模型，以尋找最符合yi的z的分布，這個問題也就被轉換為了不同權重下圖的邊覆蓋問題。

圖2 條件推論匹配問題示例圖

在求解該問題上，MultiR模型使用了一種求近似解的貪心算法，其策略如下： 首先枚舉νyr∈νy，對于該關系點，選取未被其他關系點中與它邊權最大的句子點，并將其標記為選取狀態。在所有的關系點都有句子點對應后，對于還未選取的句子點，模型選擇邊權最大的關系點作為它的抽取結果。原模型貪心匹配策略計算的時間復雜度是o(|r||s|)，其中|r|是該數據包在關系庫中的關系數量，|S|是數據包在訓練數據中的句子數。

在原模型中，該貪心算法取得了一定效果。但本文認為該方式存在比較明顯的問題。首先，求解的匹配值僅僅是較優解，而非最優解；其次，這樣的求解方式嚴重受枚舉順序的影響，如果更改枚舉點的順序，有極大的概率會導致完全不同的匹配結果。因此本文認為這樣的求解方式還存在著比較大的改進空間。

2 改進模型OptMultiR

2.1 關系權重矩陣

針對1.2.1節中提到的問題，本文認為在遠程監督中知識庫本身就是一個豐富的高可信度的基礎數據來源。舉例來說，當A分別與B和C之間存在某種親屬關系時，B和C之間也更可能被抽取出親屬關系，而非同事關系。因此我們可以在模型訓練開始之前利用實體對在知識庫中已有的關系預先生成一個權重矩陣，當對某個實體對的某個句子進行關系抽取的時候，使其更傾向于抽取出其在知識庫中存在的關系，或是與這些關系近似度比較大的關系。

2.1.1 相關定義

下面對權重矩陣W|R|*|R|進行定義，第i行表示了關系i與其他關系的權重向量，其中

(1)

表示了關系i和關系j之間的相關性(權重)，數值越大相關性越強。其中決定關系Ri與Rj關系權重的是在訓練數據中同時擁有它們兩個的實體對Et的數量。這里模型引入了一個超參數δ∈[0..1)，δ值越大，模型就認為關系之間的相關性越強(抽取的新關系越往已知關系上靠攏)，δ越小表示模型越不重視關系之間的相關性(在抽取的時候也就可以更傾向于打分的結果，有更大的概率抽取出新關系)。

當對某個實體對(e1,e2)的某個句子s進行關系抽取的時候，首先像原模型一樣通過維特比算法對每個關系進行打分，獲得一個長度為|R|的打分向量Score。然后找到(e1,e2)在知識庫中存在的關系集合Y，計算權重向量Weight，其中

(2)

最后句子s抽取出的關系r的編號sr的計算如式(3)所示。

sr=argimax(Weighti*Scoreii∈|R|)

(3)

2.1.2 對NA關系的特殊處理

現在重新考慮關系權重矩陣模型。在該模型下，所有的關系大致可以被分為三類： ①非獨立關系。這個集合下的關系或多或少都曾與該集合中的其他關系在一個或多個實體對中共同出現過，在某個句子的抽取過程中，它們會有較大的概率獲得更大的權重Weight，也就更容易被抽取出來，因此它們是關系權重矩陣中的“獲益者”。②獨立關系。這個集合中的關系從未與其他關系共同出現過，它們所出現的實體對在知識庫中的關系集合只有一個元素——它們自己，因此這些關系的權重永遠為1(歸一化前)。③NA關系。NA關系并不會與任何關系共現，它是絕對孤立的一種關系。嚴格意義上來說，NA表示的不是一個關系，而是一個實體對真實存在的關系集合減去知識庫中存在集合的子集。

基于上述情況，不難發現獨立關系集合中的關系和NA會被判定為同等權重大小(值均為1)。然而知識庫是不完備的，在現實情況下這些關系可能確實與其他關系共現過卻并未被知識庫記錄，在此情況下模型依舊賦予了其與NA相同的權重，等同于降低了該關系被抽取出的概率，變相提高了NA關系被抽取出的概率，從而使得模型的召回率降低。

因此本文進行如下修改： 針對NA關系的Weight，將其乘以一個新的超參數α∈[0..1]以平衡知識庫的不完備性帶來的影響。從實驗表現來看，該假設非常具有實際意義。

2.2 基于狀態壓縮的動態規劃算法

為解決1.2.2節中提出的條件推論求解過程中存在的缺陷，本文使用基于狀態壓縮的動態規劃算法來求解，以較小的時間代價求得該問題的最優解。

設x是一個自然數，它表示了所有的關系被選與否的狀態，其中x的二進制表達如下： 第i-1位表示了第i個關系是否被選取，1表示已經被選了，0表示沒有被選。設總關系數一共有m個，則x的取值范圍是[0..2m-1]，0為初始狀態，表示沒有關系被選擇，2m-1是算法要達到的最終狀態，表示所有關系都已經被選擇。對于第i個關系來說，它只能從滿足x&2i-1=0的x去轉移(“&”表示位運算“與”操作)，代表著x的第i-1位還是0，也就是說在這個x下第i個關系還沒有被選擇。

下面給出動態規劃轉移方程： 設f(x,y)表示x狀態下選擇到第y個句子，整個模型獲得最大權重，轉移方程如式(4)所示。

(4)

轉移方程含義： 在x狀態下僅考慮是否要把第y個句子匹配給第k個關系，如果匹配，總權重就要加上它們兩者之間的邊權。當然，這里轉移的一個重要條件是x&2k-1=0，表示x狀態下k關系還沒有與句子點匹配過。如果不去匹配，那么加入與第y個句子點權重最大的邊權即可。

有一種特殊情況是句子點的個數小于關系點，這種情況下顯然無論如何難以滿足上述的匹配條件。對于該情況，本文依舊使用枚舉句子點，為每個句子點找到一個還未被匹配過的邊權最大的關系點的貪心算法。事實上，出現這種情況的數據集并不多，對總體的影響不大。

新的匹配算法匹配一個實體對的時間復雜度是O(2|R-1||R||S|)，乍看起來相比于原模型的復雜度O(|R||S|)來說增加了一個指數級參數2|R-1|。實際上通過對數據的觀察發現，對于一個實體對來說，其知識庫中可能擁有的關系一般在1到2個，最多不會超過5個，而句子數受訓練文本規模的影響可能是成千上萬條。因此2|R-1|可以被認為是一個小于等于30的常數，其大小只受選取知識庫內容的影響，而當訓練數據足夠大的時候|S|會隨之線性增長，相比起來2|R-1|的影響因素可以說是微不足道了。表1記錄了不同數據量規模下兩種算法模型訓練過程的耗時對比。

表1 訓練耗時對比表

續表

綜合來看，使用狀態壓縮的動態規劃算法去計算條件推論，時間上并未有太大增加，求解值卻能從近似解優化到最優解，因此可以被認為是比較有效的優化。

3 實驗

為比較本文改進的OptMultiR模型相對MultiR模型的性能提升程度，本文采用與驗證MultiR相同的實驗數據。這個數據集最初由Riedel等人在文獻[6]中生成。其中訓練語料選取的是紐約《時代周刊》自1987年1月1日至2007年6月19日的約18萬篇新聞。觀察發現，這些新聞中的實體和關系與Freebase知識庫契合度較高，因此選用該知識庫進行遠程監督可以取得較好的效果。

關于評價指標，本文采用了聚集抽取和句子級抽取兩種不同的評價體系。

3.1 參數選擇

在我們的模型OptMultiR中，存在兩個超參數，一個是關系權重矩陣中的影響因子δ，另一個是對NA關系賦予的α。首先本文進行相關實驗分析其性質，并根據相關評價指標確定最優的參數取值。

通過比較幾組不同參數組合的PR曲線，本文發現僅比較曲線的最大準確率、召回率或F1值都是不夠精確的。在某些參數組合下，整個模型的置信度體系會失效，從而導致圖像在召回率<0.05之前就產生了低于原MultiR的準確率，從而與原圖像產生交叉，顯然這樣的參數是不可取的。因此本文決定選擇PR曲線與坐標軸圍成的面積大小作為性能優劣的評價指標，并且僅考慮在任意召回率下，準確率均優于原模型的PR曲線，即

通過對δ不同取值下模型性能的分析，本文發現當δ過大時，關系權重模型會導致已有關系的Weight過大，使得整個算法在抽取過程中很難抽出新的關系，因此本文對參數選取的取值范圍如下：

通過實驗，以上121種組合中僅19種符合要求，本文對剩余的參數組合及其曲線圍成的面積進行了排序，結果如表2所示。通過排名我們最終選取面積最大的參數組合作為兩個超參數最終的值(δ=0.008,α=0.3)。

表2 超參組合面積排名表

續表

3.2 聚集抽取

聚集抽取是遠程監督方法下的關系抽取算法最常用的一種評價體系。在該評價方法下，考察的是對于每一個實體對(e1,e2)的所有句子s1，…，sn，其構成的整體的抽取結果集合Y′是否與實體對在知識庫中已知的關系集合Y一致，不考慮具體句子抽取的準確性。

在整體抽取的評價中本文選用的對照算法有:

(1) Mintz： Mintz等人于2009年提出的單實例單標簽抽取算法[5]。

(2) MultiR： Hoffmann等人于2011年提出的多實例多標簽算法，本文用來改進的原型算法[7]。

(3) MIMLRE： Surdeanu等人于2012年提出的多實例多標簽算法，相比于MultiR它進行了更少的假設，對每一個關系都有單獨的分類器[8]。

聚焦抽取結果對比如圖3所示。通過圖3可以看到，在相等召回率的情況下，OptMultiR相比其他算法在準確率上都取得了更好的結果。各算法F1分數取得最大值時的準確率和召回率結果如表3所示，可以看到OptMultiR均取得了最好的結果。

圖3 聚集抽取結果對比圖

Precision/%Recall/%F1/%Mintz26.1722.6724.29MultiR32.0524.0527.48MIMLRE32.9220.5625.32OptMultiR34.0026.1029.53

3.3 句子級抽取

僅進行聚集抽取的評價是不精確的，本文還需要考量對于每一個句子來說關系抽取結果是否準確。Hoffman等人在MultiR的實驗中選取了一部分句子并對其抽取關系進行了人工標注[7]。以下實驗中均采用該人工數據集與MultiR進行句子級對比。圖4即為在該數據集下針對每一條句子OptMultiR與MultiR的抽取效果對比。在召回率最高的點上，原MultiR達到了72.4%的準確率和51.9%的召回率，對應的F1分數是60.5%。而我們優化后的OptMultiR取得了79.57%的準確率以及59.55%的召回率，對應的F1分數是68.12%，各項指標均優于原模型。此外我們還對新模型中加入的兩個超參進行了觀察，圖4中另外兩條線對應的是OptMultiR模型僅使用超參δ=0.08或超參α=0.3時的PR曲線。從圖像中我們可以觀察到，僅僅使用關系權重矩陣(δ)的確帶來了準確率的提升，同時由于先驗知識的影響其召回率大幅下降，與此對應的是僅考慮NA關系的不完備性(α)而不使用關系權重矩陣的情況下，準確率產生了大幅下滑甚至會低于原模型，但帶來了最大召回率的提升。因此將兩者進行適當結合才能互相彌補，取得整體性能上的提升。

圖4 MultiR與OptMultiR句子級抽取對比圖

3.4 特定關系上的表現

考慮到數據集中的句子關于不同關系的分布數量是不平衡的，本文額外對出現數量比較大的八種關系的抽取表現進行了對比。同樣考慮到知識庫的不完備性，本文選取了100條句子作為測試數據并進行了人工標注以保證其正確性。對這九個關系的抽取結果見表4。

表4 在特定關系下的抽取結果對比表

續表

可以看到除了關系founders的準確率以外，優化后的OptMultiR對本文選取的常見關系在準確率和召回率上都有了顯著提升。關于關系founders，它的準確率由71.4%降為62.5%，通過觀察實際樣本得出的結論是，這些未被發現的樣本標注為了NA。這也就意味著對于founders這個關系來說，模型要更加弱化NA關系以提升其準確率，這也反映了模型存在的一個不足，那就是對于所有的關系來說NA系數α是共用的，顯然關系庫中關系的不完備性是不盡相同的，如何改善這一缺陷也是本文未來工作的一項目標。

4 總結

關系抽取這一構建知識圖譜的關鍵技術，已經經過了十幾年的發展。從最初基于人工模式匹配的方式，到后來機器學習熱潮的涌現，再到遠程監督方法的流行[11-12]。在此過程中抽取模型也從單一標簽進化為多實例多標簽學習，本文選取了經典的多實例多標簽算法MultiR并對其進行優化。對于模型本身，本文引入了獨立的關系權重矩陣模型干預抽取的打分過程，使得抽取的關系更為精確。在從實現方式上，本文使用基于狀態壓縮的動態規劃算法，求得了概率圖計算問題的最優解。從實驗結果來看，無論是整體的表現性還是對于高頻出現的關系，優化后模型OptMultiR的抽取能力都遠超過原模型，性能取得了顯著的提升。在今后的工作中，我們會繼續依據關系之間的相關性對模型進行優化，并且嘗試減少模型中的超參帶來的人為干擾，以增強系統的魯棒性。