条件随机场

条件随机场(conditional random field,简称 CRF),是一种鉴别式机率模型,是随机场的一种,常用于标注或分析序列资料,如自然语言文字或是生物序列。 如同马尔可夫随机场,条件随机场为无向性之图模型,图中的顶点代表随机变量,顶点间的连线代表随机变量间的相依关系,在条件随机场当中,随机变量 Y 的分布为条件机率,给定的观察值则为随机变量 X。原则上,条件随机场的图模型布局是可以任意给定的,一般常用的布局是链接式的架构,链接式架构不论在训练(training)、推论(inference)、或是解码(decoding)上,都存在有效率的算法可供演算。 条件随机场跟隐马尔可夫模型常被一起提及,条件随机场对于输入和输出的机率分布,没有如隐马尔可夫模型那般强烈的假设存在。 线性链条件随机场应用于标注问题是由Lafferty等人与2001年提出的。

来源:维基百科
简介

条件随机场(CRF)可以理解为逻辑回归分类器对任意图形结构的扩展,或者是结构化数据的生成模型(如隐马尔可夫模型)的判别性模拟。条件随机场是机器学习领域比较复杂的一个算法模型,原因在于其涉及到的定义多(概率图模型、团等概率)、数学上近似完美。

要理解CRF,首先需要理解概率图模型的一些基本概念,我们首先介绍因子图能否“描述”一个分布的定义:

设N(a)为一组变量索引的索引,如果存在一组局部函数Ψa,使得分布p(y)可被写为:

则分布p(y)可以根据因子图G进行因式分解。

下图显示了一个关于三个随机变量的因子图的例子。在该图中,圆圈是变量节点,阴影框是因子节点。我们根据它们索引的变量或因素来标记节点。这个因子图描述了三个变量的所有分布p的集合,即对于y=(y1,y2,y3),它们可以写为p(y1,y2,y3)=Ψ1(y1,y2)Ψ2(y2,y3)Ψ3(y1,y3)。

图形模型的分解与其域中变量之间的条件独立性之间存在紧密联系,这种联系可以通过一个不同的无向图来理解,称为马尔可夫网络,它直接代表多变量分布中的条件独立关系。马尔可夫网络是仅含随机变量的图形。若让G代表一个无向图,它覆盖整数V = {1,2,...,| Y |},并每个感兴趣的随机变量进行索引。对于一个变量s∈V,设N(s)表示其在G中的邻域,那么,如果分布p满足局部马尔科夫性质,则称p是关于G的马尔可夫。局部马尔科夫性质为:对于任意两个变量Y_{s},Y_{t}∈Y,给定邻域Y_{N(s)},变量Y_{s}条件独立于Y_{t}。直观地说,这意味着Y_{N(s)}本身包含了所有对预测Y_{s}有用的信息。

接下来我们首先介绍线性链条件随机场(linear-chain conditional random field),然后给出更具一般性的条件随机场定义。

令Y,X为随机向量,θ= {θ_{k}}∈K^R为参数向量,F = {f_{k}(y,y^',x_{t})}_{ k = 1}^K为一组实值特征函数。那么线性链条件随机场就是一个分布p(y | x),其形式为:

其中Z(x)是依赖于输入的归一化函数:

可以得出,线性链条件随机场可以描述为x和y上的因子图,即:

其中每个局部函数Ψ_{t}都有特殊的对数线性形式:

下图给出几种线性链条件随机场:

上图模型只包含当前状态的特征。

上图模型转换因子取决于当前的观察结果。

上图模型转换因子取决于全部的观察结果。

下面我们将条件随机场的定义更一般化,给定如下定义:

设G是X和Y上的因子图。如果对任何X的值x,分布p(y | x)可以根据G因式分解,那么(X,Y)是一个条件随机场。

因此,每个条件分布p(y | x)都是一些因子图的CRF,即便这些因子图可能并不重要。如果F = {Ψ_{a}}是G中的一组因子,那么CRF的条件分布是:

这个方程与无向图模型的一般定义(上文中第一个定义)之间的区别在于现在归一化常数Z(x)是观测变量x的函数。由于我们不断简化图形模型,因此可能会出现以下情况:当Z(x)为可计算的时而Z却不是。

在实际应用中,CRF可以被应用于物体识别和图像分割,如对神经网络输出的图像分割结果进行处理(post-processing)来改善神经网络生成的mask线条一般比较粗糙的问题,生成更干净、细致的图片。

[描述来源:Sutton, C.; McCallum, A. (2011). An Introduction to Conditional Random Fields. Foundations and Trends in Machine Learning. 4(4): 267–373.]

发展历史

描述

自从Lafferty,McCallum和Pereira提出了条件随机场用于分割和标记序列数据后,关于条件随机场的研究一直很活跃。

定义CRF时最重要的考虑因素之一在于指定重复的结构和参数绑定,目前已经有许多在这方面的研究。2002年Taskar, Abbeel和Koller提出在许多监督学习任务中,要被标记的实体以复杂的方式相互关联,并且它们的标签不是独立的。例如,在超文本分类中,链接页面的标签高度相关。为适应这种特点,他们提出了一个基于(条件)马尔科夫网络的替代框架,该框架是一种通用的CRF,其中图形结构和参数绑定由类似SQL的语法确定。2004年Charles Sutton, Andrew McCallum和Khashayar Rohanimanesh提出了动态条件随机场(Dynamic Conditional Random Fields),这是一种线性链条件随机场的推广,它允许以类似于动态贝叶斯网络的方式,在每个时间步骤允许多个标签,而不是单个标签。Matthew Richardson和Pedro Domingos提出一种简单的方法来将一阶逻辑和概率图模型结合,叫做马尔科夫逻辑网络(MLN),其使用逻辑公式来指定无向模型中局部函数的范围。实质上,知识库中的每个一阶规则都有一组参数。MLN的逻辑部分可以被看作是一个编程约定,用于指定无向模型的重复结构和参数绑定。

在应用方面,它通常用于标记或解析序列数据,如自然语言处理或生物序列以及计算机视觉,如He等人将CRF用于标记图像,从而将其上下文特征也纳入考虑范围。具体而言,CRF在POS标签,浅层解析(Sha, F.; Pereira, F. , 2003),命名实体识别,基因发现和肽关键功能区域发现以及其他任务中都有广泛应用,是隐马尔可夫模型(HMM)的替代方案。在计算机视觉中,CRF通常用于物体识别和图像分割(Philipp Krahenbuhl,Vladlen Koltun,2011)。

主要事件

年份

事件

相关论文/Reference

2001

Lafferty,McCallum和Pereira提出了条件随机场用于分割和标记序列数据

Lafferty, J., McCallum, A., Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282–289.

2002

Taskar, Abbeel和Koller提出了一个基于(条件)马尔科夫网络的替代框架

Taskar, B.; Abbeel, P.; Koller, D. (2002). Discriminative probabilistic models for relational data. Conference on Uncertainty in Artificial Intelligence (UAI).

2003

Sha, F.和Pereira, F. ,展示了如何训练一个条件随机场,以达到与CoNLL任务中所报道的任何基础名词短语组块方法一样好的性能。

Sha, F.; Pereira, F. (2003). shallow parsing with conditional random fields. Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology. 1:134-141.

2004

Charles Sutton, Andrew McCallum和Khashayar Rohanimanesh提出了动态条件随机场(Dynamic Conditional Random Fields)

Sutton, C.; Rohanimanesh, K.; McCallum, A. (2004). Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. International Conference on Machine Learning (ICML).8:693—723.

2004

He等人将CRF用于标记图像,从而将其上下文特征也纳入考虑范围。

He, X.; Zemel, R. S.; Carreira-Perpinan, M .A. (2004). Multiscale conditional random fields for image labeling. Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2:695-702.

2006

Matthew Richardson和Pedro Domingos提出一种简单的方法来将一阶逻辑和概率图模型结合,叫做马尔科夫逻辑网络(MLN)

Richardson, M.; Domingos, P. (2006). Markov logic networks. Machine Learning. 62(1-2): 107–136.

2011

Philipp Krahenbuhl和Vladlen Koltun利用CRF改进神经网络生成的图像分割图片

Krahenbuhl, P.; Koltun, V. (2011). Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials. NIPS.

发展分析

瓶颈

条件随机场收敛速度慢,训练的参数也更多,因而需要很长的训练时间。另外模型复杂度也较高。

未来发展方向

条件随机场模型自然的将上下文标记间的联系纳入模型的考虑中,可以灵活地设计特征,因而是自然语言处理领域最常用也是表现最好的模型之一,其在这个领域还有很大的发展空间。此外,条件随机场在计算机视觉(如改进图像分割结果)等领域也表现不俗。

Contributor: Yuanyuan Li

相关人物
本·塔斯卡尔
本·塔斯卡尔
机器学习以及计算语言学和计算机视觉应用领域的教授和研究员,宾夕法尼亚大学计算机与信息科学的副教授。他是第一个定义最大边际马尔可夫网络的人,也是统计关系学习的先驱。
约翰·D·拉夫尔提
约翰·D·拉夫尔提
美国科学家,耶鲁大学教授,机器学习领域的顶尖研究者。他最出名的是与Andrew McCallum和Fernando C.N. Pereira提出条件随机场。 研究兴趣:统计机器学习、信息检索和自然语言处理,专注于非参数法的计算和统计方面、高维数据和图模型。曾在CMU任职,帮助建立世界第一个机器学习系。
Khashayar Rohanimanesh
Khashayar Rohanimanesh
彼得阿贝尔
彼得阿贝尔
安德鲁·麦卡勒姆
安德鲁·麦卡勒姆
Andrew McCallum是马萨诸塞州阿默斯特大学计算机科学系的教授兼研究员。他的主要专业是机器学习,自然语言处理,信息提取,信息整合和社交网络分析。
达芙妮·科勒
达芙妮·科勒
Fernando Pereira
Fernando Pereira
何旭铭
何旭铭
查尔斯·萨顿
查尔斯·萨顿
谷歌大脑的研究科学家,爱丁堡大学机器学习Reader(相当于副教授)。他发表了50多篇关于概率机器学习和深度学习的论文,研究方向自然语言处理( NLP )、计算机系统分析、可持续能源、数据分析和软件工程。他在软件工程方面的工作获得了ACM杰出论文奖。他曾担任爱丁堡大学EPSRC数据科学博士培训中心主任。他是英国国家人工智能和数据科学研究所艾伦·图灵研究所的研究员。
简介
相关人物