CRF的学习笔记
本文是针对《统计学习方法》第11章相关部分的纠错和更为详细的说明。
条件随机场的矩阵形式
假设现有一个线性链条件随机场$P_w(y|x)=\frac{1}{Z(x)}\exp\sum_{k=1}^K w_k f_k(y,x)$，其中$Z(x)=\sum_y \exp \sum_{k=1}^K w_k f_k(y,x)$。
表示对给定观测序列x，相应的标记序列y的条件概率。引进特殊的起点和终点状态标记$y_0=start, y_{n+1}=stop$，这时条件随机场可以通过矩阵形式表示。
对观测序列x的每一个位置$i=1,2,\cdots ,n+1$上，定义一个m阶矩阵（m是标记y的取值个数，包括start和stop）
$$M_i(x)=[M_i(y_{i-1},y_i|x)] \
M_i(y_{i-1},y_i|x) = \exp(W_i(y_{i-1},y_i|x)) \
W_i(y_{i-1},y_i|x) = \sum_{k=1}^K w_k f_k(y_{i-1},y_i,x,i)$$
这样，给定观测序列x，标记序列y的非规范化概率可以通过n+1个矩阵的乘积$\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$表示，于是条件概率$P_w(y|x)$是：
$$P_w(y|x)=\frac{1}{Z_w(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$$
其中，$Z_w(x)$为规范化因子，是n+1个矩阵的乘积的(start, stop)元素：
$$Z_w(x)=\left( \prod_{i=1}^{n+1}M_i(x)\right)_{start,stop}$$
【例1】给定如下图所示的线性链条件随机场，
观测序列x，状态序列y，i=1,2,3，n=3，标记$y_i\in {1,2}$，假设$y_0=start=0, y_4=stop=3$，各个位置的随机矩阵$M_1(x),M_2(x),M_3(x),M_4(x)$分别为是
试求状态序列y以start为起点到stop为终点的所有路径的非规范化概率及规范化因子。
解：这部分其实非常好求，直接利用给定的公式得到
其中
$$Z_(x) =a_{01}b_{11}c_{11}+a_{01}b_{11}c_{12}+a_{01}b_{12}c_{21}+a_{01}b_{12}c_{22} + a_{02}b_{21}c_{11}+a_{02}b_{21}c_{12}+a_{02}b_{22}c_{21}+a_{02}b_{22}c_{22}$$
即所以路径非规范化概率和。
条件随机场的概率计算
前向-后向算法
这里的概率计算是指，对给定观测序列x及标记序列y，可以通过前向后向算法求出任意一个位置上$y_i$是某个标记的条件概$P(y_i=u|x)$，或任意连续的两个位置$y_{i-1},y_i$上的条件概率$P(y_{i-1}=u,y_i=v|x)$。
注意：不是求一条解码序列的概率。
前向向量
对每个位置$i=0,1,\cdots ,n+1$，定义前向向量$\alpha_i(x)$(行向量):
递推公式为
$$\alpha_i(y_i|x)=\alpha_{i-1}(y_{i-1}|x)M_i(y_{i-1},y_i|x) \text{, }(i=1,2,\cdots,n+1)$$
又可以表示为：
$$\alpha_i(x)=\alpha_{i-1}(x)M_i(x)$$
$\alpha_i(y_i|x)$表示在位置i的标记是$y_i$并且到位置i的前部分标记序列的非规范化概率，$y_i$可取的值有m个。
后向向量
同样，对每个位置$i=0,1,\cdots ,n+1$，定义后向向量$\beta_i(x)$(列向量):
递推公式为
$$\beta_i(y_i|x)=M_{i+1}(y_i,y_{i+1}|x)\beta_{i+1}(y_{i+1}|x) \text{, }(i=0,1,\cdots,n)$$
又可以表示为：
$$\beta_i(x)=\beta_{i+1}(x)M_{i+1}(x)$$
$\beta_i(y_i|x)$表示在位置i的标记是$y_i$并且到$i+1$到n的后部分标记序列的非规范化概率。
由前向后向向量的定义不难得到：
$$Z(x)=\alpha_{n+1}(x)\cdot \mathbf{1}=\mathbf{1}^T \cdot \beta_0(x)$$
这里，$\mathbf{1}$是元素均为1的m维列向量。
【例2】使用【例1】中的条件随机场，计算其前向向量和后向向量。
答：（1）计算前向向量
$\alpha_0(x)=[1,0,0,0]$
$\alpha_1(x) = \alpha_0(x)M_1(x)=[0,a_{01},a_{02}, 0]$
$\alpha_2(x) = \alpha_1(x)M_2(x)=[0,a_{01}b_{11}+a_{02}b_{21},a_{01}b_{12}+a_{02}b_{22}, 0]$
$\alpha_3(x) = \alpha_2(x)M_3(x)=[0,(a_{01}b_{11}+a_{02}b_{21}) \cdot c_{11}+(a_{01}b_{12}+a_{02}b_{22}) \cdot c_{21}, (a_{01}b_{11}+a_{02}b_{21}) \cdot c_{12}+(a_{01}b_{12}+a_{02}b_{22}) \cdot c_{22},0]$
$\alpha_4(x)=[0,0,0,Z(x)]$
(2)计算后向向量
$\beta_4(x) = [0,0,0,1]^T$
$\beta_3(x)=M_4(x)\beta_4(x)=[0,1,1,0]^T$
$\beta_2(x)=M_3(x)\beta_3(x)=[0,c_{11}+c_{12},c_{21}+c_{22},0]^T$
$\beta_1(x)=M_2(x)\beta_2(x)=[0,b_{11}(c_{11}+c_{12})+b_{12}(c_{21}+c_{22}),b_{21}(c_{11}+c_{12})+b_{22}(c_{21}+c_{22}),0]^T$
$\beta_0(x)=M_1(x)\beta_1(x)=[Z(x),0,0,0]^T$
概率计算
按照前向-后向向量的定义，很容易计算标记序列在位置i是标记$y_i$的条件概率和在位置i-1与i是标记$y_{i-1}$和$y_i$的条件概率：
$$P(Y_i=y_i|x)=\frac{\alpha_i(y_i|x) \beta_i(y_i|x)}{Z(x)}$$
$$P(Y_{i-1}=y_{i-1}, Y_i=y_i|x)=\frac{\alpha_{i-1}(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}$$
【例3】计算【例1】中条件随机场的条件概率$P(y_1=1|x)$和$P(y_1=1,y_2=2|x)$：
解：（1）求条件概率$P(y_1=1|x)=\frac{\alpha_1(y_1=1|x) \beta_1(y_1=1|x)}{Z(x)}$
已知:
$\alpha_1(x) =[0,a_{01},a_{02}, 0]$，
$\beta_1(x)=M_2(x)\beta_2(x)=[0,b_{11}(c_{11}+c_{12})+b_{12}(c_{21}+c_{22}),b_{21}(c_{11}+c_{12})+b_{22}(c_{21}+c_{22}),0]^T$则有：
$\alpha_1(y_1=1|x)=a_{01}$
$\beta_1(y_1=1|x)=b_{11}(c_{11}+c_{12})+b_{12}(c_{21}+c_{22})=b_{11}c_{11}+b_{11}c_{12}+b_{12}c_{21}+b_{12}c_{22}$
所以
$$P(y_1=1|x)=\frac{a_{01}(b_{11}c_{11}+b_{11}c_{12}+b_{12}c_{21}+b_{12}c_{22})}{Z(x)}$$
分子也即所有位置i=1上y为1的路径的非规范概率和。
（2）求条件概率$P(y_1=1,y_2=2|x)=\frac{\alpha_1(y_1=1|x)M_2(y_1=1,y_2=2|x)\beta_2(y_2=2|x)}{Z(x)}$
已知:$\alpha_1(y_1=1|x)=a_{01}$, $M_2(y_1=1,y_2=2|x)=b_{12}$, $\beta_2(y_2=2|x)=c_{21}+c_{22}$
所以
$$P(y_1=1,y_2=2|x)=\frac{a_{01} \cdot b_{12} \cdot (c_{21}+c_{22})}{Z(x)}$$