Conditional Random Field

Table of Contents

1 条件随机场(CRF)简介

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

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

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

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

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

2 词性标注(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)”。

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

3 CRF的特征函数(Feature Functions in a CRF)

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

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

输出的是一个实数值(一般是0或1)。

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

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

4 从特征到概率(Features to Probabilities)

接下来,为我们的每个特征函数 \(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}')]}\]

5 特征方程示例(Example Feature Functions)

那么,这些特征方程都长什么样呢?词性标注(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)后面一般不会紧跟着一个介词,所以我们应该避免这样的标注。

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

6 权重学习(Learing Weights)

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

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

7 找到最佳标注(Finding the Optimal Labeling)

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

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

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

8 参考

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

英文原文:Introduction to Conditional Random Fields
中文译文:条件随机场介绍(译)


Author: cig01

Created: <2016-12-10 Sat 00:00>

Last updated: <2018-01-02 Tue 14:02>

Creator: Emacs 25.3.1 (Org mode 9.1.4)