条件随机场介绍（译）Introduction to Conditional Random Fields

译者序

该文是对CRF算法的介绍，介绍清晰、浅显，不对初学者设置过多的理解障碍。而且文章最后提到的学习资料，我看过部份，值得推荐。
原文链接：http://blog.echen.me/2012/01/03/introduction-to-conditional-random-fields/

正文序

想象一下，你有 Justin Bieber 一天生活中的一连串快照，你想在这些照片上面打上活动内容的标签（吃睡、睡觉、开车等）。你会怎么做？

一种方式是忽略这些快照的本质，建立一个图片分类器。举个例子，事先给定一个月的打标快照，你可能会了学到在早上6点拍的较暗的照片很可能是在睡觉，有很多明亮颜色的照片，很可以是关于跳舞，照片中有车那应该是在开车等等。

然而，忽略顺序关联，你会丢失很多信息。例如，如果你看到一张嘴张的特写照片，那它应该打标成吃饭还是唱歌呢？如果上一张 Justin Bieber 的照片中他在吃饭或者做菜，那当前这张照片很可能是他在吃饭；但如果上一张照片中 Justin Bieber 在唱歌或者跳舞，那这张很可能是在说他也在唱歌。

因此，为了提高我们打标的准确率，我们应该结合参考相近照片，这正是条件随机场（condition random field）所做的事情

词性标注（Part-of-Speech Tagging）

让我们通过更常用的词性标注的例子来了解更多细节。

词性标注（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的特征函数（Feature Functions in a CRF）

在CRF中， 每个特征函数以下列信息作为输入：

• 一个句子 s
• 词在句子中的位置 i
• 当前词的标签 $l_{i}$
• 前一个词的标签 $l_{i-1}$

输出的是一个实数值（尽管这些值一般是0或1）。

（注意：通过限制我们的特征只依赖于当前与之前的词的标签，而不是句子中的任意标签，实际上我建立了一种特殊的线性CRF，为简单起见，本文不讨论更广义的CRF）

例如，某个特征函数就可以用来衡量当上一个词是“very”时，当前词有多少程度可以被标为一个形容词。

从特征到概率(Features to Probabilities)

接下来，为我们的每个特征函数 $f_{i}$ 设置一个权重值 $λ_{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之间的概率值:

$$p(l|s)=\frac{exp[score(l|s)]}{\sum_{l'}exp[score(l'|s)]}=\frac{exp[\sum_{j=1}^{m}\sum_{i=1}^{n} \lambda_{j}f_{j}(s,i,l_{i},l_{i-1})]}{\sum_{{l}'}exp[\sum_{j=1}^{m}\sum_{i=1}^{n}\lambda_{j}f_{j}(s,i,l_{i}^{'},l_{i-1}^{'})] }$$

特征方程示例（Example Feature Functions）

那么，这些特征方程都长什么样呢？词性标注（POS tagging）的特征例子如下：

• $f_{1}(s,i,l_{i},l_{i-1})=1$ if $l_{i}$ = ADVERB 且第i个词以“-ly”结尾；否则，为0。

  • 如果该特征的权重值 $λ{1}$ 为取值较大的正数，则该特征表明我们倾向于将以 -ly 结果的单词标记为ADVERB。

• $f_{2}(s,i,l_{i},l_{i-1})=1$ if $i=1$, $l_{i}$ = VERB 且句子以问号结尾；否则，为0。

  • 同样，如果该特征的权重值 $λ_{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$ if $l_{i-1}$ = PREPOSITION 且 $l_{i}$ =PRE POSITION。

  • 如果该特征方程的权重值 $λ_{4}$ 为负，意味着介词后面一般不会紧跟着一个介词，所以我们应该避免这样的标注。

就是这样！总结起来就是：为了构建一个条件随机场，你需要定义一连串的特征方程（以整个句子、当前位置和相近位置的标签为输入），然后为它们赋值，再做累加，如果必要，在最后将累加得分转换为一个概率值。

看起来像是逻辑回归(Smells like Logistic Regression...)

CRF的概率公式 $p(l|s)=\frac{exp[score(l|s)]}{\sum_{l'}exp[score(l'|s)]} = \frac{exp[\sum_{j=1}^{m}\sum_{i=1}^{n} \lambda_{j}f_{j}(s,i,l_{i},l_{i-1})]}{\sum_{l'}exp[\sum_{j=1}^{m}\sum_{i=1}^{n} \lambda_{j}f_{j}(s,i,l_{i}^{'},l_{i-1}^{'})]}$ 看起来会有些眼熟.
这是因为实际上CRF就是序列版本的逻辑回归（logistic regression）。正如逻辑回归是分类问题的对数线性模型，CRF是序列标注问题的对数线性模型。

看着像HMM（Looks like HMMs…）

回顾隐马可夫模型（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}$ ，并为 $λ_{i}$ 计算训练样本的对数概率梯度值:

$$\frac{\partial }{\partial w_{j}} log p(l|s)=\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}^{'})$$

• 注意，梯度公式中的第一项是特征 $f_{i}$ 在正确标注下的贡献，梯度公式中的第二项是特征 $f_{i}$ 在当前模型中的贡献。这就是你所期望的梯度上升所要采用的公式。
• 将 $λ_{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）。

• 重复上述步骤，直到达到某种停止条件（例如，更新值已低于某个阈值）。

换而言之，每一步都是在抽取，当前模型与我们想要学习到的模型的差异，然后将 $λ_{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”的规则去构建特征。

最后（Fin）

我将以下列随想做为结束：

• 我刻意跳过了条件随机场的图模型框架，因为我不觉这些会对CRF的初次理解有什么帮助。但如果你想了解更多，Daphne Koller有从一月开始的免费的线上图模型教程。
• 或者，你对CRF在NLP上的许多应用(类似词性标注、命名实体抽取)更感兴趣，Manning和Jurafsky正在提供这样的NLP课程。
• 我还对CRF:HMM与Logistic Regression:Naive Bayes之间做了一些对比。下图（来自于 Sutton 和 McCallum的 introduction to conditional random fields）就是对此的总结，同时也展示了CRF的图模型特性：

20161127首发于3dobe.com
本站链接：http://3dobe.com/archives/255/