条件随机场CRF

1 条件随机场CRF：从条件随机场到线性链条件随机场

条件随机场(Conditional Random Fields, 以下简称CRF)是给定一组输入序列条件下另一组输出序列的条件概率分布模型，在自然语言处理中得到了广泛应用。

1.1 什么样的问题需要CRF模型

这里举一个简单的例子：假设有Bob一天从早到晚的一系列照片，Bob想考考我们，要我们猜这一系列的每张照片对应的活动，比如: 工作的照片，吃饭的照片，唱歌的照片等等。一个比较直观的办法就是，我们找到Bob之前的日常生活的一系列照片，然后找Bob问清楚这些照片代表的活动标记，这样我们就可以用监督学习的方法来训练一个分类模型，比如逻辑回归，接着用模型去预测这一天的每张照片最可能的活动标记。

这种办法虽然是可行的，但是却忽略了一个重要的问题，就是这些照片之间的顺序其实是有很大的时间顺序关系的，而用上面的方法则会忽略这种关系。比如我们现在看到了一张Bob闭着嘴的照片，那么这张照片我们怎么标记Bob的活动呢？比较难去打标记。但是如果我们有Bob在这一张照片前一点点时间的照片的话，那么这张照片就好标记了。如果在时间序列上前一张的照片里Bob在吃饭，那么这张闭嘴的照片很有可能是在吃饭咀嚼。而如果在时间序列上前一张的照片里Bob在唱歌，那么这张闭嘴的照片很有可能是在唱歌。

为了让我们的分类器表现的更好，可以在标记数据的时候，可以考虑相邻数据的标记信息。这一点，是普通的分类器难以做到的。而这一块，也是CRF比较擅长的地方。

在实际应用中，自然语言处理中的词性标注(POS Tagging)就是非常适合CRF使用的地方。词性标注的目标是给出一个句子中每个词的词性（名词，动词，形容词等）。而这些词的词性往往和上下文的词的词性有关，因此，使用CRF来处理是很适合的，当然CRF不是唯一的选择，也有很多其他的词性标注方法。

1.2 从随机场到马尔科夫随机场

首先，我们来看看什么是随机场。“随机场”的名字取的很玄乎，其实理解起来不难。随机场是由若干个位置组成的整体，当给每一个位置中按照某种分布随机赋予一个值之后，其全体就叫做随机场。还是举词性标注的例子：假如有一个十个词形成的句子需要做词性标注。这十个词每个词的词性可以在已知的词性集合（名词，动词...)中去选择。当我们为每个词选择完词性后，这就形成了一个随机场。

了解了随机场，我们再来看看马尔科夫随机场。马尔科夫随机场是随机场的特例，它假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关，和与其不相邻的位置的赋值无关。继续举十个词的句子词性标注的例子：　如果我们假设所有词的词性只和它相邻的词的词性有关时，这个随机场就特化成一个马尔科夫随机场。比如第三个词的词性除了与自己本身的位置有关外，只与第二个词和第四个词的词性有关。　

1.3 从马尔科夫随机场到条件随机场

CRF是马尔科夫随机场的特例，它假设马尔科夫随机场中只有X和Y两种变量，X一般是给定的，而Y一般是在给定X的条件下的输出。这样马尔科夫随机场就特化成了条件随机场。在我们十个词的句子词性标注的例子中，X是词，Y是词性。因此，如果我们假设它是一个马尔科夫随机场，那么它也就是一个CRF。

对于CRF，给出准确的数学语言描述：设X与Y是随机变量，P(Y|X)是给定X时Y的条件概率分布，若随机变量Y构成的是一个马尔科夫随机场，则称条件概率分布P(Y|X)是条件随机场。

1.4 从条件随机场到线性链条件随机场

注意在CRF的定义中，我们并没有要求X和Y有相同的结构。而实现中，我们一般都假设

X和Y有相同的结构，即:

一般考虑如下图所示的结构：X和Y有相同的结构的CRF就构成了线性链条件随机场(Linear chain Conditional Random Fields,以下简称 linear-CRF)。

在十个词的句子的词性标记中，词有十个，词性也是十个，因此，如果假设它是一个马尔科夫随机场，那么它也就是一个linear-CRF。

我们再来看看 linear-CRF的数学定义：

设均为线性链表示的随机变量序列，在给定随机变量序列 $X$ 的情况下，随机变量 $Y$ 的条件概率分布 $P(Y|X)$ 构成条件随机场，即满足马尔科性：

则称为线性链条件随机场。

1.5 线性链条件随机场的参数化形式

对于上一节讲到的linear-CRF，我们如何将其转化为可以学习的机器学习模型呢？

这是通过特征函数和其权重系数来定义的。什么是特征函数呢？

在linear-CRF中，特征函数分为两类，第一类是定义在Y节点上的节点特征函数，这类特征函数只和当前节点有关，记为：

其中， $L$ 是定义在该节点的节点特征函数的总个数， $i$ 是当前节点在序列的位置。

第二类是定义在Y上下文的局部特征函数，这类特征函数只和当前节点和上一个节点有关，记为：

其中 $K$ 是定义在该节点的局部特征函数的总个数， $i$ 是当前节点在序列的位置。之所以只有上下文相关的局部特征函数，没有不相邻节点之间的特征函数，是因为linear-CRF满足马尔科夫性。

无论是节点特征函数还是局部特征函数，它们的取值只能是0或者1。即满足特征条件或者不满足特征条件。同时，我们可以为每个特征函数赋予一个权值，用以表达我们对这个特征函数的信任度。假设 $t_{k}$ 的权重系数是 $\lambda _{k}$ ， $s_{l}$ 的权重系数是 $u_{l}$ ，则linear-CRF由所有的 $t_{k},\lambda_{k},s_{l},u_{l}$ 共同决定。

此时我们得到了linear-CRF的参数化形式如下：

其中， $Z(x)$ 为规范化因子：

回到特征函数本身，每个特征函数定义了一个linear-CRF的规则，则其系数定义了这个规则的可信度。所有的规则和其可信度一起构成了linear-CRF的最终的条件概率分布。

1.6 线性链条件随机场实例

这里我们给出一个linear-CRF用于词性标注的实例，为了方便，我们简化了词性的种类。假设输入的都是三个词的句子，即，输出的词性标记为 $Y=(Y_{1}, ,Y_{1},Y_{3})$ ，其中 $Y\in\left\{ 1(名词),2(动词) \right\}$

这里只标记出取值为1的特征函数如下：

求标记(1,2,2)的非规范化概率。

利用linear-CRF的参数化公式，我们有：

带入(1,2,2)有：

1.7 线性链条件随机场的简化形式

在上几节里面，我们用 $s_{l}$ 表示节点特征函数，用 $t_{k}$ 表示局部特征函数，同时也用了不同的符号表示权重系数，导致表示起来比较麻烦。其实我们可以对特征函数稍加整理，将其统一起来。

假设在某一节点我们有 $K_{1}$ 个局部特征函数和 $K_{2}$ 个节点特征函数，总共有 $K=K_{1}+K_{2}$ 个特征函数。用一个特征函数 $f_{k}(y_{i-1},y_{i},x,i)$ 来统一表示如下：

对在各个序列位置求和得到：

对应的权重系数 $w_{k}$ 如下：

这样，linear-CRF的参数化形式简化为：

其中， $Z(x)$ 为规范化因子：

则linear-CRF的参数化形式简化为内积形式如下：

1.8 线性链条件随机场的矩阵形式

将linear-CRF的参数化形式写成矩阵形式。为此定义一个的矩阵 $M$ ， $m$ 为 $y$ 所有可能的状态的取值个数。 $M$ 定义如下：

引入起点和终点标记，这样，标记序列 $y$ 的非规范化概率可以通过 $n+1$ 个矩阵元素的乘积得到，即：

其中， $Z_{w}(x)$ 为规范化因子。

2 前向后向算法评估标记序列概率

linear-CRF需要解决的三个问题：评估，学习和解码。

这三个问题和HMM是非常类似的，本节关注于第一个问题：评估。

2.1 linear-CRF的三个基本问题

linear-CRF第一个问题是评估，即给定 linear-CRF的条件概率分布 $P(y|x)$ ，在给定输入序列 $x$ 和输出序列 $y$ 时，计算条件概率 $P(y_{i}|x)$ 和 $P(y_{i-1},y_{i}|x)$ 以及对应的期望。

linear-CRF第二个问题是学习，即给定训练数据集 $X$ 和 $Y$ ，学习linear-CRF的模型参数 $w_{k}$ 和条件概率 $P_{w}(y|x)$ 。

linear-CRF第三个问题是解码，即给定 linear-CRF的条件概率分布 $P(y|x)$ ，和输入序列 $x$ ，计算使条件概率最大的输出序列 $y$ 。

2.2 linear-CRF的前向后向概率概述

要计算条件概率 $P(y_{i}|x)$ 和 $P(y_{i-1},y_{i}|x)$ ，也可以使用和HMM类似的方法，使用前向后向算法来完成。首先我们来看前向概率的计算。

$y_{i+1}$

定义 $\alpha _{i}(y_{i}|x)$ 表示序列位置 $i$ 的标记是 $y_{i}$ 时，在位置 $i$ 之前的部分标记序列的非规范化概率。之所以是非规范化概率是因为我们不想加入一个不影响结果计算的规范化因子 $Z(x)$ 在分母里面。

定义了下式：

这个式子定义了在给定 $y_{i-1}$ 时，从 $y_{i-1}$ 转移到 $y_{i}$ 的非规范化概率。

这样，可以得到序列位置 $i+1$ 的标记是时，在位置 $i+1$ 之前的部分标记序列的非规范化概率 $\alpha_{i+1}(y_{i+1}|x)$ 的递推公式：

在起点处，我们定义：

假设我们可能的标记总数是 $m$ ，则 $y_{i}$ 的取值就有 $m$ 个，用 $\alpha_{i}(x)$ 表示这 $m$ 个值组成的前向向量如下：

这样递推公式可以用矩阵乘积表示：

同样的，定义 $\beta _{i}(y_{i}|x)$ 表示序列位置 $i$ 的标记是 $y_{i}$ 时，在位置 $i$ 之后的从 $i+1$ 到 $n$ 的部分标记序列的非规范化概率。

这样，可以得到序列位置 $i+1$ 的标记是 $y_{i+1}$ 时，在位置 $i$ 之后的部分标记序列的非规范化概率 $\beta_{i}(y_{i}|x)$ 的递推公式：

在终点处，我们定义：

如果用向量表示，则有：

由于规范化因子 $Z(x)$ 的表达式是：

也可以用向量来表示 $Z(x)$ ：

其中， $1$ 是 $m$ 维全1向量。

2.3 linear-CRF的前向后向概率计算

有了前向后向概率的定义和计算方法，我们就很容易计算序列位置 $i$ 的标记是 $y_{i}$ 的条件概率 $P(y_{i}|x)$ ：

2.4 linear-CRF的期望计算

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

2.5 linear-CRF前向后向算法总结

以上就是linear-CRF的前向后向算法。

注意到我们上面的非规范化概率起的作用和HMM中的隐藏状态转移概率很像。但是这儿的概率是非规范化的，也就是不强制要求所有的状态的概率和为1。而HMM中的隐藏状态转移概率也规范化的。从这一点看，linear-CRF对序列状态转移的处理要比HMM灵活。

3 模型学习与维特比算法解码

linear-CRF的第二个问题与第三个问题的求解。第二个问题是模型参数学习的问题，第三个问题是维特比算法解码的问题。

3.1 linear-CRF模型参数学习思路

求解这个问题有很多思路，比如梯度下降法，牛顿法，拟牛顿法。也可以使用最大熵模型中使用的改进的迭代尺度法(improved iterative scaling, IIS)来求解。

3.2 linear-CRF模型参数学习之梯度下降法求解

在使用梯度下降法求解模型参数之前，我们需要定义我们的优化函数，一般极大化条件分布 $P_{w}(y|x)$ 的对数似然函数如下：

有了 $w$ 的导数表达式，就可以用梯度下降法来迭代求解最优的 $w$ 了。注意在迭代过程中，每次更新 $w$ 后，需要同步更新 $P_{w}(x,y)$ 以用于下一次迭代的梯度计算。

以上就是linear-CRF模型参数学习之梯度下降法求解思路总结。

3.3 linear-CRF模型维特比算法解码思路

现在我们来看linear-CRF的第三个问题：解码。

在这个问题中，给定条件随机场的条件概率 $P(y|x)$ 和一个观测序列 $x$ ，要求出满足 $P(y|x)$ 最大的序列 $y$ 。

这个解码算法最常用的还是和HMM解码类似的维特比算法。

维特比算法本身是一个动态规划算法，利用了两个局部状态和对应的递推公式，从局部递推到整体，进而得解。对于具体不同的问题，仅仅是这两个局部状态的定义和对应的递推公式不同而已。

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

现在我们总结下 linear-CRF模型维特比算法流程：

输入：模型的 $K$ 个特征函数，和对应的 $k$ 个权重。观测序列 $x=(x_{1},x_{2},...,x_{n})$ ，可能的标记个数 $m$

输出：最优标记序列

3.5 linear-CRF模型维特比算法实例

下面用一个具体的例子来描述 linear-CRF模型维特比算法，例子的模型来源于《统计学习方法》。

3.6 linear-CRF vs HMM

linear-CRF模型和HMM模型有很多相似之处，尤其是其三个典型问题非常类似，除了模型参数学习的问题求解方法不同以外，概率估计问题和解码问题使用的算法思想基本也是相同的。同时，两者都可以用于序列模型，因此都广泛用于自然语言处理的各个方面。

现在来看看两者的不同点。

最大的不同点是linear-CRF模型是判别模型，而HMM是生成模型，即linear-CRF模型要优化求解的是条件概率P(y|x),则HMM要求解的是联合分布P(x,y)。第二，linear-CRF是利用最大熵模型的思路去建立条件概率模型，对于观测序列并没有做马尔科夫假设。而HMM是在对观测序列做了马尔科夫假设的前提下建立联合分布的模型。

只有linear-CRF模型和HMM模型才是可以比较讨论的。但是linear-CRF是CRF的一个特例，CRF本身是一个可以适用于很复杂条件概率的模型，因此理论上CRF的使用范围要比HMM广泛的多。