齊振宇，劉 康，趙 軍

（中國科學院 自動化研究所 模式識別國家重點實驗室，北京100190）

1 引言

無論在學術領域還是在工業(yè)領域，同類命名實體列表都具有廣泛的應用。在工業(yè)領域中，搜索引擎公司比如Google、Yahoo、Bing等都在后臺維護大量的命名實體列表以提高用戶體驗［1］；而在學術領域，同類命名實體列表在問答系統(tǒng)、知識庫構建等方面也有重要應用［2］。鑒于此，多年來一直有研究者在研究如何獲得同類實體列表，即如何解決實體集合擴展問題。

實體集合擴展（Entity Set Expansion），指的是這樣一類問題：給定某語義類的若干實體（以下稱為“種子”），要求得到該類別的更多實體。比如已知｛中國、美國、俄羅斯｝三個國家，要求找出更多國家，比如｛德國、日本、巴西…｝。

目前解決實體集合擴展問題主要有三類方法，分別是基于分布的方法、基于模板的方法以及基于融合的方法。無論哪一類方法，都需要若干種子作為出發(fā)點，進而通過提取種子出現(xiàn)的上下文或者網(wǎng)頁結構等信息來捕獲種子共有的淺層環(huán)境特征，以此作為擴展的依據(jù)。但實體往往具有歧義性，這會導致所提取的淺層環(huán)境特征產(chǎn)生偏差，使得擴展得到的實體與原始種子在語義上不相匹配，從而影響實體集合擴展的精度。

比如“Washington”作為種子，可能指地點（美國首都）、可能指人物（美國前總統(tǒng)），也可能指一艘船（美國海軍的一艘航空母艦）等。不同語義的“Washington”，其上下文具有不同特征。如果不區(qū)分各自的語義，簡單地把不同語義的上下文特征混雜在一起，這種情況下得到的淺層環(huán)境特征是不可靠的，基于此得到的擴展結果也會包含很多錯誤。

為解決種子歧義性問題，本文提出了一種通過挖掘種子實體蘊含的語義信息，并與基于上下文統(tǒng)計特征的方法結合起來進行實體集合擴展的方法。具體地，我們在Wikipedia中利用種子實體的鏈接信息和類別信息進行實體集合擴展，在此基礎上融合了傳統(tǒng)的基于淺層環(huán)境特征的實體集合擴展方法。實驗結果表明，本文方法可以同時提高準確率、召回率和MAP值。

本文組織結構如下：第2節(jié)介紹實體集合擴展的研究現(xiàn)狀以及本文的動機；第3節(jié)介紹Wikipedia及其中蘊含的語義信息在實體集合擴展中的應用；第4節(jié)介紹本文提出的融合實體語義知識的實體集合擴展方法；第5節(jié)是實驗結果與分析；最后給出總結與展望。

2 相關工作

實體集合擴展的目標可以分為兩類，一類是大而開放類別的語義類，另一類是小而封閉類別的語義類［3］。在前者中，待擴展的語義類含有數(shù)量龐大的實體（即“大”），而且其實體可以是變化的（即“開放”）；比如“運動員”這個類別。而在后者中，待擴展的語義類規(guī)模較?。础靶　保移鋵嶓w基本沒有變化（即“封閉”）；比如“國家”這個類別。本文主要研究針對小而封閉語義類的實體集合擴展問題。

目前解決實體集合擴展問題的主流方法，大體上可以分為基于模板、基于分布以及基于融合等三大類。

基于模板的方法，代表性工作包括文獻［3－7］等。這類方法的核心思想是，通過某種方式得到模板，利用模板抽取候選實體，最后對候選進行打分排序得到結果。這里的模板可以是預先定義的語義模板，比如“such as”，“and”等，也可以是種子在語料中出現(xiàn)的高頻上下文。實驗結果［6］表明這類方法適用于處理小而封閉的語義類擴展問題。

基于分布的方法，代表性工作包括文獻［8－10］等。這類方法核心思想是，統(tǒng)計語料庫中每個詞項的上下文分布并構造詞項分布矩陣，利用該矩陣計算每個詞項與種子的相似度，以此作為打分和排序的標準。這一類方法更適用于處理大而開放的語義類擴展問題。

基于融合的方法，代表性工作包括文獻［11－12］等。這類方法使用多種類型的數(shù)據(jù)（比如普通網(wǎng)頁文本、網(wǎng)頁表格、查詢?nèi)罩镜龋瑢Σ煌愋偷臄?shù)據(jù)采用不同處理方法（基于模板或基于分布），并對各自的結果進行融合。這種方法可以降低單一方法所產(chǎn)生錯誤對總體結果的影響，這類方法同樣更適用于處理大而開放的語義類擴展問題。

已有方法均從種子的上下文統(tǒng)計特征入手，沒有使用種子的語義知識。這些方法的弊端在于單純的上下文統(tǒng)計特征不足以完整刻畫種子的全部特性。尤其當種子具有歧義性時，其上下文統(tǒng)計特征會產(chǎn)生偏差，此時擴展效果也會受到很大影響。

比如“Lincoln”這個詞，可能指人物，可能指轎車，還可能指地點。而不同語義的“Lincoln”，其上下文統(tǒng)計特征顯然具有不同規(guī)律。當指人物時，其上下文多為“…是美國總統(tǒng)”，“…出生于”等；而指轎車時，其上下文多為“…報價”，“…是一種豪華車”等；而指地點時，其上下文多為“…創(chuàng)建于”“…位于”等。

為降低種子歧義性對實體集合擴展的不良影響，我們提出一種融合實體語義知識的實體集合擴展方法。該方法把基于語義知識的擴展方法與基于模板的擴展方法融合在一起。在基于語義知識進行擴展時，引入語義知識庫來挖掘種子蘊含的語義信息，并利用這些語義信息在知識庫中進行擴展，以此降低種子歧義性的影響；在基于模板進行擴展時，使用種子的上下文進行擴展，以此彌補知識庫在更新速度和完備性上的不足。最后把這兩種方法的結果融合起來作為最終結果。

3 Wikipedia及其所蘊含語義知識的使用

3.1 Wikipedia

Wikipedia①http：／／www.wikipedia.org／是一個基于Wiki技術的百科全書項目，其產(chǎn)物是一個動態(tài)的、可自由訪問和編輯的知識體。根據(jù)知名的Alexa網(wǎng)絡流量統(tǒng)計排名，Wikipedia目前為世界網(wǎng)站流量排名第七大網(wǎng)站。

截至2011年11月，Wikipedia的總條目已達1900萬條（其中英文條目超過370萬條②http：／／en.wikipedia.org／wiki／Wikipedia：Size＿of＿Wikipedia），每個條目對應一篇高質(zhì)量的、富含超鏈接以及類別信息的文檔。Wiki基金會每個月都會放出一個新版本的Wikipedia下載以滿足用戶的需求。

由于Wikipedia具有信息量大、質(zhì)量高、獲取方便、更新快等優(yōu)點，其在自然語言處理以及知識工程領域得到廣泛的使用，大量的研究工作使用 Wikipedia作為語料或資源。本文使用英文版的 Wikipedia作為語義知識庫。

3.2 Wikipedia所蘊含語義知識在實體集合擴展中的使用

本文利用Wikipedia中條目之間的超鏈接關系以及類別標簽體系兩類語義知識進行實體集合擴展。

超鏈接關系：在Wikipedia中，每個條目對應一篇文檔（見圖1），該文檔是對該條目的描述。平均每篇Wikipedia文檔含有34個到其他條目的鏈接，同時有34個其他條目鏈接到該文檔［13］，本文將這些鏈接視為對該條目的一種語義描述。

圖1 條目“George Washington”

類別標簽體系：Wikipedia中，一個條目可以有若干個類別標簽（Category Label，見圖2），而一個標簽可以標注多個條目。這些標簽反映了該條目所屬的語義類別。此外，所有類別標簽組成了一個復雜的類別體系。通過衡量單個標簽在分類體系中的位置可以考察不同標簽的語義信息，進而考察屬于該標簽的條目的語義信息。

圖2 條目“George Washington”的類別標簽

在本文中，我們使用條目之間的超鏈接關系進行消歧以及相關度的計算，使用類別標簽體系進行擴展。在下一節(jié)中，我們會詳細描述這兩類語義知識的使用。

4 融合實體語義知識的實體集合擴展方法

在這一節(jié)中，我們將介紹融合實體語義知識的實體集合擴展方法。其中4.1節(jié)介紹基于語義知識的擴展方法；4.2節(jié)介紹基于模板的擴展方法；4.3節(jié)介紹二者的融合。

4.1 基于語義知識的實體集合擴展方法

首先我們做出一個基本假設：種子實體在Wikipedia中都能找到對應條目。

實際上，Wikipedia不可能覆蓋所有的實體。但由于人們通常使用熟悉的實體作為種子，而Wikipedia對于常見實體的覆蓋度非常高。所以這個假設可以成立。

結合Wikipedia知識庫的結構特點，我們設計了一個三階段的實體集合擴展系統(tǒng)：

第一階段—消歧階段。本階段的任務是明確種子實體在Wikipedia中對應的條目。輸入是3個種子，輸出是這3個種子在Wikipedia中對應的條目。

第二階段—擴展階段。本階段的任務是根據(jù)上一階段的結果，找到Wikipedia中可能屬于同語義類的條目作為候選。輸入是種子對應的條目，輸出是作為候選的若干條目。

第三階段—選取階段。本階段的任務是對候選條目打分并排序，得到最終的結果。

以下分別介紹這三個階段。

4.1.1 消歧階段

當確認種子實體在Wikipedia中對應的條目時，由于種子錨文本可能具有多種不同語義，會出現(xiàn)歧義問題。關于這個問題我們通過一個例子加以說明。

仍然考慮“Washington”這個詞，它可以指向很多實體：

人：1.美國第一任總統(tǒng)華盛頓。2.其他姓“華盛頓”的人，比如電影演員丹澤爾·華盛頓

地點：1.美國首都。2.美國的一個州名。3.其他地點。

船：1.美國海軍華盛頓號航空母艦。

機構：1.華盛頓大學。2.其他機構。

實際上，“Washington”作為錨文本在 Wikipedia中指向的條目超過100個。這種一個錨文本指向多個條目的現(xiàn)象非常普遍。下一節(jié)實驗數(shù)據(jù)表明，每個實體在 Wikipedia中作為錨文本指向的條目平均超過5個。為確認種子實體對應的條目，必須解決歧義問題。

我們提出了一種綜合考慮條目概率與語義相關度的消歧方法。設種子A對應的候選條目集為｛a1，a2，…，ai｝，種子 B 對應的候選條目集為｛b1，b2，…，bj｝，種子C 對應的候選條目集為｛c1，c2，…，ck｝，給定A、B、C后，我們按式（1）的方法選取最合適的條目組｛al，bm，cn｝。

該方法考察兩方面的因素：第一是三個候選條目被選中的概率得分；第二是三個候選條目之間的相關度得分。

其中概率得分通過計算三個條目被選中概率之積求對數(shù)得到：

而相關度得分通過求三個條目兩兩之間相關度得到：

其中，我們使用 Milne［13］提出的算法來計算兩個條目之間語義相關度，見式（4）。

其中x、y是兩個條目，X、Y分別是鏈接到這兩個條目的其他條目的集合，W 指整個Wikipedia。

λ作為參數(shù)調(diào)節(jié)兩部分所占的比重。

4.1.2 擴展階段

我們設計了一種使用Wikipedia中類別標簽來尋找與種子條目屬于同一語義類條目的擴展系統(tǒng)，該系統(tǒng)框架見圖3。該系統(tǒng)可以分為兩個階段：

階段一，求出a、b、c三個條目中每個條目的標簽集合，記為La、Lb、Lc。取出至少在兩個標簽集合中出現(xiàn)的標簽組成一個公共標簽集合。

階段二，抽取出公共標簽集合中標簽包括的文章作為候選條目。

為提高抽取效果，我們在階段一中進行標簽擴展：即La不僅包括條目a的標簽，還包括條目a的標簽在標簽體系中的上一層標簽。

4.1.3 候選選取階段

我們考察候選條目與種子條目之間的相關度，并選取相關度在一定閾值（以下稱該值為“相關度閾值”）以上的候選條目作為結果。

在訓練階段，為求得“相關度閾值”，我們采取以下做法：設訓練集T共有m個語義類，對其中每個語義類s，我們利用4.1.1節(jié)中的式（4）計算同類別條目之間的平均相似度：

其中n為類s含有的實體個數(shù)。之后對T中m個語義類的平均相似度求平均，得到整個訓練集T的平均語義相似度：

在本文中，經(jīng)計算得到的“相關度閾值”為AvgRrelT＝0.56。

圖3 擴展系統(tǒng)

在測試階段，我們利用4.1.1節(jié)中式（4）分別計算候選條目與三個種子條目之間的相關度并求平均值。抽取平均相關度在“相關度閾值”以上的候選條目組成結果集，并將結果集合中的條目按相關度排序作為結果返回。

4.2 基于模板的實體集合擴展

我們實現(xiàn)了一種高效的基于模板的實體集合擴展方法［6］。該算法把三個種子作為查詢詞送到搜索引擎中，并爬取搜索引擎返回的前100個URL對應的網(wǎng)頁作為語料。之后針對單個網(wǎng)頁學習種子在其中出現(xiàn)的模板，并利用學到的模板得到候選。最后我們采用按照出現(xiàn)頻率排序的方式為候選排序并抽取出現(xiàn)次數(shù)大于1的候選作為結果返回。

4.3 基于語義知識與基于模板兩種方法的融合

以上我們通過兩種擴展方法得到兩個結果集，基于語義知識的抽取結果集合記為Rs，其中的候選表現(xiàn)為＜候選，相關度＞；基于模板的抽取結果集合記為Rp，其中的候選表現(xiàn)為＜候選，出現(xiàn)次數(shù)＞。我們按以下方法對這兩個集合進行融合：

首先把Rp中候選的出現(xiàn)次數(shù)按式（7）歸一化到［0，1］區(qū)間。

其中分子為該候選出現(xiàn)的次數(shù)，分母為該類別候選中出現(xiàn)次數(shù)最多候選的出現(xiàn)次數(shù)。之后對每個候選按照下面式（8）對其打分：

其中freq和relatedness分別為該候選的頻率得分和相關度得分。如果該候選只有其中一個得分，那么另一項得分按0計算，α作為參數(shù)調(diào)節(jié)二者之間的權值。

5 實驗數(shù)據(jù)與分析

5.1 實驗數(shù)據(jù)

本文使用Wikipedia20110722版本作為知識庫，另外使用了 WikipediaMiner①http：／／wikipedia－miner.cms.waikato.ac.nz／軟件工具（1.2.0版本）處理Wikipedia數(shù)據(jù)。

本文構建了2組×6類別／組共12個語義類作為實驗數(shù)據(jù)，人工標定每個語義類所包含的實體。其中第一組作為訓練集，第二組作為測試集。相關數(shù)據(jù)如表1和表2所示。

表1 訓練集相關信息（6語義類）

表2 測試集相關信息（6語義類）

5.2 消歧算法效果驗證

本實驗驗證4.1.1節(jié)中消歧算法的有效性，對比不進行消歧與進行消歧兩種方法的效果（表3）。進行消歧時，按照第4節(jié)所述方法進行實體集合擴展。不進行消歧時，采用如下方法：設種子A對應的候選條目集為｛a1，a2，…，ai｝，種子B 對應的候選條目集為｛b1，b2，…，bj｝，種子C 對應的候選條目集為｛c1，c2，…，ck｝，抽取每個候選條目集中所有條目的標簽以及標簽的父標簽分別組成標簽集合LA，LB，LC，取出至少在其中兩個標簽集合中出現(xiàn)的標簽組成一個公共標簽集合，抽取出公共標簽集合中標簽包括的文章作為候選條目。在計算候選條目的相關度時，把候選條目與種子的所有可能條目的相關度均值作為該候選的相關度。

表3 消歧與不消歧效果比較

可以看出，由于不進行消歧，候選的相關度偏低，很難達到“相似度閾值”，使得結果很差。而進行消歧可以消除歧義，極大地提升方法的表現(xiàn)。

5.3 消歧算法中參數(shù)λ的確定

本實驗確定4.1.1節(jié)式（1）中參數(shù)λ的值。對每個語義類做100組實驗，每組實驗隨機抽取該類別的3個實體作為種子，記錄λ取不同值時3個種子對應的條目，當3個條目都正確時視為正確，否則視為錯誤。實驗結果如表4所示。

表4 消歧階段λ的確定

續(xù)表

5.4 對標簽進行擴展的重要性分析

本實驗驗證4.1.2節(jié)中標簽擴展的重要性（表5）。對每個語義類做500組實驗，每組實驗隨機3個種子，依據(jù)4.2節(jié)中描述的算法確認其在知識庫中對應條目后，對得到的3個條目抽取其標簽?？梢钥闯?，不進行標簽擴展時，平均每組種子只能抽出2.8個標簽；進行擴展后每組種子可以抽出10.3個標簽。這可以證明加入標簽擴展后，大大增加了得到相關條目的可能。

表5 擴展階段進行標簽擴展的重要性分析

5.5 候選選取過程中相關度閾值影響

本實驗驗證4.1.3節(jié)中相關度閾值對抽取條目的影響。我們對每個類別進行50組實驗，每組實驗隨機選取3個種子，通過第4節(jié)介紹的算法在Wikipedia中進行擴展。加入相關度閾值和不加入兩種情況下的實驗結果如表6所示。

表6 按照相關度規(guī)則抽取條目

從上表可以得到以下兩個結論：

1.正確候選條目和錯誤候選條目，二者與種子的相關度有很大差別（0.63Vs 0.16），引入相關度作為衡量候選準確性指標非常合理。

2.引入相關度閾值后，在損失1／3正確候選條目（96Vs 65）的前提下，濾去了4.7倍的錯誤候選條目（585Vs 101）。這證明了引入相關度閾值的有效性。

5.6 融合語義知識與統(tǒng)計信息的實體集合擴展

本實驗對比單純基于模板、單純基于語義以及二者融合三種方法的實體集合擴展結果。我們對每個類別做5組實驗，每組隨機抽取3個種子，分別使用基于模板、基于語義以及二者融合三種方法進行實體集合擴展，最后對5組實驗的結果求均值。實驗結果如表7所示。

表7 三種方法的結果比較

可以看出，傳統(tǒng)單純基于模板的方法召回率較高，但由于受到種子歧義性問題的影響，準確率較低；而單純基于語義的方法解決了種子歧義性問題，所以準確率較高，但召回率較低。二者融合以后，P值提升了18.5%，R值提升了6.8%，而MAP也提升了22.8%，這說明二者融合的方法吸收了兩種方法各自的優(yōu)點，彌補了不足，使得整體結果有了很大的提升。

另外，我們也測試了式（8）中不同α對融合結果的影響，可以看出，融合語義知識后的效果比單純使用模板的效果要好，而當α取0.2時，融合結果最好。

圖2 不同α對融合結果（MAP）的影響

6 總結與展望

實體集合擴展問題是開放式信息抽取中一個重要問題。目前解決該問題的方法基本都是從若干個種子出發(fā)，利用模板或種子的分布信息進行擴展，沒有考慮到種子的語義信息，所以無法解決種子歧義性問題。

本文提出了使用種子的語義信息進行擴展以解決種子歧義性問題的思路，并利用Wikipedia作為語義知識庫，實現(xiàn)一種基于語義知識的擴展方法。在給定種子的情況下，經(jīng)過消歧階段、擴展階段、選取階段最終得到擴展結果。

此外，本文把基于語義知識的擴展和基于模板的擴展相融合。實驗結果表明，新方法在P值上提升了18.5%，R值上提升了6.8%，MAP值提升了22.8%，這證明了本文方法的有效性。

未來工作主要包括以下幾個方向：

1.提升消歧階段準確率。消歧階段對后續(xù)工作影響重大，接下來我們考慮引入更豐富的語義知識，比如類別標簽等來提升消歧階段的準確率。

2.采用更好的融合方式。目前我們使用的是簡單的線性融合，以后還可以探索其他融合方式。

［1］Vishnu Vyas，Patrick Pantel，Eric Crestan.Helping editors choose better seed sets for entity set［C］／／Proceedings of CIKM 2009.Hong Kong：ACM，2009：225－234.

［2］Richard C Wang，Nico Schlaefer，William W Cohen et al.Automatic Set Expansion for List Question Answering［C］／／Proceedings of EMNLP 2008.USA：ACL，2008：947－954.

［3］Richard C Wang，William W Cohen.Automatic Set Instance Extraction Using the Web ［C］／／Proceedings of ACL／AFNLP 2009.Singapre：ACL，2009：441－449.

［4］Luis Sarmento， Valentiin Jijkoun. “More Like These”：Growing Entity Classes from Seeds ［C］／／Proceedings of CIKM 2007.Portugal：ACM，2007：959－962.

［5］Pasca.Weakly－supervised discovery of named entities using web search queries［C］／／Proceedings of CIKM 2007.Portugal：ACM，2007：683－690.

［6］Richard C Wang，William W Cohen.Language－Independent Set Expansion of Named Entities Using the Web［C］／／Proceedings of ICDM 2007.USA：IEEE Computer Society，2007：342－350.

［7］Richard C Wang，William W Cohen.Iterative set expansion of named entities Using the web［C］／／Proceedings of ICDM 2008.Italy：IEEE Computer Society，2008：1091－1096.

［8］Patrick Pantel，Eric Crestan，Arkady Borkovsky，et al.Web－Scale Distributional Similarity and Entity Set Expansion［C］／／Proceedings of EMNLP2009.Singapore：ACL，2009：938－947.

［9］Benjamin Van Durme，Marius Pasca.Finding Cars，Goddesses and Enzymes Parametrizable Acquisition of Labeled［C］／／Proceedings of AAAI08.USA：AAAI Press 2008：1243－1248.

［10］Yeye He，Dong Xin.SEISA Set Expansion by Iterative Similarity Aggregation ［C］／／Proceedings of WWW 2011.India：ACM，2011：427－436.

［11］Partha Pratim Talukdar，Joseph Reisinger，et al.Weakly－supervised acquisition of labeled class instances using graph random walks［C］／／Proceedings of EMNLP 2008.USA：ACL，2008：582－590.

［12］Marco Pennacchiotti，Patrick Pantel.Entity Extraction via Ensemble Semantics［C］／／Proceedings of EMNLP 2009.Singapore：ACL，2009：238－247.

［13］David Milne，Ian H Witten.Learning to link with Wikipedia ［C］／／Proceedings of CIKM 2008.USA：ACM，2008：509－518.