机器学习的核心思想就是根据已知的内容去推测未知的内容,然后在已知和未知之间建立起联系,这个联系就是机器学习中的各种模型!这和我们的经验系统很像,在第一章中的挑西瓜的例子就是我们利用经验系统来把西瓜的可观测外观信息(根蒂、花纹、声响)和未知信息(是否是好瓜)建立起联系的结果。
说回本章的内容,一种建立已知信息与未知信息联系的方法是对未知信息的概率分布进行推测。概率模型(probabilistic model)提供了一种描述框架,将学习任务归结于计算变量的概率分布。在概率模型中,利用已知变量推测未知变量的分布称为“推断”(inference),其核心是如何基于可观测变量 x 推测出未知变量 c 的条件分布 P( c | x ) 。贝叶斯学习算法就是一个经典的概率模型
具体来说,概率模型有“生成式”和“判别式”两种方式,这两种类型的区别在第七章贝叶斯分类器“一起来读西瓜书:第七章 贝叶斯分类器”中已有过介绍,简单来说,前者是通过计算 P(c, r, x) 来得到 P( c | x )的,后者是直接计算 P(c, r | x) 来得到 P( c | x )的,其中 r 是除了可观测变量和要计算的变量外的其他变量。
上边介绍了那么多,那么到底什么是概率图模型呢?
概率图模型是一类用图来表达变量相关关系的概率模型。使用概率图模型的原因是因为直接利用概率求和规则消去变量 r 计算开销太大,而且属性之间往往存在复杂的关系,而以图为表现工具,对变量间的关系进行简洁紧凑的表达将有助于提高研究推断和学习算法的效率。
概率图模型根据边的性质不同,大致可分为以下两类:第一类是使用有向无环图表示变量之间的依赖关系,称为有向图模型或者贝叶斯网(Bayesian network);第二类是使用无向图表示变量间的相关关系,称为无向图模型或者马尔可夫网(Markov network)
下边我将分别对概率图模型的不同类型、学习和推断详情以及具体的模型进行介绍,希望通过本章的学习,大伙能对概率图模型有个较为清晰的认识
1)隐马尔可夫模型(Hidden Markov Model,简称 HMM )
隐马尔可夫模型是结构最简单的动态贝叶斯网(Dynamic Bayesian Network),这是一种著名的有向图模型,主要用于时序数据建模,在语音识别、自然语言处理领域有广泛应用。
隐马尔可夫模型具有两组变量,第一组是系统的状态变量{y1, y2, ... , yn},其中 yi 为第 i 时刻系统的状态。通常假定状态变量是隐藏的、不可被观测的,因此状态变量亦称“隐变量”(hidden variable)。第二组是观测变量{x1, x2, ... , xn},其中 xi 是第 i 时刻的观测值。下图是隐马尔可夫模型的图结构:
图中的箭头表示了变量间的依赖关系。隐马尔可夫模型是建立在这样的前提下的:在任一时刻,观测变量的取值仅依赖于其对应的状态变量,即 xi 由 yi 决定;同时,t 时刻的状态变量只由 t-1 时刻的状态变量决定。
这就是所谓的“马尔可夫链”(Markov Chain):系统下一时刻的状态仅由当前状态决定,不依赖于以往的任何状态
基于这种依赖关系,所有变量的联合概率分布为:
P(x1, y1, ... , xn, yn) =
P(y1) P( x1| y1 ) P( y2 | y1 ) P( x2 | y2) ... P( yn | yn-1) P( xn | yn)
除了结构信息,欲确定一个隐马尔可夫模型还需以下三组参数:
[1]状态转移概率:A -> aij = P( yt+1 = sj | yt = si ),系统从一个状态转移到另一个状态的概率
[2]输出观测概率:B -> bij = P( xt = oj | yt = si ) ,系统在当前状态的观测值概率
[3]初始状态概率:∏ -> ∏i = P( y1 = oj ),系统的初始状态概率
通过指定状态空间 Y、观测空间 X 和上述三组概率参数 r = [A, B, ∏] ,就能确定一个隐马尔可夫模型。具体的步骤为:
[1]用初始状态概率 ∏ 算出初始状态 y0
[2]用 B 算出当前状态的观测值 xt
[3]用 A 算出下一个状态 yt+1
[4]重复第二、第三步直到到达停止条件
可在实际应用中,隐马尔可夫模型的参数并不一定都能得到,因此人们常常关注下边三个基本问题:
[1]给定了参数 r,并且知道观测序列 X = {x0, x1, ..., xn-1},评估模型与观测序列之间的匹配程度,来推测下一状态的观测概率: P( xn | r )
[2]给定了参数 r,并且知道观测序列 X = {x0, x1, ..., xn},要预测对应的状态序列 Y = {y0, y1, ..., yn}
[3]给定观测序列 X = {x0, x1, ..., xn},如何调整模型参数 r 使得该序列出现的概率最大
2)马尔可夫随机场(Markov Random Field,简称 MRF)
马尔可夫随机场是典型的马尔可夫网,这是一种著名的无向图模型。图中的每个节点代表一个或一组变量,节点之间的边表示两个变量之间的依赖关系。 马尔可夫随机场有一组势函数(potential functions),亦称“因子”(factor),这是定义在变量子集上的非负实函数,主要用于定义概率分布函数。
马尔可夫随机场是一种具有马尔可夫特性的随机场,要理解什么是马尔可夫随机场,我们得要先理解什么是随机场,而什么又是马尔科夫特性。
[1]什么是随机场
在概率论中, 由样本空间Ω = {0, 1, …, G − 1}n取样构成的随机变量Xi所组成的S = {X1, …, Xn}。若对所有的ω∈Ω下式均成立,则称π为一个随机场。
π(ω) > 0.
当给每一个位置中按照某种分布随机赋予相空间的一个值之后,其全体就叫做随机场。我们不妨拿种地来打个比方。其中有两个概念:位置(site),相空间(phase space)。“位置”好比是一亩亩农田;“相空间”好比是种的各种庄稼。我们可以给不同的地种上不同的庄稼,这就好比给随机场的每个“位置”,赋予相空间里不同的值。所以,俗气点说,随机场就是在哪块地里种什么庄稼的事情
[2]什么是马尔可夫特性
上一节我们提到了马尔可夫链的概念,即系统的下一状态仅由当前状态决定,不依赖于以往的任何状态。马尔可夫特性是这个概念的一个变化,即一个变量只与其邻接变量相关,不依赖于不相邻的任何变量
还是拿种地打比方,如果任何一块地里种的庄稼的种类仅仅与它邻近的地里种的庄稼的种类有关,与其它地方的庄稼的种类无关,那么这些地里种的庄稼的集合,就是一个马尔可夫随机场。
[3]“团”(clique)、“极大团”(maximal clique)及联合概率
下图是一个简单的马尔可夫随机场。对于图中结点的一个子集,若任意两个结点间都有边连接,则称该结点子集为一个团。若在一个团中加入另外任何一个结点都不再构成团,则称该团为极大团
引入团概念的原因是什么呢?其实很简单,就是为了能更方便的计算变量x的联合概率。根据马尔可夫特性,每个变量只与其邻接结点相关,那么多个变量之间的联合概率分布能基于团分解为多个因子的乘积。具体来说,对于 n 个变量 x = {x1, x2, ..., xn},所有团构成的集合为 C,与团 Q 属于 C 对应的变量集合记为 xQ,则联合概率 P(x) 定义为:
其中 Z 为规范化因子,被连乘的函数代表的是团 Q 对应的势函数,势函数的作用是定量刻画变量集 xQ 中变量之间的相关关系。
3)条件随机场(Conditional Random Field,简称 CRF)
条件随机场是一种判别式无向图模型,它可以被看成是给定观测值的马尔可夫随机场。前边介绍的隐马尔可夫模型和马尔可夫随机场都是“生成式”模型,而条件随机场是“判别式”模型,即给定观测数据{x1, x2, ..., xn}以及对应的标记数据{y1, y2, ..., yn},构建条件概率模型 P( y | x )。
对于一个无向图模型,若图中的每个变量 y_v 都满足马尔可夫性,即
则称 (y, x) 构造一个条件随机场
理论上来说,条件随机场的图 G 可具有任意结构,只要能表示标记变量之间的条件独立性即可。但在实际应用中,尤其是对标记序列建模时,最常用的仍是下图所示的链式结构,即“链式条件随机场”(chain-structured CRF)
与马尔可夫随机场类似,条件随机场也使用了合适的“势函数”来计算所要求的条件概率,只不过条件随机场是将势函数引入特征函数(feature function)中来进行计算的。
特征函数通常是实值函数,以刻画数据的一些很可能成立或期望成立的经验特征。比如在下图所示的语法分析任务中,
可以有如下特征函数,
这说明经验上来说,第 i 个观测值为“knock”时,其相应的标记 y_i 和 y_i+1 很可能分别为 [V] 和 [P]
4)学习与推断
在介绍了概率图模型的三种主流结构后,接下来我们继续学习如何在概率图模型中进行学习和推断。
基于概率图模型定义的联合概率分布,我们能对目标变量的边际分布或以某些可观测变量为条件的条件分布进行推断。具体来说,假设图模型所对应的变量集 x = {x1, x2, ..., xn} 能分为 x_E 和 x_F 两个不相交的变量集,推断问题的目标就是计算边际概率 P( x_E ) 或条件概率 P( x_F | x_E ),由条件概率定义有如下公式:
其中联合概率 P(x_E, x_F) 可基于概率图模型获得,因此,推断问题的关键就是如何高效的计算边际分布,即上式的分母部分。
概率图模型的推断方法大致可以分为两类:第一类是精确推断方法,希望能计算出目标变量的边际分布或条件分布的精确值;遗憾的是,一般情况下,此类算法的计算复杂度随着极大团数量的增长呈指数增长,适用范围有限。第二类是近似推断方法,希望在较低的时间复杂度下获得原问题的近似解;此类方法在现实任务中更常见。
笔者将在下一期为大家介绍这两种精确推断方法。
注:本篇文章作者系易建科技股份有限公司智慧科技事业群产品研发中心技术主管陈啸翔
联系客服