向前向后算法解决估算问题——隐马尔可夫疑难问题一

/ NLP / 没有评论 / 318浏览

估算问题

如果对隐马尔科夫模型不了解,请点这里

问题描述

给定隐马尔科夫模型 $h = ( A, B, \pi )$
给定观察序列 $O = ( o_1 o_2 o_3 … o_T )$
如何有效地计算出观察序列的概率,即 $P(O|h)$ ?

计算公式

给定 h,以及状态转换序列 $q = (q_1 q_2 q_3 … q_T )$, 产生观察序列 $O = ( o_1 o_2 o_3 … o_T )$ 的概率:

$$P(O |q, h) = b_{q_1}(o_{1})b_{q2}(o_{2})...b_{q_T}(o_{T})$$

给定 h, 则状态转换序列 $q = (q_1 q_2 q_3 … q_T )$ 的概率可以通过下面的公式计算

$$P(q | h) = \pi_{q_1}a_{q_1q_2}a_{q_2q_3}...a_{q_{T-1}q_T}$$

则 O 和 q 的联合概率为

$$P(O, q| h) = P(O |q, h)P(q | h) $$

考虑到所有的状态转换序列,则

$$P(O|h) = \sum_{q}P(O,q|h) = \sum_{q1,q2,...,qt}P(O |q, h)P(q | h)$$

存在的问题

理论上,可以通过穷举所有状态转换序列的办法计算观察序列 O 的概率。实际上,这样做并不现实

向前算法

英文名 Forward Algorithm

向前变量

$$\alpha_{t}(i) = P(o_{1} o_{2} o_{3} … o_{t}, q_{t} = i|h)$$

$\alpha_{t}(i)$ 是给定模型 h ,时刻 t 时处在状态 i,并且部分观察序列为 $o_1 o_2 o_3 … o_t$ 的概率。

递推公式

显然有$\alpha_{1}(i) = \pi_{i}b_{i}(o1)$ (1≤i≤N)

若$\alpha_{t}(i)$ (1≤i≤N)已知,则

$$\alpha_{t+1}(j) = \left [
\sum_{i = 1}^{N}\alpha_{t}(i)a_{ij} \right ] b_{j}(O_{t+1}) \qquad (1 \leq t \leq T-1, 1 \leq j \leq N) $$

终止时: $P(O | h) = \sum_{i = 1}^{N}\alpha_{T}(i)$

计算复杂度

计算量:$N(N+1)(T-1)+N$ 次乘法, $N(N-1)(T-1)$ 次加法

向后算法

英文名:Backward Algorithm

向后变量

$$\beta_{t}(i) = P(o_{t+1} o_{t+2} o_{t+3} … o_{T}, q_{t} = i|h)$$

$\beta_{t}(i)$是给定模型 h ,时刻 t 时处在状态 i,并且部分观察序列为$o_{t+1} o_{t+2} o_{t+3} … o_{T}$ 的概率。

递推公式

显然有 $\beta_{T}(i) = 1, (1 \le i \le N)$

若 $\beta_{t+1}(j), (1 \le j \le N)$ 已知,则

$$\beta_{t}(i) =\sum_{j = 1}^{N}a_{ij}b_{j}(O_{t+1})\beta_{t+1}(j) \qquad (1 \leq t \leq T-1, 1 \leq j \leq N) $$

终止时: $P(O|h) = \sum_{i = 1}^{N}\pi_{i}b_{i}(O_{1})\beta_{1}(i)$