何正焱，王厚峰

(北京大學(xué) 計算語言學(xué)教育部重點實驗室，北京 100871)

1 引言

詞匯的獲取是語言學(xué)研究的一個重要內(nèi)容。傳統(tǒng)的詞典通常需要大量的人力編撰，同時具有覆蓋面小，實時性不強等缺點，不能為一些任務(wù)如命名實體識別提供足夠有效的信息。

在中文命名體識別中, 對識別人名、地名和機構(gòu)名的研究較為深入。使用的方法主要有基于規(guī)則的命名體識別和基于序列標(biāo)注的命名實體識別[1]。

商品和品牌名稱的識別較人名、地名的識別較難。人名有一定的規(guī)律可循，且用字比較固定；地名相對變化不大。品牌名稱的取名較隨意，規(guī)律性不強，并且有很多來自外文譯名，識別相對困難。

雖然命名實體在用字和上下文有一定規(guī)律，但命名實體識別通常是一個嚴(yán)重依賴人類知識的領(lǐng)域，在地名識別中經(jīng)常用做特征的地名詞典(gazetteer)[2]，機構(gòu)名詞典便是人類知識的體現(xiàn)。因此挖掘和收集同類別實例，例如，地名、機構(gòu)名和商品品牌名稱對該類別命名體識別有很大作用。本文考慮從網(wǎng)絡(luò)資源中收集和挖掘大量的同一類別的實體名稱，為中文命名實體識別提供足夠的領(lǐng)域信息。

近年來，利用網(wǎng)絡(luò)信息獲取大量同類別實例逐漸成為一個研究的熱點。如文獻(xiàn)[3]使用分布相似性抽取Web表格中的分類實例；文獻(xiàn)[4-5]介紹了使用基于二次優(yōu)化的半指導(dǎo)的 Adsorption 算法綜合多個信息源抽取類別實例的方法。這類方法的優(yōu)點是只利用少量需人工標(biāo)記的種子節(jié)點，利用網(wǎng)頁文本的表格或共享屬性等信息，獲取大量同類別實例，既解決了人工標(biāo)注的時間代價和覆蓋率小的問題，而又不損失準(zhǔn)確率。

百度百科是一個較大的中文知識庫，包含了大量的人物、地理、歷史、機構(gòu)、商業(yè)知識，為新詞條的發(fā)現(xiàn)提供了大量可供發(fā)覺的知識源。我們利用百度百科固有的“開放分類”和“相關(guān)詞條”信息構(gòu)造詞條間的相似度，使用少量的種子詞條，通過半指導(dǎo)的方法擴(kuò)充同一類別的詞條。同樣的方法可以用來獲取地名、機構(gòu)名、人名，或獲取更細(xì)致的分類下的詞條；本文選取商品品牌名稱作為抽取和評價的對象。

2 相關(guān)工作

在一個鏈接豐富的圖結(jié)構(gòu)上定義相似度是一個被深入研究的領(lǐng)域[6]。圖上相似度度量的方法主要有基于圖的如 personalize pagerank, 其基本思想是將pagerank中某個節(jié)點的重啟概率設(shè)置為1, 靜態(tài)分布后的排序就是其他節(jié)點對該節(jié)點的相似度。hitting time[7]定義為從節(jié)點i隨機游走在重新回到i之前到達(dá)j的期望步數(shù)，兩個節(jié)點越相似，期望步數(shù)越小。Katz 得分[8]定義為節(jié)點i到節(jié)點j的長度為k的路徑數(shù)的加權(quán)平均，加權(quán)系數(shù)隨距離增加指數(shù)下降，當(dāng)大多數(shù)權(quán)重集中在短路徑上時，katz得分類似于common neighbors。公共鄰節(jié)點(common neighbors)定義為兩個節(jié)點共有的鄰節(jié)點數(shù)， Adamic/Adar 得分[9]定義為公共鄰節(jié)點的加權(quán)和，每個公共鄰節(jié)點的權(quán)值是其度的對數(shù)值的倒數(shù)，其本質(zhì)是對公共鄰節(jié)點的改進(jìn)。

在異質(zhì)的圖網(wǎng)絡(luò)中，文獻(xiàn)[10]在文章—作者的異構(gòu)圖網(wǎng)絡(luò)中，利用作者間共同創(chuàng)作，文章間相互引用和作者和文章的寫作關(guān)系，耦合兩個pagerank的隨機游走過程，同時對作者和文章排序。文獻(xiàn)[11]提出了一種在任意異構(gòu)圖網(wǎng)絡(luò)上計算相似度的框架，節(jié)點間的邊含有類型和權(quán)值，權(quán)值可以通過在訓(xùn)練數(shù)據(jù)上的錯誤反向傳播學(xué)習(xí)，相似度的計算結(jié)合了隨機游走和重新排序(reranking)、隨機游走歷史(walk history)等信息，實際上相當(dāng)于在不同類型的邊上增加權(quán)重。

標(biāo)記傳播(label propagation)[13]是一種基于圖的半監(jiān)督的機器學(xué)習(xí)方法，相對于完全監(jiān)督的學(xué)習(xí)算法，在較少訓(xùn)練數(shù)據(jù)的情況下具有較好的性能。標(biāo)記傳播中關(guān)鍵在于定義好轉(zhuǎn)移矩陣T，其中

wij是ij的相似度,l和u為帶標(biāo)和不帶標(biāo)節(jié)點的個數(shù)，Tij可以理解為j傳遞給i的相似度的難易程度。

3 品牌名稱抽取

3.1 數(shù)據(jù)整理

我們從百度百科收集了約 130 萬個詞條，從每個詞條中提取出標(biāo)題、別名(同義詞跳轉(zhuǎn)等)、開放分類、相關(guān)詞條。開放分類不同于維基百科的層次分類，傾向于扁平結(jié)構(gòu)的標(biāo)簽(tag)，命名較隨意。因此雖然比較方便，卻不夠規(guī)范。例如，一個詞條可以是被標(biāo)記為分類“中國地理”，另一個詞條被標(biāo)記為“地理”，雖然他們在概念上很接近，分類標(biāo)記卻不能匹配。這就造成了分類上的數(shù)據(jù)稀疏問題。

3.2 相似度表示

在本文中我們考慮兩類信息“開放分類”(tag)和“相關(guān)詞條”，而不考慮文檔內(nèi)容、文檔結(jié)構(gòu)、文檔內(nèi)鏈接、文檔主題、作者協(xié)作編輯等信息。“相關(guān)詞條”可以看作是類型相同的詞條，具有相同“開放分類”的詞條也視作相同類型的詞條。130萬詞條中有約125萬包含至少一個開放分類，約29萬個包含至少一個相關(guān)詞條。

相關(guān)詞條間的等價關(guān)系相對準(zhǔn)確，例如，“北京大學(xué)”的相關(guān)詞條包含科研院所和高校，基本屬于同類實體；“舒膚佳”的相關(guān)詞條包含洗化用品品牌；但是這類信息相對較少。

“開放分類”信息較豐富，大多數(shù)的詞條都包含開放分類信息，但是開放分類信息通常具有用詞隨意的特點，并且百度百科的分類體系不像 wikipedia 具有層次結(jié)構(gòu)，而是類似于任意給定的標(biāo)簽。另一個現(xiàn)象是標(biāo)記省略[14]，例如，“張朝陽”的開放分類有“畫家，教師，企業(yè)家”，卻沒有“人物”。因此需要處理分類(tag)之間的相似關(guān)系。

本文提出了類似 simfusion 中的相似度表示，結(jié)合上述兩種信息，在給定少量種子的情況下，通過半指導(dǎo)的算法進(jìn)行品牌名稱的挖掘。

為了表述方便，定義一個詞條i的相關(guān)詞條的集合為R(i)，開放分類的集合為C(i)；如果詞條j∈R(i)，j是i的鄰節(jié)點。N(i)定義為鄰節(jié)點的集合。

兩個詞條節(jié)點的相似度定義為它們公共鄰節(jié)點的個數(shù)，

Le(i,j)=|N(i)∩N(j)|

詞條和分類之間的關(guān)系定義為詞條包含分類標(biāo)簽，

Lee(i,j)=1 ifj∈C(i)

分類與分類的相似度定義為它們在相同詞條中共現(xiàn)的次數(shù)，實際是分類節(jié)點之間的公共詞條節(jié)點個數(shù)。考慮到分類之間是具有層次結(jié)構(gòu)和包含關(guān)系的，因此分類的相似度傳播不是對稱的。例如，P(人物|企業(yè)家)P(企業(yè)家|人物)，由于“企業(yè)家”一定是“人物”，而“人物”未必是“企業(yè)家”，因此前者的概率要大于后者。

設(shè)同質(zhì)節(jié)點和異質(zhì)節(jié)點間相對重要性為α，總的相似度矩陣定義為：

3.3 基于圖的半指導(dǎo)學(xué)習(xí)算法

本文使用基于圖的半指導(dǎo)學(xué)習(xí)算法，標(biāo)記傳播(label propagation)[13]。其具體步驟如下：

1. 傳遞標(biāo)記,Y←TY；

2. 對行歸一化，?

3. 重置種子節(jié)點的概率分布Y。

T 為相似度矩陣，對列做歸一化，T(i,j)=P(j→i)可以理解為j傳遞標(biāo)記給i的難易程度。l、u分別為帶標(biāo)數(shù)據(jù)和不帶標(biāo)數(shù)據(jù)的個數(shù)，C 為類別個數(shù)，Y(l+u)*C是所有數(shù)據(jù)在類別上的概率分布。

在這里我們設(shè)T=L，如果不考慮節(jié)點的類別，實際上相當(dāng)于將所有帶標(biāo)節(jié)點的標(biāo)記不斷傳遞給不帶標(biāo)數(shù)據(jù)，最后按照概率由高到低排序，獲得與種子(認(rèn)為是品牌的詞條)的類別接近的詞條或分類。

3.4 種子詞條

我們手工設(shè)計了幾十個不同領(lǐng)域的品牌名稱(見表1)，包含日化、服裝、汽車、電子、家電、餐飲、化妝品、食品等領(lǐng)域。由于品牌名稱的定義廣泛，可能包含幾十種不同領(lǐng)域。每種領(lǐng)域內(nèi)部鏈接通常豐富，分類較一致；類別之間鏈接相對較少，分類也相對分散。因此每個領(lǐng)域我們選擇幾個具有代表性的詞條作為種子節(jié)點。

表1 品牌名稱的種子節(jié)點

4 實驗與分析

4.1 實驗設(shè)計和評價

我們從百度百科中收集了130萬個詞條進(jìn)行實驗。由于實驗的數(shù)據(jù)量很大，矩陣運算我們使用 scipy*http://www.scipy.org的稀疏矩陣。我們過濾掉了不包含相關(guān)詞條和開放分類的詞條，過濾掉頻率小于5的開放分類。利用 L 作為相似度矩陣，經(jīng)過標(biāo)記傳播算法迭代 1 000次，此時矩陣Y 每個元素的平均迭代誤差小于10-4，可以認(rèn)為基本收斂。

由于標(biāo)記傳播結(jié)果的概率分布 Y 表明了某個詞條和種子詞條的相似性，我們將120萬個詞條按概率由高到低排列，得到詞條列表。概率越大，排序越高，越可能是一個商品品牌名稱。

由于收集的詞條數(shù)目太多，我們還專門從 globrand*http://www.globrand.com/brandlisttxt/搜集了756個品牌名稱，其中 667 個在我們搜集的百科詞條中或別名中存在。我們利用這667個詞條在所有120萬個詞條中的 rank 值相加，相當(dāng)于在所有正例中采樣出 667 個樣本點，以采樣的 rank 均值作為所有正例的期望 rank 值。如果 rank 值越小，表明排名越靠前，模型效果越好。

定義 rank(e) 為詞條 e 在所有 120 萬個詞條中的排序值，表2 列出了不同α下 667 個樣本詞條的排序和。

表2 不同α下667個詞條的排序和

從表2可以看出，當(dāng)α→1時，逐漸忽略分類對詞條的影響，相當(dāng)于只考慮詞條間的相似性，而不考慮類別對詞條的影響，效果逐漸變差，這表明整合兩種信息能夠提高品牌名的 rank 值，產(chǎn)生更好的效果。

4.2 實驗結(jié)果分析

我們?nèi)斯z查了排序較高的非品牌詞條。我們將其分為幾類，見表3。某些是由于包含的信息太少，而唯一包含的信息又與正例很相關(guān)，例如，“板磚”，“掏耳勺”僅僅包含一個分類“日?！保叭粘！迸c很多洗化品牌相關(guān)；“苦事”的唯一一個相關(guān)詞條“樂事”是品牌；另一些如“HR”、“名表”等雖然有多個分類和相關(guān)詞條，但是僅有少數(shù)和品牌相關(guān)，即存在不一致性和多義性。如何建模這兩種情況是我們將要考慮的方向。

表3 排序較高的非品牌詞條

表4 排序較低的品牌名稱。

在667個樣本中，前450個排序都在10 000以內(nèi)。對667個品牌名稱 rank 值較低的樣例(表4)進(jìn)行分析，我們可以發(fā)現(xiàn)多數(shù)存在歧義和多義詞現(xiàn)象，因此這類詞條只在特定上下文下才是品牌名稱(例如，白云山, 見表4)。另外一些詞條的“開放分類”或“相關(guān)詞條”提供的信息太少，或使用了很少使用的分類名稱；如何整合更多的文檔結(jié)構(gòu)和內(nèi)容信息是另一個將要研究的方向。

5 結(jié)論

我們提出了一種基于圖的半監(jiān)督學(xué)習(xí)算法，從大量百科知識庫中抽取品牌名稱。結(jié)合百度百科的相關(guān)詞條和開放分類兩種鏈接關(guān)系，定義了結(jié)合兩種關(guān)系的相似度表示方法，給定少量品牌領(lǐng)域的種子樣例，挖掘出更多的品牌名稱。實驗中我們僅利用“開放分類”和“相關(guān)詞條”兩類信息，而沒有利用諸如文檔內(nèi)容、文檔結(jié)構(gòu)、文檔內(nèi)鏈接、文檔主題、作者協(xié)作編輯等信息，取得了較好地效果。使用我們的方法，可以在指定任意領(lǐng)域(如機構(gòu)名作為種子)的少量實例的情況下，獲取更多的該領(lǐng)域相關(guān)的概念。抽取出的詞表可以用在命名實體識別領(lǐng)域。

下一步，我們將進(jìn)一步利用和融合更多信息(如文檔內(nèi)容、文檔內(nèi)鏈接、文檔模板結(jié)構(gòu)等)，并提出更合理和可行的評價方法。

[1] 周俊生，戴新宇，尹存燕，等. 基于層疊條件隨機場模型的中文機構(gòu)名自動識別[J]. 電子學(xué)報， 2006： 34(5)：804-809.

[2] David Nadeau， Satoshi Sekine. A survey of named entity recognition and classification[J].Lingvisticae Investigationes, 2007.

[3] Van Durme, B.， Pas ca, M.. Finding cars, goddesses and enzymes: Parametrizable acquisition of labeled instances for open-domain information extraction[C]//Proceedings Twenty-Third AAAI Conference on Artificial Intelligence.2008.

[4] Talukdar P. P., Reisinger J., Pasca,M., et al. Weakly-Supervised Acquisition of Labeled Class Instances using Graph Random Walks[C]//Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, 2008, 581-589.

[5] Talukdar P. P., Pereira, F. Experiments in graph-based semi-supervised learning methods for class-instance acquisition[C]//Proceedings of 48th Annual Meeting of the Association for Computational Linguistics (ACL).2010.

[6] Purnamrita Sarkar. Tractable Algorithms for Proximity Search on Large Graphs[D]. PhD thesis, Carnegie Mellon University, 2010.

[7] D. Aldous, J. Fill. Reversible Markov Chains and Random Walks on Graphs[M]. Book in preparation.

[8] Leo Katz. A new status index derived from sociometric analysis[C]. Psychometrika, 1953.

[9] Lada A. Adamic, Eytan Adar. Friends and neighbors on the web[J]. Social Networks, 2003.

[10] Ding Zhou, Sergey A. Orshanskiy, Hongyuan Zha, and C. Lee Giles. Co-ranking authors and documents in a heterogeneous network[C]//Data Mining, IEEE International Conference on, 2007:739-744.

[11] Einat Minkov. Adaptive Graph Walk Based Similarity Measures in Entity-Relation Graphs[D].PhD thesis, Carnegie Mellon University, 2008.

[12] Wensi Xi, Edward A. Fox, Weiguo Fan, et al.. Simfusion: measuring similarity using unified relationship matrix[C]//Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’05, New York, NY, USA, 2005: 130-137.

[13] Xiaojin Zhu, Zoubin Ghahramani. Learning from labeled and unlabeled data with label Propagation[R]. Technical report, 2002.

[14] Xiance Si, Zhiyuan Liu, Maosong Sun. Explore the structure of social tags by sub-sumption relations[C]//Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), Beijing, China, August 2010:1011-1019.