10_隐马尔科夫模型HMM2_统计学习方法

2024-04-06 23:32:56

文章目录

四、学习算法

1、监督学习方法
2、非监督学习方法（Baum-Welch算法）

五、预测算法

1、近似算法
2、维特比算法

（1）最优路径特性
（2）两个变量
（3）维特比算法流程

隐马尔科夫模型内容较多，方便阅读，分成2个部分
上接：10_隐马尔科夫模型HMM1_统计学习方法

四、学习算法

估计模型 $\lambda = (A,B,\Pi)$ λ=(A,B,Π)参数。

隐马尔科夫模型的学习，根据训练数据是包含观测序列和对应的状态序列还是只有观测序列，可以分为监督学习和非监督学习。

1、监督学习方法

假设已给训练数据包含 $S$ S个长度相同的观测序列和对应的状态序列 $\{(O_1,I_1),(O_2,I_2),\cdots,(O_N,I_N)\}$ {(O1,I1),(O2,I2),⋯,(ON,IN)}，那么可以用极大似然估计法来估计隐马尔科夫模型的参数。具体方法如下。

（1）转移概率 $a_{xy}$ axy的估计
设样本中时刻 $t\space$ t 处于状态 $x\space$ x 时刻 $t+1$ t+1转移到状态 $y$ y的频数为 $A_{xy}$ Axy,那么状态转移概率 $a_{xy}$ axy的估计是
$\hat a_{xy} = \dfrac{A_{xy}}{\sum_{y=1}^N A_{xy}},\space x = 1,2,\cdots,N;y = 1,2,\cdots,N \tag{30}$ a^xy=∑y=1NAxyAxy, x=1,2,⋯,N;y=1,2,⋯,N(30)

（2）观测概率 $b_{yk}$ byk的估计
设样本中状态为 $y$ y并观测为 $k$ k的频数是 $B_{yk}$ Byk，那么状态为 $y$ y观测为 $k$ k的概率 $b_{yk}$ byk的估计是
$\hat b_{yk} = \dfrac{B_{yk}}{\sum_{k=1}^M B_{yk}},\space y=1,2,\cdots,N;k=1,2,\cdots,M \tag{31}$ b^yk=∑k=1MBykByk, y=1,2,⋯,N;k=1,2,⋯,M(31)

（3）初始状态概率 $\pi_{x}$ πx的估计 $\hat \pi_{x}$ π^x为 $S$ S个样本中初始状态为 $q_x$ qx的频数

由于监督学习需要使用训练数据，而人工标注训练数据往往代价很高，有时就会利用非监督学习的方法。

2、非监督学习方法（Baum-Welch算法）

假设给定训练数据只包含 $S$ S个长度为 $T$ T的观测序列 $\{O_1,O_2,\cdots,O_S\}$ {O1,O2,⋯,OS}而没有对应的状态序列，目标是学习隐马尔科夫模型 $\lambda = (A,B,\Pi)$ λ=(A,B,Π)的参数。我们将观测序列数据看作观测数据 $O$ O，状态序列数据看作不可观测的隐数据 $I$ I，那么隐马尔科夫模型事实上是一个含有隐变量的概率模型
$P(O|\lambda) = \sum_{t}P(O|I,\lambda)P(I|\lambda) \tag{32}$ P(O∣λ)=t∑P(O∣I,λ)P(I∣λ)(32)
它的参数学习可以由EM算法实现。

（1）确定完全数据的对数似然函数

所有观测数据写成 $O = (o_1,o_2,\cdots,o_T)$ O=(o1,o2,⋯,oT)，所有隐数据写成 $I = (i_1,i_2,\cdots,i_T)$ I=(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)。完全数据的对数似然函数是 $lnP(O,I|\lambda)$ lnP(O,I∣λ)。

（2）EM算法的E步：极大化 $Q$ Q函数 $Q(\lambda,\bar\lambda)$ Q(λ,λˉ)
$\begin{aligned}arg\;\max_{\lambda} Q(\lambda,\bar\lambda) & = \sum_{I}P(I|O,\bar\lambda)lnP(O,I|\lambda)\\ & = \sum_{I}\dfrac{P(O,I|\bar\lambda)}{P(O|\hat\lambda)}lnP(O,I|\lambda) \\ & = arg\;\max_{\lambda} \sum_{I}P(O,I|\bar\lambda)lnP(O,I|\lambda) \tag{33} \end{aligned}$ argλmaxQ(λ,λˉ)=I∑P(I∣O,λˉ)lnP(O,I∣λ)=I∑P(O∣λ^)P(O,I∣λˉ)lnP(O,I∣λ)=argλmaxI∑P(O,I∣λˉ)lnP(O,I∣λ)(33)
其中 $\bar\lambda$ λˉ是隐马尔科夫模型参数的当前估计值， $\lambda$ λ是要极大化的隐马尔科夫模型参数。

由式（13）有
$P(O|\lambda) = \sum_{I} P(O,I|\lambda) = \sum_{I} P(O|I,\lambda)P(I|\lambda)= \sum_{i_1,i_2,\cdots,i_T} \pi_{i_1}b_{i_1}(o_1) a_{i_1 i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}\space\space i_{T}}b_{i_T}(o_T)$ P(O∣λ)=I∑P(O,I∣λ)=I∑P(O∣I,λ)P(I∣λ)=i1,i2,⋯,iT∑πi1bi1(o1)ai1i2bi2(o2)⋯aiT−1 iTbiT(oT)
于是函数 $Q(\lambda,\bar\lambda)$ Q(λ,λˉ)可以写成：
$\begin{aligned} Q(\lambda,\bar\lambda) = & \sum_{I}P(O,I|\bar\lambda)ln\pi_{i_1} \\ & +\sum_{I}P(O,I|\bar\lambda)\sum_{t=1}^{T-1}ln a_{i_t\,i_{t+1}}\\ & +\sum_{I}P(O,I|\bar\lambda)\sum_{t=1}^{T}ln b_{i_t}(o_t)\tag{34} \end{aligned}$ Q(λ,λˉ)=I∑P(O,I∣λˉ)lnπi1+I∑P(O,I∣λˉ)t=1∑T−1lnaitit+1+I∑P(O,I∣λˉ)t=1∑Tlnbit(ot)(34)
式中求和是对所有训练数据的序列总长度 $T$ T进行的。

（3）EM算法的M步：极大化 $Q$ Q函数 $Q(\lambda,\bar\lambda)$ Q(λ,λˉ)求模型参数 $A,B,\Pi$ A,B,Π

由于要极大化的参数在式（34）中单独地出现在3个项中，所以只需对各项分别极大化，式（34）中三项分别命名为 $\Pi$ Π式、 $A$ A式和 $B$ B式。

1）求 $\Pi$ Π式即式（34）的第1项，可以写成：
$\sum_{I}P(O,I|\bar\lambda)ln\pi_{i_1} = \sum_{x=1}^N P(O,i_1 = q_x|\bar\lambda)ln\pi_{x}$ I∑P(O,I∣λˉ)lnπi1=x=1∑NP(O,i1=qx∣λˉ)lnπx
因为有 $\pi_x$ πx满足约束条件 $\sum_{x=1}^N \pi_x = 1$ ∑x=1Nπx=1，利用拉格朗日乘子法，写出拉格朗日函数：
$\sum_{x=1}^N P(O,i_1 = q_x|\bar\lambda)ln\pi_{x} + \gamma\left( \sum_{x=1}^N \pi_x - 1\right)$ x=1∑NP(O,i1=qx∣λˉ)lnπx+γ(x=1∑Nπx−1)
对其求偏导数并令结果为0
$\dfrac{\partial}{\partial \pi_x}\left[\sum_{x=1}^N P(O,i_1 = q_x|\bar\lambda)ln\pi_{x} + \gamma\left( \sum_{x=1}^N \pi_x - 1\right)\right] = 0 \tag{35}$ ∂πx∂[x=1∑NP(O,i1=qx∣λˉ)lnπx+γ(x=1∑Nπx−1)]=0(35)
得
$P(O,i_1 = q_x|\bar\lambda) +\gamma \pi_x =0$ P(O,i1=qx∣λˉ)+γπx=0
对 $x$ x求和得到 $\gamma$ γ
$\sum_{x=1}^N P(O,i_1 = q_x|\bar\lambda) +\sum_{x=1}^N \gamma \pi_x =0 \Longrightarrow \gamma = - P(O|\bar\lambda)$ x=1∑NP(O,i1=qx∣λˉ)+x=1∑Nγπx=0⟹γ=−P(O∣λˉ)
代入式（35）即得
$\pi_x = \dfrac{P(O,i_1 = q_x|\bar\lambda)}{P(O|\bar\lambda)} = \gamma_1(x) \tag{36}$ πx=P(O∣λˉ)P(O,i1=qx∣λˉ)=γ1(x)(36)

给定模型参数 $\bar\lambda$ λˉ和观测 $O$ O，在时刻1处于状态 $q_x$ qx的概率 $\gamma_1(x)$ γ1(x)。

2） $A$ A式即式（34）中的第2项，可以写成:
$\sum_{I}P(O,I|\bar\lambda)\sum_{t=1}^{T-1}ln a_{i_t\,i_{t+1}} = \sum_{x=1}^N\sum_{y=1}^N\sum_{t=1}^{T-1}P(O,i_t = q_x,i_{t+1} = q_y|\bar\lambda)lna_{xy}$ I∑P(O,I∣λˉ)t=1∑T−1lnaitit+1=x=1∑Ny=1∑Nt=1∑T−1P(O,it=qx,it+1=qy∣λˉ)lnaxy
相似有约束条件 $\sum_{y=1}^N a_{xy} = 1$ ∑y=1Naxy=1的拉格朗日乘子法可以求出

$a_{xy} = \dfrac{\sum_{t=1}^{T-1}P(O,i_t = q_x,i_{t+1} = q_y|\bar\lambda)}{\sum_{t=1}^{T-1}P(O,i_t = q_x|\bar\lambda)} = \dfrac{\sum_{t=1}^{T-1}P(O,i_t = q_x,i_{t+1} = q_y|\bar\lambda)/P(O|\bar\lambda)}{\sum_{t=1}^{T-1}P(O,i_t = q_x|\bar\lambda)/P(O|\bar\lambda)} = \dfrac{\sum_{t=1}^{T-1}\xi_t(x,y)}{\sum_{t=1}^{T-1}\gamma_t(x)}\tag{37}$ axy=∑t=1T−1P(O,it=qx∣λˉ)∑t=1T−1P(O,it=qx,it+1=qy∣λˉ)=∑t=1T−1P(O,it=qx∣λˉ)/P(O∣λˉ)∑t=1T−1P(O,it=qx,it+1=qy∣λˉ)/P(O∣λˉ)=∑t=1T−1γt(x)∑t=1T−1ξt(x,y)(37)

给定模型 $\bar\lambda$ λˉ和观测 $O$ O，在时刻 $t\space$ t 处于状态 $q_x$ qx且在时刻 $t+1$ t+1处于状态 $q_y$ qy的概率 $\xi_t(x,y)$ ξt(x,y)，在时刻 $t\,$ t处于状态 $q_x$ qx的概率 $\gamma_t(x)$ γt(x)；
在观测 $O$ O下，状态 $q_x$ qx转移到状态 $q_y$ qy的期望值 $\sum_{t=1}^{T-1} \xi_t(x,y)$ ∑t=1T−1ξt(x,y)；
在观测 $O$ O下，由状态 $q_x$ qx转移的期望值 $\sum_{t=1}^{T-1} \gamma_t(x)$ ∑t=1T−1γt(x)。

3） $B$ B式即式（34）中的第3项，可以写成:
$\sum_{I}P(O,I|\bar\lambda)\sum_{t=1}^{T}ln b_{i_t}(o_t) = \sum_{x =1}^N \sum_{t=1}^T P(O,i_t = q_x|\bar\lambda)lnb_x(o_t)$ I∑P(O,I∣λˉ)t=1∑Tlnbit(ot)=x=1∑Nt=1∑TP(O,it=qx∣λˉ)lnbx(ot)

同样用拉格朗日乘子法，有约束条件 $\sum_{k=1}^N b_{xk} = 1$ ∑k=1Nbxk=1。注意，只有在 $o_t = v_k$ ot=vk时 $b_x(o_t)$ bx(ot)对 $b_{xk}$ bxk的偏导数才不为0，以 $I(o_t = v_k)$ I(ot=vk)表示。求得

$b_{xk} = \dfrac{\sum_{t=1}^T P(O,i_t = q_x|\bar\lambda)I(o_t = v_k)}{\sum_{t=1}^T P(O,i_t = q_x|\bar\lambda)} = \dfrac{\sum_{t=1}^T P(O,i_t = q_x|\bar\lambda)I(o_t = v_k)/P(O|\bar\lambda)}{\sum_{t=1}^T P(O,i_t = q_x|\bar\lambda)/P(O|\bar\lambda)} = \dfrac{\sum_{t=1,o_t = v_k}^T \gamma_t(x)}{\sum_{t=1}^T \gamma_t(x)} \tag{38}$ bxk=∑t=1TP(O,it=qx∣λˉ)∑t=1TP(O,it=qx∣λˉ)I(ot=vk)=∑t=1TP(O,it=qx∣λˉ)/P(O∣λˉ)∑t=1TP(O,it=qx∣λˉ)I(ot=vk)/P(O∣λˉ)=∑t=1Tγt(x)∑t=1,ot=vkTγt(x)(38)

给定模型 $\bar\lambda$ λˉ和观测 $O$ O，在时刻 $t\,$ t处于状态 $q_x$ qx的概率 $\gamma_t(x)$ γt(x)；
在观测 $O$ O下，状态 $q_x$ qx得到观测 $v_k$ vk的期望值 $\sum_{t=1,o_t = v_k}^T \gamma_t(x)$ ∑t=1,ot=vkTγt(x)；
在观测 $O$ O下，状态 $q_x$ qx出现的期望值 $\sum_{t=1}^T \gamma_t(x)$ ∑t=1Tγt(x)。

上面求得的 $\Pi$ Π式、 $A$ A式和 $B$ B式可以结合式（27）、（28）和（29）更容易理解其意义。

五、预测算法

预测问题，也称为解码（decoding）问题。已知模型 $\lambda = (A,B,\Pi)$ λ=(A,B,Π)和观测序列 $O = (o_1,o_2,\cdots,o_T)$ O=(o1,o2,⋯,oT)，求对给定观测序列条件概率 $P(I|O)$ P(I∣O)最大的状态序列 $I = (i_1,i_2,\cdots,i_T)$ I=(i1,i2,⋯,iT)。即给定观测序列，求最有可能的对应的状态序列。隐马尔科夫模型预测两种算法：近似算法和维特比算法。

1、近似算法

近似算法的想法是，在每个时刻t选择在该时刻最有可能出现的状态 $i_t^*$ it∗，从而得到一个状态序列 $I^* = (i_1^*,i_2^*,\cdots,i_T^*)$ I∗=(i1∗,i2∗,⋯,iT∗)，将它作为预测的结果。

给定隐马尔科夫模型 $\lambda$ λ和观测序列 $O$ O，在时刻t处于状态 $q_x$ qx的概率 $\gamma_t(x)$ γt(x)是
$\gamma_t(x) = \dfrac{\alpha_t(x)\beta_t(x)}{P(O|\lambda)} = \dfrac{\alpha_t(x)\beta_t(x)}{ \sum_{y=1}^N \alpha_t(y)\beta_t(y)} \tag{39}$ γt(x)=P(O∣λ)αt(x)βt(x)=∑y=1Nαt(y)βt(y)αt(x)βt(x)(39)

在每一时刻t最有可能的状态 $i_t^*$ it∗是
$i_t^* = arg\,\max_{1\leq x \leq N}[\gamma_t(x)],\;t =1,2,\cdots,T \tag{40}$ it∗=arg1≤x≤Nmax[γt(x)],t=1,2,⋯,T(40)
从而得到状态序列 $I^* = (i_1^*,i_2^*,\cdots,i_T^*)$ I∗=(i1∗,i2∗,⋯,iT∗)。

近似算法的优点是计算简单，其缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分，即单个状态的最优并不能保证整体最优。上述方法得到的状态序列中有可能存在转移概率为0的相邻状态，即对某些 $x,y,a_{xy}=0$ x,y,axy=0时。

2、维特比算法

维特比算法实际是用动态规划解隐马尔科夫模型预测问题，即用动态规划求概率最大路径，这时一条路径对应着一个状态序列。

（1）最优路径特性

根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻t通过结点 $i_t^*$ it∗，那么这一路经从结点 $i_t^*$ it∗到终点 $i_T^*$ iT∗的部分路径，对于从 $i_t^*$ it∗到 $i_T^*$ iT∗的所有可能的部分路径来说，必须是最优的。

依据上面的原理，只需从时刻 $t=1$ t=1开始，递推地计算在时刻 $t$ t状态为 $i\,$ i的各条部分路径的最大概率，直至得到时刻 $t=T$ t=T状态为 $i\,$ i的各条路径的最大概率。时刻 $t=T$ t=T的最大概率即为最优路径的概率 $P^*$ P∗，最优路径的终结点 $i_T^*$ iT∗也同时得到。
为了找出最优路径的各个结点，从终结点 $i_T^*$ iT∗开始，由后向前逐步求得结点 $i_{T-1}^*,\cdots,i_1^*$ iT−1∗,⋯,i1∗，得到最优路径 $I^* = (i_1^*,i_2^*,\cdots,i_T^*)$ I∗=(i1∗,i2∗,⋯,iT∗)。

为什么不在计算最大概率的时候就直接记住 $t\,$ t时刻的概率最大的状态呢？最终求得最大概率后，最优的状态序列 $I^*$ I∗不就直接求出了吗？

因为 $t\,$ t时刻的最优状态需要 $t+1$ t+1时刻来确认验证，而 $t+1$ t+1时刻的状态需要 $t+2$ t+2时刻验证，所以必须从最后向前才能推出最终的最优状态序列。

（2）两个变量

引入两个变量 $\delta$ δ和 $\psi$ ψ。定义在时刻 $t\,$ t状态为 $q_x\,$ qx的所有单个路径 $(i_1,i_2,\cdots,i_t)$ (i1,i2,⋯,it)中概率最大值为
$\delta_t(x) = \max_{i_1,i_2,\cdots,i_{t-1}}P(i_t = q_x,i_{t-1},\cdots,i_1,o_t,\cdots,o_1|\lambda),\;x=1,2,\cdots,N \tag{41}$ δt(x)=i1,i2,⋯,it−1maxP(it=qx,it−1,⋯,i1,ot,⋯,o1∣λ),x=1,2,⋯,N(41)

$\delta_t(x)$ δt(x)与前向概率 $\alpha_t(x)$ αt(x)比较

前向概率是计算所有路径在时刻 $t\,$ t状态为 $q_x$ qx的概率,是计算指定观测序列 $O$ O出现的概率；
$\delta_t(x)$ δt(x)是计算在时刻 $t\,$ t状态为 $q_x$ qx中所有路径中的最大概率，是用于计算指定观测序列 $O$ O对应的最大概率状态序列 $I^*$ I∗。

由定义可得变量 $\delta$ δ的递推公式：
$\begin{aligned}\delta_{t+1}(y)&=\max_{i_1,i_2,\cdots,i_{t}} P(i_{t+1} = q_y,i_{t},\cdots,i_1,o_{t+1},\cdots,o_1|\lambda)\\ &=\max_{1\leq x \leq N}[\delta_t(x)a_{xy}]b_y(o_{t+1}),\;y=1,2,\cdots,N;\,t = 1,2,\cdots,T-1 \tag{42} \end{aligned}$ δt+1(y)=i1,i2,⋯,itmaxP(it+1=qy,it,⋯,i1,ot+1,⋯,o1∣λ)=1≤x≤Nmax[δt(x)axy]by(ot+1),y=1,2,⋯,N;t=1,2,⋯,T−1(42)

定义在时刻 $t+1\,$ t+1状态为 $q_y$ qy的所有单个路径 $(i_1,i_2,\cdots,i_{t},q_y)$ (i1,i2,⋯,it,qy)中概率最大的路径的第 $t$ t个结点为
$\begin{aligned}\psi_{t+1}(y) = & arg\;\max_{1\leq x \leq N} [\delta_{t}(x)a_{xy}]b_y(o_{t+1})\\ = & arg\;\max_{1\leq x \leq N} [\delta_{t}(x)a_{xy}],\;y = 1,2,\cdots,N\tag{43} \end{aligned}$ ψt+1(y)==arg1≤x≤Nmax[δt(x)axy]by(ot+1)arg1≤x≤Nmax[δt(x)axy],y=1,2,⋯,N(43)

加深维特比算法的理解可以参考博客：数学之美：维特比和维特比算法。

（3）维特比算法流程

输入：模型 $\lambda = (A,b,\Pi)$ λ=(A,b,Π)和观测 $O = (o_1,o_2,\cdots,o_T)$ O=(o1,o2,⋯,oT)；

输出：最优路径 $I^* = (i_1^*,i_2^*,\cdots,i_T^*)$ I∗=(i1∗,i2∗,⋯,iT∗)。

1）初始化
$\delta_1(x) = \pi_x b_x(o_1),\qquad x =1,2,\cdots,N$ δ1(x)=πxbx(o1),x=1,2,⋯,N
$\psi_1(x) = 0,\qquad x =1,2,\cdots,N$ ψ1(x)=0,x=1,2,⋯,N

2）递推。对 $t = 1,2,\cdots,T-1$ t=1,2,⋯,T−1
$\delta_{t+1}(y) = \max_{1\leq x \leq N}[\delta_t(x)a_{xy}]b_y(o_{t+1}),\;y=1,2,\cdots,N$ δt+1(y)=1≤x≤Nmax[δt(x)axy]by(ot+1),y=1,2,⋯,N
$\psi_{t+1}(y) = arg\;\max_{1\leq x \leq N} [\delta_{t}(x)a_{xy}],\;y = 1,2,\cdots,N$ ψt+1(y)=arg1≤x≤Nmax[δt(x)axy],y=1,2,⋯,N

3）终止
$P^* = \max_{1\leq y \leq N}\delta_T(y)$ P∗=1≤y≤NmaxδT(y)
$i_T^* = arg\;\max_{1\leq y \leq N}[\delta_T(y)]$ iT∗=arg1≤y≤Nmax[δT(y)]

4）最优路径回溯。对 $t=T-1,T-2,\cdots,1$ t=T−1,T−2,⋯,1
$i_t^* = \psi_{t+1}(i_{t+1}^*)$ it∗=ψt+1(it+1∗)
求得最优路径 $I^* = (i_1^*,i_2^*,\cdots,i_T^*)$ I∗=(i1∗,i2∗,⋯,iT∗)。

对于隐马尔科夫模型的学习，在学习之前没有接触过相关知识。所以说我的这篇总结很适合刚入门的小白，回过头来看我总结的大部分内容来自李航老师的统计学习方法，既然是对统计学习方法的学习总结，那么我尽可能基于书本来做总结，另外学习过程中发现书确实非常不错，只是在某些方面可能有些简化，对于刚入门的来说不那么好理解。我认为理解有困难的地方，对其进行了补充说明和图示，另外我把书中所有使用 $i,j$ i,j的地方进行了替换成 $x,y$ x,y，以免与状态序列 $I$ I发生混淆。

这个模型感觉非常好，可以解决很多问题啊！后面在练习中进一步加深理解。
$********************************************$ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
未完待续……

参考资料

码农公寓