基于圖的查詢?nèi)罩緦嶓w別名抽取方法

石 貝，孫 樂，韓先培

（中國科學院 軟件研究所，北京100190）

1 引言

自然語言的多樣性決定同一實體能通過不同的別名來表達。實體的別名是指同一個實體的不同名稱。它主要包括縮略語、曾用名、拼音和其他語言的翻譯等。例如，“人人網(wǎng)”的別名有 “人人”、“校內(nèi)網(wǎng)”和“renren”等。別名抽取是指輸入一個實體的名稱，抽取并返回代表該實體的其他名稱。別名抽取的相關(guān)研究是自然語言處理的重要課題。它可以用于知識庫的構(gòu)建、機器翻譯、問答系統(tǒng)、信息檢索和實體鏈接等具體應(yīng)用中。例如，信息檢索面臨的一個重要問題就是相同的實體采用不同名稱從而造成檢索召回率的降低。使用抽取后的別名進行查詢重構(gòu)可以解決這個問題。

目前別名抽取主要是利用已有的語料庫（采用別名、原名的平行語料庫或者經(jīng)過人為分詞和詞性標注的語料庫）提取候選別名、原名集合，再利用別名、原名的上下文模板等字對齊規(guī)則進行搜索匹配［1]，或者采用機器學習的方法選擇匹配對，最后輸出正確的原名、別名對。

這類方法主要存在兩個問題。

1）語料庫構(gòu)建困難

由于別名的多樣性（包含拼音、縮略語、翻譯、曾用名），構(gòu)建高覆蓋率的別名平行語料十分困難。例如，“中國建設(shè)銀行”的別名包含“建設(shè)銀行”、“建行”、“CBC”和“Jian She Yin Hang”等。我們沒有找到包含“中國建設(shè)銀行”上述所有別名的平行語料。

2）時效性差

社交網(wǎng)絡(luò)時代的來臨讓人與人在網(wǎng)上的溝通更加頻繁，從而使自然語言的經(jīng)濟性原則得到了充分利用?！癢eibo”、“KFC”、“神九”等各種新別名出現(xiàn)越來越頻繁。Web信息的日益膨脹使平行語料的構(gòu)建速度遠遠趕不上別名的產(chǎn)生速度。如何不通過平行語料，及時地抽取別名成為了一個挑戰(zhàn)。

隨著互聯(lián)網(wǎng)信息的不斷產(chǎn)生，利用用戶生成的內(nèi)容進行別名抽取成為解決上述兩個問題的關(guān)鍵。本文提出了基于圖的查詢?nèi)罩緞e名抽取方法。首先，本文基于查詢和鏈接對應(yīng)的點擊信息，進行一次迭代，獲取候選查詢集合。然后，本文基于＜別名—模板＞對和＜查詢—鏈接＞對構(gòu)成二層圖，采用隨機游走方法對候選別名進行排序，抽取出權(quán)重較高的名稱作為實體的別名。

文章結(jié)構(gòu)安排如下：第2節(jié)介紹了別名抽取的相關(guān)方法；第3節(jié)首先介紹了算法的框架，然后詳細介紹查詢?nèi)罩局袃纱箢愑绊憚e名抽取的信息（上下文信息和查詢鏈接信息），并就各類信息的實際意義及計算方法進行詳細說明，最后綜合利用這兩個信息特征，提出一個基于二層圖的別名抽取框架；第4節(jié)用實驗對比各類信息的性能差異，并證明本文做法有效可行。第5節(jié)對本文進行總結(jié)，分析并提出下一步的工作重點和研究問題。

2 相關(guān)工作

由于別名包括縮略語等形式，所以縮略語抽取的相關(guān)工作與別名抽取密切相關(guān)。Zhu等人針對單字人名、地名簡稱，構(gòu)建了基于分類器的預(yù)測模型［2]。李斌等對漢語單字國名采取了統(tǒng)計評分法進行識別［3]。Chang和Lai使用人工標注的源短語、縮略語的平行語料庫作為訓練數(shù)據(jù)，然后利用HMM來提取縮略語、源短語對［4]。Chang和Teng提出了基于HMM的概率恢復模型（SCR），用于將縮略語擴展為源短語［5]。崔世起等利用生語料使用重復串搜索技術(shù)和詞性過濾，必要時加入人工干預(yù)，自動提取縮略語和源短語對［6]。武子英等利用上下文語義信息，基于余弦相似度自動抽取漢語縮略語［7]。Li等根據(jù)縮略語與源短語的共現(xiàn)現(xiàn)象，使用字對齊規(guī)則進行自動提取縮略語（僅處理單一類型的縮略語）［8]。上述方法目前只用于縮略語抽取，也可以用于別名的抽取，但是這些方法具有選用的語料庫時效性較差，規(guī)模較小，需要人工干預(yù)，且只解決縮略語抽取問題等缺陷。

Bollegala等人采用搜索引擎獲得候選人名別名的集合，然后利用SVM分類器進行人名別名抽取［9]。Bhat等人采用LSA方法，利用不同的別名周圍具有相同的上下文特征，進行別名抽取，但該方法有時效性低，運算量大等缺點［10]。同上述方法相比，本文方法不僅使用了上下文信息，還使用了查詢鏈接信息，提高了抽取的準確率。

對于上述方法需要平行語料，時效性低等缺點，本文提出了使用用戶查詢?nèi)罩荆詣映槿『蜻x查詢，然后利用上下文信息和查詢鏈接點擊信息構(gòu)建二層圖，再使用隨機游走算法對圖中的候選別名進行排序的方法。該方法不需要任何標注數(shù)據(jù)和人工干預(yù)，并具有很好的時效性。

3 基于查詢?nèi)罩镜膭e名抽取算法

3.1 算法框架

在輸入原名e后，別名抽取的目標是向用戶返回查詢?nèi)罩局袑嶓w的別名｛a1，a2，…，ap｝。為了便于展示，全文將通過抽取“人人網(wǎng)”的別名這個例子對我們的方法進行描述。相關(guān)定義如下：

· 輸入原名e：“人人網(wǎng)”；

· 已知由查詢記錄｛r1，r2，r3，…，rs｝構(gòu)成的文檔集合R。每一條記錄包含查詢（用q表示）和查詢對應(yīng)的點擊鏈接（用l表示）。例如，其中一條查詢記錄為“北京大學 http：／／www.pku.edu.cn”；

· 目標集合｛a1，a2，…，ap｝：“人人網(wǎng)”的別名構(gòu)成的集合。例如，“人人”，“校內(nèi)網(wǎng)”，“xiaonei”等別名所構(gòu)成的集合。

在查詢?nèi)罩局?，我們觀察到別名的特征主要包括以下兩類。

（1）和原名具有相同的上下文。例如，對于原名“人人網(wǎng)”，查詢?nèi)罩景罅坎樵儭叭巳司W(wǎng)首頁”，同時查詢?nèi)罩疽舶罅坎樵儭靶?nèi)網(wǎng)首頁”。因此，“人人網(wǎng)”和“校內(nèi)網(wǎng)”包含相同的上下文“＊首頁”。

（2）別名所構(gòu)成的查詢和原名所構(gòu)成的查詢被用戶點擊到同一鏈接。對于查詢“人人網(wǎng)地址”，其指向的鏈接為“http：／／www.renren.com”。對于查詢“校內(nèi)網(wǎng)地址”，其指向的鏈接也為“http：／／www.renren.com”。

圖1 基于圖的查詢?nèi)罩緞e名抽取算法框架

因此，利用這兩類特征，本文提出了基于圖的查詢?nèi)罩緞e名抽取算法，框架如圖1所示。

3.2 抽取候選查詢集合

實驗中查詢?nèi)罩景哂嗖樵?，?shù)據(jù)量大，因此在別名抽取前需要對查詢?nèi)罩具M行過濾，得到查詢記錄的子集——候選查詢集合Qc。候選查詢集合是有可能包含原名和別名的查詢所構(gòu)成的集合。我們的假設(shè)是，包含別名的查詢和包含原名的查詢至少指向一條共同的點擊鏈接?；诖思僭O(shè)，抽取“人人網(wǎng)”的候選查詢集合Qc的步驟如下。

1）將“人人網(wǎng)”和查詢?nèi)罩局械牟樵冎饤l匹配。如果“人人網(wǎng)”是查詢q的子串，則將q加入集合Q0中。Q0為包含原名“人人網(wǎng)”的查詢所構(gòu)成的集合。

2）對Q0中的每一個查詢q，獲得它對應(yīng)的點擊鏈接c（每一個查詢對應(yīng)的點擊鏈接可能有多個），將c加入鏈接集合C0中。

3）對C0中的每一條鏈接c，獲得c對應(yīng)的查詢q′，將q′加入候選查詢集合Qc中。

如圖2所示，我們利用了查詢—鏈接信息，生成了候選查詢集合Qc。Qc中的查詢有可能包含別名。

圖2 “人人網(wǎng)”候選查詢集合的生成過程

3.3 二層圖構(gòu)建

在獲取候選查詢集合Qc之后，我們需要抽取出Qc中的查詢所包含的別名，并對其排序。在此步驟中，本文首先構(gòu)建別名候選圖層，然后構(gòu)建查詢鏈接圖層，然后將這兩個圖層進行鏈接，得到二層圖。最后采用隨機游走算法進行排序，得到最終結(jié)果。

3.3.1 別名候選圖層的構(gòu)建

我們觀察到對于原名和別名，它們很可能共享相同的上下文。我們的假設(shè)是，如果一個查詢和包含原名的查詢有相同的上下文，那么這個查詢可能包含別名。在得到候選查詢集合Qc后，本文使用基于模板的Bootstrapping算法生成＜別名—模板＞對和＜模板—別名＞對，然后構(gòu)建別名候選圖層。構(gòu)建過程如下。

1）將原名e加入命名集合N 中。將模板池W置空。

2）分析Qc中的每個查詢q，若q包含命名集合N 中的元素n，則抽取n的上下文，生成模板w。其中，在q的句首和句尾添加 “＜s＞”和“＜／s＞”標簽作為開始標記和結(jié)束標記。例如，對于原名“人人網(wǎng)”，如果Qc中存在查詢“人人網(wǎng)首頁”，則生成模板“＜s＞＊首頁＜／s＞”。將模板w加入模板池W中，同時記錄＜別名—模板＞關(guān)系。為提高模板的有效性，減少隨機事件的影響，本文在這一階段過濾掉模板池中只出現(xiàn)過一次的模板。

3）依次取出模板池W 中的模板w。對于Qc中的每一條查詢q，若q匹配模板w，則抽取出候選別名a，并將a加入N 中，同時記錄＜模板—別名＞關(guān)系。

4）重復第2步和第3步，直至沒有新的元素加入N中。

利用上述步驟得到的＜別名—模板＞對和＜模板—別名＞對，對集合N和W 構(gòu)建二分圖。對每一個＜別名—模板＞對和＜模板—別名＞對，在圖中添加相應(yīng)的邊來連接對應(yīng)的別名節(jié)點和模板節(jié)點。如圖3所示。

圖3 別名候選圖層的構(gòu)建示例

3.3.2 查詢鏈接圖層的構(gòu)建

為了驗證使用查詢?nèi)罩具M行別名抽取的有效性，我們對查詢?nèi)罩具M行分析。我們抽取出查詢?nèi)罩局心承︰RL鏈接對應(yīng)的查詢，并按點擊次數(shù)進行排序，如表1所示。

表1 查詢?nèi)罩局心承︰RL對應(yīng)的查詢

從表1中我們觀察到，在查詢?nèi)罩局?，對于同一個鏈接“http：／／www.renren.com”或者 “http：／／www.sina.com.cn／”，其對應(yīng)的查詢（“人人網(wǎng)”和“xiaonei”，“sina”和“新浪網(wǎng)”）互為別名。因此，我們得到假設(shè)：對于同一個鏈接，如果它和幾個查詢有很強的關(guān)聯(lián)，那么這幾個查詢很可能包含同一實體對應(yīng)的別名。利用此假設(shè)，我們構(gòu)建查詢鏈接圖層的步驟如下。

1）對Qc中的每一個查詢q，將q加入查詢鏈接圖層中，同時將q對應(yīng)的鏈接l作為節(jié)點加入圖層中，并添加邊＜q，l＞。

2）對新添加的l，如果存在l對應(yīng)的查詢q不在圖層中，則將查詢q添加到圖層中，同時添加邊＜l，q＞。

重復上述兩步，直至沒有新的邊和節(jié)點加入此二分圖中，則構(gòu)建出如圖4所示的查詢鏈接圖層。

圖4 查詢鏈接圖層的構(gòu)建示例

3.3.3二層圖構(gòu)建

在構(gòu)建別名候選圖層和查詢鏈接圖層后，我們構(gòu)建一個二層圖。如圖5所示，上層為構(gòu)建好的別名候選圖層，EG＝｛EV，EE｝。EV是節(jié)點集合，包括原名e，候選別名a和包圍別名的模板w。EE是邊（evi，evj）的集合，（evi，evj）表示節(jié)點evi和evj之間的邊。下層為構(gòu)建好的查詢鏈接圖QG＝｛QV，QE｝，QV是節(jié)點集合，節(jié)點為查詢候選集合Qc中的查詢和鏈接，QE是下層節(jié)點之間的邊的集合，每個邊用日志中查詢和鏈接的共現(xiàn)來表示。如果用戶在查詢q時點擊鏈接l，則在q與l之間添加一條邊鏈接。上下兩層圖通過查詢和別名的包含關(guān)系連接。對于上層圖中的別名a，如果在下層圖中存在查詢q包含別名a，則在q和a之間添加一條邊（圖5中虛線所示）。

圖5 二層圖構(gòu)建示例

3.3.4 隨機游走算法

二層圖構(gòu)建完成之后，本文使用隨機游走算法計算圖中節(jié)點的權(quán)重［11]，然后對權(quán)重排序，返回排名靠前的別名節(jié)點。

假設(shè)該圖中節(jié)點的初始權(quán)重表示為式（1）：

其中w0i是編號為i的別名，模板，查詢或者鏈接的初始權(quán)重。該二層圖總共包含n個節(jié)點。則二層圖中邊的權(quán)重如式（2）所示：

其中ei，j表示節(jié)點i和j之間的邊的權(quán)重。針對不同的節(jié)點i和j，其權(quán)重的計算方式分為如下幾種情況。

1）如果i是別名或者原名，j是模板，那么我們使用別名i和模板j在Qc中的共現(xiàn)次數(shù)作為權(quán)重。

2）如果i是模板，j是別名或者原名，那么我們使用模板i和別名j在Qc中的共現(xiàn)次數(shù)作為權(quán)重。

3）如果i是查詢，j是點擊鏈接，那么我們使用在查詢?nèi)罩局衖和j的對應(yīng)點擊次數(shù)作為權(quán)重。

4）如果i是點擊鏈接，j是查詢，那么我們使用在查詢?nèi)罩局衖和j的對應(yīng)點擊次數(shù)作為權(quán)重。

5）如果i是別名或原名，j是查詢，那么我們使用Qc中別名或原名i被查詢j的包含次數(shù)作為權(quán)重。

6）如果i是查詢，j是別名或原名，那么我們使用Qc中查詢i包含別名或原名j的次數(shù)作為權(quán)重。

然后我們對W 進行迭代更新，如式（3）所示。

其中norm（E）是E的正規(guī)化形式，Wt是W0經(jīng)過t次迭代之后的權(quán)重向量，λ∈（0，1）是一個自由參數(shù)，表示初始向量在更新節(jié)點權(quán)重時的權(quán)重。當?shù)螖?shù)到達某個限定次數(shù)，或迭代結(jié)果趨于收斂，則停止迭代更新，作為各節(jié)點的最終權(quán)重。在本文實驗中，默認迭代50次。

在進行初始權(quán)重賦值時，原名節(jié)點賦值為1，其余節(jié)點賦值為0。在迭代一定次數(shù)，得到各節(jié)點權(quán)重后，對別名節(jié)點進行排序，輸出排序后的別名列表L。計算列表L節(jié)點權(quán)重之間梯度，將最大下降梯度之前的節(jié)點進行返回。如圖6中例子所示，返回虛線之前的節(jié)點。

圖6 列表L節(jié)點返回示例

4 實驗結(jié)果及相關(guān)分析

在這一節(jié)，我們評估了本文提出的方法，并將它同三個基準實驗進行比較。同時，我們詳細分析了實驗結(jié)果。

4.1 數(shù)據(jù)集

本文實驗數(shù)據(jù)集來自百度搜索查詢?nèi)罩緮?shù)據(jù)（2008年10月），共包含6515602個查詢。同時，本文共收集了500個原名。這500個原名主要包含機構(gòu)名（“中國建設(shè)銀行”等），品牌名（“索尼”等）和網(wǎng)站名（“新浪”，“人人網(wǎng)”）等。在該實驗中，本文基于查詢?nèi)罩緦@些原名進行別名抽取，并對抽取結(jié)果進行人工評判。

4.2 評價方式

在該實驗中，我們使用準確率（Accuracy）對實驗結(jié)果進行評判。對結(jié)果集合S，其準確率（Accuracy）如式（4）所示：

4.3 基準實驗

本文的三個基準實驗包括：

1）基于詞的上下文相似度的別名抽取方法（ConSim）。該方法抽取原名的上下文，構(gòu)成向量，然后計算候選詞的上下文向量與原名的上下文向量的余弦相似度，然后根據(jù)余弦相似度進行排序，進而抽取別名。

2）僅基于別名候選圖層，使用隨機游走算法對別名節(jié)點進行排序的別名抽取方法（ExtGraph）。

3）僅基于查詢鏈接圖層，使用隨機游走算法對查詢節(jié)點進行排序，直接將排序靠前的查詢結(jié)果作為別名（QGraph）。

本文提出的基于圖的查詢?nèi)罩緞e名抽取算法被記為（TwoGraph）。

4.4 結(jié)果與分析

在百度查詢?nèi)罩緮?shù)據(jù)上，四組實驗結(jié)果如表2所示。

表2 四種別名抽取算法的實驗結(jié)果比較

從表2可以得到如下結(jié)論。

1）四個方法中，我們的方法抽取別名效果最好。別名抽取效果比較結(jié)果為：TwoGraph＞QGraph＞ExtGraph＞ConSim。

2）和ExtGraph相比，TwoGraph在準確率上提高14.8%。這說明使用上下文信息和查詢鏈接信息進行別名抽取比僅僅使用上下文信息進行別名抽取的效果要好。

3）和QGraph相比，TwoGraph在準確率上提高9.0%。這說明使用上下文信息和查詢鏈接信息進行別名抽取比只使用查詢鏈接信息進行別名抽取的效果要好。

4）和ConSim相比，ExtGraph在準確率上提高24.8%。這證明了我們使用隨機游走算法對構(gòu)建后的別名候選圖層進行節(jié)點權(quán)重排序的有效性。

5）和ExtGraph相比，QGraph在準確率上提高5.8%。這表示查詢?nèi)罩局械牟樵冩溄有畔⒈葎e名的上下文信息更加準確。這可能因為查詢?nèi)罩局胁樵償?shù)目比較多，模板比較繁雜，所得到的上下文信息不如點擊信息更加準確。

4.5 細節(jié)分析

當輸入“人人網(wǎng)”后，TwoGraph系統(tǒng)抽取的別名列表top10如表3所示。

表3 “人人網(wǎng)”別名列表top10

從表3中可以看出，我們實驗返回的結(jié)果包括了曾用名、拼音、縮略詞、URL和拼寫錯誤。這表明了本文方法保證了別名抽取結(jié)果的多樣性。該結(jié)果也表明了該方法在抽取別名時，也抽取出了一些查詢?nèi)罩局械钠磳戝e誤（“xiaone”）。這些拼寫錯誤對系統(tǒng)性能產(chǎn)生了負面影響。

5 結(jié)論及下一步工作

本文針對目前別名抽取需要訓練語料，時效性差這兩個問題，提出了基于圖的查詢?nèi)罩緞e名抽取方法。本文總結(jié)了查詢?nèi)罩镜膬纱箢愋畔ⅲㄉ舷挛哪０逍畔⒑筒樵冩溄有畔ⅲ?，并提出了基于這兩類信息的二層圖構(gòu)建算法，然后使用隨機游走算法計算候選別名權(quán)重，抽取出別名。實驗表明：1）我們的方法可行有效，達到了71.8%的準確率；2）使用查詢鏈接信息進行別名抽取優(yōu)于使用上下文信息進行別名抽取。這兩種信息的結(jié)合能獲得更好的別名抽取效果。下一步工作中，我們將過濾查詢?nèi)罩局械钠磳戝e誤，從而降低其對別名抽取結(jié)果的負面影響；此外，如何解決查詢?nèi)罩局心承﹦e名的稀疏問題也是下一步的研究方向。

［1]劉友強，李斌，奚寧，等.基于雙語平行語料的中文縮略語提取方法［J].中文信息學報，2012，26（2）：69－74.

［2]Xiaodan Zhu，Mu Li，Jianfeng Gao，et al.Single Character Chinese Named Entity Recognition［C]／／Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing，ACL，2003.

［3]李斌，方芳.中文單字國名簡稱的自動識別［J].計算機工程與應(yīng)用，2006，42（28）：167－176.

［4]Jing－Shin Chang，Yu－Tso Lai.A preliminary study on probabilistic models for Chinese abbreviations［C]／／Proceedings of the 3rd SIGHAN Workshop on Chinese Language Processing，2004：9－16.

［5]Jing－Shin Chang，Wei－Lun Teng.Mining Atomic Chinese Abbreviation Pairs：A Probabilistic Model for Single Character Word Recovery［C]／／Proceedings of the 5th SIGHAN Workshop on Chinese Language Processing，2006：17－24.

［6]崔世起，劉群，林守勛，等.中文縮略語自動抽取初探［C]／／全國第八屆計算語言學聯(lián)合學術(shù)會議（JSCL－2005）.

［7]武子英，鄭家恒.現(xiàn)代漢語縮略語自動識別的方法研究［J].計算機工程與設(shè)計，2007，28（16）：4052－4054.

［8]Zhifei Li，David Yarowsky.Unsupervised Translation Induction for Chinese Abbreviations using Monolingual Corpora［C]／／Proceedings of ACL－08，2008：425－433.

［9]Danushka Bollegala，Yutaka Matsuo，Mitsuru Ishizuka.Extracting key phrases to disambiguate personal name queries in web search［C]／／Proceedings of CLIIR'06Proceedings of the Workshop on How Can Computational Linguistics Improve Information Retrieval，2006：17－24.

［10]Vinay Bhat，Tim Oates，Vishal Shanbhag，et al.Finding aliases on the web using latent semantic analysis［J].Data ＆ Knowledge Engineering，2004，49：129－143.

［11]Winston H Hsu， Lyndon S Kennedy，Shih－Fu Chang.Video search reranking through random walk over document－level context graph［C]／／Proceedings of MULTIMEDIA'07Proceedings of the 15th international conference on multimedia，2007：971－980.