HMM及CRF

image

概率圖模型

概率圖模型（probabilistic graphical models）在概率模型的基礎(chǔ)上，使用了基于圖的方法來(lái)表示概率分布（或者概率密度、密度函數(shù)）。

在概率圖模型的表達(dá)中，數(shù)據(jù)(樣本)由公式 G=(V,E) 建模表示：

  • V: 結(jié)點(diǎn), 表示變量, 具體地，用 Y = (y_{1}, {\cdots}, y_{n} ) 為隨機(jī)變量建模，P(V) 為這些隨機(jī)變量的聯(lián)合概率分布；
  • E: 邊, 表示相應(yīng)變量之間的概率關(guān)系

根據(jù)圖模型（graphical models）的邊是否有向，概率圖模型通常被劃分成有向概率圖模型和無(wú)向概率圖模型。

有向概率圖模型

image

求解聯(lián)合概率

P(x_{1}, {\cdots}, x_{5} )=P(x_{1})·P(x_{2}|x_{1} )·P(x_{3}|x_{2} )·P(x_{4}|x_{2} )·P(x_{5}|x_{3},x_{4} )

寫(xiě)成通用形式即

P(x_{1}, {\cdots}, x_{n} )=\prod_{i=0}P(x_{i} | \pi(x_{i}))

無(wú)向概率圖模型

如果聯(lián)合概率分布 P(V) 滿(mǎn)足成對(duì)、局部或全局馬爾可夫性，就稱(chēng)此聯(lián)合概率分布為概率無(wú)向圖模型或馬爾可夫隨機(jī)場(chǎng)(MRF)

成對(duì)馬爾可夫性

設(shè)無(wú)向圖 G 中的任意兩個(gè)沒(méi)有邊連接的節(jié)點(diǎn) u 、v ，其他所有節(jié)點(diǎn)為 O ，成對(duì)馬爾可夫性指：給定 Y_{O} 的條件下，Y_{u} 和 Y_{v} 條件獨(dú)立

image

P(Y_{u},Y_{v}|Y_{O})=P(Y_{u}|Y_{O})P(Y_{v}|Y_{O})

局部馬爾可夫性

設(shè)無(wú)向圖 G 的任一節(jié)點(diǎn) v ，W 是與 v 有邊相連的所有節(jié)點(diǎn)，O 是 v 、W 外的其他所有節(jié)點(diǎn)，局部馬爾可夫性指：給定 Y_{W} 的條件下，Y_{v} 和 Y_{O} 條件獨(dú)立

image

P(Y_{v},Y_{O}|Y_{W})=P(Y_{v}|Y_{W})P(Y_{O}|Y_{W})

當(dāng) P(Y_{O}|Y_{W})>0 時(shí)，等價(jià)于

P(Y_{v}|Y_{W})=P(Y_{v}|Y_{W},Y_{O})

如果把等式兩邊的條件里的 Y_{W} 遮住，P(Y_{v})=P(Y_{v}|Y_{O}) 這個(gè)式子表示 Y_{v} 和 Y_{O} 獨(dú)立，進(jìn)而可以理解這個(gè)等式為給定條件 YW 下的獨(dú)立。

全局馬爾可夫性

設(shè)節(jié)點(diǎn)集合 A 、B 是在無(wú)向圖 G 中被節(jié)點(diǎn)集合 C 分開(kāi)的任意節(jié)點(diǎn)集合，全局馬爾可夫性指：給定 Y_{C} 的條件下，Y_{A} 和 Y_{B} 條件獨(dú)立

image

P(Y_{A},Y_{B}|Y_{C})=P(Y_{A}|Y_{C})P(Y_{B}|Y_{C})

成對(duì)、局部或全局馬爾科夫性，大白話(huà)就是說(shuō)每一個(gè)節(jié)點(diǎn)的分布只和有邊相連的節(jié)點(diǎn)有關(guān)系。

image

不同于有向圖模型，無(wú)向圖模型的無(wú)向性很難確保每個(gè)節(jié)點(diǎn)在給定它的鄰節(jié)點(diǎn)的條件下的條件概率和以圖中其他節(jié)點(diǎn)為條件的條件概率一致。由于這個(gè)原因，無(wú)向圖模型的聯(lián)合概率并不是用條件概率參數(shù)化表示的，而是定義為由一組條件獨(dú)立的局部函數(shù)的乘積形式。因子分解就是說(shuō)將無(wú)向圖所描述的聯(lián)合概率分布表達(dá)為若干個(gè)子聯(lián)合概率的乘積，從而便于模型的學(xué)習(xí)和計(jì)算。

image

P(Y)=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c} )

其中 Z(x) = \sum_{Y} \prod_{c}\psi_{c}(Y_{c} ), 歸一化是為了讓結(jié)果算作概率。

所以像上面的無(wú)向圖：

P(Y)=\frac{1}{Z(x)} ( \psi_{1}(X_{1}, X_{3}, X_{4} ) · \psi_{2}(X_{2}, X_{3}, X_{4} ) )

其中， \psi_{c}(Y_{c} ) 是一個(gè)最大團(tuán) C 上隨機(jī)變量們的聯(lián)合概率，一般取指數(shù)函數(shù)的：

\psi_{c}(Y_{c} ) = e^{-E(Y_{c})} =e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)}

團(tuán)：無(wú)向圖G中任何兩個(gè)結(jié)點(diǎn)均有邊連接的節(jié)點(diǎn)子集成為團(tuán)。
最大團(tuán)：若C是無(wú)向圖G的一個(gè)團(tuán)，并且不能再加進(jìn)任何一個(gè)G的節(jié)點(diǎn)使其成為一個(gè)更大的團(tuán)，則稱(chēng)此C為最大團(tuán)。

那么概率無(wú)向圖的聯(lián)合概率分布可以在因子分解下表示為：

P(Y)=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c} ) = \frac{1}{Z(x)} \prod_{c} e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} = \frac{1}{Z(x)} e^{\sum_{c}\sum_{k}\lambda_{k}f_{k}(y_{i},y_{i-1},x,i)}

名詞解釋

馬爾可夫鏈

舉個(gè)栗子，一只被切除了大腦的白鼠被隨機(jī)丟進(jìn)如下洞穴, 小白鼠在洞穴間隨機(jī)躥動(dòng)

image

竄動(dòng)的路線(xiàn)就構(gòu)成一個(gè)馬爾科夫鏈。因?yàn)檫@只白鼠已沒(méi)有了記憶，瞬間產(chǎn)生的念頭決定了它從一個(gè)洞穴躥到另一個(gè)洞穴；當(dāng)其所在位置確定時(shí)，它下一步躥往何處與它以往經(jīng)過(guò)的路徑無(wú)關(guān)。

image

這種在已知“現(xiàn)在”的條件下，“未來(lái)”與“過(guò)去”彼此獨(dú)立的特性就被稱(chēng)為馬爾科夫性，具有這種性質(zhì)的隨機(jī)過(guò)程就叫做馬爾科夫過(guò)程，其最原始的模型就是馬爾科夫鏈。

隱馬爾可夫模型(HMM)

假設(shè)觀察者距離洞穴很遠(yuǎn), 看不見(jiàn)老鼠竄動(dòng)的軌跡, 但是每個(gè)洞穴中都裝有不同顏色的燈, 當(dāng)老鼠進(jìn)入到該洞穴時(shí)會(huì)觸發(fā)開(kāi)關(guān)將燈點(diǎn)亮, 觀察者可以看清被點(diǎn)亮的燈的顏色

image

假設(shè)老鼠竄動(dòng)的軌跡如下

image

那么觀察者看到的燈亮的順序則為

image

一個(gè)隱馬爾可夫模型則可以如下表示

image

小白鼠在洞穴(狀態(tài))之間的轉(zhuǎn)移存在轉(zhuǎn)移概率, 可由矩陣表示:

A= \left\{ \begin{matrix} & A & B & C & D & E & F & G & H & I \\ A & 0.2 & 0.4 & 0.4 & 0 & 0 & 0 & 0 & 0 & 0 \\ B & 0.3 & 0.1 & 0.3 & 0 & 0.3 & 0 & 0 & 0 & 0 \\ C & 0 & 0.3 & 0.4 & 0 & 0 & 0.3 & 0 & 0 & 0 \\ D & 0.33 & 0 & 0 & 0 & 0.33 & 0 & 0.33 & 0 & 0 \\ E & 0 & 0.2 & 0 & 0.2 & 0.2 & 0.2 & 0 & 0.2 & 0 \\ F & 0 & 0 & 0.33 & 0 & 0.33 & 0 & 0 & 0 & 0.33 \\ G & 0 & 0 & 0 & 0.5 & 0 & 0 & 0 & 0.5 & 0 \\ H & 0 & 0 & 0 & 0 & 0.33 & 0 & 0.33 & 0 & 0.33 \\ I & 0 & 0 & 0 & 0 & 0 & 0.33 & 0 & 0.33 & 0.33 \end{matrix} \right\}
這個(gè)矩陣稱(chēng)為狀態(tài)轉(zhuǎn)移概率分布矩陣, 如小白鼠從房間F竄到房間C的概率為0.33

假如實(shí)驗(yàn)中開(kāi)關(guān)發(fā)生故障, 每次進(jìn)入洞穴后點(diǎn)亮的燈的顏色不再確定, 而是每種顏色的燈亮存在概率, 如下矩陣:

B= \left\{ \begin{matrix} & 紅 & 綠 & 藍(lán) \\ A & 0.7 & 0.2 & 0.1 \\ B & 0.15 & 0.7 & 0.15 \\ C & 0 & 0.2 & 0.8 \\ D & 0 & 1 & 0 \\ E & 0.7 & 0.2 & 0.1 \\ F & 0.15 & 0.7 & 0.15 \\ G & 0.8 & 0.1 & 0.1 \\ H & 0.6 & 0.3 & 0.1 \\ I & 0.2 & 0.2 & 0.6 \end{matrix} \right\}

這個(gè)矩陣稱(chēng)為觀測(cè)狀態(tài)概率矩陣, 如小白鼠進(jìn)到F洞穴, 紅燈亮的概率為0.15, 綠燈亮的概率為0.7, 藍(lán)燈亮的概率為0.15

小白鼠最初被隨機(jī)丟進(jìn)每個(gè)洞穴的初始概率為π=(0.1, 0.1, 0.1, 0.2, 0, 0.12, 0.3, 0.08, 0)

隱馬爾科夫模型由初始狀態(tài)概率向量π、狀態(tài)轉(zhuǎn)移概率矩陣A和觀測(cè)概率矩陣B決定。π和A決定狀態(tài)序列，B決定觀測(cè)序列。因此，隱馬爾科夫模型λ可以由三元符號(hào)表示，即：λ=(A,B,π)。A,B,π稱(chēng)為隱馬爾科夫模型的三要素。

隱馬爾可夫模型屬于有向圖模型, 需要計(jì)算的概率是“觀測(cè)序列(輸入)和狀態(tài)序列(輸出)的聯(lián)合概率”，即P(狀態(tài)序列, 觀測(cè)序列), 然后再根據(jù)貝葉斯公式求解出P(狀態(tài)序列|觀測(cè)序列), 構(gòu)建它們的聯(lián)合概率分布P(Y,X)的模型屬于生成式模型

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

顯然在現(xiàn)實(shí)生活當(dāng)中, 一個(gè)狀態(tài)的發(fā)生很可能不僅僅依賴(lài)于前一個(gè)狀態(tài), 而是依賴(lài)于前后多個(gè)狀態(tài)。 拿詞性標(biāo)注來(lái)說(shuō), 判斷一個(gè)詞是否為動(dòng)詞, 我們可能需要考慮這個(gè)詞的前一個(gè)詞(上一個(gè)狀態(tài))是否為形容詞, 這個(gè)詞后邊(下一個(gè)狀態(tài))是否為名詞, 這個(gè)詞(本身)是否以ing或者ly結(jié)尾等等。像這種場(chǎng)景我們便可以用條件隨機(jī)場(chǎng)來(lái)解決

此前我們介紹了馬爾科夫隨機(jī)場(chǎng)(MRF), 如果給定的MRF中每個(gè)隨機(jī)變量y_{i}下面還有觀察值x_{i}，那么我們的目標(biāo)就是要確定給定觀察集合X下的MRF分布，也就是條件分布，而這種條件分布就是條件隨機(jī)場(chǎng)。

簡(jiǎn)單的說(shuō)，條件隨機(jī)場(chǎng)(CRF)類(lèi)似于MRF，只不過(guò)CRF比MRF多了一個(gè)觀察集合，或者說(shuō)，CRF本質(zhì)上就是給定了觀察值集合的MRF。

這里介紹的CRF指線(xiàn)性鏈條件隨機(jī)場(chǎng), 即觀測(cè)序列X與狀態(tài)序列Y有相同的圖結(jié)構(gòu)如下:

image
image

定義

設(shè) X=(X_{1},X_{2}，...,X_{n}), Y=(Y_{1},Y_{2},...,Y_{n}) 均為線(xiàn)性鏈表示的隨機(jī)變量序列，在給定隨機(jī)變量序列 X 的情況下，隨機(jī)變量 Y 的條件概率分布 P(Y|X) 構(gòu)成條件隨機(jī)場(chǎng)，即滿(mǎn)足馬爾科性：

P(Yi|X,Y_{1},...,Y_{i?1},Y_{i+1},...,Y_{n})=P(Y_{i}|X,Y_{i?1},Y_{i+1}), i=1,...,n

線(xiàn)性鏈條件隨機(jī)場(chǎng)的特征函數(shù)

P(Y=y|x)=\frac{1}{Z(x)}\exp\biggl(\sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)+\sum_l\mu_l\sum_is_l(y_i,x,i)\biggr)

Z(x)=\sum_y\exp\biggl(\sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)+\sum_l\mu_l\sum_is_l(y_i,x,i)\biggr)

Z(x) 作為規(guī)范化因子，是對(duì) y 的所有可能取值求和。

其中:
t_k(y_{i-1},y_i,x,i): 是定義在邊上的轉(zhuǎn)移特征函數(shù)（transition），依賴(lài)于當(dāng)前位置 i 和前一位置 i-1 ；對(duì)應(yīng)的權(quán)值為 λ_{k}
s_l(y_i,x,i): 是定義在節(jié)點(diǎn)上的狀態(tài)特征函數(shù)（state），依賴(lài)于當(dāng)前位置 i ；對(duì)應(yīng)的權(quán)值為 μ_{l}

一般來(lái)說(shuō)，特征函數(shù)的取值為 1 或 0 ，當(dāng)滿(mǎn)足規(guī)定好的特征條件時(shí)取值為 1 ，否則為 0 。

詞性標(biāo)注例子

image

  • 如果 y_{i?1}=形容詞, 且 y_{i}=名詞, 則轉(zhuǎn)移特征函數(shù) t(y_{i-1},y_i,x,i)=1, 否則為 0。如果該特征函數(shù)有一個(gè)較大的正權(quán)重\lambda_k，就表明傾向于認(rèn)為形容詞后面跟著名詞。

  • 如果 y_{i?1}=介詞, 且 y_{i}=介詞, 則轉(zhuǎn)移特征函數(shù) t(y_{i-1},y_i,x,i)=1, 否則為 0。如果該特征函數(shù)有一個(gè)較大的負(fù)權(quán)重\lambda_k，就表明傾向于認(rèn)為介詞后面不會(huì)再跟介詞。

  • 如果 y_{i}=副詞 且 x_{i} 以“-ly”結(jié)尾, 則狀態(tài)特征函數(shù) s(y_i,x,i)=1, 否則為0。如果該特征函數(shù)有一個(gè)較大的正權(quán)重，就表明傾向于將 “-ly” 結(jié)尾的單詞標(biāo)注為副詞。

  • 如果 i=1 y_{i}=動(dòng)詞 且 x 以“?”結(jié)尾, 則狀態(tài)特征函數(shù) s(y_i,x,i)=1, 否則為0。如果該特征函數(shù)有一個(gè)較大的正權(quán)重，就表明傾向于將問(wèn)句的首詞標(biāo)注為動(dòng)詞。如“Is it right?”

HMM, CRF, LSTM之間的聯(lián)系與區(qū)別

首先要說(shuō)明的是HMM, CRF, LSTM都可以用來(lái)做分詞任務(wù)。用一個(gè)分詞的例子來(lái)說(shuō)明, 假如有一句待分詞文本, 內(nèi)容是:

已結(jié)婚的和尚未結(jié)婚的青年都要實(shí)行計(jì)劃生育

采用 \{B M E S\} 4-tag方法進(jìn)行分詞, B 表示詞首, M 表示詞中, E 表示詞尾, S 表示單字。正確的結(jié)果應(yīng)該是:

已/S 結(jié)/B 婚/E 的/S 和/S 尚/B 未/E 結(jié)/B 婚/E 的/S 青/B 年/E 都/S 要/S 實(shí)/B 行/E 計(jì)/B 劃/M 生/M 育/E

如果我們用 LSTM+softmax 的話(huà), 它解決問(wèn)題的步驟是這樣的, LSTM用來(lái)生成特征向量, 再將其丟給 softmax , 預(yù)測(cè)每個(gè)分類(lèi)的概率, 將概率最大的分類(lèi)作為最終的分詞結(jié)果。 但是這樣做沒(méi)有考慮到標(biāo)簽之間的連接是否合理, 例如可能會(huì)出現(xiàn)這種情況

已/S 結(jié)/B 婚/B 的/S 和/S 尚/B 未...

顯然 B 后邊接 B 是不合理的

(找了個(gè)BiLSTM做實(shí)體標(biāo)注的示例圖)


image

如果我們用 HMM 的話(huà), 它解決問(wèn)題的步驟是這樣的, 計(jì)算每種情況的概率, 如

P_{1}=P(S轉(zhuǎn)移到B)*P(“已”表現(xiàn)為S)* P(B轉(zhuǎn)移到E)*P(“結(jié)”表現(xiàn)為B)* …*P()
P_{2}=...

然后取概率最大的一組作為最后的分詞結(jié)果。因?yàn)镠MM的條件獨(dú)立假設(shè), 使其不能充分考慮上下文信息

最后是 CRF , CRF 也是求每種情況的概率, 但是其概率求解的形式為:

P= F(y_{i-1}轉(zhuǎn)移到y(tǒng)_{i}, y_{i-1}表現(xiàn)為x_{i})

F為一個(gè)函數(shù)，是在全局范圍統(tǒng)計(jì)歸一化的概率

最后放一張關(guān)系圖


image

樸素貝葉斯：生成式模型，條件獨(dú)立 —> 序列形式 隱馬爾科夫模型 —> 圖形式 通用有向圖模型
邏輯回歸：判別式模型，條件不獨(dú)立 —> 序列形式 線(xiàn)性鏈條件隨機(jī)場(chǎng) —> 圖形式 通用條件隨機(jī)場(chǎng)

參考鏈接

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容