【免费】概率图模型研究进展综述

需积分: 0 107 浏览量 2022-08-03 15:37:20 上传评论收藏 733KB PDF 举报

资源详情

资源评论

资源推荐

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2013,24(11):24762497 [doi: 10.3724/SP.J.1001.2013.04486] http://www.jos.org.cn

概率图模型研究进展综述





张宏毅

1,2

王立威

1,2

陈瑜希

1,2

(机器感知与智能教育部重点实验室(北京大学),北京 100871)

(北京大学信息科学技术学院智能科学系,北京 100871)

通讯作者: 张宏毅, E-mail: hongyi.zhang.pku@gmail.com

摘要: 概率图模型作为一类有力的工具,能够简洁地表示复杂的概率分布,有效地(近似)计算边缘分布和条件分

布,方便地学习概率模型中的参数和超参数.因此,它作为一种处理不确定性的形式化方法,被广泛应用于需要进行

自动的概率推理的场合,例如计算机视觉、自然语言处理.回顾了有关概率图模型的表示、推理和学习的基本概念

和主要结果,并详细介绍了这些方法在两种重要的概率模型中的应用.还回顾了在加速经典近似推理算法方面的新

进展.最后讨论了相关方向的研究前景.

关键词: 概率图模型;概率推理;机器学习

中图法分类号: TP181 文献标识码: A

中文引用格式: 张宏毅,王立威,陈瑜希.概率图模型研究进展综述.软件学报,2013,24(11):24762497. http://www.jos.org.cn/

1000-9825/4486.htm

英文引用格式: Zhang HY, Wang LW, Chen YX. Research progress of probabilistic graphical models: A survey. Ruan Jian Xue

Bao/Journal of Software, 2013,24(11):24762497 (in Chinese). http://www.jos.org.cn/1000-9825/4486.htm

Research Progress of Probabilistic Graphical Models: A Survey

ZHANG Hong-Yi

1,2

, WANG Li-Wei

1,2

, CHEN Yu-Xi

1,2

(Key Laboratory of Machine Perception (Peking University), Ministry of Education, Beijing 100871, China)

(Department of Machine Intelligence, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871,

China)

Corresponding author: ZHANG Hong-Yi, E-mail: hongyi.zhang.pku@gmail.com

Abstract: Probabilistic graphical models are 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 some 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 uses 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

我们工作和生活中的许多问题都需要通过推理来解决.通过推理,我们综合已有的信息,对我们感兴趣的未

知量做出估计,或者决定采取某种行动.例如,程序员通过观察程序在测试中的输出判断程序是否有错误以及需

要进一步调试的代码位置,医生通过患者的自我报告、患者体征、医学检测结果和流行病爆发的状态判断患者

可能罹患的疾病.一直以来,计算机科学都在努力将推理自动化,例如,编写能够自动对程序进行测试并且诊断

 基金项目: 国家自然科学基金(61222307, 61075003)

收稿时间: 2013-07-17; 修改时间: 2013-08-02; 定稿时间: 2013-08-27

张宏毅等:概率图模型研究进展综述

2477

错误位置的调试工具、能够辅助医生诊断患者病情的医疗诊断专家系统、理解英语文本的含义并将其转换为

汉语的自动翻译系统、从机场监控视频中发现可疑人员的安全监控系统等等.人们设计出多种多样的方法来实

现这些应用,其中,将知识陈述式地表示为概率模型,通过计算我们所关心变量的概率分布实现推理的途径具有

独特优势:

首先,它提供了一个描述框架,使我们能够将不同领域的知识抽象为概率模型,将各种应用中的问题都归结

为计算概率模型里某些变量的概率分布,从而将知识表示和推理分离开来

[1]

.模型的设计主要关心如何根据领

域知识设计出反映问题本质的概率模型,同时兼顾有效推理的可行性,而推理算法的设计只需关心如何有效地

在一般的或者特定的概率模型中进行推理.这种一定程度上的正交性极大地扩展了概率模型的应用,也加快了

它的发展速度.

其次,它能够评估未知量取值的可能性,对不同取值的概率给出量化的估计.这在涉及风险的决策系统中非

常重要.

另外,它常常具有良好的复用性.例如,我们不需要为预测父亲和儿子患上某种家族遗传病的概率分别设计

算法,只需一个关于基因和表现型的家族遗传路径的概率模型,就能处理关于遗传病风险的各种推理问题.

概率图模型就是一类描述这种陈述式表示的概率模型的建模和推理框架,它为简洁地表示、有效地推理和

学习各种类型的概率模型提供了可能.在历史上,曾经有来自不同学科的尝试使用图的形式表示高维分布的变

量间的相关关系的例子

[2,3]

.在人工智能领域,概率方法始于构造专家系统的早期尝试

[4,5]

.到 20 世纪 80 年代末,

由于在贝叶斯网络和一般的概率图模型中进行推理的一系列重要进展

[6,7]

,以及大规模专家系统的成功应用

[8]

以概率图模型为代表的概率方法重新受到了重视.如今,经过 20 余年的发展,概率图模型的推断和学习已广泛

应用于机器学习、计算机视觉、自然语言处理、语音识别、专家系统、用户推荐、社交网络挖掘、生物信息

学等研究领域的最新成果中,成为人工智能相关研究中不可或缺的一门技术.概率图模型的研究方兴未艾,而且

应用范围和研究热度仍在继续增长.

本文首先介绍概率模型中的推断和学习问题的相关背景,并引入条件独立性这一重要概念;然后,根据研究

主题依次综述概率图模型的表示、推理和学习问题核心内容的研究进展;我们还将介绍两种近年来有较大影响

的概率图模型——条件随机场和主题模型,以说明概率图模型的表示、推理和学习这 3 个环节的联系;最后,讨

论关于大规模图模型的一些延伸主题,包括效率更高的推理算法、并行和分布式推理以及针对查询的推理

问题.

在本文中,我们将统一使用大写字母(例如 A,X)表示随机变量,如未指明变量类型,则默认为离散变量;使用

小写字母(例如 x,y)表示随机变量的赋值;使用大写字母表示集合(例如 A,X)或者某种数据结构(例如 F,H).

 推断问题

多数与人工智能相关的应用所解决的问题都可以形式化地表述为概率模型中的推断问题.在推断问题中,

目标是推断我们感兴趣的随机变量集合 S 中变量的取值分布,而我们采用生成式模型或判别式模型为问题建

模,并运用一般的或针对具体模型的推断算法来计算这一分布

.在生成式模型中,我们已知包含感兴趣变量集合

在内的一些相互联系的变量的联合分布,以及其中可观测变量的观测值(或真实值),目标是以可观测变量为条

件计算目标变量的条件概率.在判别式模型中,我们已知包含感兴趣变量集合 S 在内的一些相互联系的变量与

另一些可观测变量之间的联系,即以可观测变量为条件的条件分布,以及可观测变量的观测值,目标同样是计算

感兴趣变量集合 S 中的变量的条件概率.

例如,在计算机视觉应用中,人们可能感兴趣一个图像区域所表示的物体类别;在自然语言处理应用中,人

们可能感兴趣一句汉语文本的语法分析结果;而在用户推荐应用中,人们可能感兴趣某用户对某产品的喜好程

度.这些来自不同领域的问题都可以表示成概率模型中的推断问题,并得到统一的处理.

在以上描述中,要计算感兴趣变量的条件概率,需要知道感兴趣变量及其相关变量包含可观测变量的联合

分布或以可观测变量为条件的条件分布.一般情况下,设全体随机变量的集合为 S,感兴趣的变量集合为{X

,…,X

}=XS,可观测变量集合为{O

,…,O

}=OS,其他变量的集合记为 Y=S\(XO),则生成式模型确定了

2478

Journal of Software 软件学报 Vol.24, No.11, November 2013

联合分布P(X,Y,O),而判别式模型确定了条件分布P(X,Y|O).给定观测值,即 O 的一个赋值{o

,…,o

},在生成式

模型中,我们需要使用概率求和规则消去 Y 中的变量,并重新归一化,得到条件概率分布 P(X|O),在判别式模型

中,我们只需求和消去 Y 中的变量即可.

然而在实际的推断问题中,我们还要考虑到数据结构的表示开销和运算开销(时间和空间复杂度).假设在

某模型中,每个变量可以有两种取值,如果我们简单地定义以上概率分布,并使用求和规则推断目标分布,容易

验证时间开销和空间开销都至少是



|Y|

).因此,我们必须寻找更紧凑的表示概率分布的数据结构以及能够在

其中有效运行的推断算法.

 学习问题

推断问题研究如何在已有的模型基础上,根据观测计算目标变量的分布,并没有考虑如何构建模型的问题.

一方面,模型可以由领域专家构建,模型的结构以及参数可以由专家根据经验来指定;另一方面,实际应用中可

能需要对人类尚不了解的问题建立模型,或建立参数众多的大规模模型,或历史经验以数据的形式而不是人类

知识存储等等,在这些情况下,模型的结构和参数并不适合人工指定,因此,我们希望设计算法从已往的数据中

学习得到模型的参数和结构.

从更一般的角度来讲,学习问题可以看作是推断问题的一类特例:我们感兴趣的随机变量是模型的参数或

结构.因此,对学习问题的简单处理将会遇到与推断问题相同的困难,即表示和计算的时间和空间复杂度关于模

型的变量数目都是指数级的,而我们需要能够处理实际应用数据规模的有效的学习算法.

学习问题特有的困难在于:用于学习的训练样本通常是有限的,并且算法允许的训练时间也是有限的.当我

们允许复杂的模型尝试从数据中估计联合分布的每一项概率时,我们将面对所谓的维数灾难.相对于呈指数增

长的参数,样本量往往太少,以至于我们对真实分布的估计几乎必定有很大的误差.

 条件独立

考虑变量集 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).模型中的条件独立性是对推断问题和学习问题进行有效计

算的基础.例如,考虑对式 P(A,B,C)求和以消去 B,C,利用上述条件独立性,我们可以写出:





(,,) (|)(|)() (|)() (|).

BC B C C B

PABC PACPBCPC PACPC PBC

 

经过变换,在模型的表示上,需要指定的项从 O(|A||B||C|)个减少到 O((|A|+|B|)|C|)个,运算次数从 O(|B||C|)减少

到 O(|B|+|C|).注意到,我们可利用集合 A(或 B,C)内的条件独立性进一步简化问题的表示和计算.事实上,如果一

个概率分布能够分解为一些包含不超过 d 个变量的项的乘积,且每个变量的可取值不超过 m,则表示和推断的

复杂度有上界O(m

).其中,d 表示一个复杂的概率分布分解为若干较简单分布的乘积性质的强弱,或者说表示变

量之间的条件独立性的强弱.

条件独立性是概率图模型里非常基本的核心概念,贯穿模型的表示、推理和学习等各方面.概率图模型将

概率论与图论结合,提供了直观地表示随机变量间条件独立性质的工具,便于人们分析模型的性质,同时使得有

关图论的结论和算法可以用于处理概率模型的推断和学习问题

[1]

1 概率图模型的表示

概率图模型的表示刻画了模型的随机变量在变量层面的依赖关系,反映出问题的概率结构以及推理的难

易程度,也为推理算法提供了可以操作的数据结构.概率图模型的表示方法有多种,我们主要介绍最常见的贝叶

斯网络、马尔可夫网络、因子图等表示,以及一些简化表示的记法.

1.1 贝叶斯网络

对应于有向无环图的概率模型称为贝叶斯网络(如图 1 所示).图的每个顶点代表随机变量或随机向量,边代

表变量间的条件相关关系,常常也被用于表示因果关系.对于任意一条边和它所连接的两个顶点 AB,A 称为 B

的父节点,B 称为 A 的子节点.贝叶斯网络中每个顶点 X 和它的父节点 U(X)表示一个条件分布 P(X|U(X)),称为一

张宏毅等:概率图模型研究进展综述

2479

个因子.

整个概率分布由所有因子的乘积表示:

() ( |()).PX PX UX



Fig.1 Bayesian network of five variables and its union distribution

图 1 含有 5 个变量的贝叶斯网络及其表示的联合分布

1.1.1

贝叶斯网络中的独立性

在贝叶斯网络中,条件独立性可以直接根据图的结构判定.我们首先考虑 3 个变量之间的相互关系.由 X,Y,Z

这 3 个变量构成的 X,Y 不直接相关的贝叶斯网络,X,Y 之间的关系有以下几种形式:

X 到 Y 是成因路径(XZY).当且仅当 Z 未被观测时,X,Y 不相互影响(即 X 的取值不影响 Y 的条件分

布,反之亦然).因此,X,Y 不相互独立,但给定 Z 时,X,Y 条件独立.

X 到 Y 是证据路径(XZY).当且仅当 Z 未被观测时,X,Y 不相互影响.因此,X,Y 不相互独立,但给定 Z

时,X,Y 条件独立.

X,Y 有共同原因(XZY).当且仅当 Z 未被观测时,X,Y 不相互影响.因此,X,Y 不相互独立,但给定 Z 时,

X,Y

条件独立.

X,Y 有共同效果(XZY).当且仅当 Z 或 Z 的一个子代节点被观测时,X,Y 相互影响.因此,X,Y 相互独

立,但给定 Z 或其子代节点时,X,Y 不相互独立.

对于贝叶斯网络中的一条路径 X

…X

和观测变量的子集 Z,当 X

和 X

的取值能够相互影响时,我们称路

径

…X

是有效的.在一般情况下,我们有以下结论:给定 Z 时,X

…X

是有效的当且仅当:

对该路径上的每个 V 字结构 X

i1

X

X

i+1

,存在 X

或其子代在 Z 中;

路径上的其他任何节点都不在 Z 中.

1.2 马尔可夫网络

注意到除了用若干条件概率分布的乘积构造联合分布以外,还有更一般的构造概率分布的方法.考虑定义

在随机变量集合 X 的子集



变量值域上的非负实值函数



,若对任意 i,



(



)≥0,







且 ()









则

()







定义了一个有效的分布.其中,Z 称为归一化常数,由模型参数确定而与观测值无关.

对应于无向图的概率模型称为马尔可夫网络,图的每个顶点代表随机变量或随机向量,边代表变量间的相

关关系

.对任意一条边,其所在的最大的团(全连通子图)称为一个因子.每一条边都唯一地属于一个因子,由于有

了上述构造概率分布的方法

,只需为每个因子



指定一个非负函数



(



),并对所有因子的乘积归一化,我们就可

以构造出由马尔可夫网络表示的概率模型

归一化常数是马尔可夫网络与贝叶斯网络的重要区别之一.在许多模型中,直接计算归一化常数的复杂度

是指数级的

,因此必须寻找其他替代方法解决推断或学习问题.

1.2.1

马尔可夫网络中的独立性

马尔可夫网络中的独立性情况比贝叶斯网络要简单.与之前定义类似,对马尔可夫网络中的一条路径

-…-X

和观测变量的子集 Z,当 X

和 X

的取值能够相互影响时,我们称路径 X

-…-X

是有效的.在一般情况下,

我们有以下结论:给定 Z 时,X

-…-X

是有效的,当且仅当路径上的其他任何节点都不在 Z 中.

P(A,B,C,D,E)=P(A)P(B|A)P(C|B)P(D|B)P(E|C,D)

2480

Journal of Software

软件学报 Vol.24, No.11, November 2013

1.3 因子图

图模型的另一种常见表示是因子图

[9]

.在因子图 G=(X,F)中,我们规定存在两种顶点:随机变量和因子.边是

无向的,连接因子和它所包含的随机变量.因此,每个随机变量的邻居顶点是包含它的各个因子,而每个因子的

邻居顶点是它的辖域内的各个随机变量

因子图是一种比马尔可夫网络更精细的模型表示,例如在图 2 所示的因子图中,我们可以区分不同的分布

究竟是定义为因子



的乘积还是一个辖域为 A,B,C 的大因子



ABC

;而在马尔可夫网络中,它们有相同

的表示而无法从图结构上进行区分.

Fig.2

图 2

与马尔可夫网络相似,因子图中也有马尔可夫网络的概念.

从马尔可夫网络的特征和因子图的定义中容易推导,在因子图中,设边集为 E,变量 X

的马尔可夫网络是由

B(X

)={X

:(X



)E 且(X



)E 且 ji}构成的变量集合.

因子图数据结构由于显式地表示出构造概率分布的因子,因此特别适合一类通过在变量与因子之间传递

消息的推理算法(参见第 2.2.1节)的执行.包括微软的 Infer.NET项目

[10]

在内,许多采用这类算法的推理系统都采

用了因子图的表示

1.4 盘式记法、模板

盘式记法(plate notation)是一种常用的图模型的简化记法,考虑如下简单的概率模型:在一个装有白球和黑

球的盒子里进行有放回抽样

,n 次抽样的结果记为 X

,…,X

,盒子中白球的比例记为



,则该概率模型可以采用标

准的记法表示,也可以用盘式模型表示(如图 3 所示).在盘式模型中,我们用一个框(称为盘)圈住图模型中重复的

部分

,并在框内标注重复的次数.

Fig.3

图 3

盘式记法能够为我们表示和分析许多概率模型提供很大的方便,但它也有一定的局限性.例如,它无法表示

盘内变量不同拷贝间的相关性,而这种相关性广泛出现于动态贝叶斯网络中.在动态贝叶斯网络中,概率模型符

合

k 阶马尔可夫假设,因此,t 时刻的系统状态只与[max(0,tk)]时刻的状态有关.为了简明地表示这类含有重复的

基本结构的动态贝叶斯网络,我们可以使用称为 kBN 的模板.例如,图 4 展示了隐马尔可夫模型及其 2BN 模板

记法

(b) 仅含有 1 个三元因子的因子图 (a) 含有 3 个二元因子的因子图 (c) 对应的马尔可夫网络仅有 1 种表示

(a) 展开的摸球模型 (b) 盘式记法



…



剩余21页未读，继续阅读

评论收藏

内容反馈

禁忌的爱

粉丝: 19
资源: 334

概率图模型研究进展综述_张宏毅1

评论0

最新资源

概率图模型研究进展综述_张宏毅1

评论0

宏毅百汇-商业推广提案.ppt

宏毅百汇-商业推广提案.pptx

制冷空调设备电气与控制 - [卫宏毅].pdf

无线移动自组织网

有机蒙脱土对甲基橙的吸附行为研究

台大_李宏毅PPT_机器学习

EdgeAI_NetworkCompression_HRank-Filter-Pruning-using-High-Rank-Feature-Map_Report

fixup:修正初始化实施

单片机与DSP中的WCDMA系统基带处理的DSP FPGA实现方案

自动控制原理实验报告

一种基于区块链的安全文件存储和共享方法.zip

基于区块链的安全文件存储和共享方法.docx

BurpLoaderKeygen.jar.zip

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

STM32F103C8T6核心板-电路原理图1.PDF

软件工程导论(第六版)课后习题答案1

OpenVAS离线资源

goby红队&社区版-win-64-2.4.7

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

全面的安全基线核查清单

2023年最全最精简wifi密码字典(2.6G)

最新资源