维特比算法（ viterbi）_维比特算法找到概率最大路径

本文的内容大多来自李航的《统计学习方法》
点击此处下载书籍
这篇文章就是想以通俗易懂的方式解析维特比算法，最后用python代码实现。

算法原理

原理显而易见是求动态规划问题：

• 找出每个时刻概率最大的路径
• 将路径上的每个结点连接起来得到最优路径
• 根据观测求出每个时刻最有可能的状态

算法思路

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时刻最有可能的状态。

实现

#@author: James_Bobo
#date: 2019/10/18
'''
Input:
        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]])
'''
import numpy as np
from numpy import *
import math

def viterbi(A, B, PI, O):
    N = shape(A)[0]
    I = mat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23