放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

条件随机场

目录

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

条件随机场(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)是由图表示的概率分布。设有联合概率分布屏幕快照 2016-08-08 下午2.12.06.png屏幕快照 2016-08-08 下午2.12.50.png是一组随机变量。由无向图G=(V,E)表示概率分布。即在图G中,结点屏幕快照 2016-08-08 下午2.15.12.png表示一个随机变量屏幕快照 2016-08-08 下午2.15.27.png屏幕快照 2016-08-08 下午2.16.03.png;边屏幕快照 2016-08-08 下午2.16.58.png表示随机变量之间的概率依赖关系。

给定一个联合概率分布屏幕快照 2016-08-08 下午2.12.06.png和表示它的无向图G。首先定义无向图表示的随机变量之间存在的成对马尔可夫性(pairwise Markov property)、局部马尔可夫性(local Markov property)和全局马尔可夫性(global Markov property)。

成对马尔可夫性:设u和v是无向图G中任意两个没有边连接的结点,结点u和v分别对应随机变量屏幕快照 2016-08-08 下午2.19.53.png屏幕快照 2016-08-08 下午2.15.27.png。其他所有结点为O(集合),对应的随机变量组是屏幕快照 2016-08-08 下午2.20.49.png。成对马尔可夫性是指给定随机变量组屏幕快照 2016-08-08 下午2.20.49.png的条件下随机变量屏幕快照 2016-08-08 下午2.19.53.png屏幕快照 2016-08-08 下午2.15.27.png是条件独立的,即

屏幕快照 2016-08-08 下午2.23.32.png

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

局部马尔可夫性:设屏幕快照 2016-08-08 下午2.15.12.png是无向图G中任意一个结点,W是与v有边连接的所有结点,O是v,W以外的其他所有结点。v表示的随机变量是屏幕快照 2016-08-08 下午2.15.27.png,W表示的随机变量组是屏幕快照 2016-08-08 下午2.26.19.png,O表示的随机变量组是屏幕快照 2016-08-08 下午2.20.49.png。局部马尔可夫性是指在给定随机变量组屏幕快照 2016-08-08 下午2.26.19.png的条件下随机变量屏幕快照 2016-08-08 下午2.15.27.png与随机变量组屏幕快照 2016-08-08 下午2.20.49.png是独立的,即

屏幕快照 2016-08-08 下午2.31.25.png

屏幕快照 2016-08-08 下午2.31.59.png时,等价地,

屏幕快照 2016-08-08 下午2.32.16.png

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

屏幕快照 2016-08-08 下午2.33.35.png

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

全局马尔可夫性:设结点集合A,B是在无向图G中被结点集合C分开的任意结点集合,如图所示。结点集合A,B和C所对应的随机变量组分别是屏幕快照 2016-08-08 下午2.35.40.png,屏幕快照 2016-08-08 下午2.35.54.png屏幕快照 2016-08-08 下午2.36.08.png。全局马尔可夫性是指给定随机变量组条件下随机变量组屏幕快照 2016-08-08 下午2.35.40.png屏幕快照 2016-08-08 下午2.35.54.png是条件独立的,即

屏幕快照 2016-08-08 下午2.37.28.png

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

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

定义(概率无向图模型)设有联合概率分布屏幕快照 2016-08-08 下午2.12.06.png,由无向图G=(V,E)表示,在图G中,结点表示随机变量,边表示随机变量之间的依赖关系。如果联合概率分布屏幕快照 2016-08-08 下午2.12.06.png满足成对、局部或全局马尔可夫性,就称此联合概率分布为概率无向图模型(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没有边连接。

屏幕快照 2016-08-08 下午2.45.22.png

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

给定概率无向图模型,设其无向图为G,C为G上的最大团,屏幕快照 2016-08-08 下午2.36.08.png表示C对应的随机变量。那么概率无向图模型的联合概率分布屏幕快照 2016-08-08 下午2.12.06.png可写作图中所有最大团C上的函数屏幕快照 2016-08-08 下午3.00.36.png的乘积形式,即

屏幕快照 2016-08-08 下午3.00.10.png

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

屏幕快照 2016-08-08 下午3.04.55.png

给出。规范化因子保证屏幕快照 2016-08-08 下午2.12.06.png构成一个概率分布。屏幕快照 2016-08-08 下午3.00.36.png函数称为势函数(potential function)。这里要求势函数屏幕快照 2016-08-08 下午3.00.36.png是严格正的,通常定义为指数函数:

屏幕快照 2016-08-08 下午3.08.54.png

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

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

屏幕快照 2016-08-08 下午3.00.10.png

屏幕快照 2016-08-08 下午3.04.55.png

其中,C是无向图的最大团,屏幕快照 2016-08-08 下午2.36.08.png是C的结点对应的随机变量,屏幕快照 2016-08-08 下午3.00.36.png是C上定义的严格正函数,乘积是在无向图所有的最大团上进行的。

条件随机场的定义与形式

条件随机场的定义

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

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

定义(条件随机场)设X与Y是随机变量,屏幕快照 2016-08-08 下午3.17.37.png是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由无向图屏幕快照 2016-08-08 下午3.28.37.png表示的马尔可夫随机场,即

屏幕快照 2016-08-08 下午3.29.54.png

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

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

屏幕快照 2016-08-08 下午3.37.35.png

在此情况下,屏幕快照 2016-08-08 下午3.39.38.png,最大团是相邻两个结点的集合。线性链条件随机场有下面的定义。

屏幕快照 2016-08-08 下午3.46.30.png

线性链条件随机场

屏幕快照 2016-08-08 下午3.47.44.png

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

定义(线性链条件随机场) 屏幕快照 2016-08-08 下午3.39.38.png均为线性链表示的随机变量序列,若在给定随机变量序列尤的条件下,随机变量序列Y的条件概率分布屏幕快照 2016-08-08 下午3.17.37.png构成条件随机场,即满足马尔可夫性

屏幕快照 2016-08-08 下午3.51.04.png

则称屏幕快照 2016-08-08 下午3.17.37.png为线性链条件随机场。在标注问题中,X表示输入观测序列,Y表示对应的输出标记序列或状态序列。

条件随机场的参数化形

根据Hammersley-Clifford定理,可以给出线性链条件随机场屏幕快照 2016-08-08 下午3.17.37.png的因子分解式,各因子是定义在相邻两个结点上的函数。

定理(线性链条件随机场的参数化形式)设屏幕快照 2016-08-08 下午3.17.37.png为线性链条件随机场,则在随机变量X取值为x的条件下,随机变量Y取值为y的条件概率具有如下形式:

屏幕快照 2016-08-08 下午4.22.36.png

其中,

屏幕快照 2016-08-08 下午4.23.54.png

式中,屏幕快照 2016-08-08 下午4.26.31.png屏幕快照 2016-08-08 下午4.26.44.png是特征函数,屏幕快照 2016-08-08 下午4.27.12.png屏幕快照 2016-08-08 下午4.27.34.png是对应的权值。屏幕快照 2016-08-08 下午4.28.07.png是规范化因子,求和是在所有可能的输出序列上进行的。(这里面的特征函数有些抽象,并且也不知道为什么有两项而且要加起来,ikl分别是什么?这些问题都不用急,下文会讲解。)

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

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

条件随机场的简化形式

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

为简便起见,首先将转移特征和状态特征及其权值用统一的符号表示。设有屏幕快照 2016-08-08 下午4.50.10.png个转移特征,屏幕快照 2016-08-08 下午4.50.26.png个状态特征,屏幕快照 2016-08-08 下午4.50.55.png,记

屏幕快照 2016-08-08 下午4.53.37.png

上式其实是对特征函数进行编码,编号的前屏幕快照 2016-08-08 下午4.50.10.png个属于转移特征,后屏幕快照 2016-08-08 下午4.50.26.png个属于状态特征。编号统一了,后面就可以放到同一个矩阵里了。

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

屏幕快照 2016-08-08 下午4.54.35.png

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

屏幕快照 2016-08-08 下午4.55.23.png表示特征屏幕快照 2016-08-08 下午4.56.24.png的权值,即

屏幕快照 2016-08-08 下午4.56.58.png

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

屏幕快照 2016-08-08 下午4.58.10.png

若以w表示权值向量,即

屏幕快照 2016-08-08 下午4.59.05.png

屏幕快照 2016-08-08 下午4.59.56.png表示全局特征向量,即

屏幕快照 2016-08-08 下午5.00.31.png

则条件随机场可以写成向量w与屏幕快照 2016-08-08 下午4.59.56.png的内积的形式:

屏幕快照 2016-08-08 下午5.04.04.png

其中,

屏幕快照 2016-08-08 下午5.04.50.png

条件随机场的矩阵形式

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

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

屏幕快照 2016-08-08 下午5.09.02.png

这样,给定观测序列x,标记序列y的非规范化概率可以通过n+1个矩阵的乘积屏幕快照 2016-08-08 下午5.12.26.png表示,于是,条件概率屏幕快照 2016-08-08 下午5.06.36.png

屏幕快照 2016-08-08 下午5.13.17.png

其中,屏幕快照 2016-08-08 下午5.14.13.png为规范化因子,是n+1个矩阵的乘积的(start,stop)元素:

屏幕快照 2016-08-08 下午5.15.48.png

注意,屏幕快照 2016-08-08 下午5.16.37.png屏幕快照 2016-08-08 下午5.16.52.png表示开始状态与终止状态,规范化因子屏幕快照 2016-08-08 下午5.14.13.png是以start为起点stop为终点通过状态的所有路径的非规范化概率屏幕快照 2016-08-08 下午5.17.34.png之和。

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

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

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

前向-后向算法

对每个指标屏幕快照 2016-08-08 下午5.20.58.png,定义前向向量屏幕快照 2016-08-08 下午5.21.21.png

屏幕快照 2016-08-08 下午8.12.09.png

递推公式为

屏幕快照 2016-08-08 下午5.23.55.png

又可表示为

屏幕快照 2016-08-08 下午5.24.45.png

屏幕快照 2016-08-08 下午5.25.36.png表示在位置i的标记是y_i并且到位置i的前部分标记序列的非规范化概率,y_i可取的值有m个,所以屏幕快照 2016-08-08 下午5.25.36.png是m维列向量。

同样,对每个指标屏幕快照 2016-08-08 下午5.27.33.png,定义后向向量屏幕快照 2016-08-08 下午5.27.54.png:

屏幕快照 2016-08-08 下午7.54.18.png

又可以表示为:

屏幕快照 2016-08-08 下午7.55.45.png

屏幕快照 2016-08-08 下午7.58.03.png表示在位置i的标记为屏幕快照 2016-08-08 下午7.58.41.png,并且从i+1到n的后部分标记序列的非规范化概率。

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

屏幕快照 2016-08-08 下午8.01.04.png

这里,屏幕快照 2016-08-08 下午8.02.03.png是元素均为1的m维列向量。

概率计算

按照前向-后向向量的定义,很容易计算标记序列在位置i是标记屏幕快照 2016-08-08 下午7.58.41.png的条件概率和在位置i-1与i是标记屏幕快照 2016-08-08 下午8.03.19.png屏幕快照 2016-08-08 下午7.58.41.png的条件概率:

屏幕快照 2016-08-08 下午8.05.57.png

其中,

屏幕快照 2016-08-08 下午8.06.52.png

期望值的计算

利用前向-后向向量,可以计算特征函数关于联合分布屏幕快照 2016-08-08 下午8.14.29.png和条件分布屏幕快照 2016-08-08 下午8.14.46.png的数学期望。

特征函数屏幕快照 2016-08-08 下午8.15.17.png关于条件分布屏幕快照 2016-08-08 下午8.14.46.png的数学期望是

屏幕快照 2016-08-08 下午8.16.43.png

其中,

屏幕快照 2016-08-08 下午8.06.52.png

假设经验分布为屏幕快照 2016-08-08 下午8.18.15.png,特征函数屏幕快照 2016-08-08 下午8.15.17.png关于联合分布屏幕快照 2016-08-08 下午8.14.29.png的数学期望是

屏幕快照 2016-08-08 下午8.23.05.png

其中,

屏幕快照 2016-08-08 下午8.06.52.png

这个式子是特征函数数学期望的一般计算公式。对于转移特征屏幕快照 2016-08-08 下午8.24.40.png,可以将式中的屏幕快照 2016-08-08 下午8.15.17.png换成屏幕快照 2016-08-08 下午8.25.19.png;对于状态特征,可以将式中的屏幕快照 2016-08-08 下午8.15.17.png换成屏幕快照 2016-08-08 下午8.26.00.png,表示为屏幕快照 2016-08-08 下午8.26.14.png

有了这些式子,对于给定的观测序列x与标记序列y,可以通过一次前向扫描计算屏幕快照 2016-08-08 下午8.28.29.png屏幕快照 2016-08-08 下午8.28.43.png,通过一次后向扫描计算屏幕快照 2016-08-08 下午8.29.11.png,从而计算所有的概率和特征的期望。

条件随机场的学习算法

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

改进的迭代尺度法

已知训练数据集,由此可知经验概率分布屏幕快照 2016-08-08 下午8.33.55.png可以通过极大化训练数据的对数似然函数来求模型参数。

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

屏幕快照 2016-08-08 下午8.34.28.png

当是一个由屏幕快照 2016-08-08 下午5.04.04.png屏幕快照 2016-08-08 下午5.04.50.png给出的条件随机场模型时,对数似然函数为

屏幕快照 2016-08-08 下午8.37.10.png

改进的迭代尺度法通过迭代的方法不断优化对数似然函数改变量的下界,达到极大化对数似然函数的目的。假设模型的当前参数向量屏幕快照 2016-08-09 上午9.41.33.png,向量的增量为屏幕快照 2016-08-09 上午9.42.05.png,更新参数向量为屏幕快照 2016-08-09 上午9.42.57.png屏幕快照 2016-08-09 上午9.43.06.png。在每步迭代过程中,改进的迭代尺度法通过依次求解下面两个式子,得到屏幕快照 2016-08-09 上午9.42.05.png,推导可参考《改进的迭代尺度法》

关于转移特征屏幕快照 2016-08-09 上午9.55.22.png的更新方程为

屏幕快照 2016-08-09 上午9.55.55.png

关于状态特征屏幕快照 2016-08-08 下午4.26.44.png的更新方程为

屏幕快照 2016-08-09 上午10.00.18.png

这里,屏幕快照 2016-08-09 上午10.01.28.png是在数据屏幕快照 2016-08-09 上午10.01.56.png中出现所有特征数的总和:

屏幕快照 2016-08-09 上午10.02.22.png

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

输入:特征函数屏幕快照 2016-08-09 上午10.05.38.png;经验分布屏幕快照 2016-08-09 上午10.05.56.png;

输出:参数估计值模型屏幕快照 2016-08-09 上午10.06.27.png

(1)对所有屏幕快照 2016-08-09 上午10.06.49.png,取初值屏幕快照 2016-08-09 上午10.07.05.png

(2)对每一屏幕快照 2016-08-09 上午10.06.49.png:

(a)屏幕快照 2016-08-09 上午10.08.46.png时,令屏幕快照 2016-08-09 上午10.09.06.png是方程

屏幕快照 2016-08-09 上午10.09.36.png

的解;

屏幕快照 2016-08-09 上午10.10.06.png时,令屏幕快照 2016-08-09 上午10.10.28.png是方程

屏幕快照 2016-08-09 上午10.11.00.png

的解,式中屏幕快照 2016-08-09 上午10.11.45.png由式屏幕快照 2016-08-09 上午10.02.22.png给出。

(b)更新屏幕快照 2016-08-09 上午10.13.50.png值:屏幕快照 2016-08-09 上午10.14.10.png

(3)如果不是所有屏幕快照 2016-08-09 上午10.13.50.png都收敛,重复步骤(2)。

屏幕快照 2016-08-09 上午9.55.55.png屏幕快照 2016-08-09 上午10.00.18.png中,屏幕快照 2016-08-09 上午10.11.45.png表示数据屏幕快照 2016-08-09 上午10.15.47.png中的特征总数,对不同的数据屏幕快照 2016-08-09 上午10.15.47.png取值可能不同。为了处理这个问题,定义松弛特征

屏幕快照 2016-08-09 上午10.18.50.png

式中S是一个常数。选择足够大的常数S使得对训练数据集的所有数据屏幕快照 2016-08-09 上午10.15.47.png,屏幕快照 2016-08-09 上午10.21.49.png成立。这时特征总数可取S。

由式屏幕快照 2016-08-09 上午9.55.55.png,对于转移特征屏幕快照 2016-08-09 上午9.55.22.png屏幕快照 2016-08-09 上午10.23.02.png的更新方程是

屏幕快照 2016-08-09 上午10.25.32.png

其中,

屏幕快照 2016-08-09 上午10.26.45.png

同样由式屏幕快照 2016-08-09 上午10.00.18.png,对于状态特征屏幕快照 2016-08-08 下午4.26.44.png屏幕快照 2016-08-09 上午10.23.02.png的更新方程是

屏幕快照 2016-08-09 上午10.29.33.png

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

屏幕快照 2016-08-09 上午10.32.51.png

利用前向-后向递推公式,可以很容易地计算屏幕快照 2016-08-09 上午10.41.31.png

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

屏幕快照 2016-08-09 上午10.42.59.png

这里,屏幕快照 2016-08-09 上午10.44.13.png是特征屏幕快照 2016-08-09 上午10.44.26.png的期望值,屏幕快照 2016-08-09 上午10.44.46.png,屏幕快照 2016-08-09 上午10.45.19.png是多项式方程唯一的实根,可以用牛顿法求得。从而求得相关的屏幕快照 2016-08-09 上午10.47.19.png

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

屏幕快照 2016-08-09 上午10.47.42.png

这里,屏幕快照 2016-08-09 上午10.48.33.png是特征屏幕快照 2016-08-09 上午10.48.58.png的期望值,屏幕快照 2016-08-09 上午10.49.27.png,屏幕快照 2016-08-09 上午10.49.52.png是多项式方程唯一的实根,也可以用牛顿法求得。

拟牛顿法

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

屏幕快照 2016-08-09 上午10.51.34.png

学习的优化目标函数是

屏幕快照 2016-08-09 上午10.52.45.png

其梯度函数是

屏幕快照 2016-08-13 上午9.57.09.png

拟牛顿法的BFGS算法如下。

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

输入:特征函数屏幕快照 2016-08-09 上午10.53.43.png;经验分布屏幕快照 2016-08-09 上午10.54.04.png;

输出:最优参数值屏幕快照 2016-08-09 上午10.54.31.png;最优模型屏幕快照 2016-08-09 上午10.54.58.png

(1)选定初始点屏幕快照 2016-08-09 上午10.55.30.png,取屏幕快照 2016-08-09 上午10.56.00.png为正定对称矩阵,置屏幕快照 2016-08-09 上午10.56.27.png

(2)   计算屏幕快照 2016-08-09 上午10.57.30.png。若屏幕快照 2016-08-09 上午10.57.58.png,则停止计算;否则转(3)

(3)屏幕快照 2016-08-09 上午10.58.33.png求出屏幕快照 2016-08-09 上午10.58.52.png

(4)一维搜索:求屏幕快照 2016-08-09 上午10.59.36.png使得

屏幕快照 2016-08-09 上午11.00.41.png

(5)屏幕快照 2016-08-09 上午11.01.37.png

(6)计算屏幕快照 2016-08-09 上午11.02.43.png,若屏幕快照 2016-08-09 上午11.03.25.png=0,则停止计算;否则,按下式求出屏幕快照 2016-08-09 上午11.03.51.png:

屏幕快照 2016-08-09 上午11.04.24.png

其中,

屏幕快照 2016-08-09 上午11.05.04.png

(7)屏幕快照 2016-08-09 上午11.05.38.png,转(3)。

条件随机场的预测算法

条件随机场的预测问题是给定条件随机场屏幕快照 2016-08-09 上午11.08.44.png和输入序列(观测序列)x,求条件概率最大的输出序列(标记序列)屏幕快照 2016-08-09 上午11.09.13.png,即对观测序列进行标注。条件随机场的预测算法是著名的维特比算法。

由式屏幕快照 2016-08-09 上午11.09.59.png可得:

屏幕快照 2016-08-09 上午11.11.00.png

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

屏幕快照 2016-08-09 上午11.11.55.png

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

屏幕快照 2016-08-09 上午11.12.35.png

注意,这时只需计算非规范化概率,而不必计算概率,可以大大提高效率。为了求解最优路径,将屏幕快照 2016-08-09 上午11.11.55.png写成如下形式:

屏幕快照 2016-08-09 上午11.17.06.png

其中,

屏幕快照 2016-08-09 上午11.18.04.png

是局部特征向量。

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

屏幕快照 2016-08-09 上午11.18.58.png

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

屏幕快照 2016-08-09 上午11.22.23.png

屏幕快照 2016-08-09 上午11.23.10.png

直到屏幕快照 2016-08-09 上午11.24.01.png时终止。这时求得非规范化概率的最大值为

屏幕快照 2016-08-09 上午11.24.31.png

及最优路径的终点

屏幕快照 2016-08-09 上午11.25.18.png

由此最优路径终点返回,

屏幕快照 2016-08-09 上午11.27.18.png

求得最优路径屏幕快照 2016-08-09 上午11.27.57.png

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

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

输入:模型特征向量屏幕快照 2016-08-09 上午11.28.47.png和权值向量屏幕快照 2016-08-09 上午11.29.02.png,观测序列屏幕快照 2016-08-09 上午11.31.42.png

输出:最优路径屏幕快照 2016-08-09 上午11.32.06.png

(1)初始化

屏幕快照 2016-08-09 上午11.32.34.png

(2)递推。对屏幕快照 2016-08-09 上午11.33.26.png

屏幕快照 2016-08-09 上午11.32.49.png

(3)终止

屏幕快照 2016-08-09 上午11.34.11.png

(4)返回路径

屏幕快照 2016-08-09 上午11.34.42.png

求得最优路径屏幕快照 2016-08-09 上午11.35.30.png

CRF实现

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

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

Reference

《统计学习方法》

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

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

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    CRF算法的推导,源自于ME,MEMM算法的改进。任何算法的成功,都是在原有基础上继承改进而来的。讲述CRF,不得不先讲述最大熵模型,ME,一步一步地来。MEMM最大的缺点是标注偏置问题,原因是团势能函数归一化是局部的,每个特征的类别分布式不均匀的,CRF在此基础上进行了改进。学习这些算法,最好阅读英语原版的学术论文,搞清楚算法的来龙去脉。

    小鸟4个月前 (07-13)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机