隐马尔可夫模型(hidden Markov model,HMM)是可用于标注问题的统计学模型,描述由隐藏的马尔可夫链生成观测序列的过程,属于生成模型。
10.1 隐马尔可夫模型的基本概念
10.1.1 隐马尔可夫模型的定义
定义10.1(隐马尔可夫模型)隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列,称为状态序列;每个状态生成一个观测,而由此产生的观测的随机序列,称为观测序列。序列的每个位置可以看作是一个时刻。
隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。隐马尔可夫模型的形式定义如下:
设QQQ是所有可能的状态的集合,VVV是所有的可能的观测的集合:
Q={q1,q2,⋯,qN},V={v1,v2,⋯,vM}Q=\lbrace q_1,q_2,\cdots,q_N\rbrace,\ V=\lbrace v_1,v_2,\cdots,v_M \rbraceQ={q1,q2,⋯,qN},V={v1,v2,⋯,vM}其中,MMM表示可能的状态数,NNN表示可能的观测数。
III是长度为TTT的状态序列,OOO是对应的观测序列:
I=(i1,i2,⋯,iT),O=(o1,o2,⋯,oT)I=(i_1,i_2,\cdots,i_T),\ O=(o_1,o_2,\cdots,o_T) I=(i1,i2,⋯,iT),O=(o1,o2,⋯,oT)
AAA状态转移概率矩阵:
A=[aij]M×NA=[a_{ij}]_{M\times N}A=[aij]M×N其中,aij=P(it+1=qj∣it=qi),i,j=1,2,⋯,Na_{ij}=P(i_{t+1}=q_j|i_t=q_i),i,j=1,2,\cdots,Naij=P(it+1=qj∣it=qi),i,j=1,2,⋯,N其含义为从ttt时刻状态为qiq_iqi转移到t+1t+1t+1时刻状态为qi+1的概率。q_{i+1}的概率。qi+1的概率。
BBB观测概率矩阵:B=[bj(k)]N×MB=[b_j(k)]_{N\times M}B=[bj(k)]N×M其中,bj(k)=P(ot=vk∣it=qj),k=1,2,⋯,M;j=1,2,⋯,Nb_j(k)=P(o_t=v_k|i_t=q_j),k=1,2,\cdots,M;\ j=1,2,\cdots,Nbj(k)=P(ot=vk∣it=qj),k=1,2,⋯,M;j=1,2,⋯,N表示在ttt时刻处于状态qjq_jqj的条件下生成观测vkv_kvk的概率。
π\piπ是初始状态概率向量:π=(πi)\pi=(\pi_i)π=(πi)其中,π=P(i1=qi),i=1,2,⋯,N\pi=P(i_1=q_i),i=1,2,\cdots,Nπ=P(i1=qi),i=1,2,⋯,N表示初始时刻处于状态qiq_iqi的概率。
隐马尔可夫模型由初始状态概率向量π\piπ、状态转移概率矩阵AAA和观测概率矩阵BBB决定,其中π\piπ和AAA决定状态序列,BBB决定观测序列。因此,隐马尔可夫模型λ\lambdaλ可以用三元符号表示,即λ=(A,B,π)\lambda=(A,B,\pi)λ=(A,B,π)A、B、πA、B、\piA、B、π称为隐马尔可夫模型的三要素。
状态转移概率模型AAA与状态初始概率向量π\piπ确定了隐藏的马尔可夫链,生成不可观测的状态序列。观测概率矩阵BBB确定了如何从状态生成观测,与状态序列综合确定了如何产生观测序列。
隐马尔可夫模型做了以下两个基本假设:
(1)齐次马尔可夫性假设,假设隐藏的马尔可夫链在任意时刻ttt的状态只依赖于其前一时刻的状态,与其他时刻的状态及观测无关:P(it∣it−1,ot−1,⋯,i1,o1)=P(it∣it−1),t=1,2,⋯,TP(i_t|i_{t-1},o_{t-1},\cdots,i_1,o_1)=P(i_t|i_{t-1}),t=1,2,\cdots,TP(it∣it−1,ot−1,⋯,i1,o1)=P(it∣it−1),t=1,2,⋯,T
(2)观测独立性假设,即任意时刻的观测只依赖于该时刻的马尔可夫链的状态,与其他状态及观测无关:P(ot∣iT,oT,iT−1,oT−1,⋯,i1,o1)=P(ot∣it)P(o_t|i_T,o_T,i_{T-1},o_{T-1},\cdots,i_1,o_1)=P(o_t|i_t)P(ot∣iT,oT,iT−1,oT−1,⋯,i1,o1)=P(ot∣it)
10.1.2 观测序列的生成过程:
根据隐马尔可夫模型的定义,可以将一个长度为TTT的观测序列O=(o1,o2,⋯,oT)O=(o_1,o_2,\cdots,o_T)O=(o1,o2,⋯,oT)的生成过程描述如下:
算法10.1观测序列的生成:
输入:隐马尔可夫模型λ=(A,B,π)\lambda=(A,B,\pi)λ=(A,B,π),观测序列长度T;
输出:观测序列O=(o1,o2,⋯,oT)O=(o_1,o_2,\cdots,o_T)O=(o1,o2,⋯,oT)。
(1)按照初始状态分布π\piπ产生状态i1i_1i1;
(2)令t=1t=1t=1;
(3)按照状态iti_tit的观测概率分布bit(k)b_{i_t}(k)bit(k)生成o(t)o(t)o(t);
(4)按照状态iti_tit的状态转移概率分布aitit+1{a_{i_ti_t+1}}aitit+1产生状态it+1i_{t+1}it+1;
(5)令t=t+1t=t+1t=t+1,如果t<Tt<Tt<T,转步(3);否则,终止。
10.2 概率计算算法
10.2.1 直接计算法
给定模型λ=(A,B,π)\lambda=(A,B,\pi)λ=(A,B,π)和观测序列O=(o1,o2,⋯,oT)O=(o_1,o_2,\cdots,o_T)O=(o1,o2,⋯,oT),计算观测序列OOO出现的概率P(O∣λ)P(O|\lambda)P(O∣λ)。直接计算的思路是:首先求状态序列I=i1,i2,⋯,iTI={i_1,i_2,\cdots,i_T}I=i1,i2,⋯,iT出现的概率P(I∣λ)=πi1ai1i2ai2i3⋯aiT−1iTP(I| \lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}\cdots a_{i_T-1i_T}P(I∣λ)=πi1ai1i2ai2i3⋯aiT−1iT 对给定的状态序列III,观测序列O=(o1,o2,⋯,oT)O=(o_1,o_2,\cdots,o_T)O=(o1,o2,⋯,oT)的概率是:P(O∣I)=bi1(o1)bi2(o2)⋯biT(oT)P(O|I)=b_{i_1}(o_1)b_{i_2}(o_2)\cdots b_{i_T}(o_T)P(O∣I)=bi1(o1)bi2(o2)⋯biT(oT) OOO和III同时出现的概率为P(O,I∣λ)=P(O∣I,λ)P(I∣λ)P(O,I|\lambda)=P(O|I,\lambda)P(I|\lambda)P(O,I∣λ)=P(O∣I,λ)P(I∣λ)=πi1bi1(o1)ai1i2bi2(o2)⋯aiT−1iTbiT(o(T))=\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))=πi1bi1(o1)ai1i2bi2(o2)⋯aiT−1iTbiT(o(T))因为要将所有的长度为TTT的状态序列列举出来,状态共NNN种,所以计算量是O(TNT)O(TN^T)O(TNT)阶,这种算法不可行。
10.2.2 前向算法
定义10.2(前向概率)给定隐马尔可夫模型λ\lambdaλ,定义到ttt时刻部分观测序列为o1,o2,⋯,oto_1,o_2,\cdots,o_to1,o2,⋯,ot且状态为qiq_iqi的概率为前向概率,记作:αt(i)=P(o1,o2,…,ot,it=qi∣λ)\alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_i|\lambda)αt(i)=P(o1,o2,…,ot,it=qi∣λ)
算法10.2(观测序列概率的前向算法)
这个算法虽然从含义理解上可以认同,但是博主没能从数学的角度上找到一种说服自己的合理推导过程,望有想法者留下评论。
输入:隐马尔可夫模型λ\lambdaλ,观测序列OOO;
输出:观测序列概率P(O∣λ)P(O|\lambda)P(O∣λ)。
(1)初值α1(i)=P(o1,i1=qi∣λ)=πibi(o1),i=1,2,⋯,N\alpha_1(i)=P(o_1,i_1=q_i|\lambda)=\pi_ib_i(o_1),i=1,2,\cdots,Nα1(i)=P(o1,i1=qi∣λ)=πibi(o1),i=1,2,⋯,N
(2)递推αt+1(i)=(∑j=1Nαt(j)aji)bi(ot+1),i=1,2,3,⋯,N\alpha_{t+1}(i)=(\sum_{j=1}^N\alpha_t(j)a_{ji})b_i(o_{t+1}),i=1,2,3,\cdots,Nαt+1(i)=(j=1∑Nαt(j)aji)bi(ot+1),i=1,2,3,⋯,N
(3)终止P(O∣λ)=∑i=1NαT(i)P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)P(O∣λ)=i=1∑NαT(i)
前向算法是基于状态序列的路径结构递推计算P(O∣λ)P(O|\lambda)P(O∣λ)的算法。这种算法所需的计算量大大降低,每一次计算直接引用前一时刻的计算结果,避免了重复计算。利用前向概率计算P(O∣λ)P(O|\lambda)P(O∣λ)的计算量是O(N2T)O(N^2T)O(N2T),相比直接算法计算量已经大大降低。
从(2)到(3)的推导过程:
αt+1(i)=P(o1,o2,⋯,ot+1,it+1=qi∣λ)\alpha_{t+1}(i)=P(o_1,o_2,\cdots,o_{t+1},i_{t+1}=q_i|\lambda)αt+1(i)=P(o1,o2,⋯,ot+1,it+1=qi∣λ)=∑j=1NP(o1,o2,⋯,ot+1,it=qj,it+1=qi∣λ)=\sum_{j=1}^NP(o_1,o_2,\cdots,o_{t+1},i_t=q_j,i_{t+1}=q_i|\lambda)=j=1∑NP(o1,o2,⋯,ot+1,it=qj,it+1=qi∣λ)=∑j=1NP(o1,o2,⋯,ot,it=qj)P(ot+1,it+1=qi∣o1,o2,⋯,ot,it=qj)=\sum_{j=1}^NP(o_1,o_2,\cdots,o_t,i_t=q_j)P(o_{t+1},i_{t+1}=q_i|o_1,o_2,\cdots,o_t,i_t=q_j)=j=1∑NP(o1,o2,⋯,ot,it=qj)P(ot+1,it+1=qi∣o1,o2,⋯,ot,it=qj)=∑j=1NP(o1,o2,⋯,ot,it=qj)P(ot+1∣o1,o2,⋯,ot,it=qj,it+1=qi)P(it+1=qi∣o1,o2,⋯,ot,it=qj)=\sum_{j=1}^NP(o_1,o_2,\cdots,o_t,i_t=q_j)P(o_{t+1}|o_1,o_2,\cdots,o_t,i_t=q_j,i_{t+1}=q_i)P(i_{t+1}=q_i|o_1,o_2,\cdots,o_t,i_t=q_j)=j=1∑NP(o1,o2,⋯,ot,it=qj)P(ot+1∣o1,o2,⋯,ot,it=qj,it+1=qi)P(it+1=qi∣o1,o2,⋯,ot,it=qj)=∑j=1NP(o1,o2,⋯,ot,it=qj)P(ot+1∣it+1=qi)P(it+1=qi∣it=qj)=\sum_{j=1}^NP(o_1,o_2,\cdots,o_t,i_t=q_j)P(o_{t+1}|i_{t+1}=q_i)P(i_{t+1}=q_i|i_t=q_j)=j=1∑NP(o1,o2,⋯,ot,it=qj)P(ot+1∣it+1=qi)P(it+1=qi∣it=qj)=(∑j=1Najiαt(j))bi(ot+1)=(\sum_{j=1}^Na_{ji}\alpha_t(j))b_i(o_{t+1})=(j=1∑Najiαt(j))bi(ot+1)
10.2.3 后向算法
定义10.3(后向概率)给定隐马尔可夫模型λ\lambdaλ,定义在时刻ttt状态为qiq_iqi的条件下,从t+1t+1t+1到TTT的部分观测序列为ot+1,ot+2,⋯,oTo_{t+1},o_{t+2},\cdots,o_Tot+1,ot+2,⋯,oT的概率为后向概率,记作βt(i)=P(ot+1,ot+2,⋯,oT∣it=qi,λ)\beta_t(i)=P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_i,\lambda)βt(i)=P(ot+1,ot+2,⋯,oT∣it=qi,λ)
算法10.3(观测序列概率的后向算法)
输入:隐马尔可夫模型λ\lambdaλ,观测序列OOO;
输出:输出:观测序列概率P(O∣λ)P(O|\lambda)P(O∣λ)。
(1)βT(i)=1,i=1,2,⋯,N\beta_T(i)=1,i=1,2,\cdots,NβT(i)=1,i=1,2,⋯,N
(2)对t=T−1,T−2,⋯,1t=T-1,T-2,\cdots,1t=T−1,T−2,⋯,1βt(i)=∑j=1Naijbj(ot+1)βt+1(j),i=1,2,⋯,N\beta_t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,\cdots,Nβt(i)=j=1∑Naijbj(ot+1)βt+1(j),i=1,2,⋯,N
(3)P(O∣λ)=∑i=1Nπibi(o1)β1(i)P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)P(O∣λ)=i=1∑Nπibi(o1)β1(i)
从(2)到(3)的推导过程:???这部分推导存疑
βt(i)=P(ot+1,ot+2,⋯,oT∣it=qi)\beta_{t}(i)=P(o_{t+1},o_{t+2},\cdots,o_T|i_{t}=q_i)βt(i)=P(ot+1,ot+2,⋯,oT∣it=qi)=∑j=1NP(ot+1,ot+2,⋯,oT,it+1=qj∣it=qi)=\sum_{j=1}^NP(o_{t+1},o_{t+2},\cdots,o_T,i_{t+1}=q_j|i_{t}=q_i)=j=1∑NP(ot+1,ot+2,⋯,oT,it+1=qj∣it=qi)=∑j=1NP(ot+2,⋯,oT∣it+1=qj,it=qi,ot+1)P(ot+1,it+1=qj,it=qi)=\sum_{j=1}^NP(o_{t+2},\cdots,o_T|i_{t+1}=q_j,i_t=q_i,o_{t+1})P(o_{t+1},i_{t+1}=q_j,i_t=q_i)=j=1∑NP(ot+2,⋯,oT∣it+1=qj,it=qi,ot+1)P(ot+1,it+1=qj,it=qi)
利用前向概率和后向概率的定义可以将观测序列概率P(O∣λ)=∑i=1N∑j=1Nαt(i)aijbj(ot+1)βt+1(j),t=1,2,⋯,T−1P(O|\lambda)=\sum_{i=1}^N\sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\ \ t=1,2,\cdots,T-1P(O∣λ)=i=1∑Nj=1∑Nαt(i)aijbj(ot+1)βt+1(j),t=1,2,⋯,T−1
10.2.4 一些概率与期望值的计算
利用前向概率和后向概率,可以得到关于单个状态和两个状态概率的计算公式。
1. 给定模型λ\lambdaλ和观测OOO,在时刻ttt 处于状态qiq_iqi的概率,记作γt(i)=P(it=qi∣λ,O)=P(it=qi,O∣λ)P(O∣λ)\gamma_t(i)=P(i_t=q_i|\lambda,O)=\frac{P(i_t=q_i,O|\lambda)}{P(O|\lambda)}γt(i)=P(it=qi∣λ,O)=P(O∣λ)P(it=qi,O∣λ)通过前向概率αt(i)\alpha_t(i)αt(i)和后向概率βt(i)\beta_t(i)βt(i)的定义:αt(i)βt(i)=P(it=qt,O∣λ)\alpha_t(i)\beta_t(i)=P(i_t=q_t,O|\lambda)αt(i)βt(i)=P(it=qt,O∣λ)于是,γt(i)=αt(i)βt(i)P(O∣λ)=αt(i)βt(i)∑j=1Nαt(j)βt(j)\gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)}γt(i)=P(O∣λ)αt(i)βt(i)=∑j=1Nαt(j)βt(j)αt(i)βt(i)
2.给定模型 λ\lambdaλ和观测OOO,在时刻ttt处于状态qiq_iqi且在时刻t+1t+1t+1处于状态qjq_jqj的概率,记作ξt(i,j)=P(it=qi,it+1=qj∣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,λ)通过前向后向概率计算:ξt(i,j)=P(it=qi,it+1=qj,O∣λ)P(O∣λ)=P(it=qi,it+1=qj,O∣λ)∑i=1N∑j=1NP(it=qi,it+1=qj,O∣λ)\xi_t(i,j)=\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)}{\sum_{i=1}^N\sum_{j=1}^NP(i_t=q_i,i_{t+1}=q_j,O|\lambda)}ξt(i,j)=P(O∣λ)P(it=qi,it+1=qj,O∣λ)=∑i=1N∑j=1NP(it=qi,it+1=qj,O∣λ)P(it=qi,it+1=qj,O∣λ)而P(it=qi,it+1=qj,O∣λ)=αt(i)aijbj(ot+1)βt+1(j)P(i_t=q_i,i_{t+1}=q_j,O|\lambda)=\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)P(it=qi,it+1=qj,O∣λ)=αt(i)aijbj(ot+1)βt+1(j)所以ξt(i,j)=αt(i)aijbj(ot+1)βt+1(j)∑i=1N∑j=1Nαt(i)aijbj(ot+1)βt+1(j)\xi_t(i,j)=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}ξt(i,j)=∑i=1N∑j=1Nαt(i)aijbj(ot+1)βt+1(j)αt(i)aijbj(ot+1)βt+1(j)
3. 将γt(i)\gamma_t(i)γt(i)和ξt(i,j)\xi_t(i,j)ξt(i,j)对各个时刻ttt求和,可以得到一些有用的期望值。
(1). 在观测OOO下状态III出现的期望值:∑t=1Tγt(i)\sum_{t=1}^T\gamma_t(i)t=1∑Tγt(i)
(2).在观测OOO下由状态iii转移的期望值:∑t=1T−1γt(i)\sum_{t=1}^{T-1}\gamma_t(i)t=1∑T−1γt(i)
(3).在观测OOO下由状态iii转移到状态jjj的期望值:∑t=1T−1ξt(i,j)\sum_{t=1}^{T-1}\xi_t(i,j)t=1∑T−1ξt(i,j)
10.3 学习算法
隐马尔可夫模型的学习,根据训练数据是包括观测序列和对应的状态序列还是只有观测序列,可以分别由监督学习与无监督学习实现。
10.3.1 监督学习方法
假设已给的训练数据包括SSS个长度相同的观测序列和对应的状态序列{(O1,I1),(O2,I2),⋯,(OS,IS)}\lbrace(O_1,I_1),(O_2,I_2),\cdots,(O_S,I_S)\rbrace{(O1,I1),(O2,I2),⋯,(OS,IS)},那么可以通过极大似然估计法来估计隐马尔可夫模型的参数。
1. 转移概率aija_{ij}aij的估计
2.观测概率bj(k)b_j(k)bj(k)的估计
3.初始状态概率πi\pi_iπi的估计π^i\hat\pi_iπ^i为SSS个样本中初始状态为qiq_iqi的频率
10.3.2 Baum-Welch算法
假设给定的数据集仅包含SSS个长度为TTT的观测序列{O1,O2,⋯,OS}\lbrace O_1,O_2,\cdots,O_S\rbrace{O1,O2,⋯,OS}而没有对应的状态序列,目标是学习隐马尔可夫模型λ=(A,B,π)\lambda=(A,B,\pi)λ=(A,B,π)的参数。将观测序列数据作为观测数据OOO,状态序列数据看作不可观测的隐数据III,隐马尔可夫模型是一个含有隐变量的概率模型,符合使用EM算法的条件。P(O∣λ)=∑IP(O∣I,λ)P(I∣λ)P(O|\lambda)=\sum_IP(O|I,\lambda)P(I|\lambda)P(O∣λ)=I∑P(O∣I,λ)P(I∣λ)
1. 确定完全数据的对数似然函数
所有观测数据写成O=(o1,o2,⋯,oT)O=(o_1,o_2,\cdots,o_T)O=(o1,o2,⋯,oT),所有隐数据写成I=(i1,i2,⋯,iT)I=(i_1,i_2,\cdots,i_T)I=(i1,i2,⋯,iT),完全数据是(O,I)=(o1,o2,⋯,oT,i1,i2,⋯,iT)(O,I)=(o_1,o_2,\cdots,o_T,i_1,i_2,\cdots,i_T)(O,I)=(o1,o2,⋯,oT,i1,i2,⋯,iT)。完全数据的对数似然函数是logP(O,I∣λ)logP(O,I|\lambda)logP(O,I∣λ).
2. EM算法的E步骤,求Q函数Q(λ,λ‾)Q(\lambda,\overline\lambda)Q(λ,λ)Q(λ,λ‾)=∑IlogP(I,O∣λ)P(I∣O,λ‾)=∑IlogP(I,O∣λ)P(I,O∣λ‾)P(O∣λ‾)Q(\lambda,\overline\lambda)=\sum_IlogP(I,O|\lambda)P(I|O,\overline\lambda)=\sum_IlogP(I,O|\lambda)\frac{P(I,O|\overline\lambda)}{P(O|\overline\lambda)}Q(λ,λ)=I∑logP(I,O∣λ)P(I∣O,λ)=I∑logP(I,O∣λ)P(O∣λ)P(I,O∣λ)省略对λ\lambdaλ而言是常数项的1P(O∣λ‾)\frac{1}{P(O|\overline\lambda)}P(O∣λ)1,最终的QQQ函数为Q(λ,λ‾)=∑IlogP(I,O∣λ)P(I,O∣λ‾)Q(\lambda,\overline\lambda)=\sum_IlogP(I,O|\lambda)P(I,O|\overline\lambda)Q(λ,λ)=I∑logP(I,O∣λ)P(I,O∣λ)其中,λ‾\overline\lambdaλ是隐马尔可夫模型参数的当前估计值,λ\lambdaλ是要极大化的隐马尔可夫模型参数。P(O,I∣λ)=πi1bi1(o1)ai1i2bi2(o2)⋯aiT−1iTbiT(oT)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∣λ)=πi1bi1(o1)ai1i2bi2(o2)⋯aiT−1iTbiT(oT)