結合語境與布朗聚類特征的上下位關系驗證

張志昌,陳松毅,劉 鑫,馬慧芳

(西北師范大學計算機科學與工程學院,蘭州730070)

結合語境與布朗聚類特征的上下位關系驗證

張志昌,陳松毅,劉 鑫,馬慧芳

(西北師范大學計算機科學與工程學院,蘭州730070)

對海量文本語料進行上下位語義關系自動抽取是自然語言處理的重要內容,利用簡單模式匹配方法抽取得到候選上下位關系后,對其進行驗證過濾是難點問題。為此,分別通過對詞匯語境相似度與布朗聚類相似度計算,提出一種結合語境相似度和布朗聚類相似度特征對候選下位詞集合進行聚類的上下位關系驗證方法。通過對少量已標注訓練語料的語境相似度和布朗聚類相似度進行計算,得到驗證模型和2種相似度的結合權重系數。該方法無需借助現有的詞匯關系詞典和知識庫,可對上下位關系抽取結果進行有效過濾。在CCF NLP&2012詞匯語義關系評測語料上進行實驗,結果表明,與模式匹配和上下文比較等方法相比,該方法可使F值指標得到明顯提升。

上下位關系;語境相似度;布朗聚類相似度;點互信息;模式匹配;聚類驗證

1 概述

詞匯上下位關系是指詞匯概念之間在語義上的從屬關系,即給定概念A和B,若A的外延包含B的外延,則認為A和B具有上下位關系,即A是B的上位概念,B是A的下位概念,這種關系也被稱作“is-a”關系,記作ISA(B,A)。例如,“中國是一個國家”,則“國家”是“中國”的上位概念,即ISA(中國,國家)。這種語義上的詞匯上下位關系在本體知識庫構建、機器翻譯、自動問答等自然語言領域的相關應用中起著重要的作用。自文獻[1]開始,已有很多關于上下位關系自動抽取的研究。但多數抽取方法都面臨一個重要問題:如何驗證抽取到的一組候選上下位關系詞匯實例是否真正屬于同一個語義類,即候選上下位關系的驗證問題[2-3]。

本文提出一種基于統計并且無指導的詞匯上下位關系驗證方法。利用簡單的模式匹配方法獲得候選的詞匯上下文關系后,通過計算詞匯語境相似度和布朗聚類的相似度,將兩者進行結合作為新的相似度特征,通過對上位詞的全部候選下位詞進行K-means聚類來對候選上下位關系進行驗證和選擇。

2 相關研究

對已有的研究成果進行總結,可將詞匯上下位關系自動抽取的方法大致分為以下3類:

(1)基于模式匹配的方法

該方法以文獻[1]的研究為代表,主要根據特定語言的使用習慣,將人工設置的多種匹配模式在大語料中進行匹配來獲取上下位關系。例如:設置模式形如“Bis a A”,“Bis a kind ofA”,“B,Cand otherA”等(中文模式如:“B是一個/類/種A”等)。該方法有不同的變體,如文獻[4]使用模式自舉方法,而文獻[5]使用了詞性模板。該方法實現簡單,并且模式的形式符合語言使用習慣,容易理解。但由于模式是由人來構造,模式的形式單一,只能覆蓋部分詞匯的表達形式,因此存在稀疏性問題[6],導致系統的準確率和召回率相對偏低。

(2)基于語義詞典、知識庫的方法

目前廣泛使用的語義詞典、在線百科等知識庫中都含有同義、反義、上下位關系等語義信息(英文有WordNet[7],Wikipedia,Freebase等,中文有HowNet、百度百科、互動百科等)。許多語義關系的抽取研究借助于此類語義詞典、知識庫所包含的語義信息[6,8]。但由于此類語義詞典的構建多由人工參與,耗時耗力,因此往往其知識覆蓋范圍非常有限,且實時性較弱,無法及時體現最新的語言現象。

(3)基于統計的方法

這類方法基于統計思想,通過機器學習方法構建語義模型,應用分類等數據挖掘技術計算不同概念之間的相關程度來獲取上下位關系。文獻[9]運用依存句法構建語義模型,通過SVM進行分類來抽取上下位關系,文獻[10]運用了一種非線性概率模型,文獻[11]構建了概念空間,并運用了潛在語義分析。該類方法越來越普遍地使用在語義關系抽取任務中。該類方法普遍基于以下假設:語義相似的概念出現在相似的上下文之中。

針對已有方法的特點和不足,本文提出一種基于統計并且無指導的詞匯上下位關系驗證方法,該方法和已有方法的區別在于:(1)利用無指導的聚類方法對上下位關系進行驗證選擇;(2)將聚類所用的相似度特征在傳統的語境相似度的基礎上結合了詞匯的布朗聚類相似度。

3 候選上下位關系的獲取

借鑒文獻[12]方法,本文對候選上下位關系的獲取方法進行了擴展,其實質是一種改良的基于模式匹配的方法。根據中文語法特點構造表1中的模式,然后利用搜索引擎索抽取大量能夠匹配該模式的上下位候選上下位關系詞對。在表1中,模式1為基本模式,模式2～模式4為模式1的擴展模式,即通過擴展模式對基本模式獲得的抽取結果進行自舉擴展。

表1 上下位關系抽取模式

抽取算法如下:

輸入上位詞C,閾值R(本文設R=5)

輸出與C對應的實例集合IS=[I1,I2,…,In]

步驟1通過模式1在搜索引擎中進行查詢獲得支持句。從而獲得候選上下位關系詞對,放入集合IS?。

步驟2對于集合IS?的每個元素,分別根據模式2～模式4構造相應的查詢字符串,獲得相應的擴展支持句,并從中獲得擴展后的上下位關系候選詞對。

步驟3統計擴展詞的出現次數,將出現次數大于閾值R次的詞語放入集合IS中。

步驟4重復步驟2～步驟3,直到擴展詞數量不再明顯增加。

通過抽取算法可以獲得一定數量的候選上下位關系。通過實驗可知,對獲取結果進行自舉擴展對召回率有較大的提高,但同時又增加了錯誤結果的數量,準確率大大降低。因此,為有效提高準確率,本文提出一種基于語境特征與布朗聚類相結合的上下位關系驗證方法,用于對模式匹配的結果進行驗證過濾。

4 語境與布朗聚類特征結合的關系驗證

將詞匯的語境相似度特征和布朗聚類相似度特征結合起來,通過聚類進行詞匯的上下位關系驗證,也是基于分布假設,即語義相似的概念出現在相似的上下文中。根據聚類理論:同一類別中的對象相似度較高,而不同類別中的對象相似度較小。同理,在候選上下位關系中,具有相同類別候選詞的相似度較高,反之,相似度較低。

基于上述分析,本文將K-means聚類作為候選上下位關系的驗證方法。在聚類過程中所使用的相似度分別為語境相似度、布朗聚類相似度和兩者加權調和平均結合之后的相似度。

4.1 語境相似度特征

每個實體詞在自然文本中都有各自的使用環境,即語境。語境即言語環境,分為狹義和廣義2種。狹義的語境是指書面語的上下文或口語的前言后語所形成的言語環境。后者則是指言語表達時的具體環境(既可指具體場合、也可指社會環境)。本文使用的詞匯語境是指前者,即自然文本中的上下文信息。例如,“國家”一詞常常出現在“舉辦”、“經濟”等語境詞之中,“中國”和“國家”有著相似的語境,但“中國人”跟“國家”的語境就有很大區別。如果可以獲得概念的語境信息,就可以利用該信息對相應的上下位關系進行驗證,從而過濾錯誤結果。

鑒于點互信息(Point Mutual Information,PMI)能較好地反映詞匯與特征之間的共現關系,本文采用點互信息來選擇和衡量詞的語境特征及其權重,對詞的語境信息進行量化建模。詞匯wi與上下文語境特征fj之間的點互信息定義為:

其中,P(wi,fj)是詞wi和上下文語境特征fj的共現概率;P(wi)和P(fj)分別是詞的出現概率,它們均可從語料庫中用最大似然估計得到。

首先,通過點互信息值構造出目標詞的語境特征詞集合。本文通過對大量文本語料進行統計,取得與目標詞互信息值最大的前20個詞,并將這些詞作為目標詞的語境特征詞,記作CF(T)。CF(T)是一個詞集合,例如,“體育運動”的語境特征詞如表2所示。

表2 “體育運動”的語境特征詞集合

根據向量空間模型可以構造該詞的語境特征向量Tcf=(w1,t,w2,t,…,wN,t),其中,權重值wN,t為在目標詞和第n維上的語境特征詞之間的點互信息值;N為詞匯表中的詞量。本文通過計算2個語境特征向量的余弦相似度值來得到兩詞之間的語境相似度,即:

4.2 布朗聚類相似度特征

聚類方法是數據挖掘中通過特征進行無監督分類的有效方法。本文首先使用布朗聚類計算出各個候選下位詞的前綴編碼[13],得到候選詞間布朗相似度,然后使用K-Means聚類方法進行多次聚類,通過計算上位詞與每個候選詞子集的距離,選擇距離更近的一個,即可達到上下位關系驗證的目的。

布朗聚類算法是文獻[13]提出的一種基于純文本的以詞為處理單位的聚類算法。該方法用于分析未標注的大語料詞匯聚合分布情況,并根據詞分布相似度對詞進行聚類。

定義分類器C,C:V→{1,2,…,k}表示C將V中的詞劃分為k類,其中,V為詞匯表。

布朗聚類模型定義如下:

其中,w1,w2,…,wn是自然句詞序列;e表示在wi的分類下產生詞wi的概率;q表示wi-1出現后接wi的概率,即:

根據以上定義,將分類器評價函數定義為:

其中,G為常數。

通過對語料進行布朗聚類分析,可得每個詞的前綴編碼(記為M(word)),在此基礎上可構造一顆分類樹。根據分布假設可以知,具有相似前綴碼的詞的語義相似度較高,即分享同一個節點的詞的語義相似度較高。所以,對于每一個從模式支持句中獲得的候選上下位關系候選,本文使用候選詞之間的布朗聚類相似度SimBrown(A,B)進行驗證過濾。

定義A,B節點距離為NodeDis(A,B):

其中,BLSS(M(A),M(B))表示A和B前綴碼從根開始的最長連續公共子序列;Len(S)代表序列長度。

通過節點距離,本文定義兩節點布朗聚類相似度為:

4.3 語境和布朗聚類結合的相似度特征

除了利用語境相似度(SimCF)和布朗聚類相似度(SimBrown)作為K-means聚類的相似度特征,對候選上下位關系進行聚類驗證之外,本文提出一種基于2種相似度相結合的新的相似度特征計算方法。該方法采用加權調和平均的方式結合了語境、布朗2種相似度。具體的結合公式如下:

其中,α是結合系數。

通過式(9)計算出的候選上下位關系相似度值越高,則目標候選上下位關系屬于正確關系的概率也就越大。所以,參數α優化過程的實質為使得∑AllSimilarity(A,B)最大化的過程。通過訓練可知,α=0.595時獲得最佳效果。

以結合相似度為例,選擇上位詞“主食”和其候選下位詞,如表3所示。

表3 “主食”的候選下位詞集合

將候選下位詞集合中的所有詞基于式(9)所得的相似度進行K-means聚類(本文取K=2),可得到如圖1所示的散點圖,該圖體現點間距離的聚合關系,其坐標無實義。

圖1 “主食”的候選下位詞集合聚類散點圖

從圖1可得候選詞集合的2個子集。定義上位詞與候選詞子集距離如下:

其中,[B1,B2,…,Bn]是上位詞A的下位詞集合。

通過式(10)計算上位詞與每個候選詞子集的距離,選擇距離更近的一個,并對結果進行多次迭代過濾,即可達到候選上下位關系驗證過濾的目的。

5 實驗結果與分析

5.1 評測語料與評價標準

本文采用CCF NLP&CC 2012語義關系識別標準評測集作為詞匯上下位關系驗證方法的訓練和評測語料。該評測集包含256個上位詞和分別與之對應的5 718個下位詞。評測集的數據來源包括普通詞典、百科詞條、敘詞表等多種資源。詞匯的詞性包括普通名詞和專有名詞。評測集格式如表4所示。

表4 CCF NLP&CC 2012標準評測集中“廟號”的下位詞

本文將評測集等分為訓練集和測試集2個部分,每部分各有128個上位詞,分別用于結合權重系數α的確定訓練和方法的驗證測試。

評測方法使用CCF NLP&CC 2012語義關系識別中的評測方法[14]。對抽取到的候選中文詞匯上下位關系進行驗證過濾,然后對結果采用準確率(Precision)、召回率(Recall)和F值(F-measure)3個評測指標進行評價。

5.2 權重系數α的確定

單個上位詞與其對應下位詞相似度計算公式如下:

其中,Qk為k個詞相似度。

在計算出訓練集中所有128個上位詞與它們分別對應的下位詞的語境特征相似度、布朗聚類相似度之后,可計算出訓練集中所有上位詞與其對應下位詞的結合相似度值,公式如下:

根據訓練集計算出所有的SimCF(Ak,Bk,i)和SimBrown(Ak,Bk,i)之后,式(12)就成為了關于α的函數。依照上文分析,為使Q128最大,對該函數求導,且令Q’=0,所獲得的極值點,即最優的α值:

令Xik=SimCF(Ak,Bik),Yik=SimBrown(Ak,Bik),則有:

根據訓練集數據(128個上位詞),計算可得α= 0.595。

5.3 結果分析

綜合上述方法,對CCF NLP&CC 2012語義關系識別評測集中的上位詞(即測試集中的128個詞)做上下位關系抽取。本文使用搜狗實驗室2012年發布的全網新聞數據和搜狐新聞數據(http://www. sogou.com/labs/resources.html)作為下位詞抽取的主要數據來源,以訓練語境特征模型和布朗聚類模型。該數據集為2012年6月-2012年7月國內、國際、體育、社會、娛樂等18個頻道的新聞數據,共包含2 623 521篇文檔。

首先用模式匹配和模式自舉的方法抽取下位詞,對獲得的候選上下位關系集合進行性能評測,評測結果如表5所示。

表5 基于模式匹配的上下位關系抽取結果

由表5可以看出,通過模式匹配抽取上下位關系的方法可以獲得較多的候選結果,獲得相對較高的召回率,但準確率很低。通過對抽取結果進行進一步的自舉擴展,召回率方面獲得了約10%的提升,但準確率進一步下降。說明模式自舉擴展方法在提升召回率的同時使得錯誤結果數量也同時增大。

在模式匹配方法獲取的候選結果基礎上,本文分別使用語境特征相似度聚類驗證方法、布朗聚類相似度聚類驗證方法和二者結合的相似度特征聚類方法,對測試集進行驗證過濾,不同方法的性能對比如表6所示。

表6 不同上下位關系驗證方法的性能對比

從表6可知,對候選上下位關系分別進行基于語境特征相似度的聚類驗證和基于布朗聚類相似度的聚類驗證,抽取結果的準確率和F值均獲得較大幅度的提升。但2種相似度特征結合后獲得了比單一特征方法更好的效果,即證明了結合語境相似度和布朗聚類相似度為特征的上下位關系聚類驗證方法的有效性。

將本文方法與其他參與了CCF NLP&CC 2012語義關系識別評測的中科院聲學所等5種系統[15]進行比較,不同系統的方法性能比較情況如表7所示。

表7 本文方法與其他系統的方法評測結果對比

由表7可見,在參與該次評測的所有方法中,方法5所使用方法在F值上取到了較好的性能,該方法主要是通過使用維基百科和百度百科等現有的開放語義資源,并結合模板匹配和復合詞拆解的方法得到了較高的準確率和召回率。可以認為該方法是一種基于現有知識詞庫和在線百科的上下位關系抽取方法。而本文所提出的方法無需借助現有上下位關系詞庫和在線百科,同樣達到了較好的性能。

另外,由于測評結果根據CCF NLP&CC 2012語義關系所使用的標準評測集所判定,但該標準評測集中所包含的上下位關系相對有限,從而導致結果測試指標普遍偏低。例如,“傳輸協議”一詞在標準集中的下位詞集合與本文抽取結果對比如圖2所示。由圖2可見,在使用本文抽取方法獲得的結果中只有“網絡傳輸協議”一詞出現在標準評測集中,而根據人工評測,本文方法抽取到了更多的正確結果。因此,CCF NLP&&CC 2012的評測集對上下位關系的覆蓋并不完備。鑒于此,筆者對本文方法抽取結果進行了人工評測(僅計算準確率),評測結果如表8所示。

圖2 “傳輸協議”在標準評測集中的下位詞集合與本文抽取結果對比

表8 人工評測結果

6 結束語

詞匯的上下位關系在自然語言處理領域有著重要的應用價值。本文提出一種結合語境相似度特征和布朗聚類相似度特征的詞匯上下位關系聚類驗證方法,該方法在模式匹配方法抽取結果的基礎上對上下位關系進行驗證過濾。在CCF NLP&CC 2012評測語料上的實驗結果表明,該方法實現簡單,同時可取得較好的效果。

本文方法的不足在于語境特征提取過程和布朗聚類過程所需時間較長,且由于中文普遍存在的分詞(詞組)問題也對結果有較大的影響。下一步將嘗試使用更高效的上下位詞抽取方法,并結合有監督的自動分類方法對候選上下位關系進行是否為上下位關系的分類判斷,以進一步優化驗證效果。

[1] Hearst M.Automatic Acquisition of Hyponyms from Large Text Corpora[C]//Proceedings of COLING’92. New York,USA:[s.n.],1992:539-545.

[2] Kozareva Z,Riloff E,Hovy E.Semantic Class Learning fromtheWebwithHyponymPatternLinkage Graphs[C]//Proceedings of the 46th Annual Meeting oftheAssociationforComputationalLinguistics: HumanLanguageTechnologies.Columbus,USA: [s.n.],2008:1048-1056.

[3] Kozareva Z,Hovy E.A Semi-supervised Method to Learn and Construct Taxonomies Using the Web[C]// Proceedings of EMNLP’10.Boston,USA:[s.n.], 2010:1110-1118.

[4] Zhang Chunxia,Jiang Peng.Automatic Extraction of Definitions[C]//Proceedings of ICCSIT’09.Beijing, China:[s.n.],2009:364-368.

[5] Westerhout E.Definition Extraction Using Linguistic and StructuralFeatures[C]//Proceedingsofthe1st Workshop on Definition Extraction.Borovets,Bulgaria: [s.n.],2009:61-67.

[6] Akiba T,Sakai T.Japanese Hyponymy Extraction Based on a Term Similarity Graph[R].Tokyo,Japan:IPSJ SIG,Technical Reprot:2011-IFAT-104,2011.

[7] Miller G A.WordNet:A Lexical Database for English[J]. Communications of the ACM,1995,38(11):39-41.

[8] Suchanek F M,Kasneci G,Weikum G.Yago:A Large Ontology from Wikipedia and WordNet[J].Web Semantics:Science,Services and Agents on the World Wide Web,2008,6(3):203-217.

[9] Boella G,diCaroL.ExtractingDefinitionsand Hypernym Relations Relying on Syntactic Dependencies and Support Vector Machines[C]//Proceedings of the 51stAnnualMeetingoftheAssociationfor Computational Linguistics.Sofia,Bulgaria:[s.n.], 2013:532-537.

[10] Zhang Fan,Shi Shuming,Liu Jing,et al.Nonlinear EvidenceFusionandPropagationforHyponymy Relation Mining[C]//Proceedings of the 49th Annual MeetingoftheAssociationforComputational Linguistics.Portland,USA:[s.n.],2011,1159-1168.

[11] 劉 磊,曹存根,張春霞,等.概念空間中上下位關系的意義識別研究[J].計算機學報,2009,32(8):1-14.

[12] Wang R C,CohenWW.AutomaticSetInstance Extraction Using Web[C]//Proceedings of the18th International Conference on World Wide Web.Madrid, Spain:[s.n.],2009:101-110.

[13] Brown P F,Pietra V J D,de Souza P V.Class-based ngram Models of Natural Language[J].Computational Linguistics,1992,18(4):467-480.

[14] CCF NLP&CC2012語義關系識別標準評測集[EB/OL]. [2014-02-14].http://tcci.ccf.org.cn/conference/2012.

[15] CCF NLP&CC2012語義關系評測結果[EB/OL]. [2014-02-14].http://tcci.ccf.org.cn/conference/ 2012/dldoc/2012語義關系評測結果.pdf.

編輯 金胡考

Hyponymy Relation Validation Combined with Context and Brown Clustering Feature

ZHANG Zhichang,CHEN Songyi,LIU Xin,MA Huifang
(School of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

Hyponymy has many important applications in the field of Natural Language Processing(NLP)and the automatic extraction of hyponym relation from massive text datasets is naturally one of important NLP research tasks.The emphasis and difficult point of the research is how to validate a hyponym which is extracted with simple pattern matching method is really correct.By calculating the context feature similarity(SimCF)and Brown clustering similarity (SimBrown),this paper proposes a novel approach of hyponymy validation.It applies a clustering on hyponym candidates,and the clustering similarity feature is obtained by combiningSimCFandSimBrown.The combination coefficient of two kinds of similarity is derived based on theSimCFs andSimBrowns between all labeled training words and their hyponyms.The model can filter roughly extraction results without any existed lexical relation dictionary or knowledge base.Evaluation on CCF NLP&CC2012 word semantic relation corpus shows that the proposed approach in this paper significantly improves the F measure value compared with other approaches including pattern matching and simple context comparison.

hyponymy relation;context similarity;Brown clustering similarity;Point Mutual Information(PMI); pattern matching;clustering validation

張志昌,陳松毅,劉 鑫,等.結合語境與布朗聚類特征的上下位關系驗證[J].計算機工程,2015, 41(2):145-150.

英文引用格式:Zhang Zhichang,Chen Songyi,Liu Xin,et al.Hyponymy Relation Validation Combined with Context and Brown Clustering Feature[J].Computer Engineering,2015,41(2):145-150.

1000-3428(2015)02-0145-06

:A

:TP18

10.3969/j.issn.1000-3428.2015.02.028

國家自然科學基金資助項目(61163039,61163036,61363058);西北師范大學青年教師科研能力提升計劃基金資助項目(NWNU-LKQN-10-2)。

張志昌(1976-),男,副教授、博士,主研方向:自然語言處理,Web挖掘;陳松毅、劉 鑫,碩士研究生;馬慧芳,副教授、博士。

2014-03-04

:2014-04-03E-mail:zzc@nwnu.edu.cn