形式与定义

什么是条件随机场

条件随机场(conditional random field) 是给定随机变量X的条件下，随机变量Y 的马尔可夫随机场。常用于标注、实体识别等问题。

接下来我们通过命名实体识别来介绍crf。

先介绍实体识别：

给定一个句子：我爱*。实体识别的任务是从句子中识别出地点实体：*。

由于汉字不能直接作为模型的输入，我们先构造一个简单的实体识别的模型输入与label:

word_alphabet: {0: ‘我’, 1: ‘爱’, 2: ‘天’, 3: ‘安’, 4:‘门’}

label_alphabet: {0: b, 1: m, 2: e, 3: s,4: o, 5: ‘start’, 6: ‘pad’ }

label_alphabet中的b 代表实体的开始(begin)，m代表实体的中间部分(middle)，e代表尸体的结束(end)，o代表不是实体(none)，start、pad分别表示这个label序列的开始和结束。

所以有：

我们将构造的word_index作为模型的输入，label_index作为数据的label。我们希望实体识别模型能过通过word_index 预测出label_index，进而得到实体。

对于每一个字来说label有7种可能，为了数字化这些可能，我们从word_index到label_index设置一种分数，叫做状态分数，每一个字对应7种状态，如下图的红色箭头所示。

把状态分数记作：$\mu_{1-4}$μ1−4​，表示’爱’对应状态4的得分是多少。

同时因为这是一个序列，label_index 的状态应该应该还与前一个状态有关，比如状态4(o: 不是实体)的后面不可能是状态1(m：实体的中间部分)，也不可能是状态3(e:实体的结束)。所以这个时候需要一个转移分数代表前一个label到后一个label的分数。

把转移分数记作：$\lambda_{4-4}$λ4−4​，表示从状态4转移到状态4的得分是多少。 所以我们得到word_index=1到label_index=4的分数为$\mu_{1-4}+\lambda_{4-4}$μ1−4​+λ4−4​，CRF考虑了全局：将前一个分数累加到当前分数上，将其作为已经预测的序列的整体分数。所以当前得分为：
$scores = \mu_{0-4}+\lambda_{5-4} +\mu_{1-4}+\lambda_{4-4} + \mu_{2-0}+\lambda_{4-0} +\mu_{3-1}+\lambda_{0-1} + \mu_{4-3}+\lambda_{1-3}+\lambda_{3-6}$scores=μ0−4​+λ5−4​+μ1−4​+λ4−4​+μ2−0​+λ4−0​+μ3−1​+λ0−1​+μ4−3​+λ1−3​+λ3−6​
即：
$score(x,y) = \sum_{i=0}^n \lambda_{y_{i-1},y_i} + \sum_{i=0}^n \mu_{i,y_i}$score(x,y)=i=0∑n​λyi−1​,yi​​+i=0∑n​μi,yi​​

因为这个预测序列有很多种，种类为label的排列组合大小。其中只有一种组合是对的，我们想通过模型训练使得对的score的比重在总体的所有score的越大越好。而这个时候我们一般softmax化，即：
$P(y|x) = \frac{e^{score(x,y)}}{\sum_y e^{score(x,y)}}$P(y∣x)=∑y​escore(x,y)escore(x,y)​
上面这个实体识别中，X和Y有相同的图结构，其条件随机场的概率图模型应该长这样：

在一些问题种 X 和Y结构不同，其概率图模型如下图所示：

上面的例子有这样一个问题：有些组合根本不存在，如：状态4(o: 不是实体)的后面不可能是状态1(m：实体的中间部分)，也不可能是状态3(e:实体的结束), 因此我们不能单纯的求分数的相加，需要引入一些限制。即引入转移特征函数$t_k$tk​ 和状态特征函数$s_l$sl​ ,取值为0或者1，当满足条件时取值1，否则取值0。

说明：因为状态4(o: 不是实体)的后面不可能是状态1(m：实体的中间部分)，即：
$t_1 = t_1(y_{i-1}=4,y_i=1,x,i)=0, i=1,2\ldots6$t1​=t1​(yi−1​=4,yi​=1,x,i)=0,i=1,2…6
此时某一转移可能性的得分也更新为：$t_k\lambda_k$tk​λk​ 如果$t_k=0$tk​=0则此种转移不存在，转移得分为0，对于状态得分也存在这样的情况。

此时CRF的参数化形式定义如下：
$P(y|x)=\frac{1}{Z}\exp\left(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i+\sum_{i,l}\mu_ls_l(y_i,x,i)\right)$P(y∣x)=Z1​exp⎝⎛​i,k∑​λk​tk​(yi−1​,yi​,x,i+i,l∑​μl​sl​(yi​,x,i)⎠⎞​

$Z(x)=\sum_y exp \left(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)\right)$Z(x)=y∑​exp⎝⎛​i,k∑​λk​tk​(yi−1​,yi​,x,i)+i,l∑​μl​sl​(yi​,x,i)⎠⎞​

式中$t_k$tk​是定义在边上的特征函数和$s_l$sl​ 是定义在节点上的特征函数，$\lambda_k$λk​ 和$\mu_l$μl​ 是对应的权值。$Z(x)$Z(x) 是规范化因子，求和是在所有可能的输出序列上进行的 。

至此我们已经了解了CRF基本的思想了。

下面来看一个简单得例子深入了解CRF。

假设有一个标注问题，输入序列为$X=(X_1,X_2,X_3)$X=(X1​,X2​,X3​) ,输出的标记序列为$Y=(Y_1,Y_2,Y_3)$Y=(Y1​,Y2​,Y3​) ,$Y_i$Yi​ 的取值为1或2。假设$t_k,s_l$tk​,sl​ 和对应的权值$\lambda_k,\mu_l$λk​,μl​ 如下：
$\begin{aligned} t_1&=t_1(y_{i-1}=1,y_i=2,x,i),&i&=2,3,&\lambda_1&=1 \\ t_2&=t_2(y_{i-1}=1,y_i=1,x,i),&i&=2,&\lambda_2&=0.5\\ t_3&=t_3(y_{i-1}=2,y_i=1,x,i),&i&=3,&\lambda_3&=1\\ t_4&=t_4(y_{i-1}=2,y_i=1,x,i),&i&=2,&\lambda_4&=1\\ t_5&=t_5(y_{i-1}=2,y_i=2,x,i),&i&=3,&\lambda_5&=0.2\\ s_1&=s_1(y_i=1,x,i),&i&=1,&\mu_1&=1\\ s_2&=s_2(y_i=1,x,i),&i&=1,2,&\mu_2&=0.5\\ s_3&=s_3(y_i=1,x,i),&i&=2,3,&\mu_3&=0.8\\ s_4&=s_4(y_i=2,x,i),&i&=3&\mu_4&=0.5\\ \end{aligned}$t1​t2​t3​t4​t5​s1​s2​s3​s4​​=t1​(yi−1​=1,yi​=2,x,i),=t2​(yi−1​=1,yi​=1,x,i),=t3​(yi−1​=2,yi​=1,x,i),=t4​(yi−1​=2,yi​=1,x,i),=t5​(yi−1​=2,yi​=2,x,i),=s1​(yi​=1,x,i),=s2​(yi​=1,x,i),=s3​(yi​=1,x,i),=s4​(yi​=2,x,i),​iiiiiiiii​=2,3,=2,=3,=2,=3,=1,=1,2,=2,3,=3​λ1​λ2​λ3​λ4​λ5​μ1​μ2​μ3​μ4​​=1=0.5=1=1=0.2=1=0.5=0.8=0.5​
这里只注明特征值取1的条件，取值为0的省略。

对于给定的观测序列 x, 求标记序列为$y=(y_1,y_2,y_3)=(1,2,2)$y=(y1​,y2​,y3​)=(1,2,2) 的非规范化条件概率。

根据$t_k,s_l$tk​,sl​ 和对应的权值$\lambda_k,\mu_l$λk​,μl​ ，我们可以画出转移图如下：

图中红色路径的得分即为$y=(1,2,2)$y=(1,2,2) 的非规范化条件概率。即：
$P(y_1=1,y_2=2,y_3=2|x) \rightarrow e^{(\lambda_1t_1 + \lambda_5 t_5 +\mu_1s_1+\mu_2s_2 + \mu_4s_4)} = e^{3.2}$P(y1​=1,y2​=2,y3​=2∣x)→e(λ1​t1​+λ5​t5​+μ1​s1​+μ2​s2​+μ4​s4​)=e3.2
从公式的角度看：
$\begin{aligned} P(y|x) &\rightarrow \exp\left(\sum_{k=1}^5\lambda_k \sum_{i=2}^3t_k(y_{i-1},y_i,x,i)+\sum_{k=1}^4\mu_l\sum_{i=1}^3 s_l(y_i,x,i)\right) \end{aligned}$P(y∣x)​→exp(k=1∑5​λk​i=2∑3​tk​(yi−1​,yi​,x,i)+k=1∑4​μl​i=1∑3​sl​(yi​,x,i))​
其中：
$\begin{aligned} &\sum_{k=1}^5\lambda_k \sum_{i=2}^3t_k(y_{i-1},y_i,x,i) \\ =&\lambda_1 (t_1(y_{1},y_2,x,2)+t_1(y_{2},y_3,x,3)) + \lambda_2 (t_2(y_{1},y_2,x,2)+t_2(y_{2},y_3,x,3)) \\ &+\lambda_3 (t_3(y_{1},y_2,x,2)+t_3(y_{2},y_3,x,3))+\lambda_4 (t_4(y_{1},y_2,x,2)+t_4(y_{2},y_3,x,3)) \\ &+\lambda_5 (t_5(y_{1},y_2,x,2)+t_5(y_{2},y_3,x,3))\\ =&\lambda_1 t_1(y_{1}=1,y_2=2,x,2) + \lambda_5 t_5(y_{2}=2,y_3=2,x,3) \end{aligned}$==​k=1∑5​λk​i=2∑3​tk​(yi−1​,yi​,x,i)λ1​(t1​(y1​,y2​,x,2)+t1​(y2​,y3​,x,3))+λ2​(t2​(y1​,y2​,x,2)+t2​(y2​,y3​,x,3))+λ3​(t3​(y1​,y2​,x,2)+t3​(y2​,y3​,x,3))+λ4​(t4​(y1​,y2​,x,2)+t4​(y2​,y3​,x,3))+λ5​(t5​(y1​,y2​,x,2)+t5​(y2​,y3​,x,3))λ1​t1​(y1​=1,y2​=2,x,2)+λ5​t5​(y2​=2,y3​=2,x,3)​

$\begin{aligned} &\sum_{l=1}^4\mu_l\sum_{i=1}^3 s_l(y_i,x,i) \\ =&\mu_1(s_1(y_1,x,1)+s_1(y_2,x,2)+s_1(y_3,x,3))+\mu_2(s_2(y_1,x,1)+s_2(y_2,x,2)+s_2(y_3,x,3)) \\ &+\mu_3(s_3(y_1,x,1)+s_3(y_2,x,2)+s_3(y_3,x,3))+\mu_4(s_4(y_1,x,1)+s_4(y_2,x,2)+s_4(y_3,x,3))\\ =&\mu_1s_1(y_1=1,x,1)+\mu_2s_2(y_2=1,x,2)+\mu_4s_4(y_3=3,x,3) \end{aligned}$==​l=1∑4​μl​i=1∑3​sl​(yi​,x,i)μ1​(s1​(y1​,x,1)+s1​(y2​,x,2)+s1​(y3​,x,3))+μ2​(s2​(y1​,x,1)+s2​(y2​,x,2)+s2​(y3​,x,3))+μ3​(s3​(y1​,x,1)+s3​(y2​,x,2)+s3​(y3​,x,3))+μ4​(s4​(y1​,x,1)+s4​(y2​,x,2)+s4​(y3​,x,3))μ1​s1​(y1​=1,x,1)+μ2​s2​(y2​=1,x,2)+μ4​s4​(y3​=3,x,3)​

带入数值即可。

简化形式

上述公式中，有两个特征函数，两个权值，为了简化，我们首先将转移特征和状态特征及其权值用统一的符号表示。假设有$K_1$K1​ 个转移特征，$K_2$K2​个状态特征，$K=K_1+K_2$K=K1​+K2​，记：
$\color{red} f_k(y_{i-1},y_i,x,i)= \begin{cases} t_k(y_{i-1},y_i,x,i),&k=1,2,\dots,K_1\\ s_l(y_i,x,i),&k=K_1+l;l=1,2,\dots,K_2 \end{cases}$fk​(yi−1​,yi​,x,i)={tk​(yi−1​,yi​,x,i),sl​(yi​,x,i),​k=1,2,…,K1​k=K1​+l;l=1,2,…,K2​​
然后，对转和状态特征在各个位置$i$i求和，记作:
$f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i)=\begin{cases} \sum_{i=1}^n t_k(y_{i-1},y_i,x,i),&k<K_1\\ \sum_{i=1}^ns_l(y_i,x,i),&K_1<k<K \end{cases}$fk​(y,x)=i=1∑n​fk​(yi−1​,yi​,x,i)={∑i=1n​tk​(yi−1​,yi​,x,i),∑i=1n​sl​(yi​,x,i),​k<K1​K1​<k<K​
用$w_k$wk​表示特征$f_k(y,x)$fk​(y,x)的权值
$w_k= \begin{cases} \lambda_k,&k=1,2,\dots,K_1\\ \mu_l,&k=K_1+l;l=1,2,\dots,K_2 \end{cases}$wk​={λk​,μl​,​k=1,2,…,K1​k=K1​+l;l=1,2,…,K2​​

于是条件随机场可以表示为
$\begin{aligned} P(y|x)&=\frac{1}{Z(x)}\exp\sum_{k=1}^Kw_kf_k(y,x)\\ Z(x)&=\sum_y\exp\sum_{k=1}^Kw_kf_k(y,x) \end{aligned}$P(y∣x)Z(x)​=Z(x)1​expk=1∑K​wk​fk​(y,x)=y∑​expk=1∑K​wk​fk​(y,x)​
若以$w$w表示权值向量， 即
$w=(w_1,w_2,\dots,w_K)^T$w=(w1​,w2​,…,wK​)T
以$F$F表示全局特征向量，即
$F(y,x)=(f_1(y,x),f_2(y,x),\dots,f_K(y,x))^T$F(y,x)=(f1​(y,x),f2​(y,x),…,fK​(y,x))T
条件随机场可以表示成向量内积的形式
$\begin{aligned} P_w(y|x)&=\frac{\exp(w\cdot F(y,x))}{Z_w(x)}\\ Z_w(x)&=\sum_y\exp\left(w\cdot F(y,x)\right) \end{aligned}$Pw​(y∣x)Zw​(x)​=Zw​(x)exp(w⋅F(y,x))​=y∑​exp(w⋅F(y,x))​

矩阵形式

针对线性链条件随机场引入起点和终点状态标记$y_0=start,y_{n+1}=end$y0​=start,yn+1​=end， 这时$P_w(y|x)$Pw​(y∣x)可以矩阵形式表示。

对观测序列$x$x 的每一个位置$i = 1,2,\ldots,n+1$i=1,2,…,n+1 ,由于$y_{i-1}$yi−1​ 和$y_i$yi​ 在m个标记中取值，可以定义一个m 阶矩阵：
$\begin{aligned} M_i(x)&=\left[M_i(y_{i-1},y_i|x)\right]\\ \end{aligned}$Mi​(x)​=[Mi​(yi−1​,yi​∣x)]​
矩阵随机变量的元素为：
$\begin{aligned} M_i(y_{i-1},y_i|x)&=\exp\left(W_i(y_{i-1},y_i|x)\right)\\ W_i(y_{i-1},y_i|x)&=\sum_{k=1}^Kw_kf_k(y_{i-1},y_i|x) \end{aligned}$Mi​(yi−1​,yi​∣x)Wi​(yi−1​,yi​∣x)​=exp(Wi​(yi−1​,yi​∣x))=k=1∑K​wk​fk​(yi−1​,yi​∣x)​
举例：假设$y_1 \in \{1,2\}$y1​∈{1,2}
$\begin{aligned} W_2(y_{1},y_2|x)&=\sum_{k=1}^Kw_kf_k(y_{1},y_2|x) \\ &= \sum_{k=1}^{K_1}\lambda_kt_k(y_{1},y_2,x,2)+\sum_{l=1}^{K-K_1} \mu_ls_l(y_2,x,2) \end{aligned}$W2​(y1​,y2​∣x)​=k=1∑K​wk​fk​(y1​,y2​∣x)=k=1∑K1​​λk​tk​(y1​,y2​,x,2)+l=1∑K−K1​​μl​sl​(y2​,x,2)​
则可以求得：$W_2(y_{1}=1,y_2=1|x),W_2(y_{1}=1,y_2=2|x),W_2(y_{1}=2,y_2=1|x),W_2(y_{1}=2,y_2=2|x)$W2​(y1​=1,y2​=1∣x),W2​(y1​=1,y2​=2∣x),W2​(y1​=2,y2​=1∣x),W2​(y1​=2,y2​=2∣x)

取对数，构成$2\times2$2×2矩阵矩阵$M_2(x)$M2​(x)，分别表示$y_1$y1​ 转移到$y_2$y2​ 的可能性的大小。

这样给定观测序列$x$x，相应的标记序列$y$y 的非规范化概率可以通过该序列的n+1个矩阵原色的乘积$\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$∏i=1n+1​Mi​(yi−1​,yi​∣x) 表示。所以：
$P_w(y|x)=\frac{1}{Z_w(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$Pw​(y∣x)=Zw​(x)1​i=1∏n+1​Mi​(yi−1​,yi​∣x)
其中，$Z_w$Zw​为规范化因子，是n+1个矩阵的乘积的(start,stop)元素
$Z_w(x)=(M_1(x)M_2(x)\dots M_{n+1}(x))_{start,stop}$Zw​(x)=(M1​(x)M2​(x)…Mn+1​(x))start,stop​
注：$y_0=start, y_{n+1}=stop$y0​=start,yn+1​=stop 表示开始状态和终止状态，规范化因子$Z_w(x)$Zw​(x) 是以start为起点，end为终点通过状态的所有路径$y_1y_2\ldots y_n$y1​y2​…yn​ 的非规范化概率$\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$∏i=1n+1​Mi​(yi−1​,yi​∣x) 之和。

举例如下：

给定下图的线性链条件随机场，观测序列x,状态序列y,假设$y_0=start=1, y_{4}=stop=1$y0​=start=1,y4​=stop=1 。

各个位置的随机矩阵(可以理解为状态转移矩阵)为：
$\begin{aligned} M_1(x)= \begin{bmatrix} &a_{11}&a_{12}\\ &0&0 \end{bmatrix} &,M_2(x)= \begin{bmatrix} &b_{11}&b_{12}\\ &b_{21}&b_{22} \end{bmatrix} \\ M_3(x)= \begin{bmatrix} &c_{11}&c_{12}\\ &c_{21}&c_{22} \end{bmatrix} &,M_4(x)= \begin{bmatrix} &1&0\\ &1&0 \end{bmatrix} \end{aligned}$M1​(x)=[​a11​0​a12​0​]M3​(x)=[​c11​c21​​c12​c22​​]​,M2​(x)=[​b11​b21​​b12​b22​​],M4​(x)=[​11​00​]​
其中：
$M_i(x)=\left[\exp\left(\sum_{k=1}^Kw_kf_k(y_{i-1},y_i|x)\right)\right],i=1,2,\dots,n+1$Mi​(x)=[exp(k=1∑K​wk​fk​(yi−1​,yi​∣x))],i=1,2,…,n+1
例如$M_1(x)$M1​(x)：
$M_1(x)= \begin{bmatrix} &a_{11} =\exp\left(\sum_{k=1}^Kw_kf_k(y_{0}=1,y_1=1|x)\right)&a_{12}=\exp\left(\sum_{k=1}^Kw_kf_k(y_{0}=1,y_1=2|x)\right)\\ &a_{21}=\exp\left(\sum_{k=1}^Kw_kf_k(y_{0}=2,y_1=1|x)\right)&a_{22}=\exp\left(\sum_{k=1}^Kw_kf_k(y_{0}=2,y_2=1|x)\right) \end{bmatrix}$M1​(x)=⎣⎡​​a11​=exp(∑k=1K​wk​fk​(y0​=1,y1​=1∣x))a21​=exp(∑k=1K​wk​fk​(y0​=2,y1​=1∣x))​a12​=exp(∑k=1K​wk​fk​(y0​=1,y1​=2∣x))a22​=exp(∑k=1K​wk​fk​(y0​=2,y2​=1∣x))​⎦⎤​
显然，$a_{21}, a_{22}$a21​,a22​为0。

将上述矩阵相乘：
$\prod_{i=1}^{4}M_i(y_{i-1},y_i|x)$i=1∏4​Mi​(yi−1​,yi​∣x)
可以得到各个路径的非规范化概率为：
$a_{11}b_{11}c_{11},\quad a_{11}b_{11}c_{12},\quad a_{11}b_{12}c_{21},\quad a_{11}b_{12}c_{22},\quad \\ a_{12}b_{21}c_{11},\quad a_{12}b_{21}c_{12},\quad a_{12}b_{22}c_{21},\quad a_{12}b_{22}c_{22},\quad$a11​b11​c11​,a11​b11​c12​,a11​b12​c21​,a11​b12​c22​,a12​b21​c11​,a12​b21​c12​,a12​b22​c21​,a12​b22​c22​,
规范化因子，即最终计算结果左上角的元素，为：
$a_{11}b_{11}c_{11}+ a_{11}b_{11}c_{12}+ a_{11}b_{12}c_{21}+ a_{11}b_{12}c_{22}+ \\ a_{12}b_{21}c_{11}+ a_{12}b_{21}c_{12}+ a_{12}b_{22}c_{21}+ a_{12}b_{22}c_{22}$a11​b11​c11​+a11​b11​c12​+a11​b12​c21​+a11​b12​c22​+a12​b21​c11​+a12​b21​c12​+a12​b22​c21​+a12​b22​c22​

学习算法

条件随机场模型的学习通过拟牛顿法进行。

CRF的模型：
$\begin{aligned}P(y|x)&=\frac{1}{Z(x)}\exp\sum_{i=1}^nw_if_i(y,x)\\Z(x)&=\sum_y\exp\sum_{i=1}^nw_if_i(y,x) \end{aligned}$P(y∣x)Z(x)​=Z(x)1​expi=1∑n​wi​fi​(y,x)=y∑​expi=1∑n​wi​fi​(y,x)​
已知训练数据的经验概率分布$\widetilde {P}(x,y)$P(x,y)，条件概率分布的对数似然函数表示为：
$L_{\widetilde {P}}(P_w)=log \prod_{x,y}{P}(y|x)^{\widetilde {P}(x,y)} =\sum \limits_{x,y}\widetilde {P}(x,y)\log{P}(y|x)$LP​(Pw​)=logx,y∏​P(y∣x)P(x,y)=x,y∑​P(x,y)logP(y∣x)
所以
$\begin{aligned} L_{\widetilde {P}}(P_w)&=\sum \limits_{x,y}\widetilde {P}(x,y)\log{P}(y|x)\\ &=\sum \limits_{x,y}\widetilde {P}(x,y)\sum \limits_{i=1}^{n}w_if_i(x,y) -\sum \limits_{x,y}\widetilde{P}(x,y)\log{(Z_w(x))}\\ &=\sum \limits_{x,y}\widetilde {P}(x,y)\sum \limits_{i=1}^{n}w_if_i(x,y) -\sum \limits_{x,y}\widetilde{P}(x)P(y|x)\log{(Z_w(x))}\\ &=\sum \limits_{x,y}\widetilde {P}(x,y)\sum \limits_{i=1}^{n}w_if_i(x,y) -\sum \limits_{x}\widetilde{P}(x)\log{(Z_w(x))}\sum_{y}P(y|x)\\ &=\sum \limits_{x,y}\widetilde {P}(x,y)\sum \limits_{i=1}^{n}w_if_i(x,y) -\sum \limits_{x}\widetilde{P}(x)\log{(Z_w(x))} \end{aligned}$LP​(Pw​)​=x,y∑​P(x,y)logP(y∣x)=x,y∑​P(x,y)i=1∑n​wi​fi​(x,y)−x,y∑​P(x,y)log(Zw​(x))=x,y∑​P(x,y)i=1∑n​wi​fi​(x,y)−x,y∑​P(x)P(y∣x)log(Zw​(x))=x,y∑​P(x,y)i=1∑n​wi​fi​(x,y)−x∑​P(x)log(Zw​(x))y∑​P(y∣x)=x,y∑​P(x,y)i=1∑n​wi​fi​(x,y)−x∑​P(x)log(Zw​(x))​
以上推导用到了$\sum\limits_yP(y|x)=1$y∑​P(y∣x)=1

要极大化似然函数，即极小化$-L_{\widetilde {P}}(P_w)$−LP​(Pw​)。

所以学习的优化目标是：
$\min\limits_{w \in \R^n} f(w) =\sum \limits_{x}\widetilde{P}(x)\log{\sum_y\exp \left(\sum_{i=1}^nw_if_i(y,x)\right)} - \sum \limits_{x,y}\widetilde {P}(x,y)\sum \limits_{i=1}^{n}w_if_i(x,y)$w∈Rnmin​f(w)=x∑​P(x)logy∑​exp(i=1∑n​wi​fi​(y,x))−x,y∑​P(x,y)i=1∑n​wi​fi​(x,y)
其梯度函数是
$g(w) = \left( \frac{\partial f(w)}{\partial w_1},\frac{\partial f(w)}{\partial w_2},\ldots \frac{\partial f(w)}{\partial w_n}\right)^T$g(w)=(∂w1​∂f(w)​,∂w2​∂f(w)​,…∂wn​∂f(w)​)T
其中：
$\frac{\partial f(w)}{\partial w_i}=\sum \limits_{x,y}\widetilde{P}(x)P_w(y|x)f_i(y,x) - \sum \limits_{x,y}\widetilde {P}(x,y)f_i(x,y)$∂wi​∂f(w)​=x,y∑​P(x)Pw​(y∣x)fi​(y,x)−x,y∑​P(x,y)fi​(x,y)
向量化：
$\frac{\partial f(w)}{\partial w}=\sum \limits_{x,y}\widetilde{P}(x)P_w(y|x)f(y,x) - \sum \limits_{x,y}\widetilde {P}(x,y)f(x,y)$∂w∂f(w)​=x,y∑​P(x)Pw​(y∣x)f(y,x)−x,y∑​P(x,y)f(x,y)

条件随机场学习的BFGS算法：

输入：特征函数$f_1,f_2,\ldots,f_n$f1​,f2​,…,fn​ ；经验分布$\widetilde P(x,y)$P(x,y);

输出：最优参数$\hat w$w^ ; 最优模型$P_w(y|x)$Pw​(y∣x) 。

（1）选定初始点$w^{(0)}$w(0) 取 $\mathbf B_0$B0​ 为正定对称矩阵，$k=0$k=0。

（2）计算$g_k=g(w^{(k)})$gk​=g(w(k)) 。若$g_k=0$gk​=0 则停止计算，否则转(3)。

（3）由$B_kp_k=-g_k$Bk​pk​=−gk​ 求出$p_k$pk​

（4）一维搜索：求$\lambda_k$λk​ 使得：
$f(w^{(k)}+\lambda_kp_k)= \min\limits_{\lambda \geq 0}f(w^{(k)}+\lambda p_k)$f(w(k)+λk​pk​)=λ≥0min​f(w(k)+λpk​)
（5）置 $w^{(k+1)} = w^{(k)} + \lambda_k p_k$w(k+1)=w(k)+λk​pk​

（6）计算 $g_{k+1} = g(w^{(k+1)})$gk+1​=g(w(k+1)) ，若$g_{k+1} = 0$gk+1​=0 ，则停止计算，否则，按下式更新$B_{k+1}$Bk+1​:
$\mathbf B_{k+1} = \mathbf B_{k}+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{\mathbf B_k\delta_k \delta_k^T\mathbf B_k}{\delta_k^T\mathbf B_k\delta_k}$Bk+1​=Bk​+ykT​δk​yk​ykT​​−δkT​Bk​δk​Bk​δk​δkT​Bk​​
其中：
$y_k = g_{k+1} - g_k, \qquad\delta_k=w^{(k+1)} - w^{k}$yk​=gk+1​−gk​,δk​=w(k+1)−wk
（7）置 $k=k+1$k=k+1 , 转(3)

概率计算

即给定 linear-CRF的条件概率分布P(y|x)， 在给定输入序列x和输出序列y时，计算条件概率$P(y_i|x)$P(yi​∣x)和$P(y_i−1，y_i|x)$P(yi​−1，yi​∣x)以及对应的期望。

前向后向概率概述

要计算条件概率$P(y_i|x)$P(yi​∣x)和$P(y_{i-1}，y_i|x)$P(yi−1​，yi​∣x)，可以使用前向后向算法来完成。

前向概率

定义$\alpha_i(y_i|x)$αi​(yi​∣x)表示序列位置i的标记是$y_i$yi​时，在位置i之前的部分标记序列的非规范化概率。

而我们在上面定义了：
$M_i(y_{i-1},y_i |x) = exp(\sum\limits_{k=1}^Kw_kf_k(y_{i-1},y_i, x,i))$Mi​(yi−1​,yi​∣x)=exp(k=1∑K​wk​fk​(yi−1​,yi​,x,i))
用于计算在给定$y_{i-1}$yi−1​时，从$y_{i-1}$yi−1​转移到$y_i$yi​的非规范化概率。

那么在得知在位置$i+1$i+1处标记为$y_{i+1}$yi+1​时，位置$i+1$i+1之前的标记序列非规范化概率$\alpha_{i+1}(y_{i+1}|x)$αi+1​(yi+1​∣x)的递推公式：
$\alpha_{i+1}(y_{i+1}|x) = \alpha_i(y_i|x)M_{i+1}(y_{i+1},y_i|x) \;\; i=1,2,...,n+1$αi+1​(yi+1​∣x)=αi​(yi​∣x)Mi+1​(yi+1​,yi​∣x)i=1,2,...,n+1
特别的，在起点处，我们令：
$\alpha_0(y_0|x)= \begin{cases} 1 & {y_0 =start}\\ 0 & {else} \end{cases}$α0​(y0​∣x)={10​y0​=startelse​
由于在位置$i+1$i+1处，$y_{i+1}$yi+1​的可能取值有m种，我们用$\alpha_i(x)$αi​(x)表示这m个可能取值对应的前向向量：
$\alpha_i(x) = (\alpha_i(y_i=1|x), \alpha_i(y_i=2|x), ... \alpha_i(y_i=m|x))^T$αi​(x)=(αi​(yi​=1∣x),αi​(yi​=2∣x),...αi​(yi​=m∣x))T
则递推公式可以表示为：
$\alpha_{i+1}^T(x) = \alpha_i^T(x)M_{i+1}(x)$αi+1T​(x)=αiT​(x)Mi+1​(x)
后向概率

同样定义$\beta_i(y_i|x)$βi​(yi​∣x)表示序列位置i的标记是$y_i$yi​时，在位置i之后的部分(i+1到n的部分)标记序列的非规范化概率。

那么在得知$i+1$i+1处标记为$y_(i+1)$y(​i+1)时，位置i之后的部分标记序列的非规范化概率$\beta_i(y_i|x)$βi​(yi​∣x)的递推公式：
$\beta_{i}(y_{i}|x) = M_{i+1}(y_i,y_{i+1}|x)\beta_{i+1}(y_{i+1}|x)$βi​(yi​∣x)=Mi+1​(yi​,yi+1​∣x)βi+1​(yi+1​∣x)
特别的，在终点处定义：
$\beta_{n+1}(y_{n+1}|x)= \begin{cases} 1 & {y_{n+1} =stop}\\ 0 & {else} \end{cases}$βn+1​(yn+1​∣x)={10​yn+1​=stopelse​
如果用向量表示则有：
$\beta_i(x) = M_{i+1}(x)\beta_{i+1}(x)$βi​(x)=Mi+1​(x)βi+1​(x)
规范化因子$Z(x)$Z(x)的表达式为：
$Z(x) = \sum\limits_{c=1}^m\alpha_{n}(y_c|x) = \sum\limits_{c=1}^m\beta_{1}(y_c|x)$Z(x)=c=1∑m​αn​(yc​∣x)=c=1∑m​β1​(yc​∣x)
向量化的表示为：
$Z(x) = \alpha_{n}^T(x) \bullet \mathbf{1} = \mathbf{1}^T \bullet \beta_{1}(x)$Z(x)=αnT​(x)∙1=1T∙β1​(x)
其中，1是m维全1向量。

前向后向概率计算

有了前向后向概率的定义和计算方法，我们就很容易计算序列位置i的标记是$y_i$yi​时的条件概率$P(y_i|x)$P(yi​∣x)：
$P(y_i|x) = \frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{Z(x)} = \frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{ \alpha_{n}^T(x) \bullet \mathbf{1}}$P(yi​∣x)=Z(x)αiT​(yi​∣x)βi​(yi​∣x)​=αnT​(x)∙1αiT​(yi​∣x)βi​(yi​∣x)​
也容易计算序列位置i的标记是$y_i$yi​，位置$i-1$i−1的标记是$y_{i-1}$yi−1​时的条件概率$P(y_{i-1},y_i|x)$P(yi−1​,yi​∣x):
$\begin{aligned} P(y_{i-1},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)} \\ &= \frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{ \alpha_{n}^T(x) \bullet \mathbf{1}} \end{aligned}$P(yi−1​,yi​∣x)​=Z(x)αi−1T​(yi−1​∣x)Mi​(yi−1​,yi​∣x)βi​(yi​∣x)​=αnT​(x)∙1αi−1T​(yi−1​∣x)Mi​(yi−1​,yi​∣x)βi​(yi​∣x)​​

期望计算

有了上一节计算的条件概率，我们也可以很方便的计算联合分布$P(x,y)$P(x,y)与条件分布$P(y|x)$P(y∣x)的期望。

特征函数$f_k(x,y)$fk​(x,y)关于条件分布$P(y|x)$P(y∣x)的期望表达式是：
$\begin{aligned} E_{P(y|x)}[f_k] & = E_{P(y|x)}[f_k(y,x)] \\ & = \sum\limits_{i=1}^{n+1} \sum\limits_{y_{i-1}\;\;y_i}P(y_{i-1},y_i|x)f_k(y_{i-1},y_i,x, i) \\ & = \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)}{ \alpha_{n}^T(x) \bullet \mathbf{1}} \end{aligned}$EP(y∣x)​[fk​]​=EP(y∣x)​[fk​(y,x)]=i=1∑n+1​yi−1​yi​∑​P(yi−1​,yi​∣x)fk​(yi−1​,yi​,x,i)=i=1∑n+1​yi−1​yi​∑​fk​(yi−1​,yi​,x,i)αnT​(x)∙1αi−1T​(yi−1​∣x)Mi​(yi−1​,yi​∣x)βi​(yi​∣x)​​
同样可以计算联合分布$P(x,y)$P(x,y)的期望：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ E_{P(x,y)}[f_k…
假设一共有K个特征函数，则$k=1,2,...K$k=1,2,...K。

预测算法—维特比算法

预测问题也可以理解为解码问题：给定条件随机场的条件概率$P(y|x)$P(y∣x)和一个观测序列x,要求出满足$P(y|x)$P(y∣x)最大的序列y。这个解码算法最常用的还是和HMM解码类似的维特比算法。

对于我们linear-CRF中的维特比算法，我们定义一个局部状态$\delta_i(l)$δi​(l)，表示在位置$i$i标记$l$l各个可能取值(1,2…m)对应的非规范化概率的最大值。之所以用非规范化概率是，规范化因子$Z(x)$Z(x)不影响最大值的比较。根据$\delta_i(l)$δi​(l)的定义，我们递推在位置$i+1$i+1标记$l$l的表达式为：
$\delta_{i+1}(l) = \max_{1 \leq j \leq m}\{\delta_i(j) + \sum\limits_{k=1}^Kw_kf_k(y_{i} =j,y_{i+1} = l,x,i)\}\;, l=1,2,...m$δi+1​(l)=1≤j≤mmax​{δi​(j)+k=1∑K​wk​fk​(yi​=j,yi+1​=l,x,i)},l=1,2,...m
我们需要用另一个局部状态$\Psi_{i+1}(l)$Ψi+1​(l)来记录使$\delta_{i+1}(l)$δi+1​(l)达到最大的位置$i$i的标记取值，这个值用来最终回溯最优解，$\Psi_{i+1}(l)$Ψi+1​(l)的递推表达式为：
$\Psi_{i+1}(l) = arg\;\max_{1 \leq j \leq m}\{\delta_i(j) + \sum\limits_{k=1}^Kw_kf_k(y_{i} =j,y_{i+1} = l,x,i)\}\; ,l=1,2,...m$Ψi+1​(l)=arg1≤j≤mmax​{δi​(j)+k=1∑K​wk​fk​(yi​=j,yi+1​=l,x,i)},l=1,2,...m

维特比算法流程

linear-CRF模型维特比算法流程：

输入：模型的K个特征函数，和对应的K个权重。观测序列$x=(x_1,x_2,...x_n)$x=(x1​,x2​,...xn​)，可能的标记个数m

输出：最优标记序列$y^* =(y_1^*,y_2^*,...y_n^*)$y∗=(y1∗​,y2∗​,...yn∗​)

具体而言：

1，初始化：
$\delta_{1}(l) = \sum\limits_{k=1}^Kw_kf_k(y_{0} =start,y_{1} = l,x,i)\}\;, l=1,2,...m \\ \Psi_{1}(l) = start\;, l=1,2,...m$δ1​(l)=k=1∑K​wk​fk​(y0​=start,y1​=l,x,i)},l=1,2,...mΨ1​(l)=start,l=1,2,...m
2，对于$i=1,2...n-1$i=1,2...n−1进行递推：
$\delta_{i+1}(l) = \max_{1 \leq j \leq m}\{\delta_i(j) + \sum\limits_{k=1}^Kw_kf_k(y_{i} =j,y_{i+1} = l,x,i)\}\;, l=1,2,...m$δi+1​(l)=1≤j≤mmax​{δi​(j)+k=1∑K​wk​fk​(yi​=j,yi+1​=l,x,i)},l=1,2,...m

$\Psi_{i+1}(l) = arg\;\max_{1 \leq j \leq m}\{\delta_i(j) + \sum\limits_{k=1}^Kw_kf_k(y_{i} =j,y_{i+1} = l,x,i)\}\; ,l=1,2,...m$Ψi+1​(l)=arg1≤j≤mmax​{δi​(j)+k=1∑K​wk​fk​(yi​=j,yi+1​=l,x,i)},l=1,2,...m

3，$i$i迭代到n-1时停止：
$y_n^* = arg\;\max_{1 \leq j \leq m}\delta_n(j)$yn∗​=arg1≤j≤mmax​δn​(j)
4，回溯：
$y_i^* = \Psi_{i+1}(y_{i+1}^*)\;, i=n-1,n-2,...1$yi∗​=Ψi+1​(yi+1∗​),i=n−1,n−2,...1
最终得到的标记序列为：
$y^* =(y_1^*,y_2^*,...y_n^*)$y∗=(y1∗​,y2∗​,...yn∗​)

维特比算法实例

假设输入的都是三个词的句子，即$X=(X_1,X_2,X_3)$X=(X1​,X2​,X3​)，输出的词性标记为$Y=(Y_1,Y_2,Y_3)$Y=(Y1​,Y2​,Y3​)，其中$Y \in \{1(名词)，2(动词)\}$Y∈{1(名词)，2(动词)}。

这里只标记出取值为1的特征函数如下：
$t_1 =t_1(y_{i-1} = 1, y_i =2,x,i), i =2,3,\;\;\lambda_1=1\\ t_2 =t_2(y_1=1,y_2=1,x,2)\;\;\lambda_2=0.6\\ t_3 =t_3(y_2=2,y_3=1,x,3)\;\;\lambda_3=1\\ t_4 =t_4(y_1=2,y_2=1,x,2)\;\;\lambda_4=1\\ t_5 =t_5(y_2=2,y_3=2,x,3)\;\;\lambda_5=0.2\\ s_1 =s_1(y_1=1,x,1)\;\;\mu_1 =1\\ s_2 =s_2( y_i =2,x,i), i =1,2,\;\;\mu_2=0.5\\ s_3 =s_3( y_i =1,x,i), i =2,3,\;\;\mu_3=0.8\\ s_4 =s_4(y_3=2,x,3)\;\;\mu_4 =0.5$t1​=t1​(yi−1​=1,yi​=2,x,i),i=2,3,λ1​=1t2​=t2​(y1​=1,y2​=1,x,2)λ2​=0.6t3​=t3​(y2​=2,y3​=1,x,3)λ3​=1t4​=t4​(y1​=2,y2​=1,x,2)λ4​=1t5​=t5​(y2​=2,y3​=2,x,3)λ5​=0.2s1​=s1​(y1​=1,x,1)μ1​=1s2​=s2​(yi​=2,x,i),i=1,2,μ2​=0.5s3​=s3​(yi​=1,x,i),i=2,3,μ3​=0.8s4​=s4​(y3​=2,x,3)μ4​=0.5
求标记(1,2,2)的最可能的标记序列。
状态转移图如下：

首先初始化:
$\delta_1(1) = \mu_1s_1 = 1\;\;\;\delta_1(2) = \mu_2s_2 = 0.5\;\;\;\Psi_{1}(1) =\Psi_{1}(2) = start$δ1​(1)=μ1​s1​=1δ1​(2)=μ2​s2​=0.5Ψ1​(1)=Ψ1​(2)=start
接下来开始递推，先看位置2的：
$\begin{aligned} \delta_2(1) &= max\{\delta_1(1) + t_2\lambda_2+\mu_3s_3, \delta_1(2) + t_4\lambda_4+\mu_3s_3 \} \\ &= max\{1+0.6+0.8,0.5+1+0.8\} \\ &=2.4\;\;\;\\ \end{aligned}$δ2​(1)​=max{δ1​(1)+t2​λ2​+μ3​s3​,δ1​(2)+t4​λ4​+μ3​s3​}=max{1+0.6+0.8,0.5+1+0.8}=2.4​

$\Psi_{2}(1) =1$Ψ2​(1)=1

$\begin{aligned} \delta_2(2) &= max\{\delta_1(1) + t_1\lambda_1+\mu_2s_2, \delta_1(2) + \mu_2s_2\}\\& = max\{1+1+0.5,0.5+0.5\} \\&=2.5\;\;\; \end{aligned}$δ2​(2)​=max{δ1​(1)+t1​λ1​+μ2​s2​,δ1​(2)+μ2​s2​}=max{1+1+0.5,0.5+0.5}=2.5​

$\Psi_{2}(2) =1$Ψ2​(2)=1

再看位置3的：
$\begin{aligned} \delta_3(1) &= max\{\delta_2(1) +\mu_3s_3, \delta_2(2) + t_3\lambda_3+\mu_3s_3\} \\&= max\{2.4+0.8,2.5+1+0.8\} \\&=4.3 \end{aligned}$δ3​(1)​=max{δ2​(1)+μ3​s3​,δ2​(2)+t3​λ3​+μ3​s3​}=max{2.4+0.8,2.5+1+0.8}=4.3​

$\Psi_{3}(1) =2$Ψ3​(1)=2

$\begin{aligned} \delta_3(2) &= max\{\delta_2(1) +t_1\lambda_1 + \mu_4s_4, \delta_2(2) + t_5\lambda_5+\mu_4s_4\} \\&= max\{2.4+1+0.5,2.5+0.2+0.5\} \\&=3.9 \end{aligned}$δ3​(2)​=max{δ2​(1)+t1​λ1​+μ4​s4​,δ2​(2)+t5​λ5​+μ4​s4​}=max{2.4+1+0.5,2.5+0.2+0.5}=3.9​

$\Psi_{3}(2) =1$Ψ3​(2)=1

最终得到$y_3^* =\arg\;max\{\delta_3(1), \delta_3(2)\}$y3∗​=argmax{δ3​(1),δ3​(2)}递推回去，得到：
$y_2^* = \Psi_3(1) =2\;\;y_1^* = \Psi_2(2) =1$y2∗​=Ψ3​(1)=2y1∗​=Ψ2​(2)=1
即最终的结果为$(1,2,1)$(1,2,1)，即标记为(名词，动词，名词)。

LR & CRF & HMM

说明：

第一行是生成模型，第二行是判别模型

第一行是有向图模型，第二行是无向图模型

HMM可以看成朴素贝叶斯的扩展模型

CRF可以看成逻辑回归的扩展模型