基于用戶查詢日志的命名實體挖掘

翟海軍，郭嘉豐，王小磊，許洪波

(1. 中國科學技術大學 計算機學院，安徽 合肥 230027； 2. 中國科學院 計算技術研究所，北京 100190)

1 引言

近年來，數據挖掘領域的一個發展趨勢是對大規模數據信息抽取技術的研究，盡管這些研究工作在抽取的目標信息、底層算法以及使用工具上可能各有不同。其中，用戶查詢日志作為一類富含大眾智慧的海量數據資源，成為了數據挖掘領域廣泛關注的研究對象。從查詢日志中獲取的各種知識不僅可以為信息檢索領域所用，還可以成為機器翻譯、自然語言處理等領域的基礎。本文研究了針對大規模查詢日志中豐富的命名實體的挖掘技術。對查詢日志中命名實體的挖掘在垂直搜索，查詢推薦，以及Web檢索等方面都有廣泛的應用前景。例如用戶提交了查詢“the family stone”，基于命名實體挖掘的結果可以知道“the family stone”是指一部電影，通過將該查詢提交到影視相關的垂直搜索中，返回的查詢結果可以更好地滿足用戶的查詢需求。

以往對命名實體識別的研究主要集中在文本領域中[1-3]，至今已有近20年的發展歷史。它作為自然語言處理領域的一項重要技術，已經取得了很多成果。早期命名實體識別的技術通常依賴于人工指定規則。近年來，機器學習的方法應用于命名實體識別，包括了監督學習[1]，半監督學習[2]和無監督學習[3]。

與文本領域中的命名實體識別不同，用戶查詢通常都很簡短(往往只有2～3個詞)，并且不具備嚴格的語法，語義很模糊，因此文本領域中的命名實體識別技術不能直接有效地應用到查詢上。這給基于用戶查詢的命名實體挖掘的研究工作提出了新的挑戰。已有的研究表明用戶查詢數據具有一些獨有的分布特性，分析這些特性有助于我們從用戶查詢日志中挖掘命名實體。Pasca[4]提出了一種利用查詢模板從用戶查詢日志中挖掘命名實體的確定性方法(Determ)。作者將查詢分解為兩部分，某個類別的實例(即命名實體)和查詢模板(即查詢上下文)。在此基礎上，通過人工給定目標類別下的一組種子(命名實體)作為指導，估計目標類別下的查詢模板的分布，從用戶查詢日志中挖掘目標類別下的新命名實體。然而該工作的一個主要的局限在于他們的方法是確定性的，只有當種子實體僅屬于單個語義類別時才能取得好的結果。而實際中，命名實體往往可能從屬于多個語義類別。比如，命名實體“harry potter”，在用戶查詢“harry potter poster”中指得是“harry potter”這部電影；而在用戶查詢“harry potter author”中指得是“harry potter”這本書。這樣的類別模糊性使得Determ方法對實體抽取的性能受到了很大影響。

因此，本文針對命名實體的類別模糊性，提出了一個基于弱指導話題模型的命名實體挖掘框架。和Determ方法相似，該框架也利用實體的分布相似性，基于種子實體來從大規模查詢日志數據中挖掘多個語義類別的命名實體。不同的是我們的方法通過引入一個弱指導的生成概率模型來學習各個類別的查詢模板分布，很好地解決了命名實體的類別模糊性。這里所使用的話題模型，是關聯話題模型CTM(Correlated Topic Model)的一個衍生，稱為弱指導關聯話題模型WSCTM(Weak-Supervised Correlated Topic Model)。但是，不同于使用無指導學習的CTM模型，WSCTM 可以利用少量人工標注的命名實體的話題信息來指導學習，從而確保結果話題與任務所關注的話題一一對齊。通過對該話題模型的使用，我們可以更加準確地估計目標類別下查詢模板的分布，從而更好地挖掘命名實體。

在文章最后的實驗中，我們收集了來自微軟Live Search的1 500萬條真實用戶查詢數據，通過人工標注了少量種子命名實體，來訓練弱指導話題模型，實驗結果表明我們的方法在實體挖掘性能上顯著優于已有的方法。

2 命名實體挖掘框架

這一部分介紹基于弱指導話題模型的命名實體挖掘框架。給定一組目標類別和類別下一組作為種子的命名實體，命名實體挖掘的目標是從用戶查詢日志中大規模挖掘目標類別相關的新命名實體，無需任何其他領域相關知識。我們的命名實體挖掘框架可以分為三個階段：

(1) 首先選擇一組命名實體作為種子，并且對每個種子指派類別?？紤]到命名實體往往從屬于多個類別，因此這里的種子命名實體可能同時被指派一個或多個類別，比如命名實體“American pie”同時標注了“Movie”和“Music”兩個類別。這里，我們對命名實體進行標注，而不是針對單個的用戶查詢，并且只需標注少量的種子命名實體，確保了標注工作可以簡單進行。

(2) 針對每個種子命名實體獲取相應描述文檔，然后采用弱指導話題模型來學習話題模型。具體來說，對每個種子命名實體，我們通過遍歷整個查詢日志，收集所有包含該命名實體的用戶查詢。類似于Determ方法，這里將查詢分解為兩部分，命名實體和查詢模板。例如命名實體“harry portter”，對于查詢“harry portter poster”，相應的查詢模板是“# poster”。通過組合該命名實體的所有查詢模板，得到該命名實體的描述文檔。我們可以像普通文檔一樣來看待描述文檔，區別在于這里查詢模板被當成文檔中的“詞”。例如我們在查詢日志中找到兩個包含命名實體“harry portter”的查詢，分別是“harry potter review”和“harry potter author”，則相應的描述文檔包含兩個“詞”，分別是“# review”和“# author”。這樣，對所有種子命名實體，通過遍歷整個查詢日志，匹配得到相應的描述文檔集合，作為我們的訓練集。對訓練集中的每個描述文檔，將其相對應的命名實體的標注信息作為該描述文檔的標注信息，然后采用我們提出的弱指導話題模型來學習，這樣我們可以得到每個目標類別中查詢模版的概率分布的估計。

(3) 獲取候選命名實體，并采用分布相似度計算來排序候選命名實體。將第二階段中所獲取的所有種子命名實體的查詢模板作為目標串，遍歷整個查詢日志通過匹配獲取候選命名實體及相應的描述文檔。結合前面學習得到的每個目標類別中查詢模版的概率分布的估計，通過計算目標類別和候選命名實體的描述文檔間的相似度排序候選命名實體，來挖掘目標類別下的新命名實體。

上面我們詳細描述了基于弱指導話題模型的命名實體挖掘框架，該框架中通過弱指導的話題模型來學習各個類別的查詢模板分布，很好地解決了命名實體的類別模糊性，同時采用分布相似度計算來挖掘目標類別的新命名實體。整個框架簡潔有效，其中關鍵部分是弱指導話題模型。

3 話題模型

這一部分，我們將詳細地介紹弱指導話題模型，該話題模型是已有關聯話題模型(CTM)的擴展。我們在前面已提到，在命名實體挖掘任務中，類別(即話題)是預先給定，例如“Book”、“Music”等等。如何讓話題模型中學習得到的結果話題(即類別)與任務所關注的話題一一對齊是首要解決的問題。然而，已有的CTM是一個隱式話題模型，不能確保結果話題和預先給定話題之間對齊。因此，我們提出了弱指導關聯話題模型(WSCTM)，通過利用種子命名實體的標注信息指導學習，有效地解決話題對齊的問題。

3.1 關聯話題模型

我們首先簡要回顧已有的關聯話題模型。話題模型是一種生成概率模型[5-7]，該模型假定每篇文檔中的詞都是由一組話題混合生成，每個話題都是詞空間上的一個分布。CTM是在早期話題模型LDA[7]的基礎上提出來。相對于LDA模型，CTM可以獲取不同話題之間的關聯關系，更好地擬合文檔集合。

給定由M個文檔組成的集合D={ω1,...,ωM}，這組文檔共享K個話題，并且每個文檔可以用包含N個詞的序列來表示ω={ω1,...,ωN}。在CTM中，文檔集合D中每篇文檔ω的生成過程如下：

(1) Drawη～Nk(μ,Σ)，

(2) For each of theNwordsωn，

(b) Draw wordωn～Multinomial(βzn),βis ak×Vmatrix。

整個過程的概率圖模型如圖1所示。給定參數μ，Σ和β，文檔的生成概率如下：

(1)

最后，將所有文檔的生成概率相乘，我們可以得到文檔集合的生成概率如下：

(2)

圖1 CTM的圖模型表示

3.2 弱指導關聯話題模型

在本文的命名實體挖掘任務中，每個種子命名實體的描述文檔都包含一個或多個類別標簽。這些信息可以很好地指導算法的學習過程。WSCTM采用弱指導的方式，將已有的標注信息作為修正項，添加到目標函數來對齊結果話題和任務所關注的話題。

這里我們采用向量y={y1,…,yK}來表示每篇文檔的標注信息，其中K表示話題數，當文檔被指派了第i話題時，yi的取值為1，否則為0。我們通過修正已有的CTM，提出一個基于弱指導的關聯話題模型(WSCTM)，來建模給定了類別標簽的文檔集合。新的文檔生成目標函數定義如下：

O(w,y)=L(w)+ρR(y)

(3)

其中ρ是修正參數，L(w)是文檔的對數似然L(w)=logp(w|μ,Σ,β) 和定義在文檔標簽上的修正項R(y)：

(4)

(5)

在公式(5)中，我們通過修正已有的CTM，給出了WSCTM的目標函數。在該目標函數中L(D)衡量話題模型生成數據的概率，R(Y)約束每篇文檔的話題分布集中在相應的標注話題上。修正參數ρ指示文檔遵循文檔標注的程度。當ρ等于0，WSCTM退化為CTM。

3.3 參數推導和估計

這一節我們詳細地介紹WSCTM的參數估計。WSCTM通過最大化目標函數進行參數估計。給定文檔w和模型{μ,Σ,β1∶K}，每個文檔隱變量的后驗分布是

(6)

如同CTM，該公式難于計算。因此，我們采用變分期望最大化(Variational Expectation-Maximization)方法來估計參數。

我們采用Jensen不等式來計算文檔生成目標函數的下界：

(7)

其中的期望基于隱變量的變分分布q來求取，H(q)表示分布的熵。

(8)

在M(最大化)步中，我們最大化公式(5)來求取模型參數μ,Σ和β。參數的更新公式如下：

上面我們詳細地介紹了WSCTM的學習過程。我們可以將訓練好的WSCTM用于預測新文檔的話題分布。預測的程序與CTM的預測程序相同，限于篇幅這里不再贅敘。

4 實驗結果及分析

我們收集了來自微軟Live Search的真實用戶查詢數據，通過實驗來驗證我們方法的有效性。實驗中，我們與已有的Determ方法做了比較。Determ方法的基本思想，假定每個命名實體只屬于一個類別，通過統計每個類別下所有種子命名實體的查詢模板的分布，作為該類別的查詢模板的真實分布的估計，通過計算候選命名實體的描述文檔與類別查詢模型的估計分布之間的相似度來排序候選命名實體。在這里，WSCTM的修正參數ρ設置為1。

4.1 實驗數據

本文所采用的實驗數據集包含了1 500萬條真實用戶查詢數據，這些查詢數據是從微軟Live Search隨機采樣得到。該數據集包含6 623 961個不同的用戶查詢，用戶查詢的平均長度為2.423個英文單詞。這里，用戶查詢被認為是互相獨立的，不考慮它們是否來自同一用戶。

本實驗中，我們共考慮了10個不同語義類別。這樣的實驗設置，綜合考慮了不同粒度的類別，其中包括命名實體識別和挖掘中經常會涉及的粒度較粗的類別，比如“Location”，“Person”和“Food”等，也引入了一些粒度相對較細的類別，比如來自“Entertainment”的“Movie”，“Music”和“Game”。對于這些類別，我們從不同的網站收集了150個種子命名實體，這些網站包括有Amazon(www.amazon.com)，GameSpot(www.gamespot.com)和Lyrics(www.lyrics.com)等等。我們召集了3個研究生來標注這些命名實體，對標注不一致的命名實體，采用投票的方式來確定命名實體最終的標簽(多于2個人同時標注了的標簽被接受)。其中有31個種子命名實體同時被標注了多個類別(占據總數的20.7%)，比如“lord of the rings”同時屬于“Movie”和“Game”。

每個類別中都有標注多類別的命名實體，多類別命名實體所占比例隨類別而不同(≥12.5%)，其中類別“Book”中多類別命名實體所占比率最大(60.6%)，類別“Software”中多類別命名實體所占比例最少(12.5%)。此外，類別間的命名實體的重疊率(重名命名實體所占比率)各不相同，其中“Movie”和“Book”，“Movie”和“Game”兩對類別的重疊率最高(≥24%)。這符合實際中，電影經常由同名書籍改編而來，而后又改編制作出同名游戲的現象。比如電影“Harry Potter”就是由同名書籍改編拍攝的，而后又通過改編制作出了同名游戲。

4.2 評價方法

為了確保評價的公平性，將由本文的方法得到的結果和Determ方法的結果，按類別各取前250個相混合，然后通過人工評判各類別下的結果命名實體(對評價人員隱藏了結果的來源)，對屬于該類別的結果命名實體判定為true，否則判定為false。另外，為了確保結果的準確性，我們同時召集了3個研究生來做評價，對評價結果不一致的命名實體，采用投票的方式來確定命名實體最終的評價結果(多于2個人同時認同的結果將被接受)?；谏鲜鋈斯ぴu價后的結果數據，我們采用前N個結果的準確率P@N來度量在每個類別下各算法的性能，P@N表示在結果列表的前N個結果中人工判斷為true的實例所占比率。

4.3 實驗結果及其分析

采用上面所描述的實驗數據和度量，將我們的方法(Our)與Determ方法相比較。實驗結果如表1所示。從表1可以看出，在所有類別下，我們方法的準確率P@N都優于(或等于)Determ方法，并且我們方法的P@250平均準確率(0.912)相對Determ方法的P@250平均準確率(0.799)顯著提高了14.1%(統計顯著性P<0.01)。此外，Determ方法的準確率P@N隨結果數N的增加急劇下降，而我們的方法所產生的結果相對要穩定很多。需要特別指出的是，對于類別“Location”和“Company”，兩個方法所得到的結果都非常好(我們方法的結果略好)，這可能是因為類別“Location”和“Company”下命名實體對應的查詢上下文非常豐富，而且這些查詢上下文對類別的指示作用也很明確，例如類別“Location”下的查詢模板“# daily news”、“map of #”等等。

這里我們進一步分析了我們的方法能夠取得更好的挖掘效果的原因，這主要是由于我們的方法通過考慮命名實體的多類別特性，更加準確地估計出各目標類別的查詢模板分布。表2中給出了我們的方法和Determ方法所估計的各類別下前5個查詢模板(根據各類別下查詢模板出現的概率從大到小取前5個，限于篇幅這里只取了前5個)。從表2可以很直觀地看出，Determ方法中，各類別下的前5個查詢模板中往往混雜有其它類別的查詢模板，比如類別“Book”的第2個模板“# movie”。這是因為Determ方法忽略了命名實體的類別歧義性，將同時屬于類別“Book”與“Movie”的命名實體對應的查詢上下文都強行歸于“Book”類別下；與之相反，在我們的方法中，由于考慮命名實體的多類別特性，使得各類別下的查詢模板分布學習得更加準確。

5 結論

查詢日志是大量用戶長期查詢行為的記錄，其中包含豐富的知識。本文研究了對大規模查詢日志中命名實體的挖掘技術。與文本領域的命名實體挖掘不同，用戶查詢通常很簡短，并且含有大量的噪音。因此文本領域中的命名實體識別技術不能直接有效地應用到查詢上。這給基于用戶查詢的命名實體挖掘的研究提出了極大的挑戰。但是，用戶查詢數據具有一些獨有的分布特性。并且現實中，命名實體往往可能從屬于多個類別。本文提出了一個弱指導話題模型的命名實體挖掘框架，該框架下通過一個弱指導的生成概率模型來學習各個類別的查詢模板分布，很好地解決了命名實體的類別模糊性，同時結合實體的分布相似性，來提高挖掘的有效性。本文最后通過實驗驗證了我們方法的優越性。下一步我們期望探索挖掘得到的大量命名實體在檢索方面的應用。

表1 各類別下準確率P@N對比

表2 各類別下前5個查詢模板對比

[1] Borthwick Andrew，Sterling J.，Agichtein E，Grishman R.. NYU: Description of the MENE Named Entity System as used in MUC-7[C]//Proc. Seventh Message Understanding Conference. 1998.

[2] Cucchiarelli Alessandro，Velardi P. Unsupervised Named Entity Recognition Using Syntactic and Semantic Contextual Evidence[J]. Computational Linguistics，2001，27(1)：123-131。

[3] Evans Richard. A Framework for Named Entity Recognition in the Open Domain[C]// Proc. Recent Advances in Natural Language Processing. 2003.

[5] D. M. Blei and J. D. Lafferty. Correlated topic models[C]// Proceedings of the 23rd International Conference on Machine Learning, 2006：113-120.

[6] T. Hofmann. Probabilistic latent semantic indexing[C]// SIGIR '99: Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, 1999: 50-57.

[7] D. M. Blei，A. Y. Ng and M. I. Jordan. Latent dirichlet allocation[J]. Journal of Machine Learning Research，2003， 3(1)：993-1022.