周 云，王 挺，易綿竹，張祿彭，王之元,4

(1. 國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073； 2. 解放軍外國(guó)語(yǔ)學(xué)院 國(guó)防語(yǔ)言文化研究所，河南 洛陽(yáng) 471003；3. 解放軍外國(guó)語(yǔ)學(xué)院 歐亞語(yǔ)系，河南 洛陽(yáng) 471003； 4. 國(guó)防科技大學(xué) 并行與分布處理國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410073)

1 引言

詞義消歧，即在特定的上下文中確定歧義詞的詞義。根據(jù)詞義消歧的范圍，可將其分為詞樣消歧(Lexical-Sample WSD)和全詞消歧(All-Words WSD)。詞樣消歧對(duì)給定文本中的某些指定詞進(jìn)行消歧，而全詞消歧對(duì)給定文本中的所有開(kāi)放詞(包括名詞、動(dòng)詞、形容詞和副詞)進(jìn)行消歧。詞樣消歧是一個(gè)典型的分類問(wèn)題，可使用各種成熟的有監(jiān)督分類算法，如樸素貝葉斯[1]、最大熵算法[2]和支持向量機(jī)[3]等。對(duì)于全詞消歧，目前通常的做法是將其當(dāng)作詞樣消歧，對(duì)句中出現(xiàn)的每個(gè)開(kāi)放詞逐個(gè)進(jìn)行消歧，各個(gè)詞之間的消歧是獨(dú)立的。但是，全詞消歧中前后兩個(gè)詞的消歧實(shí)際上是相互關(guān)聯(lián)的，全詞消歧可以看作一個(gè)序列標(biāo)注問(wèn)題。

序列標(biāo)注指的是對(duì)觀察值序列的每個(gè)成員指定一個(gè)類別標(biāo)簽，因此序列標(biāo)注可視為一系列的分類任務(wù)。由于序列標(biāo)注利用相鄰元素的依賴性對(duì)整個(gè)序列進(jìn)行全局優(yōu)化，一次性為所有觀察值給出標(biāo)簽，因而標(biāo)注性能通常會(huì)得到提升。常用的序列標(biāo)注算法有隱馬爾可夫模型(Hidden Markov Model, HMM)[4]、最大熵馬爾可夫模型(Maximum Entropy Markov Model, MEMM)[5]和條件隨機(jī)域[6]等。雖然HMM等序列標(biāo)注方法在一些自然語(yǔ)言處理任務(wù)中取得了突出的成績(jī)，如詞性標(biāo)注[7]和語(yǔ)音識(shí)別[8]等，但在詞義消歧中的結(jié)果卻并不理想[9-13]。這可能是由于:第一，HMM的觀察值只能是詞形，難以有效利用各類語(yǔ)言學(xué)特征；第二，全詞消歧是一個(gè)超大狀態(tài)問(wèn)題，序列標(biāo)注方法存在嚴(yán)重的數(shù)據(jù)稀疏問(wèn)題，并且具有很高的時(shí)間復(fù)雜度。

針對(duì)上述問(wèn)題，本文提出兩種基于序列標(biāo)注的全詞消歧方法，主要貢獻(xiàn)如下:(1)提出了一種基于HMM的全詞消歧方法；(2)將基于HMM的方法推廣為基于MEMM的全詞消歧方法，將觀察值由詞形擴(kuò)展為特征向量，引入了大量的語(yǔ)言學(xué)特征；(3)通過(guò)柱狀搜索和平滑策略解決上述模型中存在的數(shù)據(jù)稀疏問(wèn)題，在解決數(shù)據(jù)稀疏問(wèn)題的同時(shí)，柱狀搜索還顯著降低了解碼的時(shí)間復(fù)雜度；(4)在Senseval數(shù)據(jù)集上對(duì)序列標(biāo)注方法進(jìn)行了系統(tǒng)的評(píng)測(cè)。

本文結(jié)構(gòu)安排如下。第二節(jié)，我們給出一種基于HMM的全詞消歧方法。第三節(jié)，我們將模型推廣為MEMM模型，將觀察值擴(kuò)展為若干特征構(gòu)成的向量，這些特征包括鄰近詞詞性、局部搭配關(guān)系、依存句法關(guān)系、WordNet上位詞鏈、WordNet語(yǔ)義標(biāo)簽、WordNet動(dòng)詞框架和詞袋等。針對(duì)序列標(biāo)注方法存在的數(shù)據(jù)稀疏和很高的時(shí)間復(fù)雜度等問(wèn)題，在第四節(jié)我們?cè)O(shè)計(jì)了平滑策略和柱狀搜索Viterbi算法加以解決。第五節(jié)，我們?cè)赟enseval-2和Senseval-3上對(duì)HMM和MEMM方法進(jìn)行了評(píng)測(cè)，并與以往的序列標(biāo)注方法的性能進(jìn)行了對(duì)比。第六節(jié)，我們總結(jié)全文并討論下一步工作。

2 基于HMM的全詞消歧方法

HMM是一個(gè)經(jīng)典的數(shù)學(xué)模型[4]，它一般用以解決評(píng)估、序列標(biāo)注(也稱為解碼)和學(xué)習(xí)等三個(gè)問(wèn)題，這三個(gè)問(wèn)題分別可用前向算法(或后向算法)、Viterbi算法和前向—后向算法解決。在本文中我們主要關(guān)心序列標(biāo)注問(wèn)題和Viterbi算法。

HMM包含兩個(gè)隨機(jī)過(guò)程Qt,Qt,1≤t≤T，和五個(gè)模型參數(shù)S,V,A,B,π除特殊說(shuō)明外，本文均沿用文獻(xiàn)[4]中的符號(hào))。其中，(1)S={s1,s2,…,sN}為狀態(tài)集合；(2)V={v1,v2,…,vM}為觀察值集合；(3)A={aij},aij=P(Qt+1=sj|Qt=st),1≤1,j≤N為狀態(tài)轉(zhuǎn)移概率矩陣；(4)B={bj(k)},bj(k)=P(Qt=vk|Qt=sj),1≤j≤N,1≤k≤M為狀態(tài)—觀察值發(fā)射概率矩陣；(5)π={πi},πi=P(Q1=si),1≤i≤N為狀態(tài)初始分布概率向量。

(1)

這個(gè)問(wèn)題可通過(guò)稱為Viterbi算法的動(dòng)態(tài)規(guī)劃方法加以解決，其時(shí)間復(fù)雜度為O(TN2)。

基于HMM的全詞消歧模型需要選擇合適的狀態(tài)集合S和觀察值集合V。狀態(tài)集合S的選擇有多種，我們直接取訓(xùn)練集中出現(xiàn)過(guò)的synset作為狀態(tài)集S的一部分。由于封閉詞的個(gè)數(shù)是有限的，我們令每個(gè)封閉詞為一個(gè)狀態(tài)。另外，對(duì)于某些特殊的詞類(子類)，我們認(rèn)為它們的成員對(duì)于詞義消歧而言是等價(jià)的，因而將它們整體作為一個(gè)狀態(tài)，這有利于緩解數(shù)據(jù)的稀疏性，這包括人名、地名、組織名、其他專有名詞、序數(shù)詞、屬格代詞、聯(lián)結(jié)詞和情態(tài)動(dòng)詞。觀察值集合V的選擇也有多種，我們以詞條(lemma)和詞性的字符串連接作為觀察值?？捎米饔^察值的有:詞、詞條、詞與詞性的字符串連接或詞條與詞性的字符串連接等。文獻(xiàn)[13]的實(shí)驗(yàn)結(jié)果表明，詞與詞性的字符串連接作為輸入效果較好，我們沿用這一作法。A,B,π均由訓(xùn)練集作最大似然估計(jì)得到。

3 基于MEMM模型的全詞消歧方法

McCallum等人在文獻(xiàn)[5]中將HMM改造為MEMM，其不同之處在于:(1)觀察值的擴(kuò)充。HMM的觀察值集合一般只能為一個(gè)有限的詞表；而MEMM對(duì)原始觀察值抽取若干個(gè)非獨(dú)立特征，構(gòu)成特征向量，然后根據(jù)特征向量計(jì)算給定觀察序列的狀態(tài)序列的條件概率； (2)由生成模型到條件模型。在HMM中，當(dāng)前狀態(tài)僅依賴于前一狀態(tài)(馬爾可夫性)；在MEMM中，當(dāng)前狀態(tài)不僅依賴于前一狀態(tài)，還依賴于當(dāng)前特征向量。

在MEMM中，狀態(tài)轉(zhuǎn)移概率和狀態(tài)—觀察值發(fā)射概率被一個(gè)統(tǒng)一的新的概率Pqt-1(Qt-qt+Ot=ot)=P(Qt=qt|Ot=ot,Qt-1=qt-1)所代替，即在前一狀態(tài)為qt-1且當(dāng)前特征向量為ot時(shí)，當(dāng)前狀態(tài)為qt的概率。Pqt-1(Qt=qt|Ot=ot)可用某些帶概率輸出的機(jī)器學(xué)習(xí)算法進(jìn)行訓(xùn)練得到，如最大熵算法、樸素貝葉斯算法和支持向量機(jī)等。最早提出該模型的文獻(xiàn)[5]采用了最大熵算法，MEMM模型因此得名。

MEMM模型的要素為S,V,M,π。其中，(1)S={s1,s2,…,sN}為狀態(tài)集合；(2)V={v1,v2,…}為由觀察值抽取的特征向量構(gòu)成的集合；(3)M={Pqt-1(Q1=qt|Ot=ot},qt∈S,ot∈V},qt-1∈S為概率模型集合；(4)π={PBegin(Q1=q1|O1=o1),q1∈S,o1∈V}為初始概率模型。在MEMM中，序列標(biāo)注問(wèn)題為也可通過(guò)Viterbi算法加以解決，它與HMM的Viterbi算法是十分類似的。

在基于MEMM的全詞消歧模型中，狀態(tài)集合S與HMM的狀態(tài)集合S相同。特征向量集合V中的元素為由原始觀察值抽取的特征向量構(gòu)成的集合。我們以文獻(xiàn)[2，14]中的特征為基礎(chǔ)，設(shè)計(jì)了以下七類特征:(1)鄰近詞的詞性；(2)局部詞形搭配關(guān)系；(3)依存句法關(guān)系；(4)特定范圍內(nèi)的WordNet上位詞(hypernym)鏈；(5)特定范圍內(nèi)的WordNet語(yǔ)義標(biāo)簽；(6)特征范圍內(nèi)的WordNet動(dòng)詞框架；(7)句中的各個(gè)單詞構(gòu)成的詞袋。上述特征的詳細(xì)解釋及例子見(jiàn)附錄A。對(duì)于每一個(gè)概率模型Pqt-1(Qt=qt|Ot=ot)，我們通過(guò)將訓(xùn)練集中緊接在qt-1后面的所有狀態(tài)-特征向量對(duì)(qt,ot)收集起來(lái)，然后用最大熵算法進(jìn)行訓(xùn)練，就得到了模型Pqt-1(Qt=qt|Ot=ot)。對(duì)于初始概率模型PBegin(Q1=q1|O1=o1)，我們則收集句首的狀態(tài)—特征向量對(duì)即可。

4 實(shí)現(xiàn)

如前所述，序列標(biāo)注一般通過(guò)Viterbi算法解決。全詞消歧作為一個(gè)超大狀態(tài)問(wèn)題，上述兩個(gè)模型均存在嚴(yán)重的數(shù)據(jù)稀疏問(wèn)題，同時(shí)還具有過(guò)高的時(shí)間復(fù)雜度。下面提出的柱狀搜索Viterbi算法和平滑策略，解決了數(shù)據(jù)稀疏的問(wèn)題。另外，柱狀搜索在解決數(shù)據(jù)稀疏問(wèn)題的同時(shí)，還顯著地降低了解碼的時(shí)間復(fù)雜度。

4.1 柱狀搜索

在全詞消歧的HMM模型中，發(fā)射概率矩陣是十分稀疏的。狀態(tài)空間S的非常大，包括訓(xùn)練集中出現(xiàn)過(guò)的synset及封閉詞等，其規(guī)模約為數(shù)萬(wàn)。然而，一個(gè)觀察值ot(lemma)對(duì)應(yīng)的狀態(tài)數(shù)(synset數(shù))卻是十分有限的，至多為數(shù)十個(gè)。為解決這個(gè)問(wèn)題，我們采用柱狀搜索Viterbi算法進(jìn)行解碼。我們將觀察值ot對(duì)應(yīng)的狀態(tài)集合記為stateSet(ot)，在Viterbi算法迭代的每一步，只搜索stateSet(ot)，而不是整個(gè)狀態(tài)空間，即

這不僅有效地解決了發(fā)射概率矩陣稀疏問(wèn)題，還顯著地降低了解碼的時(shí)間復(fù)雜度。通常，Viterbi算法的時(shí)間復(fù)雜度為O(TN2)，其中，T為待消歧句子的長(zhǎng)度，N為狀態(tài)空間S的大小。在HMM方法中，由于N的值非常大，該算法的實(shí)際運(yùn)行時(shí)間是難以承受的。使用柱狀搜索后，Viterbi算法的時(shí)間復(fù)雜度由O(TN2)降為其中Smax為一個(gè)lemma最多可能對(duì)應(yīng)的synset數(shù)。MEMM的柱狀解碼與此十分類似，本文從略。

4.2 平滑策略

在全詞消歧的HMM模型中，轉(zhuǎn)移概率矩陣也是稀疏的。Viterbi算法計(jì)算概率的乘積，若轉(zhuǎn)移概率為0，則乘積結(jié)果為0，無(wú)法比較結(jié)果的大小。為了避免整個(gè)乘積的結(jié)果為0，我們必須采用某種平滑策略。在HMM中，轉(zhuǎn)移概率矩陣A中元素aij的極大似然估計(jì)為其中C(sisj)表示在訓(xùn)練集中sisj出現(xiàn)的次數(shù)。我們令aij平滑后的值為：

其中，I(·)為指示函數(shù)，表示觀察值v(lemma)對(duì)應(yīng)的狀態(tài)(synset)數(shù)，F(xiàn)(sj)表示sj對(duì)應(yīng)的synset在WordNet中出現(xiàn)的頻數(shù)。上述公式的直觀含義是，我們假設(shè)si的轉(zhuǎn)移概率中有1-γ出現(xiàn)在訓(xùn)練集中，有γ未出現(xiàn)在訓(xùn)練集中；對(duì)于未出現(xiàn)在訓(xùn)練集中的sj，若sj∈Synsets(v)，我們令其概率與其對(duì)應(yīng)的synset在WordNet中出現(xiàn)的頻數(shù)F(sj)成正比；對(duì)于所有未出現(xiàn)在訓(xùn)練集中的sj，若sj?Synsents(v)，我們令其概率均相等。在我們的實(shí)驗(yàn)中，γ=0.999。

對(duì)于MEMM模型,我們令Psi(sj|v)平滑后的值為：

式(3)的直觀含義與式(2)類似。

5 實(shí)驗(yàn)

在Senseval/Semeval出現(xiàn)之前，曾有少數(shù)學(xué)者嘗試用HMM等序列標(biāo)注方法進(jìn)行全詞消歧，如Segond等人[9]采用HMM進(jìn)行全詞標(biāo)注，其標(biāo)記為WordNet的45個(gè)語(yǔ)義標(biāo)簽；Loupy等人[10]采用一種集成了語(yǔ)義標(biāo)簽和詞義的混合HMM進(jìn)行全詞標(biāo)注。但由于上述研究并未使用通用測(cè)試集，其結(jié)果并不具有可比性。

Senseval/Semeval(2007年之前稱為Senseval)是目前國(guó)際上最權(quán)威的詞義消歧評(píng)測(cè)，我們的測(cè)試集來(lái)自Senseval-2(2001)[15]、Senseval-3(2004)[16]的English All Words任務(wù)，表1給出了這些任務(wù)的基本信息。

English All Words為開(kāi)放測(cè)試，只提供測(cè)試集，對(duì)訓(xùn)練集沒(méi)有限制。我們僅使用了SemCor[17]的Brown1和Brown2作為訓(xùn)練集，包含359 732個(gè)詞(不含標(biāo)點(diǎn))，其中192 639個(gè)詞有詞義標(biāo)注。對(duì)于訓(xùn)練集中不存在的觀察值，我們使用WordNet中的最常用詞義進(jìn)行標(biāo)注。MEMM方法采用GIS算法訓(xùn)練最大熵模型，迭代次數(shù)為100。表2給出了參加英語(yǔ)全詞消歧任務(wù)系統(tǒng)的性能(F1值)。

表1 英語(yǔ)全詞消歧任務(wù)基本信息

English All Words對(duì)訓(xùn)練集沒(méi)有限制，因此對(duì)不同系統(tǒng)的比較是十分困難的，下面我們?cè)噲D對(duì)實(shí)驗(yàn)結(jié)果作出一些說(shuō)明。

首先，本文提出的MEMM方法的性能顯著高于相同數(shù)據(jù)集上的其他序列標(biāo)注方法，包括本文提出的HMM方法。這證明了將簡(jiǎn)單觀察值擴(kuò)展為復(fù)雜的特征向量確實(shí)是有效的， 這得益于大量語(yǔ)言學(xué)特征的引入。

表2 參加英語(yǔ)全詞消歧任務(wù)的系統(tǒng)性能(F1值)

其次，在僅采用SemCor作為訓(xùn)練集的情況下，本文提出的MEMM方法也超過(guò)了Senseval-2的第2名和Senseval-3的第1名。其中，Senseval-2的第2名[19]采用了基于記憶的方法，并使用多個(gè)分類器進(jìn)行投票；Senseval-3的第1名[20]也采用了基于記憶的方法，它的訓(xùn)練集包括SemCor，Senseval-2的數(shù)據(jù)以及WordNet中的例子。這說(shuō)明序列標(biāo)注方法完全可以用于全詞消歧，并且性能與最好的有監(jiān)督方法相當(dāng)。我們看到，本文MEMM方法與Senseval-2的第1名[18]還有一定的差距，部分原因是文獻(xiàn)[18]采用了很多SemCor以外的數(shù)據(jù)，如WordNet中的定義和互聯(lián)網(wǎng)收集的數(shù)據(jù)等。

在Senseval-2中，Crestan等人[11]采用兩階段HMM進(jìn)行全詞消歧。第一階段先通過(guò)HMM確定詞形的語(yǔ)義標(biāo)簽，第二階段再用HMM確定詞形+語(yǔ)義標(biāo)簽的詞義，另外還對(duì)高頻詞采用詞樣消歧的方法進(jìn)行消歧。就性能而言，這種兩階段HMM方法與與單一HMM方法相當(dāng)[10]，在本實(shí)驗(yàn)中也得到了證實(shí)。

在Senseval-2和Senseval-3中，Molina等人[12-13]采用HMM進(jìn)行全詞消歧，其狀態(tài)為SemCor中的lex_sense[17]。這相當(dāng)于對(duì)synset進(jìn)行了壓縮，其好處在于使?fàn)顟B(tài)數(shù)減少，從而緩解矩陣稀疏的問(wèn)題。但是，我們認(rèn)為這種壓縮并不具備語(yǔ)言學(xué)基礎(chǔ)，有可能造成算法的不穩(wěn)定性，而且難以將HMM擴(kuò)展為MEMM。實(shí)驗(yàn)表明，本文的HMM方法以synset為狀態(tài)是合適的，其性能要略好于以lex_sense為狀態(tài)的文獻(xiàn)[12-13]，且具備良好的可擴(kuò)展性。

6 結(jié)束語(yǔ)

全詞消歧可以看作一個(gè)序列標(biāo)注問(wèn)題。然而，現(xiàn)有序列標(biāo)注方法在全詞消歧上的表現(xiàn)卻不盡如人意，主要原因在于特征的有效利用和數(shù)據(jù)稀疏問(wèn)題。本文從全詞消歧的特點(diǎn)出發(fā)，針對(duì)上述不足，提出了兩種基于序列標(biāo)注的全詞消歧方法，并采用柱狀搜索和平滑策略解決了數(shù)據(jù)稀疏和高時(shí)間復(fù)雜度等問(wèn)題，其中基于MEMM的全詞消歧方法的性能較大幅度地超過(guò)了文獻(xiàn)中已有的基于序列標(biāo)注的方法。由于本文僅使用了基本的訓(xùn)練語(yǔ)料，本文提出的方法的實(shí)際性能還有進(jìn)一步提高的空間。實(shí)際上，本文提出的方法可適用于一般的超大狀態(tài)序列優(yōu)化問(wèn)題。

無(wú)論是一般的分類問(wèn)題還是序列標(biāo)注，特征選擇都是至關(guān)重要的，下一步我們將研究各種特征對(duì)整體性能的影響，以便更好地改進(jìn)算法。另外，條件隨機(jī)域(CRF)是近來(lái)出現(xiàn)、在多個(gè)領(lǐng)域均有突出表示的序列標(biāo)注方法。CRF是HMM和MEMM的推廣，一般認(rèn)為CRF的效果要比HMM和MEMM好。但是，CRF訓(xùn)練的時(shí)間復(fù)雜度比HMM和MEMM要高得多，一般只用于狀態(tài)數(shù)較少(一般數(shù)百個(gè)狀態(tài)以內(nèi))的場(chǎng)合。對(duì)于全詞消歧這類含有數(shù)萬(wàn)個(gè)狀態(tài)的問(wèn)題，即使在采用柱狀搜索算法后，CRF的訓(xùn)練仍然不可能在普通的工作站上完成，我們下一步將嘗試采用集群計(jì)算的方式來(lái)解決這個(gè)問(wèn)題。

[1] Mooney R. J. Comparative experiments on disambiguating word senses: An illustration of the role of bias in machine learning [C]//Proceedings of the 1996 Conference on Empirical Methods in Natural Language Processing (EMNLP). 1996. 82-91.

[2] Tratz S., Sanfillippo A., Gregory M., et al.PNNL: A supervised maximum entropy approach to word sense disambiguation [C]//Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007). Stroudsburg, PA, USA, 2007. 264-267.

[3] Escudero G., M rquez L., Rigau, G. On the portability and tuning of supervised word sense disambiguation [C]//Proceedings of the Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora (EMNLP). 2000. 172-180.

[4] Lawrence R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition [C]//Proceedings of the IEEE. 1989. 257-286.

[5] Andrew McCallum, Dayne Freitag, Fernando Pereira. Maximum Entropy Markov Models for Information Extraction and Segmentation [C]//Proceedings of the 17th International Conference on Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.， 2000. 591-598.

[6] John Lafferty, Andrew McCallum, Fernando Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data [C]//Proceedings of the 18th International Conference on Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2001. 282-289.

[7] El-B ze M., M rialdo B.. HMM Based Taggers [C]//H. Van Halteren eds. Syntactic Wordclass Tagging. Kluwer Academic Publishers, 1999.

[8] F. Jelinek. Statistical Methods for Speech Recognition [M]. Cambridge: MIT Press, 1998.

[9] Segond F., Schiller, A., Grefenstette, G., et al. An Experiment in Semantic Tagging using Hidden Markov Model Tagging [C]//Proceedings of the Joint ACL/EACL Workshop on Automatic Information Extraction and Building of Lexical Semantic Resources. Stroudsburg, PA, USA, 1997. 78-81.

[10] Claude de Loupy, MarcEl-Beze, Pierre-Fran ois Marteau. Word Sense Disambiguation using HMM Tagger [C]//Proceedings of the 1st International Conference on Language Resources and Evaluation (LREC). Granada, Spain, 1998. 1255-1258.

[11] E. Crestan, M. El-Beze, C. De Loupy. Improving WSD with Multi-Level View of Context Monitored by Similarity Measure [C]//Proceedings of the 2nd International Workshop on Evaluating Word Sense Disambiguation Systems. Toulouse, France, 2001. 67-70.

[12] Antonio Molina, Ferran Pla, Encarna Segarra. A Hidden Markov Model Approach to Word Sense Disambiguation [C]//Proceedings of the 8th Ibero-American Conference on AI: Advances in Artificial Intelligence. Longdon, UK: Springer-Verlag. 2002. 655-663.

[13] Antonio Molina, Ferran Pla, Encarna Segarra. WSD system based on Specialized Hidden Markov Model [C]//Proceedings of the Third International Workshop on the Evalution of Systems for the Semantic Analysis of Text, 2004.

[14] Yoong Keok Lee, Hwee Tou Ng. An Empirical Evaluation of Knowledge Sources and Learning Algorithms for Word Sense Disambiguation [C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). Stroudsburg, PA, USA, 2002. 41-48.

[15] Edmonds P., Cotton S. Senseval-2: Overview [C]//Proceedings of the 2nd Internationnal Workshop on Evaluating Word Sense Disambiguation Systems. 2001. 1-6.

[16] Benjamin Snyder, Martha Palmer. The English All-Words Task [C]//Proceeding of Senseval-3: The 3rd International Workshop on the Evaluation of Systems for the Semantic Analysis of Text. Barcelona, Spain, 2004. 41-43.

[17] Miller G.A., Chodorow M., Landes S., et al. Using a Semantic Concordance for Sense Identification [C]//Proceedings of the ARPA Workshop on Human Language Technology. Stroudsburg, PA, USA, 1994. 240-243.

[18] Mihalcea R. Word sense disambiguation with pattern learning and automatic feature selection [J]. Natural Language Engineering, 2002,8(4):348-358.

[19] Hoste V., Hendrickx I., Daelemans W., et al. Parameter optimization for machine learning of word sense disambiguation [J]. Natural Language Engineering, 2002,8(4):311-325.

[20] Decadt B., Hoste V., Daelemans W., et al. GAMBL, genetic algorithm optimization of memory-based WSD [C]//Proceedings of the 3rd International Workshop on the Evaluation of Systems for the Semantic Analysis of Text. 2004. 108-112.

[21] Mihalcea R., Faruque E. Senselearner: Minimally supervised word sense disambiguation for all words in option text [C]//Proceedings of the 3rd International Workshop on the Evaluation of Systems for the Semantic Analysis of Text. 2004. 155-158.

附錄A MEMM模型采用的特征

MEMM模型與一般HMM的最大不同，就是語(yǔ)言學(xué)特征的使用。相對(duì)于lemma而言，特征的引入可以捕獲目標(biāo)詞的上下文中的各類語(yǔ)言學(xué)特征，有利于對(duì)目標(biāo)詞義的消歧。這些特征主要包括七類： 鄰近詞的詞性、局部搭配關(guān)系、依存句法關(guān)系、特定范圍內(nèi)的上位詞(hypernym)鏈、特定范圍內(nèi)的WordNet語(yǔ)義標(biāo)簽、特征范圍內(nèi)的WordNet動(dòng)詞框架和句中的各個(gè)單詞。

A.1 鄰近詞詞性(七維)

我們用Pi(P-i)表示當(dāng)前詞w右(左)邊第i個(gè)詞的詞性，使用以下七個(gè)特征：P-3,P-2,P-1,P0,P1,P2,P3。所有的詞不能跨越句子的邊界。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，當(dāng)前詞為bars，則它的鄰近詞詞性特征為，其中ε為跨越句子后的標(biāo)記。

A.2 局部搭配關(guān)系(11維)

我們用Ci,j表示當(dāng)前詞的從第i個(gè)詞到第j個(gè)詞的詞條的字符串連接，使用以下11個(gè)特征：C-1，-1,C1，1,C-2，-2,C2，2,C-2，-1,C-1，1,C1，2,C-3，-1,C-2，1,C-1，2,C1，3。 例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，當(dāng)前詞為bars，則它的C-2，1特征為the_iron_bar_.。

A.3 依存句法關(guān)系(10維)

該特征假設(shè)當(dāng)前詞的語(yǔ)義與和其有直接依存關(guān)系的詞有關(guān)，這在某種程度上反映了語(yǔ)義的長(zhǎng)距離(句法)依賴關(guān)系。依存句法假設(shè)，句法結(jié)構(gòu)是用非對(duì)稱的二元關(guān)系將詞連接而成的。這種二元關(guān)系稱為依存關(guān)系，被支配的詞稱為依賴詞(dependent)，另一個(gè)詞則稱為頭詞(head)。我們使用以下特征： 當(dāng)前詞w的頭詞h的詞條，h與w的依存關(guān)系類型，h的詞性，h與w的相對(duì)位置(h在w的左邊還是右邊)；當(dāng)前詞w左邊最近的依賴詞l的詞條，l與w的依存關(guān)系類型，l的詞性；當(dāng)前詞w右邊最近的依賴詞r的詞條，r與w的依存關(guān)系類型，r的詞性。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”， 其依存關(guān)系見(jiàn)圖A1，當(dāng)前詞為looking，則它的依存句法關(guān)系特征為。

圖A1 依存關(guān)系

A.4 特定范圍內(nèi)的上位詞鏈

特定范圍，指目標(biāo)單詞的前后三個(gè)鄰近詞及依存關(guān)系鏈三步以內(nèi)的詞，下同。上位詞從WordNet中抽取，我們包含給定范圍內(nèi)的詞的最常用詞義(MFS, Most Frequent Sense)的整個(gè)上位詞鏈。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，當(dāng)前詞為looking.looking的前后三個(gè)鄰近中具有上位詞的詞有saw和iron，而looking的三步以內(nèi)依存關(guān)系鏈中具有上位詞的詞有iron和bars，則共有saw，iron和bars三個(gè)單詞具有上位詞鏈，他們分別為,和。

A.5 特定范圍內(nèi)的WordNet語(yǔ)義標(biāo)簽

語(yǔ)義標(biāo)簽從WordNet中抽取，我們包含給定范圍內(nèi)的詞的最常用詞義的語(yǔ)義標(biāo)簽。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，當(dāng)前詞為looking。特定范圍內(nèi)具有語(yǔ)義標(biāo)簽的詞為saw，iron和bars，則語(yǔ)義標(biāo)簽特征為。

A.6 特定范圍內(nèi)的WordNet動(dòng)詞框架

動(dòng)詞框架從WordNet中抽取，我們包含給定范圍內(nèi)的詞的最常用詞義的動(dòng)詞框架。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，當(dāng)前詞為looking。特定范圍內(nèi)具有動(dòng)詞框架的詞為，則動(dòng)詞框架特征為<2,8,9>。在WordNet中框架號(hào)2表示句式”Somebody——s”，框架號(hào)8表示句式”Somebody——s something”，框架號(hào)9表示句式”Somebody——s somebody”。

A.7 句中的各個(gè)單詞

我們直接將句中的每個(gè)單詞作為當(dāng)前觀察值的一個(gè)特征。