基于隱馬爾可夫模型的中文分詞

吳帥，潘海珍

（上饒師范學院數(shù)學與計算機科學學院，上饒 334001）

0 引言

中文分詞是中文自然語言處理中的基礎(chǔ)環(huán)節(jié)，由于中文的詞語之間沒有明顯的分隔符，使得中文相對其他語言的分詞難度更大，中文分詞的質(zhì)量和分詞效率將會影響建立在其基礎(chǔ)上的高級應(yīng)用。中文分詞也是中文自然語言處理中的瓶頸問題，解決好了中文分詞，將會給其他相關(guān)領(lǐng)域的研究帶來突破性的發(fā)展。中文分詞的研究工作已經(jīng)持續(xù)了三十多年，分詞的準確度和速度得到非常大的提高，目前比較流行且效果比較好的方法是基于統(tǒng)計的機器學習方法。

隱馬爾可夫模型是一種基于統(tǒng)計的機器學習模型，可以通過觀測數(shù)據(jù)來預(yù)測數(shù)據(jù)最可能的原始狀態(tài)，這點正好滿足中文分詞的要求，將漢字序列切分成一個個獨立且最合理的詞。首先為中文文本建立統(tǒng)計模型，利用隱馬爾可夫假設(shè)簡化模型，降低計算的復(fù)雜度，最后通過Viterbi算法來預(yù)測最佳的詞方式。本文分析了隱馬爾可夫模型實現(xiàn)中文分詞的基本原理、過程及分詞模型的Python實現(xiàn)。

1 中文分詞算法

近年來，專家學者們提出了許多的中文分詞算法，可以歸納為三大類：基于詞典匹配的算法、基于統(tǒng)計的算法和基于理解的算法?；谠~典匹配的算法是按照一定的策略將文本中準備分析的字符串與詞典中的詞語進行匹配，若在詞典中找到某個字符串，則識別出文本中的詞語；基于統(tǒng)計的算法是基于人的直觀理解，任意相鄰的漢字出現(xiàn)的頻率越高，說明它們組成詞的可能性就越大；基于理解的算法是讓計算機模擬人對句子的理解，達到識別詞的效果，分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧義現(xiàn)象，該方法還處于理論研究，未有實際的應(yīng)用。中文分詞中存在歧義識別和未登錄詞識別兩大難點。各類算法的具體比較見表1。

表1 三類分詞算法的比較

2 隱馬爾可夫模型概述

2.1 隱馬爾可夫模型

隱馬爾可夫模型（Hidden Markov Model，HMM）描述了含有隱藏變量的馬爾可夫隨機過程，該模型涉及兩個序列和三個概率矩陣，即可觀察的觀測序列O、隱藏的狀態(tài)序列Z、初始的狀態(tài)概率矩陣π，狀態(tài)轉(zhuǎn)移概率矩陣A及狀態(tài)生成觀測的概率矩陣B。HMM可表示為{O,Z,π,A,Bλ=(π,A,B)}，λ=(π,A,B)決定 HMM 模型，PIπ和A決定觀測序列，B決定狀態(tài)序列。

HMM具有三個基本問題：概率計算問題、學習問題和預(yù)測問題。概率計算問題是計算在模型λ下觀測序列O的概率P(O/λ)，直接求解的方法不可行，計算量非常大，有效的方法是前向-后向算法。學習問題是已知觀測 O 估計模型λ=(π,A,B)λ=(π,A,B)的參數(shù)，有監(jiān)督可用極大似然估計法、無監(jiān)督可用Baum-Welch算法。預(yù)測問題是給定觀測序列，求出最有可能的對應(yīng)的狀態(tài)序列，可用近似算法和Viterbi算法。

2.2 應(yīng)用原理

中文的詞是由漢字構(gòu)成，每個漢字在構(gòu)詞時都有一個確定的位置。字在詞中出現(xiàn)的位置可用BMSE四種標簽表示，B表示詞的開始位置、M表示多字詞的中間位置、E表示詞的結(jié)束位置，S表示字單獨成詞。如“明月湖的荷花露出迷人的笑臉”對應(yīng)的詞位標簽序列為“BMESBEBESBE”，分詞結(jié)果為“明月湖/的/荷花/露出/迷人/的/笑臉”。

文本中的每個字構(gòu)成觀測序列，每個字的詞位標注構(gòu)成狀態(tài)序列。中文分詞就轉(zhuǎn)換為求解字的詞位標注問題，基于已加工好的語料庫訓，訓練得到HMM的參數(shù)λ=(π,A,B)，再通過Viterbi算法得到待分詞文本的詞位標注序列，從而得到最佳分詞。

3 HMM在中文分詞中的實現(xiàn)

隱馬爾可夫模型實現(xiàn)中文分詞主要由三個步驟組成，即訓練、預(yù)測和分詞，如圖1所示。

圖1 HMM的中文分詞過程

（1）訓練

通過統(tǒng)計語料庫中相關(guān)信息訓練HMM中的三個參數(shù)PI、A和B。A表示字的詞位狀態(tài)轉(zhuǎn)移矩陣，B表示詞位到詞的混淆矩陣。從語料庫中可以獲得每個詞位出現(xiàn)的次數(shù)，每個字符出現(xiàn)的次數(shù)，通過頻率代替概率得到三個參數(shù)的值。

公式中Z={B,M,E,S}為字的詞位序列，O={字符集}為觀測序列，freq(Zi,Zj)表示ZiZj在語料庫中相鄰?fù)瑫r出現(xiàn)的次數(shù)，freq(Oj,Zi)表示字符Oj和Zi某個詞位同時出現(xiàn)的次數(shù)。HMM在分詞中的狀態(tài)轉(zhuǎn)移概率矩陣為：

計算過程中會出現(xiàn)頻數(shù)為零或很小的值，為了避免出現(xiàn)計算結(jié)果的下溢，對頻數(shù)取對數(shù)，如Aij=log(freq程序中采用的是北京大學加工的1998年《人民日報》語料庫，該語料庫具有較為完整的加工規(guī)范說明，目前較為成熟，被研究人員普遍采用。

若訓練樣本的數(shù)據(jù)不足，混淆矩陣B會過于稀疏。矩陣B的形式為：

給定觀測序列學習HMM模型參數(shù)，采用Baum-Welch算法[4]訓練分詞模型，參數(shù)估計公式分別為：

算法的實現(xiàn)代碼如下：

（2）預(yù)測

從語料庫中訓練HMM分詞模型后，可通過Viter?bi算法來預(yù)測未知語言中漢字的詞位標記從而達到分詞的目的，可以求得全局最優(yōu)的分詞結(jié)果。Viterbi算法實際是用動態(tài)規(guī)劃來求解隱馬爾可夫模型預(yù)測問題，即用動態(tài)規(guī)劃求概率最大路徑。δt定義在時刻t狀態(tài)為i的所有單個路徑(i1,i2,…,it) 中的概率最大值為：

遞推公式為：

定義在t狀態(tài)為i的所有單個路徑中概率最大的路徑的第t-1個結(jié)點為：

（3）分詞

一般情況下，完成文本的標注序列后，需要進行分詞，分詞的方法是從左到右，采用最大匹配模式。程序中分詞的實現(xiàn)如下所示。

基于HMM的分詞模型經(jīng)常會將一起出現(xiàn)頻率高的字組切分成詞，如“我的”、“每個”等，會出現(xiàn)錯誤分詞的現(xiàn)象。有訓練語料時，訓練模型的時間較短。HMM是生成模型，即使沒有先驗語料，也可以使用EM方法進行估計，估計原則是使每個序列的P(X)最大，這個優(yōu)勢是判別模型無法比擬的。

4 結(jié)語

本文分析隱馬爾可夫模型的理論基礎(chǔ)，論述基于隱馬爾可夫模實現(xiàn)中文分詞的基本原理。HMM分詞模型只考慮詞前后關(guān)系，未考慮詞的上下文之間的關(guān)系，但在中文分詞中表現(xiàn)較好，HMM可以求得全局最優(yōu)的分詞結(jié)果。中文分詞涉及的范圍非常廣，由于中文本身的特殊性，中文分詞算法在不斷地發(fā)展和完善，在分詞速度更快、精度更高、歧義詞、未登錄詞、新詞的識別等方面會得到突破。