关键词:
概率无向图模型
又称马尔可夫随机场(Markov random field)或马尔可夫网络,是一个由无向图表示的联合概率分布。
图是由结点和边组成,无向图中的边没有方向。概率无向图中结点表示随机变量,边表示结点之间的概率依赖关系。
成对马尔可夫性:
设u和v是无向图G中任意两个没有连接边的结点,对应随机变量分别为Yu和Yv,图中其他所有结点为O,对应随机变量组YO,那么给定随机变量组YO的条件下,Yu和Yv是条件独立的,此为成对马尔可夫性,即
(1)
局部马尔可夫性:
设v是无向图G中的任意一个节点,W是与v有边连接的所有结点,O是除v和W之外的其他所有结点(即,与v没有边连接的所有结点),给定随机变量组YW的条件下,Yv与YO是条件独立的,此为局部马尔可夫性,即,
(2)
如果P(YO|YW)>0,那么(2)式两边同时除以P(YO|YW),
(3)
下图表示局部马尔可夫性,
上图中,假设某个黑点表示v,那么与其有边连接的有一个或大于一个白点为W,剩余的其他点(包括白点和黑点)为O。
全局马尔可夫性:
设结点集合A和B是在无向图G中被结点集合C分开的任意结点集合,结点集合A,B,C所对应的随机变量组分别是YA,YB,YC,给定随机变量组YC的条件下,YA和YB是条件独立的,此为全局马尔可夫性,即,
(4)
可用下图表示全局马尔可夫性,
从图中可见,A中任意结点到B中任意结点之间的所有路径,都经过C中结点,也就是说被C隔断,A和B关于C条件独立。
不难发现上述成对、局部和全局 马尔可夫性是等价的,从特殊到一般的过程。
概率无向图
设联合概率分布P(Y)由无向图G=(V,E)表示,结点表示随机变量,边表示随机变量之间的依赖关系。如果联合概率分布P(Y)满足成对、局部或全局马尔可夫性,就称此联合概率分布为概率无向图模型。
无向图G中如果存在一个结点子集,并且子集中任意两个结点均有边连接,则称这样的子集为团(clique)。
若C是G中的一个团,并且无法再加入一个G的其他结点,使C成为一个更大的团,那么C就是一个最大团。
如下图,由两个结点组成的团为:{Y1,Y2},{Y2,Y3},{Y3,Y4},{Y4,Y2},{Y1,Y3},有两个最大团:{Y1,Y2,Y3},{Y2,Y3,Y4}。
将概率无向图的联合概率分布表示为其最大团上的随机变量的函数乘积形式的操作,称为因子分解。
给定概率无向图G,C为G上的最大团,YC表示C对应的随机变量组,那么G对应的联合概率分布P(Y)为G中所有最大团C上的函数的乘积,
(5)
其中,Z是规范化因子,即
(6)
规范化因子保证P(Y)构成一个概率分布,即对P(Y)求和为1。函数 称为势函数,是一个严格正的函数,通常定义为指数函数,
(7)
条件随机场
给定随机变量X的条件下,随机变量Y的马尔可夫随机场称为条件随机场。这里主要涉及线性马尔可夫链,所以就介绍线性链上的特殊的条件随机场,称为线性链条件随机场。在条件概率模型中P(Y|X),Y是输出变量表示标记序列(或状态序列),X是输入变量表示需要标注的观测序列。利用训练数据集通过极大似然估计或正则化的极大似然估计学习条件概率模型。
设随机变量X和Y,P(Y|X)表示给定X的条件下Y的条件概率分布。若Y构成一个由无向图G=(V,E)表示的马尔可夫随机场,即
(8)
对任意结点v 成立,则称条件概率分布P(Y|X)为条件随机场。其中w~v表示图G中与v结点有边连接的所有结点w,w!=v表示结点v以外的所有结点。从上式可见,在给定X的大前提下,给定除v 之外所有结点条件下 v的条件概率,与 给定v结点有边连接的所有邻结点条件下v 的条件概率 相等,也就是说 v结点 与 除v和v的邻结点w之外的所有结点子集关于w条件独立,这正好就是指局部马尔可夫性。
实际中,一般假设X与Y有相同的图结构。
考虑如下图所示的线性链,此时图G可以表示为:G=(V={1,2,...,n}, E={(i,i+1)}), i=1,2,...,n-1,此时X=(X1,X2,...,Xn),Y=(Y1,Y2,...,Yn),最大团是相邻两个结点的集合。
线性链条件随机场 X和Y有相同图结构的线性链条件随机场
线性链条件随机场
设X=(X1,X2,...,Xn),Y=(Y1,Y2,...,Yn)均为线性链表示的随机变量序列,给定X的条件下,Y的条件概率分布P(Y|X)构成条件随机场,即满足马尔可夫性:
(9)
其中,i=1,2,...,n,且在i=1和n的时候分别只考虑右边 和 左边,此时 P(Y|X)表示线性链条件随机场。
在标注问题中,X表示观测序列,Y表示对应的标注序列(或状态序列)
至此,以上内容都不难理解,然而下面给出线性链条件随机场的参数化形式则不是很显然的了,事实上,稍显突兀,不过没关系,本篇文章只要对上述内容能够理解即可,下面的参数化形式后面还要进行深入讨论的,这里只需有个印象便可。
设P(Y|X)为线性链条件随机场,则随机变量X取值为x的条件下,随机变量Y取值为y的条件概率为,
(10)
其中,
(11)
式中,tk和sl是特征函数,λk和ul是对应的权值,Z(x)是规范化因子,求和是在所有可能的输出序列{y}上进行的。
(10)和(11)是线性链条件随机场模型的参数化形式,表示给定输入序列x,对输出序列y的预测的条件概率。其实,tk 是定义在边上的特征函数,称为转移特征,依赖于当前和前一个位置,sl 是定义在结点上的特征函数,称为状态特征,依赖于当前位置。tk 和 sl 都依赖于位置,是局部特征函数,通常, tk 和 sl 取值为 1 或 0; 当满足特征条件时取值为1,否则为0。
ref
统计学习方法,李航
条件随机场入门条件随机场的概率计算问题
条件随机场的概率计算问题是给定条件随机场P(Y|X),输入序列x和输出序列y,计算条件概率$P(y_i|x)$,$P(y_{i-1},y_i|x)$以及相应的数学期望的问题。为了方便起见,像HMM那样,引进前向-后向向量,递归地计算以上概率及期望值。这样... 查看详情
条件随机场介绍——anintroductiontoconditionalrandomfields
2.模型本部分从建模的角度讨论条件随机场,解释条件随机场如何将结构化输出上的概率分布表示为高维输入向量的函数。条件随机场即可以理解为逻辑回归在任意图结构上的扩展,也可以理解为结构化数据的生成模型(如隐马... 查看详情
条件随机场(crf)-基础
条件随机场(conditionalrandomfields,简称CRF,或CRFs)下文简称CRF,是一种典型的判别模型,相比隐马尔可夫模型可以没有很强的假设存在,在分词、词性标注、命名实体识别等领域有较好的应用。CRF是在马尔可夫随机场的基础... 查看详情
ml-13-5条件随机场(crf-conditionalrandomfield)
目录知识串讲HMMVSMEMM从随机场到马尔科夫随机场条件随机场(CRF)MRF因子分解定理线性链条件随机场(Linear-CRF)一句话简介:条件随机场(ConditionalRandomFields,以下简称CRF)是给定一组输入序列条件下另一组输出序列的条件概率分布模型... 查看详情
条件随机场介绍——anintroductiontoconditionalrandomfields
条件随机场介绍原文:AnIntroductiontoConditionalRandomFields作者:CharlesSutton(SchoolofInformatics,UniversityofEdinburgh,Edinburgh,EH89AB,UK)AndrewMcCallum(DepartmentofComputerScience,UniversityofMassachusetts,Amh 查看详情
理解条件随机场(转)
理解条件随机场最好的办法就是用一个现实的例子来说明它。但是目前中文的条件随机场文章鲜有这样干的,可能写文章的人都是大牛,不屑于举例子吧。于是乎,我翻译了这篇文章。希望对其他伙伴有所帮助。原文在这里[http:... 查看详情
条件随机场
...calT$上进行对数似然函数$mathcalL$的极大化。根据上一篇《条件随机场(三)》,我们知道线性链CRF的模型为egin{equation}p_{vec{lambda}}(vecy|vecx)=frac1{Z_{vec{lambda}}(vecx)}exp( 查看详情
ml-13-6条件随机场的三个问题(crf-conditionalrandomfield)
目录条件随机场CRF——前向后向算法评估标记序列概率条件随机场CRF——模型参数学习条件随机场CRF——维特比算法解码一、条件随机场CRF——前向后向算法评估标记序列概率 linear-CRF第一个问题是评... 查看详情
条件随机场
概述条件随机场(conditionalrandomfield,CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型,其特点是假设输出随机变量构成马尔可夫随机场。条件随机场可以用于不同的预测问题,本章主要讲述线性链(linearc... 查看详情
条件随机场
...有结点为O,对应随机变量组YO,那么给定随机变量组YO的条件下,Yu和Yv是 查看详情
nlp——图模型条件随机场(conditionalrandomfield,crf)
...rkovrandomfield,无向图模型)简单回顾 (二)条件随机场(Conditionalrandomfield,CRF) 这篇写的非常浅,基于[1]和[5]梳理。感觉[1]的讲解很 查看详情
条件随机场介绍——anintroductiontoconditionalrandomfields
6.相关研究和未来方向本部分简要分析条件随机场的发展路线,特别是在结构化预测(structuredprediction)方面。除此之外,还将分析条件随机场与神经网络和最大熵马尔可夫模型(MEMMs)的关系。最后列出了几个未来研究的开放领... 查看详情
条件随机场(crf)-1-简介(转载)
转载自:http://www.68idc.cn/help/jiabenmake/qita/20160530618222.html 首先我们先弄懂什么是“条件随机场”,然后再探索其详细内容。 于是,先介绍几个名词。马尔可夫链 & 查看详情
条件随机场摘要
条件随机场(ConditionalRandomFields,以下简称CRF)是给定一组输入序列条件下另一组输出序列的条件概率分布模型,在自然语言处理中得到了广泛应用。HMM引入了马尔科夫假设,即当前时刻的状态只与其前一时刻的状态有关,HMM是一种... 查看详情
条件随机场-应用
今天介绍CRFs在中文分词中的应用 工具:CRF++,可以去 https://taku910.github.io/crfpp/下载,训练数据和测试数据可以考虑使用bakeoff2005,这是链接http://sighan.cs.uchicago.edu/bakeoff2005/ 首先需要了解一些概念 字标记法——统... 查看详情
条件随机场(crf)占坑,待补充
CRF看了好久,一直感觉理解不太透彻,今天按照52自然语言处理运行了一下CRF++,先占坑,等忙完毕设,好好整理一下CRF与HMM(20181026) 查看详情
条件随机场(crf)-2-定义和形式(转载)
转载自:http://www.68idc.cn/help/jiabenmake/qita/20160530618218.html 参考书本:《2012.李航.统计学习方法.pdf》 书上首先介绍概率无向图模型,然后叙述条件随机场的定义和 查看详情
条件随机场介绍——anintroductiontoconditionalrandomfields
参考文献[1]S.M.AjiandR.J.McEliece,“Thegeneralizeddistributivelaw,”IEEETrans-actionsonInformationTheory,vol.46,no.2,pp.325–343,2000.[2]Y.Altun,I.Tsochantaridis,andT.Hofmann,“HiddenMarkovsupportvectormachin 查看详情