概率图模型研究进展综述.pdf

《概率图模型研究进展综述.pdf》由会员分享，可在线阅读，更多相关《概率图模型研究进展综述.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 软件学报 ISSN 1000-9825,CODEN RUXUEW E-mail: Journal of Software,2013,24(11):24762497 doi:10.3724/SP.J.1001.2013.04486 http:/ 中国科学院软件研究所版权所有.Tel/Fax:+86-10-62562563 概率图模型研究进展综述 张宏毅1,2,王立威1,2,陈瑜希1,2 1(机器感知与智能教育部重点实验室(北京大学),北京 100871)2(北京大学 信息科学技术学院 智能科学系,北京 100871)通讯作者:张宏毅,E-mail: 摘 要:概率图模型作为一类有力的工具,能够简

2、洁地表示复杂的概率分布,有效地(近似)计算边缘分布和条件分布,方便地学习概率模型中的参数和超参数.因此,它作为一种处理不确定性的形式化方法,被广泛应用于需要进行自动的概率推理的场合,例如计算机视觉、自然语言处理.回顾了有关概率图模型的表示、推理和学习的基本概念和主要结果,并详细介绍了这些方法在两种重要的概率模型中的应用.还回顾了在加速经典近似推理算法方面的新进展.最后讨论了相关方向的研究前景.关键词:概率图模型;概率推理;机器学习 中图法分类号:TP181 文献标识码:A 中文引用格式:张宏毅,王立威,陈瑜希.概率图模型研究进展综述.软件学报,2013,24(11):24762497.http

3、:/ 英文引用格式:Zhang HY,Wang LW,Chen YX.Research progress of probabilistic graphical models:A survey.Ruan Jian Xue Bao/Journal of Software,2013,24(11):24762497(in Chinese).http:/ Research Progress of Probabilistic Graphical Models:A Survey ZHANG Hong-Yi1,2,WANG Li-Wei1,2,CHEN Yu-Xi1,2 1(Key Laboratory of

4、 Machine Perception(Peking University),Ministry of Education,Beijing 100871,China)2(Department of Machine Intelligence,School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China)Corresponding author:ZHANG Hong-Yi,E-mail: Abstract:Probabilistic graphical models are

5、powerful tools for compactly representing complex probability distributions,efficiently computing(approximate)marginal and conditional distributions,and conveniently learning parameters and hyperparameters in probabilistic models.As a result,they have been widely used in applications that require so

6、me sort of automated probabilistic reasoning,such as computer vision and natural language processing,as a formal approach to deal with uncertainty.This paper surveys the basic concepts and key results of representation,inference and learning in probabilistic graphical models,and demonstrates their u

7、ses in two important probabilistic models.It also reviews some recent advances in speeding up classic approximate inference algorithms,followed by a discussion of promising research directions.Key words:probabilistic graphical model;probabilistic reasoning;machine learning 我们工作和生活中的许多问题都需要通过推理来解决.通过

8、推理,我们综合已有的信息,对我们感兴趣的未知量做出估计,或者决定采取某种行动.例如,程序员通过观察程序在测试中的输出判断程序是否有错误以及需要进一步调试的代码位置,医生通过患者的自我报告、患者体征、医学检测结果和流行病爆发的状态判断患者可能罹患的疾病.一直以来,计算机科学都在努力将推理自动化,例如,编写能够自动对程序进行测试并且诊断 基金项目:国家自然科学基金(61222307,61075003)收稿时间:2013-07-17;修改时间:2013-08-02;定稿时间:2013-08-27 张宏毅 等:概率图模型研究进展综述 2477 错误位置的调试工具、能够辅助医生诊断患者病情的医疗诊断专家

9、系统、理解英语文本的含义并将其转换为汉语的自动翻译系统、从机场监控视频中发现可疑人员的安全监控系统等等.人们设计出多种多样的方法来实现这些应用,其中,将知识陈述式地表示为概率模型,通过计算我们所关心变量的概率分布实现推理的途径具有独特优势:首先,它提供了一个描述框架,使我们能够将不同领域的知识抽象为概率模型,将各种应用中的问题都归结为计算概率模型里某些变量的概率分布,从而将知识表示和推理分离开来1.模型的设计主要关心如何根据领域知识设计出反映问题本质的概率模型,同时兼顾有效推理的可行性,而推理算法的设计只需关心如何有效地在一般的或者特定的概率模型中进行推理.这种一定程度上的正交性极大地扩展了概

10、率模型的应用,也加快了它的发展速度.其次,它能够评估未知量取值的可能性,对不同取值的概率给出量化的估计.这在涉及风险的决策系统中非常重要.另外,它常常具有良好的复用性.例如,我们不需要为预测父亲和儿子患上某种家族遗传病的概率分别设计算法,只需一个关于基因和表现型的家族遗传路径的概率模型,就能处理关于遗传病风险的各种推理问题.概率图模型就是一类描述这种陈述式表示的概率模型的建模和推理框架,它为简洁地表示、有效地推理和学习各种类型的概率模型提供了可能.在历史上,曾经有来自不同学科的尝试使用图的形式表示高维分布的变量间的相关关系的例子2,3.在人工智能领域,概率方法始于构造专家系统的早期尝试4,5.

11、到 20 世纪 80 年代末,由于在贝叶斯网络和一般的概率图模型中进行推理的一系列重要进展6,7,以及大规模专家系统的成功应用8,以概率图模型为代表的概率方法重新受到了重视.如今,经过 20 余年的发展,概率图模型的推断和学习已广泛应用于机器学习、计算机视觉、自然语言处理、语音识别、专家系统、用户推荐、社交网络挖掘、生物信息学等研究领域的最新成果中,成为人工智能相关研究中不可或缺的一门技术.概率图模型的研究方兴未艾,而且应用范围和研究热度仍在继续增长.本文首先介绍概率模型中的推断和学习问题的相关背景,并引入条件独立性这一重要概念;然后,根据研究主题依次综述概率图模型的表示、推理和学习问题核心内

12、容的研究进展;我们还将介绍两种近年来有较大影响的概率图模型条件随机场和主题模型,以说明概率图模型的表示、推理和学习这 3 个环节的联系;最后,讨论关于大规模图模型的一些延伸主题,包括效率更高的推理算法、并行和分布式推理以及针对查询的推理 问题.在本文中,我们将统一使用大写字母(例如 A,X)表示随机变量,如未指明变量类型,则默认为离散变量;使用小写字母(例如 x,y)表示随机变量的赋值;使用大写字母表示集合(例如 A,X)或者某种数据结构(例如 F,H).推断问题 多数与人工智能相关的应用所解决的问题都可以形式化地表述为概率模型中的推断问题.在推断问题中,目标是推断我们感兴趣的随机变量集合 S

13、 中变量的取值分布,而我们采用生成式模型或判别式模型为问题建模,并运用一般的或针对具体模型的推断算法来计算这一分布.在生成式模型中,我们已知包含感兴趣变量集合在内的一些相互联系的变量的联合分布,以及其中可观测变量的观测值(或真实值),目标是以可观测变量为条件计算目标变量的条件概率.在判别式模型中,我们已知包含感兴趣变量集合 S 在内的一些相互联系的变量与另一些可观测变量之间的联系,即以可观测变量为条件的条件分布,以及可观测变量的观测值,目标同样是计算感兴趣变量集合 S 中的变量的条件概率.例如,在计算机视觉应用中,人们可能感兴趣一个图像区域所表示的物体类别;在自然语言处理应用中,人们可能感兴趣

14、一句汉语文本的语法分析结果;而在用户推荐应用中,人们可能感兴趣某用户对某产品的喜好程度.这些来自不同领域的问题都可以表示成概率模型中的推断问题,并得到统一的处理.在以上描述中,要计算感兴趣变量的条件概率,需要知道感兴趣变量及其相关变量包含可观测变量的联合分布或以可观测变量为条件的条件分布.一般情况下,设全体随机变量的集合为 S,感兴趣的变量集合为X1,X2,Xn=XS,可观测变量集合为O1,O2,Om=OS,其他变量的集合记为 Y=S(XO),则生成式模型确定了 2478 Journal of Software 软件学报 Vol.24,No.11,November 2013 联合分布P(X,Y

15、,O),而判别式模型确定了条件分布P(X,Y|O).给定观测值,即O的一个赋值o1,o2,om,在生成式模型中,我们需要使用概率求和规则消去 Y 中的变量,并重新归一化,得到条件概率分布 P(X|O),在判别式模型中,我们只需求和消去 Y 中的变量即可.然而在实际的推断问题中,我们还要考虑到数据结构的表示开销和运算开销(时间和空间复杂度).假设在某模型中,每个变量可以有两种取值,如果我们简单地定义以上概率分布,并使用求和规则推断目标分布,容易验证时间开销和空间开销都至少是(2|Y|).因此,我们必须寻找更紧凑的表示概率分布的数据结构以及能够在其中有效运行的推断算法.学习问题 推断问题研究如何在

16、已有的模型基础上,根据观测计算目标变量的分布,并没有考虑如何构建模型的问题.一方面,模型可以由领域专家构建,模型的结构以及参数可以由专家根据经验来指定;另一方面,实际应用中可能需要对人类尚不了解的问题建立模型,或建立参数众多的大规模模型,或历史经验以数据的形式而不是人类知识存储等等,在这些情况下,模型的结构和参数并不适合人工指定,因此,我们希望设计算法从已往的数据中学习得到模型的参数和结构.从更一般的角度来讲,学习问题可以看作是推断问题的一类特例:我们感兴趣的随机变量是模型的参数或结构.因此,对学习问题的简单处理将会遇到与推断问题相同的困难,即表示和计算的时间和空间复杂度关于模型的变量数目都是

17、指数级的,而我们需要能够处理实际应用数据规模的有效的学习算法.学习问题特有的困难在于:用于学习的训练样本通常是有限的,并且算法允许的训练时间也是有限的.当我们允许复杂的模型尝试从数据中估计联合分布的每一项概率时,我们将面对所谓的维数灾难.相对于呈指数增长的参数,样本量往往太少,以至于我们对真实分布的估计几乎必定有很大的误差.条件独立 考虑变量集 A,B,C,如果 P(A,B|C=c)=P(A|C=c)=P(B|C=c),c 成立,我们就称以 C 为条件,变量集 A,B 相互独立.此时容易验证,P(A|B,C)=P(A|C),P(B|A,C)=P(B|C).模型中的条件独立性是对推断问题和学习问

18、题进行有效计算的基础.例如,考虑对式 P(A,B,C)求和以消去 B,C,利用上述条件独立性,我们可以写出:(),(,)(|)(|)()(|)()(|).B CBCCBP A B CP A C P B C P CP A C P CP B C=经过变换,在模型的表示上,需要指定的项从O(|A|B|C|)个减少到O(|A|+|B|)|C|)个,运算次数从O(|B|C|)减少到 O(|B|+|C|).注意到,我们可利用集合 A(或 B,C)内的条件独立性进一步简化问题的表示和计算.事实上,如果一个概率分布能够分解为一些包含不超过 d 个变量的项的乘积,且每个变量的可取值不超过 m,则表示和推断的复杂

19、度有上界O(md).其中,d表示一个复杂的概率分布分解为若干较简单分布的乘积性质的强弱,或者说表示变量之间的条件独立性的强弱.条件独立性是概率图模型里非常基本的核心概念,贯穿模型的表示、推理和学习等各方面.概率图模型将概率论与图论结合,提供了直观地表示随机变量间条件独立性质的工具,便于人们分析模型的性质,同时使得有关图论的结论和算法可以用于处理概率模型的推断和学习问题1.1 概率图模型的表示 概率图模型的表示刻画了模型的随机变量在变量层面的依赖关系,反映出问题的概率结构以及推理的难易程度,也为推理算法提供了可以操作的数据结构.概率图模型的表示方法有多种,我们主要介绍最常见的贝叶斯网络、马尔可夫

20、网络、因子图等表示,以及一些简化表示的记法.1.1 贝叶斯网络 对应于有向无环图的概率模型称为贝叶斯网络(如图1所示).图的每个顶点代表随机变量或随机向量,边代表变量间的条件相关关系,常常也被用于表示因果关系.对于任意一条边和它所连接的两个顶点 AB,A 称为 B的父节点,B 称为 A 的子节点.贝叶斯网络中每个顶点 X 和它的父节点 U(X)表示一个条件分布 P(X|U(X),称为一 张宏毅 等:概率图模型研究进展综述 2479 个因子.整个概率分布由所有因子的乘积表示:()(|().P XP X U X=Fig.1 Bayesian network of five variables an

21、d its union distribution 图1 含有5个变量的贝叶斯网络及其表示的联合分布 1.1.1 贝叶斯网络中的独立性 在贝叶斯网络中,条件独立性可以直接根据图的结构判定.我们首先考虑3个变量之间的相互关系.由X,Y,Z这3个变量构成的X,Y不直接相关的贝叶斯网络,X,Y之间的关系有以下几种形式:1)X到Y是成因路径(XZY).当且仅当Z未被观测时,X,Y不相互影响(即X的取值不影响Y的条件分布,反之亦然).因此,X,Y不相互独立,但给定Z时,X,Y条件独立.2)X到Y是证据路径(XZY).当且仅当Z未被观测时,X,Y不相互影响.因此,X,Y不相互独立,但给定Z时,X,Y条件独立

22、.3)X,Y有共同原因(XZY).当且仅当Z未被观测时,X,Y不相互影响.因此,X,Y不相互独立,但给定Z时,X,Y条件独立.4)X,Y有共同效果(XZY).当且仅当Z或Z的一个子代节点被观测时,X,Y相互影响.因此,X,Y相互独立,但给定Z或其子代节点时,X,Y不相互独立.对于贝叶斯网络中的一条路径X1?Xn和观测变量的子集 Z,当X1和Xn的取值能够相互影响时,我们称路径X1?Xn是有效的.在一般情况下,我们有以下结论:给定 Z 时,X1?Xn是有效的当且仅当:1)对该路径上的每个V字结构Xi1XiXi+1,存在Xi或其子代在 Z 中;2)路径上的其他任何节点都不在 Z 中.1.2 马尔可

23、夫网络 注意到除了用若干条件概率分布的乘积构造联合分布以外,还有更一般的构造概率分布的方法.考虑定义 在随机变量集合X的子集变量值域上的非负实值函数,若对任意i,i(i)0,iiX=且()iiXiZ=0,则1()iiiZ 定义了一个有效的分布.其中,Z称为归一化常数,由模型参数确定而与观测值无关.对应于无向图的概率模型称为马尔可夫网络,图的每个顶点代表随机变量或随机向量,边代表变量间的相关关系.对任意一条边,其所在的最大的团(全连通子图)称为一个因子.每一条边都唯一地属于一个因子,由于有了上述构造概率分布的方法,只需为每个因子指定一个非负函数(),并对所有因子的乘积归一化,我们就可以构造出由马

24、尔可夫网络表示的概率模型.归一化常数是马尔可夫网络与贝叶斯网络的重要区别之一.在许多模型中,直接计算归一化常数的复杂度是指数级的,因此必须寻找其他替代方法解决推断或学习问题.1.2.1 马尔可夫网络中的独立性 马尔可夫网络中的独立性情况比贝叶斯网络要简单.与之前定义类似,对马尔可夫网络中的一条路径X1-Xn和观测变量的子集 Z,当X1和Xn的取值能够相互影响时,我们称路径X1-Xn是有效的.在一般情况下,我们有以下结论:给定 Z 时,X1-Xn是有效的,当且仅当路径上的其他任何节点都不在 Z 中.P(A,B,C,D,E)=P(A)P(B|A)P(C|B)P(D|B)P(E|C,D)B A C

25、E D 2480 Journal of Software 软件学报 Vol.24,No.11,November 2013 1.3 因子图 图模型的另一种常见表示是因子图9.在因子图G=(X,F)中,我们规定存在两种顶点:随机变量和因子.边是无向的,连接因子和它所包含的随机变量.因此,每个随机变量的邻居顶点是包含它的各个因子,而每个因子的邻居顶点是它的辖域内的各个随机变量.因子图是一种比马尔可夫网络更精细的模型表示,例如在图2所示的因子图中,我们可以区分不同的分布究竟是定义为因子AB,BC,AC的乘积还是一个辖域为A,B,C的大因子ABC;而在马尔可夫网络中,它们有相同的表示而无法从图结构上进行

26、区分.Fig.2 图2 与马尔可夫网络相似,因子图中也有马尔可夫网络的概念.从马尔可夫网络的特征和因子图的定义中容易推导,在因子图中,设边集为E,变量Xi的马尔可夫网络是由B(Xi)=Xj:(Xj,)E且(Xi,)E且ji构成的变量集合.因子图数据结构由于显式地表示出构造概率分布的因子,因此特别适合一类通过在变量与因子之间传递消息的推理算法(参见第2.2.1节)的执行.包括微软的Infer.NET项目10在内,许多采用这类算法的推理系统都采用了因子图的表示.1.4 盘式记法、模板 盘式记法(plate notation)是一种常用的图模型的简化记法,考虑如下简单的概率模型:在一个装有白球和黑球

27、的盒子里进行有放回抽样,n次抽样的结果记为X1,Xn,盒子中白球的比例记为,则该概率模型可以采用标准的记法表示,也可以用盘式模型表示(如图3所示).在盘式模型中,我们用一个框(称为盘)圈住图模型中重复的部分,并在框内标注重复的次数.Fig.3 图3 盘式记法能够为我们表示和分析许多概率模型提供很大的方便,但它也有一定的局限性.例如,它无法表示盘内变量不同拷贝间的相关性,而这种相关性广泛出现于动态贝叶斯网络中.在动态贝叶斯网络中,概率模型符合k阶马尔可夫假设,因此,t时刻的系统状态只与max(0,tk)时刻的状态有关.为了简明地表示这类含有重复的基本结构的动态贝叶斯网络,我们可以使用称为kBN的

28、模板.例如,图4展示了隐马尔可夫模型及其2BN模板 记法.(b)仅含有 1 个三元因子的因子图(a)含有 3 个二元因子的因子图(c)对应的马尔可夫网络仅有 1 种表示 B A CBACBA C(a)展开的摸球模型(b)盘式记法 X1 X2XNXiN 张宏毅 等:概率图模型研究进展综述 2481 Fig.4 图4 2 概率图模型的推理 在本节中,我们介绍图模型推理所使用的一些重要算法.这些算法可大致分为3类:精确推理算法.能够计算查询变量的边缘分布或条件分布的精确值,但其计算复杂度随着图模型的树宽呈指数增长,因此适用范围有限.基于优化的推理算法.将图模型的推断形式化为优化问题,通过松弛优化问题

29、的约束条件或者调整优化的目标函数,算法能够在较低的时间复杂度下获得原问题的近似解;对于多数难以进行精确推理的图模型,对其变量进行抽样并不困难.基于抽样的推理算法.试图产生所求边缘分布或条件分布的抽样,使用样本的经验分布来近似真实 分布.一般的图模型中的推理是困难的.关于最坏情况下推理的复杂度,我们已经知道一系列负面的结果:图模型精确推理是#P-完全的;相对误差的图模型近似推理是NP-难的;绝对误差(0,1/2)的图模型近似推理有多项式的时间复杂度,但以证据为条件的近似推理依旧是NP-难的11.然而,实际应用中的问题往往具有良好的条件独立结构,因而图模型的精确推理和近似推理算法带来了许多成功的应

30、用.从推理的目标来区分,有时我们希望计算目标变量的(条件)边缘分布,称为后验推理;有时我们希望计算目标变量(集合)最可能的(联合)赋值,称为最大后验推理.我们将首先介绍3类后验推理方法,最后统一介绍最大后验推理方法.由于贝叶斯网络中的条件分布P(X|Y)也可看作因子(X|Y),本节中,我们将统一地采用因子来构造分布.2.1 精确推理 图模型的精确推理算法实质是一类动态规划算法,它利用条件独立性导致的联合分布的因子化特征,压缩图模型变量之间传递的信息.2.1.1 变量消去算法 变量消去算法12是最直观且容易推导的精确推理算法,然而它却是其他更高级的精确推理算法的基础.考虑贝叶斯网络(如图1所示)

31、所定义的联合分布P(A,B,C,D,E),我们如果观测到变量E=e,并且想要计算变量C=c的条件概率P(c|e),则可以简单地写出:,1(|)(,),a b dP c eP a b c d eZ=其中,(,).a b c dZP a b c d e=利用贝叶斯网络所蕴含的独立性,以上求和可分别化简为 ,(,)()(|)(|)(|)(|,)(|,)(|)(|)()(|)a b da b ddbaP a b c d eP a P b a P c b P d b P e c dP e c dP c b P d bP a P b a=(1)简而言之,变量消去算法实际是利用了乘法对加法的分配律,将对多个

32、变量的积的求和分解为对部分变量xiyix2 x1 y1 y2 yn xn (a)展开的隐马尔可夫模型(b)2BN-记法(该记法要求使用盘分别圈住 t 时刻的变量和它们的父节点变量)xi1 2482 Journal of Software 软件学报 Vol.24,No.11,November 2013 交替进行的求积与求和.变量消去算法的缺点在于:一次变量消去只能求出本次查询变量的条件分布,不同的查询将带来大量的重复计算.为实现一次计算、多次使用,就需要更加仔细地进行算法设计.为了保证算法的正确性,需要保证所有与求和变量有关的项都在求和符号内,这也是以下两种常用精确推理算法的理论基础.2.1.2

33、 团树算法 为了实现精确推理的更高效算法,需要设计一种支持推理运算的数据结构:团树.团树是一种具有如下性质的树结构:1)团树的每个顶点都是对应图模型中因子的集合.2)族保持性:原图模型中的每个因子都属于至少1个团树顶点.3)流动相交性:如果变量X在团树的两个顶点 Ci,Cj中出现,则X出现在 Ci,Cj之间的每一个顶点中.团树中,相邻两顶点的变量的交 Sij=CiCj称为两顶点的割集.从同一图模型可以生成多种团树,它们的推理代价并不相同,但寻找推理代价最小的团树是困难的.一个比较好的方法是在所谓“最大消去团”的全连通图上寻找好的团树.指定一个变量消去的顺序,考虑依次消去变量时所生成的团,以其中

34、的最大团为顶点生成全连通图,用割集的基数为边赋权,则该全连通图的最大权生成树就是一个较好的团树.这是因为在变量消去的过程中,我们只需要消去未出现在割集中的变量,因此对于给定的顶点集合,割集中包含的变量较多,计算代价相对就较小.团树生成之后,需要计算团树顶点对应的因子.为此,只需对每个顶点遍历原图模型因子的集合,若该因子所含变量是该团树顶点所含变量的子集,则将其乘入该顶点的因子中.团树对应的因子集合称为可分解密度,这是因为它们是原概率分布在团树上分解的结果.有了团树和可分解密度,就可以执行以下精确推理算法了:消息传递(也称Shafer-Shenoy算法13、和-积算法).在消息传递算法中,当且仅

35、当节点A收到了除邻居节点B外所有邻居节点的消息时,A才向B传递消息.消息传递算法按如下步骤执行:1)在团树中选择一个根节点,由根节点出发构造一个单根树.2)从根节点起递归地执行:如果该节点的子节点收到了其他所有邻居的消息,则子节点向该节点传递 消息.3)从根节点起递归地执行:如果该节点收到了除某个子节点外其他所有邻居的消息,则该节点向子节点传递消息.信念传播(也称HUGIN算法14).在信念传播算法中,我们为每个节点附加一个称为信念的变量.在算法运行的每一步,每个节点都同时向其相邻节点传递消息,消息的内容是该节点当前关于其割集中变量的边缘分布的信念.每个节点在接收到来自其他节点的消息后立即更新

36、其信念:将自身的信念乘以新接收的消息,并除去上一次从相同节点接收到的消息.如果任一节点在收到其邻居节点的消息后自身的信念都不再发生变化,算法就收敛了.可以证明:对于团树上的信念传播,每对节点间传递两次消息后,算法就会收敛,且收敛于正确的分布(可能需要归一化).2.2 基于优化的近似推理 在上一节中,我们介绍了用于精确推理的信念传播算法,其中使用到了团树这一数据结构.团树可以在对原始的图模型进行变量消去的过程中生成,团树上信念传播的复杂度是团树中最大团所含变量数目的指数量级.而如果我们对于在计算机视觉等领域常用的伊辛(Ising)模型生成团树(如图5所示,其中,灰色加粗的变量集合为变量X2,2的

37、马尔可夫毯),设图模型的变量数量为(N2),则一个团中将含有(N)个变量,精确推理的复杂度是2(N).因此,对于具有这类变量耦合性质的模型,团树上的信念传播算法就不适用了.通过对团树信念传播算法的进一步分析人们发现:它可以表示成一个关于团节点信念的优化问题的求解算法,其约束就是节点信念关于割集中变量的边缘分布一致.可以证明,这也保证了联合分布整体的一致性.类似地,我们也可以把其他图模型(例如伊辛模型)中更困难的推理表示成优化问题,考虑其近似求解方案,对应地 张宏毅 等:概率图模型研究进展综述 2483 设计出推理算法.Fig.5 Representation of graph models o

38、f Ising model 图5 伊辛(Ising)模型的图模型表示 2.2.1 环路信念传播 环路信念传播(loopy belief propagation,简称LBP6)是团树信念传播方法的自然推广.从算法上看,LBP与团树算法的区别仅在于它放松了团树算法所要求的流动相交性这个性质,因此允许在有环图上执行算法.保留环路的结果,是从节点 Ci到节点 Cj关于X变量的信息可能影响了 Cj对Y的信念,既而又传播回 Ci并对其关于X的信念造成反馈.这可能导致X的信念无法收敛,或者收敛到错误的分布.尽管环路信念传播的运行结果取决于具体模型及其参数,缺乏理论上好的保证,但在实际中其表现常常令人满意.在

39、编解码问题研究中,著名的Turbocode解码算法就被证明与环路信念传播算法等价15.可以证明,在伊辛模型上直接运行环路信念传播算法,等价于求解原优化问题的一个近似16:目标函数等价于优化Bethe近似的能量函数,而约束条件仅要求割集变量的边缘分布一致.在环路图中,这并不保证联合分布的整体一致.2.2.2 平均场近似 通过对可行域施加更多约束条件,平均场(mean field)算法简化优化目标函数,从另一个角度解决在类似伊辛模型的高树宽模型中近似推理的问题.例如对于伊辛模型,原优化问题为 ()()(,()supMAH p =+(2)其中,是模型参数;是对应的因子在该参数下的充分统计量的期望;M

40、称为边缘(概率)多面体剖分,是所有合理的边缘分布的集合;,为内积,H()是分布的熵函数,而p()是充分统计量期望对应的模型参数所定义的分 布.平均场算法采用,:u vuvM =替代实际可行域M,这相当于在去掉原伊辛模型所有边连接的一类模 型中,寻找伊辛模型的最佳近似.从而,其对应的熵函数化简为易于优化的形式:()()(log(1)log(1)vvvvv VH p=+(3)新的优化问题对每个v分别是凹的,因此可以采用迭代地关于每个v进行优化的方法求解,得到的更新方程为 ()1expvvuuu N v=(4)当算法收敛时,得到的v和A()就是原问题解的平均场近似.2.3 基于抽样方法的推理 当精确

41、推理计算困难时,抽样方法提供了计算随机变量边缘(条件)分布和其他函数的另一种途径17.抽样方法的种类很多,包括拒绝性采样、重要性采样1820、粒子滤波21、马尔可夫链蒙特卡罗(MCMC)22,23算法等.与变分推理方法不同,基于马尔可夫链的抽样推理方法在一定条件下,理论上能够渐近地收敛于真实分布;不仅如此,它还具有普遍的适用性.但对复杂的推理问题,马尔可夫链的混合时间通常无法估计,其实际效率也往往X1,1X1,3X1,2X2,3X2,2X3,1X3,3X3,2X2,1 2484 Journal of Software 软件学报 Vol.24,No.11,November 2013 低于针对具体

42、模型设计的变分优化推理算法.2.3.1 拒绝性采样 拒绝式采样意指与观测不一致的采样将被拒绝,它是贝叶斯网络中采样的最简单方法.考虑依条件概率分布从图模型G中抽样,则得到样本x的概率为P(x).若观测变量Xe=xe,查询变量Xq,则有:()1(|)()1qeexXqeeexP xXxP xxP xXx=(5)即在所有与观测一致的抽样中,查询变量Xq=xq的比例即其取值xq的条件概率.注意到接受概率1Xe=xe关于观测变量的数目呈指数趋于0,因此,拒绝性采样不适用于连续变量以及有大量观测的模型.2.3.2 重要性采样 重要性采样意指首先获得服从另一分布的样本,再根据重要性对样本加权,以使样本等效

43、于来自目标分布.考虑欲估计关于X的函数f(X),抽样分布q(X),目标分布p(X),则由 1()1()()()()d(),()()Mipiiiiip Xp XEf Xf Xq XXf X wwq XMq X=(6)可依分布q(x)抽样得到X1,XM,计算wi进行重要性加权,即可得到Ep(f(X)的估计.对一般的图模型,往往只知 道()(),()(),pqp Xp X Zq Xq X Z=?而不知道其归一化常数.此时,可利用:()()()(),()()qppqqpqZZp Xp XEf XEf XEZq XZq X=?,得到:11()()()()()()()MqiiipMiqip XEf Xf

44、X wq XEf Xp XwEq X=?(7)其中,()()iiip Xwq X=.因此,同样可以从样本中获得关于目标分布的函数值估计.在应用中,虽然只要求q(x)0,xy:p(y)0,但若q(x)与p(x)差别较大,估计的误差也往往较大.结合退火等技术发展出的退火重要性采样(annealed importance sampling,简称AIS)可以减少估计误差.似然度加权也是一种常用的图模型抽样算法.它可以看作重要性采样的一个特例.在似然度加权中,样本及其权重按如下算法产生:算法 1.似然度加权.输入:观测集合(E,xE).输出:样本x以及重要性权值w.(1)w1(2)foreach 拓扑排

45、序中的第i个变量 do(3)if iE then(4)Xixi(5)wwp(xi|X(i)(6)else(7)依Xip(Xi|XN(i)抽样(8)return(x,w)张宏毅 等:概率图模型研究进展综述 2485 2.3.3 MCMC算法 考虑随机向量X状态空间上的随机过程X(1),X(t),如果适当选择状态转移矩阵并作用于X,则可构造出马尔可夫链使X(t)的分布收敛于后验分布.因此,这一类算法称为MCMC算法.由不同的状态转移方法确定的MCMC算法具有不同的性质.下面主要介绍最简单、最常见的两种算法:Gibbs抽样和Metropolis-Hastings算法.Gibbs抽样 Gibbs抽样算

46、法假定对任意变量Xi,我们可以从p(xi|xi)中抽样.算法的每一步依次选择一个变量,以其他变量的当前值为条件,从该变量的条件分布中抽样更新其值.Gibbs抽样的优势在于算法简单,缺点在于一次只能更新一个变量,效率较低.改进的联锁(blocked)Gibbs抽样在每一步能够对相互条件独立的变量同时抽样.但当从p(xi|xi)中抽样比较困难时,Gibbs抽样就不适用了.Gibbs抽样可以看作下面介绍的Metropolis-Hastings算法的一个特例.Metropolis-Hastings算法 Metropolis-Hastings算法具有更大的灵活性.它只假定我们可以产生遍历状态空间的马尔可

47、夫链,并且能够计算样本的生成概率和比较不同样本的似然比.我们可以为算法设计不同的建议分布(proposal distribution)Q,通过控制接受概率(acceptance probability),使状态转移分布对目标分布满足细致平衡(detailed balance)性质.具体地,设Q(xx)表示由状态转移函数从x生成状态x的概率密度,A(xx)表示状态转移xx的接受概率,则由细致平衡原理有:()()()()()()A xxp x Q xxA xxp x Q xx=(8)取接受概率为()()()min 1,()()p x Q xxA xxp x Q xx=,即可使上式成立.通常,我们希

48、望建议分布Q的选择能够使算法有较高的接受概率,同时又能较快而全面地探索状态空间的不同区域.但实际中,算法的表现往往依赖于概率分布的复杂程度以及算法设计者对问题的理解.一些高级的MCMC算法,例如推广的Swendsen-Wang算法24,25以及Hamiltonian Monte Carlo26方法,针对不同的方面对基本算法进行了改进.3 概率图模型的学习 对于复杂的、缺乏专家经验的概率模型,如果我们有一定数量的观测数据,通常希望能够从观测数据中获得模型的参数甚至结构.这又分为几种不同的情况:贝叶斯网络或马尔可夫网络;所有变量都可观测的模型或只可观测部分变量的模型;结构已知的模型或结构未知的模型

49、.不同的情况产生出一系列不同难度的问题.在参数估计的不同准则中:一种常用的估计方法是最大似然估计(maximum likelihood estimation,简称MLE),即在参数空间中寻找使观测数据的似然最大的参数;另一种称为最大后验(maximum a posteriori,简称MAP)的估计方法寻找参数空间中后验概率最大的参数.以下为叙述简单,我们只介绍最大似然估计的方法,对应的最大后验估计可通过相同方法导出.在有缺失数据的参数估计中,我们还将介绍视参数为潜在的随机变量,估计其后验分布的贝叶斯推断方法.3.1 完全可观测模型的参数估计 由于已知的信息最多,完全可观测模型的学习问题是各类学

50、习问题中最简单的.然而即使在这种情况下,贝叶斯网络和马尔可夫网络的学习算法代价也有着本质的不同.我们将会看到:贝叶斯网络的参数估计问题是可分解的,因而容易求解;但是马尔可夫网络由于其因子缺少局部的归一化性质,由全局归一化常数带来的模型参数之间的耦合增大了学习的难度.3.1.1 估计贝叶斯网络的参数 对于贝叶斯网络G,记其变量集合为X,参数为,观测样本为D=X(1),X(N),则似然函数为 2486 Journal of Software 软件学报 Vol.24,No.11,November 2013 ()()1(;)(|();)jNiijjjiXxLDp xu x=(9)最大化似然函数等价于最