Baum-Welch算法与参数估计——隐马尔可夫疑难问题三

/ NLP / 没有评论 / 1140浏览

参数估计问题

如果对隐马尔科夫模型不了解,请点这里
如果对向前变量和向后变量不了解,请点这里

问题描述

隐马尔科夫模型 h 参数未知或不准确的情况下
给定观察序列 $O = ( o_1 o_2 o_3 … o_T )$
按照 MLE 的原则,求得模型参数或调整模型参数,即如何确定一组模型参数,使得 $P(O|h)$ 最大

有指导的参数学习

英文名:supervised learning

在模型 h 未知的情况下,如果给定观察序列的同时,也给定了状态转换序列,此时可以通过有指导的学习方法学习模型参数。

给定下面的训练数据,可以通过最大似然估计法估计模型参数:
H/1 H/1 T/1 T/2 H/3 T/3
T/2 H/1 T/2 H/3 H/3 H/1

优缺点

无指导的参数学习

英文名:unsupervised learning

在模型 h 未知的情况下,如果仅仅给定了观察序列,此时学习模型的方法可以使用无指导的学习方法。

参数学习步骤

首先随机产生一组参数,通过反复迭代逐步求精的方式调整参数,最终使其稳定在一个可以接受的精度。

并不能一定保证求得最优模型,一般可以得到一个局部最优模型。

权值的选择

对状态转换序列 q 而言,选择权值为

$$P(q|O,h) = \frac{P(q, O | h)}{P(O | h)} = \frac{P(q,O | h)}{\sum_{q}P(q,O|h)}$$

状态转移矩阵

计算对于时刻 t 和时刻 t + 1,出现转移 (i,j) 的期望

在所有的路径中,选择出 $q_{t}= i$ 且 $q_{t+1} = j$ 的路径

设满足该条件的路径集合是 Q = { $q |q_{t} = i, q_{t+1} = j$ },则对于时刻 t 和时刻 t+ 1,出现转移 (i,j) 的期望为

$$\frac{\sum_{q \in Q}P(q, O|h)}{P(O | h)}$$

理论上可行,现实中不可行

Baum-Welch 算法

定义变量 $\xi_{t}(i, j)=P(q_{t} = i, q_{t+1} = j | O, h)$

$\xi_{t}(i, j)$ 是给定模型 h 和观察序列 O,在时刻 t 处在状态 i,时刻 t+1 处在状态 j 的概率

$$\xi_{t}(i,j) = \frac{P(q_{t}= i, q_{t+1} = j, O| h)}{P(O | h)} = \frac{\alpha_{t}(i)a_{ij}b_{j}(O_{t+1})\beta_{t+1}(j)}{P(O|h)} =\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)}$$

定义变量 $\gamma_{t}(i)$,令其表示在给定模型以及观察序列的情况下, t 时刻处在状态 i 的期望, 则有

$$\gamma_{t}(i) = \sum_{j=1}^{N}\xi_{t}(i,j)$$

$\sum_{t=1}^{T-1}\gamma_{t}(i)$ 是观察序列 O 中从状态 i 出发的转换的期望
$\sum_{t=1}^{T-1}\xi_{t}(i,j)$ 是观察序列 O 中从状态 i 到状态 j 的转换的期望

关于 $\pi, A, B$,一种合理的估计方法如下

初始状态概率

$$\overline{\pi_{i}} = \gamma_{1}(i)$$

即在t = 1时处在状态 i 的期望

状态转移矩阵

从状态 i 到状态 j 的转换的期望除以从状态 i 出发的转换的期望就是状态 i 到状态 j 的转移概率

$$\overline{a_{ij}} = \frac{\sum_{t=1}^{T-1}\xi_{t}(i,j)}{\sum_{t=1}^{T-1}\gamma_{t}(i)}$$

输出符号概率

定义$\delta(O_{t},v_{k})$

$O_{t} = v_{k}$ 时为 1
$O_{t} \neq v_{k}$ 时为0

则在状态 j 时输出符号 $v_k$ 的概率

$$\overline{b_{j}}(k) = \frac{\sum_{t=1}^{T}\gamma_{t}(j)\delta(O_{t},v_{k})}{\sum_{t= 1}^{T}\gamma_{t}(j)}$$

参数估计步骤

选择模型参数初始值,初始值应满足隐马尔科夫模型的要求

$$\sum_{i = 1}^{N}\pi_{i} = 1, \qquad \sum_{j = 1}^{N}a_{ij} = 1\quad 1 \leq i \leq N, \qquad \sum_{k = 1}^{M}b_{j}(k) = 1 \quad 1 \leq j \leq N$$

Baum-Welch是 EM 算法

E-step

计算 $\xi_{t}(i, j)$ 和 $\gamma_{t}(i)$

M-step

估计模型 $\bar{h}$

终止条件

$\left | \log(P(O | h_{i+1})) - \log(P(O|h_{i})) \right | < \varepsilon$

参数最终的收敛点并不一定是一个全局最优值,但一定是一个局部最优值