3 向前向后算法

和HMM第一大问题相似，计算给定x,y序列的条件概率。

定义 $\alpha_i(x)$为在时刻$i$止之前所有时刻的所有可能$y$取值联合当前$y_i$取值的非规范化概率。$m=|y|$。类似再定义和$\alpha$相反，从 $n+1$时刻开始的反向计算的向量$\beta_i(x)$。

3.1 向前向后

3.1.1 向前

定义向前联合非规范化概率,

$$\begin{align} \alpha_i(x) &= \left[ \sum_{y_1, \cdots, y_{i-1}} p(x_1, \cdots, x_i, y_1, \cdots, y_{i-1}, y_i) \right] \\ &= \left[ p(x_1, \cdots, x_i, y_i) \right] \\ \alpha_{i+1}(x) &= \left[ \sum_{y_i} p(x_1,\cdots,x_i, y_i) p(x_{i+1}, y_i, y_{i+1}) \right] \\ &= \left[ \alpha_i^T(x)M_{i+1}(x) \right]^T \end{align}$$

1, $i=0$:

此时$y \equiv start$，这是必然发生的事件。

$$\alpha_0(x)=1$$

2, 时刻$i=1, \cdots, n$:

$$\alpha_i^T(x) = \alpha_{i-1}^T(x) M_i(x)$$

3, 时刻$i=n+1$:

此时$y \equiv stop$。因此直接乘向量$1$。

$$Z(x) = \alpha_n^T(x) \, \cdot \, 1$$

这里得到的是规范化因子。其实整个步骤就是之前的线性链条件随机场矩阵表现形式的规范化因子计算过程。线性链条件随机场
在工程中，$Z_w(x)$的值会非常大，甚至超出计算机浮点数范围，造成计算出错。因此，实际操作中使用 $\log Z_w(x)$ 替代它，为此，相应的计算均更改为对数，在迭带中使用 $\log \sum \exp$ 函数计算。替代连续的矩阵相乘。

3.1.2 向后

定义向后联合非规范化概率，

$$\begin{align} \beta_i(x) &= \left[ \sum_{y_{i+1}, \cdots, y_n} p(y_i, y_{i+1}, \cdots, y_n, x_{i+1}, \cdots, x_n) \right] \\ &= \left[ p(y_i, x_{i+1}, \cdots, x_n) \right] \\ \beta_{i-1}(x) &= \left[ \sum_{y_i} p(y_{i-1}, y_i, x_i) p(y_i, x_{i+1}, \cdots, x_n) \right] \\ &= M_i(x) \beta_i(x) \end{align}$$

1, 时刻$i=n+1$:

此时$y \equiv stop$， 这是必然发生事件。

$$\beta_{n+1}(x)=1$$

2, 时刻$i=n, \cdots, 1$:

$$\beta_i=M_{i+1}(x) \beta_{i+1}(x)$$

3, 时刻$i=0$:

此时$y \equiv start$。因此直接乘向量$1$。

$$Z(x) = 1^T \, \cdot \, \beta_1(x)$$

这里其实就是把之前的向前计算顺序反过来。

3.2 概率计算

这里值得注意的是$\alpha_i, \beta_i$这两个向量分别表示了在序列时刻$i$之前和之后所有可能状态的非规范化概率。很显然，
$$\begin{align} p(y_i=s^\prime|x) &= \frac{\alpha_i(y_i=s^\prime, x) \beta_i(y_i=s^\prime, x) }{ Z(x) } \\ p(y_{i-1}=s, y_i=s^\prime |x ) &= \frac{ \alpha_{i-1}(y_{i-1}=s, x) M_i(y_{i-1}=s,y_i=s^\prime, x ) \beta_i(y_i=s^\prime, x) }{Z(x)} \end{align}$$

这里是取对应$y_{i-1}, y_i$的向量或矩阵元素乘积。并不是矩阵相乘。

[1] 李航; 统计机器学习