隐马尔可夫模型【学习笔记】
TLE_Automat
·
·
算法·理论
upd on 5.25 - 修改了三处笔误
隐马尔可夫模型
一. 隐马尔可夫模型的性质
-
具有马尔可夫性的状态序列 X，但这个序列是不可被直接观测的，故称之为隐状态序列，我们假设隐状态共有 N 种取值。
-
还具有一个证据状态序列 E。对于所有时刻 t，可观测到与隐状态 X_t 有关的输出 E_t。
-
独立性假设 1 ：对于所有时刻 t，给定前一个时刻的隐状态 X_{t-1}，则当前时刻的隐状态 X_{t} 独立于过去所有隐状态和证据状态，即 X_t 只依赖于 X_{t - 1}（X_{t - 1} 给定的条件下）。
-
独立性假设 2 ：对于所有时刻 t，给定当前时刻的隐状态 X_t，则当前时刻的证据状态 E_t 独立于过去所有隐状态和证据状态，即 E_t 只依赖于 X_t（X_{t} 给定的条件下）。
二. 隐马尔可夫模型的概率推理
0. 一些符号说明
- 隐状态序列 X：将 t 时刻的隐藏状态记为 X_{t}。
- 证据状态序列 E：将 t 时刻的证据状态记为 E_t。
- 初始概率 \pi：隐状态 X 的先验概率分布，\pi_{i} = P(X_1 = i)。
- 转移概率 A：描述前一状态转移到后一状态的概率，A_{i, j} = P(X_{t + 1} = j \mid X_{t} = i)。
- 发射概率 B：描述从隐状态到证据状态的概率，B_{i}(e_j) = P(E_{t} = e_{j}\mid X_{t} = i)。
1. 滤波任务
- 目标：根据截至当前时刻 t 的所有观测信息构成的证据状态 e_{1:t} = (e_1, e_2, \cdots, e_t)，推断当前时刻 t 的隐藏状态 X_t 的概率分布 \gamma_{t}(i) = P(X_t = i\mid e_{1:t})。这个分布也被称为状态置信分布或滤波概率。
至于这个任务为什么叫“滤波”，我个人的理解是——这个任务要根据当前已经观测到的状态实时反馈当前的隐藏状态的概率分布，相当于边听边翻译，这跟滤波很像，所以我们这么叫也很合理，接下来我们开始推导。
根据条件概率的公式可以比较容易地得到
P(X_{t} = j \mid e_{1:t-1}) = \sum\limits_{i = 1}^{N} P(X_{t} = j \mid X_{t - 1} = i) P(X_{t - 1} = i\mid e_{1:t-1}) \ \ \ \ \ \ \ \ \ \ \ \ (1)
由贝叶斯公式可知
P(A\mid BC) = \frac{P(ABC)}{P(BC)} = \frac{P(B\mid AC)P(A\mid C)P(C)}{P(BC)} = \frac{P(B\mid AC)P(A\mid C)}{P(B \mid C)}
所以有
\begin{aligned}
P(X_{t} = j \mid e_{1:t}) &= P(X_{t} = j \mid (e_{t}, e_{1:t-1})) = \frac{P(e_{t} \mid (X_{t} = j, e_{1:t-1}))P(X_{t} = j \mid e_{1:t-1})}{P(e_{t}\mid e_{1:t-1})} \ \ \ \ \ \ \ \ \ \ \ \ (2)
\end{aligned}
由独立性假设 2
P(e_{t} \mid (X_{t} = j, e_{1:t-1})) = P(e_{t} \mid X_{t} = j)\ \ \ \ \ \ \ \ \ \ \ \ (3)
将 (1),(3) 两式带入 (2) 式即可得到
P(X_{t} = j \mid e_{1:t}) = \frac{P(e_{t} \mid X_{t} = j)\sum\limits_{i = 1}^{N} P(X_{t} = j \mid X_{t - 1} = i) P(X_{t - 1} = i\mid e_{1:t-1})}{P(e_{t}\mid e_{1:t-1})}
令常数 \displaystyle\alpha = \frac{1}{P(e_t \mid e_{1:t-1})}，则
P(X_{t} = j \mid e_{1:t}) = \alpha P(e_{t} \mid X_{t} = j)\sum\limits_{i = 1}^{N} P(X_{t} = j \mid X_{t - 1} = i) P(X_{t - 1} = i\mid e_{1:t-1})
即
\gamma_{t}(j) = \alpha B_{j}(e_t)\sum\limits_{i=1}^{N}A_{i,j}\gamma_{t-1}(i)
如果我们定义两个 N 维向量到一个 N 维向量的运算 (\mathbf a\circ \mathbf b)_i = a_i b_i，将 \gamma_{t} = [\gamma_{t}(1), \cdots, \gamma_{t}(N)]^{\top} 和 \mathbf B(e_{t}) = [B_{1}(e_{t}), \cdots, B_{N}(e_{t})]^{\top} 看作 N 维列向量，转移写成矩阵形式就是
\gamma_{t}^{\top} = \alpha \mathbf B(e_{t}) \circ (\gamma_{t-1}^{\top}\mathbf A)
由于常数 \alpha 不好计算，我们可以忽略这个常数，直接计算得到 \gamma_{t} 然后概率归一化即可。
2. 预测任务
- 目标：根据截至当前时刻 t 的所有观测信息构成的证据状态 e_{1:t} = (e_1, e_2, \cdots, e_t)，预测未来时刻 t+k(k > 0) 的隐藏状态 X_{t + k} 的概率分布 \gamma_{t+k\mid t}(i) = P(X_{t + k} = i \mid e_{1:t})。
这个任务的目标非常明确，那就让我们直接推式子吧。
首先，我们先使用滤波任务中的方法推出 \gamma_{t}(i) = P(X_t = i\mid e_{1:t})。
先考虑单步预测，即如何得到 P(X_{t + 1} = j \mid e_{1:t}) 的预测值。通过条件概率的公式，我们也可以比较容易地得到
\gamma_{t+1\mid t} = P(X_{t + 1} \mid e_{1:t}) = \sum\limits_{i = 1}^{N} \gamma_{t}(i)A_{i,j}
写成矩阵形式就是
\gamma_{t+1\mid t}^{\top} = \gamma_{t}^{\top} \mathbf A
于是可以得到
\gamma_{t+k\mid t}^{\top} = \gamma_{t}^{\top}\mathbf{A}^{k}
3. 平滑任务
假如你正在听英语听力，判断说话的人在每个时间点的情绪（隐状态），那么以下是使用滤波概率推理和平滑概率推理的区别。
- 滤波：在听完前 k 秒的录音时，立即对第 k 秒的情绪做出判断。
- 平滑：在听完完整录音后，重新利用所有信息，评估第 k 秒的情绪。
我们先定义前向信息
\alpha_{t}(i) = P(X_{k} = i , e_{1:k})
注意区别 \alpha 与滤波任务里的 \gamma，这里的 \alpha 是联合概率，之前的 \gamma 是条件概率。
首先，我们先确定递推的初值
\alpha_{1}(i) = P(X_{1} = i, e_{1}) = P(X_{1} = i)P(e_{1} \mid X_{1} = i) = \pi_{i}B_{i}(e_1)
考虑递推
\begin{aligned}
\alpha_{t}(j) = P(X_{t} = j, e_{1:t-1}, e_{t}) = P(e_{t} \mid (X_t = j, e_{1:t-1}))P(X_t=j, e_{1:t-1})
\end{aligned}
由独立性假设 2
P(e_{t} \mid (X_t = j, e_{1:t-1})) = P(e_{t} \mid X_{t} = j)
所以
\begin{aligned}
\alpha_{t}(j) &= P(e_{t} \mid X_{t} = j)\sum\limits_{i=1}^{N}P(X_{t-1} = i, e_{1:t-1})P(X_t = j, X_{t-1}=i) \\
&= B_{j}(e_t)\sum\limits_{i=1}^{N}\alpha_{t-1}(i)A_{i,j}
\end{aligned}
我们定义后向信息
\beta_{k}(i) = P(e_{k+1:T} \mid X_{k} = i)
这表示在时刻 k 处于状态 i 的条件下，观测到从时刻 k+1 到 T 的后续观测序列 e_{k+1:T} 的概率。
首先，由于 T 时刻之后没有观测序列，所以我们定义
\beta_{T}(i) = 1
考虑递推
\begin{aligned}
\beta_{t}(j) = P(e_{t+1:T} \mid X_{t} = j) = \sum\limits_{i=1}^{N} P((e_{t+1:T},X_{t+1}=i)\mid X_{t}=j) = \sum\limits_{i=1}^{N} P((e_{t+1}, e_{t+2:T},X_{t+1}=i)\mid X_{t}=j)
\end{aligned}
由贝叶斯公式可知
P(ABC | D) = \frac{P(ABCD)}{P(D)} = \frac{P(ABCD)}{P(BCD)}\cdot \frac{P(BCD)}{P(CD)} \cdot \frac{P(CD)}{P(D)} = P(A\mid BCD)P(B\mid CD)P(C\mid D)
所以
\beta_{t}(j) = \sum\limits_{i=1}^{N}P(e_{t+1} \mid (e_{t + 2:T}, X_{t + 1} = i, X_{t} = j))P(e_{t + 2:T}\mid (X_{t + 1} = i, X_{t} = j))P(X_{t + 1}=i \mid X_{t}=j)
由独立性假设 1 和 2，可直接推出
\begin{aligned}
\beta_{t}(j) &= \sum\limits_{i = 1}^{N} P(e_{t + 1} \mid X_{t+1}=i)P(e_{t+2:T}\mid X_{t + 1}=i)P(X_{t+1}=i, X_{t}=j) \\
&= \sum\limits_{i=1}^{N} B_{i}(e_{t+1})A_{j,i}\beta_{t+1}(i)
\end{aligned}
现在我们要求平滑概率
P(X_{k} = i \mid e_{1:T}) = \frac{P(X_{k} = i, e_{1:T})}{P(e_{1:T})}
对于分子有
\begin{aligned}
P(X_{k}=i, e_{1:T}) = P(X_{k} = i, e_{1:k}, e_{k + 1:T}) = P(X_{k} = i, e_{1:k})P(e_{k+1:T} \mid (X_{k} = i, e_{1:k}))
\end{aligned}
由独立性假设 1 和 2，可知
P(e_{k+1:T} \mid (X_{k} = i, e_{1:k})) = P(e_{k+1:T} \mid X_{k} = i) = \beta_{k}(i)
所以
P(X_{k}=i, e_{1:T}) = \alpha_{k}(i)\beta_{k}(i)
对于分母有
P(e_{1:T}) = \sum\limits_{j=1}^{N} P(X_{k} = j, e_{1:T}) = \sum\limits_{j=1}^{N}\alpha_{k}(j)\beta_{k}(j)
所以平滑概率
P(X_{k} = i \mid e_{1:T}) = \frac{\alpha_{k}(i)\beta_{k}(i)}{\sum\limits_{j = 1}^{N}\alpha_{k}(j)\beta_{k}(j)}
4. 解释任务
假如你正在听一段录音（观测到的证据序列），我们想知道的是最有可能的整个句子是什么，而不是每个时间点最有可能的单词的简单拼接。
- 目标：这个任务不是计算某个时刻的状态概率分布，而是找到最有可能产生整个观测序列 e_{1:T} 的那个，即求 \operatorname{argmax}\limits_{X_{1:T}} P(X_{1:T}\mid e_{1:T})，由于 P(e_{1:T}) 对于所有路径来说都是常数，所以等价于求 X^{*}_{1:T} = \operatorname{argmax}_{X_{1:T}} P(X_{1:T}, e_{1:T})。
考虑使用动态规划的思想，设 m_t(i) 为已经观测到 e_{1:t}，且到达当前隐状态 X_t = i 的所有可能路径中概率最大的路径的概率，即 m_t(i) = \max\limits_{X_1, \cdots, X_{t - 1}}P(X_1, \cdots, X_{t-1}, X_t=i, e_{1:t})。
考虑初始状态 m_{1}(i) = P(X_{1} = i, e_{1}) = \pi_{i}B_i(e_1)。
考虑枚举时刻 t-1 的状态，根据前面三种推导的方法，可以比较显然地得到状态转移式
m_{t}(j) = \left[\max\limits_{i=1}^{N} m_{t-1}(i)A_{i,j}\right]B_j(e_t)
为了记录最优路径，我们还需要开一个数组 a 来储存转移信息
a_t(j) = \operatorname{argmax}_{i=1}^{N}(m_{t-1}(i)A_{i,j})
整个观测序列的最可能路径的概率 P^{*} = \max_{i=1}^{N}m_{T}(i)，最优路径的最后一个状态 X_{T}^{*} = \operatorname{argmax}_{i=1}^{N}m_{T}(i)，之后可以通过 a 数组反向回溯出整个最优路径 X_{t}^{*} = a_t(X_{t+1}^{*})。