条件随机场的条件概率计算

【概述】

对于线性链条件随机场的概率计算问题，即：给定线性链条件随机场 $P(Y|X)$，输入序列 $x$ 和输出序列 $y$，计算条件概率 $P(Y_i=y_i|x)$ 和 $P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$，以及相应的数学期望

与隐马尔可夫模型类似，引入前向向量与后向向量，递推的计算条件概率以及期望值，这样的算法称为前向-后向算法（Forward-backward Algorithm）

【前向向量与后向向量】

前向向量

对于线性链条件随机场的矩阵形式：

$$\begin{array}{rl}{P}_{\mathbf{w}}(y|x)& =\frac{1}{Z_{\mathbf{w}}(x)}\prod _{i=1}^{n+1}{M}_i(y_{i-1},y_i|x)\\ Z_{\mathbf{w}}(x)& =[M_1(x)M_2(x)\cdots M_{n+1}(x){]}_{\text{start},\text{stop}}\end{array}$$

对每个指标 $i=0,1,\cdots ,n+1$，定义前向向量 ${\alpha }_i(x)$：

$${\alpha }_0(y|x)=\{\begin{array}{lr}1,& y=\text{start}\\ 0,& y\ne \text{start}\end{array}$$

有递推公式：

$${\alpha }_i^T(y_i|x)={\alpha }_{i-1}^T(y_{i-1}|x)[M_i(y_i,y_i|x)],i=1,2,\cdots ,n+1$$

其中，${\alpha }_i(y_i|x)$ 表示在位置 $i$ 的标记是 $y_i$ 且从 $1$ 到 $i$ 的前部分标记序列的非规范化概率，$y_i$ 可取的值有 $m$ 个，故可将其写为 $m$ 维列向量形式，即：

$${\alpha }_i^T(x)={\alpha }_{i-1}^T(x)M_i(x)$$

后向向量

同理，对每个指标 $i=0,1,\cdots ,n+1$，定义后向向量 ${\beta }_i(x)$：

$${\beta }_{n+1}(y_{n+1}|x)=\{\begin{array}{lr}1,& y_{n+1}=\text{stop}\\ 0,& y_{n+1}\ne \text{stop}\end{array}$$

有递推公式：

$${\beta }_i(y_i|x)=[M_{i+1}(y_i,y_{i+1}|x)]{\beta }_{i+1}(y_{i+1}|x),i=1,2,\cdots ,n+1$$

其中，${\beta }_i(y_i|x)$ 表示在位置 $i$ 的标记是 $y_i$ 且从 $i+1$ 到 $n$ 的后部分标记序列的非规范化概率，$y_i$ 可取的值有 $m$ 个，故可将其写为 $m$ 维行向量形式，即：

$${\beta }_i(x)=M_{i+1}(x){\beta }_{i+1}(x)$$

【概率计算】

根据前向向量与后向向量的定义，可计算出标记序列在位置 $i$ 是标记 $y_i$ 的条件概率：

$$P(Y_i=y_i|x)=\frac{{\alpha }_i^T(y_i|x){\beta }_i(y_i|x)}{Z(x)}$$

以及在位置 $i-1$ 与 $i$ 是标记 $y_{i-1}$ 和 $y_i$ 的条件概率，即：

$$P(Y_{i-1}=y_{i-1},Y_i=y_i|x)=\frac{{\alpha }_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x){\beta }_i(y_i|x)}{Z(x)}$$

其中，对于规范化因子 $Z(x)$，有：

$$Z(x)={\alpha }_n^T(x)\mathbf{1}=\mathbf{1}{\beta }_1(x)$$

$\mathbf{1}$ 是元素均为 $1$ 的 $m$ 维列向量

【期望值计算】

条件分布

根据前向向量与后向向量的定义，对于特征函数 $f_k(y,x)$，其关于条件分布 $P(Y|X)$ 的数学期望为：

$$\begin{array}{rl}{E}_{P(Y|X)}[f_k]& =\sum _{y}P(y|x)f_k(y,x)\\ & =\sum _{i=1}^{n+1}\sum _{y_{i-1}{y}_i}{f}_k(y_{i-1},y_i,x,i)\frac{{\alpha }_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x){\beta }_i(y_i|x)}{Z(x)}\\ & k=1,2,\cdots ,K\end{array}$$

其中，对于规范化因子 $Z(x)$​，有：

$$Z(x)={\alpha }_n^T(x)\mathbf{1}=\mathbf{1}{\beta }_1(x)$$

上式为特征函数关于 $P(X|Y)$ 的数学期望的一般计算公式，对于转移特征

$$t_k(y_{i-1},y_i,x,i),k=1,2,\cdots ,K_1$$

可将上式中的 $f_k$ 替换为 $t_k$，对于状态特征

$$s_l(y_i,x,i)k=K_1+l,l=1,2,\cdots ,K_2$$

可将上式中的 $f_k$ 替换为 $s_l$

联合分布

假设经验分布为 $\tilde{P}(X)$，特征函数 $f_k(y,x)$ 关于联合分布 $P(X,Y)$ 的数学期望为：

$$\begin{array}{rl}{E}_{P(X,Y)}[f_k]& =\sum _{x,y}P(x,y)\sum _{i=1}^{n+1}{f}_k(y_{i-1},y_i,x,i)\\ & =\sum _x\tilde{P}(x)\sum _{y}P(y|x)\sum _{i=1}^{n+1}{f}_k(y_{i-1},y_i,x,i)\\ & =\sum _x\tilde{P}(x)\sum _{i=1}^{n+1}\sum _{y_{i-1}{y}_i}{f}_k(y_{i-1},y_i,x,i)\frac{{\alpha }_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x){\beta }_i(y_i|x)}{Z(x)}\\ & k=1,2,\cdots ,K\end{array}$$

其中，对于规范化因子 $Z(x)$​，有：

$$Z(x)={\alpha }_n^T(x)\mathbf{1}=\mathbf{1}{\beta }_1(x)$$

上式为特征函数关于 $P(X,Y)$ 的数学期望的一般计算公式，对于转移特征

$$t_k(y_{i-1},y_i,x,i),k=1,2,\cdots ,K_1$$

可将上式中的 $f_k$ 替换为 $t_k$，对于状态特征

$$s_l(y_i,x,i)k=K_1+l,l=1,2,\cdots ,K_2$$

可将上式中的 $f_k$ 替换为 $s_l$