隐马尔可夫模型的前向算法和后向算法理解与实现（Python）
前言
隐马尔可夫模型（HMM）是可用于标注问题的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。
马尔可夫模型理论与分析
参考《统计学习方法》这本书，书上已经讲得很详细，本文只是想详细分析一下前向算法和后向算法，加深对算法的理解，并希望能帮助到他人。
前向算法理论分析
定义
前向算法的定义.PNG
定义解析：由于每个状态生成一个观测变量，那么在t时刻就会生成t个观测变量，在t时刻处于状态i的概率就是前向概率。
前向算法
算法1.PNG
算法2.PNG
在分析算法之前，先介绍一下隐马尔可夫模型的两个基本假设，后面分析算法会用到这两个假设。
两个基本假设.PNG
下面就简要分析一下前向算法各个步骤表示的意思，只有理解了算法各步骤的意思才能写出代码。
算法的目的：根据初始参数和观测序列求出观测序列概率
步骤（1）初始值：
首先我们假设i = 1的情况，后面的解析依旧采用这样的方法，先假设一种状态，再推广到全部的状态。假设i = 1，则右边表达式的意思依次是，t = 1时刻处于状态1的概率 * 观测变量1的概率 = t = 1时刻状态1生成观测变量1的概率。推广到i = 1,2,3,...,N则整个表达式的意思是：t = 1时刻1~N个状态分别生成观测变量1的概率。
步骤（2）递推：
这里表达式很复杂，分析表达式的意思时，可以先从最里面的求和开始分析，再分析外面的，由内而外的分析思路比较清晰。既然从最里面的求和表达式分析，那么假设t和i不变j = 1时的情况。
当j = 1则公式（10.16）表达式依次表示的意思是，t时刻状态1生成观测变量1的概率 * 状态1到状态i的转移概率 * t + 1时刻状态i下生成观测变量t + 1的概率 = t时刻的状态1转移到t + 1时刻状态i生成观测变量t+1的概率。这里用到了基本假设1，计算t + 1时刻的观测变量概率只依赖于t时刻的状态，与其他状态无关。那么当j = 1,2,3,4,...,N求和时，右边表达式表示意思：t时刻的状态转移到t+1时刻状态i生成观测变量t + 1的概率。
如果想要求出在t时刻的状态转移到t + 1时刻N个状态生成观测变量t+1的概率。那么式子（10.16）处于对i = 1,2,3,...,N的循环下。
如果想要求出在T时刻状态i = 1,2,3,4,...,N分别生成观测变量T的概率，那么式子（10.16）最外面再套一个循环t = 1,2,3,....,T - 1。
步骤（3）终止：
T时刻对N个状态生成观测变量T的概率求和，表示T时刻观测变量T的概率。
前向算法代码
#隐马尔科链模型前向算法
def hmm_forward(A, PI, B, O):
M = shape(PI)[0] #观测序列大小
N = shape(A)[1] #状态序列大小
T = M
alpha = mat(zeros((M, N)))
P = 0.0
for i in range(N):
alpha[0, i] = PI[i, 0] * B[i, 0]
for t in range(T - 1):
for i in range(N):
temp_value = 0.0;
for j in range(N):
temp_value += alpha[t, j] * A[j, i]
index = 0
if(O[t + 1, 0] == 0):
index = 0
else:
index = 1
alpha[t + 1, i] = temp_value * B[i, index]
for i in range(N):
P += alpha[T - 1, i]
return P,alpha
只要对照我的前向算法分析就能看懂代码，并且知道我为什么会那样写。
后向算法理论分析
定义
后向算法定义.PNG
这个定义比较好懂，就不解析了。
后向算法
算法3.PNG
后向算法就不详细分析了，按照我分析前向算法的思路取分析就可清楚的理解每一个步骤代表的意思。
后向算法代码
#隐马尔科链模型后向算法
def hmm_backword(A, PI, B, O):
T,N = shape(A)
beta = mat(zeros((T, N)))
P = 0.0
beta[T - 1, :] = 1
t = T - 2
while t >= 0:
for i in range(N):
temp_value = 0.0
for j in range(N):
index = 0
if(O[t + 1, 0] == 0):
index = 0
else:
index = 1
temp_value += A[i, j] * B[j, index] * beta[t + 1, j]
beta[t, i] = temp_value
t -= 1
for i in range(N):
index = 0
if(O[0, 0] == 0):
index = 0
else:
index = 1
P += PI[i, 0] * B[i, index] * beta[0, i]
return P,beta
完整代码如下
from numpy import *
import numpy as np
import matplotlib as plt
import math
#隐马尔科链模型前向算法
def hmm_forward(A, PI, B, O):
M = shape(PI)[0] #观测序列大小
N = shape(A)[1] #状态序列大小
T = M
alpha = mat(zeros((M, N)))
P = 0.0
for i in range(N):
alpha[0, i] = PI[i, 0] * B[i, 0]
for t in range(T - 1):
for i in range(N):
temp_value = 0.0;
for j in range(N):
temp_value += alpha[t, j] * A[j, i]
index = 0
if(O[t + 1, 0] == 0):
index = 0
else:
index = 1
alpha[t + 1, i] = temp_value * B[i, index]
for i in range(N):
P += alpha[T - 1, i]
return P,alpha
#隐马尔科链模型后向算法
def hmm_backword(A, PI, B, O):
T,N = shape(A)
beta = mat(zeros((T, N)))
P = 0.0
beta[T - 1, :] = 1
t = T - 2
while t >= 0:
for i in range(N):
temp_value = 0.0
for j in range(N):
index = 0
if(O[t + 1, 0] == 0):
index = 0
else:
index = 1
temp_value += A[i, j] * B[j, index] * beta[t + 1, j]
beta[t, i] = temp_value
t -= 1
for i in range(N):
index = 0
if(O[0, 0] == 0):
index = 0
else:
index = 1
P += PI[i, 0] * B[i, index] * beta[0, i]
return P,beta
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]])
P,alpha = hmm_forward(A, PI, B, O)
print(P)
print("--------------------------------------")
P,beta = hmm_backword(A, PI, B, O)
print(P)
输入数据
和《统计学习方法》这本书上的输入数据一样
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
结果分析
由以上输出结果可知，本文的输出结果与书上的输出结果一致，且前向算法和后向算法的输出结果也一致，则本文的前向算法与后向算法完全正确。
