Forward和Viterbi的一个Python实现

qweewq123qwe

　　前一向研究HMM(隐马尔可夫模型)，在wiki上看到了一个python实现的forward&viterbi算法，就先放在这里，过几天研究。HMM是人们在研究人工智能(语音设别，模式识别)方面的一个重要理论，差不多相当于“知道一些线索的情况下，跟据结论推出结果”的算法，很简单，很强大!
　　好了，先看看这个代码，慢慢分析之

def forward_viterbi(obs, states, start_p, trans_p, emit_p):
T = {}
for state in states:
##          prob.           V. path  V. prob.
T[state] = (start_p[state], [state], start_p[state])
for output in obs:
U = {}
for next_state in states:
total = 0
argmax = None
valmax = 0
for source_state in states:
(prob, v_path, v_prob) = T[source_state]
p = emit_p[source_state][output] * trans_p[source_state][next_state]
prob *= p
v_prob *= p
total += prob
if v_prob > valmax:
argmax = v_path + [next_state]
valmax = v_prob
U[next_state] = (total, argmax, valmax)
T = U
## apply sum/max to the final states:
total = 0
argmax = None
valmax = 0
for state in states:
(prob, v_path, v_prob) = T[state]
total += prob
if v_prob > valmax:
argmax = v_path
valmax = v_prob
return (total, argmax, valmax)

　　python就是简单，这要撂别的高级语言，这么短的代码说不定连局部变量还没初始化完呢。这个是算法主题，下面是如何测试这个算法的一个小函数和几个状态集合。

states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {
'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
}
emission_probability = {
'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}
#A simple example of the using algorithm
def example():
return forward_viterbi(observations,
states,
start_probability,
transition_probability,
emission_probability)
print example()
　　okay,这些代码放入一个文件，就可以做一个简单的测试了。先把代码放在这里，过几天完整的分析一下。