何正焱，王厚峰

(北京大學(xué) 計(jì)算語(yǔ)言學(xué)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871)

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 品牌名稱抽取

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

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

3.2 相似度表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 對(duì)行歸一化，?

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

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

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

3.4 種子詞條

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)和評(píng)價(jià)

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

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

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

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

表2 不同α下667個(gè)詞條的排序和

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

5 結(jié)論

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

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

[1] 周俊生，戴新宇，尹存燕，等. 基于層疊條件隨機(jī)場(chǎng)模型的中文機(jī)構(gòu)名自動(dòng)識(shí)別[J]. 電子學(xué)報(bào)， 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.