条件随机场概率计算

这里的概率计算问题指的是:

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

前向后向算法

像HMM一样, 使用前向-后向向量, 递归地计算以上概率及期望值.

前向向量

对于每个位置$i=0,1,2,\cdots,n+1$, 定义前向向量$\alpha_i(x)$, 注意这是一个向量, 长度为状态$y_i$可以取的状态数量, 即$m$维向量, 每个向量定义为:

$\alpha_0(y_0|x)= \begin{cases} 1,\ y_0=start \\ 0,\ else \end{cases}$

$\alpha_i^T(y_i|x)=\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x),\ i=1,2,\cdots,n+1$

对于初始情况, 定义$\alpha_0(y|x)$向量在初始状态$start$位置上为1, 其他位置都为0.

$\alpha_0(y|x)$表示在位置$i$上, 标记为$y_i$并且到位置$i$之前的所有位置上为标记序列对应的前半部分状态的非规范化概率. 上式又可表示为:

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

后向向量

对于每个位置$i=0,1,2,\cdots,n+1$, 定义后向向量$\beta_i(x)$, 向量的长度与前向向量相同:

$\beta_{n+1}(y_{n+1}|x)= \begin{cases} 1,\ y_{n+1}=stop \\ 0,\ else \end{cases}$

$\beta_i(y_i|x)=M_{i+1}(y_i,y_{i+1}|x)\beta_{i+1}(y_{i+1}|x),\ i=0,2,\cdots,n$

$\beta_i(y_i|x)$表示在位置$i$上标记为$y_i$且从$i+1$到$n$的后部分标记序列对应的非规范化概率

概率计算

根据前向-后向向量的定义, 计算状态序列在位置$i$上标记$y_i$的条件概率:

$\begin{aligned} P(Y_i=y_i|x)=\frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{Z(x)} \end{aligned}$

在位置$i-1$和位置$i$标记$y_{i-1}$和$y_i$的条件概率:

$\begin{aligned} 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)} \end{aligned}$

其中$Z(x)=\alpha_n^T(x)\cdot\textbf{1}=\textbf{1}^T\cdot\beta_1(x)$

期望计算

计算特征函数关于联合分布$P(X,Y)$和条件分布$P(Y|X)$的数学期望.

特征函数关于条件分布$P(Y|X)$的数学期望为:

$\begin{aligned} E_{P(Y|X)}[f_k] &= \sum\limits_{y}P(y|x)f_k(y,x) \\ &= \sum\limits_{i=1}^{n+1}\sum\limits_{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{aligned}$

另外, 假设经验分布为$\tilde{P}(X)$, 特征函数关于联合分布$P(X,Y)$的数学期望为:

$\begin{aligned} E_{P(X,Y)}[f_k] &= \sum\limits_{x,y}P(x,y)\sum\limits_{i=1}^{n+1}f_k(y_{i-1},y_{i},x,i) \\ &= \sum\limits_{x}\tilde{P}(X)\sum\limits_{y}P(y|x)\sum\limits_{i=1}^{n+1}f_k(y_{i-1},y_{i},x,i) \\ &= \sum\limits_{x}\tilde{P}(X)\sum\limits_{i=1}^{n+1}\sum\limits_{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{aligned}$

对于给定的观测序列$x$和状态序列$y$, 可以通过一次前向扫描计算$\alpha_{i}$和$Z(x)$, 一次后向扫描计算$\beta_i$, 从而得到所有概率和特征的期望.