HMM 关键词检索

2017-02-06

记一下 HMM 的一些总是忘记的名词和计算过程。

HMM

离散一阶马尔可夫链：系统在 t 时刻状态只和其在 t-1 时刻的状态相关。
马尔可夫模型：随机过程独立于时间 t，且状态转移概率 Σ a_ij = 1 (j=1..N)。
HMM 可观察到的事件是状态的随机函数，状态转移过程隐蔽（马尔可夫链），事件是一般随机过程。一个随机事件由观察值序列 O = O_1, O_2, .., O_T 表示，该事件背后隐藏着实际的状态序列 Q = q_1, q_2, .., q_T。HMM 的关键在于将两个序列联系起来，用可观察明字符组成的观察序列去表征由离散隐状态组成的状态序列（路径）。
HMM 要求满足马尔可夫性假设（状态构成一阶马尔可夫链）、不动性假设（状态和具体时间无关）以及输出独立性假设（输出，也就是观察到的值仅与背后的状态有关）。
HMM 由五元组 λ = (N, M, A, B, π) 描述：
- N = {q_1, q_2, .., q_N}：有限状态集合
- M = {v_1, v_2, .., v_M}：有限观察值集合
- A = {a_ij}：状态转移概率矩阵
- B = {b_jk}, b_jk = P(O_t = v_k | q_t = Sj)：观察值概率分布矩阵
- π = π_i：初始状态概率分布
给定 HMM 模型 λ = (A, B, π)，观察序列通过状态的不断转移和 B 矩阵产生，初始根据 π 选择 q_1，根据状态转移概率生成 q_t，并根据 q_t = i 和 b_ik 生成 O_t = v_k。
对于给定模型 λ = (π, A, B)，令 O = O_1, O_2, .., O_T 为观察值序列，三个基本问题及解决方案：
- 评估问题（前向算法）：对于给定模型，求任意观察值序列的概率 P(O | λ)。
- 解码问题（韦特比算法）：对于给定模型和观察值序列，求可能性最大的状态序列 maxQ{P(Q | O, λ)}，也称 Q 为最优路径。即有效选择 “最优” 状态序列以尽量好地解释观察序列。
- 学习问题（向前向后算法）：给定观察值序列，调整 λ 使该观察值序列出现的概率 P(O | λ) 最大。

前向算法

α(t, i) = P(o_1, o_2, .., o_T, q_t = S_i | λ) 指 “在时刻 t，得到 t 之前的所有明符号序列，且时刻 t 的状态是 S_i” 这一事件的概率。
- α(1, i) = P(o_1, q_1 = S_i | λ) = π(i)b(i, o_1)；
- 递推：`α(t+1, j) = [Σ α(t, i) · a(i, j), i=1..N] × b(j, o_t+1)；
- α(T, i) = P(o_1, .., o_T, q_T = S_i | λ)；
- P(O | λ) = Σ α(T, i), (i = 1..N)

Viterbi 算法

算法和卷积码的韦特比解码同名，因为本质就一样。
δ(t, i) 为在 1..t 时刻按照状态序列 q_1, .., q_t 且 q_t = S_i 能够产生出 o_1, o_2, .., o_t 的最大概率，即 δ(t, i) = max{ P(q_1, .., q_t-1, q_t = Si, o_1, .., o_t | λ) }。序列 o 和系统 λ 都是确定的，max 根据序列 q 的变动选取最优解。
记忆变量：φ(t, i) 记录概率最大路径上当前状态的前一个状态。
初始化：δ(1, i) = π(i)b(i, O_1)，φ(1, i) = 0；
递推：δ(t, j) = max{δ(t-1, j) × a_ji} × b(i, O_t), 2 ≤ t ≤ T, 1 ≤ i ≤ N；
终止：p* = max{δ(T, i)}；
路径回溯：q* = φ(t+1, q*_t+1), t = T-1, T-2, .., 1。

向前向后算法

最大似然估计无法解决学习问题，因为 HMM 中的状态序列为隐变量，无法被观察到。EM 算法由交替的 “期望” 过程（E）和 “极大似然估计” 过程（M）组成，E 过程从条件期望中构造完全数据的似然函数值，M 过程利用参数的统计量重新估计概率模型的参数，使训练数据对数似然最大。
初始化：满足概率条件的情况下随机给 π_i、a_ij 和 b_jk 赋值，得模型 λ_0，设 i = 0；
E 过程：由 λ_i 根据下面公式计算期望值 ε(t, i, j)（给定模型和观察序列，在时间 t 位于状态 S_i，时间 t+1 位于状态 S_j 的概率）和 γ(t, i)（给定模型和观察序列，在时间 t 位于状态 i 的概率），E 过程的期望是根据上一个 M 过程重估后的模型计算的；

ε(t, i, j) = P(q_t = S_i, q_t+1 = S_j | O, λ)
           = P(q_t = S_i, q_t+1 = S_j, O | λ) / P(O | λ)
           = α(t, i)· a(i, j) · b(j, O_t+1) · β(t+1, j) / P(O | λ)
           = α(t, i)· a(i, j) · b(j, O_t+1) · β(t+1, j) / {Σi Σj α(t, i) · a(i, j) · b(j, O_t+1) · β(t+1, j) }
γ(t, i) = Σj ε(t, i, j)

M 过程：根据 E 过程得出的期望值，根据下面公式重新估计 πi，a_ij 和 b_jk，得到模型 λ_i+1。

1
2
3

π(i) = P(q_1 = S_i) = γ(1, i)
a(i, j) = {Σt ε(t, i, j)} / {Σt γ(t, i)}, t = 1..T-1
b(j, k) = {Σt γ(t, j) × δ(O_t, v_k)} / {Σt γ(t, j)}, t = 1..T

重复 E、M 过程直到模型收敛。

问题

前向算法、Viterbi 和 Baum-Welch 算法的概率值连续乘法运算容易下溢。
前向算法中每步运算都可以乘一个比例因子 c(t)，如下：

1
2
3

α(t+1, j) = [Σ α(t, i) · a(i, j), i=1..N] × b(j, o_t+1)
α'(t+1, j) = c(t) × [Σ α(t, i)' · a(i, j), i=1..N] × b(j, o_t+1)
c(t) = 1 / Σ α(t, i) , i = 1..N

Viterbi 算法可以将概率值取对数（乘积化为对数求和）。

计算机理论基础

HMM 关键词检索

HMM

前向算法

Viterbi 算法

向前向后算法

问题

相关链接