转载链接：https://zhuanlan.zhihu.com/p/25558273
词性标注任务
词性标注（POS Tagging）的目标是使用类似ADJECTIVE, NOUN, PREPOSITION, VERB, ADVERB, ARTICLE的标签对句子（一连串的词或短语）进行打签。
例如，句子“Bob drank coffee at Starbucks”的标注的结果就应该是“Bob (NOUN) drank (VERB) coffee (NOUN) at (PREPOSITION) Starbucks (NOUN)”。
那么就让我们建立一个条件随机场来为句子做词性标注。正如分类器所做，我们首先要设定一组特征方程 $f_i$。
CRF的特征函数
在CRF中，每个特征函数都要以下列信息作为输入：
- 一个句子s
- 词在句子中的位置i
- 当前词的标签$l_i$
- 前一个词的标签$l_{i-1}$
可以表示为$f_j(s, i, l_i, l_{i - 1})$
特征函数的输出的是一个实数值（尽管这些值一般是0或1）。
（注意：通过限制我们的特征只依赖于当前与之前的词的标签，而不是句子中的任意标签，实际上我建立了一种特殊的线性CRF，为简单起见，本文不讨论更广义的CRF）
例如，某个特征函数就可以用来衡量当上一个词是“very”时，当前词有多少程度可以被标为一个形容词。
从特征到概率
接下来，我们需要为每个特征函数$f_j$设置一个权重$\lambda_j$
给定一个句子s，现在可以通过累加句中所有词的加权的特征为s的打标结果$l$打分
$$ score(l|s))=\sum_{j=1}^{m}\sum_{i=1}^{n} \lambda_{j}f_{j}(s,i,l_{i}^{‘},l_{i-1}^{‘}) $$
其中，第一个求和是对遍历特征函数j的求和，内层的求和是对句子中的每个位置i进行遍历求和。
最终，我们通过指数和归一化的方法将转换这些得分为0，1的概率值。
特征函数示例
我们以POS tagging任务为例：
- $f_1(s, i, l_i, l_{i-1})=1$ 如果l_i=ADVERB, 且第i个词是以“-ly”结尾；否则为0
- 如果该特征的权重值 $\lambda_{1}$ 为取值较大的正数，则该特征表明我们倾向于将以 -ly 结果的单词标记为ADVERB。
- $f_{2}(s,i,l_{i},l_{i-1})=1$ if $i=1, l_{i} = VERB$ 且句子以问号结尾；否则，为0。
- 同样，如果该特征的权重值 $\lambda_{2}$ 为取值较大的正数，就偏向于将问句里的第一个词标为VERB（例如 “Is this a sentence beginning with a verb?”）。
- $f_{3}(s,i,l_{i},l_{i-1})=1 if l_{i-1} = ADJECTIVE 且 l_{i}= NOUN$；否则，为0。
- 同样，如果权重值为正，表明形容词后面倾向于跟着名词。
- $f_{4}(s,i,l_{i},l_{i-1})=1 ifl_{i-1} = PREPOSITION$ 且$l_{i}=PRE POSITION$。
- 如果该特征方程的权重值 $\lambda _{4}$ 为负，意味着介词后面一般不会紧跟着一个介词，所以我们应该避免这样的标注。
就是这样！总结起来就是：为了构建一个条件随机场，你需要定义一连串的特征方程（以整个句子、当前位置和相近位置的标签为输入），然后为它们赋值，再做累加，如果必要，在最后将累加得分转换为一个概率值。
看起来像是逻辑回归(Smells like Logistic Regression…)
CRF的概率公式
看起来会有些眼熟.
这是因为实际上CRF就是序列版本的逻辑回归（logistic regression）。正如逻辑回归是分类问题的对数线性模型，CRF是序列标注问题的对数线性模型。
看起像HMM
回顾隐马可夫模型（Hidden Markov Model）它是另一种用于词性标注（和序列标注）的模型 。CRF使用任意的特征函数组用于得到标注得分，HMM采用生成方式进行标注， 定义如下：
$p(l,s)=p(l_{1})\prod_{i}p(l_{i}|l_{i-1})p(w_{i}|l_{i})$
其中
$p(l_{i}|l_{i-1})$ 为 转移概率（例如，一个介词后面紧跟着一个名词的概率）。
$p(w_{i}|l_{i})$ 为 发射概率（例如，当已知是名词，会出现“dad”的概率）。
那么，HMM与CRF比较会是如何? CRF更加强大- CRF可以为任何HMM能够建模的事物建模，甚至更多。以下的介绍就可以说明这一点。
设HMM概率的对数为log p(l,s)=log p(l_{0})+\sum_{i}log p(l_{i}|l_{i-1})+\sum_{i}log p(w_{i}|l_{i})。如果我们将这些对数概率值看作二进制的转换指示符与发射指示符的权重，这就完全具备了CRF的对数线性形式。
也就是说，我们可以对任意的HMM建立等价的CRF：
为每个HMM的转换概率 $p(l_{i}=y|l_{i-1}=x)$，定义一组转换形式为$f_{x,y}(s,i,l_{i},l_{i-1})=1$ if $l_{i}=y$ 且$l_{i-1}=x$的CRF转换特征。给定每个特征权重值为$w_{x,y)=log p(l_{i}=y|l_{i-1}=x)$。
类似的，为每个HMM的发射概率 $p(w_{i}=z|l_{i}=x)$，定义一组CRF发射特征形如 $g_{x,y}(s,i,l_{i},l_{i-1})$ if $w_{i}=z$且 $l_{i}=x$。给定每个特征的权重值为$w_{x,z}=log p(w_{i}=z|l_{i}=x)$。
这样，使用这些特征方程由CRF计算得到的 p(l|s)是与相应的HMM计算得到的得分是精确成正比的，所以每个HMM都存在某个对等的CRF。
但是，出于以下两个原因，CRF同样可以为更为丰富的标签分布建模：
CRF可以定义更加广泛的特征集。 而HMM在本质上必然是局部的（因为它只能使用二进制的转换与发射特征概率，导致每个词仅能依赖当前的标签，而每个标签仅依赖于上一个标签），而CRF就可以使用更加全局的特征。例如，在上文提到的词性标注特征中就有一个特征，如果句子的结尾包含问号，那么句子中的第一个字为动词（VERB）的概率会增加。
CRF可以有任意权重值。HMM的概率值必须满足特定的约束（例如，$0<=p(w_{i}|l_{i})<=1$，$\sum_{w}p(w_{i}=w|l_{i})=1$,而CRF没有限制（例如，$log p(w_{i}|l_{i})$可以是任意它想要的值）。
权重学习（Learing Weights）
让我们回到如何学习CRF的权重这个问题。有一种方式是使用梯度上升（gradient ascent）。
假设我们有一组训练样本（包括句子与相关的词性标注标签结果）。一开始，为我们的CRF模型随机初始化权重值。为了使这些随机初始的权重值最终调整为正确的值 ，遍历每个训练样本，执行如下操作：
遍历每个特征函数 f_{i} ，并为\lambda_{i} 计算训练样本的对数概率梯度值:
注意，梯度公式中的第一项是特征f_{i} 在正确标注下的贡献，梯度公式中的第二项是特征 f_{i} 在当前模型中的贡献。这就是你所期望的梯度上升所要采用的公式。
将$\lambda_{i}$ 朝着梯度方向移动：
$$\lambda_{i} = \lambda_{i}+\alpha [\sum_{j=1}^{m}f_{i}(s,j,l_{j},l_{j-1})-\sum_{l’}p(l’|s)\sum_{j=1}^{m}f_{i}(s,j,l_{j}^{‘},l_{j-1}^{‘})]$$
其中α是某个学习率（learning rate）。
重复上述步骤，直到达到某种停止条件（例如，更新值已低于某个阈值）。
换而言之，每一步都是在抽取，当前模型与我们想要学习到的模型的差异，然后将$\lambda_{i}$ 朝正确的方向移动。
找到最佳标注（Finding the Optimal Labeling）
假设我们已经训练好了CRF模型，这时来了一个新的句子，我们应当如何去标注它？
最直接的方式，就是为每个可能的标注 l计算 p(l|s)， 接着选取一种概率值最大的打标。然而，对一个大小为k标签组和一个长度为m的句子，有 k^{m}种可能的打标方式，这就方式得检查的打准方式是指数级的个数。
一种更好的办法是使（线性链式）CRF满足最佳子结构（optimal substructure）的属性，使得我们可以使用一种（多项式时间复杂度）动态规划算法去找到最佳标注，类似于HMM的Viterbi算法。
更有趣的应用(A More Interesting Application)
好吧，词性标注略显无聊，除了它还有很多种其他的标注方法。那现实中什么时候还会用到CRF呢？
假设你想要从Twitter上了解人们想要在圣诞节上得到什么样的礼物：
如何才能找出哪些词代表礼物呢？
为了收集到上图中的数据，我只是简单的去匹配形如“I want XXX for Christmas” 和 “I got XXX for Christmas”的句式。然而，一个更加复杂的CRF变种就可以做GIFT词标注（甚至可以添加其也的类似GIFT-GIVER、GIFT-RECEIVER的标签以获取更丰富的信息），将其转换为词性标注问题来看待。我们可以基于类似“如果上一个词是一个GITF-RECIVER且它的前一个词是‘gave’，那这个词就是一个GITF”或者“如果后面紧跟着的两个词是’for Christmas’，那么这个词就是一个GIFT”的规则去构建特征。