層次化的隱馬爾可夫模型

在自然語言處理等應(yīng)用中，由于處理序列具有遞歸特性，尤其當(dāng)序列長度比較大時(shí)，HMM的復(fù)雜度將會(huì)急劇增大，因此層次化隱馬爾可夫模型（HHMM）被提出了。

我們知道HMM是由兩個(gè)隨機(jī)過程構(gòu)成的，而HHMM是由多層隨機(jī)過程構(gòu)成的。在HHMM中每個(gè)狀態(tài)就是一個(gè)獨(dú)立的HHMM，因此一個(gè)HHMM的狀態(tài)就產(chǎn)生一個(gè)觀察序列，而不是一個(gè)觀察符號(hào)。HHMM通過狀態(tài)遞歸地產(chǎn)生觀察序列，一個(gè)狀態(tài)可以激活下層狀態(tài)中的某個(gè)狀態(tài)，而被激活的狀態(tài)又可以再激活下層的狀態(tài)，直至到達(dá)某個(gè)特定的狀態(tài)，這一遞歸過程結(jié)果。該特定狀態(tài)成為生產(chǎn)狀態(tài)，只有生產(chǎn)狀態(tài)才能通過常規(guī)的HMM機(jī)制，即根據(jù)輸出符號(hào)的概率分布產(chǎn)生可觀察的輸出符號(hào)。不直接產(chǎn)生可觀察符號(hào)的隱藏狀態(tài)稱作內(nèi)部狀態(tài)，不同層次之間的狀態(tài)轉(zhuǎn)移叫垂直轉(zhuǎn)移，同一層次上狀態(tài)之間的轉(zhuǎn)移叫做水平轉(zhuǎn)移。特殊的終止?fàn)顟B(tài)負(fù)責(zé)控制轉(zhuǎn)移過程返回到激活該層狀態(tài)轉(zhuǎn)移的上層狀態(tài)。

這一遞歸過程將形成一個(gè)生產(chǎn)狀態(tài)序列，而每個(gè)生產(chǎn)狀態(tài)生成一個(gè)觀察輸出符號(hào)，因此生產(chǎn)狀態(tài)序列將為頂層狀態(tài)生成一個(gè)觀察輸出序列，HHMM的樹狀結(jié)構(gòu)如圖所示：

HHMM的樹狀結(jié)構(gòu)

最上面的q1就是一個(gè)能產(chǎn)生一個(gè)觀察序列的HHMM狀態(tài)，而q1產(chǎn)生的這個(gè)結(jié)構(gòu)也是一個(gè)獨(dú)立了HHMM，圖中畫雙圈的就是終止?fàn)顟B(tài)，用于控制轉(zhuǎn)移過程返回到激活該層狀態(tài)的上層狀態(tài)。其它狀態(tài)為內(nèi)部狀態(tài)。終止?fàn)顟B(tài)與生產(chǎn)狀態(tài)不同，圖中并沒有畫出生產(chǎn)狀態(tài)。

為了避免誤解，我特意找了另一張HHMM的圖對(duì)比著來看：

HHMM

圖中畫雙圈的是終止?fàn)顟B(tài)，能夠輸出符號(hào)的是生產(chǎn)狀態(tài)，不能輸出符號(hào)且不是終止?fàn)顟B(tài)的被叫做內(nèi)部狀態(tài)。

像HMM一樣，HHMM中也有三個(gè)基本問題，第一個(gè)就是快速地計(jì)算觀察序列的概率，第二個(gè)就是求解模型最有可能的狀態(tài)序列，第三個(gè)就是在給定一個(gè)HHMM的結(jié)構(gòu)和一個(gè)或多個(gè)觀察序列的條件下，估計(jì)模型的最優(yōu)參數(shù)。

馬爾可夫網(wǎng)絡(luò)（馬爾可夫隨機(jī)場(chǎng)）

前面其實(shí)是講過馬爾可夫模型的，馬爾可夫網(wǎng)絡(luò)不同于馬爾可夫模型，我們來回顧一下前面的圖：

常見的概率圖模型

我們知道馬爾可夫模型和隱馬爾科夫模型HMM都是有向圖模型，而馬爾可夫網(wǎng)絡(luò)是無向圖模型。

馬爾可夫網(wǎng)絡(luò)和貝葉斯網(wǎng)絡(luò)有類似之處，也可用于表示變量之間的依賴關(guān)系，但它又與貝葉斯網(wǎng)絡(luò)有所不同。一方面它可以表示貝葉斯網(wǎng)絡(luò)無法表示的一些依賴關(guān)系，如循環(huán)依賴；另一方面，它不能表示貝葉斯網(wǎng)絡(luò)能夠表示的某些關(guān)系，如推導(dǎo)關(guān)系。

一個(gè)簡單的無向圖

馬爾可夫網(wǎng)絡(luò)是一組有馬爾可夫性質(zhì)的隨機(jī)變量的聯(lián)合概率分布模型，由一個(gè)無向圖G（如上圖）和定義在G上的勢(shì)函數(shù)組成。

無向圖的每個(gè)頂?shù)妆硎疽粋€(gè)隨機(jī)變量，每條邊表示兩個(gè)隨機(jī)變量之間的依賴關(guān)系。

首先簡單說一下什么是子圖，假設(shè)有兩個(gè)圖，如果第二個(gè)圖的頂點(diǎn)都是第一個(gè)圖的頂點(diǎn)，第二個(gè)圖的邊也都是第一個(gè)圖的邊，那么第二個(gè)圖就是第一個(gè)圖的子圖。

如果一個(gè)子圖任意兩個(gè)頂點(diǎn)都有邊相連，那么這個(gè)子圖就是一個(gè)完全子圖，一個(gè)完全子圖又稱為一個(gè)團(tuán)，一個(gè)團(tuán)的完全子圖叫子團(tuán)。

因?yàn)閳D是無向的，所以我們不能用條件概率對(duì)模型進(jìn)行參數(shù)化，而是使用團(tuán)勢(shì)能函數(shù)或簡稱勢(shì)函數(shù)進(jìn)行參數(shù)化，每個(gè)團(tuán)都對(duì)應(yīng)一個(gè)勢(shì)函數(shù)，表示團(tuán)的一個(gè)狀態(tài)。

我們的目的是什么？是對(duì)無向圖進(jìn)行參數(shù)化，得到概率分布，進(jìn)而描述出整個(gè)馬爾科夫網(wǎng)絡(luò)。拿上面的那個(gè)簡單的無向圖舉例，這個(gè)圖可以拆成兩個(gè)團(tuán)，一個(gè)是XC1 = {x1, x2}，另一個(gè)是XC2 = {x1, x3, x4}，這個(gè)馬爾可夫網(wǎng)絡(luò)H的分布概率PΦ(x1, x2, x3, x4)可以由這兩個(gè)團(tuán)的團(tuán)勢(shì)能函數(shù)Φ(XC)進(jìn)行因子化，PΦ(x1, x2, x3, x4)可以看做是這個(gè)馬爾可夫網(wǎng)絡(luò)H的一個(gè)吉布斯分布：

Z是歸一化常量，稱為劃分函數(shù)，不重要。

那然后我們只需要確定每個(gè)團(tuán)的團(tuán)勢(shì)能函數(shù)Φ(XC)了。我們一般將團(tuán)勢(shì)能函數(shù)Φ(XC)定義為：Φ(XC) = exp{-E(XC)}，其中-E(XC)叫做團(tuán)XC的能量函數(shù)。

這樣我們就得到了整個(gè)圖模型的吉布斯分布。而且因?yàn)槭阶永锸沁B乘，我們可以通過取對(duì)數(shù)，將因子化的乘積運(yùn)算轉(zhuǎn)變?yōu)榧臃ㄟ\(yùn)算：

最大熵模型

前面講熵的時(shí)候我們就提到過最大熵模型，它的基本原理是：在只掌握關(guān)于未知分布的部分信息的情況下，符合已知知識(shí)的概率分布可能有多個(gè)，但使熵值最大的概率分布最真實(shí)的反映了事件的分布情況，因?yàn)殪囟x了隨機(jī)變量的不確定性，當(dāng)熵最大時(shí)，隨機(jī)變量最不確定，最難準(zhǔn)確地預(yù)測(cè)其行為。也就是說，在已知部分信息的前提下，關(guān)于未知分布最合理的推斷應(yīng)該是符合已知信息最不確定或最大隨機(jī)的推斷。

最大熵模型的推導(dǎo)比較復(fù)雜，這里盡量不列公式，而是側(cè)重于把原理講清楚。

這里我們先引入特征的概念，簡單的說，就是一個(gè)待消歧問題可能的候選結(jié)果與上下文信息的一個(gè)對(duì)應(yīng)關(guān)系。就是在怎樣的上下文條件下，這個(gè)待消歧問題的結(jié)果是什么。

最大熵模型說，在已知部分信息的前提下，關(guān)于未知分布最合理的推斷應(yīng)該是符合已知信息最不確定或最大隨機(jī)的推斷，實(shí)際上就是下面這個(gè)式子：

首先式子左側(cè)的是條件概率，a就是『待消歧問題的結(jié)果』，b就是『上下文條件』，這個(gè)條件概率就是最大熵模型所要描述的概率分布，即知道在特定上下文條件下，某待消歧問題的結(jié)果。

然后式子的右側(cè)就是所謂的『最不確定或最大隨機(jī)的推斷』了，我們選擇所建模型中所有與已知樣本中的概率分布相吻合的概率分布中熵最大的推斷作為最終的結(jié)果，P就是這些符合條件的模型的集合。

我們建的模型中p(b)的概率分布必須符合已知訓(xùn)練樣本中的概率分布，所以我們直接代入已知訓(xùn)練樣本中的概率分布，也即式子中帶了估計(jì)符號(hào)的p(b)。

其實(shí)上面那個(gè)式子就是我們需要求最大值的目標(biāo)函數(shù)，接下來的問題就是如何確定所建模型中所有與已知樣本中的概率分布相吻合的概率分布的集合P。

最大熵模型也說，在已知部分信息的前提下，關(guān)于未知分布最合理的推斷應(yīng)該是符合已知信息最不確定或最大隨機(jī)的推斷，那什么叫做『符合已知信息』？

符合已知信息也即，所建立模型的概率分布應(yīng)該與已知樣本中的概率分布相吻合（這里用的是聯(lián)合概率分布），而我們通過所建立模型中『特征』的期望值和已知樣本中『特征』的期望值作比較。如果特征對(duì)于模型是有用的，那這兩個(gè)期望值應(yīng)當(dāng)是相等的。

而且我們往往選擇不止一個(gè)特征，比如，我們選取k種在建模過程中對(duì)輸出有影響的特征，分別表示出這k種特征下所建立模型中『特征』的期望值和已知樣本中『特征』的期望值，
令其相等，那么也就相應(yīng)的產(chǎn)生了k個(gè)約束條件，符合k條已知信息。

這樣，問題就變成了在滿足k個(gè)約束條件下求解目標(biāo)函數(shù)的最優(yōu)解的問題，而拉格朗日乘子法可以用于解決這一問題。也即如下式：

接下來是最大熵模型的訓(xùn)練，最大熵模型訓(xùn)練的任務(wù)就是選取有效的特征f以及權(quán)重λ。由于可以利用歧義點(diǎn)所在的上下文信息（如詞形、詞性、窗口大小等）作為特征條件，而歧義候選往往也有多個(gè)，因此各種特征條件和歧義候選可以組合成很多特征函數(shù)，必須對(duì)其進(jìn)行篩選。

比如從候選特征集中選擇那些訓(xùn)練數(shù)據(jù)中出現(xiàn)頻次超過一定閾值的特征，或者利用互信息作為評(píng)價(jià)尺度從候選特征集中選擇滿足一定互信息要求的特征等等。

而對(duì)于權(quán)重參數(shù)λ，最開始的訓(xùn)練方法是通用迭代算法（Generalized Iterative Scaling，GIS），GIS實(shí)際上是一個(gè)典型的期望最大化算法（EM），簡單的說，就是在第零次迭代時(shí)，在遵循限制條件的前提下任意的初始化參數(shù)λ，然后用第N次迭代的模型來估算訓(xùn)練數(shù)據(jù)中的分布。如果超過了實(shí)際的，就把相應(yīng)的參數(shù)減小，否則，將他們變大。重復(fù)這個(gè)過程直到收斂。

GIS算法每次的迭代時(shí)間都很長，需要迭代很多次才能收斂，而且不太穩(wěn)定，所以在實(shí)際應(yīng)用中很少有人使用。改進(jìn)迭代算法IIS（Improved Iterative Scaling）等，在GIS的基礎(chǔ)上進(jìn)行了優(yōu)化，不過計(jì)算量仍然非常巨大。

最大熵馬爾可夫模型

最大熵馬爾可夫模型（maximum-entropy Markov model，MEMM）又稱條件馬爾可夫模型（conditional Markov model，CMM）。它結(jié)合了隱馬爾可夫模型和最大熵模型的共同特點(diǎn)，被廣泛應(yīng)用于處理序列標(biāo)注問題。

McCallum認(rèn)為，在HMM模型中存在兩個(gè)問題，一個(gè)是，在很多序列標(biāo)注任務(wù)中，尤其是不能枚舉觀察輸出時(shí)，需要用大量的特征來刻畫觀察序列。比如識(shí)別一個(gè)公司名的時(shí)候，除了通過單詞，還要考慮到大寫字母、結(jié)尾詞、詞性、格式、在文本中的位置等。也就是說，我們需要用特征對(duì)觀察序列輸出進(jìn)行參數(shù)化。

然后是，在很多自然語言處理任務(wù)中，需要解決的問題是在已知觀察序列的情況下求解狀態(tài)序列，HMM采用生成式的聯(lián)合概率模型P(ST,OT)來求解這種概率問題，這種方法不適合處理用很多特征描述觀察序列的情況。為此，MEMM直接采用條件概率模型P(ST|OT)（所以MEMM不是一種生成式模型），從而使觀察輸出可以用特征表示，借助最大熵模型進(jìn)行特征選取。

下圖展示了HMM和MEMM的區(qū)別：

HMM與MEMM依存圖對(duì)照

在上一篇我們說過HMM有三個(gè)假設(shè)：

• 有限歷史性假設(shè)：也即一階馬爾可夫模型，認(rèn)定t時(shí)刻出現(xiàn)的狀態(tài)只與t-1時(shí)刻的狀態(tài)有關(guān)
• 齊次性假設(shè)：假定P(s(i+1)|si)=P(s(j+1),sj)
• 輸出獨(dú)立性假設(shè)：假定輸出僅與當(dāng)前狀態(tài)有關(guān)

其中包括輸出獨(dú)立性假設(shè)，認(rèn)為當(dāng)前時(shí)刻的觀察輸出只取決于當(dāng)前狀態(tài)，而在MEMM中，當(dāng)前時(shí)刻的觀察輸出還可能取決于前一時(shí)刻的狀態(tài)，MEMM解決了HMM輸出獨(dú)立性假設(shè)的問題。實(shí)際上，MEMM也舍棄了齊次性假設(shè)，不再用生成式的聯(lián)合概率模型P(ST,OT)來求解，而是直接采用條件概率模型P(ST|OT)。

假設(shè)已知觀察序列O1O2...OT，要求解狀態(tài)序列S1S2...ST，并使條件概率P(S1S2...ST|O1O2...OT)最大。在MEMM中，將這一概率因子化為馬爾可夫轉(zhuǎn)移概率，從上面的圖中也可以看出，在MEMM中，當(dāng)前時(shí)刻的狀態(tài)St取決于前一時(shí)刻的狀態(tài)S(t-1)和當(dāng)前時(shí)刻的觀察輸出Ot，所以：

這樣，MEMM中的MM有了，接下來是ME，我們還記得上一篇講最大熵模型的時(shí)候，講到，最大熵模型解決的是給定上下文條件下，獲得待消歧問題結(jié)果的問題，那么在現(xiàn)在情況下，前一時(shí)刻的狀態(tài)S(t-1)和當(dāng)前時(shí)刻的觀察輸出Ot就是上下文，而當(dāng)前時(shí)刻的狀態(tài)St就是待消歧問題，所以我們依照這個(gè)思想通過最大熵分類器建模：

前面講過最大熵模型可以通過GIS來進(jìn)行求解，GIS是一種EM算法，HMM中用于參數(shù)估計(jì)的前后向算法也是一種EM算法，在這里，前向后向算法修改后可用于MEMM的狀態(tài)轉(zhuǎn)移概率估計(jì)，這里具體的計(jì)算方法較為復(fù)雜，還用到了維特比算法的思想，這里不再深入講解。

MEMM是有向圖和無向圖的混合模型，其主體還是有向圖框架，與HMM相比，MEMM最大的優(yōu)點(diǎn)在于它允許使用任意特征刻畫觀察序列，因?yàn)樵贛EMM里，處理觀察序列的實(shí)際上是最大熵模型的套路，最大熵模型在推導(dǎo)時(shí)就考慮了處理多種特征的情況。

MEMM的缺點(diǎn)在于存在標(biāo)記偏置問題（label bias problem），MEMM解決了HMM輸出獨(dú)立性假設(shè)的問題，但是只解決了觀察值獨(dú)立的問題，而狀態(tài)之間的假設(shè)--有限歷史性假設(shè)，則是標(biāo)注偏置問題產(chǎn)生的根源。

什么是標(biāo)注偏置問題？比如這樣的狀態(tài)轉(zhuǎn)換概率分布：

路徑1-1-1-1的概率：0.40.450.5=0.09
路徑2-2-2-2的概率：0.018
路徑1-2-1-2的概率：0.06
路徑1-1-2-2的概率：0.066

由此看來，最優(yōu)的路徑是1-1-1-1，但是實(shí)際上，狀態(tài)1偏向于轉(zhuǎn)移到狀態(tài)2，而狀態(tài)2總傾向于停留在狀態(tài)2，這就是所謂的標(biāo)注偏置問題，由于分支數(shù)不同，概率的分布不均衡，導(dǎo)致狀態(tài)的轉(zhuǎn)移存在不公平的情況。條件隨機(jī)場(chǎng)CRF則解決了標(biāo)注偏置問題，是進(jìn)一步優(yōu)化。

這里給出HMM、MEMM、CRF的對(duì)比圖：

HMM

可以清晰的看到HMM的有限歷史性假設(shè)（認(rèn)為Yt只取決于Y(t-1)）和輸出獨(dú)立性假設(shè)（認(rèn)為Xt只取決于Yt）。

MEMM

MEMM克服了HMM的輸出獨(dú)立性假設(shè)，不再認(rèn)為Xt只取決于Yt。但是仍然存在有限歷史性假設(shè)，認(rèn)為Yt只取決于Y(t-1)。

CRF

CRF模型解決了標(biāo)注偏置問題，去除了HMM中兩個(gè)不合理的假設(shè)（有限歷史性假設(shè)、輸出獨(dú)立性假設(shè)），當(dāng)然，模型相應(yīng)得也變復(fù)雜了。

條件隨機(jī)場(chǎng)

條件隨機(jī)場(chǎng)（conditional random fields）由J.Lafferty提出，是一種典型的判別模型，就是對(duì)于給定的輸出標(biāo)識(shí)序列Y和觀測(cè)序列X；條件隨機(jī)場(chǎng)通過定義條件概率P(Y|X)，而不是聯(lián)合概率分布P(X,Y)來描述模型。CRF也可以看做一個(gè)馬爾可夫隨機(jī)場(chǎng)（無向圖模型、馬爾可夫網(wǎng)絡(luò)）。

我們先給出一張更清晰的CRF的鏈?zhǔn)浇Y(jié)構(gòu)圖：

CRF的鏈?zhǔn)浇Y(jié)構(gòu)圖

如果以觀察序列X為條件，條件隨機(jī)場(chǎng)中，每一個(gè)隨機(jī)變量Yv都滿足以下馬爾可夫特性：

其中，w~v表示兩個(gè)結(jié)點(diǎn)在圖中是臨近節(jié)點(diǎn)。也即，就像前面所提到的，在條件隨機(jī)場(chǎng)中，有限歷史性假設(shè)也被舍棄了，Yt不再只取決于前一時(shí)刻的臨近節(jié)點(diǎn)Y(t-1)，CRF統(tǒng)計(jì)了全局概率，在做歸一化時(shí)，考慮了數(shù)據(jù)在全局的分布，而不是僅僅在局部歸一化，是全局最優(yōu)的解，這樣就解決了MEMM中的標(biāo)記偏置的問題。

參考了標(biāo)注偏置問題(Label Bias Problem)和HMM、MEMM、CRF模型比較，舉一個(gè)例子，對(duì)于一個(gè)標(biāo)注任務(wù)『我愛北京天安門』：假設(shè)標(biāo)注為" s c b e b c e"。

對(duì)于HMM的話，其判斷這個(gè)標(biāo)注成立的概率為：
P= P(s轉(zhuǎn)移到c)*P('我'表現(xiàn)為s)* P(c轉(zhuǎn)移到b)*P('愛'表現(xiàn)為c)* ...
訓(xùn)練時(shí)，要統(tǒng)計(jì)狀態(tài)轉(zhuǎn)移概率矩陣和符號(hào)發(fā)射概率矩陣。

對(duì)于MEMM的話，其判斷這個(gè)標(biāo)注成立的概率為：
P= P(s轉(zhuǎn)移到c|'我'表現(xiàn)為s)*P('我'表現(xiàn)為s)* P(c轉(zhuǎn)移到b|'愛'表現(xiàn)為c)*P('愛'表現(xiàn)為c)*...
訓(xùn)練時(shí)，要統(tǒng)計(jì)條件狀態(tài)轉(zhuǎn)移概率矩陣和符號(hào)發(fā)射概率矩陣。

前面也給出了這個(gè)圖：

HMM與MEMM依存圖對(duì)照

MEMM中，除了t-1時(shí)刻的狀態(tài)，當(dāng)前時(shí)刻的觀察輸出也是當(dāng)前時(shí)刻狀態(tài)的決定條件。

對(duì)于CRF的話，其判斷這個(gè)標(biāo)注成立的概率為：
P= F(s轉(zhuǎn)移到s,'我'表現(xiàn)為s...)
F為一個(gè)函數(shù)，是在全局范圍統(tǒng)計(jì)歸一化的概率而不是像MEMM在局部統(tǒng)計(jì)歸一化的概率。

條件隨機(jī)場(chǎng)的條件概率公式較為復(fù)雜，這里不再給出推導(dǎo)過程。

條件隨機(jī)場(chǎng)也需要解決三個(gè)基本問題：特征的選取、解碼和參數(shù)訓(xùn)練。

前面提到了條件隨機(jī)場(chǎng)就是一個(gè)馬爾可夫隨機(jī)場(chǎng)，這里簡要介紹一下馬爾可夫隨機(jī)場(chǎng)與條件隨機(jī)場(chǎng)的關(guān)系，參考了隨機(jī)場(chǎng)。

馬爾可夫一般是馬爾可夫性質(zhì)的簡稱，它指的是一個(gè)隨機(jī)變量序列按時(shí)間先后關(guān)系依次排開的時(shí)候，第N+1時(shí)刻的分布特性，與N時(shí)刻以前的隨機(jī)變量的取值無關(guān)。

隨機(jī)場(chǎng)包含兩個(gè)要素：位置（site），相空間（phase space）。當(dāng)給每一個(gè)位置中按照某種分布隨機(jī)賦予相空間的一個(gè)值之后，其全體就叫做隨機(jī)場(chǎng)。我們不妨拿種地來打個(gè)比方?！何恢谩缓帽仁且划€畝農(nóng)田；『相空間』好比是種的各種莊稼。我們可以給不同的地種上不同的莊稼，這就好比給隨機(jī)場(chǎng)的每個(gè)『位置』，賦予『相空間』里不同的值。所以，俗氣點(diǎn)說，隨機(jī)場(chǎng)就是在哪塊地里種什么莊稼的事情。

然后類比馬爾可夫隨機(jī)場(chǎng)，還是拿種地打比方，如果任何一塊地里種的莊稼的種類僅僅與它鄰近的地里種的莊稼的種類有關(guān)，與其它地方的莊稼的種類無關(guān)，那么這些地里種的莊稼的集合，就是一個(gè)馬爾可夫隨機(jī)場(chǎng)。

其實(shí)通過上文也能發(fā)現(xiàn)，CRF和MRF（馬爾可夫隨機(jī)場(chǎng)）的關(guān)鍵區(qū)別就在馬爾可夫性質(zhì)上，CRF是在給定需要標(biāo)記的觀察序列的條件下，計(jì)算整個(gè)標(biāo)記序列的聯(lián)合概率分布，而不是在給定當(dāng)前狀態(tài)條件下，定義下一個(gè)狀態(tài)的狀態(tài)分布。

個(gè)人理解，馬爾可夫性質(zhì)就是前面提到的有限歷史性假設(shè)，CRF舍棄掉了有限歷史性假設(shè)，這也就是CRF與MRF（馬爾可夫隨機(jī)場(chǎng)）的最大區(qū)別。

上面的講法可能還會(huì)有誤解，看下面這張圖：

樸素貝葉斯序列化得到HMM，Logistic回歸序列化得到鏈?zhǔn)紺RF，HMM與鏈?zhǔn)紺RF的區(qū)別就類似于樸素貝葉斯算法與Logistic回歸的區(qū)別。CRF舍棄掉了HMM的有限歷史性假設(shè)、輸出獨(dú)立性假設(shè)，由生成模型轉(zhuǎn)變?yōu)榕袆e模型，由概率圖轉(zhuǎn)變?yōu)?strong>函數(shù)擬合（這句是解釋力最強(qiáng)的，如果你真的理解樸素貝葉斯算法和Logistic回歸算法的區(qū)別）。就像Logistic回歸，它不再像樸素貝葉斯算法那樣計(jì)算各種先驗(yàn)條件概率，由貝葉斯公式得到計(jì)算結(jié)果，而是整體的去做函數(shù)擬合，表示出訓(xùn)練集整體的聯(lián)合分布概率，并對(duì)其做期望最大化，這與CRF之于HMM是相同的。

自動(dòng)分詞、命名實(shí)體識(shí)別與詞性標(biāo)注

由于詞是最小的能夠獨(dú)立運(yùn)用的語言單位，而漢語的詞與詞之間沒有任何空格之類的顯式標(biāo)志指示詞的邊界，因此，自動(dòng)分詞問題就成了處理漢語文本時(shí)面臨的首要基礎(chǔ)性問題。

漢語自動(dòng)分詞中的基本問題

簡單地講，漢語自動(dòng)分詞就是讓計(jì)算機(jī)系統(tǒng)在漢語文本的詞與詞之間自動(dòng)加上空格或其他邊界標(biāo)記。漢語自動(dòng)分詞的主要困難來自如下三個(gè)方面：分詞規(guī)范、歧義切分和未登錄詞的識(shí)別。

首先是漢語分詞規(guī)范，『詞是什么』、『什么是詞』這兩個(gè)基本問題飄忽不定，迄今拿不出一個(gè)公認(rèn)的、權(quán)威的詞表來。單字詞與詞素之間的劃界、詞與短語（詞組）的劃界，都是很難解決的問題。不同的人、普通人和語言學(xué)家之間的分詞標(biāo)準(zhǔn)都有很大的差異。

然后是歧義切分問題，梁南元定義了兩種基本的切分歧義類型，一個(gè)是交集型切分歧義，另一個(gè)是組合型切分歧義。

先說交集型切分歧義，漢字串AJB稱作交集型切分歧義，如果滿足AJ、JB同時(shí)為詞。此時(shí)漢字串J稱作交集串。比如『從小學(xué)起』可以切為『從小|學(xué)起』、『從|小學(xué)|起』。

一個(gè)交集型切分歧義所擁有的交集串的集合稱為交集串鏈，它的個(gè)數(shù)稱為鏈長。比如『結(jié)合成分子』，『結(jié)合』、『合成』、『成分』、『分子』均成詞，交集串的集合為『合、成、分』，因此鏈長為3。

接下來是組合型切分歧義，漢字串AB稱為多義組合型切分歧義，如果滿足A、B、AB同時(shí)成詞。比如『起身』，『他站|起|身|來』和『他|明天|起身|去北京』。還有別的例子，比如『才能』、『學(xué)生會(huì)』。而且嚴(yán)格定義的話，需要補(bǔ)充一個(gè)條件，文本中至少存在一個(gè)上下文語境C，在C的約束下，將AB切開成A、B，在語法和語義上都成立。

有人還將交集型切分歧義成為偶發(fā)歧義，多義組合型切分歧義稱為固有歧義。

對(duì)于一些較為復(fù)雜的文本，還可能會(huì)出現(xiàn)交集型歧義內(nèi)包含組合型歧義的情況，有人稱其為混合型切分歧義。

第三個(gè)是未登錄詞問題。未登錄詞又稱生詞（unknown word），未登錄詞可以有兩種解釋，一種是已有的詞表中沒有收錄的詞，另一個(gè)種是已有的訓(xùn)練語料中未曾出現(xiàn)過的詞。由于目前的漢語自動(dòng)分詞系統(tǒng)多采用基于大規(guī)模訓(xùn)練語料的統(tǒng)計(jì)方法，所以這兩種解釋通常可以不用區(qū)分。

未登錄詞可能是：

• 新出現(xiàn)的普通詞，比如一些最先流行在互聯(lián)網(wǎng)上的詞
• 命名實(shí)體，比如人名、地名（包括城市名、省名、國家名等）、組織機(jī)構(gòu)名、時(shí)間和數(shù)字表達(dá)
• 專業(yè)名詞和研究領(lǐng)域名稱，比如三聚氰胺、堰塞湖
• 其他專用名詞，比如新出現(xiàn)的產(chǎn)品、電影、書籍名等等

而且，在漢語分詞中對(duì)命名實(shí)體詞匯的識(shí)別不是只識(shí)別整個(gè)實(shí)體的左右邊界，而是將命名實(shí)體中可獨(dú)立成詞的切分單位正確地識(shí)別出來。比如『2017年3月27日』，這是一個(gè)命名實(shí)體，但在分詞時(shí)不能將其整個(gè)的作為一個(gè)實(shí)體識(shí)別出來，而是要分出『2017|年|3|月|27|日』。比如人名也要把姓和名分開。

漢語分詞方法

漢語自動(dòng)分詞問題被提出來之后，上世紀(jì)80年代及之前，人們提出過很多分詞方法，比如正向最大匹配法、逆向最大匹配法、雙向掃描法、逐詞遍歷法等。這些方法大多數(shù)都是基于詞表進(jìn)行的，因此，一般統(tǒng)稱為基于詞表的分詞方法。

隨著統(tǒng)計(jì)方法的迅速發(fā)展，人們又提出了若干基于統(tǒng)計(jì)模型（比如HMM和n元文法模型）的分詞方法，以及規(guī)則方法與統(tǒng)計(jì)方法相結(jié)合的分詞技術(shù)。

N-最短路徑方法

我們先來介紹N-最短路徑方法，考慮到漢語自動(dòng)分詞中存在切分歧義消除和未登錄詞識(shí)別兩個(gè)主要問題，有人提出將分詞過程分為兩個(gè)階段：首先采用切分算法對(duì)句子詞語進(jìn)行初步切分，得到一個(gè)相對(duì)最好的粗分結(jié)果，然后，再進(jìn)行歧義排除和未登錄詞識(shí)別。

粗切分結(jié)果的準(zhǔn)確性與包容性（即必須涵蓋正確結(jié)果）直接影響后續(xù)的歧義排除和未登錄詞識(shí)別模塊的效果，并最終影響整個(gè)分詞系統(tǒng)的正確率和召回率。

N-最短路徑方法就是一個(gè)漢語詞語粗分模型，基本思想是，先根據(jù)詞典找到字串中所有可能的詞，構(gòu)造一個(gè)詞語切分的有向無環(huán)圖，每個(gè)詞對(duì)應(yīng)一條有邊長（權(quán)值）的邊，然后我們找出由起點(diǎn)到終點(diǎn)的所有路徑中，擁有N個(gè)最小長度值的路徑結(jié)果，所以得到的路徑數(shù)量可能大于N。簡單的來說，就是整體上盡可能多的用上詞典里的詞，而不是讓詞處于未處理的狀態(tài)，因?yàn)樵~的邊長要比組成詞的字的總邊長要短。

因?yàn)樯婕暗綀D的邊長，N-最短路徑方法還可以分為非統(tǒng)計(jì)粗分模型和統(tǒng)計(jì)粗分模型，所謂非統(tǒng)計(jì)粗分模型就是假定切分有向無環(huán)圖中所有詞的權(quán)重都是相等的，即每個(gè)詞對(duì)應(yīng)的邊長為1。

既然是求最短路徑，就要考慮Dijkstra算法了，Dijkstra算法的過程這里不講，下面是求『他說的確實(shí)在理』的3-最短路徑的示例：

『他說的確實(shí)在理』的求解過程（N=3）

最終起點(diǎn)0到終點(diǎn)7有兩條長度為5的路徑，一條長度為6的路徑，一條長度為7的路徑，從Table表中就可以看出。前驅(qū)(i,j)中的i表示到達(dá)當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，而j表示對(duì)應(yīng)到前一個(gè)節(jié)點(diǎn)i編號(hào)為j的路徑上。這樣根據(jù)這個(gè)表就能回溯出所有的路徑。

非統(tǒng)計(jì)模型給每個(gè)詞對(duì)應(yīng)邊的長度賦值為1，隨著字串長度n和最短路徑數(shù)N的增大，長度相同的路徑數(shù)會(huì)急劇增加，同時(shí)粗切分結(jié)果數(shù)量必然上升，這對(duì)于后期處理和整個(gè)分詞系統(tǒng)的性能很不利。接下來我們介紹基于統(tǒng)計(jì)的N-最短路徑方法。

假定一個(gè)詞串W經(jīng)過信道傳送，由于噪聲干擾而丟失了詞界的切分標(biāo)志，到輸出端便成了漢字串C。N-最短路徑方法詞語粗分模型可以相應(yīng)地改進(jìn)為：求N個(gè)候選切分W，使概率P(W|C)為前N個(gè)最大值。

然后根據(jù)貝葉斯公式P(W|C)=P(W)P(W|C)/P(C)，P(C)是常數(shù)，P(W|C)為1，所以我們只需考慮P(W)即可，粗分的目標(biāo)就是確定P(W)最大的N種切分結(jié)果。

然后我們采用一元文法模型，假定詞的出現(xiàn)相互獨(dú)立，以W=w1w2...wm作為一種切分結(jié)果，那切分W的概率為：

因?yàn)槭沁B乘，為了處理方面，對(duì)其取對(duì)數(shù)，即變成了對(duì)數(shù)值的累加，那每一個(gè)對(duì)數(shù)值就可以看做是對(duì)應(yīng)的詞在有向無環(huán)圖中的邊長，當(dāng)然我們可能還需要做適當(dāng)?shù)臄?shù)據(jù)平滑處理。

這樣對(duì)邊長進(jìn)行修改后，直接代入之前非統(tǒng)計(jì)粗分模型的求解算法即可。

基于詞的n元語法模型的分詞方法

基于詞的n元語法模型是一個(gè)典型的生成式模型，早期很多統(tǒng)計(jì)分詞方法均以它為基本模型，然后配合其它未登錄詞識(shí)別模塊進(jìn)行拓展。

基于詞的生成式模型的二元文法切分詞圖

其基本思想是：首先根據(jù)詞典對(duì)句子進(jìn)行簡單匹配，找出所有可能的詞典詞，然后，將它們和所有的單個(gè)字作為結(jié)點(diǎn)構(gòu)造n元的切分詞圖。圖中的結(jié)點(diǎn)表示可能的詞候選，邊表示路徑，邊上的n元概率表示代價(jià)，最后利用相關(guān)算法（如維特比算法）從圖中找到代價(jià)最小的路徑作為最后的分詞結(jié)果。

由于未登錄詞的識(shí)別是漢語分詞過程中的關(guān)鍵問題之一，因此，很多專家認(rèn)為未登錄詞的識(shí)別與歧義切分應(yīng)該是一體化處理的過程，而不是相互分離的。所以這種基于改進(jìn)的信道信源模型的分詞方法被提出了。

為了給自動(dòng)分詞任務(wù)一個(gè)明確的定義，J.Gao等人（2003）對(duì)文本中的詞給出了一個(gè)可操作的定義，把漢語詞定義成下列4類：

• 待切分文本中能與分詞詞表中任意一個(gè)詞相匹配的字段為一個(gè)詞
• 文本中任意一個(gè)經(jīng)詞法派生出來的詞或短語為一個(gè)詞
• 文本中被明確定義的任意一個(gè)實(shí)體名詞（如：日期、時(shí)間、貨幣、百分?jǐn)?shù)、溫度、長度、面積、體積、重量、地址、電話號(hào)碼、傳真號(hào)碼、電子郵件地址等）是一個(gè)詞。
• 文本中任意一個(gè)專有名詞（人名、地名、機(jī)構(gòu)名）是一個(gè)詞。

假設(shè)隨機(jī)變量S為一個(gè)漢字序列，W是S上所有可能的詞序列結(jié)果，所以經(jīng)過貝葉斯公式轉(zhuǎn)化，我們求的就是：

為了把4類詞納入同一個(gè)統(tǒng)計(jì)語言模型框架，一般把人名（PN）、地名（LN）、機(jī)構(gòu)名（ON）各作為一類，實(shí)體名詞中的日期、時(shí)間、百分?jǐn)?shù)、貨幣作為一類處理，簡稱實(shí)體名，詞法派生詞（MW）個(gè)詞表詞（LW）每個(gè)詞單獨(dú)作為一類。那么詞序列W可以被我們轉(zhuǎn)換成一個(gè)詞類序列C：

P(C)就是我們熟悉的語言模型，P(S|C)我們可以稱之為基于詞的生成式模型。

對(duì)P(C)我們采用三元文法模型：

而對(duì)于P(S|C)，我們認(rèn)為其滿足獨(dú)立性假設(shè)，總概率為各個(gè)概率的乘積，而對(duì)每個(gè)詞類的處理參考下表：

一些數(shù)據(jù)平滑操作也是需要的。

模型的訓(xùn)練過程一般如下：

• 在詞表的基礎(chǔ)上，先根據(jù)正向最大匹配法切分訓(xùn)練語料，專有名詞特殊標(biāo)注，實(shí)體名詞用規(guī)則和有限狀態(tài)自動(dòng)機(jī)標(biāo)注，得到一份帶類別標(biāo)記的初始語料
• 根據(jù)語料，采用最大似然估計(jì)法估計(jì)模型的概率參數(shù)
• 采用得到的語言模型對(duì)訓(xùn)練語料進(jìn)行重新切分和標(biāo)注
• 重復(fù)上兩步直到系統(tǒng)性能不再有明顯提高

對(duì)于交集型歧義字段（OAS），該方法首先通過最大匹配檢測(cè)出這些字段，然后用一個(gè)特定的類<GAP>取代全體OAS，以此來訓(xùn)練語言模型P(C)。類<GAP>通過消歧規(guī)則或機(jī)器學(xué)習(xí)方法來估計(jì)。

對(duì)于組合型歧義字段（CAS），該方法通過對(duì)訓(xùn)練語料的統(tǒng)計(jì)，選出最高頻、且分布比較均勻的70條CAS，用機(jī)器學(xué)習(xí)方法為每一條CAS訓(xùn)練一個(gè)二值分類器，這些分類器用于訓(xùn)練語料中消解這些CAS的歧義。

由字構(gòu)詞的漢語分詞方法

由字構(gòu)詞的漢語分詞方法將分詞看做字的分類問題，是一種基于字的判別式模型，在以往的分詞方法中，無論是基于規(guī)則的方法還是基于統(tǒng)計(jì)的方法，一般都依賴于一個(gè)事先編制的詞表，自動(dòng)分詞過程就是通過查詞表作出詞語切分的決策。與此相反，由字構(gòu)詞的分詞方法認(rèn)為每個(gè)字在構(gòu)造一個(gè)特定的詞語時(shí)都占據(jù)著一個(gè)確定的構(gòu)詞位置，比如詞首（B）、詞中（M）、詞尾（E）、單獨(dú)成詞（S）。

分詞結(jié)果表示成字標(biāo)注形式之后，分詞問題就變成了序列標(biāo)注問題。

因?yàn)槲覀冃枰鶕?jù)上下文來判斷待消歧問題的結(jié)果，所以通常情況下，使用基于字的判別模型時(shí)需要在當(dāng)前字的上下文中開一個(gè)w字的窗口（一般取w=5，也就是前后各兩個(gè)字），在這個(gè)窗口里抽取分詞相關(guān)的特征，常用的特征模板如下：

• c(k)（k＝-2，-1,0,1,2）
• c(k)c(k+1)（k＝-2，-1,0,1）
• c(-1)c(1)
• T(c(-2))T(c(-1))T(c(0))T(c(1))T(c(2))

c指k位置上的字，T指字的類型。

有了這些特征以后，我們就可以利用常見的判別模型，比如最大熵模型、條件隨機(jī)場(chǎng)、SVM和感知機(jī)等進(jìn)行參數(shù)訓(xùn)練了。

由字構(gòu)詞的重要優(yōu)勢(shì)在于，它能夠平衡地看待詞表詞和未登錄詞的識(shí)別問題，文本中的詞表詞和未登錄都是用統(tǒng)一的字標(biāo)注過程來實(shí)現(xiàn)的，分詞過程就成了字重組的簡單過程。

基于詞感知機(jī)算法的漢語分詞方法

基于詞感知機(jī)算法的漢語分詞方法是一種基于詞的判別式模型，不同于前面基于詞的生成模型和基于字的判別模型。該模型采用平均感知機(jī)作為學(xué)習(xí)算法，直接使用詞而不是字的相關(guān)特征。

基于感知機(jī)算法的漢語自動(dòng)分詞方法的基本思路是，對(duì)于任意給定一個(gè)輸入句子，解碼器每次讀一個(gè)字，生成所有的候選詞。生成候選詞的方式有兩種，第一個(gè)是，作為上一個(gè)候選詞的末尾，與上一個(gè)候選詞組合成一個(gè)新的候選詞；或者是，作為下一個(gè)候選詞的開始。這種方式可以保證在解碼過程中窮盡所有分詞候選。

在解碼的過程中，解碼器維持兩個(gè)列表，源列表和目標(biāo)列表。開始時(shí)，兩個(gè)列表都為空。解碼器每讀入一個(gè)字，就與源列表中的候選組合，按上一段說的兩種方法，生成兩個(gè)新的候選詞放入目標(biāo)列表。當(dāng)源列表中的候選都處理完成之后，將目標(biāo)列表中的所有候選詞復(fù)制到源列表中，并清空目標(biāo)列表。然后讀入下一個(gè)字，如此循環(huán)往復(fù)直到句子結(jié)束。

這種算法類似于全切分算法，理論上生成切分結(jié)果的數(shù)量會(huì)隨句長指數(shù)增長，為了提升速度，可以對(duì)目標(biāo)列表的條目數(shù)進(jìn)行限制，每次只保留B個(gè)得分最高的候選?？梢杂闷骄兄獧C(jī)算法對(duì)目標(biāo)列表中的切分候選進(jìn)行打分和排序。

平均感知機(jī)算法也是套用一些特征模板，使用一些規(guī)則，進(jìn)行打分和排序，這里不再細(xì)說。

基于字的生成式模型和判別式模型相結(jié)合的漢語分詞方法

前面講的，基于詞的n元語法模型（生成式模型）和基于字的序列標(biāo)注模型（判別式模型）是兩大主流方法。

其中，基于詞的生成式模型在處理詞典詞時(shí)可以獲得較好的表現(xiàn)，而基于字的判別式模型則想法，對(duì)未登錄詞的處理要更好一些。

而且實(shí)驗(yàn)發(fā)現(xiàn)，兩個(gè)處于詞邊界的字之間的依賴關(guān)系和兩個(gè)處于詞內(nèi)部的字的依賴關(guān)系是不一樣的。基于詞的生成式模型實(shí)際上隱含的考慮了這種處于不同位置的字的依賴關(guān)系，而基于字的判別式模型卻無法考慮這種依賴關(guān)系。但是判別式模型能夠充分利用上下文特征信息，擁有較大的靈活性和魯棒性，所以基于字的n元語法模型，并將生成式模型與判別式模型相結(jié)合的漢語分詞方法被提出。

我們將基于詞的生成式模型中的詞替換為相應(yīng)的字即得到了基于字的生成式模型。

基于字的生成式模型仍然以字作為基本單位，但考慮了字與字之間的依賴關(guān)系，與基于字的判別式模型相比，處理詞典詞的能力有了大幅改觀。但是該模型并不能像基于字的判別模型那樣考慮整個(gè)窗口，也即當(dāng)前字后面的上下文。因此，基于字的生成式模型在處理未登錄詞的能力仍然若于基于字的判別式模型。

為了同時(shí)利用生成式模型和判別式模型的優(yōu)點(diǎn)，利用線性插值法將這兩個(gè)模型進(jìn)行整合，就提出了集成式分詞模型。