HMM

# coding:utf-8
## viterbi算法
# 根据观测，求最优状态
import numpy as np
import copy
A = np.array([0.5,0.3,0.2,0.2,0.5,0.3,0.3,0.2,0.5]).reshape((3,3),order='F')
B = np.array([0.5,0.4,0.7,0.5,0.6,0.3]).reshape((3,2),order='F')
P = np.array([0.2,0.4,0.4])
O = np.array([0,1,0])
# A ：状态转移矩阵
# B ：观测矩阵
# P ：初始状态概率
# O ：观测序列
laststate = P*B[:,O[0]]
tmp = np.zeros(len(laststate))
dp = np.zeros((len(A), len(O)),dtype='int')
print laststate # 初始状态
for t in range(1,len(O)): # 序列长度
    for i in range(len(A)): # 状态数
        state = laststate*A[:,i]*B[i,O[t]] # 这里B只用一个值，从状态i观测O[t]
        dp[i][t] = state.argmax()
        tmp[i] = state.max()
    laststate = copy.copy(tmp)
end = laststate.argmax()
# 输出最优序列
end = 0
res = []
res.append(end)
cnt = len(dp[0])-1
for i in range(cnt,0,-1):
    res.append(dp[end,cnt])
    end = dp[end,cnt]
    cnt = cnt - 1
res.reverse()
print res