隐马尔可夫模型

《统计学习方法》笔记 第10章

Posted by Cheereus on February 19, 2020

第10章 隐马尔可夫模型

隐马尔可夫模型(hidden Markov model,HMM)是可用于标注问题的统计学习模型,描述由隐藏的马尔科夫链随机生成观测序列的过程,属于生成模型。

10.1 隐马尔可夫模型的基本概念

10.1.1 隐马尔可夫模型的定义

隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列,称为状态序列(state sequence);每个状态生成一个观测,而由此产生的观测的随机序列,称为观测序列(observation sequence),序列的每一个位置又可以看作是一个时刻。

马尔可夫模型由初始状态概率向量 $\pi$、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。$\pi$ 和 $A$ 决定状态序列,$B$ 决定观测序列。因此,隐马尔可夫模型 $\lambda$ 可以用三元符号表示,即

\[\lambda = (A,B,\pi)\]

$A,B,\pi$ 称为隐马尔可夫模型的三要素。

从定义可知,隐马尔可夫模型作了两个基本假设:

(1) 齐次马尔可夫性假设,即假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态,与其他时刻的状态及观测无关,也与时刻 $t$ 无关。

(2) 观测独立性假设,即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态,与其他观测及状态无关。

10.1.2 观测序列的生成过程

输入:隐马尔可夫模型 $\lambda = (A,B,\pi)$,观测序列长度 $T$;

输出:观测序列 $O=(o_1,o_2,\cdots,o_T)$。

(1) 按照初始状态分布 $\pi$ 产生状态 $i_1$;

(2) 令 $t=1$;

(3) 按照状态 $i_t$ 的观测概率分布 $b_{i_t}(k)$ 生成 $o_t$;

(4) 按照状态 $i_t$ 的状态转移概率分布 $\{a_{i_ti_{t+1} }\}$ 产生状态 $i_{t+1},i_{i+1}=1,2,\cdots,N$;

(5) 令 $t=t+1$;如果 $t<T$,转步 (3);否则,终止。

10.2 概率计算算法

10.2.1 直接计算法

给定模型 $\lambda = (A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$,计算观测序列 $Q$ 出现的概率 $P(O\vert\lambda)$。最直接的方法是按概率公式直接计算。通过列举所有可能的长度为 $T$ 的状态序列 $I=(i_1,i_2,\cdots,i_T)$,求各个状态序列 $I$ 与观测序列 $O=(o_1,o_2,\cdots,o_T)$ 的联合概率 $P(O,I\vert\lambda)$,然后对所有可能的状态序列求和,得到 $P(O\vert\lambda)$。

但这种方式计算量很大,是 $Q(TN^T)$ 阶的,只是概念上可行而计算上不可行。

10.2.2 前向算法

给定隐马尔可夫模型 $\lambda$,定义到时刻 $t$ 部分观测序列为 $o_1,o_2,\cdots,o_t$ 且状态为 $q_i$ 的概率为前向概率,记作

\[\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i\vert\lambda)\]

可以递推地求得前向概率 $\alpha_t(i)$ 及观测序列概率 $P(O\lambda)$。

观测序列概率的前向算法

输入:隐马尔可夫模型 $\lambda$,观测序列 $O$;

输出:观测序列概率 $P(O\lambda)$。

(1) 初值

\[\alpha_1(i)=\pi_i b_i(o_1),i=1,2,\cdots,N\]

(2) 递推,对 $t=1,2,\cdots,T-1$,

\[\alpha_{t+1}(i)=\bigg[\sum_{j=1}^N\alpha_t(j)a_{ji}\bigg]b_i(o_{t+1}),i=1,2,\cdots,N\]

(3) 终止

\[P(O\lambda)=\sum_{i=1}^N\alpha_T(i)\]

10.2.3 后向算法

给定隐马尔可夫模型 $\lambda$,定义在时刻 $t$ 状态为 $q_i$ 的条件下,从 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1},o_{t+2},\cdots,o_T$ 且概率为后向概率,记作

\[\beta_t(i)=P(o_{t+1},o_{t+2},\cdots,o_T\vert i_t=q_i,\lambda)\]

可以递推地求得前向概率 $\beta_t(i)$ 及观测序列概率 $P(O\lambda)$。

观测序列概率的后向算法

输入:隐马尔可夫模型 $\lambda$,观测序列 $O$;

输出:观测序列概率 $P(O\lambda)$。

(1)

\[\beta_1(i)=1,i=1,2,\cdots,N\]

(2) 对 $t=T-1,T-2,\cdots,1$

\[\beta_t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,\cdots,N\]

(3)

\[P(O\lambda)=\sum_{i=1}^N\pi_i b_i(o_1)\beta_1(i)\]

10.3 学习算法

10.3.1 监督学习方法

设样本中时刻 $t$ 处于状态 $i$ 时刻 $t+1$ 转移到状态 $j$ 的频数为 $A_{ij}$,那么状态转移概率的 $a_{ij}$ 的估计是

\[\hat{a}_{ij}=\frac{A_{ij} }{\displaystyle\sum_{j=1}^N A_{ij} },j=1,2,\cdots,N\]

设样本中状态为 $j$ 并观测为 $k$ 的频数是 $B_{jk}$,那么状态为 $j$ 观测为 $k$ 的概率 $b_j(k)$ 的估计是

\[\hat{b}_j(k)=\frac{B_{jk} }{\displaystyle\sum_{k=1}^M B_{jk} },j=1,2,\cdots,N;k=1,2,\cdots,M\]

初始状态概率 $\pi_i$ 的估计 $\hat{\pi}_i$ 为 $S$ 个样本中初始状态为 $q_i$ 的概率。

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

10.3.2 Baum-Welch 算法

输入:观测数据 $O=(o_1,o_2,\cdots,o_T)$;

输出:隐马尔可夫模型参数。

(1) 初始化。对 $n=0$,选取 $a_{ij}^{(0)},b_{j}^{(0)},\pi_{i}^{(0)}$,得到模型 $\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})$。

(2) 递推。对 $n=1,2,\cdots$,

\[a_{ij}^{(n+1)}=\frac{\displaystyle\sum_{t=1}^{T-1}\epsilon_t(i,j)}{\displaystyle\sum_{t=1}^{T-1}\gamma_t(i)}\] \[b_{j}^{(n+1)}=\frac{\displaystyle\sum_{t=1,o_t=v_k}^{T}\gamma_t(i)}{\displaystyle\sum_{t=1}^{T}\gamma_t(i)}\] \[\pi_i^{(n+1)}=\gamma_1(i)\]

右端各值按观测 $O=(o_1,o_2,\cdots,o_T)$ 和模型 $\lambda^{(n)}=(A^{(n)},B^{(n)},\pi^{(n)})$ 计算。

(3) 终止。得到模型参数 $\lambda^{(n+1)}=(A^{(n+1)},B^{(n+1)},\pi^{(n+1)})$

10.4 预测算法

10.4.1 近似算法

给定隐马尔可夫模型 $\lambda$ 和观测序列 $O$,在时刻 $t$ 处于状态 $q_i$ 的概率 $\gamma_t(i)$ 是

\[\gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{P(O\vert\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\displaystyle\sum_{j=1}^N\alpha_t(j)\beta_t(j)}\]

在每一时刻 $t$ 最有可能的状态 $i_t^*$ 是

\[i_t^*=\arg\underset{1\leq i\leq N}{max}[\gamma_t(i)],i=1,2,\cdots,T\]

从而得到状态序列 $I^=(i_1^,i_2^,\cdots,i_T^)$。

近似算法的优点是计算简单,其缺点是不能保证预测的状态序列整体是最有可能的状态序列,因为预测的状态序列可能有实际不发生的部分。尽管如此,近似算法仍然是有用的。

10.4.2 维特比算法

输入:模型 $\lambda = (A,B,\pi)$ 和观测 $O=(o_1,o_2,\cdots,o_T)$;

输出:最优路径 $I^=(i_1^,i_2^,\cdots,i_T^)$。

(1) 初始化

\[\delta_1(i)=\pi_i b_i(o_1),i=1,2,\cdots,N\] \[\Psi_1(i)=0,i=1,2,\cdots,N\]

(2) 递推。对 $t=2,3,\cdots,T$

\[\delta_1(i)=\underset{1\leq j\leq N}{max}[\delta_{t-1}(j)a_{ji}]b_i(o_t),i=1,2,\cdots,N\] \[\Psi_t(i)=\arg\underset{1\leq j\leq N}{max}[\delta_{t-1}(j)a_{ji}],i=1,2,\cdots,N\]

(3) 终止

\[P^*=\underset{1\leq j\leq N}{max}\delta_T(i)\] \[i_T^*=\arg\underset{1\leq j\leq N}{max}[\delta_T(i)]\]

(4) 最优路径回溯。对 $t=T-1,T-2,\cdots,1$

\[i_t^*=\Psi_{t+1}(i_{t+1}^*)\]

求得最优路径 $I^=(i_1^,i_2^,\cdots,i_T^)$。

第10章完结


如果对您有帮助,欢迎赞助一杯咖啡!