引言

viterbi算法簡化最有可能的天氣序列的運(yùn)算過程，forward算法簡化該該觀察值的概率。

問題描述

你在中國，你朋友F在美國，F的作息有walk, shop, clean，但這選擇跟天氣有關(guān)，我們又知道Rainy的概率比Sunny的概率大
這是初始概率

這是天氣轉(zhuǎn)移矩陣

這是在相應(yīng)天氣下發(fā)生相應(yīng)事的概率分布
然后，F這三天是walk，walk，shop，問最有可能的天氣序列

問題分析

同樣的，我們先用窮舉法來算，即

Sunny Sunny Sunny?
Sunny Sunny Rainy
Sunny Rainy Sunny
Sunny Rainy Rainy
Rainy?Sunny Sunny
Rainy?Sunny Rainy
Rainy?Rainy Sunny
Rainy?Rainy Rainy

分別求出在各個(gè)情況下，{walk，walk，shop}的概率，然后比較概率，最大的就是我們想要的結(jié)果，我們發(fā)現(xiàn)這跟我們forward的應(yīng)用場景相似，只不過，forward算法是求和，而viterbi算法是求最大，forward算法是所有路徑之和，而viterbi算法只是求一條路徑。這也就意味著這兩算法可以寫在一起。

那我們重點(diǎn)講講算法吧，這次我是看wiki上的代碼，再寫，再比較，發(fā)現(xiàn)wiki上的代碼有一處甚是費(fèi)解，因此，加以修改，并一目了然了，我把我的思考羅列如下

1）我的思路是把第一天的情況特殊考慮，可wiki上的代碼直接整合在一起了，其意義甚是費(fèi)解，所以，我把第一天特殊考慮了

2）再者，我發(fā)現(xiàn)wiki上的代碼，明明要求只需要確定三天的天氣卻出現(xiàn)四天的天氣，估計(jì)是第一天沒用的

3）我修改后代碼跟wiki上代碼，forward算法最終結(jié)果是一樣的，但過程中求得值是不一樣的

4）用viterbi求得概率是不同的，但wiki上的代碼，把第一天去掉之后，剩下的天氣序列跟我的是一樣

不管怎樣，wiki上的代碼整體框架還是非常好的（或許還是我改錯(cuò)了），思路如下：

1）我上一篇自己寫forward算法，差不多用二維數(shù)組來記錄整個(gè)過程，其實(shí)沒必要，只需一維足以，用完一行，替代一行，所以才會(huì)有字典T和字典U

2）返回三樣，分別是該觀察序列的最大概率（即之前用forward求出來的），最可能出現(xiàn)的天氣序列，該天氣序列的概率，同時(shí)每次都更新這三個(gè)值

3）三重for循環(huán)，第一重是第幾天，第二重是第幾天晴天還是雨天，第三重是前一天是晴天還是雨天下求得概率，再具體求和，求最大值

我稍加修改的Python代碼及結(jié)果

1 def forward_viterbi(obs, states, start_p, trans_p, emit_p): 2 T = {} 3 #for the first one 4 for state in states: 5 T[state] = (start_p[state] * emit_p[state][obs[0]], [state], start_p[state]) 6 for output in obs: 7 U = {} 8 #pass the first one 9 if output == obs[0]: 10 continue 11 for next_state in states: 12 total = 0 13 argmax = None 14 valmax = 0 15 for source_state in states: 16 #get the previous one 17 (prob, v_path, v_prob) = T[source_state] 18 #caculate the commone one 19 p = trans_p[source_state][next_state] * emit_p[next_state][output] 20 prob *= p 21 v_prob *= p 22 #sum up 23 total += prob 24 #find the max 25 if v_prob > valmax: 26 argmax = v_path + [next_state] 27 valmax = v_prob 28 U[next_state] = (total, argmax, valmax) 29 T = U 30 #sum up & find the max one 31 total = 0 32 argmax = None 33 valmax = 0 34 for state in states: 35 (prob, v_path, v_prob) = T[state] 36 total += prob 37 if v_prob > valmax: 38 valmax = v_prob 39 argmax = v_path 40 return (total, argmax, valmax) 41 states = ('Rainy', 'Sunny') 42 observations = ('walk', 'shop', 'clean') 43 start_probability = {'Rainy': 0.6, 'Sunny': 0.4} 44 transition_probability = { 45 'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3}, 46 'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6}, 47 } 48 emission_probability = { 49 'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5}, 50 'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}, 51 } 52 #A simple example of the using algorithm 53 def example(): 54 return forward_viterbi(observations, 55 states, 56 start_probability, 57 transition_probability, 58 emission_probability) 59 print example() 60 61 #(0.033611999999999996, ['Rainy', 'Rainy', 'Rainy'], 0.05879999999999999)

?

wiki代碼及結(jié)果

1 def forward_viterbi(obs, states, start_p, trans_p, emit_p): 2 T = {} 3 for state in states: 4 ## prob. V. path V. prob. 5 T[state] = (start_p[state], [state], start_p[state]) 6 for output in obs: 7 print T 8 U = {} 9 for next_state in states: 10 total = 0 11 argmax = None 12 valmax = 0 13 for source_state in states: 14 (prob, v_path, v_prob) = T[source_state] 15 p = emit_p[source_state][output] * trans_p[source_state][next_state] 16 #caculate 17 prob *= p 18 v_prob *= p 19 #the different way to gain 20 total += prob 21 if v_prob > valmax: 22 argmax = v_path + [next_state] 23 valmax = v_prob 24 U[next_state] = (total, argmax, valmax) 25 T = U 26 print T 27 ## apply sum/max to the final states: 28 total = 0 29 argmax = None 30 valmax = 0 31 for state in states: 32 (prob, v_path, v_prob) = T[state] 33 total += prob 34 if v_prob > valmax: 35 argmax = v_path 36 valmax = v_prob 37 return (total, argmax, valmax) 38 39 states = ('Rainy', 'Sunny') 40 observations = ('walk', 'shop', 'clean') 41 start_probability = {'Rainy': 0.6, 'Sunny': 0.4} 42 transition_probability = { 43 'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3}, 44 'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6}, 45 } 46 emission_probability = { 47 'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5}, 48 'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}, 49 } 50 #A simple example of the using algorithm 51 def example(): 52 return forward_viterbi(observations, 53 states, 54 start_probability, 55 transition_probability, 56 emission_probability) 57 print example() 58 59 #(0.033611999999999996, ['Sunny', 'Rainy', 'Rainy', 'Rainy'], 0.009407999999999998)

總結(jié)

以上是生活随笔為你收集整理的隐马尔可夫HMM中viterbi算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。