合集：统计学习方法笔记

---

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 生成过程

1. 初始化：选择初始状态 $i_1$ 根据 $\pi$。
2. 对于 $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算法）

需要实现如下：

1. 确定完整数据的对数似然函数： \(\log L(\lambda; I, O) \xrightarrow[]{} 要最大化模型的当前似然值\)

2. 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转换自本人的统计学习方法笔记。