隐马尔可夫模型（HMM）

本文摘抄自《统计学习方法》

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

HMM 的基本概念

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

隐藏的马尔科夫链随机生成的状态的序列，称为状态序列（state sequence）；每个生成一个观测，而由此产生的观测的随机序列，称为观测序列（observation sequence）。序列的每一个位置又可以看作一个时刻。

HMM 由初始概率分布、状态转移概率分布和观测概率分布，HMM 的形式定义如下：

• 设 $Q$ 是所有可能的状态的集合，$V$ 是所有可能的观测的集合： \(Q = \{q_1, q_2, ..., q_N\}, ~~~~ V = \{v_1, v_2, ..., v_M\}\)

  其中，$N$ 是可能的状态数，$M$ 是可能的观测数

• $I$ 是长度为 $T$ 的状态序列，$O$ 是对应的观测序列： \(I = (i_1, i_2, ..., i_T), ~~~~ O = (o_1, o_2, ..., o_T)\)

• $A$ 是状态转移概率矩阵： \(A = [a_{i,j}]_{N \times N} \\ a_{i,j} = P(i_{t+1} = q_j | i_t = q_i),~~~~i = 1, 2, ..., N; j = 1, 2, ..., N\)

  其中，$a_{i,j}$ 是在时刻 $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, ..., M; j = 1, 2, ..., N\)

  其中，$b_j(k)$ 是在时刻 $t$ 处于状态 $q_j$ 的条件下生成观测 $v_k$ 的概率。

• $\pi$ 是初始状态概率向量： \(\pi = (\pi_i) \\ \pi_i = P(i_1 = q_i), ~~~~i = 1, 2, ..., N\)

  其中，$\pi_i$ 是时刻 $t=1$ 处于状态 $q_i$ 的概率。

HMM 由初始状态概率向量 $\pi$ 、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。符号表示为： \(\lambda = (A, B, \pi)\) $A, B, \pi$ 称为 HMM 的三要素。

由定义可知，HMM 作了两个基本假设：

• 齐次马尔可夫性假设：当前时刻的状态值，仅依赖于前一时刻的状态值，而不依赖于更早时刻的状态值（马尔可夫性），也与时刻无关（齐次性；即所有时刻共享一个状态转移矩阵）。
• 观测独立性假设：当前时刻的观察值，仅依赖于当前时刻的状态值。

HMM 的三个基本问题:

• 概率计算问题：给定模型 $\lambda = (A, B, \pi)$ 和观测序列 $O = (o_1, o_2, …, o_T)$，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O

  \lambda)$

• 学习问题：已知观测序列 $O=(o_1, o_2, …, o_T)$，估计模型 $\lambda = (A, B, \pi)$ 参数，使得在该模型下观测序列概率 $P(O

  \lambda)$ 最大，即用极大似然估计的方法估计参数

• 预测问题：也称为解码问题。已知模型 $\lambda=(A, B, \pi)$ 和观测序列 $O=(o_1, o_2, …, o_T)$，求对给定观测序列条件概率 $P(I

  O)$ 最大的状态序列 $I = (i_1, i_2, …, i_T)$，即给定观测序列，求最有可能的对应的状态序列

概率计算算法

给定模型 $\lambda = (A, B, \pi)$ 和观测序列 $O = (o_1, o_2, …, o_T)$，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O

\lambda)$

直接计算法（实际不可行）

通过列举所有可能的长度为 $T$ 的状态序列 $I=(i_1, i_2, …, i_T)$，求各个状态序列 $I$ 与观测序列 $O=(o_1, o_2, …, o_T)$ 的联合概率 $P(O,I

\lambda)$，然后对所有可能的状态序列求和，得到 $P(O

\lambda)$

状态序列 $I=(i_1, i_2, …, i_T)$ 的概率是： \(P(I|\lambda) = \pi_{i_1}a_{i_1i_2}a_{i_2i_3}...a_{i_{T-1}i_{T}}\) 对固定的状态序列 $I=(i_1, i_2, …, i_T)$，观测序列 $O=(o_1, o_2, …, o_T)$ 的概率是： \(P(O|I,\lambda) = b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T)\) $O$ 和 $I$ 同时出现的联合概率是： \(\begin{align} P(O,I|\lambda) &= P(O|I,\lambda)P(I|\lambda) \\ & = \pi_{i_1} b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_{T}}b_{i_T}(o_T) \end{align}\) 然后对所有可能的状态序列 $I$ 求和，得到观测序列 $O$ 的概率 $P(O|\lambda)$，即： \(\begin{align} P(O|\lambda) &= \sum_I P(O|I,\lambda)P(I|\lambda) \\ & = \sum_{i_1,i_2, ..., i_T} \pi_{i_1} b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_{T}}b_{i_T}(o_T) \end{align}\) 但是上式计算量大（$O(TN^T)$），故可不行

前向算法

前向概率：给定 HMM $\lambda$，定义到时刻 $t$ 部分观测序列为 $o_1, o_2, …, o_t$ 且状态为 $q_i$ 的概率为前向概率，记作： \(\alpha_t(i) = P(o_1, o_2, ..., o_t, i_t = q_i|\lambda)\)

输入：HMM $\lambda$，观测序列 $O$ 输出：观测序列概率 $P(O|\lambda)$

1. 初值

\[\alpha_1(i) = \pi_ib_i(o_1), ~~~~i = 1, 2, ..., N\]

1. 递推，对 $t = 1, 2, …, T-1$ \(\alpha_{t+1}(i)=[\sum_{j=1}^N \alpha_t(j)a_{ji}]b_i(o_{t+1}), ~~~~i = 1, 2, ..., N\)

2. 终止 \(p(O|\lambda) = \sum_{i=1}^N \alpha_T(i)\)

后向算法

给定 HMM $\lambda$，定义在时刻 $t$ 状态为 $q_i$ 的条件下，从 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1}, o_{t+2}, … , o_T$ 的概率为后向概率，记作： \(\beta_t(i) = P(o_{t+1}, o_{t+2}, ..., o_T|i_t=q_i, \lambda)\)

输入：HMM $\lambda$，观测序列 $O$ 输出：观测序列概率 $P(O|\lambda)$

1. 初值 \(\beta_T(i) = 1, ~~~~i = 1, 2, ..., N\)

2. 递推，对 $t = T-1, T-2, …, 1$ \(\beta_{t}(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j), ~~~~i = 1, 2, ..., N\)
3. 终止

\[p(O|\lambda) = \sum_{i=1}^N \pi_ib_i(o_1)\beta_1(i)\]

一些概率与期望的计算

todo

学习算法

监督学习方法

todo

EM 算法

todo

预测算法

已知模型 $\lambda=(A, B, \pi)$ 和观测序列 $O=(o_1, o_2, …, o_T)$，求对给定观测序列条件概率 $P(I

O)$ 最大的状态序列 $I = (i_1, i_2, …, i_T)$，即给定观测序列，求最有可能的对应的状态序列

近似算法

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

给定 HMM $\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}[\gamma_t(i)], ~~~~t= 1, 2, ..., T\) 从而得到状态序列 $I^=(i_1^,i_2^, …, i_T^*)$

优点是计算简单，缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列有可能有实际上不发生的部分（状态转移概率为0，即对某些 $i, j$ 有 $a_{ij} = 0$）。

维特比算法（Viterbi algorithm）

通俗解释 Viterbi algorithm

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

根据动态规划原理，最优路径具有这样特性：如果最优路径在时刻 $t$ 通过结点 $i_t^$，那么这一路径从结点 $i_t^$ 到终点 $i_T^$ 的部分路径，对于从 $i_t^$ 到 $i_T^$ 的所有可能的部分路径来说，必然是最优的。所以，我们只需从时刻 $t=1$ 开始，递推的计算在时刻 $t$ 状态为 $i$ 的各条部分路径的最大概率，直至得到时刻 $t=T$ 状态为 $i$ 的各条路径的最大概率。 时刻 $t=T$ 状态的最大概率即为最优路径的概率 $P^$，最优路径的终结点 $i_T^$ 也同时得到。之后，为了找出最优路径的各个结点，从终结点 $i_T^$ 开始，由后往前逐步求得结点 $i_{T-1}^, …, i_1^$，得到最优路径 $I^* = (i_1^, i_2^, …, i_T^*)$。

首先导入两个变量 $\delta$ 和 $\psi$

定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1, i_2, …, i_t)$ 中概率最大值为： \(\delta_t(i) = \max_{i_1, i_2, ..., i_{t-1}} P(i_t=i, i_{t-1}, ..., i_1, o_t, ..., o_1|\lambda), ~~~~i = 1, 2, ..., N\) 由定义可得变量 $\delta$ 的递推公式： \(\begin{align} \delta_{t+1}(i) &= \max_{i_1, i_2, ..., i_t} P(i_{t+1}=i, i_t, ..., i_1, o_{t+1}, ..., o_1|\lambda), ~~~~i=1,2,...,N \\ &= \max_{1 \leqslant j \leqslant N}[\delta_t(j)a_{ji}]b_i(o_{t+1}), ~~~~i=1,2,...,N;t=1,2,...,T-1 \end{align}\) 定义在时刻 $t$ 的状态为 $i$ 的所有单个路径 $(i_1, i_2, …, i_{t-1}, i)$ 中概率最大的路径的第 $t-1$ 个结点为 \(\psi_t(i) = \arg \max_{1 \leqslant j \leqslant N}[\delta_{t-1}(j)a_{ji}], ~~~~i=1,2,...,N\)

输入：模型 $\lambda=(A,B,\pi)$ 和观测 $O=(o_1, o_2, …, o_T)$ 输出：最优路径 $I^=(i_1^,i_2^,…,i_T^)$

1. 初始化 \(\delta_1(i) = \pi_ib_i(o_1), ~~~~i = 1,2,...,N \\ \psi_1(i) = 0, ~~~~i = 1, 2, ..., N\)

2. 递推，对 $t=2,3,…,T$ \(\delta_t(i) = \max_{1 \leqslant j \leqslant N}[\delta_{t-1}(j)a_{ji}]b_i(o_t), ~~~~i = 1,2,...,N \\ \psi_t(i) = \arg \max_{1 \leqslant j \leqslant N}[\delta_{t-1}(j)a_{ji}], ~~~~i = 1, 2, ..., N\)

3. 终止 \(p^* = \max_{1 \leqslant i \leqslant N} \delta_T(i) \\ i_T^* = \arg \max_{1 \leqslant i \leqslant N} [\delta_T(i)]\)

4. 最优路径回溯，对 $t=T-1,T-2, …, 1$ \(i_t^* = \psi_{t+1}(i_{t+1}^*)\) 求得最优路径 $I^* = (i_1^, i_2^, …, i_T^*)$