条件随机场课件.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《条件随机场课件.pptx》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 条件 随机 课件
- 资源描述:
-
1、条件随机场1条件随机场模型是Lafferty于2001年,在最大熵模型和隐马尔科夫模型的基础上,提出的一种判别式概率无向图学习模型,是一种用于标注和切分有序数据的条件概率模型。CRF最早是针对序列数据分析提出的,现已成功应用于自然语言处理(Natural Language Processing,NLP)、生物信息学、机器视觉及网络智能等领域。序列标注标注:人名 地名 组织名观察序列:毛泽东标注:名词 动词 助词 形容词 副词 观察序列:今天天气非常好!实体命名识别汉语词性标注 产生式模型:构建o和s的联合分布p(s,o),因可以根据联合概率来生成样本,如HMM,BNs,MRF。产生式模型:无穷
2、样本=概率密度模型=产生模型 =预测判别式模型:有限样本=判别函数=预测模型 =预测 判别式模型:构建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/2Generative model:从统计的角度表示数据的分布情况,能够反映同类数据本身的相似度,不关心
3、判别边界。优点:实际上带的信息要比判别模型丰富,研究单类问题比判别模型灵活性强能更充分的利用先验知识模型可以通过增量学习得到缺点:学习过程比较复杂在目标分类问题中易产生较大的错误率 Discriminative model:寻找不同类别之间的最优分类面,反映的是异类数据之间的差异。分类边界更灵活,比使用纯概率方法或生产模型得到的更高级。能清晰的分辨出多类或某一类与其他类之间的差异特征在聚类、viewpoint changes,partial occlusion and scale variations中的效果较好适用于较多类别的识别不能反映训练数据本身的特性。能力有限,可以告诉你的是1还是2,
4、但没有办法把整个场景描述出来。由生成模型可以得到判别模型,但由判别模型得不到生成模型。(,)GV E:V顶点/节点,表示随机变量:E边/弧两个节点邻接:两个节点之间存在边,记为 ,不存在边,表示条件独立ijXX路径:若对每个i,都有 ,则称序列 为一条路径1iiXX 1,.,NXX是一类用图的形式表示随机变量之间条件依赖关系的概率模型,是概率论与图论的结合。图中的节点表示随机变量,缺少边表示条件独立假设。有向图:最基本的是贝叶斯网络(Bayesian Networks,BNs)举例(,)P A O C D S M ()()()(,)(,)P A M P O M P C M P D A O C
5、M P S D M有向图模型的联合概率分解121(,)()NNiiiP XXXp XX ,1251213242534(,)()()()()()P XXXp Xp XXp XXp XXp XX X,每个节点的条件概率分布表示为:P(当前节点|它的父节点)联合分布:无向图:马尔可夫随机场(Markov Random Fields,MRF)马尔可夫随机场模型中包含了一组具有马尔可夫性质的随机变量,这些变量之间的关系用无向图来表示 (,),ijijijp x xjip x xxx 马尔科夫性:举例团(clique):任何一个全连通(任意两个顶点间都有边相连)的子图最大团(maximal clique)
6、:不能被其它团所包含的团X1X2X3X4例如右图的团有C1=X1,X2,X3和C2=X2,X3,X4无向图模型的联合概率分解势函数(potential function)():iiC 是关于上随机变量的函数iC1211(,)()NNiiiP XXXCZ,12,1()NNiiXXXiZC,123411232234123411232234,(,)(,)(,)(,)(,)XXXXXXXXXXp XXXXXXXXXX 设x是一个类别未知的数据样本,Y为类别集合,若数据样本x属于一个特定的类别yj,那么分类问题就是决定P(yj|x),即在获得数据样本x时,确定x的最佳分类。所谓最佳分类,一种办法是把它定
7、义为在给定数据集中不同类别yj先验概率的条件下最可能的分类。贝叶斯理论提供了计算这种可能性的一种直接方法。如果没有这一先验知识,那么可以简单地将每一候选类别赋予相同的先验概率。不过通常我们可以用样例中属于yj的样例数|yj|比上总样例数|D|来近似,即P(yj)代表还没有训练数据前,yj拥有的初始概率。P(yj)常被称为yj的先验概率(prior probability),它反映了我们所拥有的关于yj是正确分类机会的背景知识,它应该是独立于样本的。jj|y|P(y)=|D|()()()()jjjp x yp yp y xp x()()()()jjjp x yp yp y xp x 是联合概率,
8、指当已知类别为yj的条件下,看到样本x出现的概率。()()jjp x yp y若设12(,)mxa aa 则12()(,)jmjp x yp a aay(,)()()p a b cp a c p b c 在给定随机变量C时,a,b条件独立。假定:在给定目标值yj时,x的属性值之间相互条件独立。12()(,)jmjp x yp a aay 1p(|)mijia y P(yj|x)被称为Y的后验概率(posteriorprobability),因为它反映了在看到数据样本x后yj成立的置信度。()()()()jjjp x yp yp y xp x 是后验概率,即给定数据样本x时yj成立的概率,而这正
9、是我们所感兴趣的。()jp y x123argmax()argmax(,)jjjjp y xp y xxx()()()()jjjp yp x yp y xp x 1,jY 后验概率123123(,)()argmax(,)jjjp xxxyp yp xxx 123argmax(,)jjp xxxy 31argmax()()ijjjip x yp y 123123(,)()()()()jjjjjP xxxyp yp x yp xyp xy 11(,)()()niiiiip y xp y yp x y 马尔可夫模型:是一个三元组=(S,A)其中 S是状态的集合,是初始状态的概率,A是状态间的转移概率
10、。一阶马尔可夫链0.500.3750.1250.250.1250.6250.250.3750.375todaysuncloudrainyesterday suncloudrain (1,1,0,0,0)0)123,Ss ss 晴 云 雨一阶马尔可夫模型的例子:假设今天是晴天,请问未来三天的天气呈现云雨晴的概率是多少?隐马尔可夫模型(HMM)0.050.150.200.600.250.250.250.250.50.350.100.05soggydampdryishdrysuncloudrainHMM是一个五元组=(Y,X,A,B),其中 Y是隐状态(输出变量)的集合,)X是观察值(输入)集合,是
11、初始状态的概率,A是状态转移概率矩阵,B是输出观察值概率矩阵。0.500.3750.1250.250.1250.6250.250.3750.375todaysuncloudrainyesterday suncloudrain实验进行方式如下:根据初始概率分布,随机选择N个缸中的一个开始实验根据缸中球颜色的概率分布,随机选择一个球,记球的颜色为x1,并把球放回缸中根据缸的转移概率分布,随机选择下一口缸,重复以上步骤。Urn NUrn NUrn 1Urn 1Urn 2Urn 2Observed Ball SequenceObserved Ball Sequence最后得到一个描述球的颜色的序列x1
12、,x2,称为观察值序列X。:给定观察序列 以及模型,如何选择一个对应的状态序列 ,使得Y能够最为合理的解释观察序列X?12,TXxxx 12(,)NYyyy:给定观察序列以及模型,计算(,)A B()P X 12,TXxxx:给定观察序列 ,调整模型参数 ,使 最大?12,TXxxx(,)A B()P X 评价问题解码问题参数学习问题(/)P X (/,)P X Y(/)P Y Y 所所有有0.60.40.90.1RG120.30.20.70.8=0.5 0.5TRRG0.5 0.3 0.30.6 0.6 0.4 基本算法:给定观察序列以及模型,计算(,)A B()P X 12,TXxxx 1
13、2()(,)1tttiP xxxyitT 11()()1iiib xtT111()()()11,1Nttijjtiji a b xtTjN 1(/)()NTiP Xi 终结:递归:定义前向变量:初始化:.6.2.2.2.5.3.0.3.7RGB123.5.6.4.4.1=1 0 0TRRGB1231.6.60.2.00.0.0.5.6.18.6.2.048.0.4.2.1.0.4.0.5.2.018.6.5.0504.01116.4.5.1.3.4.3.5.2.0018.6.3.01123.01537.4.3.1.7.4.7 1 .t t+1 .a1jt1yN.yi.yj.y1tNtiaNja
14、ij1jt定义后向变量12()(,/)11tttTtiP xxxyitT终结:递归:初始化:()11TiiN 111()()()1,2,.,1,1Ntijjttjia b xjtTTiN 11(/)()NiP Xi :给定观察序列 以及模型,如何选择一个对应的状态序列 ,使得Y能够最为合理的解释观察序列X?12,TXxxx 12(,)NYyyy 1211,2,().,ttttiP y yyyi x xx定义:要找的就是T时刻 所代表的那个状态序列()Tiargmax(|)YP Y X11()()iiib x111()max()()ttijjti Nji a b x)(max1iPTNi111(
15、)argmax()()ttijjti Nji a b x 1argmax()TTi Nyi 11(),1,1tttyytT 0)(1i初始化递归结束得到最优路径.6.2.2.2.5.3.0.3.7RGB123.5.6.4.4.1=1 0 0TRRGB.61.60.2.00.0.0.5.2.018.6.5.036.00576.4.5.1.3.4.3.5.6.18.6.2.048.0.4.2.1.0.4.0.5.2.0018.4.3.00648.1.7.01008.6.3.4.7思想:给定一个模型和输出字符序列,任意设定初始参数值,通过不断循环更新参数的方法,设法达到最优。Baum 1970算法步
16、骤:2.基于0 以及观察值序列X,训练新模型;1.初始模型(待训练模型)0,3.如果 logP(X|)-log(P(X|0)Delta,说明训练已经达到预期效果,算法结束。4.否则,令0,继续第2步工作:给定观察序列 ,调整模型参数 ,使 最大?12,TXxxx(,)A B()P X 定义:1111111ij(,)(,)(,|,)()()()()()()tttttijjttNNtijjttiji ji jP yi yj Xi a bxji a bxj给定模型 和观察序列条件下,从 到 的转移概率定义为i11i11ij1()(,)y()y(,)yyNttjTttTttii jtii j时刻处于状
17、态 的概率整个过程中从状态转出的次数(number of time)的预期从跳转到次数的预期,x()()()tttkjttjb kj(,)(,)ttijttji jai j1t1()iiSi当 时 处 于的 概 率该算法又称为向前向后算法(Forward-backward algorithm)经常得到局部最优解T11()()()iiiiiP Xp y yp x y 所所有有的的Y YHMMs等生产式模型存在的问题:1.由于生成模型定义的是联合概率,必须列举所有观察序列的可能值,这对多数领域来说是比较困难的。2.基于观察序列中的每个元素都相互条件独立。即在任何时刻观察值仅仅与状态(即要标注的标签
18、)有关。对于简单的数据集,这个假设倒是合理。但大多数现实世界中的真实观察序列是由多个相互作用的特征和观察序列中较长范围内的元素之间的依赖而形成的。最大熵的原理认为,从不完整的信息(例如有限数量的训练数据)推导出的唯一合理的概率分布应该在满足这些信息提供的约束条件下拥有最大熵值。求解这样的分布是一个典型的约束优化问题。最大熵模型主要是在已有的一些限制条件下估计未知的概率分布。熵的计算公式:熵的性质:()()log()x XH Xp xp x 0logH XX 其中X在离散分布时是随机变量的个数;当X为确定值,即没有变化的可能时,左边等式成立;可以证明,当X服从均匀分布时,右边等式成立,即均匀分布
19、时熵最大。定义条件熵(,)()(,)log()x yzH y xp y xp y x *()()arg max()p y xPpy xH y x 模型目的定义特征函数(,)0,1if x y ()()iiE fE f 约束条件1,2,im 1,2,im(,)()(,)(,)iix yzE fp x y f x y (,)()(,)(,)iix yzE fp x y f x y (,)()()(,)ix yzp x p y x f x y (,)1(,)ix yTf x yN 1()(,)ix T y Yp y x f x yN NT(1)()1y Yp y x (2)11(,)()()()()
20、1miiimiy YpH y xE fE fp y x 该条件约束优化问题的Lagrange函数1211(,)()NNiiiP XXXCZ,11()exp(,)()miiipy xf x yZx 2 不同之处无向图模型因子是势函数,需要全局归一有向图模型因子是概率分布、无需全局归一1 共同之处将复杂的联合分布分解为多个因子的乘积3 优缺点无向图模型中势函数设计不受概率分布约束,设计灵活,但全局归一代价高有向图模型无需全局归一、训练相对高效序列序列HMMsMEMsNBsMEMM:用一个P(yi|yi-1,xi)分布来替代HMM中的两个条件概率分布,它表示从先前状态,在观察值下得到当前状态的概率,
21、即根据前一状态和当前观察预测当前状态。每个这样的分布函数都是一个服从最大熵的指数模型。HMM:状态集合Y,观察值集合X,两个状态转移概率:从yi-1到yi的条件概率分布P(yi|yi-1),状态yi的输出观察值概率P(xi|yi),初始概率P0(y).111()exp(,)(,)iyiaaiiiaiipy xfxyZ xy HMMMEMM1,2,iT 参数学习目的:通过学习a使得MEMM中的每个转换函数达到最大熵。GIS(Generalized Iterative Scaling)算法编码问题Viterbi算法的思想MEMM存在的问题:标记偏见(Label Bias Problem)问题序列序
展开阅读全文