HMM_Viterbi

发表于 | 分类于

HMM_Viterbi

算法原理简述：

本篇博客中主要介绍的是关于HMM算法中的维特比算法。该算法主要是给定A,B,PI参数和观测序列的情况下要求求出最有可能出现的状态序列。利用的思想还是动态规划的思想。
主要是定义了两个函数:

  • delta(t, i),表示在所有到t时刻的状态为i的状态序列中概率最大的那个状态序列。
  • psi(t, i)表示在到t时刻状态为i的所有状态序列中概率最大序列的t-1时刻的状态。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : HMM_Viterbi.py
# @Author: mfzhu
# @Date  : 2017/5/7
# @Desc  :
import numpy as np
class HMM_Vtterbi(object):
    def __init__(self, state2state, state2observation, pi):
        self.state2state = state2state
        # 初始化状态转移矩阵
        self.state2observation = state2observation
        # 初始化观测转移矩阵
        self.pi = pi
        # 初始化初始状态概率向量
        self.num_state = len(state2state)
        # 确定模型中的状态数
    def predict(self, sequence):
        # 预测序列的可能状态
        res = []
        # 保存结果
        delta = self.pi * self.state2observation[:, sequence[0]]
        # 初始化delta函数向量
        psi = np.zeros([self.num_state, len(sequence)], int)
        # 初始化psi函数矩阵
        for t in range(1, len(sequence)):
            # 从时刻1开始迭代
            new_delta = []
            psi_col = []
            # 保存当前轮迭代的delta和psi
            for i in range(self.num_state):
                tmp = delta * self.state2state[:, i]
                index = tmp.argmax()
                # 找到最大值所对应的index
                psi_col.append(index)
                new_delta.append(tmp[index] * self.state2observation[i, sequence[t]])
                # 更新当前轮的delta和psi
            psi[:, t] = psi_col
            delta = np.array(new_delta)
            # 保存结果
        last = delta.argmax()
        res.insert(0, last)
        # 回溯找到最大概率所对应的状态序列
        for t in range(len(sequence) - 1, 0, -1):
            res.insert(0, psi[last, t])
            last = int(psi[last, t])
        return res
if __name__ == '__main__':
    state2state = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
    state2observation = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
    pi = np.array([0.2, 0.4, 0.4])
    sequence = [0, 1, 0]
    # 以上数据初始化模型
    v = HMM_Vtterbi(state2state, state2observation, pi)
    print(v.predict(sequence))
    # 训练模型并预测对应的状态序列

代码结果：

通过与李航老师书本上的例子进行比较可知，当前算法的运算结果是正确的。

img