Hidden Markov Model (HMM)

隐马可夫模型（HMM）描述隐藏的马可夫链随机生成观测序列的过程，属于生成模型。 HMM在语音识别、自然语言处理、生物信息、模式识别等领域由广泛应用。

1. HMM的定义

隐马可夫模型是关于时序的概率模型， 描述由一个隐藏的马可夫链随机生成不可观测的状态，再由各个状态生成一个观测，从而产生观测随机序列的过程。

简而言之，隐马可夫链随机成状态序列（state sequence），而每个状态生成观测，产生观测序列（observation sequence）。序列的一个位置可以看作一个时刻。

令$Q$ 表示所有可能状态的集合：$Q = { q_1, q_2, \cdots, q_N }$;
令$V$ 表示所有可能的观测集合：$V = {v_1, v_2, \cdots, v_M }$;
令$I$ 表示长度为T的状态序列： $I = (i_1, i_2, \cdots, i_T)$;
令$O$ 表示对应的是观测序列： $O = (o_1, o_2, \cdots, o_T)$.

令$A$是转移概率矩阵：

$$A = [a_{ij}]_{N \times N}$$

其中，

$$a_{ij} = P(i_{t+1} = q_j | i_t = q_j), i=1,2, \cdots, N; j = 1,2, \cdots, N$$

是在时刻$t$处于状态$q_i$的条件下生成观测$t +1$转移到状态$q_j$的概率。

令$B$是观测概率矩阵：

$$B = [b_j(k)]_{N \times M}$$

其中，

$$b_j(k) = P(o_t = v_k | i_t = q_j), k=1,2,\cdots, M; j=1,2,\cdots, N$$

是在时刻$t$处于状态$q_j$的条件下生成观测$v_k$ 的概率。

令$\pi$是初始状态概率向量：

$$\pi = (\pi_i)$$

其中，

$$\pi_{i} = P(i_1 = q_i),i=1,2,\cdots, N$$

是时刻t=1处于状态$q_i$的概率.

隐马可夫模型$\lambda$由$\pi$， $A$，$B$决定。

$$\lambda = (A, B, \pi)$$

其中，$\pi$和$A$决定状态序列，$B$决定观测序列。

隐马可夫模型的两个基本假设

1. 齐次马可夫性

• 隐马可夫链在任意时刻t的状态前一时刻状态，与其他时刻的隐状态和观测无关， 也与时刻t无关：

$$P(i_t | i_{t-1}, O_{t-1}, \cdots, i_1, o_1) = P(i_t | i_{t-1}), t = 1,2,\cdots,T$$

2. 观测独立性

• 任意时刻的观测只依赖改时刻的马可夫链状态，与其他观测和状态无关:

  $$P(o_t | i_{T}, O_{T}, i_{T-1}, o_{T-1}\cdots, i_{t+1}, O_{t+1}, i_{t-1}, O_{t-1}, i_1, o_1) = P(o_t | i_{t})$$

2. HMM的3个基本问题

概率计算：给定模型$\lambda = (A, B, \pi)$和观测序列 $O = (o_1, o_2, \cdots, o_T)$， 求概率$P(O | \lambda)$

学习: 已知观测序列$O = (o_1, o_2, \cdots, o_T)$，估计模型参数$\lambda = (A, B, \pi)$， 使概率$P(O \vert \lambda)$最大（用极大似然估计）。

预测：给定模型$\lambda = (A, B, \pi)$和观测序列 $O = (o_1, o_2, \cdots, o_T)$，求条件概率$P(I | O)$最大的状态序列 $I = (i_1, i_2, \cdots, i_T)$.

2.1 概率计算前向（forward）和后向（backward）算法

2.1.1 前向算法

给定模型$\lambda$，当时刻$t$时，状态为$q_i$，部分观测序列为$o_1, o_2, \cdots, o_t$，记：

$$\alpha_{t}(i) = P(o_1, o_2, \cdots, o_t, i_t = q_i | \lambda)$$

输入： 隐马可夫模型 $\lambda$， 观测序列$O$;
输出： 观测序列概率$P(O | \lambda)$

（1）初值

$$ \alpha_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right), \quad i=1,2, \cdots, N $$

（2）递推 对 $t = 1,2, \cdots, T-1,$

$$ \alpha_{t+1}(i)=\left[\sum_{j=1}^{N} \alpha_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right), \quad i=1,2, \cdots, N $$

（3）终止

$$ P(O | \lambda)=\sum_{i=1}^{N} \alpha_{T}(i) $$

2.1.2 后向算法

给定模型$\lambda$，当时刻$t$时，状态为$q_i$，部分观测序列为$o_1, o_2, \cdots, o_t$，记：

$$\beta_{t}(i) = P(o_{t+1}, o_{t+2}, \cdots, o_T | i_t = q_i, \lambda)$$

输入： 隐马可夫模型 $\lambda$， 观测序列$O$;
输出： 观测序列概率$P(O | \lambda)$

（1）初始 令最终时刻所有状态$q_i$

$$\beta_T(i) = 1, i=1,2,\cdots, N$$

（2）递推 对$t=T-1, T-2, \cdots, 1$

$$ \beta_{t}(i)=\sum_{j=1}^{N} a_{i j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j), \quad i=1,2, \cdots, N $$

（3）终止

$$ P(O | \lambda)=\sum_{i=1}^{N} \pi_{i} b_{i}\left(o_{1}\right) \beta_{1}(i) $$

利用前后向概率定义，可以将观测序列概率$P(O \vert \lambda)$统一写成

$$ P(O | \lambda)=\sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{t}(i) a_{i j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j), \quad t=1,2, \cdots, T-1 $$

2.2 学习问题的EM算法

实质上求一个隐变量的概率模型的参数估计：

$$ P(O | \lambda)=\sum_{I} P(O | I, \lambda) P(I | \lambda) $$

参数估计由EM算法实现: (待续)

输入：观测数据$O = (o_1, o_2, \cdots, o_T)$;
输出：隐马可夫模型参数

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

（2）递推
对$n=1,2, \cdots,$, 有

$$ a_{i j}^{(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, o_{t}=v_{k}}^{T} \gamma_{t}(j)}{\sum_{t=1}^{T} \gamma_{t}(j)} $$

$$ \pi_{i}^{(n+1)}=\gamma_{1}(i) $$

其中，时刻$t$处于$q_i$，且时刻$t+1$处于状态$q_j$的概率, 记

$$ \xi_{t}(i, j)=P\left(i_{t}=q_{i}, i_{t+1}=q_{j} | O, \lambda\right) $$

那么

$$ \xi_{t}(i, j)=\frac{P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)}{P(O | \lambda)}=\frac{P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)}{\sum_{i=1}^{N} \sum_{j=1}^{N} P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)} $$

和时刻$t$处于$q_i$的概率， 有

$$ \gamma_{t}(i)=P\left(i_{t}=q_{i} | O, \lambda\right)=\frac{P\left(i_{t}=q_{i}, O | \lambda\right)}{P(O | \lambda)} $$

（3）终止

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

2.3 预测算法

包括近似算法和维特比算法（Viterbi algorithm）

2.3.1 近似算法

在每个时刻$t$， 选择在该时刻最可能出现的状态 $i^*_t$从而得到一个状态序列 $I^* = (i^*_i, i^*_i, \cdots, i^*_T)$，将它最为预测结果。

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

$$ \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_{t}^{*}$是

$$ i_{t}^{*}=\arg \max _{1 \leqslant i \leqslant N}\left[\gamma_{t}(i)\right], \quad t=1,2, \cdots, T $$

从而得到状态序列

$$I^* = (i^*_i, i^*_i, \cdots, i^*_T)$$

缺点： 不能保证预测状态序列整体是最有可能的状态序列，因为预测的状态序列实际可能由不发生的部分。

2.3.2 维特比算法

实质是运用动态规划求概率最大路径，从而解决HMM的预测问题

维特比算法: 只需从时刻$t=1$开始，递推地计算在时刻$t$状态为$q_i$的各条部分路径的最大概率，直至得到时刻$t = T$状态为$i$的各条路径的最大概率。时刻 $t = T$ 的最大概率即为最优路径的概率 $P^\ast$, 最优路径的终结点$i^*_T$ 也同时得到。之后，为了找出最优路径的各个结点，从终结点$i^*_T$开始，由后向前逐步求得结点 $i^*_{T-1}, \cdots, i^*_1$，得到最优路径$I^* = (i^*_i, i^*_i, \cdots, i^*_T)$。

定义在时刻$t$状态$i$的所有单个路径中概率最大值为

$$ \delta_{t}(i)=\max_{i_{1}, i_{2}, \cdots, i_{t-1}} P\left(i_{t}=i, i_{t-1}, \cdots, i_{1}, o_{t}, \cdots, o_{1} | \lambda\right), \quad i=1,2, \cdots, N $$

因此

$$ \begin{aligned} \delta_{t+1}(i) &=\max _{i_{1}, i_{2}, \cdots, i_{t}} P\left(i_{t+1}=i, i_{t}, \cdots, i_{1}, o_{t+1}, \cdots, o_{1} | \lambda\right) \cr &= \max _{1 \leqslant j \leqslant N}\left[\delta_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right), \quad i=1,2, \cdots, N ; \quad t=1,2, \cdots, T-1 \end{aligned} $$

定义在时刻t状态i的所有单个路径中概率最大路径的第$t-1$个节点为

$$ \Psi_{t}(i)=\arg \max _{1 \leqslant j \leqslant N}\left[\delta_{t-1}(j) a_{j i}\right], \quad i=1,2, \cdots, N $$

输入： 隐马可夫模型 $\lambda$， 观测序列$O$;
输出： 最优路径$$I^* = (i^*_i, i^*_i, \cdots, i^*_T)$$

(1) 初始化:

$$ \begin{array}{c} \delta_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right), \quad i=1,2, \cdots, N \cr \Psi_{1}(i)=0, \quad i=1,2, \cdots, N \end{array} $$

(2) 递推:

$$ \begin{array}{c} \delta_{t}(i)=\max _{1 \leqslant j \leqslant N}\left[\delta_{t-1}(j) a_{j i}\right] b_{i}\left(o_{t}\right), \quad i=1,2, \cdots, N \cr \Psi_{t}(i)=\arg \max _{1 \leqslant j \leqslant N}\left[\delta_{t-1}(j) a_{j i}\right], \quad i=1,2, \cdots, N \end{array} $$

(3) 终止

$$ \begin{array}{c} P^* = \max _{1 \leqslant i \leqslant N} \delta_T(i) \cr i^*_T = \arg \max _{1 \leqslant i \leqslant N} [ \delta_T(i)] \end{array} $$

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

$$i^*_t = \Psi_{t+1}(i^*_{t+1})$$

参考： 李航《统计学习方法》