前言-- 廢話

在這么多篇的基礎(chǔ)后，終于可以開(kāi)始我一開(kāi)始想學(xué)習(xí)的東西這里，也就是HMM，Hidden Markov Models，基于前三篇的內(nèi)容，可以理解和學(xué)習(xí)這一篇的內(nèi)容。
PGM(Probabilistic Graphical Models)系列--1.基礎(chǔ)
PGM(Probabilistic Graphical Models)系列--2. 貝葉斯網(wǎng)絡(luò)
PGM(Probabilistic Graphical Models)系列--3. 馬爾科夫模型

過(guò)渡到HMM

在學(xué)習(xí)過(guò)程中，其實(shí)我是十分的confused的，因?yàn)閭鹘y(tǒng)的HMM和MRF不太一樣，跟貝葉斯網(wǎng)絡(luò)也不太一樣，很難說(shuō)是其中任何一個(gè)的直接衍生物。更像是二者的結(jié)合物？

例如

一個(gè)常規(guī)的HMM

但實(shí)際上，又是一個(gè)MRF，為什么呢？
重點(diǎn)在于，y的變化是指發(fā)生在y的幾種可能性之間。

若引用wiki 的一張圖來(lái)闡釋。

HMM的局部狀態(tài)

每一次的Y以及導(dǎo)致的X之間的關(guān)系，應(yīng)該由上圖來(lái)進(jìn)行闡釋。
如：
Y1 = Healthy -->X1 = Cold
這樣到了第二天，可能Y1繼續(xù)產(chǎn)生了變化，當(dāng)然也有可能沒(méi)有變化。（這其中都帶有一個(gè)所謂的概率轉(zhuǎn)移矩陣(類似于CPDs)）。
其中由于概率轉(zhuǎn)移矩陣的雙向能力，所以也類似于CRF的感覺(jué)。

用下面一個(gè)圖來(lái)展示各種圖模型的關(guān)系。

感謝知乎上的這個(gè)問(wèn)題

那么我們還是把它當(dāng)做一個(gè)獨(dú)立的模型先去理解。

HMM

定義：每個(gè)狀態(tài)的轉(zhuǎn)移只依賴于之前的 n 個(gè)狀態(tài)，這個(gè)過(guò)程被稱為1個(gè) n 階的模型，其中 n 是影響轉(zhuǎn)移狀態(tài)的數(shù)目。最簡(jiǎn)單的馬爾科夫過(guò)程就是一階過(guò)程，每一個(gè)狀態(tài)的轉(zhuǎn)移只依賴于其之前的那一個(gè)狀態(tài)。
(也就是上上圖所表示的，y的概率只與其前后的有關(guān)。)

概率轉(zhuǎn)移矩陣(Transition Probability Matrix)：由于一個(gè)特征有多個(gè)狀態(tài)，即假設(shè)Y有N個(gè)狀態(tài)，則概率轉(zhuǎn)移矩陣就為一個(gè)N^2的矩陣。(主要說(shuō)的是隱含層)
混淆矩陣 (confusion matrix)：由隱含層的特征多個(gè)狀態(tài)與觀察層的特征多個(gè)狀態(tài)的關(guān)聯(lián)，由于觀察到的是有限的，所以隱含層的單個(gè)狀態(tài)對(duì)應(yīng)的觀察層多個(gè)狀態(tài)的概率之和為1。

這樣一個(gè)馬爾科夫過(guò)程就建立起來(lái)，即一個(gè)具有時(shí)間序列的貝葉斯網(wǎng)絡(luò)。

三個(gè)重要假設(shè)

解釋一下：
第一個(gè)即只與前后的相關(guān)，所以其它都條件獨(dú)立，可以約去
第二個(gè)即前后的轉(zhuǎn)移概率不以時(shí)間改變而改變
第三個(gè)即觀察層的概率只與隱含層的相關(guān)

那么由上面的這些總結(jié)可知。由于HMM的假設(shè)十分的簡(jiǎn)單，那么我們其實(shí)可以用一個(gè)五元的參數(shù)來(lái)表達(dá)一個(gè)特定的HMM。
即{N, M, π，A，B}

N為隱含的狀態(tài)數(shù)
M為觀察的狀態(tài)數(shù)
π為初始的狀態(tài)概率
A為轉(zhuǎn)移矩陣
B誒混淆矩陣
λ 可以代表π，A，B的集合

用HMM解決的三大類問(wèn)題

若已經(jīng)有λ和M,N，若在所有可能的隱藏狀態(tài)序列下，給定的可觀察狀態(tài)序列的概率(前向算法)

直觀的去思考，大概分為以下求解步驟。

1. 假設(shè)給定一個(gè)隱藏序列，通過(guò)混淆矩陣，求出概率。

2. 通過(guò)只與前后相關(guān)的馬爾科夫假設(shè)，求出隱含狀態(tài)層的概率

對(duì)所有的隱含層求解以上兩步，并累加，可得出給定的一個(gè)觀察序列的概率

當(dāng)然，算法上怎么解決當(dāng)序列長(zhǎng)時(shí)窮舉產(chǎn)生的巨大的復(fù)雜度的問(wèn)題，請(qǐng)看后面算法部分。

根據(jù)可觀察狀態(tài)的序列找到一個(gè)最可能的隱藏狀態(tài)序列

在已知一個(gè)HMM下，這也是一個(gè)比較符合現(xiàn)實(shí)情況的問(wèn)題，我們記錄下了觀察到的序列，求解可能性最大的隱藏狀態(tài)的序列。

同樣的，

如果用窮舉的方法，同樣可以算出以上的最大值，窮舉所有隱藏序列，計(jì)算隱藏序列的轉(zhuǎn)移概率，計(jì)算隱藏序列到觀察序列的概率。

根據(jù)觀察到的序列集來(lái)找到一個(gè)最有可能的 HMM。

除去上述的情況外，現(xiàn)實(shí)情況中更加有可能的是不知道HMM的各個(gè)參數(shù)，只能先進(jìn)行ML中的學(xué)習(xí)。由于給定的可觀察狀態(tài)序列 O 來(lái)說(shuō)，沒(méi)有任何一種方法可以精確地找到一組最優(yōu)的 HMM 參數(shù) λ 使 P(O | λ) 最大。所以人們使用前向后向算法（也稱為Baum-Welch算法）近似的求解HMM。

HMM中求解問(wèn)題使用到的算法

前向算法(Forward -Backward Algorithm)

由于上面說(shuō)到的大多數(shù)的計(jì)算方法都是窮舉去計(jì)算所有的時(shí)間序列下的所有情況，這樣就會(huì)隨著時(shí)間序列的增加而指數(shù)級(jí)的增長(zhǎng)算法的復(fù)雜度。這顯然對(duì)計(jì)算機(jī)是一個(gè)十分大的負(fù)擔(dān)，為了加快速度和減少計(jì)算機(jī)資源的使用。

我們利用概率不隨時(shí)間的變化而變化的特性來(lái)降低開(kāi)銷

前向算法是為了解決在所有可能的隱藏序列下，給定的可觀察狀態(tài)序列的概率。

那么用 αt(j) 來(lái)表示在 t 時(shí)刻是隱含狀態(tài) j 的概率，αt(j)=Pr(觀察狀態(tài) | 隱含狀態(tài) j ) x Pr(t 時(shí)刻到達(dá)隱含狀態(tài) j 的所有路徑)。

對(duì)于這么個(gè)隱含層，觀察序列為最下面的dry，damp，soggy。這個(gè)可以作為t=2時(shí)的概率。由于各個(gè)時(shí)間點(diǎn)均為各自獨(dú)立，所以我們可以遞歸的沿著時(shí)間鏈去獨(dú)立計(jì)算每一個(gè)時(shí)間點(diǎn)下各個(gè)狀態(tài)的概率。

1. t=1時(shí)，即初始概率表π乘以觀測(cè)序列第一個(gè)狀態(tài)到各自隱含狀態(tài)的混淆矩陣中的值

2. t>1時(shí)，即t-1的時(shí)間點(diǎn)的各個(gè)狀態(tài)的值即包含了 Pr(t 時(shí)刻到達(dá)隱含狀態(tài) j 的所有路徑)，所以我們只需要計(jì)算Pr(觀察狀態(tài) | 隱含狀態(tài) j )。大大的節(jié)省了時(shí)間。

   
   
   
   

   算到了最后一個(gè)時(shí)間點(diǎn)時(shí)，所有狀態(tài)的概率之和即結(jié)果。

維特比(Viterbi) 算法

這個(gè)算法比較廣泛的使用在自然語(yǔ)言處理中的詞性標(biāo)注。句子中的單詞是可以觀察到的，詞性是隱藏的狀態(tài)。通過(guò)根據(jù)語(yǔ)句的上下文找到一句話中的單詞序列的最有可能的隱藏狀態(tài)序列，我們就可以得到一個(gè)單詞的詞性（可能性最大）

這個(gè)算法本身與前向算法是十分類似的，也是利用了概率不隨時(shí)間變化而變化，通過(guò)逐步遞歸的方法減少計(jì)算量。其中最大的不同就是在t時(shí)刻最可能到達(dá)某個(gè)狀態(tài)的一條路徑的概率，而不是所有概率之和。

用 δ(i, t) 來(lái)表示在t時(shí)刻，到隱含狀態(tài)i的所有可能的序列（路徑）中概率最大的序列的概率。

1. t = 1時(shí)，由于不存在t = 0的前置狀態(tài)，所以直接用即初始概率表π乘以觀測(cè)序列第一個(gè)狀態(tài)到各自隱含狀態(tài)的混淆矩陣中的值。
2. t > 1時(shí)，我們就要使用t-1時(shí)的值，求解從t-1各個(gè)狀態(tài)到t時(shí)特定狀態(tài)時(shí)的概率，從中選出最大的值，再加上與混淆矩陣的計(jì)算，則可以得到當(dāng)前的 δ(i, t)。

3. 總結(jié)可知

   ，即aji 表示從狀態(tài) j 轉(zhuǎn)移到狀態(tài) i 的概率，bikt 表示狀態(tài)i被觀察成 kt 的概率，乘上t-1時(shí)為j的概率，整體的最大值。即得到 t 時(shí)刻可觀察狀態(tài)為 kt 的第 i 個(gè)狀態(tài)的最大部分概率。

確定終點(diǎn)后，反過(guò)來(lái)往前回溯，確定前一個(gè)最佳的點(diǎn)。從而確定一個(gè)隱藏狀態(tài)的時(shí)間序列。

Baum-Welch Algorithm

大概的思路是類似于EM算法的，通過(guò)初始化一個(gè)參數(shù)，并多次的評(píng)估參數(shù)的有效性去更新它的參數(shù)，從而逐步的漸進(jìn)最有可能的參數(shù)。而且由于是一個(gè)最大似然估計(jì)，所以得到的是一個(gè)局部最優(yōu)解。那么實(shí)際上是怎么操作呢？

先定義一個(gè)后向變量，作為β，即當(dāng)前狀態(tài)下后面特定觀察序列的概率，同樣的，可以用遞歸的方法去計(jì)算，所以得到一個(gè)類似于前向算法的值。最后綜合前后向變量，可以得到一個(gè)特定觀察序列的概率。

1. 先定義兩個(gè)輔助變量。
   a. 定義為 t 時(shí)狀態(tài) i 和 t+1 時(shí)狀態(tài) j 的概率，
   用前后的時(shí)刻的i，j來(lái)定義。通過(guò)代入前后向變量可以展開(kāi)為
   
   
   b. 后驗(yàn)概率
   同樣的，代入前后向變量可以展開(kāi)為

后序

由于HMM的強(qiáng)大，使得HMM至今還在語(yǔ)音語(yǔ)義識(shí)別領(lǐng)域發(fā)揮著重要的作用，但是由于HMM的假設(shè)過(guò)于簡(jiǎn)單，從而也導(dǎo)致了大家產(chǎn)生了擴(kuò)展HMM的需求。也就產(chǎn)生了N-1階的HMM，若N=2，即我們這里說(shuō)的HMM，一般用到的N=3,更高階的模型用到的就很少了，由于每一階的擴(kuò)展都是在指數(shù)級(jí)上的復(fù)雜度的提高
但由于自然語(yǔ)言的特性，上下文之間的聯(lián)系絕對(duì)不僅僅是幾個(gè)詞之間的聯(lián)系可以說(shuō)得通的。有一些甚至需要聯(lián)系前后的好幾個(gè)段落才能夠說(shuō)明白一個(gè)詞的語(yǔ)義，所以對(duì)于一些長(zhǎng)距離的詞性依賴，是很難解決的。這時(shí)就需要?jiǎng)e的統(tǒng)計(jì)模型進(jìn)行解讀。

參考

http://www.52nlp.cn/hmm-learn-best-practices-five-forward-algorithm-3
[轉(zhuǎn)載]轉(zhuǎn)：隱馬爾科夫模型HMM攻略
http://blog.csdn.net/xueyingxue001/article/details/52396494
數(shù)學(xué)之美 吳軍