这一节介绍CRF的概率计算问题(它是下一节参数估计的基础):即在给定条件随机场参数$w$、特征函数$F(\cdot)$、输入序列$x$以及输出序列$y$的情况下,计算条件概率$P(Y_i=y_i\mid x),P(Y_{i-1}=y_{i-1},Y_i=y_i\mid x)$以及相应数学期望。其实对于概率的动态规划求解在前面CRF的矩阵形式那小节已经做了简单介绍,这里再简单分析一下:

以$P(Y_i=y_i\mid x)$为例,要计算该条件概率,需要对另外的$n-1$项:$y_1,y_2,...,y_{i-1},y_{i+1},...,y_n$做$\sum$将其积掉,所以会有$n-1$个求和叠在一起:$\sum\sum\cdots\sum$,而它的每一个计算项即CRF的势函数又可以拆解为$n$个独立相乘的子项:$exp(W_i(y_{i-1},y_i\mid x))$(见矩阵形式那一节),所以这一节的概率计算问题同之前的HMM本质是一样的问题,可以利用前向或者后向的方法,将需要被多次计算的项的结果缓存下来,下面就直接写前向后向算法的求解过程

一.前向后向算法

前向

(1)初始化$y=start$步:

$$ \alpha_0(x)=[1,1,...,1]^T $$

(2)对$i=1,2,...,n+1$:

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

$\alpha_i(x)$表示从前往后截止到位置$i$时,第$i$个位置的非规范化概率分布(即对前面$i-1$步求了积分),显然$Z(x)=\alpha_n^T(x)\hat{1}=\alpha_{n+1}(x)[-1]$(假设$stop$的标签状态在第后一位),$\hat{1}$表示元素均为1的列向量

后向

(1)初始化$y=stop$步:

$$ \beta_{n+1}(x)=[1,1,...,1]^T $$

(2)对$i=n,n-1,...,0$有:

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

$\beta_i(x)$表示从后往前截止到位置$i$时,第$i$个位置的非规范化概率分布,同样$Z(x)=\hat{1}^T\beta_1(x)=\beta_0(x)[0]$(假设$start$的标签状态在第0位)

类似于HMM,前向后向也可以结合起来:

$$ Z(x)=\alpha_i^T(x)\beta_i(x),i=0,1,...,n+1 $$

二.概率计算

有了前向后向算法,对于$P(Y_i=y_i\mid x)$以及$P(Y_{i-1}=y_{i-1},Y_i=y_i\mid x)$的计算就也很方便了

$P(Y_i=y_i\mid x)$的计算

$$ P(Y_i=y_i\mid x)=\frac{\alpha_i(y_i\mid x)\beta_i(y_i\mid x)}{Z(x)} $$

$\alpha_i(y_i\mid x)$表示$\alpha_i(x)$中对应标签状态为$y_i$的非规范化概率,$\beta_i(y_i\mid x)$同理

$P(Y_{i-1}=y_{i-1},Y_i=y_i\mid x)$的计算

$$ P(Y_{i-1}=y_{i-1},Y_i=y_i\mid x)=\frac{a_{i-1}(y_{i-1}\mid x)M_i(y_{i-1},y_i\mid x)\beta_i(y_i\mid x)}{Z(x)} $$

三.期望值计算

下一节,参数的估计中需要用到特征函数关于条件分布以及联合分布的期望,这里同样需要用到前向后向的求解结果

特征函数$f_k$关于条件分布$P(Y\mid X)$的期望

$$ E_{y\sim P(Y\mid X)}[f_k]=\sum_yP(y\mid 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}(y_{i-1}\mid x)M_i(y_{i-1},y_i\mid x)\beta_i(y_i\mid x)}{Z(x)}\\ k=1,2,...,K $$

特征函数$f_k$关于联合分布$P(X,Y)$的期望

由于CRF是直接对$P(Y\mid X)$建模的,所有对于$P(X)$是无法得知,假设在知道$\tilde{P}(X)$的情况下:

$$ E_{x,y\sim 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_yP(y\mid 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}(y_{i-1}\mid x)M_i(y_{i-1},y_i\mid x)\beta_i(y_i\mid x)}{Z(x)}\\ k=1,2,...,K $$

四.小结一下计算过程

总结一下计算的流程:(代码放到后面一节参数的估计中实现)

(1)对所有$i=1,2,...,n+1$计算$M_i(x)$;

(2)在$M_i(x)$的基础上分别前向/后向扫描一次,得到$\alpha_i(x)$与$\beta_i(x)$以及$Z(x)$;

(3)最后在得到的$\alpha_i(x),\beta_i(x),M_i(x),Z(x)$的基础上计算条件概率以及数学期望

In [ ]: