隐马尔科夫模型

隐马尔科夫模型的定义

隐马尔科夫模型有如下两个假设：任意状态只依赖于前一时刻状态和任意时刻的观测只依赖于该时刻的马尔科夫链的状态。
设 $Q$ 是所有可能的状态的集合，$V$是所有可能的观测的集合：

$$Q =\{q_1, q_2, \dots, q_N\}, \quad V = \{v_1, v_2, \dots, v_M\}$$

其中，$N$ 是可能的状态数，$M$ 是可能的观测数。
$I$ 是长度为 $T$ 的状态序列，$O$ 是对应的观测序列：

$$I = (i_1, i_2, \dots, i_T), \quad O =(o_1, o_2, \dots, o_T)$$

$A$ 是状态转移概率矩阵：

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

其中，

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

$B$ 是观测概率矩阵：

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

其中，

$$b_j(k) = P(o_t = v_k | i_t = q_j), \quad k = 1, 2, \dots, M; \quad j = 1, 2, \dots, N \tag{4}$$

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

$$\pi = (\pi_i) \tag{5}$$

其中，

$$\pi_i = P(i_1 = q_i), \quad i = 1, 2, \dots, N \tag{6}$$

综上，可以将隐马尔科夫模型用三元符号表示，即

$$\lambda = (A, B, \pi) \tag{7}$$

隐马尔科夫模型的3个基本问题

概率计算问题

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

前向算法

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

（1）初值

$$\alpha_1(i) = \pi_i b_i(o_1), \quad i = 1, 2, \dots, N \tag{8}$$

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

$$\alpha_{t + 1}(i) = \left[\sum_{j = 1}^{N} \alpha_t(j) a_{ji}\right]b_i(o_{t + 1}), \quad i = 1, 2, \dots, N \tag{9}$$

（3）终止

$$P(O | \lambda) = \sum_{i = 1}^{N} \alpha_T(i) \tag{10}$$

这个算法中的 $\alpha$ 可以用一个矩阵表示，其中下标表示行号，括号内表示列号

$$\alpha = \begin{bmatrix} \alpha_1(1) & \alpha_1(2) & \alpha_1(3) & \cdots & \alpha_1(N) \\\\[10pt] \alpha_2(1) & \alpha_2(2) & \alpha_2(3) & \cdots & \alpha_2(N) \\\\[10pt] \vdots & \vdots & \vdots & \ddots & \vdots \\\\[10pt] \alpha_T(1) & \alpha_T(2) & \alpha_T(3) & \cdots & \alpha_T(N) \end{bmatrix} \tag{11}$$

每次迭代就是在一次计算行内容。

后向算法

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

（1）

$$\beta_T(i) = 1, \quad i = 1, 2, \dots, N \tag{12}$$

（2）对 $t = T - 1, T - 2, \dots, 1$

$$\beta_t(i) = \sum_{j = 1}^{N} a_{ij} b_j(o_{t + 1})\beta_{t + 1}(j) \tag{13}$$

（3）

$$P(O | \lambda) = \sum_{i = 1}^{N} \pi_i b_i(o_1) \beta_1(i) \tag{14}$$

$\beta$ 矩阵

$$\beta = \begin{bmatrix} \beta_1(1) & \beta_1(2) & \beta_1(3) & \cdots & \beta_1(N) \\\\[10pt] \beta_2(1) & \beta_2(2) & \beta_2(3) & \cdots & \beta_2(N) \\\\[10pt] \vdots & \vdots & \vdots & \ddots & \vdots \\\\[10pt] \beta_T(1) & \beta_T(2) & \beta_T(3) & \cdots & \beta_T(N) \end{bmatrix} \tag{15}$$

一些概率与期望值的计算

单个状态的计算公式

给定模型 $\lambda$ 和观测 $O$，在时刻 $t$ 处于状态 $q_i$ 的概率。记

$$\gamma_t(i) = P(i_t = q_i |O, \lambda) \tag{16}$$

可以通过前向后向概率计算：

$$\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) \alpha_t(j)} \tag{17}$$

两个状态的计算公式

给定模型 $\lambda$ 和观测 $O$，在时刻 $t$ 处于状态 $q_i$，在时刻 $t + 1$ 处于 $q_j$ 的概率。记

$$\xi_t(i, j) = \frac{\alpha_t(i)a_{ij}b_j(o_{t + 1})\beta_{t + 1}(j)}{\sum_{i = 1}^{N} \sum_{j = 1}^{N} \alpha_t(i) a_{ij} b_j(o_{t + 1}) \beta_{t + 1}(j)} \tag{18}$$

在观测 $O$ 下状态 $i$ 出现的期望值

$$\sum_{t = 1}^{T} \gamma_t(i) \tag{19}$$

在观测 $O$ 下由状态 $i$ 转移的期望值

$$\sum_{t = 1}^{T - 1} \gamma_t(i) \tag{20}$$

在观测 $O$ 下由状态 $i$ 转移到状态 $j$ 的期望值

$$\sum_{t = 1}^{T - 1} \xi_t(i, j) \tag{21}$$

学习算法

前文的内容是都和概率计算有关，那如何根据训练集训练一个隐马尔科夫模型模型呢？

监督学习方法

如果已给训练数据集包含 $S$ 个长度相同的观测序列和对应的状态序列，我们可以用极大似然估计法来估计参数。分别的有：

$$\begin{align*} \hat{a_{ij}} &= \frac{A_{ij}}{\sum_{j = 1}^{N} A_{ij}}, \quad i = 1, 2, \dots, N; \quad j = 1, 2, \dots, N \tag{22} \\[10pt] \hat{b_{j}}(k) &= \frac{B_{jk}}{\sum_{k = 1}^{M} B_{jk}}, \quad j = 1, 2, \dots, N; \quad k = 1, 2, \dots, M \tag{23} \\[10pt] \hat{\pi_{i}} &= \frac{\sum \text{初始状态为$q_i$} }{S} \tag{24} \end{align*}$$

其中 $A_{ij}$ 表示在训练数据中，从状态 $q_i$ 转移到状态 $q_j$ 的次数总和。$B_{jk}$ 表示在状态 $q_j$ 下，观测到符号 $v_k$ 的次数总和。

Baum-Welch 算法

假定训练数据只包含 $S$ 个长度为 $T$ 的观测序列 $\{O_1, O_2, \dots, O_S\}$，我们将观测序列数据看作观测数据 $O$，状态序列数据看做不可观测的隐数据 $I$，那么存在如下概率模型

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

实际上，这个模型的参数学习可由 EM 算法实现。

（1）确定完全数据的对数似然函数。完全数据是$(O, I) = (o_1, o_2, \dots, o_T, i_1, i_2, \dots, i_T)$。

$$\log P(O, T |\lambda) \tag{26}$$

（2）E步

$$Q(\lambda, \bar{\lambda}) = \sum_{I} \log P(O, I |\lambda) P(O, I |\bar{\lambda}) \tag{27}$$

其中 $\bar{\lambda}$ 是当前模型参数的估计值，$\lambda$ 是要极大化的模型参数。

$$P(O, I |\lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2) \cdots a_{i_{T-1}i_{T}}b_{i_{T}}(o_T) \tag{28}$$

于是，函数 $Q$ 可以写成：

$$\begin{align*} Q(\lambda, \bar{\lambda}) = &\sum_{I} \log \pi_{i_1} P(O, I |\bar{\lambda}) + \sum_{I} \left(\sum_{t = 1}^{T - 1} \log a_{i_t i_{t + 1}} \right) P(O, I |\bar{\lambda}) + \\[10pt] &\sum_{I} \left(\sum_{t = 1}^{T} \log b_{i_t}(o_t) \right) P(O, I |\bar{\lambda}) \end{align*}$$

算法步骤

（1）初始化。对 $n = 0$，随机初始化 $\lambda^{(0)}$。
（2）递推。对 $n = 1, 2, \dots$，

$$\begin{align*} \alpha_{ij}^{(n + 1)} &= \frac{\sum_{t = 1}^{T - 1} \xi_t(i, j)}{\sum_{t = 1}^{T - 1} \gamma_t(i)} \\[10pt] b_{j}(k)^{(n + 1)} &= \frac{\sum_{t = 1, o_t = v_k}^{T} \gamma_t(j)}{\sum_{t= 1}^{T} \gamma_t(j)} \\[10pt] \pi_{i}^{(n + 1)} &= \gamma_1(i) \end{align*}$$

预测算法

近似算法

由公式：

$$\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) \alpha_t(j)}$$

知，在每一时刻 $t$ 最有可能的状态 $i_t^{\ast}$ 是

$$i_t^{\ast} = \operatorname{arg} \max_{1 \leq i \leq N} [\gamma_t(i)], \quad t = 1, 2, \dots, T \tag{29}$$

维特比算法

维特比算法是用动态规划解隐马尔科夫模型的预测问题。

算法步骤

输入：模型 $\lambda = (A, B, \pi)$ 和观测序列 $O = (o_1, o_2, \dots, o_T)$；
输出：最优路径 $I^{\ast} = (i_1^{\ast}, i_2^{\ast}, \dots, i_T^{\ast})$。

（1）初始化

$$\begin{align*} \delta_1(i) = \pi_i b_i(o_1), \quad i = 1, 2, \dots, N \\[10pt] \Psi_1(i) = 0, \quad i = 1, 2, \dots, N \end{align*}$$

（2）递推。对 $t = 2, 3, \cdots, T$

$$\begin{align*} \delta_t(i) &= \max_{1 \leq j \leq N} [\delta_{t - 1}(j) a_{ji}] b_i(o_t), \quad i = 1, 2, \cdots, N \\[10pt] \Psi_t(i) &= \operatorname{arg} \max_{1 \leq j \leq N}[\delta_{t - 1} a_{ji}], \quad i = 1, 2, \cdots, N \end{align*}$$

（3）终止

$$\begin{align*} P^{\ast} &= \max_{1 \leq i \leq N} \delta_{T}(i) \\[10pt] i_{T}^{\ast} &= \operatorname{arg} \max_{1 \leq i \leq N} [\delta_{T}(i)] \end{align*}$$

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

$$i_t^{\ast} = \Psi_{t + 1}(i_{t + 1}^{\ast})$$

求得最优路径 $I^{\ast} = (i_1^{\ast}, i_2^{\ast}, \dots, i_T^{\ast})$。