200字范文,内容丰富有趣,生活中的好帮手!
200字范文 > 【机器学习】(七)马尔可夫链 马尔可夫随机场 条件随机场

【机器学习】(七)马尔可夫链 马尔可夫随机场 条件随机场

时间:2020-05-08 14:05:19

相关推荐

【机器学习】(七)马尔可夫链 马尔可夫随机场 条件随机场

概率模型与概率图模型

概率模型

概率模型(probabilistic model)提供了一种描述框架,将学习任务归结于计算变量的概率分布。在概率模型中,利用已知变量推测未知变量的分布称为推断(inference),其核心是如何基于可观测变量推测出未知变量的条件分布。假定所关心的变量集合为Y,可观测变量集合为O,其他变量的集合为R。

生成式(generative)模型考虑联合分布P(Y,R,O)判别式(discriminative)模型考虑条件分布P(Y,R|O)

给定一组观测变量值,推断就是要由P(Y,R,O)或P(Y,R|O)得到条件概率分布P(Y|O)

概率图模型

概率图模型(probabilistic graphical model)是一类用图来表达变量相关关系的概率模型。它以图为表示工具,最常见的是用一个结点表示一个或一组随机变量,结点之间的边表示变量间的概率相关关系,即变量关系图。

根据边的性质不同,概率图模型可大致分为两类

贝叶斯网(Bayesian network):使用有向无环图表示变量间的依赖关系马尔可夫网(Markovnetwork):使用无向图表示变量间的相关关系,又称为无向图模型

隐马尔可夫模型

隐马尔可夫模型(Hidden Markov Model,HMM)是结构最简单的动态贝叶斯网(dynamic Bayesian network),主要用于时序数据建模。

隐马尔可夫模型中的变量可以分为两组:

状态变量:状态变量yi表示第i时刻的系统状态,通常假定状态变量是隐藏的、不可被观测的,因此也称隐变量(hidden variable)。隐马尔可夫模型中,系统的状态通常在多个状态之间互相转化,因此一般认为状态变量的取值是有限的离散值。观测变量:观测变量xi表示第i时刻的观测值。它可以是离散型也可以是连续型。

隐马尔可夫模型各变量的依赖关系如下图。在任一时刻,观测变量的取值仅依赖于状态变量,即 xt 仅由 yt 确定;任一时刻的状态变量仅依赖于其上一时刻的状态变量,即 yt 仅依赖于 y(t-1)。这就是马尔可夫链(Markov chain),即:系统下一时刻的状态仅由当前状态决定,不依赖于以往的任何状态。

基于马尔可夫链,所有变量的联合概率分布为:

为确定一个隐马尔可夫模型,需要以下三组参数:

状态转移概率:模型在各个状态间转换的概率,通常记为矩阵A=[aij]N×N,其中

表示在任意时刻t,若状态为si,则在下一时刻状态为sj的概率输出观测概率:模型根据当前状态获得各个观测值的概率,通常记为矩阵B=[bij]N×M,其中

表示在任意时刻t,若状态为si,则观测值oj被获取的概率初始状态概率:模型在初始时刻各状态出现的概率,通常记为π=(π1, π2, …, πN),其中

表示模型的初始状态为si的概率

从而,隐马尔可夫模型通常使用 λ=[A, B, π] 来表示。

马尔可夫随机场

马尔可夫随机场(Markov Random Field,MRF)是典型的马尔可夫网,这是一种无向图模型。图中每个结点表示一个或一组变量,结点之间的边表示两个变量之间的依赖关系。马尔可夫随机场有一组势函数(potential functions),亦称因子(factor),这是定义在变量子集上的非负实函数,主要用于定义概率分布函数。

如下图即一个简单的马尔可夫随机场:

马尔可夫随机场计算联合分布

在一个马尔可夫随机场中定义如下概念:

团(clique):对于图中结点的一个子集,若其中任意两个结点之间都有边连接,则称该子集为一个团极大团(maximal clique):若某个团加入另外任何一个结点都不能再够成团,则称该团为极大团,即极大团就是不能被其他团所包含的团

马尔可夫随机场中,所有变量的联合概率可以通过团来定义,每个因子仅与一个团相关。若所有的团构成集合C,与团Q相关的变量集合记为xQ,则联合概率定义为:

其中ψQ为与团Q对应的势函数,用于对团Q中的变量关系进行建模

称为规范化因子,一般很难计算,所以往往不需要Z的精确值

为了减少团的数量同时保证满足每个因子仅与一个团相关这个条件,通常使用极大团Q*来计算,使用极大团定义的联合概率为:

马尔可夫随机场中的条件独立性

定义如下概念:

若马尔可夫随机场中,结点集A中的结点到B中的结点都必须经过结点集C中的结点,则称结点集A和B被结点集C分离,结点集C称为分离集(separating set),如图所示:

全局马尔可夫性(global Markov property):给定两个变量子集的分离集,则这两个变量子集条件独立,如上图中,xA和xB在给定xC的条件下独立,记为:

局部马尔可夫性(local Markov property):给定某变量的邻接变量,则该变量条件独立于其他变量。例如,令V为图的结点集,n(v)为结点v在图上的邻接结点,n*(v)=n(v)U{v},有:

成对马尔可夫性(pairwise Markov property):给定所有其他变量,两个非邻接变量条件独立。例如,令图的结点集和边集分别为V和E,对图中的两个结点u和v,若⟨n,v⟩∉E,则:

势函数

势函数定量地刻画变量集xQ中变量之间的相关关系,是非负函数,且在所偏好的变量取值上有较大的函数值,势函数常用指数函数定义:

HQ(xQ)是一个定义在变量xQ上的实值函数,常见形式为:

条件随机场

条件随机场(Conditional Random Field,CRF)是一种判别式无向图模型,对条件分布进行建模。隐马尔可夫模型和马尔可夫随机场为生成式模型,直接对联合分布进行建模。

条件随机场试图对多个变量在给定观测值后的条件概率进行建模。具体来说,若令x={x1, x2, …, xn}为观测序列,y={y1, y2, …, yn} 为与之相应的标记序列,则条件随机场的目标是构建条件概率模型P(y|x)。

令G=<V,E>表示结点与标记变量y中元素一一对应的无向图,yv表示与结点v对应的标记变量,n(v)表示结点v的邻接结点,若图G的每个变量yv都满足马尔可夫性,即:

则G=<V,E>构成一个条件随机场

理论上来说,图G可具有任意结构,只要能表示标记变量之间的条件独立性关系即可。但在现实应用中,尤其是对标记序列建模时,最常用的仍是如下图所示的链式结构,即链式条件随机场(chain-structured CRF):

条件随机场中,通过选用指数势函数并引入特征函数(feature function),条件概率被定义为:

其中tj是定义在观测序列的两个相邻标记位置上的转移特征函数(transition feature function),用于刻画相邻标记变量之间的相关关系以及观测序列对它们的影响,sk是定义在观测序列的标记位置i上的状态特征函数(status feature function),用于刻画观测序列对标记变量的影响,λj和μk为参数,Z为规范化因子。

条件随机场和马尔可夫随机场均使用团上的势函数定义概率,两者在形式上没有显著区别条件随机场处理的是条件概率,而马尔可夫随机场处理的是联合概率

全文参考:周志华 著 《机器学习》

转载请注明出处,本文永久更新链接:小天才的杂货铺-学习笔记

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。