動態(tài)自適應加權的多分類器融合詞義消歧模型

張仰森，郭 江

（北京信息科技大學 智能信息處理研究所，北京100192）

許多與自然語言處理相關的應用系統(tǒng)，如機器翻譯、文本校對、信息檢索、文本分類等，其性能的優(yōu)劣與詞義消歧的效果密切相關。因此，長期以來，漢語詞義消歧一直是中文信息處理領域的難點和熱點。由于詞義消歧本身可以看作分類問題，因此，詞義消歧模型的構(gòu)建其實就是分類器的構(gòu)建。由于不同分類器在不同領域的表現(xiàn)效果不同，因此，近年來集成學習方法成為機器學習領域的發(fā)展趨勢［1］，采用多分類器融合方法建立詞義消歧模型的技術越來越受到研究者的關注，并在實際中得到應用［2－3］。多分類器融合就是通過某種規(guī)則將多個基分類器的判定結(jié)果融合起來，使得各基分類器之間相互彌補，得到系統(tǒng)最終的決策結(jié)果。構(gòu)建多分類器融合詞義消歧模型的工作一般由四步構(gòu)成［4］，包括模型參數(shù)輸入、基分類器的設計與選擇、模型體系結(jié)構(gòu)、融合規(guī)則。模型參數(shù)輸入是指用于確定語句中某個詞詞義的特征表示方式；基分類器設計與選擇是指選擇哪些分類器來進行集成融合；模型體系結(jié)構(gòu)是指對各基分類器進行融合的體系結(jié)構(gòu)；融合規(guī)則是指將各基分類器判定結(jié)果進行組合獲取最終判定結(jié)果的規(guī)則與算法。關于多義詞詞義消歧的特征選擇，已有很多的相關研究，我們在實驗部分再進行討論，下面主要就模型的體系結(jié)構(gòu)、基分類器集合的設計與選擇、多分類器的融合規(guī)則進行討論。

1 多分類器融合的體系結(jié)構(gòu)

多分類器融合的體系結(jié)構(gòu)有級聯(lián)方式和并聯(lián)方式兩種。采用級聯(lián)方式時，將多個基分類器串聯(lián)起來，前一級分類器為后一級分類器提供分類信息，指導下一級分類器的判斷；而采用并聯(lián)方式時，各基分類器的設計是獨立的，各基分類器給出詞義消歧的判定結(jié)果，按照某種融合規(guī)則將各單分類器的結(jié)果進行融合得到最終的詞義判定結(jié)果。

由于并聯(lián)方式可以使各基分類器并行工作，因此在分類速度上有較大優(yōu)勢。近幾年，多分類器融合的研究主要集中在并聯(lián)方式，特別是融合規(guī)則或算法的研究。分類器融合的目標是對各基分類器提供的信息進行融合，各基分類器提供的信息可以分為結(jié)果級、排序級和度量級三個層次［4］。（1）結(jié)果級是指基分類器給出的某個確定的詞義，即最終分類的結(jié)果；（2）排序級是指基分類器按照多義詞的上下文特征給出多義詞詞義類別的一個排序列表，排在最前面的是第一選擇；（3）度量級是指基分類器給出選擇每個詞義類別的概率值。在這三個層次中，度量層所含的信息最豐富，結(jié)果層最少。從分類器工作過程來看，排序?qū)邮鞘褂枚攘繉拥慕Y(jié)果來排序，結(jié)果層是使用排序?qū)拥慕Y(jié)果。從度量層到結(jié)果層是一個信息量遞減的過程。所以適用于信息量少的層級融合的方法同樣適用于含信息量多的層。

采用并聯(lián)方式的分類器融合，可根據(jù)基分類器的信息層次分為三類：基于結(jié)果層的融合方法、基于排序?qū)拥娜诤戏椒ā⒒诙攘繉拥娜诤戏椒?。這三類融合方法利用的信息是一個逐步具體的過程。對于第一類方法，其利用的信息最為簡單，其規(guī)則的設計也相對簡單；對于第三類方法，由于提供的信息量增多，規(guī)則或算法的設計相對繁瑣，如果設計得當，多分類器融合模型的分類效果會比較好，若設計得不好，融合分類器的分類效果可能還不如單個分類器的分類效果。

2 基分類器的分析與選擇

要想在多分類器的融合上取得好的效果，除了融合算法的設計，對于每個分類器而言，一般需要滿足以下原則：

（1）基分類器的精確度要高，否則構(gòu)造的融合分類器精確度也不會很高。

（2）基分類器應該具有多樣性?；诸惼髦g應該產(chǎn)生互補信息，如果不同的分類器產(chǎn)生相同的錯誤，則融合就變得沒有意義了，整體性能也不會有任何提高。

基于上述基分類器的選擇原則，我們考察了最大熵分類器、樸素貝葉斯分類器、向量空間分類器和決策樹分類器。這幾種方法很具有代表性，且原理和方法互補性很強。我們分別利用這幾種模型進行了詞義消歧實驗，相關的分析實驗結(jié)果已在另一篇論文［5］中給出。其中樸素貝葉斯是傳統(tǒng)的概率統(tǒng)計方法，簡單快速，準確率高，穩(wěn)定性強，對不同的特征對象進行實驗，其最低準確率達到了78.12%；決策樹是以實例為基礎的歸納學習算法，易于理解，但對不同特征對象進行實驗的效果不是太好，最好為67.3%。最大熵模型由于是一種使用多種類型特征的模型，在實驗中表現(xiàn)不俗，其最低達到了83.35%。向量空間方法，是信息檢索領域的基礎，能夠克服數(shù)據(jù)稀疏的問題，當特征選擇恰當?shù)臅r候，比如整句特征時，其最低準確率為68.52%以上。鑒于以上分析，在后面的融合實驗中選擇最大熵分類器、樸素貝葉斯分類器、向量空間分類器作為融合算法的基分類器。

3 分類器融合的主要方法

近年來已經(jīng)有人將多分類器融合技術應用到詞義消歧領域。融合方法主要有兩種：（1）采用不同種類的分類器作為基分類器進行融合；（2）對同一種分類器選擇不同詞義消歧特征進行計算，將計算結(jié)果進行融合。融合計算常用的方法有乘法規(guī)則、均值、最大值Max、最小值Min、最大投票、序列投票、加權投票、概率加權等［2］。2000年 Kilgarriff和Rosenzweig采用簡單投票策略集成SenSeval－1多個參賽系統(tǒng)的輸出結(jié)果進行詞義消歧［6］；2008年吳云芳等［2］采用支持向量機、樸素貝葉斯、決策樹，綜合運用乘法規(guī)則、均值等9種集成方法，在兩個不同數(shù)據(jù)集上進行了實驗。它們都屬于前述的第一種融合方法。2004年Wang和Matsumoto提出了一種堆棧集成法［7］，單分類器選用樸素貝葉斯分類器，使用特征模板提取特征；2006年全昌勤等應用AdaBoost思想［3］，選擇貝葉斯分類器，通過學習少量帶有詞義標注的語料構(gòu)造多個消歧分量分類器，并利用未標語料動態(tài)地對這些分類器進行更新，根據(jù)最終分量分類器進行集成確定多義詞義項。它們都是采用了一種分類器對多種特征或分量進行疊加融合，屬于前述的第二種融合方法。

（1）最大投票（Majority Voting，MV）方法

最大投票法是一種簡單的分類器融合方法，由基分類器先對樣本進行判斷得出自己的分類結(jié)果，對自己所預測的類投一票，最后得票最多的類就是融合學習算法最終的預測結(jié)果。假設詞有n個詞義，有m個分類器參與投票，則其融合模型如公式（1）所示：

其中，sk表示詞W 的第k個詞義，fi表示第i個分類器，sj表示第i個分類器確定的詞義，Δji是第i個分類器對第j個詞義的投票結(jié)果，是m個分類器融合后得到的詞義消歧結(jié)果。

（2）改進的投票（Improved Voting，IV）方法

簡單的投票融合過程是結(jié)果級的融合，基分類器只輸出單純的分類決策，沒有其他附加信息。對簡單投票做以下改進，使其融合在度量級上進行，計算式如下：

其中，sj表示詞W 的第j個詞義，fi表示第i個分類器，P（sj）表示所有單分類器對詞義sj輸出概率的均值，是m個分類器融合后得到的詞義消歧結(jié)果。這種方法屬于上述的第二種融合方法。

（3）性能加權投票 （Performance Weighted Voting，PWV）方法

最大投票方法在確定最后結(jié)果時，沒有考慮不同基分類器的分類性能及所采用的不同分類特征。所以，該方法無法體現(xiàn)性能高的分類器的優(yōu)勢，于是，人們就想到對上述兩類方法進行改進，給性能高的分類器賦一個高的權值，這就是基于性能的加權投票方法。基于性能的加權投票方法可在結(jié)果級和度量級進行，結(jié)果級性能加權是對MV方法中式（1）和（2）的改進，結(jié)果如式（5）和（6）；度量級性能加權是對IV方法中式（3）和（4）的改進，結(jié)果如式（7）和式（8）。

其中，sk表示詞W 的第k個詞義，fi表示第i個分類器，sj表示第i個分類器確定的詞義，Δji是第i個分類器對第j個詞義的投票結(jié)果，是m個分類器融合后得到的詞義消歧結(jié)果，λi為分類器fi的加權系數(shù)。

4 動態(tài)自適應加權分類器融合模型

我們已在文獻［5］中對四種分類器在詞義消歧方面的應用情況進行了分析比較，目的是希望通過融合技術來提高詞義消歧模型的性能。前面介紹的性能加權投票方法就考慮了各種分類器的性能，但其權值λi的確定缺乏依據(jù)，不能根據(jù)各基分類器在相應樣本特征情況下動態(tài)自適應確定。本文在前述分析的基礎上提出了一種動態(tài)自適應加權投票融合方法（Auto Weight Adjust，AWA），它充分考慮了各分類器在不同樣本環(huán)境下的性能表現(xiàn)，計算出確定分類器fi加權系數(shù)的閾值θi，再根據(jù)θi計算該分類器的加權系數(shù)βi。動態(tài)自適應加權投票融合模型如式（9）所示。

βi是我們設計的加權系數(shù)函數(shù)，用來表示基分類器fi對類別sj的權值；θi為確定分類器fi加權分量的閾值，閾值θi根據(jù)單分類器fi在決策時的“自信”值確定，“自信”值為分類器fi對每個類別sj（j＝1，2，…，n）給出的度量層結(jié)果的概率平均值。用數(shù)學公式表示如式（10）所示。

與上述性能加權投票（PWV）不同，PWV通常將加權系數(shù)λi設置為基分類器的概率p（fi）［2］，而這是很難求得的。本文設計的加權系數(shù)根據(jù)分類器fi的自信程度來確定它的權值，θi反映了分類器fi對所有類別sj（j＝1，2，…，n）計算出的度量層的分類概率的平均值，如果P（sj｜fi）大于或等于平均值θi，則說明fi對分類結(jié)果更傾向于類別sj，也就是說，它自信自己對確定最終類別sj的貢獻要大，因此，給P（sj｜fi）的權重系數(shù)為0.7，而如果P（sj｜fi）＜θi，則說明分類器fi對選擇類別sj并不自信，因此在最終確定sj時只對自己計算出的概率值P（sj｜fi）要30%的加權值。

這樣設計的性能加權系數(shù)，能夠保證每個分類器fi（i＝1，2，…，m）對最后類別的確定具有發(fā)言權，只是每個分類器根據(jù)其自信度（是否大于閾值θi）發(fā)言權的大小不同?？朔酥豢紤]那些對類別確定具有最大概率的分類器的缺陷，讓所有分類器都能發(fā)揮作用，計算的結(jié)果更合理。在詞義消歧應用中，分類的類別就是多義詞的義項，這里所設計的模型，考慮了更多的上下文特征，不同的上下文特征集對應于不同的分類器，每個分類器都能對當前多義詞的義項確定發(fā)揮作用，只是每個分類器對多義詞的每個義項的貢獻權重不同。綜合計算出它的每個義項的概率值之后，排序選擇概率最大的那個義項作為多義詞的義項。通過大量實驗，我們發(fā)現(xiàn)使用0.7確定“自信”特征的加權系數(shù)效果比較好。具體算法步驟如下：

Step1.對數(shù)據(jù)集（人民日報2000年11、12月中的50天語料）按不同的特征提取方法（所設計的7種特征模板）進行特征提取，形成7個特征集。

Step2.對每個基分類器fi（i＝1，2，…，m），利用Step1得到的7種特征集，對多義詞進行消歧分類實驗，將消歧效果好的特征集作為與自己相適應的特征集。

Step3.對基分類器fi（i＝1，2，…，m）確定在其相應的特征集下，在度量層計算出每個類別sj的概率值，并按式（10）計算相應的“自信”閾值θi。

Step4.For Each sjin S

Step5.對度量層的sj（j＝1，2，…，n）進行排序，選出sumj最大的那個sj作為分類結(jié)果。

5 實驗設計與實現(xiàn)

選取的實驗語料為北京大學計算語言學研究所標注的《人民日報》詞義標注語料庫，實驗選取了2000年11月和12月兩個月的標注語料共20M，其中80%（50天）作為訓練語料，20%作為測試語料。同樣從語料中統(tǒng)計出現(xiàn)頻率大于500的動詞，選取如表1所示的15個作為實驗對象，其中CSD表示《現(xiàn)代漢語語義詞典》。

表1 15個實驗用的多義詞

（1）特征模板設計與特征提取。上下文知識選擇了“整句范圍詞性”、“整句范圍詞”、“整句范圍詞性＋詞”、“（－2，＋2）范圍詞性”、“（－2，＋2）范圍詞”、“（－2，＋2）范圍詞性＋詞”、“依存句法”等七種特征，作為備選特征。

融合實驗結(jié)果比較的主要技術指標是：準確率＝正確標注數(shù)／標注總數(shù)。

（2）實驗過程。實驗過程遵循多分類器系統(tǒng)構(gòu)建的三個步驟：數(shù)據(jù)預處理，基分類器訓練，融合基分類器。

數(shù)據(jù)預處理：包括特征提取和數(shù)據(jù)規(guī)范化，這些操作在模型訓練和測試中都會用得到。

基分類器訓練：針對貝葉斯、向量空間、最大熵等三種消歧模型，在備選樣本集中進行模型的訓練，取得效果理想的基分類器。

分類器融合：用上述提出的動態(tài)自適應加權投票分類器融合方法將生成的基分類器組合在一起。

（3）實驗設計。通過分析，我們設計了以下四種實驗，對本文所提的分類器融合模型進行驗證。

實驗一：成員分類器選擇貝葉斯、向量空間、最大熵三種模型，舍棄決策樹分類算法，因為決策樹算法性能不高，會影響集成分類器的效果。多分類器集成方法采用了最大投票（MV），改進的投票（IV），性能加權投票（PWV）和動態(tài)自適應加權投票（AWA）

實驗二：只選取平均結(jié)果在85%以上的單分類器作為基分類器，即貝葉斯、最大熵進行實驗。由于只有兩種基分類器無法使用簡單投票法進行集成，實驗選擇改進的投票（IV）和動態(tài)自適應加權投票（AWA）的融合算法。

實驗三：選擇最大熵分類器，在七種備選特征集上分別進行訓練，得到不同的模型，然后使用最大投票（MV）、改進的投票（IV）、性能加權投票（PWV）和動態(tài)自適應加權投票（AWA）的融合算法進行計算。

實驗四：選擇貝葉斯分類器，在七種備選特征集上進行分別訓練，得到不同的模型，然后使用最大投票（MV）、改進的投票（IV）、性能加權投票（PWV）和動態(tài)自適應加權投票（AWA）的融合算法進行計算。

6 實驗結(jié)果分析比較

實驗一結(jié)果如表2所示。

表2 實驗一結(jié)果

續(xù)表

由實驗一的結(jié)果可以看出，融合分類器的平均準確率從高到低依次為AWA、IV、PWV、MV。其中，IV、PWV、AWA結(jié)果優(yōu)于最佳單分類器最大熵（91.08%）［5］，效果最好的 AWA 比之高出0.53%。進一步分析，可以得出以下結(jié)論：

（1）最大投票方法表現(xiàn)較差的原因是它只利用了單分類器結(jié)果層的信息。雖然性能最佳的單分類器超出其他成員分類器許多，但在最大投票中卻不占優(yōu)勢，因為規(guī)則是“一人一票”。就像真理掌握在少數(shù)人手中，卻不被大多數(shù)人接受。

（2）改進的投票方法成功的原因在于結(jié)果的融合是在度量層。該方法充分考慮了單分類器給出的義項概率估計值會提供潛在的有用信息，體現(xiàn)出了性能好的單分類器的優(yōu)勢。

（3）性能加權投票略遜于改進的投票方法。雖然其結(jié)果的融合也是在度量層，但它在融合結(jié)果時加了一個權值，這樣就引入了人為的噪聲。

（4）動態(tài)自適應加權投票結(jié)果融合也是在度量層。其之所以獲得最終的成功，在于權值的設定去掉了人為的因素，而是根據(jù)各基分類器自身情況自動決定的。

實驗二的結(jié)果如表3所示。

表3 實驗二結(jié)果

在去掉了性能較差的向量空間模型之后，改進的投票方法和動態(tài)自適應加權投票的正確率都獲得了提升。究其原因，在于性能不好的單分類器扯了“大家”的后腿，其提供的互補信息，不足以彌補性能低下帶來的損失。而且動態(tài)自適應加權投票仍然領先于改進投票方法，充分說明了本文所提算法的有效性。深入分析原因，得到如下觀點：AWA之所以有效可以從它的模型算法看出來，它克服了性能好的單分類器“過度自信”的缺點，同時又照顧了性能好的單分類器的權重，但如果單分類器表現(xiàn)出“不自信”就進行懲罰，降低其權重。算法關鍵就在自調(diào)節(jié)性上。

本實驗結(jié)果，為下一步的深入研究指明了方向，成員分類器一定要選擇性能好的單分類器，否則構(gòu)造的集成分類器精確度也不會很高。

實驗三的結(jié)果如表4所示。

表4 實驗三結(jié)果

由實驗三的結(jié)果可以看出，集成分類器的平均準確率從高到底依次為 MV、PWV、IV、AWA。所有集成分類器的結(jié)果均優(yōu)于單分類器最大熵的最佳性能（91.08%）［5］。這說明特征之間的互補信息，幫助提高了最終融合結(jié)果的準確率。在一種特征空間中難以識別的模式，可能在另一種特征空間中很容易識別。

實驗四結(jié)果如表5所示。

由實驗四的結(jié)果可以看出融合分類器的平均準確率從高到底依次為AWA、PWV、IV、MV。除了AWA超出了貝葉斯最佳性能（87.66%），其他集成分類器均略低于最佳性能。

表5 實驗四結(jié)果

綜合實驗三的結(jié)果和實驗四的結(jié)果可以看出，一種規(guī)則并不是放之四海而皆準的，在一種模型上適用的融合方法，并不一定在另一種模型上適用。但通過這兩個實驗也可以看出，多分類器融合方法能夠提高單分類器的效果。

本文在分析了前人分類器融合算法的基礎上，結(jié)合詞義消歧的任務提出了一種動態(tài)自適應加權投票的多分類器融合算法。通過實驗檢測表明，所提出的分類器融合模型充分利用了各基分類器輸出的義項概率值，提高了詞義消歧的準確率，分析其原因主要在于模型本身的自調(diào)節(jié)性上。另外，實驗也表明，一種融合規(guī)則并不是適合任意的多分類器進行融合。

［1］Thomas G.Dietterich.Machine learning research：Four current directions［J］.AI Magazine，1997，18（4）：97－136.

［2］吳云芳，王淼，金澎，等.多分類器集成的漢語詞義消歧研究［J］.計算機研究與發(fā)展，2008，45（8）：1354－1361.

［3］全昌勤，何婷婷，姬東鴻，等.基于多分類器決策的詞義消歧方法［J］.計算機研究與發(fā)展，2006，43（5）：933－939.

［4］Latinne P，Debeir O，Decaestecker C.Combining Different Methods and Numbers of Weak Decision Trees［J］.Pattern Analysis ＆ Applications，2002，5（2）：201－209.

［5］張仰森，郭江.四種統(tǒng)計詞義消歧模型的分析與比較.北京信息科技大學學報，2011，26（2）：13－18.

［6］Kilgarriff A，Rosenzweig J.Framework and results for English SenSeval ［J］. Computers and the Humanities 34：15－48，2000.

［7］Xiaojie Wang， Yuji Matsumoto.Trajectory based word sense disambiguation ［C／OL］／／COLING 2004：Proceedings of the 20th International Conference on Computational Linguistics. http：／／aclweb. org／anthology／C／C04／C04－1130.pdf.