学习隐马尔可夫模型（HMM），主要就是学习三个问题：概率计算问题，学习问题和预测问题。概率计算问题主要是讲前向算法和后向算法，这两个算法可以说是隐马尔可夫的重中之重，接下来会依次介绍以下内容。
补充：推导公式很依赖模型的假设与贝叶斯网络，所以在这之前最好了解贝叶斯网络，这两天会补充贝叶斯网络。
学习资料：《统计学习方法》，邹博老师的HMM的ppt，其他。
隐马尔可夫模型是关于时序的概率模型。由一个隐藏的马尔可夫链随机生成的不可观测的状态随机序列（理解为隐变量），再由各个状态生成一个观测而产生观测随机序列（理解为显变量）的过程。如下图就是一个隐马尔可夫链，状态序列 { Z 1 , Z 2 , . . . , Z n + 1 } {Z_1,Z_2,...,Z_{n+1}} {Z1,Z2,...,Zn+1}，再由各个状态序列生成观测序列 { X 1 , X 2 , . . . , X n + 1 } {X_1,X_2,...,X_{n+1}} {X1,X2,...,Xn+1}，而每个节点（位置）对应一个时刻，从前往后就是时刻 t 1 , t 2 , . . . , t n + 1 t_1,t_2,...,t_{n+1} t1,t2,...,tn+1。
隐马尔可夫模型由初始状态概率向量 π pi π、状态转移矩阵 A A A和观测矩阵 B B B确定，称为隐马尔可夫三要素，表示为 λ = ( π , A , B ) lambda=(pi,A,B) λ=(π,A,B)，关于具体的参数介绍如下：
记： Q = { q 1 , q 2 , . . . , q N } Q={q_1,q_2,...,q_N} Q={q1,q2,...,qN}表示所有可能的状态集合， V = { v 1 , v 2 , . . . , v M } V={v_1,v_2,...,v_M} V={v1,v2,...,vM}表示所有可能的观测集合。
I = { i 1 , i 2 , . . . , i T } I={i_1,i_2,...,i_T} I={i1,i2,...,iT} 表示状态序列， O = { o 1 , o 2 , . . . , o N } O={o_1,o_2,...,o_N} O={o1,o2,...,oN} 为对应的观测序列。
状态转移矩阵 A A A:
令 a i j = P ( i t + 1 = q j ∣ i t = q i ) a_{ij}=P(i_{t+1}=q_j|i_{t}=q_i) aij=P(it+1=qj∣it=qi) 表示 t t t时刻状态为 q i q_i qi，下一时刻（即 t + 1 t+1 t+1）状态为 q j q_j qj的概率，而状态转移矩阵 A = ( a i j ) N × N A=(a_{ij})_{N×N} A=(aij)N×N，注意这里是 N × N N×N N×N的方阵。
观测矩阵 B B B:
令 b j ( k ) = P ( o t = v k ∣ i t = q j ) b_{j}(k)=P(o_t=v_k|i_t=q_j) bj(k)=P(ot=vk∣it=qj)表示 t t t时刻状态为 q j q_j qj的条件下，观测值为 v k v_k vk的概率，而观测矩阵 B = ( b j ( k ) ) N × M B=(b_{j}(k))_{N×M} B=(bj(k))N×M。
初始状态概率向量 π pi π：
π i = P ( i 1 = q i ) pi_i=P(i_1=q_i) πi=P(i1=qi)表示初始时刻（即 t = 1 t=1 t=1）时状态为 q i q_i qi的概率。
π , A pi,A π,A决定状态序列， B B B决定观测序列。
由以上定义知，隐马尔可夫做了如下两个假设（两个基本性质）：
下面给出《统计学习方法》上的盒子和球的例子
隐马尔可夫模型有三个基本问题：
在这里就只讲概率计算问题，后面会接着讲学习问题和预测问题。
概率计算问题指的是给定模型 λ = ( π , A , B ) lambda=(pi,A,B) λ=(π,A,B)和观测序列 O = { o 1 , o 2 , . . . , o N } O={o_1,o_2,...,o_N} O={o1,o2,...,oN}，求在模型 λ lambda λ下，观测序列 O O O出现的概率，即 P ( O ∣ λ ) P(O|lambda) P(O∣λ)，下面会介绍三个方法来讲述，分别为
1、直接计算法
给定模型 λ = ( π , A , B ) lambda=(pi,A,B) λ=(π,A,B)和观测序列 O = { o 1 , o 2 , . . . , o N } O={o_1,o_2,...,o_N} O={o1,o2,...,oN}，计算 P ( O ∣ λ ) P(O|lambda) P(O∣λ)。
P ( O ∣ λ ) = ∑ I P ( I ∣ λ ) P ( O ∣ I , λ ) P(O|lambda)=sumlimits_{I}P(I|lambda)P(O|I,lambda) P(O∣λ)=I∑P(I∣λ)P(O∣I,λ)
补充：根据贝叶斯网络，对于任意随机变量有 P ( x 1 , x 2 , . . . , x N ) = P ( x N ∣ x 1 , . . . , X N − 1 ) . . . P ( x 2 ∣ x 1 ) P ( x 1 ) P(x_1,x_2,...,x_N)=P(x_N|x_1,...,X_{N-1})...P(x_2|x_1)P(x_1) P(x1,x2,...,xN)=P(xN∣x1,...,XN−1)...P(x2∣x1)P(x1)
计算 P ( I ∣ λ ) P(I|lambda) P(I∣λ):
P ( I ∣ λ ) = P ( i 1 , i 2 , . . . , i T ∣ λ ) = P ( i 1 ∣ λ ) P ( i 2 , . . . , i T ∣ i 1 , λ ) = π i 1 P ( i 3 , . . . , i T ∣ i 2 , i 1 , λ ) P ( i 2 ∣ i 1 , λ ) = π i 1 a i 1 i 2 P ( i 3 , . . . , i T ∣ i 2 , i 1 , λ ) P(I|lambda)=P(i_1,i_2,...,i_T|lambda)=P(i_1|lambda)P(i_2,...,i_T|i_1,lambda)=pi_{i_1}P(i_3,...,i_T|i_2,i_1,lambda)P(i_2|i_1,lambda)=pi_{i_1}a_{i_1i_2}P(i_3,...,i_T|i_2,i_1,lambda) P(I∣λ)=P(i1,i2,...,iT∣λ)=P(i1∣λ)P(i2,...,iT∣i1,λ)=πi1P(i3,...,iT∣i2,i1,λ)P(i2∣i1,λ)=πi1ai1i2P(i3,...,iT∣i2,i1,λ)
由于状态2给定条件下，状态1和其它状态条件独立（这点由贝叶斯网络得出，或者根据HMM的齐次性假设， i 3 , . . . , i T i_3,...,i_T i3,...,iT与 i 1 i_1 i1是相互独立的），所以 P ( i 3 , . . . , i T ∣ i 2 , i 1 , λ ) = P ( i 3 , . . . , i T ∣ i 2 , λ ) P(i_3,...,i_T|i_2,i_1,lambda)=P(i_3,...,i_T|i_2,lambda) P(i3,...,iT∣i2,i1,λ)=P(i3,...,iT∣i2,λ)，所以有
P ( I ∣ λ ) = π i 1 a i 1 i 2 P ( i 3 , . . . , i T ∣ i 2 , λ ) = π i 1 a i 1 i 2 P ( i 4 , . . . , i T ∣ i 3 , i 2 , λ ) P ( i 3 ∣ i 2 , λ ) = π i 1 a i 1 i 2 a i 2 i 3 P ( i 4 , . . . , i T ∣ i 3 , i 2 , λ ) = . . . = π i 1 a i 1 i 2 a i 2 i 3 . . . a i T − 1 i T P(I|lambda)=pi_{i_1}a_{i_1i_2}P(i_3,...,i_T|i_2,lambda)=pi_{i_1}a_{i_1i_2}P(i_4,...,i_T|i_3,i_2,lambda)P(i_3|i_2,lambda)=pi_{i_1}a_{i_1i_2}a_{i_2i_3}P(i_4,...,i_T|i_3,i_2,lambda)=...=pi_{i_1}a_{i_1i_2}a_{i_2i_3}...a_{i_{T-1}i_T} P(I∣λ)=πi1ai1i2P(i3,...,iT∣i2,λ)=πi1ai1i2P(i4,...,iT∣i3,i2,λ)P(i3∣i2,λ)=πi1ai1i2ai2i3P(i4,...,iT∣i3,i2,λ)=...=πi1ai1i2ai2i3...aiT−1iT
计算 P ( O ∣ I , λ ) P(O|I,lambda) P(O∣I,λ)：
根据HMM的独立性假设得到如下的式子
P ( O ∣ I , λ ) = P ( o 1 , o 2 , . . . , o T ∣ i 1 , i 2 , . . . , i T , λ ) = b i 1 ( o 1 ) b i 2 ( o 2 ) . . . b i T ( o T ) P(O|I,lambda)=P(o_1,o_2,...,o_T|i_1,i_2,...,i_T,lambda)=b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T) P(O∣I,λ)=P(o1,o2,...,oT∣i1,i2,...,iT,λ)=bi1(o1)bi2(o2)...biT(oT)
最终得到 P ( O ∣ λ ) = ∑ I P ( I ∣ λ ) P ( O ∣ I , λ ) = ∑ i 1 , i 2 , . . . , i T π i 1 b i 1 ( o 1 ) a i 1 i 2 b i 2 ( o 2 ) a i 2 i 3 . . . a i T − 1 i T b i T ( o T ) P(O|lambda)=sumlimits_{I}P(I|lambda)P(O|I,lambda)=sumlimits_{i_1,i_2,...,i_T}pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)a_{i_2i_3}...a_{i_{T-1}i_T}b_{i_T}(o_T) P(O∣λ)=I∑P(I∣λ)P(O∣I,λ)=i1,i2,...,iT∑πi1bi1(o1)ai1i2bi2(o2)ai2i3...aiT−1iTbiT(oT)
考虑以下时间复杂度： π i 1 b i 1 ( o 1 ) a i 1 i 2 b i 2 ( o 2 ) a i 2 i 3 . . . a i T − 1 i T b i T ( o T ) pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)a_{i_2i_3}...a_{i_{T-1}i_T}b_{i_T}(o_T) πi1bi1(o1)ai1i2bi2(o2)ai2i3...aiT−1iTbiT(oT)一共是 2 T 2T 2T个因子，那么就是 2 T − 1 2T-1 2T−1个乘号，而外层求和符号是 T T T层，每个状态 i i i有 N N N种取法（状态），所以取法是 N T N^T NT种，所以时间复杂度是 O ( ( 2 T − 1 ) N T ) O((2T-1)N^T) O((2T−1)NT) 即 O ( T N T ) O(TN^T) O(TNT)，这个时间复杂度是很恐怖的，并不可取，考虑以下的有效方法：前向算法、后向算法。
2、前向算法
前向算法实际上算作是动态规划算法，也就是将大问题分解分众多小问题，通过小问题的解来得到大问题的解。对各个小问题进行求解后，会将结果保存下来，下次要用的时候就不用再去计算而是直接拿来用了，这样能有效避免重复计算问题，基本上都会涉及到递推。具体的可以去leetcode上刷两题感受一下。
前向概率： 给定隐马尔科夫模型 λ lambda λ，定义到时刻 t t t的观测序列为 o 1 , o 2 , . . . , o t o_1,o_2,...,o_t o1,o2,...,ot 且状态为 i t = q i i_t=q_i it=qi的概率为前向概率，记做 a t ( i ) a_t(i) at(i)，表示如下：
α t ( i ) = P ( o 1 , o 2 , . . . , o t , i t = q i ∣ λ ) alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|lambda) αt(i)=P(o1,o2,...,ot,it=qi∣λ)
为什么要给这么个定义呢，因为我们要求的是 P ( O ∣ λ ) = P ( o 1 , o 2 , . . . , o T ∣ λ ) P(O|lambda)=P(o_1,o_2,...,o_T|lambda) P(O∣λ)=P(o1,o2,...,oT∣λ)
α T ( i ) = P ( o 1 , o 2 , . . . , o T , i T = q i ∣ λ ) alpha_T(i)=P(o_1,o_2,...,o_T,i_T=q_i|lambda) αT(i)=P(o1,o2,...,oT,iT=qi∣λ)，得到
α T ( 1 ) + α T ( 2 ) + . . . + α T ( N ) = P ( o 1 , o 2 , . . . , o T , i T = q 1 ∣ λ ) + P ( o 1 , o 2 , . . . , o T , i T = q 2 ∣ λ ) . . . + P ( o 1 , o 2 , . . . , o T , i T = q N ∣ λ ) = P ( o 1 , o 2 , . . . , o T ∣ λ ) alpha_T(1)+alpha_T(2)+...+alpha_T(N)\=P(o_1,o_2,...,o_T,i_T=q_1|lambda)+P(o_1,o_2,...,o_T,i_T=q_2|lambda)...+P(o_1,o_2,...,o_T,i_T=q_N|lambda)\=P(o_1,o_2,...,o_T|lambda) αT(1)+αT(2)+...+αT(N)=P(o1,o2,...,oT,iT=q1∣λ)+P(o1,o2,...,oT,iT=q2∣λ)...+P(o1,o2,...,oT,iT=qN∣λ)=P(o1,o2,...,oT∣λ)
最后一个等号根据全概率公式得来。
所以我们可以先对每个 i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N求出 α 1 ( i ) alpha_1(i) α1(i)，从而递推得到 α T ( i ) alpha_T(i) αT(i)，下面看递推公式是怎样的。即，对于每个 i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N求出了 α t ( i ) alpha_t(i) αt(i)，那么 α t + 1 ( i ) alpha_{t+1}(i) αt+1(i)是怎么得到的。
前面说了根据贝叶斯网络有： P ( A , B , C ) = P ( A ∣ B , C ) P ( B ∣ C ) P ( C ) P(A,B,C)=P(A|B,C)P(B|C)P(C) P(A,B,C)=P(A∣B,C)P(B∣C)P(C)
α t ( j ) a j i = P ( o 1 , o 2 , . . . , o t , i t = q j ∣ λ ) P ( i t + 1 = q i ∣ i t = q j , λ ) = P ( o 1 , o 2 , . . . , o t ∣ i t = q j , λ ) P ( i t + 1 = q i ∣ i t = q j , λ ) P ( i t = q j ∣ λ ) alpha_t(j)a_{ji}=P(o_1,o_2,...,o_t,i_t=q_j|lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)=P(o_1,o_2,...,o_t|i_t=q_j,lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)P(i_t=q_j|lambda) αt(j)aji=P(o1,o2,...,ot,it=qj∣λ)P(it+1=qi∣it=qj,λ)=P(o1,o2,...,ot∣it=qj,λ)P(it+1=qi∣it=qj,λ)P(it=qj∣λ)
由于 P ( o 1 , o 2 , . . . , o t ∣ i t = q j λ ) = P ( o 1 , o 2 , . . . , o t ∣ i t = q j , i t + 1 = q i , λ ) P(o_1,o_2,...,o_t|i_t=q_jlambda)=P(o_1,o_2,...,o_t|i_t=q_j,i_{t+1}=q_i,lambda) P(o1,o2,...,ot∣it=qjλ)=P(o1,o2,...,ot∣it=qj,it+1=qi,λ)这个在前面的直接计算法中已经说了。所以有
α t ( j ) a j i = P ( o 1 , o 2 , . . . , o t ∣ i t = q j , i t + 1 = q i , λ ) P ( i t + 1 = q i ∣ i t = q j , λ ) P ( i t = q j ∣ λ ) = P ( o 1 , o 2 , . . . , o t ， i t = q j ， i t + 1 = q i ∣ λ ) alpha_t(j)a_{ji}=P(o_1,o_2,...,o_t|i_t=q_j,i_{t+1}=q_i,lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)P(i_t=q_j|lambda)=P(o_1,o_2,...,o_t，i_t=q_j，i_{t+1}=q_i|lambda) αt(j)aji=P(o1,o2,...,ot∣it=qj,it+1=qi,λ)P(it+1=qi∣it=qj,λ)P(it=qj∣λ)=P(o1,o2,...,ot，it=qj，it+1=qi∣λ)
表示在时刻 t t t生成的观测序列 o 1 , o 2 , . . . , o t o_1,o_2,...,o_t o1,o2,...,ot且状态为 q j q_j qj同时在 t + 1 t+1 t+1时刻的状态为 q i q_i qi的联合概率。（不写推导，直观上也能理解，在后面会不加解释的给出一些式子，因为直观上是容易理解的）。
从而 ∑ j = 1 N α t ( j ) a j i = ∑ j = 1 N P ( o 1 , o 2 , . . . , o t ， i t = q j ， i t + 1 = q i ∣ λ ) = P ( o 1 , o 2 , . . . , o t , i t + 1 = q i ∣ λ ) sumlimits_{j=1}^{N}alpha_t(j)a_{ji}=sumlimits_{j=1}^{N}P(o_1,o_2,...,o_t，i_t=q_j，i_{t+1}=q_i|lambda)=P(o_1,o_2,...,o_t,i_{t+1}=q_i|lambda) j=1∑Nαt(j)aji=j=1∑NP(o1,o2,...,ot，it=qj，it+1=qi∣λ)=P(o1,o2,...,ot,it+1=qi∣λ)
表示在时刻得到的观测序列为 o 1 , o 2 , . . . , o t o_1,o_2,...,o_t o1,o2,...,ot并且在时刻 t + 1 t+1 t+1得到的状态为 q i q_i qi的联合概率。
b i ( o t + 1 ) = P ( o t + 1 ∣ i t + 1 = q i , λ ) b_i(o_{t+1})=P(o_{t+1}|i_{t+1}=q_i,lambda) bi(ot+1)=P(ot+1∣it+1=qi,λ)
从而得到 ( ∑ j = 1 N α t ( j ) a j i ) b i ( o t + 1 ) = P ( o 1 , o 2 , . . . , o t , i t + 1 = q i ∣ λ ) P ( o t + 1 ∣ i t + 1 = q i , λ ) = P ( o 1 , o 2 , . . . , o t ∣ i t + 1 = q i , λ ) P ( o t + 1 ∣ i t + 1 = q i , λ ) P ( i t + 1 = q i ∣ λ ) (sumlimits_{j=1}^{N}alpha_t(j)a_{ji})b_i(o_{t+1})=P(o_1,o_2,...,o_t,i_{t+1}=q_i|lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)=P(o_1,o_2,...,o_t|i_{t+1}=q_i,lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)P(i_{t+1}=q_i|lambda) (j=1∑Nαt(j)aji)bi(ot+1)=P(o1,o2,...,ot,it+1=qi∣λ)P(ot+1∣it+1=qi,λ)=P(o1,o2,...,ot∣it+1=qi,λ)P(ot+1∣it+1=qi,λ)P(it+1=qi∣λ)
根据隐马尔可夫模型的独立性假设得到 P ( o 1 , o 2 , . . . , o t ∣ i t + 1 = q i , λ ) = P ( o 1 , o 2 , . . . , o t ∣ i t + 1 = q i , o t + 1 λ ) P(o_1,o_2,...,o_t|i_{t+1}=q_i,lambda)=P(o_1,o_2,...,o_t|i_{t+1}=q_i,o_{t+1}lambda) P(o1,o2,...,ot∣it+1=qi,λ)=P(o1,o2,...,ot∣it+1=qi,ot+1λ)，带入到上式同时根据贝叶斯网络得到：
( ∑ j = 1 N α t ( j ) a j i ) b i ( o t + 1 ) = P ( o 1 , o 2 , . . . , o t ∣ i t + 1 = q i , o t + 1 λ ) P ( o t + 1 ∣ i t + 1 = q i , λ ) P ( i t + 1 = q i ∣ λ ) = P ( o 1 , o 2 , . . . , o t , o t + 1 , i t + 1 = q i ) = α t + 1 ( i ) (sumlimits_{j=1}^{N}alpha_t(j)a_{ji})b_i(o_{t+1})=P(o_1,o_2,...,o_t|i_{t+1}=q_i,o_{t+1}lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)P(i_{t+1}=q_i|lambda)=P(o_1,o_2,...,o_t,o_{t+1},i_{t+1}=q_i)=alpha_{t+1}(i) (j=1∑Nαt(j)aji)bi(ot+1)=P(o1,o2,...,ot∣it+1=qi,ot+1λ)P(ot+1∣it+1=qi,λ)P(it+1=qi∣λ)=P(o1,o2,...,ot,ot+1,it+1=qi)=αt+1(i)
到这里基本就知道前向算法怎么得到 P ( O ) P(O) P(O)了，下面写出正式的流程。
前向算法：
输入：隐马尔可夫模型 λ lambda λ，观测序列 O = { o 1 , o 2 , . . . , o T } O={o_1,o_2,...,o_T} O={o1,o2,...,oT}
输出： 观测序列的概率 P ( O ∣ λ ) P(O|lambda) P(O∣λ)
（1）、对于每个 i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N计算时刻 t = 1 t=1 t=1 初值:
α 1 ( i ) = P ( o 1 , i 1 = q i ∣ λ ) = P ( o 1 ∣ i 1 = q i , λ ) P ( i 1 = q i ∣ λ ) = π i b i ( o 1 ) alpha_1(i)=P(o_1,i_1=q_i|lambda)\=P(o_1|i_1=q_i,lambda)P(i_1=q_i|lambda)\=pi_ib_i(o_1) α1(i)=P(o1,i1=qi∣λ)=P(o1∣i1=qi,λ)P(i1=qi∣λ)=πibi(o1)
（2）、递推 对每个 t = 1 , 2 , . . . , T − 1 t=1,2,...,T-1 t=1,2,...,T−1 计算
α t + 1 ( i ) = ( ∑ j = 1 N α t ( j ) a j i ) b i ( o t + 1 ) , i = 1 , 2 , . . . , N alpha_{t+1}(i)=(sumlimits_{j=1}^{N}alpha_t(j)a_{ji})b_i(o_{t+1}),i=1,2,...,N αt+1(i)=(j=1∑Nαt(j)aji)bi(ot+1),i=1,2,...,N
（3）、终止，计算最终结果：
P ( O ∣ λ ) = ∑ i = 1 N α T ( i ) P(O|lambda)=sumlimits_{i=1}^{N}alpha_T(i) P(O∣λ)=i=1∑NαT(i)
再来考虑前向算法的时间复杂度，看第二步就行，最外层对 t t t进行遍历，第二层对 i i i进行遍历，循环体粗略算是 N N N个乘号，所以最终时间复杂度为 T N 2 TN^2 TN2，相比于直接计算的方法时间复杂度降低了太多，那么再来看后向算法。
3、后向算法
后向算法就不写的那么详细了，具体的推导就不写的太详细了。
后向概率： 给定隐马尔可夫模型 λ lambda λ，定义在时刻 t t t 状态为 q i q_i qi的条件下，从 t + 1 t+1 t+1 到 T T T 部分的概率为后向概率，记做 β t ( i ) beta_t(i) βt(i)
β t ( i ) = P ( o t + 1 , . . . , o T ∣ i t = q i , λ ) beta_t(i)=P(o_{t+1},...,o_{T}|i_{t}=q_i,lambda) βt(i)=P(ot+1,...,oT∣it=qi,λ)
那么根据后向概率怎么得到观测序列的概率 P ( O ) P(O) P(O)呢？
π i b i ( o 1 ) β 1 ( i ) = P ( i 1 = q i ∣ λ ) P ( o 1 ∣ i 1 = q i , λ ) P ( o 2 , . . . , o T ∣ i 1 = q i , λ ) pi_i b_i(o_1)beta_1(i)=P(i_1=q_i|lambda)P(o_1|i_1=q_i,lambda)P(o_{2},...,o_{T}|i_{1}=q_i,lambda) πibi(o1)β1(i)=P(i1=qi∣λ)P(o1∣i1=qi,λ)P(o2,...,oT∣i1=qi,λ)
同样也是根据贝叶斯网络那个公式，以及HMM的假设得到：
π i b i ( o 1 ) β 1 ( i ) = P ( i 1 = q i ∣ λ ) P ( o 1 ∣ i 1 = q i , λ ) P ( o 2 , . . . , o T ∣ i 1 = q i , o 1 , λ ) = P ( o 1 , o 2 , . . . , o T , i 1 = q i ∣ λ ) pi_i b_i(o_1)beta_1(i)=P(i_1=q_i|lambda)P(o_1|i_1=q_i,lambda)P(o_{2},...,o_{T}|i_{1}=q_i,o_1,lambda)=P(o_1,o_{2},...,o_{T},i_1=q_i|lambda) πibi(o1)β1(i)=P(i1=qi∣λ)P(o1∣i1=qi,λ)P(o2,...,oT∣i1=qi,o1,λ)=P(o1,o2,...,oT,i1=qi∣λ)
根据全概率公式，那么有 ∑ i = 1 N P ( o 1 , o 2 , . . . , o T , i 1 = q i ∣ λ ) = P ( o 1 , o 2 , . . . , o T ∣ λ ) = P ( O ∣ λ ) sumlimits_{i=1}^{N}P(o_1,o_{2},...,o_{T},i_1=q_i|lambda)=P(o_1,o_{2},...,o_{T}|lambda)=P(O|lambda) i=1∑NP(o1,o2,...,oT,i1=qi∣λ)=P(o1,o2,...,oT∣λ)=P(O∣λ)，这不就得到了么。
首先规定 β T ( i ) = 1 beta_T(i)=1 βT(i)=1，那么主要是通过递推得到 β 1 ( i ) beta_1(i) β1(i)。也就是有 β t + 1 ( i ) beta_{t+1}(i) βt+1(i)怎么推到 β t ( i ) beta_{t}(i) βt(i)。
β t ( i ) = ∑ j = 1 N a i j b j ( o t + 1 ) β t + 1 ( j ) beta_{t}(i)=sumlimits_{j=1}^{N} a_{ij}b_j(o_{t+1})beta_{t+1}(j) βt(i)=j=1∑Naijbj(ot+1)βt+1(j)
这个是怎么来的可以直观理解也可以推导试试，下面给出正式的算法。
后向算法：
输入：隐马尔可夫模型 λ lambda λ，观测序列 O = { o 1 , o 2 , . . . , o T } O={o_1,o_2,...,o_T} O={o1,o2,...,oT}
输出： 观测序列的概率 P ( O ∣ λ ) P(O|lambda) P(O∣λ)
（1）、对于每个 i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N计算时刻 t = 1 t=1 t=1 初值规定:
β T ( i ) = 1 beta_T(i)=1 βT(i)=1
（2）、递推 对每个 t = T − 1 , T − 2 , . . . , 1 t=T-1,T-2,...,1 t=T−1,T−2,...,1 计算
β t ( i ) = ∑ j = 1 N a i j b j ( o t + 1 ) β t + 1 ( j ) beta_{t}(i)=sumlimits_{j=1}^{N} a_{ij}b_j(o_{t+1})beta_{t+1}(j) βt(i)=j=1∑Naijbj(ot+1)βt+1(j)
（3）、终止，计算最终结果：
P ( O ∣ λ ) = ∑ i = 1 N π i b i ( o 1 ) β 1 ( i ) P(O|lambda)=sumlimits_{i=1}^{N}pi_i b_i(o_1)beta_1(i) P(O∣λ)=i=1∑Nπibi(o1)β1(i)
考虑时间复杂度，和前向算法是一样的。如果前向和后向算法放在一起的话，我们会得到下面的一些结论。
一些结论
结论1、 P ( O , i t = q i ∣ λ ) = α t ( i ) β t ( i ) P(O,i_t=q_i|lambda)=alpha_t(i)beta_t(i) P(O,it=qi∣λ)=αt(i)βt(i)
P ( O , i t = q i ∣ λ ) = P ( o 1 , o 2 , . . . , o t , o t + 1 , . . . , o T ∣ i t = q i , λ ) P ( i t = q i ∣ λ ) P(O,i_t=q_i|lambda)=P(o_1,o_2,...,o_t,o_{t+1},...,o_T|i_t=q_i,lambda)P(i_t=q_i|lambda) P(O,it=qi∣λ)=P(o1,o2,...,ot,ot+1,...,oT∣it=qi,λ)P(it=qi∣λ)
由于给定 i t = q i i_t=q_i it=qi，那么序列 o 1 , o 2 , . . . , o t o_1,o_2,...,o_t o1,o2,...,ot 和序列 o t + 1 , . . . , o T o_{t+1},...,o_T ot+1,...,oT 是条件独立的，所以 P ( o 1 , o 2 , . . . , o t , o t + 1 , . . . , o T ∣ i t = q i , λ ) = P ( o 1 , o 2 , . . . , o t ∣ i t = q i , λ ) P ( o t + 1 , . . . , o T ∣ i t = q i , λ ) P(o_1,o_2,...,o_t,o_{t+1},...,o_T|i_t=q_i,lambda)=P(o_1,o_2,...,o_t|i_t=q_i,lambda)P(o_{t+1},...,o_T|i_t=q_i,lambda) P(o1,o2,...,ot,ot+1,...,oT∣it=qi,λ)=P(o1,o2,...,ot∣it=qi,λ)P(ot+1,...,oT∣it=qi,λ)，带入上式子得到
P ( O , i t = q i ∣ λ ) = P ( o 1 , o 2 , . . . , o t ∣ i t = q i , λ ) P ( o t + 1 , . . . , o T ∣ i t = q i , λ ) P ( i t = q i ∣ λ ) = P ( o 1 , o 2 , . . . , o t , i t = q i ∣ λ ) P ( o t + 1 , . . . , o T ∣ i t = q i , λ ) = α t ( i ) β t ( i ) P(O,i_t=q_i|lambda)=P(o_1,o_2,...,o_t|i_t=q_i,lambda)P(o_{t+1},...,o_T|i_t=q_i,lambda)P(i_t=q_i|lambda)\=P(o_1,o_2,...,o_t,i_t=q_i|lambda)P(o_{t+1},...,o_T|i_t=q_i,lambda)\=alpha_t(i)beta_t(i) P(O,it=qi∣λ)=P(o1,o2,...,ot∣it=qi,λ)P(ot+1,...,oT∣it=qi,λ)P(it=qi∣λ)=P(o1,o2,...,ot,it=qi∣λ)P(ot+1,...,oT∣it=qi,λ)=αt(i)βt(i)
得到的结论是 P ( O , i t = q i ∣ λ ) = α t ( i ) β t ( i ) P(O,i_t=q_i|lambda)=alpha_t(i)beta_t(i) P(O,it=qi∣λ)=αt(i)βt(i)，根据这个结论可以得到下面两个结论
结论2、 γ t ( i ) = α t ( i ) β t ( i ) ∑ i = 1 N α t ( i ) β t ( i ) gamma_t(i)=frac{alpha_t(i)beta_t(i)}{sumlimits_{i=1}^{N}alpha_t(i)beta_t(i)} γt(i)=i=1∑Nαt(i)βt(i)αt(i)βt(i)
记 γ t ( i ) = P ( i t = q i ∣ O , λ ) gamma_t(i)=P(i_t=q_i|O,lambda) γt(i)=P(it=qi∣O,λ)，即已知模型 λ lambda λ，给定观测序列条件下，在 t t t 时刻状态为 q i q_i qi 的概率。
γ t ( i ) = P ( i t = q i ∣ O , λ ) = P ( i t = q i , O ∣ λ ) P ( O ∣ λ ) = P ( i t = q i , O ∣ λ ) ∑ i = 1 N P ( i t = q i , O ∣ λ ) = α t ( i ) β t ( i ) ∑ i = 1 N α t ( i ) β t ( i ) gamma_t(i)=P(i_t=q_i|O,lambda)\=frac{P(i_t=q_i,O|lambda)}{P(O|lambda)}\=frac{P(i_t=q_i,O|lambda)}{sumlimits_{i=1}^{N}P(i_t=q_i,O|lambda)}\=frac{alpha_t(i)beta_t(i)}{sumlimits_{i=1}^{N}alpha_t(i)beta_t(i)} γt(i)=P(it=qi∣O,λ)=P(O∣λ)P(it=qi,O∣λ)=i=1∑NP(it=qi,O∣λ)P(it=qi,O∣λ)=i=1∑Nαt(i)βt(i)αt(i)βt(i)
结论3、
记 ξ t ( i , j ) = P ( i t = q i , i t + 1 = q j ∣ O , λ ) xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,lambda) ξt(i,j)=P(it=qi,it+1=qj∣O,λ)，即已知模型 λ lambda λ和观测 O O O，在时刻 t t t 处于 q i q_i qi状态，时刻 t + 1 t+1 t+1处于 q j q_j qj 状态的概率。
根据后向算法的递推公式可以得到
a i j b j ( o t + 1 ) β t + 1 ( i ) = P ( o t + 1 , o t + 2 , . . . , o T , i t + 1 = q j ∣ i t = q i , λ ) a_{ij}b_j(o_{t+1})beta_{t+1}(i)=P(o_{t+1},o_{t+2},...,o_{T},i_{t+1}=q_j|i_t=q_i,lambda) aijbj(ot+1)βt+1(i)=P(ot+1,ot+2,...,oT,it+1=qj∣it=qi,λ)
那么
α t ( i ) a i j b j ( o t + 1 ) β t + 1 ( i ) = P ( o 1 , o 2 , . . . , o t , i t = q i ∣ λ ) P ( o t + 1 , o t + 2 , . . . , o T , i t + 1 = q j ∣ i t = q i , λ ) = P ( o 1 , o 2 , . . . , o t ∣ i t = q i , λ ) P ( i t = q i ∣ λ ) P ( o t + 1 , o t + 2 , . . . , o T , i t + 1 = q j ∣ i t = q i , λ ) = P ( o 1 , . . . , o t , o t + 1 , o t + 2 , . . . , o T , i t + 1 = q j ∣ i t = q i , λ ) P ( i t = q i ∣ λ ) = P ( o 1 , . . . , o t , o t + 1 , o t + 2 , . . . , o T , i t = q i , i t + 1 = q j ∣ λ ) = P ( O , i t = q i , i t + 1 = q j ∣ λ ) alpha_t(i)a_{ij}b_j(o_{t+1})beta_{t+1}(i)\=P(o_1,o_2,...,o_t,i_t=q_i|lambda)P(o_{t+1},o_{t+2},...,o_{T},i_{t+1}=q_j|i_t=q_i,lambda)\=P(o_1,o_2,...,o_t|i_t=q_i,lambda)P(i_t=q_i|lambda)P(o_{t+1},o_{t+2},...,o_{T},i_{t+1}=q_j|i_t=q_i,lambda)\=P(o_1,...,o_t,o_{t+1},o_{t+2},...,o_{T},i_{t+1}=q_j|i_t=q_i,lambda)P(i_t=q_i|lambda)\=P(o_1,...,o_t,o_{t+1},o_{t+2},...,o_{T},i_t=q_i,i_{t+1}=q_j|lambda)\=P(O,i_t=q_i,i_{t+1}=q_j|lambda) αt(i)aijbj(ot+1)βt+1(i)=P(o1,o2,...,ot,it=qi∣λ)P(ot+1,ot+2,...,oT,it+1=qj∣it=qi,λ)=P(o1,o2,...,ot∣it=qi,λ)P(it=qi∣λ)P(ot+1,ot+2,...,oT,it+1=qj∣it=qi,λ)=P(o1,...,ot,ot+1,ot+2,...,oT,it+1=qj∣it=qi,λ)P(it=qi∣λ)=P(o1,...,ot,ot+1,ot+2,...,oT,it=qi,it+1=qj∣λ)=P(O,it=qi,it+1=qj∣λ)
注意：第二个等号到第三个等号的成立的原因是在 i t = q i i_t=q_i it=qi的条件下， o 1 , o 2 , . . . , o t o_1,o_2,...,o_t o1,o2,...,ot和 o t + 1 , o t + 2 , . . . , o T , i t + 1 = q j o_{t+1},o_{t+2},...,o_{T},i_{t+1}=q_j ot+1,ot+2,...,oT,it+1=qj 是条件独立的。
ξ t ( i , j ) = P ( i t = q i , i t + 1 = q j ∣ O , λ ) = P ( i t = q i , i t + 1 = q j , O ∣ λ ) P ( O ∣ λ ) = P ( i t = q i , i t + 1 = q j , O ∣ λ ) ∑ i = 1 N ∑ j = 1 N P ( i t = q i , i t + 1 = q j , O ∣ λ ) = α t ( i ) a i j b j ( o t + 1 ) β t + 1 ( i ) ∑ i = 1 N ∑ j = 1 N α t ( i ) a i j b j ( o t + 1 ) β t + 1 ( i ) xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,lambda)\=frac{P(i_t=q_i,i_{t+1}=q_j,O|lambda)}{P(O|lambda)}\=frac{P(i_t=q_i,i_{t+1}=q_j,O|lambda)}{sumlimits_{i=1}^{N}sumlimits_{j=1}^{N}P(i_t=q_i,i_{t+1}=q_j,O|lambda)}\=frac{alpha_t(i)a_{ij}b_j(o_{t+1})beta_{t+1}(i)}{sumlimits_{i=1}^{N}sumlimits_{j=1}^{N}alpha_t(i)a_{ij}b_j(o_{t+1})beta_{t+1}(i)} ξt(i,j)=P(it=qi,it+1=qj∣O,λ)=P(O∣λ)P(it=qi,it+1=qj,O∣λ)=i=1∑Nj=1∑NP(it=qi,it+1=qj,O∣λ)P(it=qi,it+1=qj,O∣λ)=i=1∑Nj=1∑Nαt(i)aijbj(ot+1)βt+1(i)αt(i)aijbj(ot+1)βt+1(i)
本文发布于:2024-01-28 01:44:55，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/17063775013923.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
