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

齊振宇，劉 康，趙 軍

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

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

3.1 Wikipedia

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

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

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

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

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

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

圖1 條目“George Washington”

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

圖2 條目“George Washington”的類別標(biāo)簽

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

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

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

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

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

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

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

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

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

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

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

4.1.1 消歧階段

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

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

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

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

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

機構(gòu)：1.華盛頓大學(xué)。2.其他機構(gòu)。

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

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

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

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

而相關(guān)度得分通過求三個條目兩兩之間相關(guān)度得到：

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

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

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

4.1.2 擴展階段

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

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

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

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

4.1.3 候選選取階段

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

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

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

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

圖3 擴展系統(tǒng)

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

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

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

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

以上我們通過兩種擴展方法得到兩個結(jié)果集，基于語義知識的抽取結(jié)果集合記為Rs，其中的候選表現(xiàn)為＜候選，相關(guān)度＞；基于模板的抽取結(jié)果集合記為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分別為該候選的頻率得分和相關(guān)度得分。如果該候選只有其中一個得分，那么另一項得分按0計算，α作為參數(shù)調(diào)節(jié)二者之間的權(quán)值。

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

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

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

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

表1 訓(xùn)練集相關(guān)信息（6語義類）

表2 測試集相關(guān)信息（6語義類）

5.2 消歧算法效果驗證

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

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

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

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

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

表4 消歧階段λ的確定

續(xù)表

5.4 對標(biāo)簽進行擴展的重要性分析

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

表5 擴展階段進行標(biāo)簽擴展的重要性分析

5.5 候選選取過程中相關(guān)度閾值影響

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

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

從上表可以得到以下兩個結(jié)論：

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

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

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

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

表7 三種方法的結(jié)果比較

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

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

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

6 總結(jié)與展望

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

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

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

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

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

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.