条件随机场

本文是《统计学习方法》第11章的笔记，在课本的基础上加入了自己的注释和理解。作为CRF的入门读物，著名的几篇英文教程难度稍高，还是李航博士的《方法》比较适合初学者。其拟牛顿法讲解可以直接与CRF++的代码对应，实为难得。我还单独写了篇《CRF++代码分析》，与本文互为参考。

条件随机场（conditional random field，CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。条件随机场可以用于不同的预测问题，本章仅论及它在标注问题的应用。因此主要讲述线性链（linear chain)条件随机场，这时，问题变成了由输入序列对输出序列预测的判别模型，形式为对数线性模型，其学习方法通常是极大似然估计或正则化的极大似然估计。线性链条件随机场应用于标注问题是由Lafferty等人于2001年提出的。

本章首先介绍概率无向图模型，然后叙述条件随机场的定义和各种表示方法，最后介绍条件随机场的3个基本问题：概率计算问题、学习问题和预测问题。

概率无向图模型

概率无向图模型（probabilistic undirected graphical model)，又称为马尔可夫随机场（Markov random field)，是一个可以由无向图表示的联合概率分布。本节首先叙述概率无向图模型的定义，然后介绍概率无向图模型的因子分解。

模型定义

先啰嗦一下图的定义：

图（graph)是由结点（node)及连接结点的边（edge)组成的集合。结点和边分别记作v和e,结点和边的集合分别记作V和E，图记作G=(V,E)。无向图是指边没有方向的图。

概率图模型（probabilistic graphical model)是由图表示的概率分布。设有联合概率分布，是一组随机变量。由无向图G=(V,E)表示概率分布。即在图G中，结点表示一个随机变量，；边表示随机变量之间的概率依赖关系。

给定一个联合概率分布和表示它的无向图G。首先定义无向图表示的随机变量之间存在的成对马尔可夫性（pairwise Markov property)、局部马尔可夫性（local Markov property)和全局马尔可夫性（global Markov property)。

成对马尔可夫性：设u和v是无向图G中任意两个没有边连接的结点，结点u和v分别对应随机变量和。其他所有结点为O（集合），对应的随机变量组是。成对马尔可夫性是指给定随机变量组的条件下随机变量和是条件独立的，即

其实这么定义有些啰嗦了，一句话，没有直连边的任意两个节点都是独立的。

局部马尔可夫性：设是无向图G中任意一个结点，W是与v有边连接的所有结点，O是v,W以外的其他所有结点。v表示的随机变量是,W表示的随机变量组是，O表示的随机变量组是。局部马尔可夫性是指在给定随机变量组的条件下随机变量与随机变量组是独立的，即

在时，等价地，

下图表示了局部马尔可夫性。

我觉得局部马尔可夫性就是成对马尔可夫性的推论。

全局马尔可夫性：设结点集合A，B是在无向图G中被结点集合C分开的任意结点集合，如图所示。结点集合A，B和C所对应的随机变量组分别是,和。全局马尔可夫性是指给定随机变量组条件下随机变量组和是条件独立的，即

上述成对的、局部的、全局的马尔可夫性定义是等价的。

下面定义概率无向图模型。

定义(概率无向图模型）设有联合概率分布,由无向图G=(V,E)表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型(probability undirected graphical model)，或马尔可夫随机场(Markov random field)。

以上是概率无向图模型的定义，实际上，我们更关心的是如何求其联合概率分布。对给定的概率无向图模型，我们希望将整体的联合概率写成若干子联合概率的乘积的形式，也就是将联合概率进行因子分解，这样便于模型的学习与计算。事实上，概率无向图模型的最大特点就是易于因子分解。下面介绍这一结果。

概率无向图模型的因子分解

首先给出无向图中的团与最大团的定义。

定义(团与最大团）无向图G中任何两个结点均有边连接的结点子集称为团（clique)。若C是无向图G的一个团，并且不能再加进任何一个G的结点使其成为一个更大的团，则称此C为最大团（maximal clique)。

下图表示由4个结点组成的无向图。图中由2个结点组成的团有5个:{y1,y2},{y2,y3}，{y3,y4}和{y4,y2}，{y1,y3}。有2个最大团：{y1,y2,y3}和{y2,y3,y4}。而{y1,y2,y3,y4}不是一个团，因为y1和y4没有边连接。

将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解（factorization)。

给定概率无向图模型，设其无向图为G，C为G上的最大团，表示C对应的随机变量。那么概率无向图模型的联合概率分布可写作图中所有最大团C上的函数的乘积形式，即

其中，Z是规范化因子（normalization factor),由式

给出。规范化因子保证构成一个概率分布。函数称为势函数(potential function)。这里要求势函数是严格正的，通常定义为指数函数：

概率无向图模型的因子分解由下述定理来保证。

定理(Hammersley-Clifford定理）概率无向图模型的联合概率分布可以表示为如下形式：

其中，C是无向图的最大团，是C的结点对应的随机变量，是C上定义的严格正函数，乘积是在无向图所有的最大团上进行的。

条件随机场的定义与形式

条件随机场的定义

条件随机场（conditional random field)是给定随机变量X条件下，随机变量Y的马尔可夫随机场。这里主要介绍定义在线性链上的特殊的条件随机场，称为线性链条件随机场（linear chain conditional random field)。线性链条件随机场可以用于标注等问题。这时，在条件概率模型中，Y是输出变量，表示标记序列，X是输入变量，表示需要标注的观测序列。也把标记序列称为状态序列（参见隐马尔可夫模型)。学习时，利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型；预测时，对于给定的输入序列x,求出条件概率最大的输出序列y。

首先定义一般的条件随机场，然后定义线性链条件随机场。

定义(条件随机场）设X与Y是随机变量，是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由无向图表示的马尔可夫随机场，即

对任意结点v成立，则称条件概率分布为条件随机场。式中w~v表示在图中与结点v有边连接的所有结点w,w≠v表示结点v以外的所有结点，，与为结点v，u与w对应的随机变量。从定义来看，左边到右边点的数量大大减小，w≠v的点有|V|-1个，而w~v就少了。

在定义中并没有要求X和Y具有相同的结构。现实中，一般假设X和Y有相同的图结构。本书主要考虑无向图为线性链的情况，即

在此情况下，,最大团是相邻两个结点的集合。线性链条件随机场有下面的定义。

线性链条件随机场

X和Y有相同的图结构的线性链条件随机场

定义(线性链条件随机场) 设均为线性链表示的随机变量序列，若在给定随机变量序列尤的条件下，随机变量序列Y的条件概率分布构成条件随机场，即满足马尔可夫性

则称为线性链条件随机场。在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。

条件随机场的参数化形式

根据Hammersley-Clifford定理,可以给出线性链条件随机场的因子分解式，各因子是定义在相邻两个结点上的函数。

定理(线性链条件随机场的参数化形式）设为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率具有如下形式：

其中，

式中，和是特征函数，和是对应的权值。是规范化因子，求和是在所有可能的输出序列上进行的。(这里面的特征函数有些抽象，并且也不知道为什么有两项而且要加起来，ikl分别是什么？这些问题都不用急，下文会讲解。)

上面两个式子是线性链条件随机场模型的基本形式，表示给定输入序列x,对输出序列y预测的条件概率。其中是定义在边上的特征函数，称为转移特征（t是transition的缩写，方便记忆），依赖于当前和前一个位置，是定义在结点上的特征函数，称为状态特征（s是status的缩写），依赖于当前位置（无论哪种特征函数，都将当前可能的y_i作为参数）。和都依赖于位置，是局部特征函数。通常，特征函数和取值为1或0;当满足特征条件时取值为1,否则为0。条件随机场完全由特征函数和对应的权值、确定。

线性链条件随机场也是对数线性模型（loglinear model)。

条件随机场的简化形式

条件随机场还可以由简化形式表示。注意到条件随机场式中同一特征在各个位置都有定义，可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数，这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式。

为简便起见，首先将转移特征和状态特征及其权值用统一的符号表示。设有个转移特征，个状态特征，,记

上式其实是对特征函数进行编码，编号的前个属于转移特征，后个属于状态特征。编号统一了，后面就可以放到同一个矩阵里了。

然后，对转移与状态特征在各个位置i求和，记作

上式的特征函数虽然都写成接受4个参数的形式，但对状态特征函数而言，y_i-1是会被忽略掉的。

用表示特征的权值，即

于是，条件随机场可表示为

若以w表示权值向量，即

以表示全局特征向量，即

则条件随机场可以写成向量w与的内积的形式:

其中，

条件随机场的矩阵形式

条件随机场还可以由矩阵表示。假设是由内积形式给出的线性链条件随机场，表示对给定观测序列x，相应的标记序列y的条件概率。引进特殊的起点和终点状态标记,这时可以通过矩阵形式表示。

对观测序列x的每一个位置i=1,2,…，n+1，定义一个m阶矩阵（m是标记y_i取值的个数，因为x是给定的，i-1位置和i位置各有m种可能，所以是m阶的）

这样，给定观测序列x,标记序列y的非规范化概率可以通过n+1个矩阵的乘积表示，于是，条件概率是

其中，为规范化因子，是n+1个矩阵的乘积的(start,stop)元素：

注意，与表示开始状态与终止状态，规范化因子是以start为起点stop为终点通过状态的所有路径的非规范化概率之和。

这里的M矩阵像极了一阶HMM中的转移概率矩阵，因为链式CRF中只有相邻两个节点间才有连接边。

条件随机场的概率计算问题

条件随机场的概率计算问题是给定条件随机场，输入序列x和输出序列y,计算条件概率以及相应的数学期望的问题。为了方便起见，像隐马尔可夫模型那样，引进前向-后向向量，递归地计算以上概率及期望值。这样的算法称为前向-后向算法。

前向-后向算法

对每个指标，定义前向向量：

递推公式为

又可表示为

表示在位置i的标记是y_i并且到位置i的前部分标记序列的非规范化概率，y_i可取的值有m个，所以是m维列向量。

同样，对每个指标，定义后向向量:

又可以表示为：

表示在位置i的标记为,并且从i+1到n的后部分标记序列的非规范化概率。

由前向-后向向量定义不难得到：

这里，是元素均为1的m维列向量。

概率计算

按照前向-后向向量的定义，很容易计算标记序列在位置i是标记的条件概率和在位置i-1与i是标记和的条件概率：

其中，

期望值的计算

利用前向-后向向量，可以计算特征函数关于联合分布和条件分布的数学期望。

特征函数关于条件分布的数学期望是

其中，

假设经验分布为，特征函数关于联合分布的数学期望是

其中，

这个式子是特征函数数学期望的一般计算公式。对于转移特征，可以将式中的换成;对于状态特征，可以将式中的换成,表示为。

有了这些式子，对于给定的观测序列x与标记序列y，可以通过一次前向扫描计算及,通过一次后向扫描计算，从而计算所有的概率和特征的期望。

条件随机场的学习算法

本节讨论给定训练数据集估计条件随机场模型参数的问题，即条件随机场的学习问题。条件随机场模型实际上是定义在时序数据上的对数线形模型，其学习方法包括极大似然估计和正则化的极大似然估计。具体的优化实现算法有改进的迭代尺度法IIS、梯度下降法以及拟牛顿法。（其中，主流的CRF软件之CRF++采用了拟牛顿法+L-BFGS优化，所以着重看这种训练方法即可。）

改进的迭代尺度法

已知训练数据集，由此可知经验概率分布可以通过极大化训练数据的对数似然函数来求模型参数。

训练数据的对数似然函数为

当是一个由和给出的条件随机场模型时，对数似然函数为

改进的迭代尺度法通过迭代的方法不断优化对数似然函数改变量的下界，达到极大化对数似然函数的目的。假设模型的当前参数向量,向量的增量为,更新参数向量为。在每步迭代过程中，改进的迭代尺度法通过依次求解下面两个式子,得到，推导可参考《改进的迭代尺度法》。

关于转移特征的更新方程为

关于状态特征的更新方程为

这里，是在数据中出现所有特征数的总和:

算法(条件随机场模型学习的改进的迭代尺度法）

输入：特征函数;经验分布;

输出：参数估计值模型。

(1)对所有，取初值

(2)对每一:

(a)当时，令是方程

的解;

当时，令是方程

的解，式中由式给出。

(b)更新值：

(3)如果不是所有都收敛，重复步骤(2)。

在和中，表示数据中的特征总数，对不同的数据取值可能不同。为了处理这个问题，定义松弛特征

式中S是一个常数。选择足够大的常数S使得对训练数据集的所有数据,成立。这时特征总数可取S。

由式,对于转移特征，的更新方程是

其中，

同样由式，对于状态特征，的更新方程是

以上算法称为算法S。在算法S中需要使常数S取足够大，这样一来，每步迭代的增量向量会变大，算法收敛会变慢。算法T试图解决这个问题。算法T对每个观测序列x计算其特征总数最大值:

利用前向-后向递推公式，可以很容易地计算。

这时，关于转移特征参数的更新方程可以写成：

这里，是特征的期望值，,是多项式方程唯一的实根,可以用牛顿法求得。从而求得相关的。

同样，关于状态特征的参数更新方程可以写成：

这里，是特征的期望值，,是多项式方程唯一的实根,也可以用牛顿法求得。

拟牛顿法

条件随机场模型学习还可以应用牛顿法或拟牛顿法。对于条件随机场模型

学习的优化目标函数是

其梯度函数是

拟牛顿法的BFGS算法如下。

算法(条件随机场模型学习的BFGS算法）

输入：特征函数；经验分布;

输出：最优参数值；最优模型。

(1)选定初始点，取为正定对称矩阵，置

(2)   计算。若,则停止计算；否则转(3)

(3)由求出

(4)一维搜索：求使得

(5)置

(6)计算，若=0,则停止计算；否则，按下式求出:

其中，

(7)置，转(3)。

条件随机场的预测算法

条件随机场的预测问题是给定条件随机场和输入序列（观测序列）x,求条件概率最大的输出序列（标记序列），即对观测序列进行标注。条件随机场的预测算法是著名的维特比算法。

由式可得：

于是，条件随机场的预测问题成为求非规范化概率最大的最优路径问题

这里，路径表示标记序列。其中，

注意，这时只需计算非规范化概率，而不必计算概率，可以大大提高效率。为了求解最优路径，将写成如下形式：

其中，

是局部特征向量。

下面叙述维特比算法。首先求出位置1的各个标记j=1,2,…，m的非规范化概率:

一般地，由递推公式，求出到位置》。的各个标记/=l，2，。。。，m的非规范化概率的最大值，同时记录非规范化概率最大值的路径

直到时终止。这时求得非规范化概率的最大值为

及最优路径的终点

由此最优路径终点返回,

求得最优路径。

综上所述，得到条件随机场预测的维特比算法：

算法(条件随机场预测的维特比算法）

输入：模型特征向量和权值向量,观测序列

输出：最优路径。

(1)初始化

(2)递推。对

(3)终止

(4)返回路径

求得最优路径。

CRF实现

关于具体的实现，这次发现CRF++与《方法》的契合度非常之高，所以请直接参考《CRF++代码分析》。

目前Python阵营里并没有简单好懂的实现，反而不如直接切入CRF++的生产代码有效果，还可以顺便学到不少C++的小知识。

Reference

《统计学习方法》

http://mi.eng.cam.ac.uk/~cz277/doc/Slides-CRFASR-CSLT.pdf

 知识共享署名-非商业性使用-相同方式共享：码农场 » 条件随机场