【机器学习】隐马尔可夫模型及其三个基本问题（二）观测序列概率计算算法及python实现

隐马尔可夫（HMM）模型的第一个基本问题是评估观测序列概率：

给定模型λ=[A,B,∏]\lambda = \left[ {A,B,\prod } \right]λ=[A,B,∏]和观测序列X={x1,x2,⋯ ,xn}X = \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\}X={x1​,x2​,⋯,xn​}，计算模型λ\lambdaλ下观测序列XXX出现的概率P(X∣λ)P\left( {X\left| \lambda \right.} \right)P(X∣λ)。

一、前向算法

1、前向概率：给定隐马尔可夫模型λ\lambdaλ，到时刻ttt为止，观测序列为{x1,x2,⋯ ,xt}\left\{ {{x_1},{x_2}, \cdots ,{x_t}} \right\}{x1​,x2​,⋯,xt​}，且时刻ttt的隐藏状态yt=qiy_t=q_iyt​=qi​的概率为前向概率，记为：

αt(i)=P(x1,x2,⋯ ,xt,yt=qi∣λ){\alpha _t}\left( i \right) = P\left( {{x_1},{x_2}, \cdots ,{x_t},{y_t} = {q_i}\left| \lambda \right.} \right)αt​(i)=P(x1​,x2​,⋯,xt​,yt​=qi​∣λ)

2、前向算法是一个递推过程，具体步骤如下：

输入：隐马尔可夫模型λ\lambdaλ，观测序列XXX。

输出：观测序列概率P(X∣λ)P\left( {X\left| \lambda \right.} \right)P(X∣λ)。

（1）初始化：α1(i)=πibi(x1){\alpha _1}(i) = {\pi _i}{b_i}({x_1})α1​(i)=πi​bi​(x1​)，i=1,2,⋯ ,Ni = 1,2, \cdots ,Ni=1,2,⋯,N

（2）递推：ttt fromfromfrom 111 tototo n−1n-1n−1

αt+1(i)=[∑j=1Nαt(j)aji]bi(xt+1){\alpha _{t + 1}}\left( i \right) = \left[ {\sum\limits_{j = 1}^N {{\alpha _t}\left( j \right){a_{ji}}} } \right]{b_i}\left( {{x_{t + 1}}} \right)αt+1​(i)=[j=1∑N​αt​(j)aji​]bi​(xt+1​)，i=1,2,⋯ ,Ni = 1,2, \cdots ,Ni=1,2,⋯,N

（3）终止：P(X∣λ)=∑i=1Nαn(i)P\left( {X\left| \lambda \right.} \right) = \sum\limits_{i = 1}^N {{\alpha _n}\left( i \right)}P(X∣λ)=i=1∑N​αn​(i)

3、算法分析

αt(j){\alpha _t}\left( j \right)αt​(j)是到时刻ttt为止，观测序列为{x1,x2,⋯ ,xt}\left\{ {{x_1},{x_2}, \cdots ,{x_t}} \right\}{x1​,x2​,⋯,xt​}，且时刻ttt的隐藏状态yt=qjy_t=q_jyt​=qj​的前向概率，那么αt(j)aji{{\alpha _t}\left( j \right){a_{ji}}}αt​(j)aji​是到时刻ttt，观测序列为{x1,x2,⋯ ,xt}\left\{ {{x_1},{x_2}, \cdots ,{x_t}} \right\}{x1​,x2​,⋯,xt​}，时刻ttt的隐藏状态yt=qjy_t=q_jyt​=qj​而在时刻t+1t+1t+1到达状态qiq_iqi​的概率。对这个乘积在时刻ttt的所有可能的NNN个状态qjq_jqj​求和，其结果就是到时刻ttt，观测序列为{x1,x2,⋯ ,xt}\left\{ {{x_1},{x_2}, \cdots ,{x_t}} \right\}{x1​,x2​,⋯,xt​}，且在时刻t+1t+1t+1隐含状态为qiq_iqi​的联合概率。

αt+1(i)=[∑j=1Nαt(j)aji]bi(xt+1){\alpha _{t + 1}}\left( i \right) =\left[ {\sum\limits_{j = 1}^N {{\alpha _t}\left( j \right){a_{ji}}} } \right]{b_i}\left( {{x_{t + 1}}} \right)αt+1​(i)=[j=1∑N​αt​(j)aji​]bi​(xt+1​)是到时刻t+1t+1t+1观测序列为{x1,x2,⋯ ,xt,xt+1}\left\{ {{x_1},{x_2}, \cdots ,{x_t},{x_{t+1}}} \right\}{x1​,x2​,⋯,xt​,xt+1​}，并在时刻t+1t+1t+1处于隐含状态qiq_iqi​的前向概率。

二、后向算法

1、后向概率：给定隐马尔可夫模型λ\lambdaλ，定义在时刻ttt隐含状态yt=qiy_t=q_iyt​=qi​的前提下，从t+1t+1t+1到nnn的部分观测序列为{xt+1,xt+2,⋯ ,xn}\left\{ {{x_{t + 1}},{x_{t + 2}}, \cdots ,{x_n}} \right\}{xt+1​,xt+2​,⋯,xn​}的概率为后向概率，记为：

βt(i)=P(xt+1,xt+2,⋯ ,xn∣yt=qi,λ){\beta _t}\left( i \right) = P\left( {{x_{t + 1}},{x_{t + 2}}, \cdots ,{x_n}\left| {{y_t} = {q_i},\lambda } \right.} \right)βt​(i)=P(xt+1​,xt+2​,⋯,xn​∣yt​=qi​,λ)

2、后向算法也是一个递推过程，具体步骤如下

输入：隐马尔可夫模型λ\lambdaλ，观测序列XXX。

输出：观测序列概率P(X∣λ)P\left( {X\left| \lambda \right.} \right)P(X∣λ)。

（1）初始化：βn(i)=1{\beta _n}\left( i \right) = 1βn​(i)=1，i=1,2,⋯ ,Ni = 1,2, \cdots ,Ni=1,2,⋯,N

（2）递推：ttt fromfromfrom n−1n-1n−1 tototo 111

βt(i)=∑j=1Naijbj(xt+1)βt+1(j){\beta _t}\left( i \right) = \sum\limits_{j = 1}^N {{a_{ij}}{b_j}\left( {{x_{t + 1}}} \right){\beta _{t + 1}}\left( j \right)}βt​(i)=j=1∑N​aij​bj​(xt+1​)βt+1​(j)，i=1,2,⋯ ,Ni = 1,2, \cdots ,Ni=1,2,⋯,N

（3）终止：P(X∣λ)=∑i=1Nπibi(x1)β1(i)P\left( {X\left| \lambda \right.} \right) = \sum\limits_{i = 1}^N {{\pi _i}{b_i}\left( {{x_1}} \right){\beta _1}\left( i \right)}P(X∣λ)=i=1∑N​πi​bi​(x1​)β1​(i)

3、算法分析

为了计算在时刻ttt隐含状态为qi{q_i}qi​条件下时刻t+1t+1t+1之后的观测序列为{xt+1,xt+2,⋯ ,xn}\left\{ {{x_{t + 1}},{x_{t + 2}}, \cdots ,{x_n}} \right\}{xt+1​,xt+2​,⋯,xn​}的后向概率βt(i){\beta _t}\left( i \right)βt​(i),只需考虑在时刻t+1t+1t+1所有可能的NNN个状态qjq_jqj​的转移概率（aija_{ij}aij​），以及在此状态下的观测xt+1x_{t+1}xt+1​的观测概率（bj(xt+1){{b_j}\left( {{x_{t + 1}}} \right)}bj​(xt+1​)），然后考虑状态qjq_jqj​

三、前向-后向算法的python实现

本博客的python代码的HMM模型采用上一篇博客最后部分举出的实例。观测序列为[红，白，红]，在python中观测序列为O=[0,1,0]O=[0,1,0]O=[0,1,0]。

python代码如下（参考资料2）

import numpy as npclass FB:def __init__(self, A, B, Pi, O):self.A = np.array(A) # 状态转移概率矩阵self.B = np.array(B) # 观测概率矩阵self.Pi = np.array(Pi) # 初始状态概率矩阵self.O = np.array(O) # 观测序列self.N = self.A.shape[0] # 状态取值个数self.M = self.B.shape[1] # 观测值取值个数## 1. 前向算法def forward(self):n = len(self.O) #观测序列长度alpha = np.zeros((n,self.N)) # 初始化所有alpha值# 计算初始值for i in range(self.N):alpha[0,i] = self.Pi[i] * self.B[i,self.O[0]]# 递推for t in range(n-1):for i in range(self.N):summation = 0 for j in range(self.N):summation += alpha[t,j] * self.A[j,i]alpha[t+1,i] = summation * self.B[i,self.O[t+1]]# 终止Polambda = 0.0 # 在模型确定的情况下观测序列概率for i in range(self.N):Polambda += alpha[n-1,i]return Polambda,alpha## 2. 后向算法def backward(self):n = len(self.O) #观测序列长度beta = np.zeros((n,self.N)) # 初始化所有beta值# 计算初始值for i in range(self.N):beta[n-1,i] = 1.0# 递推for t in range(n-2,-1,-1):for i in range(self.N):summation = 0.0# for every i 'summation' should reset to '0'for j in range(self.N):summation += self.A[i,j] * self.B[j, self.O[t+1]] * beta[t+1,j]beta[t,i] = summation# 终止Polambda = 0.0for i in range(self.N):Polambda += self.Pi[i] * self.B[i, self.O[0]] * beta[0, i]return Polambda, betaif __name__ == '__main__':print('--------------1.HMM 模型---------------')A = [[0,1,0,0],[0.4,0,0.6,0],[0,0.4,0,0.6],[0,0,0.5,0.5]]B = [[0.5,0.5],[0.3,0.7],[0.6,0.4],[0.8,0.2]]Pi = [0.25,0.25,0.25,0.25]print('------------- 2.观测序列---------------')O = [0,1,0]print('--------------3.前向后向算法-----------')fb = FB(A,B,Pi,O)f_P,alpha = fb.forward()print('前向算法计算观测序列概率为：',f_P)b_P,beta = fb.backward()print('后向算法计算观测序列概率为：',b_P)

参考资料

1、《统计学习方法》李航

2、/d-roger/articles/5719979.html

如果觉得《【机器学习】隐马尔可夫模型及其三个基本问题（二）观测序列概率计算算法及python实现》对你有帮助，请点赞、收藏，并留下你的观点哦！