锐客网

  1. 首页 > it技术 > >

隐马尔可夫模型（HMM）的原理以及三种主要问题的解决

隐马尔可夫模型介绍 【隐马尔可夫模型（HMM）的原理以及三种主要问题的解决】隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而形成观测序列的过程。
设 Q Q Q为所有可能的状态的集合， V V V是所有可能的观测集合:
Q = { q 1 , q 2 , ? ? , q N } , ???? V = { v 1 , v 2 , ? ? , v M } Q=\{q_1,q_2,\cdots,q_N\},\,\,\,\,V=\{v_1,v_2,\cdots,v_M\} Q={q1?,q2?,?,qN?},V={v1?,v2?,?,vM?}
其中， N N N是可能的状态数， M M M是可能的观测数。
I I I是长度为 T T T的状态序列， O O O是对应的观测序列：
I = ( i 1 , i 2 , ? ? , i T ) , ???? O = ( o 1 , o 2 , ? ? , o T ) I=(i_1,i_2,\cdots,i_T),\,\,\,\,O=(o_1,o_2,\cdots,o_T) I=(i1?,i2?,?,iT?),O=(o1?,o2?,?,oT?)
A A A为状态转移矩阵：
A = [ a i j ] N × N A=[a_{ij}]_{N\times N} A=[aij?]N×N?
其中，
a i j = P ( i t + 1 = q j ∣ i t = q i ) , i = 1 , 2 , ? ? , N ; j = 1 , 2 , ? ? , N a_{ij}=P(i_{t+1}=q_j|i_t=q_i),i=1,2,\cdots,N; j=1,2,\cdots,N aij?=P(it+1?=qj?∣it?=qi?),i=1,2,?,N; j=1,2,?,N
是在时刻 t t t处于状态 q i q_i qi?的条件下在时刻 t + 1 t+1 t+1转移到状态 q j q_j qj?的概率。
B B B是观测概率矩阵：
B = [ b j ( k ) ] N × M B=[b_j(k)]_{N\times M} B=[bj?(k)]N×M?
其中，
b j ( k ) = P ( o t = v k ∣ i t = q j ) , k = 1 , 2. ? ? , M ; j = 1 , 2 , ? ? , N b_j(k)=P(o_t=v_k|i_t=q_j),k=1,2.\cdots,M; j=1,2,\cdots,N bj?(k)=P(ot?=vk?∣it?=qj?),k=1,2.?,M; j=1,2,?,N
是在时刻 t t t处于状态 q j q_j qj?的条件下生成观测 v k v_k vk?的概率。
π \pi π是初始状态概率向量：
π = ( π i ) \pi=(\pi_i) π=(πi?)
其中，
π i = P ( i 1 = q i ) , i = 1 , 2 , ? ? , N \pi_i=P(i_1=q_i),i=1,2,\cdots,N πi?=P(i1?=qi?),i=1,2,?,N
是时刻 t = 1 t=1 t=1处于状态 q i q_i qi?的概率。
则，隐马尔可夫模型可以表述为：
λ = ( A , B , π ) \lambda=(A,B,\pi) λ=(A,B,π)
隐马尔可夫的三个基本问题
1、概率计算问题
给定模型的参数，求某一个观测序列出现的概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)
2、概率计算问题
给出某一个观测序列，估计该模型的参数，采用极大似然估计的方法估计参数
3、预测问题
给定模型和观测序列，求最有可能对应的状态序列
概率计算问题 采用前向算法：
给定隐马尔可夫模型 λ \lambda λ，定义到时刻 t t t部分观测序列为 o 1 , o 2 , ? ? , o t o_1,o_2,\cdots,o_t o1?,o2?,?,ot?且状态为 q i q_i qi?的概率为前向概率，记作
α t ( i ) = P ( o 1 , o 2 , ? ? , o t , i t = q i ∣ λ ) \alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i|\lambda) αt?(i)=P(o1?,o2?,?,ot?,it?=qi?∣λ)
则可以递归地求得前向概率 α t ( i ) \alpha_t(i) αt?(i)及观测序列概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)
算法：
1、设定初值
α 1 = π i b i ( o 1 ) , i = 1 , 2 , ? ? , N \alpha_1=\pi_ib_i(o_1), i=1,2,\cdots,N α1?=πi?bi?(o1?),i=1,2,?,N
2、递推 对 t = 1 , 2 , ? ? , T ? 1 , t=1,2,\cdots,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)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1}),i=1,2,\cdots,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)=\sum_{i=1}^N\alpha_T(i) P(O∣λ)=i=1∑N?αT?(i)
学习问题 引入隐变量：状态序列 I = ( 1 1 , i 2 , ? ? , i t ) I=(1_1,i_2,\cdots,i_t) I=(11?,i2?,?,it?)
采用EM算法
首先，完全信息的对数似然函数为：
log ? P ( O , I ∣ λ ) \log P(O,I|\lambda) logP(O,I∣λ)
E步：
Q ( λ , λ ^ ) = ∑ I log ? P ( O , I ∣ λ ) P ( I ∣ O , λ ^ ) Q(\lambda,\hat{\lambda})=\sum_I\log P(O,I|\lambda)P(I|O,\hat{\lambda}) Q(λ,λ^)=I∑?logP(O,I∣λ)P(I∣O,λ^)
由于
P ( I ∣ O , λ ^ ) = P ( O , I ∣ λ ^ ) P ( O ∣ λ ^ ) P(I|O,\hat{\lambda})=\frac{P(O,I|\hat{\lambda})}{P(O|\hat{\lambda})} P(I∣O,λ^)=P(O∣λ^)P(O,I∣λ^)?
而 P ( O ∣ λ ^ ) P(O|\hat{\lambda}) P(O∣λ^)对与需要优化的参数 λ \lambda λ来说是常数，因此可以令：
Q ( λ , λ ^ ) = ∑ I log ? P ( O , I ∣ λ ) P ( O , I ∣ λ ^ ) Q(\lambda, \hat{\lambda})=\sum_I\log P(O,I|\lambda)P(O,I|\hat{\lambda}) Q(λ,λ^)=I∑?logP(O,I∣λ)P(O,I∣λ^)
其中，
P ( O , I ∣ λ ) = π i 1 b i 1 ( o 1 ) a i 1 i 2 b i 2 ( o 2 ) ? a i T ? 1 i T b i T ( o T ) P(O,I|\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}i_T}b_{i_T}(o_T) P(O,I∣λ)=πi1??bi1??(o1?)ai1?i2??bi2??(o2?)?aiT?1?iT??biT??(oT?)
带入之后，可以得到：
Q ( λ , λ ^ ) = ∑ I log ? π i 1 P ( O , I ∣ λ ^ ) + ∑ I ( ∑ t = 1 T ? 1 log ? a i t i t + 1 ) P ( O , I ∣ λ ^ ) + ∑ I ( ∑ t = 1 T log ? b i t ( o t ) ) P ( O , I ∣ λ ^ ) Q(\lambda,\hat{\lambda})=\sum_I\log\pi_{i_1}P(O,I|\hat{\lambda})+\sum_I(\sum_{t=1}^{T-1}\log a_{i_ti_{t+1}})P(O,I|\hat{\lambda})+\sum_I(\sum_{t=1}^T\log b_{i_t}(o_t))P(O,I|\hat{\lambda}) Q(λ,λ^)=I∑?logπi1??P(O,I∣λ^)+I∑?(t=1∑T?1?logait?it+1??)P(O,I∣λ^)+I∑?(t=1∑T?logbit??(ot?))P(O,I∣λ^)
注意，式中所有的求和都是对所有数据的序列总长度 T T T进行的，可以对每一项分别求最优
第一项：
∑ I log ? π i 1 P ( O , I ∣ λ ^ ) = ∑ i = 1 N log ? π i P ( O , i 1 = i ∣ λ ^ ) \sum_I\log\pi_{i_1}P(O,I|\hat{\lambda})=\sum_{i=1}^N\log\pi_iP(O,i_1=i|\hat{\lambda}) I∑?logπi1??P(O,I∣λ^)=i=1∑N?logπi?P(O,i1?=i∣λ^)
并且，要优化的量需要满足约束条件 ∑ i = 1 N π i = 1 \sum_{i=1}^N\pi_i=1 ∑i=1N?πi?=1，因此，采用拉格朗日乘子法，最终求得：
π i = P ( O , i 1 = i ∣ λ ^ ) P ( O ∣ λ ^ ) \pi_i=\frac{P(O,i_1=i|\hat{\lambda})}{P(O|\hat{\lambda})} πi?=P(O∣λ^)P(O,i1?=i∣λ^)?
同理可以求得其他两项的参数估计为
a i j = ∑ t = 1 T ? 1 P ( O , i t = i , i t + 1 = j ∣ λ ^ ) ∑ t = 1 T ? 1 P ( O , i t = i ∣ λ ^ ) a_{ij}=\frac{\sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1}=j|\hat{\lambda})}{\sum_{t=1}^{T-1}P(O,i_t=i|\hat{\lambda})} aij?=∑t=1T?1?P(O,it?=i∣λ^)∑t=1T?1?P(O,it?=i,it+1?=j∣λ^)?
b j ( k ) = ∑ t = 1 T P ( O , i t = j ∣ λ ^ ) I ( o t = v k ) ∑ t = 1 T P ( O , i t = j ∣ λ ^ ) b_j(k)=\frac{\sum_{t=1}^TP(O,i_t=j|\hat{\lambda})I(o_t=v_k)}{\sum_{t=1}^TP(O,i_t=j|\hat{\lambda})} bj?(k)=∑t=1T?P(O,it?=j∣λ^)∑t=1T?P(O,it?=j∣λ^)I(ot?=vk?)?

    推荐阅读


    上一篇：ModuleNotFoundError: No module named 'flask.ext'

    下一篇：eclipse换工作空间后配置