RT，HMM中的维特比解码，给定观测序列的情况下求概率最大的隐藏的状态序列？
思路：
模拟小蓝本HMM中的例子，
开始前向传播
1. 对于每个观测序列来说，对于每个状态，记录当前的前向向量fai 当初始的第一个观测序列值，fai 由 pai和B求得 否则fai由最大的前向向量和A的乘积最大，然后再乘以B求得
2. 求完每个前向向量，记录当前状态下的最大路径的上一个状态
开始回溯
3. 第N个前向向量求完，取最大的前项向量最大值，得到最终状态
4. 根据最终状态，逐渐回溯，得到最终解码序列
代码如下：
A = [ [0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5] ] B = [ [0.5, 0.5], [0.4, 0.6], [0.7, 0.3] ] pai = [0.2, 0.4, 0.4] def Viterbi(pai, A, B): # pai is list # A, B is matrix # 1. forward broadcast .. for i in range(len(guanceLst)): for j in range(len(stateLst)): # init if i == 0: forward[i][j] = pai[j] * B[j][guanceLst[i]] else: maxx = 0 # get maxx from last forward vector for k in range(len(stateLst)): tmp = forward[i-1][k] * A[k][j] if tmp > maxx: maxx = tmp keep[i][j] = k # save # update forward vector forward[i][j] = maxx * B[j][guanceLst[i]] # 2. backward P = max(forward[len(guanceLst)-1][:]) last = forward[len(guanceLst)-1][:].indexOf(P) # 3. result res = [] res.append(last) cur = last for w in range(len(guanceLst)-1,1,-1): cur = keep[w][cur] res.append(cur) return res[::-1]
