https://blog.csdn.net/athemeroy/article/details/79342048
本文致力于解釋隱含馬爾科夫模型和上一篇我們提到的籬笆網絡的最短路徑問題的相同點和不同點，盡量通俗易懂但是也有些必要的公式。如果你有數學恐懼癥，請無視所有的“注”。我的概率論學的很爛，如果“注”里面有錯誤，請務必直接噴，不要留情，謝謝！

隱馬爾科夫模型（HMM）和籬笆網絡（神馬關系）
咱先別”隱身”，先說說啥是馬爾科夫模型？
隱馬爾科夫模型，一聽這個名字就和馬爾科夫模型有著隱藏的聯系。
所謂的馬爾科夫模型，其實說的就是好好一個人，是怎么變來變去的（旁白：？？？）。比如說，一個人某一天可能輕微感冒，也可能正常，還可能重感冒（請原諒我對病不是很了解）。如果你認為這個是上天隨機拋硬幣決定的倒也可以，比如我們可以認為：

P（身體狀態=正常）=0.7
P（身體狀態=輕感冒）=0.2
P（身體狀態=重感冒）=0.1 

• 1
• 2
• 3

但是可能更多的，某一天的身體狀態是由這個人長期以來作出來的……啊不是，是和前一天（或者N天）的身體狀態變來的。比如正常可能會更大概率讓第二天依然正常，而輕感冒比正常更容易讓第二天表現為重感冒。
如果我們認為某一天的身體狀態完全由前一天的身體狀態來決定（這叫做一階馬爾科夫假設，這算是這個世界上最不負責任的10000個假設之一了，好在很多情況下這種假設還蠻好用），那么我們可以畫這樣一個圖出來：

簡單解釋一下，如果某個人在昨天是輕感冒，那么在今天他有0.4的概率維持輕感冒的狀態，0.4的概率病情好轉，還有0.2的概率病情惡化。
Emmmm…看上去有點亂，如果只有這么三個狀態還好，如果狀態再多點，感覺就要眼花繚亂了！
所以通常來說，我們使用類似下面的表格來描述整個馬爾科夫過程的。

這樣是不是清楚多了！那么如果我們省去不必要的字，僅僅用一個矩陣來表示的話，可以這樣來寫（稱為狀態轉移矩陣）：

當然了，既然有一階馬爾科夫假設，當然就有二階、三階乃至N階，他們都是假設今天（t時刻）的狀態僅僅和前n天（t-1,t-2…t-n時刻）的狀態來決定。比如如果基于二階馬爾科夫假設，某個人前天和昨天分別是重感冒、輕感冒，那么今天說不定感冒也就快好了（美好的祝愿），而今天的狀態僅僅和昨天前天有關，和再往前的歷史已經沒什么關系了。

馬爾科夫模型和籬笆網絡
那么這個時候我們就可以把上一篇文章的籬笆網絡弄過來了。

咱們把這幅圖簡單改一下，把A和E去掉（當然可以留下A，這個時候是所謂的”先驗”，我們先不考慮這個），然后把節點的權重修改一下，就得到了“治病救人籬笆網絡”：

“我能在河邊，畫上一整天的圖！”納特·帕格興高采烈地說道。

我們很容易發現，只要把原本的節點間的距離，換成狀態轉移矩陣中的轉移概率，我們就輕松地把“跑腿不累籬笆網絡”改成了“治病救人籬笆網絡”。
那你看這個時候你的老師就很容易考你了，“已知一個人2月1號重感冒，2月5號正常，告訴我他經歷了哪條狀態序列的概率最大！”（旁白：鬼知道他經歷了什么，大概是吃了感冒藥吧！）你會發現這個問題和上一篇文章的“跑腿不累籬笆網絡”幾乎沒什么區別，如果硬要說有區別的話，既然每一天轉移都是獨立的，那么概率需要乘在一起（見下注），最后看誰最大，而不是“跑腿”中的簡單做加法。

比如他經歷了“重感冒、正常、輕感冒、重感冒、輕感冒、正常”（旁白：這個人也是體弱多病！）的概率是P=0.2×0.2×0.2×0.5×0.4=0.0016。我們可以算出所有路徑的概率得到最大的那個，但是我們上一篇已經學會了維特比算法，你應該學會減少了很多路徑。

注：為什么我們簡單把路徑上的概率乘在一起就可以呢？（一階）馬爾科夫假設事實上是這樣一個東西（豎線|表示“給定，以…為條件”）：image_1c6qsenns13e97qfd7k10bl1b6m9.png-1.9kB（來自維基百科），即在已經出現了前N個狀態的條件下得到第N+1個狀態的概率等于已經出現了第N個狀態時出現第N+1個概率（所以才說“和前天無關只和昨天有關”）。而根據條件概率，我們有
P(Xn+1=輕感冒,Xn=重感冒)=P(Xn+1=輕感冒|Xn=重感冒)P(Xn=重感冒)(0)
即這個人昨天重感冒今天輕感冒的概率（聯合概率）=在昨天重感冒的情況下今天輕感冒的概率（轉移概率）×這個人昨天重感冒的概率。所以如果我們已知昨天這個人重感冒，那么P(Xn=重感冒)=1，這個聯合概率和轉移概率就相等了。 
那么如果轉移兩天呢？比如我們已知一個人第n天重感冒，求第n+1天第n+2天分別是輕感冒、正常的概率呢？我們嘗試著把公式寫出來: 
P(Xn+2=正常,Xn+1=輕感冒,Xn=重感冒)=(1)
P(Xn+2=重感冒|Xn+1=輕感冒,Xn=重感冒)×P(Xn+1=輕感冒,Xn=重感冒) 
也就是說，這三天出現“重感冒、輕感冒、正常”的概率，等于在已知前兩天分別是“重感冒、輕感冒”而最后一天“正常”的概率，乘以前兩天分別“重感冒、輕感冒”的概率。而根據一階馬爾科夫假設，我們知道最后一天“正常”和第一天是什么狀態并沒有什么關系，僅僅和第二天的狀態有關，也就意味著我們發現等式右邊的第一項其實與第二天到第三天的轉移概率相等: 
P(Xn+2=正常|Xn+1=輕感冒,Xn=重感冒)=P(Xn+2=正常|Xn+1=輕感冒) 
所以（1）式就變為了： 
P(Xn+2=正常,Xn+1=輕感冒,Xn=重感冒)= 
P(Xn+2=正常|Xn+1=輕感冒)×P(Xn+1=輕感冒,Xn=重感冒) 
這時候再看最后一項：這個我們熟，在上面(0)呢： 
P(Xn+1=輕感冒,Xn=重感冒)=P(Xn+1=輕感冒|Xn=重感冒)P(Xn=重感冒)所以最后(1)式就變為： 
P(Xn+2=正常,Xn+1=輕感冒,Xn=重感冒)= 
P(Xn+2=正常|Xn+1=輕感冒)P(Xn+1=輕感冒|Xn=重感冒)P(Xn=重感冒) 
也就是說，如果我們知道了第一天“重感冒”的概率P(Xn=重感冒)，想要得到接下來兩天“輕感冒、正常”的概率，我們只需要把相應的轉移概率乘在上面就可以了。所以說如果給定了馬爾科夫鏈的狀態序列，我們就從頭到尾把所有的轉移概率乘在一起就得到了最終這條狀態序列出現的概率。

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

什么是隱馬爾科夫模型？

馬爾科夫模型介紹完了，那么什么是隱馬爾科夫模型？
咱們再舉個栗子，某個小鎮的醫療水平，根本測不出某個人到底是正常，還是輕感冒，還是重感冒。他們鎮的赤腳醫生只能看出來這個人到底是沒什么癥狀、咳嗽、發燒還是拉肚子（旁白：拉肚子是怎么看出來的！）。在這個例子里我們可以認為這四種（活蹦亂跳、咳嗽、發燒、拉肚子）是外在表現，而正常和感冒等等被稱為內在的狀態（事實上是狀態的“輸出”）。我們沒有辦法直接觀測內在狀態，因為他們是隱藏的（沒有醫療器械），但是我們可以直接觀測外在表現。
假設病人的外在表現僅僅和他當天的內在狀態有關，和其他的條件無關（這叫做獨立輸出假設），關系如下表（對應的矩陣叫做發射矩陣，大概是因為是從內在狀態發射出來的外在表現（輸出）吧）：

我們就可以通過觀察他的外在表現來推斷他的內在狀態了。比如如果一個人活蹦亂跳，常識你應該推斷他是正常的（事實上是基于極大似然，咱們先不提），但是如果告訴你這個人2月1號到5號分別是拉肚子、咳嗽、發燒、咳嗽、活蹦亂跳（這個序列叫做輸出序列），讓你寫出可能性最大的狀態序列，也就是他每一天的內在狀態分別是什么，難度上就會大很多了。

隱馬爾科夫模型與籬笆網絡

事實上，在我們不考慮路徑的權重的情況下，整個問題和圖4的網絡沒什么區別。每一天都有可能是三個狀態之一（當然從發射矩陣來看，如果第三天發燒，第三天不大可能是正常的，為什么？），而每一天的狀態遵循一階馬爾科夫假設，僅僅和前一天的狀態有關，所以整個圖的節點是沒有任何區別的。

但是概率（節點的權重）有區別。咱們舉個剛才提到過的例子：第三天是發燒，第二天的任意一個節點指向第三天“正常”這個狀態的概率應該都是0：因為正常這個狀態對發燒的發射概率是0。所以雖然t時刻的狀態僅僅和t-1時刻的狀態有關，但是既然給定了輸出序列，每一個時刻的輸出都給了我們更多關于當天的狀態的信息。
我們舉個更簡單的例子：

已知某人第一天輕感冒，第二天發燒，求第二天最可能的內在狀態。

• 1

表面上看是這樣：從第一天的輕感冒到第二天的三種狀態，僅僅對應著轉移概率：

但是其實可以認為是從這樣：第一天輕感冒，經過轉移之后變為第二天有可能的三種狀態，而每種狀態都會根據他們不同的發射概率發射出四類不同的外在表現：

退化成了這樣：因為這個人第二天的外在表現是發燒，所以其他的外在表現就不考慮了

不過請注意這不是真正的狀態轉移，因為內在的狀態依然是僅僅和前一天的狀態有關，只是因為給了一些新的附加的條件，我們可以對內在狀態的估計進行一定的“修正”。

注：這里的0.4×0.2=0.08事實上是聯合概率 P(Xn?1=輕感冒,Xn=輕感冒,Yn=發燒)(2)
=P(Yn=發燒|Xn?1=輕感冒,Xn=輕感冒)P(Xn?1=輕感冒,Xn=輕感冒) 而因為獨立輸出假設，第n天外在表現為“發燒”，僅僅和第n天內在的狀態有關，和前一天的狀態無關：P(Yn=發燒|Xn?1=輕感冒,Xn=輕感冒)=P(Yn=發燒|Xn=輕感冒)
所以最終(2)式就表現為 P(Xn?1=輕感冒,Xn=輕感冒,Yn=發燒)
=P(Yn=發燒|Xn=輕感冒)P(Xn?1=輕感冒,Xn=輕感冒)其中后一項我們上文已經討論過很多次了，通過轉移概率很容易計算，而前一項就是內在狀態到外在表現的發射概率。

所以最后權重變成了這樣：

從圖上可以看出，第二天內在狀態為輕感冒的概率最大（0，0.08，0.06）。
細心的小伙伴可以看出，三條路徑加在一起并不等于1。的確是的，因為這個聯合概率是要比原本的轉移概率“多了一個條件的”，需要利用貝葉斯公式進行“歸一化”的處理，但是因為我們只需要比較哪條路徑的概率更大，所以我們簡單的把他們乘在一起也不算什么錯誤。

注：理論上來講，我們路徑上標明的其實應該是“已知第一天輕感冒，在給定第二天發燒的條件下，求第二天內在狀態是輕感冒的概率”所以事實上是一個條件概率：
P(Xn=輕感冒|Yn=發燒,Xn?1=輕感冒)而不單單是聯合概率。根據貝葉斯公式我們有 P(Xn=輕感冒|Yn=發燒,Xn?1=輕感冒)

=P(Xn?1=輕感冒,Xn=輕感冒,Yn=發燒)P(Yn=發燒,Xn?1=輕感冒)
=P(Yn=發燒|Xn?1=輕感冒,Xn=輕感冒)P(Xn?1=輕感冒,Xn=輕感冒)P(Yn=發燒,Xn?1=輕感冒)
=P(Yn=發燒|Xn=輕感冒)P(Xn?1=輕感冒,Xn=輕感冒)P(Yn=發燒,Xn?1=輕感冒) 而分數線下面的概率（歸一化系數），輸出僅與當天的內在狀態有關，和前一天的狀態無關
=P(Yn=發燒|Xn=輕感冒)P(Xn?1=輕感冒,Xn=輕感冒)P(Yn=發燒)P(Xn?1=輕感冒) 根據全概率公式
=P(Yn=發燒|Xn=輕感冒)P(Xn?1=輕感冒,Xn=輕感冒)∑XnP(Yn=發燒|Xn)P(Xn?1=輕感冒) 看得出這個歸一化系數就是各條路徑的和，它總是個常數。所以如果我們僅僅考慮哪條路徑最大，是否歸一化其實也區別不大。
同時，對于標注問題來說，隱馬爾科夫模型求得的是一種生成模型，我們本身應該求的就是整條路徑的聯合概率，所以考慮這個問題其實沒有特別大的意義。

下篇文章：
為什么說標注問題可以看做隱馬爾科夫過程？

• n-gram語言模型
• 不是題外話的題外話：拼音輸入法
• 標注問題
  維特比算法怎么解決標注問題？

參考：
http://www.52nlp.cn/hmm-learn-best-practices-two-generating-patterns

總結

以上是生活随笔為你收集整理的小白给小白详解维特比算法（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。