这一节介绍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本质是一样的问题,可以利用前向或者后向的方法,将需要被多次计算的项的结果缓存下来,下面就直接写前向后向算法的求解过程
$$ \beta_{n+1}(x)=[1,1,...,1]^T $$(1)初始化$y=stop$步:
$$ \beta_i(x)=M_{i+1}(x)\beta_{i+1}(x) $$(2)对$i=n,n-1,...,0$有:
$\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)$的计算就也很方便了
$\alpha_i(y_i\mid x)$表示$\alpha_i(x)$中对应标签状态为$y_i$的非规范化概率,$\beta_i(y_i\mid x)$同理
由于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)$的基础上计算条件概率以及数学期望