【李航统计学习笔记】第十章：隐马尔科夫模型

10.1 隐马尔科夫模型

蓝色圆圈代表状态变量，绿色圆圈代表观测变量。

模型参数及符号：

状态集合： Q = { q 1 , … q N } Q=\left\{q_{1, \ldots} q_{N}\right\} Q={q1,…​qN​}

预测集合： V = { v 1 , … v M } V=\left\{v_{1, \ldots} v_{M}\right\} V={v1,…​vM​}

状态序列： I = { i 1 , … i T } i t ⊂ Q I=\left\{i_{1, \ldots} i_{T}\right\} \quad i_{\mathrm{t}} \subset Q I={i1,…​iT​}it​⊂Q

预测序列 : O = { 0 1 , … o T } o t ⊂ O=\left\{0_{1, \ldots} o_{T}\right\} \quad o_{\mathrm{t}} \subset O={01,…​oT​}ot​⊂ $V$

然后我们可以构建状态转移矩阵
i 2 = q 1 i 2 = q 2 … i 2 = q N i 1 = q 1 a 11 a 12 … a 1   N a 1 j = P ( i 2 = q j ∣ i 1 = q 1 ) i 1 = q 2 a 21 a 22 … a 2   N a 2 j = P ( i 2 = q j ∣ i 1 = q 2 ) … … … … … … i 1 = q N a N 1 a N 2 … a N N a N j = P ( i 2 = q j ∣ i 1 = q N )

i1​=q1​i1​=q2​…i1​=qN​​i2​=q1​a11​a21​…aN1​​i2​=q2​a12​a22​…aN2​​……………​i2​=qN​a1 N​a2 N​…aNN​​a1j​=P(i2​=qj​∣i1​=q1​)a2j​=P(i2​=qj​∣i1​=q2​)…aNj​=P(i2​=qj​∣i1​=qN​)​​
也就是
A N × N = [ a 11 a 12 ⋯ a 1 N a 21 a 22 ⋯ a 2 N ⋯ ⋯ ⋯ ⋯ a N 1 a N 2 ⋯ a N N ] A_{N \times N}=\left[

a11a12⋯a1Na21a22⋯a2N⋯⋯⋯⋯aN1aN2⋯aNN" role="presentation" style="position: relative;">a11a21⋯aN1a12a22⋯aN2⋯⋯⋯⋯a1Na2N⋯aNN$$\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1N}\\ a_{21}& a_{22}& \cdots & a_{2N}\\ \cdots & \cdots & \cdots & \cdots \\ a_{N1}& a_{N2}& \cdots & a_{NN}\end{array}$$

\right] AN×N​=⎣ ⎡​a11​a21​⋯aN1​​a12​a22​⋯aN2​​⋯⋯⋯⋯​a1N​a2N​⋯aNN​​⎦ ⎤​
然后我们构建观测概率矩阵
o 1 = v 1 o 1 = v 2 … o 1 = v M i 1 = q 1 b 1 ( 1 ) b 1 ( 2 ) … b 1 ( M ) i 1 = q 2 b 2 ( 1 ) b 2 ( 2 ) … b 2 ( M ) … … … … … i 1 = q N b N ( 1 ) b N ( 2 ) … b N ( M )

o1=v1o1=v2…o1=vMi1=q1b1(1)b1(2)…b1(M)i1=q2b2(1)b2(2)…b2(M)……………i1=qNbN(1)bN(2)…bN(M)" role="presentation" style="position: relative;">i1=q1i1=q2…i1=qNo1=v1b1(1)b2(1)…bN(1)o1=v2b1(2)b2(2)…bN(2)……………o1=vMb1(M)b2(M)…bN(M)$$\begin{array}{|ccccc|}\hline & o_1=v_1& o_1=v_2& \dots & o_1=v_{\mathrm{M}}\\ i_1=q_1& b_1(1)& b_1(2)& \dots & b_1(\mathrm{M})\\ i_1=q_2& b_2(1)& b_2(2)& \dots & b_2(\mathrm{M})\\ \dots & \dots & \dots & \dots & \dots \\ i_1=q_{\mathrm{N}}& b_{\mathrm{N}}(1)& b_{\mathrm{N}}(2)& \dots & b_{\mathrm{N}}(\mathrm{M})\\ \hline\end{array}$$

i1​=q1​i1​=q2​…i1​=qN​​o1​=v1​b1​(1)b2​(1)…bN​(1)​o1​=v2​b1​(2)b2​(2)…bN​(2)​……………​o1​=vM​b1​(M)b2​(M)…bN​(M)​​

B N × M = [ b 11 b 12 ⋯ b 1 M b 21 b 22 ⋯ b 2 M ⋯ ⋯ ⋯ ⋯ b N 1 b N 2 ⋯ b N M ] B_{N \times M}=\left[

\right] BN×M​=⎣ ⎡​b11​b21​⋯bN1​​b12​b22​⋯bN2​​⋯⋯⋯⋯​b1M​b2M​⋯bNM​​⎦ ⎤​

我们设定初始状态概率向量为
π = [ π 1 π 2 ⋯ π N ] = [ P ( i 1 = q 1 ) P ( i 2 = q 2 ) ⋯ P ( i N = q N ) ] \pi=\left[

\right]=\left[\right] π=⎣ ⎡​π1​π2​⋯πN​​⎦ ⎤​=⎣ ⎡​P(i1​=q1​)P(i2​=q2​)⋯P(iN​=qN​)​⎦ ⎤​
模型参数量是
$$\lambda =\left({\pi }_{N\times 1},A_{N\times N},B_{N\times M}\right)$$
总参数量=$N\times (N\times N)\times (N\times M)$。而自由参数量=$(N-1)\times (N\times N-N)\times (N\times M-N)$。

在隐马尔科夫模型中，我们有两个基本假设:

• 齐次马尔科夫性: $P\left(i_t\mid i_{t-1},\cdots ,i_1\right)=P\left(i_t\mid i_{t-1}\right)$
• 观测独立假设

同时我们有三个基本问题：

• 概率计算问题：$P(O\mid \lambda )$
• 学习问题: $\arg \max P(O\mid \lambda )$
• 预测问题: $\arg \max P(I\mid O)$

概率算法，计算$P(O\mid \lambda )$

1.直接计算法

$$P(O\mid \lambda )=\sum _{I}P(O\mid I,\lambda )P(I\mid \lambda )=\sum _{i_1,i_2,\dots ,i_T}{\pi }_{i_1}{b}_{i_1\left(o_1\right)}{a}_{i_1{i}_2}{b}_{i_2\left(o_2\right)}\dots a_{i_{T-1}{i}_T}{b}_{i_T\left(o_T\right)}$$

但是这个式子的计算复杂度为$O(T{N}^T)$

2.前向计算法

计算复杂度为: $O\left(T{N}^2\right)$

引入新变量: ${\alpha }_t(i)=P\left(o_1,\cdots ,o_t,i_t=q_i\mid \lambda \right),i=1,\dots ,N$

输入：隐马尔科夫模型$\lambda$, 观测序列$O$

输出：观测序列概率$P(O\mid \lambda )$

步骤：

(1) 初值: ${\alpha }_1(i)={\pi }_i{b}_i\left(o_1\right),i=1,2,\dots ,N$
(2) 递推: 对于$\mathrm{t}=1,2,\dots ,T-1$
α t + 1 ( i ) = P ( O 1 , … , o t , o t + 1 , i t + 1 = q i ) = ∑ j = 1 N P ( O 1 , … , O t , i t = q i ) P ( O t + 1 ∣ i t + 1 = q i ) P ( i t + 1 = q i ∣ i t = q j ) = [ ∑ j = 1 N α t ( j ) a j i ] b i ( o t + 1 )

αt+1​(i)=P(O1​,…,ot​,ot+1​,it+1​=qi​)=j=1∑N​P(O1​,…,Ot​,it​=qi​)P(Ot+1​∣it+1​=qi​)P(it+1​=qi​∣it​=qj​)=[j=1∑N​αt​(j)aji​]bi​(ot+1​)​
(3) 终止：
$$P(O\mid \lambda )=\mathrm{P}\left(O_1,\dots ,O_T\mid \lambda \right)=\sum _{i=1}^N\mathrm{P}\left(O_1,\dots ,O_T,i_T=q_i\mid \lambda \right)=\sum _{i=1}^N{\alpha }_T(i)$$
我们引入新变量${\beta }_t(i)=\mathrm{P}\left(o_{t+1},\cdots ,o_T\mid i_t=q_i,\lambda \right),i=1,\dots ,N$

3.后向算法

计算复杂度$O(T{N}^2)$

输入：隐马尔科夫模型$\lambda$,观测序列$O$

输出：观测序列概率$P(O\mid \lambda )$

步骤：

(1) 初值：${\beta }_T(i)=1,i=1,2,\dots ,N$
(2) 递推：对t $=T-1,T-2,\dots ,1$
$${\beta }_t(i)=\sum _{j=1}^N{a}_{ij}{b}_j\left(o_{t+1}\right){\beta }_{t+1}(j),i=1,2,\dots ,N$$
(3) 终止： $P(O\mid \lambda )={\sum }_{i=1}^N{\pi }_i{b}_i\left(o_i\right){\beta }_1(i)$

学习算法，估计参数$\lambda =(\pi ,A,B)$

1.监督学习方法

已知训练数据包含$S$个长度相同的观测序列和对应的状态序列 { ( O 1 , I 1 ) , ( O 2 , I 2 ) , … , ( O S , I S ) } \left\{\left(O_{1}, I_{1}\right),\left(O_{2}, I_{2}\right), \ldots,\left(O_{S}, I_{S}\right)\right\} {(O1​,I1​),(O2​,I2​),…,(OS​,IS​)}

(1)转移概率 $a_{ij}$ 的估计
$${\hat{a}}_{ij}=\frac{A_{ij}}{{\sum }_{j=1}^N{A}_{ij}},i=1,2,\dots ,N;j=1,2,\dots ,N$$
(2)转移概率 $a_{ij}$ 的估计
$${\hat{b}}_j(k)=\frac{B_{jk}}{{\sum }_{k=1}^M{B}_{jk}}j=1,2,\dots ,N;k=1,2,\dots ,M$$
(3)初始状态概率 ${\pi }_i$ 的估计 ${\hat{\pi }}_i$ 为 $S$ 个样本中初始状态为 $q_i$ 的频率

2.Buam-Welch算法（EM算法）

输入：观测数据$$O=\left(O_1,O_2,\dots ,O_T\right)$$

输出：隐马尔科夫模型参数

(1)初始化：对$n=0$,选取$a_{ij}^{(0)},b_j(k{)}^{(0)},{\pi }_i^{(0)}$,得到模型${\lambda }^{(0)}=\left(A^{(0)},B^{(0)},{\pi }^{(0)}\right)$

(2)递推：对$n=1,2,\cdots ,$
$$\begin{gathered} a_{ij}^{(n+1)}=\frac{{\sum }_{t=1}^{T-1}{\xi }_t(i,j)}{{\sum }_{t=1}^{T-1}{\gamma }_t(i)} \\ {b}_j(k{)}^{(n+1)}=\frac{{\sum }_{t=1,ot=vk}^T{\gamma }_t(j)}{{\sum }_{t=1}^T{\gamma }_t(j)} \\ {\pi }_i^{(n+1)}={\gamma }_1(i) \end{gathered}$$
其中
γ t ( i ) = α t ( i ) β t ( i ) P ( O ∣ λ ) = α t ( i ) β t ( i ) ∑ j = 1 N α t ( j ) β t ( j ) ξ t ( i , j ) = α t ( i ) a i j b j ( o t + 1 ) β t + 1 ( j ) ∑ i = 1 N ∑ j = 1 N α t ( i ) a i j b j ( o t + 1 ) β t + 1 ( j )

γt​(i)=P(O∣λ)αt​(i)βt​(i)​=∑j=1N​αt​(j)βt​(j)αt​(i)βt​(i)​ξt​(i,j)=∑i=1N​∑j=1N​αt​(i)aij​bj​(ot+1​)βt+1​(j)αt​(i)aij​bj​(ot+1​)βt+1​(j)​​

预测算法

目标：计算$\arg \max P(I\mid O,\lambda )$

1.近似算法

$$i_t^{\ast }=\arg \underset{1\le i\le N}{\max }\left[{\gamma }_t(i)\right],t=1,2,\dots ,T$$

其中${\gamma }_t(\mathrm{i})=P\left(i_t=q_i\mid O,\lambda \right)$

当$t=1$:
i 1 ∗ = arg ⁡ max ⁡ 1 ≤ j ≤ N P ( i 1 = q j ∣ O , λ ) = arg ⁡ max ⁡ 1 ≤ j ≤ N { P ( i 1 = q j ∣ O , λ ) ⋯ ( i 1 = q N ∣ O , λ ) } i_{1}^{*}=\arg \max _{1 \leq j \leq N} P\left(i_{1}=q_{j} \mid O, \lambda\right)=\arg \max _{1 \leq j \leq N}\left\{

\right\} i1∗​=arg1≤j≤Nmax​P(i1​=qj​∣O,λ)=arg1≤j≤Nmax​⎩ ⎨ ⎧​P(i1​=qj​∣O,λ)⋯(i1​=qN​∣O,λ)​⎭ ⎬ ⎫​
当$t=2$
$$i_2^{\ast }=\arg \underset{1\le j\le N}{\max }P\left(i_2=q_j\mid O,\lambda \right)$$
最后
$$I^{\ast }=\left(i_1^{\ast },\dots ,i_T^{\ast }\right)$$

2.维特比算法

输入：模型$\lambda =(A,B,\pi )$观测数据$O=(o_1,o_2,\cdots ,o_T)$

输出：最优路径$I^{\ast }=\left(i_1^{\ast },\dots ,i_T^{\ast }\right)$

(1)初始化
δ t ( i ) = π i b i ( o 1 ) , i = 1 , 2 , … , N Ψ t ( i ) = 0 , i = 1 , 2 , … , N

δt​(i)=πi​bi​(o1​),i=1,2,…,NΨt​(i)=0,i=1,2,…,N​
(2)递推

对于$t=2,3,\cdots ,T$
δ t ( i ) = max ⁡ 1 ≤ j ≤ N [ δ t − 1 ( j ) a i j ] b i ( o t ) , i = 1 , 2 , … , N Ψ t ( i ) = arg ⁡ max ⁡ 1 ≤ j ≤ N [ δ t − 1 ( j ) a i j ] , i = 1 , 2 , … , N

δt​(i)=1≤j≤Nmax​[δt−1​(j)aij​]bi​(ot​),i=1,2,…,NΨt​(i)=arg1≤j≤Nmax​[δt−1​(j)aij​],i=1,2,…,N​
(3)终止
P ∗ = max ⁡ 1 ≤ i ≤ N δ T ( i ) i T ∗ = arg ⁡ max ⁡ 1 ≤ i ≤ N [ δ T ( i ) ]

P∗=max1≤i≤NδT(i)iT∗=arg⁡max1≤i≤N[δT(i)]" role="presentation" style="position: relative;">P∗=max1≤i≤NδT(i)i∗T=argmax1≤i≤N[δT(i)]$$\begin{array}{c}{P}^{\ast }=\underset{1\le i\le N}{max}{\delta }_T(i)\\ i_T^{\ast }=\arg \underset{1\le i\le N}{max}\left[{\delta }_T(i)\right]\end{array}$$

P∗=1≤i≤Nmax​δT​(i)iT∗​=arg1≤i≤Nmax​[δT​(i)]​
(4)最优路径回溯

对于$t=T-1,T-2,\cdots ,1$
$$i_t^{\ast }={\Psi }_{t+1}\left(i_{t+1}^{\ast }\right)$$
求得最优路径$I^{\ast }=\left(i_1^{\ast },i_2^{\ast },\dots ,i_T^{\ast }\right)$

总结

1. 状态链、观测链、状态转移矩阵、观测转移矩阵
2. 隐马尔可夫两种假设：齐次马尔可夫性、观测独立假设
3. 概率计算法：直接计算法、前向算法、后向算法
4. 学习算法：EM算法
5. 预测算法：近似算法、维特比算法

10.2 维特比算法(Viterbi Algorithm)

如上一节所示，我们在初始化中引入了新变量
$${\delta }_t(j)=\underset{i_1,i_2,\dots ,i_{t-1}}{\max }\mathrm{P}\left(i_1,\dots ,i_{t-1},i_t=j,o_t,\dots ,o_1\mid \lambda \right),i=1,2,\dots ,N$$
推导：
δ t + 1 ( i ) = max ⁡ i 1 , i 2 , … , i t P ( i 1 , … , i t , i t + 1 = i , O t + 1 , … , o 1 ∣ λ ) = max ⁡ 1 ≤ j ≤ N δ t ( j ) P ( o t + 1 ∣ i t + 1 = q i ) P ( i t + 1 = q i ∣ i t = q j ) = max ⁡ 1 ≤ j ≤ N [ δ t ( j ) a j i ] b i ( o t + 1 ) i = 1 , 2 , … , N ; t = 1 , 2 , … , T − 1

δt+1​(i)​=i1​,i2​,…,itmax​P(i1​,…,it​,it+1​=i,Ot+1​,…,o1​∣λ)=1≤j≤Nmax​δt​(j)P(ot+1​∣it+1​=qi​)P(it+1​=qi​∣it​=qj​)=1≤j≤Nmax​[δt​(j)aji​]bi​(ot+1​)i=1,2,…,N;t=1,2,…,T−1​
维特比算法本质是用动态规划来解决隐马尔科夫模型的预测问题