Conditional Random Field

条件随机场（Conditional Random Field, CRF）属于“概率图模型”中的“无向图模型”。为简单起见，后文并不会讲解条件随机场的概率图模型框架，仅仅从例子出发介绍 CRF 的基本思路。

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

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

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

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

让我们通过更常见的词性标注的例子来了解更多条件随机场的细节。

词性标注（POS Tagging）的目标是使用类似 ADJECTIVE, NOUN, PREPOSITION, VERB, ADVERB, ARTICLE 的标签对句子（一连串的词或短语）进行标注。例如，句子“Bob drank coffee at Starbucks”的标注的结果就应该是“Bob (NOUN) drank (VERB) coffee (NOUN) at (PREPOSITION) Starbucks (NOUN)”。

那么就让我们建立一个条件随机场来为句子做词性标注。正如分类器所做，我们首先要设定一组特征方程。

在 CRF 中，每个特征函数（Feature Function） \(f_i\) 以下列信息作为输入：

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

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

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

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

接下来，为我们的每个特征函数 \(f_i\) 设置一个权重值 \(\lambda_i\) （后面会介绍如何通过训练学习得到这些权重值）。给定一个句子 \(s\) ，现在我们可以通过累加句中所有词加权后的特征来为 \(s\) 的打标结果 \(l\) 打分：
\[score(l \mid s) = \sum_{j=1}^m \sum_{i=1}^n \lambda_j f_j (s, i, l_i, l_{i-1})\]
第一个求和是对遍历特征方程的求和（共 \(m\) 个特征方程），而内层的求和是对句子里面的每一个位置 \(i\) 进行遍历的求和。

最终，我们通求指数与归一的方式将这些得分转换为 0、1 之间的概率值：
\[p(l \mid s) = \frac{exp[ score(l \mid s)]}{\sum_{l'} exp[ score(l' \mid 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}')]}\]

那么，这些特征方程都长什么样呢？词性标注（POS tagging）的特征方程例子如下：
\[f_1(s,i,l_i,l_{i-1}) = \begin{cases} 1 & \text{if} \; l_i = \text{ADVERB，并且第 i 个词以“-ly”结尾} \\ 0 & \text{otherwise} \\ \end{cases}\]
设上面特征的权重值为 \(\lambda_1\) ，如果它是取值较大的正数，则该特征表明我们倾向于将以“-ly”结尾的单词标记为 ADVERB。
\[f_2(s,i,l_i,l_{i-1}) = \begin{cases} 1 & \text{if} \; i=1,l_i = \text{VERB，并且句子以问号结尾} \\ 0 & \text{otherwise} \\ \end{cases}\]
设上面特征的权重值为 \(\lambda_2\) ，如果它是取值较大的正数，则该特征表明我们倾向于将问句里的第一个词标为 VERB（例如 “Is this a sentence beginning with a verb?”）。
\[f_3(s,i,l_i,l_{i-1}) = \begin{cases} 1 & \text{if} \; l_{i-1} = \text{ADJECTIVE，并且} \; l_i = \text{NOUN}\\ 0 & \text{otherwise} \\ \end{cases}\]
设上面特征的权重值为 \(\lambda_3\) ，如果它是正数，则表明形容词（ADJECTIVE）后面倾向于跟着名词（NOUN）。
\[f_4(s,i,l_i,l_{i-1}) = \begin{cases} 1 & \text{if} \; l_{i-1} = \text{PREPOSITION，并且} \; l_i = \text{PREPOSITION}\\ 0 & \text{otherwise} \\ \end{cases}\]
设上面特征的权重值为 \(\lambda_4\) ，如果它是负数，则表明介词（PREPOSITION）后面一般不会紧跟着一个介词，所以我们应该避免这样的标注。

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

假设我们有一组训练样本（包括句子与相关的词性标注标签结果），用“极大似然估计”可以求得 CRF 模型的权重 \(\boldsymbol{\lambda}\) ，具体的优化算法可以是“改进的迭代尺度法（Improved Iterative Scaling）”、“梯度下降法”或者“拟牛顿法”。

参考：统计学习方法，李航，11.4 节，条件随机场的学习算法

假设我们已经训练好了 CRF 模型，这时来了一个新的句子，我们应当如何去标注它？

最直接的方式，就是为每个可能的标注 \(l\) 计算 \(p(l \mid s)\) ，接着选取一种概率值最大的打标。然而，对一个大小为 \(k\) 标签组和一个长度为 \(m\) 的句子，有 \(k^m\) 种可能的打标方式，这就方式得检查的打标方式是指数级的个数。

一种更好的办法是使（线性链式）CRF 满足最佳子结构（Optimal Substructure）的属性，使得我们可以使用一种（多项式时间复杂度）动态规划算法去找到最佳标注，类似于 HMM 的 Viterbi 算法。

本文只是一篇转载（删除了部分内容）。

英文原文：Introduction to Conditional Random Fields
中文译文：条件随机场介绍（译）