（僅作為個人的讀書筆記）
**一、前言**
作者：嶽席文
連結：https://www.zhihu.com/question/20136144/answer/154753703
很多人都用隐馬爾科夫模型來回答viterbi算法，其實viterbi算法隻是解決隐馬第三個問題（求觀察序列的最可能的标注序列）的一種實作方式。這個問題可以用于viterbi算法實作，也可以用其他方式實作（如窮舉法）；而viterbi算法可以用于解決隐馬第三問題，也可以用于解決其他問題。是以千萬不要把viterbi算法和隐馬爾科夫模型等價了。
viterbi算法其實就是多步驟每步多選擇模型的最優選擇問題，其在每一步的所有選擇都儲存了前續所有步驟到目前步驟目前選擇的最小總代價（或者最大價值）以及目前代價的情況下前繼步驟的選擇。依次計算完所有步驟後，通過回溯的方法找到最優選擇路徑。符合這個模型的都可以用viterbi算法解決，隐馬模型的第三問題剛好符合這個模型，是以才采用了viterbi算法。
**二、方法對比**
作者：UFO
連結：https://www.zhihu.com/question/20136144/answer/310197856
## 窮舉法
我把所有可能路徑都計算一遍，最優路徑自然就出來了。
缺點：計算量太大。
## A*算法
我每一步隻走最好走的路。
優點：計算快，而且這種貪心或者說啟發式的算法，通常情況下，效果還是不錯的。
缺點：“九陰白骨爪”比“九陰真經”速成，然而要是一開始就練“九陰白骨爪”，多半成不了絕頂高手（最優解）。
## beam search
我每一步隻走最好走的前N條路。這裡的N也叫Beam Width。
上圖是一個Beam Width為2的Beam Search的剪枝示意圖。每一層隻保留2個最優的分支，其餘分支都被剪掉了。
顯然，Beam Width越大，找到最優解的機率越大，相應的計算複雜度也越大。是以，設定合适的Beam Width是一個工程中需要trade off的事情。
## Viterbi算法
這個動圖可以助于了解，但是沒法放了。那就下面這個圖吧，也可以。
**三、舉例了解**
作者：李大雷
連結：https://www.zhihu.com/question/20136144/answer/37291465
1.題目背景：
從前有個村兒，村裡的人的身體情況隻有兩種可能：健康或者發燒。
假設這個村兒的人沒有體溫計或者百度這種神奇東西，他唯一判斷他身體情況的途徑就是到村頭我的偶像金正月的小診所詢問。
月兒通過詢問村民的感覺，判斷她的病情，再假設村民隻會回答正常、頭暈或冷。
有一天村裡奧巴驢就去月兒那去詢問了。
第一天她告訴月兒她感覺正常。
第二天她告訴月兒感覺有點冷。
第三天她告訴月兒感覺有點頭暈。
那麼問題來了，月兒如何根據阿驢的描述的情況，推斷出這三天中阿驢的一個身體狀态呢?
為此月兒上百度搜 google ，一番狂搜，發現維特比算法正好能解決這個問題。月兒樂了。
2.已知情況：
隐含的身體狀态 = { 健康 , 發燒 }
可觀察的感覺狀态 = { 正常 , 冷 , 頭暈 }
月兒預判的阿驢身體狀态的機率分布 = { 健康：0.6 , 發燒： 0.4 }
月兒認為的阿驢身體健康狀态的轉換機率分布 = {
健康->健康： 0.7 ,
健康->發燒： 0.3 ,
發燒->健康：0.4 ,
發燒->發燒： 0.6
}
月兒認為的在相應健康狀況條件下，阿驢的感覺的機率分布 = {
健康，正常：0.5 ，冷 ：0.4 ，頭暈： 0.1 ；
發燒，正常：0.1 ，冷 ：0.3 ，頭暈： 0.6
}
阿驢連續三天的身體感覺依次是： 正常、冷、頭暈 。
3.題目：
已知如上，求：阿驢這三天的身體健康狀态變化的過程是怎麼樣的？
4.過程：
根據 Viterbi 理論，後一天的狀态會依賴前一天的狀态和目前的可觀察的狀态。那麼隻要根據第一天的正常狀态依次推算找出到達第三天頭暈狀态的最大的機率，就可以知道這三天的身體變化情況。
1.初始情況：
- P(健康) = 0.6，P(發燒)=0.4。
2.求第一天的身體情況：
計算在阿驢感覺正常的情況下最可能的身體狀态。
- P(今天健康) = P(正常|健康)*P(健康|初始情況) = 0.5 * 0.6 = 0.3
- P(今天發燒) = P(正常|發燒)*P(發燒|初始情況) = 0.1 * 0.4 = 0.04
那麼就可以認為第一天最可能的身體狀态是：健康。
3.求第二天的身體狀況：
計算在阿驢感覺冷的情況下最可能的身體狀态。
那麼第二天有四種情況，由于第一天的發燒或者健康轉換到第二天的發燒或者健康。
- P(前一天發燒，今天發燒) = P(前一天發燒)*P(發燒->發燒)*P(冷|發燒) = 0.04 * 0.6 * 0.3 = 0.0072
- P(前一天發燒，今天健康) = P(前一天發燒)*P(發燒->健康)*P(冷|健康) = 0.04 * 0.4 * 0.4 = 0.0064
- P(前一天健康，今天健康) = P(前一天健康)*P(健康->健康)*P(冷|健康) = 0.3 * 0.7 * 0.4 = 0.084
- P(前一天健康，今天發燒) = P(前一天健康)*P(健康->發燒)*P(冷|發燒) = 0.3 * 0.3 *0.3 = 0.027
那麼可以認為，第二天最可能的狀态是：健康。
4.求第三天的身體狀态：
計算在阿驢感覺頭暈的情況下最可能的身體狀态。
- P(前一天發燒，今天發燒) = P(前一天發燒)*P(發燒->發燒)*P(頭暈|發燒) = 0.027 * 0.6 * 0.6 = 0.00972
- P(前一天發燒，今天健康) = P(前一天發燒)*P(發燒->健康)*P(頭暈|健康) = 0.027 * 0.4 * 0.1 = 0.00108
- P(前一天健康，今天健康) = P(前一天健康)*P(健康->健康)*P(頭暈|健康) = 0.084 * 0.7 * 0.1 = 0.00588
- P(前一天健康，今天發燒) = P(前一天健康)*P(健康->發燒)*P(頭暈|發燒) = 0.084 * 0.3 *0.6 = 0.01512
那麼可以認為：第三天最可能的狀态是發燒。
反推出結論：發燒（第三天）——>健康（第二天）——>健康（第一天）
看到網上有人說，有正向、逆向結果不一樣的。我想那應該是以逆向的為準吧，因為是找整個的最優解，而不是局部的。
5.結論
根據如上計算。這樣月兒斷定，阿驢這三天身體變化的序列是：健康->健康->發燒。
**四、有關代碼**
此例子也挺好了解，特别是關鍵代碼注釋部分
https://blog.csdn.net/zhangduan8785/article/details/80443650
def viterbi(obs, states, start_p, trans_p, emit_p):
result_m = [{}] # 存放結果,每一個元素是一個字典，每一個字典的形式是 state:(p,pre_state)
# 其中state,p分别是目前狀态下的機率值，pre_state表示該值由上一次的那個狀态計算得到
for s in states: # 對于每一個狀态
result_m[0][s] = (E(start_p[s]*emit_p[s][obs[0]]),None) # 把第一個觀測節點對應的各狀态值計算出來
for t in range(1,len(obs)):
result_m.append({}) # 準備t時刻的結果存放字典，形式同上
for s in states: # 對于每一個t時刻狀态s,擷取t-1時刻每個狀态s0的p,結合由s0轉化為s的轉移機率和s狀态至obs的發散機率
# 計算t時刻s狀态的最大機率，并記錄該機率的來源狀态s0
# max()内部比較的是一個tuple:(p,s0),max比較tuple内的第一個元素值
result_m[t][s] = max([(E(result_m[t-1][s0][0]*trans_p[s0][s]*emit_p[s][obs[t]]),s0) for s0 in states])
return result_m # 所有結果（包括最佳路徑）都在這裡，但直覺的最佳路徑還需要依此結果單獨生成，在顯示的時候生成
1.代碼部分我自己的了解
維特比算法是将客體的一種描述轉換成另一種描述，如這裡所謂的“觀測序列”（‘正常’，‘發冷’，‘發暈’）轉換成這裡所謂的“隐藏序列”（‘健康’，‘生病’）。為了友善了解，以上例子取一種說法，将“觀測序列”說成“感官描述”，将“隐藏序列”說成“健康狀态”。
(1)第一個感官描述轉換（為什麼要單獨拿出來，當然是由于沒有健康狀态的轉移啊）
将第一個感官描述的各種可能的健康狀态都列舉出來。
沒有健康狀态轉移，那就各個健康狀态的影響因素就隻有目前健康狀态的占比和目前健康狀态下此感官描述的占比（就是感受）
for s in states: # 對于每一個狀态
result_m[0][s] = (E(start_p[s]*emit_p[s][obs[0]]),None) # 把第一個觀測節點對應的各狀态值計算出來
(2)後面的感官描述轉換
對于每一個感官描述而言，當然也需要各種可能的健康狀态都列舉出來呀。
for t in range(1,len(obs)):
result_m.append({}) # 準備t時刻的結果存放字典，形式同上
for s in states:
由于不是第一個感官描述，列舉的每一種健康狀态會受到前一健康狀态的影響。影響因素有：前一健康狀态機率、前一健康狀态轉移到目前健康狀态的幾率、目前健康狀态下目前感官描述的幾率。有點暈了～_~
看着主要公式之有一個，很好了解。
result_m[t][s] = max([(E(result_m[t-1][s0][0]*trans_p[s0][s]*emit_p[s][obs[t]]),s0) for s0 in states])
令目前感官描述下目前健康狀态的幾率(P) = max(前一健康狀态機率 × 前一健康狀态轉移到目前健康狀态的幾率 × 目前健康狀态下目前感官描述的幾率)
(前一健康狀态包括所有的健康狀态，展現在for循環處)
此處可能有點繞，但确實是這麼回事。代入執行個體，
今天發暈推出今天生病=max（昨天生病的機率×昨天生病且今天生病的機率×生病感覺發暈的機率，
昨天健康的機率×昨天健康且今天生病的機率×生病感覺發暈的機率）
今天發暈推出今天健康=max（昨天生病的機率×昨天生病且今天健康的機率×健康感覺發暈的機率，
昨天健康的機率×昨天健康且今天健康的機率×健康感覺發暈的機率）
簡而言之，每個感官描述要去找是每個健康狀态的機率，而每個健康狀态要去前一時刻的所有健康狀态中找到能使其最大的健康狀态。
2.參數部分的分析
之前看到自然語言處理——分詞的部分，使用HMM（viterbi）的過程了解的不是很透。（是以訓練出來的參數到底是什麼？？？）經過以上通過症狀描述轉換成健康狀态的例子，照着葫蘆畫瓢。下面用‘有意見分歧’——>'BEMS'（‘觀測序列’——>‘隐藏序列'）為例。
觀測序列：obs，隐藏序列：status，起始機率：start_p，轉移機率：trans_p，發射機率：emit_p
(0)目标
‘有意見分歧’——>'BEMS'模式
(1)觀測序列（原模式）
obs=('有','意','見','分','歧')
(2)隐藏序列（目标模式）
status=('B','E','M','S')
'B':詞的開頭 ,'E':詞的結尾 ,'M':詞的中間 ,'S':單個字的詞
(3)起始機率（隐藏序列，也即目标模式中各個狀态的占比。如“健康”，“生病”各占比。）
start_p={'B': ,'E': ,'M': ,'S': }
(4)轉移機率（隐藏序列，也即目标模式中各個狀态互相轉換的比率。如“健康”——"生病“的機率。）
其中可能的轉移：B->M,B->E ; E->B,E->S ; M->M,M->E ; S->B,S->S
trans_p={'B':{'E': ,'M': },
'E':{'B': ,'S': },
'M':{'M': ,'E': },
'S':{'B': ,'S': }
}
(5)發射機率（對應在”健康判斷“例子中，可以說是隐藏序列中各隐藏序列元對應的各觀測序列元的機率，也即目标模式中各模式對應的各原模式的機率。如”健康”狀态對應：”正常“，”發暈“，”冷“的機率。此處延伸到分詞時，應該是目标模式中各模式對應的所有可能的觀測序列元的機率。換句話講，就是'BEMS'模式中'B','E','M','S'分别對應的各種可能的中文字的機率。因為隻有這樣，才能在某狀态的時候将該狀态對應的某個字識别出來，發射出去。這一點展現在代碼的emit_p[s][obs[t]]處。）
result_m[t][s] = max([(E(result_m[t-1][s0][0]*trans_p[s0][s]*emit_p[s][obs[t]]),s0) for s0 in states])
emit_p={'B':{'有': ,'意': ,'見': ,'分': ,'歧': ...},
'E':{'有': ,'意': ,'見': ,'分': ,'歧': ...},
'M':{'有': ,'意': ,'見': ,'分': ,'歧': ...},
'S':{'有': ,'意': ,'見': ,'分': ,'歧': ...}
}
如有錯誤歡迎指正 ^_^