基于敘詞表的領域知識圖譜初始種子集自動生成算法

韓其琛,趙亞偉,姚 鄭,付立軍

(中國科學院大學 大數據分析技術實驗室，北京 100049)

0 引言

隨著互聯網的快速發展，網絡上的數據變得越來越龐大，伴隨而來的就是對于龐大數據的管理問題。同時傳統的文檔網頁組織方式造成了大量數據資源浪費，也加大了人們從互聯網中查詢信息的難度。知識圖譜作為一種用實體及其語義關系來表達知識的有向圖，可以將傳統互聯網中由龐大信息組成的文檔(網頁)萬維網變為包含大量描述各種實體和實體之間豐富關系的數據萬維網。因此，自動構建圖譜的算法成為目前的研究熱點。

Bootstrapping算法是目前開放域信息抽取中比較常見的一種方法，通過模板生成和實例抽取兩個階段不斷迭代，進而不斷擴充關系實例。由于Bootstrapping的使用并不需要引入句法分析等深度語言分析工具，因此具有很強的跨領域通用性和魯棒性。但是Bootstrapping的效果往往取決于種子的選取和設置[1]。在Bootstrapping方法中，自動化的種子生成主要利用現有的知識庫如知識圖譜或本體，從知識庫中已經確定的實體和關系類型中抽取種子[2]。這種方法在構建通用知識圖譜時產生了很好的效果，但是在垂直行業領域，由于領域本體和圖譜均尚未成熟，實體和關系類型粒度過粗，導致該方法難以利用。與之相對的是，目前很多行業領域都有自己較成熟的敘詞表。

敘詞表是一個相對完善并且發展成熟的受控詞表，最早用于傳統文獻標引工作，其內部蘊含豐富的語義關系。敘詞表中的關系有相等關系、等級關系和相關關系三種，其中除了相等關系和等級關系，其余的所有關系都用相關關系命名。作為一個受控詞表，敘詞表并沒有顯式地表達出實體類型和關系類型。針對這一問題，本文提出兩個假設，即一元關系種子假設和二元關系種子假設，利用假設可以從敘詞表內部結構中提取實體類型和關系類型，進而提出了一種基于敘詞表的自動生成高質量種子的方法。在實驗中，利用由敘詞表自動生成的種子作為初始種子進行抽取工作，通過對抽取結果進行分析，發現利用敘詞表得到的初始種子可以取得同人工設計種子比較接近的效果。

1 相關工作

在關于開放域無/弱監督信息抽取的研究中，除了Bootstrapping方法外，主流方法有開放域抽取[3-5]和遠程監督方法[6-8]。開放域抽取方法雖然可以在無監督的條件下從句子中抽取關系，但無法明確定義關系類別；而遠程監督方法則需要一個具有一定規模且關系種類多的知識庫，因此在垂直領域難以應用。

Bootstrapping方法最早由Blum等人于1998年提出[9]，Wang和Cohen進一步完善該方法，提出了用于抽取一元關系和二元關系的SEAL算法[10-11]，這也是目前Bootstrapping算法的基本形式。Carlson等人利用SEAL及其改進方法構建一個NELL(toward never ending language learning)系統[2,12]，利用一個初始的本體得到需要抽取的實體和關系類型，并通過人來手工構造種子。Bootstrapping方法面臨的一個主要問題是在迭代過程中會引入噪聲實例和噪聲模板，這一問題稱為語義漂移問題[13]，這也是導致算法準確度下降的主要原因。為了解決這一問題，文獻[14]通過建模不同抽取關系之間的約束，尋找最大化滿足這些約束的抽取結果；文獻[15]通過引入負實例來限制語義漂移，以上均是在抽取的過程中進行改進。Wang和Cohen等人在其研究中證實良好的種子設計同樣可以大大提高算法的準確度[16]。這也說明，高質量的種子可以在算法迭代的初始階段有效地避免語義漂移問題的發生。

關于敘詞表的應用，同本文類似的研究為敘詞表到本體的轉化。與本文只需要從敘詞表中提取實體和關系類型不同，該研究最終需要得到一個符合OWL等相關規范的具有完整體系的本體。由于本體同敘詞表的結構有著很大的差異[17]，因此，該類研究通常需要先手工構建對應領域的本體框架，隨后將敘詞表中的關系轉化到對應的框架中。文獻[18]發現大部分轉換方法只針對特定敘詞表，缺乏通用性的轉換方法。文獻[19]給出了從領域敘詞表轉化為領域本體的完整方法，使得在保留原有語義的同時能夠具有本體特有的語義信息如推理等，但是依舊需要人工來制定本體的基本結構以及轉化規則。

2 相關定義

敘詞表一般可表示為一個三元組G={PT,VT,R}，PT為敘詞集合，也稱為優選術語集合，是所有關系的基礎，VT為非敘詞集合，與優選術語定義等價，所有詞的集合為WT=PT∪VT。R為詞間關系，可表示為一個五元組R=D,S,F,C,Z，其中有三種關系為建立在PT內部的對應，對于任一敘詞x∈PT，S(x)表示x的上位詞，F(x)表示x下位詞，C(x)表示x的相關詞。D為建立在PT子集到VT之間的對應，對于任一敘詞x∈PT，D(x)代表x的同義詞。Z為建立在PT到TT的映射，對于任一敘詞x∈PT，Z(x)代表x的族首詞，其中TT={x∈PT|Sx=?∧Fx≠?}。

定義1(敘詞表概念樹) 在敘詞表中，對于?z∈TT，集合y∈PT|Zy=z為一個由有限節點組成的具有層次關系的集合，根據樹的定義，該集合可以用多叉樹表示，該集合T稱為敘詞表概念樹。樹中的節點N稱為敘詞節點。對于每一個節點N所對應的敘詞y，若D(y)不為空集，那么D(y)中的非敘詞也在節點中存儲。每個敘詞節點對應一個實體。

敘詞表概念樹的形式如圖1所示。

圖1 敘詞表概念樹

定義2(敘詞森林) 對于集合TT={z1,z2,...,zn}，根據定義1將族首詞zi轉化為敘詞表概念樹ti。 所有ti構成的集合稱為敘詞森林。

根據前兩個定義，可以將整個敘詞表轉化為一個敘詞森林。值得注意的是，在每棵敘詞表概念樹T的內部，只存在等級和等價兩種關系，相關關系存在于樹與樹之間。為了得到更多的相關關系，對敘詞表中原有的相關關系做了擴充。

定義3(相關關系) 相關關系CP=C∪CI，若x,y存在相關關系，那么CP(x,y)為真。其中，敘詞表中所規定的相關關系C稱為直接相關關系，本文拓展得到的相關關系CI稱為間接相關關系。

定義4(間接相關關系) 假設兩個節點對應的敘詞yi,yj存在相關關系C，那么存在式(1)。

為了篩選出運行性能最好的種子，引入有效候選實體(對)和語義范圍的概念進行種子篩選，從而得到抗語義漂移能力強且更加具體的種子。一般來說，一個一(二)元種子包含兩個實體詞(對)，因此規定一個一元種子為集合useed=s1,s2，一個二元種子為集合bseed=px1,py1,px2,py2。

定義5(有效候選實體) 對于?useed進行一輪迭代，對于返回的候選實體t，若滿足t∈{y|s1,s2,y∈T}，其中，T為一棵敘詞表概念樹，則t稱為有效候選實體。

定義6(實體類型集合) 設USi={useed1,useed2}為自動生成的第i個實體類型的種子，規定對USi進行擴充后的實體詞集合為ETi=bstuseed1∪bstuseed2∪Ti。 其中，Ti為種子所在的敘詞表概念樹，bstuseed指對種子useed進行限輪次的迭代得到的實體集合。將所有實體類別分別進行擴展得到的ETS={ET1,ET2,...,ETn}稱為實體類型集合。

定義7(有效候選實體對) 對?bseed進行一輪迭代，對于返回的候選實體對(x,y)，若滿足x,y∈{x,y|y,py1,py2∈ETi∧x,px1,px2∈ETj}，則稱(x,y)為有效候選實體對。

定義8(語義范圍) 在敘詞表概念樹T中，對于任意節點N，其語義范圍定義為式(2)。

其中，ln為以節點N為根節點的子樹所包含的葉子節點數目，lN為T所包含的全部葉子節點數目。

3 種子自動生成算法

3.1 一元關系種子自動生成

當Bootstrapping進行一元關系擴展時，其主要接受少部分詞作為種子，在文本中找到適用于這些種子的共同模板，利用這些共同模板從文本中抽取新的候選實體，從中優選出合適的實體詞加入到種子集合中，從而達到一元關系擴展的目的。本算法首先提出一個判斷敘詞表內部任意兩個詞是否屬于同一個實體類型的假設，隨后利用該假設提出USAG(unary seed auto-generation)算法。首先，本文提出假設1，如下文所示。

假設1(一元關系種子假設) 在敘詞表中，對于任意兩個詞?w1,w2∈WT，若存在一個敘詞表概念樹T，滿足w1∈T∧w2∈T，那么w1,w2具有相同的實體類型，否則，w1,w2具有不同的實體類型。

例如，在地質領域敘詞表中有兩個族首詞分別為金屬元素和金屬礦，由這兩個族首詞所形成的兩棵敘詞表概念樹分別代表地質領域兩種常見的實體類型。

根據假設1，可以將敘詞森林中的每一棵樹轉化為一個實體類型集合。為了選擇更加合適的種子，提出一元種子評分函數。種子評分函數的設計主要考慮兩方面要素。首先是指代明確，種子中的實體詞應表示明確的實體，這樣才能找到更多有效的實體；其次是防止語義漂移的能力，如果一個種子在初始階段會發生嚴重的語義漂移現象，那么后續的準確率將無法保證。對于一個一元種子useed=s1,s2迭代三到五輪，其評分uscore定義如式(3)所示。

其中，q為每輪迭代返回候選實體的平均數，p為每輪迭代有效候選實體的平均數，α為調節因子。

在評分公式中，返回的有效實體比例越大，該種子的防止語義漂移的能力越強；兩個實體的語義范圍越小，該種子中的實體詞更加明確具體。

算法1 USAG算法偽代碼輸入: 敘詞森林TF=T1,T2,…,Tn 輸出: TOP1,TOP2,…,TOPm ,TOPm指第m個實體類型的種子1. 根據假設1構建實體類型集合,size表示集合元素的個數。ETS=ETi|sizeETi >2 ,ETi={y|y∈Ti};2. 對于ETS中的每個元素ETi,執行步驟3;3. 將ETi中的元素兩兩組合,利用Bootstrapping算法進行迭代,并根據公式(3)計算uscore,選取得分最高的前兩個種子加入TOPi

3.2 二元關系種子自動生成

當Bootstrapping進行二元關系擴展時，其主要接受少部分實體對作為種子，主要的步驟和方法同一元關系類似，最終將優選的實體對加入到種子集合中。在設計種子時，需要預先定義好所有的關系類型，從而根據關系的類型來選取合適的實體對作為種子。本算法首先提出一個判斷敘詞表中任意兩個實體詞對是否具有同一個關系類型的假設，隨后利用該假設提出BSAG(binary seed auto-generation)算法。本文提出的假設2如下所示。

假設2(二元關系種子假設) 在敘詞表中，對于兩個具有相關關系的實體詞對{x1,y1,x2,y2|CPx1,y1∧CPx2,y2}，若存在兩棵敘詞表概念樹T1,T2，滿足y1,y2∈T1∧x1,x2∈T2，那么x1,y1,x2,y2具有相同的關系類型，否則，x1,y1,x2,y2具有不同的關系類型。

文獻[20]中曾提出一個假設: 如果關系已經確定，那么關系前后的實體類別就可以確定。本文所提出假設可以視為該假設的反向結論，但是需要一個前提，就是在同一個領域敘詞表中。在敘詞表中，由于族的劃分非常細致，實體類型粒度足夠小，因此，利用關系前后主體和客體的實體類別基本可以限定一個關系。例如，敘詞表中含有兩個族首詞為金屬元素和金屬礦，那么如果一個具有相關關系的實體對包括一個金屬元素和一個金屬礦，其描述的關系可以確定為是一種包含關系。

算法2 BSAG算法偽代碼輸入: 敘詞森林TF=T1,T2,…,Tn 輸出: TOP1,TOP2,…,TOPi ,TOPi指第i個關系類型的種子1. 根據假設2構建關系類型集合RTS={RTi|sizeRTi >2},RTi={x,y |x∈Ti∧y∈Tj∧CPx,y };2. 對于RTS中的每個元素RTi,執行步驟3;3. 將RTi中的元素兩兩組合,利用Bootstrapping算法進行迭代,并根據公式(4)計算bscore,選取得分最高的前兩個種子加入TOPi

借助假設2，可以將敘詞表中的相關關系根據前后實體類型的不同轉化為不同的關系。利用有效實體對和語義范圍的定義，對于一個二元種子bseed=px1,py1,px2,py2迭代三到五輪，其評分bscore定義如式(4)所示。

其中，q為每輪迭代之后返回候選實體對的平均數，p為每輪迭代有效候選實體對的平均數，β為調節因子，sc為scover函數的簡寫。在評分公式中，返回的有效實體對比例越大，該種子的防止語義漂移的能力越強；關系的前后實體的語義范圍越小，該種子中的關系也更加明確具體。

種子自動生成整體框架如圖2所示。

圖2 種子自動生成框架

4 實驗

4.1 實驗數據和評價指標的選取

為了更好地驗證方法的通用性，本文利用由中國地質圖書館提供的地質領域敘詞表(總詞數為10 511，族首詞數為431)，以及從中國林業信息網得到的林業敘詞表(總詞數為38 521，族首詞數為93)作為實驗的敘詞表資源，通過抓取搜索引擎的每條檢索結果對應的網頁得到。實驗采用百度搜索作為搜索引擎。

本文選取文獻[11]中的SEAL算法實現作為實驗的Bootstrapping算法。在SEAL中，每一輪算法會返回一個排序后的候選實體列表。因此，本文采用信息檢索的方式來對種子抽取的效果進行評估。平均準確率(MAP)是在信息檢索領域常用的評價指標，該指標融合了準確率和召回率的衡量，而且對于排序的位置非常敏感。在MAP公式的設置上，為了更加合理的對比，本文采用文獻[11]中的設計方式，具體如式(5)所示。

其中，L為抽取候選實例的列表；cn表示正確實例的個數；prec(r)為截止r之前的準確率，若r位置的實例不正確，則為0；isfresh(r)是一個二值函數，判斷同義的實例是否在之前出現過，如果出現，則為0，否則，為1。對于關系類型抽取得到的實體對，也按照式(5)進行檢驗，每一個實體對作為一個關系實例來判斷是否正確。

4.2 類型抽取檢驗

為了驗證算法中所提出的兩個假設的準確性，根據兩個假設的內容，從兩個不同領域的敘詞表中提取各自的實體類型和關系類型，通過人工評測的方式找到其中的有效實體(關系)類型。這里有效的標準在于類型表達的含義明確而且和其他類型可以明確區分。由于敘詞表的編排相對比較隨意，這里保留至少有10個實例的實體類型和至少有七個實例的關系類型作為最終的類型。實驗結果如表1所示。

表1 類型抽取測試

從表1中看出，實體類型的有效比例要好于關系類型，這是由于敘詞表中族首詞的劃分本身就是由領域專家指定，相對來說比較規范；地質領域的效果普遍好于林業領域，這是由于不同敘詞表雖然遵循同樣的標準，但是其質量還是取決于人工制定的質量。通過對于無效類型的分析，主要的問題在于由于族首詞劃分過細導致類型之間會互相覆蓋。

4.3 種子質量實驗

為了檢驗算法中自動生成的種子的質量，從兩個領域各自抽取八個實體(關系)類型，選取的類型如表2第二列所示。

對于每個實體(關系)類型分別得到兩個種子，分別利用SEAL迭代至10輪，對于第10輪返回的候選實例列表進行MAP的測試。實驗結果如表3所示。

表2 實例展示

關于超參數的設定，從表2的16個類型中，每個領域分別選擇兩個實體類型和兩個關系類型共計八個用于測試超參數取值。利用網格搜索方法確定兩個超參數α和β的取值，具體方法為，令α和β的取值區間均為[0, 10]，設定步長(本文設為0.5)，以第10輪返回的候選實例列表的MAP值作為最終的評價指標。最終確定最優的超參數的取值，本實驗獲得的最優超參數α的值為1，β的值為1.5。

表3 種子質量測試

這里利用三種方法對于兩個領域的類型進行了測試。

(1) 隨機選擇種子是從類型當中隨機抽取兩個作為種子進行測試，對于關系類型，由于百度結果本身較少，有可能存在隨機抽取得到的種子沒有找到任何候選是實體對，那么以第一個有結果的種子作為結果記錄。

(2) 自動生成種子就是利用本文提出的兩個算法得到。

(3) 人工構造種子由人工來設計多個種子，最終選擇效果最好的種子作為結果記錄，基本可以認為是最好的結果。

SEAL平均得分是對于通用領域的人工設計種子進行的測試，相比于專業領域，通用領域所涉及的信息在互聯網上更加全面豐富。

從實體類型的結果來看，自動生成的種子相比隨機選擇得到的種子效果有了大幅度的提升，取得了近似于人工構造種子的效果；林業領域的效果要略好于地質領域，但是基本上比較接近，這說明算法的跨領域通用性。

從關系類型的結果來看，相比于一元關系種子，通過三種方法得到的二元關系種子的準確率有一定程度的下降。其主要原因在于二元關系限制較多，從互聯網中得到同時包含多個專業領域實體的文檔數量會快速下降，在沒有足夠語料保障的情況下，候選種子的準確率會快速下降。

4.4 樣例展示

為了更好地展示抽取效果，在表2第三列展示用于實驗的實體類型和關系類型的前十個抽取結果。根據SEAL算法的規定，同4.3節中用于評估MAP的第10輪候選實例列表不同，這里的抽取結果是由每一輪迭代返回的候選列表中評分最高且非重復實例組成。為了方便進行錯誤的分析，在表2中利用黑體加框表示抽取錯誤。

通過觀察表2，可以發現抽取的結果大部分都是符合其對應的類型名稱，對于某些實例有限的類型例如育種培養和湖泊地貌，基本覆蓋了常見的全部實例，這說明本文算法的有效性。

針對錯誤的實例，可以發現少量的實體類型錯誤，主要原因是由于實體范圍有限或者語義漂移導致。例如，黃土地貌類型下，由于實體范圍有限，前九個實體基本涵蓋了所有常見的黃土地貌，所以第十個會出現錯誤；而在育種培養中，花器官作為植物繁殖器官同其他育種實體有著比較大的語義關系，這種情況會導致語義漂移的現象出現。

關系類型存在比較明顯的語義漂移現象，例如，交代作用—變質巖以及顯生宙—地殼運動中的錯誤，這是由于通用搜索引擎的領域性不強所導致，在沒有足夠語料保障的情況下，會出現一些錯誤；表中其他的關系類型錯誤主要是由于關系中實體類型不準確導致，例如，烏姆賴薩斯考古遺址并不屬于國家公園，熱帶草原不屬于森林等。

4.5 模型通用性分析

經過幾十年的發展，敘詞表的編制方法得到不斷改善，最終形成了一系列的國際標準。國際標準有1974年發布的ISO 2788和1985年發布的ISO 5964, 中國目前的現行標準為 1991 年發布的GB/T 13190。在這些標準中均明確規定了敘詞表的結構以及詞間關系。本文所利用的敘詞表的結構以及詞間關系在現行任何符合標準的敘詞表中均是存在的，因此本文所提出的算法具有較強的通用性。

5 結束語

由于Bootstrapping算法的性能很大程度上依賴于種子設計的質量，本文利用敘詞表中所蘊含的語義信息，提出了從敘詞表內部結構中提取實體類型和關系類型的兩個假設，并設計了一種基于敘詞表的自動生成高質量種子的方法，實驗表明，該方法取得了同人工設計種子比較接近的效果。由于敘詞表的通用性，本文模型同樣適合其他的行業領域。該方法為構建領域知識圖譜提供了一個新的研究思路。在今后的研究中可以從引入第三方監督進行聯合建模等方面進行改進和完善。