隐马尔科夫模型——前向后向算法python实现

描述：隐马尔科夫模型的三个基本问题之一：概率计算问题。给定模型λ=（A，B，π）和观测序列O=(o1，o2，...，oT)，计算在模型λ下观测序列O出现的概率P(O|λ)

概率计算问题有三种求解方法：

　　直接计算法（时间复杂度为O(TN^T)，计算量非常大，不易实现）

　　前向算法：A：状态转移概率矩阵；B：观测概率矩阵；Pi：初始状态概率向量；O：观测序列

 1 def forward(A, B, Pi, O):
 2     """计算前向概率"""
 3     m = np.shape(A)[0]
 4     n = np.shape(O)[0]
 5     alpha = np.zeros((n, m))
 6 
 7     for i in range(m):
 8         alpha[0][i] = Pi[0][i]*B[i][0]
 9 
10     for t in range(1, n):
11         for i in range(m):
12             sum = 0
13             for j in range(m):
14                 sum += alpha[t-1][j]*A[j][i]
15             alpha[t][i] = sum * B[i][O[t]-1]
16 
17     return alpha
18 
19 def calc_forward(alpha):
20     """前向算法计算观测序列O出现的概率"""
21     p = 0
22     m = np.shape(alpha)[0]
23     for i in range(m):
24         p += alpha[-1][i]
25 
26     return p

　　后向算法：A：状态转移概率矩阵；B：观测概率矩阵；Pi：初始状态概率向量；O：观测序列

 1 # 方法一
 2 def backward1(A, B, Pi, O):
 3     """计算后向概率"""
 4     m = np.shape(A)[0]
 5     n = np.shape(O)[0]
 6     beta = np.zeros((n, m))
 7     sum_beta = np.zeros((m, m))
 8 
 9     for i in range(m):
10         beta[n-1][i] = 1
11 
12     for t in range(n-1, 0, -1):
13         for i in range(m):
14             for j in range(m):
15                 sum_beta[i, j] = A[i, j]*B[j, O[t]-1]*beta[t, j]
16         beta[t-1][:] = sum_beta.sum(1)
17 
18     return beta
19 
20 # 方法二
21 def backward(A, B, Pi, O):
22     """计算后向概率"""
23     m = np.shape(A)[0]
24     n = np.shape(O)[0]
25     beta = np.zeros((n, m))
26     sum_beta = np.zeros((m, m))
27 
28     for i in range(m):
29         beta[n-1][i] = 1
30 
31     for t in range(n-1, 0, -1):
32         for i in range(m):
33             sum_beta[i, :] = A[i, :]*B[:, O[t]-1]*beta[t, :]
34         beta[t-1][:] = sum_beta.sum(1)
35 
36     return beta
37 
38 def calc_backward(beta, Pi, B):
39     """后向算法计算观测概率O出现的概率"""
40     r = Pi[0]*B[:, 0]*beta[0, :]
41     p = r.sum()
42 
43     return p