维特比算法理解与实现（Python）

前言

写这篇文章就是想以通俗易懂的方式解析维特比算法，最后给出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这个参数的值，也是和书上的例子是一样的。