前言
写这篇文章就是想以通俗易懂的方式解析维特比算法，最后给出Python代码的实现。下面的公式和原理均出自《统计学习方法》。
算法的原理
算法的原理1.PNG
算法的原理2.PNG
上面写了一大堆，意思就是：每个时刻选择出概率最大的路径，将路径上的每个结点连接起来就得到了最优路径。那么可以根据这个原理，很容易就可以根据观测求出每个时刻最有可能的状态。
算法的思路
算法思路1.PNG
算法思路2.PNG
下面我们可以根据算法的原理，分析书上算法的思路。
步骤(1)初始化：
t = 1时刻分别求出N个状态下产生观测变量1的概率。
步骤(2)递推：
当t和i不变时j = 1,2,3,...,N是分别求出t - 1时刻所有可能的状态，转移到t时刻状态i的概率。max是求最大值，就是在t-1时刻各个状态转移到t时刻状态 i 的最大概率，最后乘以观测概率就是t状态 i 最有可能产生观测变量 t 的概率。argmax是求在t-1时刻的状态最有可能转移到 t 时刻的状态 i 。
如果想求出t - 1时刻的所有可能状态转移到 t 时刻所有可能状态的最大概率，则在步骤(2)的式子最外层再增加一个循环i = 1,2,3,...,N。
如果想求出各个时刻最有可能的状态，则在步骤(2)的式子最外层增加一个循环t = 2,3,4,...,T。
步骤(3)终止：
这个很简单没什么好说的了。
步骤(4)最优路径回溯：
根据t = T时刻最有可能的状态反向推出t = T - 1, t = T - 1,...,2,1时刻最有可能的状态。
完整实现代码
import numpy as np
from numpy import *
import math
def viterbi(A, B, PI, O):
N = shape(A)[0]
I = mat(zeros((N, 1)))
T = N
sigma = mat(zeros((N, N)))
omiga = mat(ones((N, N)))
index = 0
for i in range(N):
if(O[0, 0] == 0):
index = 0
else:
index = 1
sigma[0, i] = PI[i, 0] * B[i, index]
t = 1
while(t < T):
for i in range(N):
sigma_temp = mat(zeros((N, 1)))
for j in range(N):
sigma_temp[j, 0] = sigma[t - 1, j] * A[j, i]
max_value = sigma_temp.max(axis = 0)
if(O[t, 0] == 0):
index = 0
else:
index = 1
sigma[t, i] = max_value[0, 0] * B[i, index]
omiga[t, i] = sigma_temp.argmax() + 1
t += 1
P = sigma[N - 1, :].max()
I[T -1, 0] = sigma[N - 1, :].argmax() + 1
t = T - 2
print(omiga)
while(t >= 0):
index = int(I[t + 1, 0] - 1)
I[t, 0] = omiga[t + 1, index]
t -= 1
return I
if __name__ == "__main__":
A = mat([[0.5, 0.2, 0.3],
[0.3, 0.5, 0.2],
[0.2, 0.3, 0.5]])
B = mat([[0.5, 0.5],
[0.4, 0.6],
[0.7, 0.3]])
PI = mat([[0.2],
[0.4],
[0.4]])
O = mat([[0],
[1],
[0]])
I = viterbi(A, B, PI, O)
print(I)
输入数据
输入数据和《统计学习方法》这本书上的例子一样
A = mat([[0.5, 0.2, 0.3],
[0.3, 0.5, 0.2],
[0.2, 0.3, 0.5]])
B = mat([[0.5, 0.5],
[0.4, 0.6],
[0.7, 0.3]])
PI = mat([[0.2],
[0.4],
[0.4]])
O = mat([[0],
[1],
[0]])
输入数据.PNG
本文的输出结果
输出结果.PNG
书上的输出结果
书上的输出结果.PNG
两者结果对比是一样的，有兴趣的可以运行一下我的代码，打印出w这个参数的值，也是和书上的例子是一样的。
