第讲条件随机场课件.pdf

第讲条件随机场课件.pdf

《第讲条件随机场课件.pdf》由会员分享，可在线阅读，更多相关《第讲条件随机场课件.pdf（71页珍藏版）》请在冰点文库上搜索。

第14讲条件随机场余正涛余正涛郭剑毅郭剑毅李玉惠李玉惠李勇李勇苏磊苏磊范玉刚等范玉刚等昆明理工大学信息工程与自动化学院大纲产生式模型和判别式模型产生式模型和判别式模型概率图模型概率图模型条件随机场理论条件随机场理论条件随机场模型应用示例条件随机场模型应用示例条件随机场工具包使用条件随机场工具包使用条件随机场研究进展条件随机场研究进展产生式模型：

构建o和s的联合分布p（s,o），因可以根据联合概率来生成样本，如HMM，BNs，MRF。

产生式模型：

无穷样本=概率密度模型=产生模型=预测判别式模型：

有限样本=判别函数=预测模型=预测判别式模型：

构建o和s的条件分布p（s|o），因为没有s的知识，无法生成样本，只能判断分类，如SVM，CRF，MEMM。

o和s分别代表观察序列和标记序列产生式模型和判别式模型举例（1,0）,（1,0）,（2,0）,（2,1）产生式模型：

P（x,y）：

P（1,0）=1/2,P（1,1）=0,P（2,0）=1/4,P（2,1）=1/4.判别式模型：

P（y|x）：

P（0|1）=1,P（1|1）=0,P（0|2）=1/2,P（1|2）=1/2Generativemodel：

从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度，不关心判别边界。

优点:

实际上带的信息要比判别模型丰富，研究单类问题比判别模型灵活性强能更充分的利用先验知识模型可以通过增量学习得到缺点：

学习过程比较复杂在目标分类问题中易产生较大的错误率两种模型比较Discriminativemodel：

寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。

优点优点:

分类边界更灵活，比使用纯概率方法或生产模型得到的更高级。

能清晰的分辨出多类或某一类与其他类之间的差异特征在聚类、viewpointchanges,partialocclusionandscalevariations中的效果较好适用于较多类别的识别缺点：

缺点：

不能反映训练数据本身的特性。

能力有限，可以告诉你的是1还是2，但没有办法把整个场景描述出来。

二者关系：

由生成模型可以得到判别模型，但由判别模型得不到生成模型。

两种模型比较概率图模型基本思想朴素贝叶斯分类器隐马尔可夫模型最大熵模型最大熵马尔可夫模型（,）（,）（,）（,）GVEGVEGVEGVE=:

VVVV顶点/节点，表示随机变量:

EEEE边/弧两个节点邻接两个节点邻接：

两个节点之间存在边，记为，不存在边，表示条件独立ijXX路径路径：

若对每个I,都有，则称序列为一条路径。

1111iiiiiiiiXXXXXXXX1,.,NXX概率图模型概率图模型：

是一类用图的形式表示随机变量之间条件依赖关系的概率模型，是概率论与图论的结合。

图中的节点表示随机变量，缺少边表示条件独立假设。

概率图模型基本思想有向图：

最基本的是贝叶斯网络（BayesianNetworks,BNs）年龄Age职业Occupation气候Climate疾病Disease症状Symptoms举例（,）（,）（,）（,）PAOCDSMPAOCDSMPAOCDSMPAOCDSM=（）（）（）（,）（,）（）（）（）（,）（,）（）（）（）（,）（,）（）（）（）（,）（,）PAMPOMPCMPDAOCMPSDMPAMPOMPCMPDAOCMPSDMPAMPOMPCMPDAOCMPSDMPAMPOMPCMPDAOCMPSDM根据图中边有无方向，常用的概率图模型分为两类：

根据图中边有无方向，常用的概率图模型分为两类：

概率图模型基本思想1111XXXX2222XXXX3333XXXX4444XXXX5555XXXX121212121111（,）（）（,）（）（,）（）（,）（）NNNNNiiNiiNiiNiiiiiiPXXXpXXPXXXpXXPXXXpXXPXXXpXX=，1251213242534125121324253412512132425341251213242534（,）（）（）（）（）（）（,）（）（）（）（）（）（,）（）（）（）（）（）（,）（）（）（）（）（）PXXXpXpXXpXXpXXpXXXPXXXpXpXXpXXpXXpXXXPXXXpXpXXpXXpXXpXXXPXXXpXpXXpXXpXXpXXX=，每个节点的条件概率分布表示为：

P（当前节点|它的父节点）联合分布：

有向图模型的联合概率分解：

有向图模型的联合概率分解：

概率图模型基本思想无向图：

马尔可夫随机场（MarkovRandomFields,MRF）马尔可夫随机场模型中包含了一组具有马尔可夫性质的随机变量，这些变量之间的关系用无向图来表示（）（,）,（,）,（,）,（,）,ijijijijijijijijijijijijpxxjipxxxxpxxjipxxxxpxxjipxxxxpxxjipxxxx=马尔科夫性：

举例概率图模型基本思想不同之处无向图模型因子是势函数，需要全局归一有向图模型因子是概率分布、无需全局归一共同之处将复杂的联合分布分解为多个因子的乘积优缺点无向图模型中势函数设计不受概率分布约束，设计灵活，但全局归一代价高有向图模型无需全局归一、训练相对高效有向图模型和无向图模型的对比序列序列HMMsMEMsNBsyyyyxxxx有向图模型和无向图模型的对比设x是一个类别未知的数据样本，Y为类别集合，若数据样本x属于一个特定的类别yj，那么分类问题就是决定P（yj|x），即在获得数据样本x时，确定x的最佳分类。

所谓最佳分类，一种办法是把它定义为在给定数据集中不同类别yj先验概率的条件下最可能的分类。

贝叶斯理论提供了计算这种可能性的一种直接方法。

朴素贝叶斯分类器jjjjyyyyjjjjyyyy123123123123123123123123（,）（）（）（）（）（,）（）（）（）（）（,）（）（）（）（）（,）（）（）（）（）jjjjjjjjjjjjjjjjjjjjPxxxypypxypxypxyPxxxypypxypxypxyPxxxypypxypxypxyPxxxypypxypxypxy=jjjjyyyyxxxx朴素贝叶斯分类器的概率图表示隐马尔可夫概念（HMM）HMM是一种随机过程，它用概率统计的方法来描述语音信号的变化过程。

HMM与通常的Markov链的不同之处在于其观察结果不是与状态有确定的对应关系，而是系统所处状态的概率函数，所以模型本身是隐藏的，它与观察结果之间还有一层随机的关系。

HMM是对语音信号的时间序列结构建立统计模型，将之看做一个数学上的双重随机过程：

一个是用具有有限状态的Markov链来模拟语音信号统计特性变化的隐含随机过程，另一个是与Markov链的每一个状态相关联的观测序列观测序列的随机过程。

前者通过后者表现出来，但前者的具体参数是不可测的。

隐马尔可夫概念（HMM）HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系HMM是一个双重随机过程，两个组成部分：

马尔可夫链马尔可夫链：

描述状态的转移，用转移概率转移概率描述。

一般随机过程一般随机过程：

描述状态与观察序列间的关系，用观察值概率观察值概率描述。

隐马尔可夫模型马尔可夫模型：

是一个三元组=（S,A）其中S是状态的集合，是初始状态的概率,A是状态间的转移概率。

S0S1ST-1ST一阶马尔可夫链晴云雨0.500.3750.1250.500.3750.1250.500.3750.1250.500.3750.1250.250.1250.6250.250.1250.6250.250.1250.6250.250.1250.6250.250.3750.3750.250.3750.3750.250.3750.3750.250.3750.375todaytodaytodaytodaysuncloudrainsuncloudrainsuncloudrainsuncloudrainyesterdaysunyesterdaysunyesterdaysunyesterdaysuncloudcloudcloudcloudrainrainrainrain=（1，1，0，0，0）0）123123123123,SsssSsssSsssSsss=晴云雨一阶马尔可夫模型的例子问题问题：

假设今天是晴天，请问未来三天的天气呈现云雨晴的概率是多少？

隐马尔可夫模型0.050.150.200.600.050.150.200.600.050.150.200.600.050.150.200.600.250.250.250.250.250.250.250.250.250.250.250.250.250.250.250.250.50.350.100.050.50.350.100.050.50.350.100.050.50.350.100.05soggydampdryishdrysoggydampdryishdrysoggydampdryishdrysoggydampdryishdrysunsunsunsuncloudcloudcloudcloudrainrainrainrainHMM是一个五元组=（Y,X,A,B），其中Y是隐状态（输出变量）的集合，）X是观察值（输入）集合，是初始状态的概率，A是状态转移概率矩阵，B是输出观察值概率矩阵。

0.500.3750.1250.500.3750.1250.500.3750.1250.500.3750.1250.250.1250.6250.250.1250.6250.250.1250.6250.250.1250.6250.250.3750.3750.250.3750.3750.250.3750.3750.250.3750.375todaytodaytodaytodaysuncloudrainsuncloudrainsuncloudrainsuncloudrainyesterdaysunyesterdaysunyesterdaysunyesterdaysuncloudcloudcloudcloudrainrainrainrain隐马尔可夫模型HMMHMM实例实验进行方式如下：

根据初始概率分布，随机选择N个缸中的一个开始实验根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为x1，并把球放回缸中根据缸的转移概率分布，随机选择下一口缸，重复以上步骤。

UrnNUrnNUrn1Urn1Urn2Urn2ObservedBallSequenceObservedBallSequence最后得到一个描述球的颜色的序列x1,x2,称为观察值序列X。

TTTT11111111（）（）（）（）（）（）（）（）（）（）（）（）iiiiiiiiiiiiiiiiiiiiPXpyypxyPXpyypxyPXpyypxyPXpyypxy=所所有有的的YYHMMsHMMs等生产式模型存在的问题：

等生产式模型存在的问题：

由于生成模型定义的是联合概率，必须列举所有观察序列的可能值，这对多数领域来说是比较困难的。

基于观察序列中的每个元素都相互条件独立。

即在任何时刻观察值仅仅与状态（即要标注的标签）有关。

对于简单的数据集，这个假设倒是合理。

但大多数现实世界中的真实观察序列是由多个相互作用的特征和观察序列中较长范围内的元素之间的依赖而形成的。

最大熵模型最大熵的原理认为，从不完整的信息（例如有限数量的训练数据）推导出的唯一合理的概率分布应该在满足这些信息提供的约束条件下拥有最大熵值。

求解这样的分布是一个典型的约束优化问题。

最大熵模型主要是在已有的一些限制条件下估计未知的概率分布。

熵的计算公式：

熵的性质：

（）（）log（）（）（）log（）（）（）log（）（）（）log（）xXxXxXxXHXpxpxHXpxpxHXpxpxHXpxpx=（）0log0log0log0logHXXHXXHXXHXX其中X在离散分布时是随机变量的个数；当X为确定值，即没有变化的可能时，左边等式成立；可以证明，当X服从均匀分布时，右边等式成立，即均匀分布时熵最大。

MEMM：

用一个P（yi|yi-1,xi）分布来替代HMM中的两个条件概率分布，它表示从先前状态，在观察值下得到当前状态的概率，即根据前一状态和当前观察预测当前状态。

每个这样的分布函数都是一个服从最大熵的指数模型。

HMM：

状态集合Y，观察值集合X，两个状态转移概率：

从yi-1到yi的条件概率分布P（yi|yi-1），状态yi的输出观察值概率P（xi|yi），初始概率P0（y）.111111111111（）exp（,）（）exp（,）（）exp（,）（）exp（,）（,）（,）（,）（,）iiiiyiaaiiyiaaiiyiaaiiyiaaiiiiiiaaaaiiiiiiiipyxfxypyxfxypyxfxypyxfxyZxyZxyZxyZxy=1111iiiiyyyyiiiiyyyy1111iiiiyyyy+1111iiiixxxxiiiixxxx1111iiiixxxx+1111iiiiyyyyiiiiyyyy1111iiiiyyyy+1111iiiixxxxiiiixxxx1111iiiixxxx+HMMMEMM1,2,1,2,1,2,1,2,iTiTiTiT=最大熵马尔科夫模型参数学习参数学习目的：

通过学习a使得MEMM中的每个转换函数达到最大熵。

GIS（GeneralizedIterativeScaling）算法编码问题编码问题Viterbi算法的思想最大熵马尔科夫模型基于文本的网络地址信息抽取任务：

完成地址，电话，传真，E-mail等信息的识别和抽取最大熵马尔科夫模型举例流程图页面预处理页面文本中加入#用于保留结构信息和页面内容的自然划分，便于对文本页面的进一步处理。

最大熵马尔科夫模型举例确定状态集合Y，观察值（特征）集合X状态集合包含：

邮编、电话、电邮、地址、联系人、账号、手机、网址、传真，对于其他可能出现的状态定义了“other”来代表。

特征集合包含：

“具有符号”“最大数字串长度为6”“最大数字串长度为11”“最大数字长度大于15”“最大数字长度小于6，字符串总长度介于8到30”“最大数字长度小于6，字符串总长度小于6”，“最大数字串长度介于6到11”“最大数字长度小于6，字符串总长度大于30”模型建立111111111111（）exp（,）（）exp（,）（）exp（,）（）exp（,）（,）（,）（,）（,）iiiiyiaaiiyiaaiiyiaaiiyiaaiiiiiiaaaaiiiiiiiipyxfxypyxfxypyxfxypyxfxyZxyZxyZxyZxy=1111iiiiyyyyiiiiyyyy1111iiiiyyyy+1111iiiixxxxiiiixxxx1111iiiixxxx+特征函数表示数据集的特性：

（,）（,）（,）（,）aaaafxyfxyfxyfxy1111（,）（,）（,）（,）0000aaaafxyfxyfxyfxy=如果x只含有6位数字&y=邮编其他进一步引入一系列的特征函数12121212,nnnnffffffffffff模型建立参数学习111111111111（）exp（,）（）exp（,）（）exp（,）（）exp（,）（,）（,）（,）（,）iiiiyiaaiiyiaaiiyiaaiiyiaaiiiiiiaaaaiiiiiiiipyxfxypyxfxypyxfxypyxfxyZxyZxyZxyZxy=用上述的状态和特征集对初步抽取样本进行统计，得到每个状态所对应的样本集，通过对于每个这样的样本集合采用GIS算法进行参数学习，最终得到MEMM。

说明：

说明：

GIS算法要求对于每一个,特征之和达到一个常数C，即有1111（,）（,）（,）（,）nnnniiiiiiiifxyCfxyCfxyCfxyC=如果不满足，则令,1111max（,）max（,）max（,）max（,）nnnniiiixyxyxyxyiiiiCfxyCfxyCfxyCfxy=并加入一个修正函数，使得11111111（,）（,）（,）（,）（,）（,）（,）（,）nnnnninininiiiiifxyCfxyfxyCfxyfxyCfxyfxyCfxy+=模型建立评测指标召回率（Recall）=正确识别出的实体个数标准结果中实体的总数精确率（Precision）=正确识别出的实体个数识别出的实体总数关键：

特征的选择100%100%模型建立标记偏见问题序列序列HMMsMEMs1111iiiiyyyyiiiiyyyy1111iiiiyyyy+1111iiiixxxxiiiixxxx1111iiiixxxx+linear-chainCRFNBsyyyyxxxx条件随机场理论概述定义Linear-chainCRFs模型特征函数选择参数估计模型推断条件随机场特点条件随机场概述条件随机场模型是Lafferty于2001年，在最大熵模型和隐马尔科夫模型的基础上，提出的一种判别式概率无向图学习模型，是一种用于标注和切分有序数据的条件概率模型。

CRF最早是针对序列数据分析提出的，现已成功应用于自然语言处理（NaturalLanguageProcessing，NLP）、生物信息学、机器视觉及网络智能等领域。

序列标注序列标注标注：

人名地名组织名观察序列：

毛泽东标注：

名词动词助词形容词副词观察序列：

今天天气非常好！

实体命名识别汉语词性标注条件随机场概述条件随机场概述简单地讲，随机场可以看成是一组随机变量的集合（这组随机变量对应同一个样本空间）。

当给每一个位置按照某种分布随机赋予一个值之后，其全体就叫做随机场随机场。

当然，这些随机变量之间可能有依赖关系，一般来说，也只有当这些变量之间有依赖关系的时候，我们将其单独拿出来看成一个随机场才有实际意义。

马尔科夫随机场（MRF）对应一个无向图。

这个无向图上的每一个节点对应一个随机变量，节点之间的边表示节点对应的随机变量之间有概率依赖关系。

因此，MRF的结构本质上反应了我们的先验知识哪些变量之间有依赖关系需要考虑，而哪些可以忽略。

具有马尔科夫性质：

离当前因素比较遥远（这个遥远要根据具体情况自己定义）的因素对当前因素的性质影响不大。

条件随机场概述现在，如果给定的MRF中每个随机变量下面还有观察值，我们要确定的是给定观察集合下，这个MRF的分布，也就是条件分布，那么这个MRF就称为CRF。

它的条件分布形式完全类似于MRF的分布形式，只不过多了一个观察集合x。

最通用角度来看，CRF本质上是给定了观察值（observations）集合的MRF设G=（V，E）是一个无向图，vvvvYYvVYYvVYYvVYYvV=是以G中节点v为索引的随机变量vvvvYYYY构成的集合。

在给定的条件下，如果每个随机变量服从马尔可XXXXvvvvYYYY夫属性，即（,）（,）,（,）（,）,（,）（,）,（,）（,）,vuvuvuvuvuvuvuvupYXYuvpYXYuvpYXYuvpYXYuvpYXYuvpYXYuvpYXYuvpYXYuv=则就构成（）,XYXYXYXY一个条件随机场。

最简单且最常用的是一阶链式结构，即线性链结构（Linear-chainCRFs）1111iiiiyyyyiiiiyyyy1111iiiiyyyy+1111iiiixxxxiiiixxxx1111iiiixxxx+CRF定义：

令表示观察序列，12121212,nnnnxxxxxxxxxxxxxxxx=12121212,nnnnyyyyyyyyyyyyyyyy=是有限状态的集合，根据随机场的基本理论：

（）1111,exp（,）（,）,exp（,）（,）,exp（,）（,）,exp（,）（,）jjiikkijjiikkijjiikkijjiikkijkjkjkjkpyxtyyxisyxipyxtyyxisyxipyxtyyxisyxipyxtyyxisyxi+1111（,）:

（,）:

（,）:

（,）:

jiijiijiijiityyxityyxityyxityyxi对于观察序列的标记位置i-1与i之间的转移特征函数（,）:

（,）:

（,）:

（,）:

kikikikisyxisyxisyxisyxi观察序列的i位置的状态特征函数将两个特征函数统一为：

1111（,）（,）（,）（,）jiijiijiijiifyyxifyyxifyyxifyyxi（）111111111111,exp（,）,exp（,）,exp（,）,exp（,）（）（）（）（）nnnnjjiijjiijjiijjiiijijijijpyxfyyxipyxfyyxipyxfyyxipyxfyyxiZxZxZxZx=11111111（）exp（,）（）exp（,）（）exp（,）（）exp（,）nnnnjjiijjiijjiijjiijijjijjijjijZxfyyxiZxfyyxiZxfyyxiZxfyyxi=Linear-chainCRFs模型关键问题特征函数的选择参数估计模型推断特征函数的选取直接关系模型的性能。

从已经标注好的训练数据集学习条件随机场模型的参数，即各特征函数的权重向量。

在给定条件随机场模型参数下，预测出最可能的状态序列。

特征函数的选择1111（,）（,）（,）（,）jjijjijjijjifyyxifyyxifyyxifyyxi1111（,）（,）（,）（,）0000bxibxibxibxi=如果时刻i观察值x是大写开头否则11111111（,）,（,）,（,）,（,）,（,）（,）（,）（,）0000iiiiiiiii