1. HMM 的定义与特点¶
隐马尔可夫模型（Hidden Markov Model, HMM）是一种统计模型，它描述了一个由隐藏状态序列和观测序列组成的系统。在 HMM 中，隐藏状态是不可直接观察的，但可以通过观测到的数据来推断。
- 输入: $\lambda = (A, B, \pi)$
- 输出: 观测序列 $O$
- 用途: HMM 可用于语音识别、自然语言处理等领域。
2. 观测序列生成过程¶
2.1 输入¶
- $\lambda = (A, B, \pi)$：模型参数。
- $T$：观测序列的长度。
2.2 输出¶
- $O = (o_1, o_2, ..., o_T)$：生成的观测序列。
2.3 生成过程¶
- 初始化：选择初始状态 $i_1$ 根据 $\pi$。
- 对于 $t = 1$ 到 $T$：
- 根据当前状态 $i_t$ 和观测概率 $b_{i_t}(o_t)$ 生成观测 $o_t$。
- 根据状态转移概率 $a_{i_t i_{t+1}}$ 转移到下一个状态 $i_{t+1}$。
3. HMM的基本问题¶
3.1 算法计算问题¶
3.1.1 直接计算法（直观但计算上不可行）¶
- 列举所有状态序列，计算 $P(O|\lambda) = \sum_{I} P(O|I,\lambda)$
3.1.2 前向算法¶
定义$\alpha_t(i)$：给定$\lambda = (A, B, \pi)$，时刻$t$大部分观测序列为$o_1, o_2, ..., o_t$，且状态为$i$的概率。
- (1) 初始化：$\alpha_1(i) = p(o_1, s_1=i|\lambda)$
- (2) 递推：对$t=1, 2, ..., T-1$，
$$ \alpha_{t+1}(j) = \left[\sum_{i=1}^{N} \alpha_t(i)a_{ij}\right]b_j(o_{t+1}), \quad j=1,2,...,N $$
- (3) 终止：$P(O|\lambda) = \sum_{i=1}^{N} \alpha_T(i)$
前向算法的时间复杂度$O(N^2T)$
3.1.3 后向算法¶
定义$\beta_t(i)$：给定$\lambda = (A, B, \pi)$，在时刻$t$状态为$i$的条件下，从时刻$t$到末尾观测序列为$o_{t+1}, o_{t+2}, ..., o_T$的概率。
- 输入：$\lambda, O$
- 输出：$P(O|\lambda)$
- (1) $\beta_T(i) = 1, \quad 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) $$
后向算法的时间复杂度$O(N^2T)$
4. 学习问题¶
4.1 观测序列 → λ：无监督学习：Baum-Welch算法¶
4.2 观测序列 → λ：有监督学习¶
4.2.1 采用极大似然估计算法¶
参数估计：
$$ \hat{\alpha}_{ij} = \frac{A_{ij}}{\sum_{j=1}^{N} A_{ij}}, \quad i,j=1,2,\ldots,N $$
$$ \hat{b}_j(k) = \frac{B_{jk}}{\sum_{k=1}^{M} B_{jk}}, \quad j=1,2,\ldots,N, \quad k=1,2,\ldots,M $$
$$ \hat{\pi}_i = \frac{n_i}{\sum_{i=1}^{N} n_i} \rightarrow 初始状态为\pi_i的频率 $$
4.3 无监督学习情况¶
假设给定数据仅包含$\lambda = (O_1, O_2, ..., O_T)$，没有隐状态序列，目标：学习$\lambda$。
4.3.1 模型假设：含有隐变量的生成模型：¶
$$ P(O|\lambda) = P(O|I,\lambda) \cdot P(I|\lambda) $$
4.3.2 Baum-Welch算法（EM算法）¶
需要实现如下：
-
确定完整数据的对数似然函数：
$$ \log L(\lambda; I, O) \xrightarrow[]{} 要最大化模型的当前似然值 $$ -
E步：求目标函数：$Q(\lambda, \pi)$
$$ Q(\lambda, \pi) = E_{T}[ \log P(O,I|\lambda, \pi) ] $$
5. Baum-Welch算法详解¶
5.1 E步：求Q函数¶
$$ Q(\lambda, \lambda_0) = E_{\pi}[\log p(O, I|\lambda_0, \lambda)] $$
由链式法则：
$$ p(l_0, l_T|\lambda) = \pi_{i_0} b_{i_0 i_1}(O_1) \cdot a_{i_1 i_2} b_{i_2 i_3}(O_2) \cdots a_{i_{T-1} i_T} b_{i_T i_{T+1}}(O_T) $$
则Q函数可写为：
$$ Q(\lambda, \lambda_0) = \sum_{I} (\log \pi_i) p(l_0, I|\lambda) + \sum_{t=1}^{T} (\sum_{i,j} \log a_{ij} b_{ij}(O_t)) p(I_0, I|\lambda) + \sum_{I} (\log b_{i_T i_{T+1}}(O_T)) p(C|I|\lambda) $$
5.2 M步：最大化Q函数¶
对上述三项分别进行最大化：
第一项：¶
利用拉格朗日乘数法：
$$ \pi_i = \frac{p(l_0, I|\lambda)}{p(l_0|\lambda)} $$
第二项：¶
$$ a_{ij} = \frac{\sum_{t=1}^{T} p(l_0, I_t=i, I_{t+1}=j|\lambda)}{\sum_{j=1}^{M} \sum_{t=1}^{T} p(l_0, I_t=i, I_{t+1}=j|\lambda)} $$
第三项：¶
$$ b_j(k) = \frac{\sum_{t=1}^{T} \alpha_t(j) a_{jk} b_k(o_t) \beta_t(j)}{\sum_{t=1}^{T} \alpha_t(j) \beta_t(j)} $$
5.3 算法步骤¶
输入: 观测数据 $O = (o_1, o_2, \ldots, o_T)$
初始化: $\forall t=0$, 选取 $\alpha_{tj}^{(0)}, b_j^{(0)}(k), \pi_i^{(0)}$, 得模型 $\lambda^{(0)} = (A^{(0)}, B^{(0)}, \pi^{(0)})$
迭代更新:
- E步：计算$\gamma_{tij}^{(n)} = (A^{(n)}, B^{(n)}, \pi^{(n)})$
- M步：更新参数
6. 预测算法¶
包括 维特比算法 和 近似算法
6.1 近似算法¶
在每日每时刻最有可能出现的状态 $i^*$, 从而得到状态序列，将其作为预测结果。
$$ I^* = (i_1^*, i_2^*, \ldots, i_T^*) $$
$$ Y_t(i) = P(C_t | \lambda) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^{N} \alpha_t(j) \beta_t(j)} $$
$$ \hat{x}_t = \arg\max_{i \in S} Y_t(i) $$
优点: 计算简单
缺点: 结果可能存在概率为0的相邻状态, 即可能存在状态 $x_t, x_{t+1}$, 使得 $\alpha_{x_t x_{t+1}} = 0$
6.2 维特比算法 (Viterbi Algorithm)¶
6.2.1 定义 $\delta_t(i)$：¶
时刻 $t$ 状态为 $i$ 的所有单个路径 $(x_1, x_2, ..., x_t)$ 中概率最大值：
$$ \delta_t(i) = \max_{x_1, x_2, ..., x_{t-1}} p(x_1, x_2, ..., x_{t-1}, x_t=i, y_1, y_2, ..., y_t) $$
6.2.2 递推公式：¶
$$ \begin{aligned} \delta_{t+1}(j) &= \max_{1 \leq i \leq N} \left[ \delta_t(i) a_{ij} \right] b_j(y_{t+1}), \quad j=1,2,...,N; t=1,2,...,T-1 \\ \psi_{t+1}(j) &= \arg \max_{1 \leq i \leq N} \left[ \delta_t(i) a_{ij} \right], \quad j=1,2,...,N \end{aligned} $$
6.2.3 算法步骤¶
输入：
- $\lambda = (A, B, \pi)$，观测序列 $O = (o_1, o_2, ..., o_T)$
- 输出：最优路径 $\pi^* = (x_1^*, x_2^*, ..., x_T^*)$
初始化：
$$
\begin{aligned}
\delta_1(i) &= \pi_i b_i(o_1), \quad i=1,2,...,N \\
\psi_1(i) &= 0, \quad i=1,2,...,N
\end{aligned}
$$
递推：
$$
\begin{aligned}
\delta_t(i) &= \max_{1 \leq j \leq N} \left[ \delta_{t-1}(j) a_{ji} \right] b_i(o_t), \quad i=1,2,...,N; t=2,3,...,T \\
\psi_t(i) &= \arg \max_{1 \leq j \leq N} \left[ \delta_{t-1}(j) a_{ji} \right], \quad i=1,2,...,N
\end{aligned}
$$
终止：
$$
\begin{aligned}
P^* &= \max_{1 \leq i \leq N} \delta_T(i) \\
x_T^* &= \arg \max_{1 \leq i \leq N} \delta_T(i)
\end{aligned}
$$
回溯：
$$
x_t^* = \psi_{t+1}(x_{t+1}^*), \quad t=T-1, T-2, ..., 1
$$
注：本文使用Qwen转换自本人的统计学习方法笔记。
