当前位置：文档库 › 概率图模型研究进展综述

概率图模型研究进展综述

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/15304200.html,

Journal of Software,2013,24(11):2476?2497 [doi: 10.3724/SP.J.1001.2013.04486] https://www.wendangku.net/doc/15304200.html,

概率图模型研究进展综述

张宏毅1,2, 王立威1,2, 陈瑜希1,2

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

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

通讯作者: 张宏毅, E-mail: hongyi.zhang.pku@https://www.wendangku.net/doc/15304200.html,

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

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

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

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

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

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

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

中文引用格式: 张宏毅,王立威,陈瑜希.概率图模型研究进展综述.软件学报,2013,24(11):2476?2497.https://www.wendangku.net/doc/15304200.html,/

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).https://www.wendangku.net/doc/15304200.html,/1000-9825/4486.htm

Research Progress of Probabilistic Graphical Models: A Survey

ZHANG Hong-Yi1,2, WANG Li-Wei1,2, CHEN Yu-Xi1,2

1(Key Laboratory of 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: hongyi.zhang.pku@https://www.wendangku.net/doc/15304200.html,

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,感兴趣的变量集合为{X1, X2,…,X n}=X?S,可观测变量集合为{O1,O2,…,O m}=O?S,其他变量的集合记为Y=S\(X∪O),则生成式模型确定了

2478 Journal of Software 软件学报 V ol.24, No.11, November 2013 联合分布P (X ,Y ,O ),而判别式模型确定了条件分布P (X ,Y |O ).给定观测值,即O 的一个赋值{o 1,o 2,…,o m },在生成式模型中,我们需要使用概率求和规则消去Y 中的变量,并重新归一化,得到条件概率分布P (X |O ),在判别式模型中,我们只需求和消去Y 中的变量即可.

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

某模型中,每个变量可以有两种取值,如果我们简单地定义以上概率分布,并使用求和规则推断目标分布,容易验证时间开销和空间开销都至少是Ω(2|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 ,利用上述条件独立性,我们可以写出:

(),(,,)(|)(|)()(|)()(|).B C B C C B P A B C P A C P B C P C P A C P C P B C ==∑∑∑∑∑

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

到O (|B |+|C |).注意到,我们可利用集合A (或B ,C )内的条件独立性进一步简化问题的表示和计算.事实上,如果一个概率分布能够分解为一些包含不超过d 个变量的项的乘积,且每个变量的可取值不超过m ,则表示和推断的复杂度有上界O (m d ).其中,d 表示一个复杂的概率分布分解为若干较简单分布的乘积性质的强弱,或者说表示变量之间的条件独立性的强弱.

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

概率论与图论结合,提供了直观地表示随机变量间条件独立性质的工具,便于人们分析模型的性质,同时使得有关图论的结论和算法可以用于处理概率模型的推断和学习问题[1].

1 概率图模型的表示

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

易程度,也为推理算法提供了可以操作的数据结构.概率图模型的表示方法有多种,我们主要介绍最常见的贝叶斯网络、马尔可夫网络、因子图等表示,以及一些简化表示的记法.

1.1 贝叶斯网络

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

表变量间的条件相关关系,常常也被用于表示因果关系.对于任意一条边和它所连接的两个顶点A →B ,A 称为B 的父节点,B 称为A 的子节点.贝叶斯网络中每个顶点X 和它的父节点U (X )表示一个条件分布P (X |U (X )),称为一

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

2479

个因子.

整个概率分布由所有因子的乘积表示: ()(|()).P X P X U X =∏

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 条件独立. 2)

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

X ,Y 有共同原因(X ←Z →Y ).当且仅当Z 未被观测时,X ,Y 不相互影响.因此,X ,Y 不相互独立,但给定Z 时, X ,Y 条件独立. 4) X ,Y 有共同效果(X →Z ←Y ).当且仅当Z 或Z 的一个子代节点被观测时,X ,Y 相互影响.因此,X ,Y 相互独

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

对于贝叶斯网络中的一条路径X 1 … X n 和观测变量的子集Z ,当X 1和X n 的取值能够相互影响时,我们

称路径X 1 … X n 是有效的.在一般情况下,我们有以下结论:给定Z 时,X 1 … X n 是有效的当且仅当:

对该路径上的每个V 字结构X i ?1→X i ←X i +1,存在X i 或其子代在Z 中; 2) 路径上的其他任何节点都不在Z 中.

1.2 马尔可夫网络

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

在随机变量集合X 的子集Ψ变量值域上的非负实值函数φ,若对任意i ,φi (Ψi )≥0,i i X Ψ=∪且()i i X i Z φΨ=>∑∏

0,则

1()i i i Z

φΨ∏定义了一个有效的分布.其中,Z 称为归一化常数,由模型参数确定而与观测值无关. 对应于无向图的概率模型称为马尔可夫网络,图的每个顶点代表随机变量或随机向量,边代表变量间的相关关系.对任意一条边,其所在的最大的团(全连通子图)称为一个因子.每一条边都唯一地属于一个因子,由于有了上述构造概率分布的方法,只需为每个因子Ψ指定一个非负函数φ(Ψ),并对所有因子的乘积归一化,我们就可以构造出由马尔可夫网络表示的概率模型.

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

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

1.2.1 马尔可夫网络中的独立性

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

X 1-…-X n 和观测变量的子集Z ,当X 1和X n 的取值能够相互影响时,我们称路径X 1-…-X n 是有效的.在一般情况下,我们有以下结论:给定Z 时,X 1-…-X n 是有效的,当且仅当路径上的其他任何节点都不在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 软件学报 V ol.24, No.11, November 2013

1.3 因子图图模型的另一种常见表示是因子图[9].在因子图G =(X ,F )中,我们规定存在两种顶点:随机变量和因子.边是

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

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

究竟是定义为因子ΨAB ,ΨBC ,ΨAC 的乘积还是一个辖域为A ,B ,C 的大因子ΨABC ;而在马尔可夫网络中,它们有相同的表示而无法从图结构上进行区分.

Fig.2

图2

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

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

B (X i )={

X j :(X j ,α)∈

E 且(X i ,α)∈E 且j ≠i }构成的变量集合.

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

消息的推理算法(参见第2.2.1节)的执行.包括微软的https://www.wendangku.net/doc/15304200.html, 项目[10]在内,许多采用这类算法的推理系统都采用了因子图的表示.

1.4 盘式记法、模板

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

球的盒子里进行有放回抽样,n 次抽样的结果记为X 1,…,X n ,盒子中白球的比例记为θ,则该概率模型可以采用标准的记法表示,也可以用盘式模型表示(如图3所示).在盘式模型中,我们用一个框(称为盘)圈住图模型中重复的部分,并在框内标注重复的次数.

Fig.3

图3

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

盘内变量不同拷贝间的相关性,而这种相关性广泛出现于动态贝叶斯网络中.在动态贝叶斯网络中,概率模型符合k 阶马尔可夫假设,因此,t 时刻的系统状态只与[max(0,t ?k )]时刻的状态有关.为了简明地表示这类含有重复的基本结构的动态贝叶斯网络,我们可以使用称为kBN 的模板.例如,图4展示了隐马尔可夫模型及其2BN 模板记法.

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

B A

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

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

2481

Fig.4

图4

2 概率图模型的推理

在本节中,我们介绍图模型推理所使用的一些重要算法.这些算法可大致分为3类:

? 精确推理算法.能够计算查询变量的边缘分布或条件分布的精确值,但其计算复杂度随着图模型的树

宽呈指数增长,因此适用范围有限.

? 基于优化的推理算法.将图模型的推断形式化为优化问题,通过松弛优化问题的约束条件或者调整优

化的目标函数,算法能够在较低的时间复杂度下获得原问题的近似解;对于多数难以进行精确推理的

图模型,对其变量进行抽样并不困难.

? 基于抽样的推理算法.试图产生所求边缘分布或条件分布的抽样,使用样本的经验分布来近似真实

分布.

一般的图模型中的推理是困难的.关于最坏情况下推理的复杂度,我们已经知道一系列负面的结果:图模型

精确推理是#P -完全的;相对误差ε的图模型近似推理是NP-难的;绝对误差ε∈(0,1/2)的图模型近似推理有多项式的时间复杂度,但以证据为条件的近似推理依旧是NP-难的[11].然而,实际应用中的问题往往具有良好的条件独立结构,因而图模型的精确推理和近似推理算法带来了许多成功的应用.

从推理的目标来区分,有时我们希望计算目标变量的(条件)边缘分布,称为后验推理;有时我们希望计算目

标变量(集合)最可能的(联合)赋值,称为最大后验推理.我们将首先介绍3类后验推理方法,最后统一介绍最大后验推理方法.

由于贝叶斯网络中的条件分布P (X |Y )也可看作因子ψ(X |Y ),本节中,我们将统一地采用因子ψ来构造分布.

2.1 精确推理

图模型的精确推理算法实质是一类动态规划算法,它利用条件独立性导致的联合分布的因子化特征,压缩

图模型变量之间传递的信息.

2.1.1 变量消去算法

变量消去算法[12]是最直观且容易推导的精确推理算法,然而它却是其他更高级的精确推理算法的基础.考

虑贝叶斯网络(如图1所示)所定义的联合分布P (A ,B ,C ,D ,E ),我们如果观测到变量E =e ,并且想要计算变量C =c 的条件概率P (c |e ),则可以简单地写出:

,,1(|)(,,,,),a b d

P c e P a b c d e Z =∑ 其中,,,,(,,,,).a b c d Z P a b c d e =∑

利用贝叶斯网络所蕴含的独立性,以上求和可分别化简为

,,,,(,,,,)()(|)(|)(|)(|,)(|,)(|)(|)()(|)a b d a b d d b a

P a b c d e P a P b a P c b P d b P e c d P e c d P c b P d b P a P b a ????==????????∑∑∑∑∑ (1) 简而言之,变量消去算法实际是利用了乘法对加法的分配律,将对多个变量的积的求和分解为对部分变量

x y (a) 展开的隐马尔可夫模型 (b) 2BN-记法 (该记法要求使用盘分别圈住t 时刻的变量和它们的父节点变量)

2482 Journal of Software软件学报 V ol.24, No.11, November 2013

交替进行的求积与求和.变量消去算法的缺点在于:一次变量消去只能求出本次查询变量的条件分布,不同的查询将带来大量的重复计算.为实现一次计算、多次使用,就需要更加仔细地进行算法设计.为了保证算法的正确性,需要保证所有与求和变量有关的项都在求和符号内,这也是以下两种常用精确推理算法的理论基础.

2.1.2 团树算法

为了实现精确推理的更高效算法,需要设计一种支持推理运算的数据结构:团树.团树是一种具有如下性质的树结构:

1) 团树的每个顶点都是对应图模型中因子的集合.

2) 族保持性:原图模型中的每个因子都属于至少1个团树顶点.

3) 流动相交性:如果变量X在团树的两个顶点C i,C j中出现,则X出现在C i,C j之间的每一个顶点中.

团树中,相邻两顶点的变量的交S ij=C i∩C j称为两顶点的割集.

从同一图模型可以生成多种团树,它们的推理代价并不相同,但寻找推理代价最小的团树是困难的.一个比较好的方法是在所谓“最大消去团”的全连通图上寻找好的团树.指定一个变量消去的顺序,考虑依次消去变量时所生成的团,以其中的最大团为顶点生成全连通图,用割集的基数为边赋权,则该全连通图的最大权生成树就是一个较好的团树.这是因为在变量消去的过程中,我们只需要消去未出现在割集中的变量,因此对于给定的顶点集合,割集中包含的变量较多,计算代价相对就较小.

团树生成之后,需要计算团树顶点对应的因子.为此,只需对每个顶点遍历原图模型因子的集合,若该因子所含变量是该团树顶点所含变量的子集,则将其乘入该顶点的因子中.团树对应的因子集合称为可分解密度,这是因为它们是原概率分布在团树上分解的结果.

有了团树和可分解密度,就可以执行以下精确推理算法了:

? 消息传递(也称Shafer-Shenoy算法[13]、和-积算法).

在消息传递算法中,当且仅当节点A收到了除邻居节点B外所有邻居节点的消息时,A才向B传递消息.消息传递算法按如下步骤执行:

1) 在团树中选择一个根节点,由根节点出发构造一个单根树.

2) 从根节点起递归地执行:如果该节点的子节点收到了其他所有邻居的消息,则子节点向该节点传递

消息.

3) 从根节点起递归地执行:如果该节点收到了除某个子节点外其他所有邻居的消息,则该节点向子节点

传递消息.

? 信念传播(也称HUGIN算法[14]).

在信念传播算法中,我们为每个节点附加一个称为信念的变量.在算法运行的每一步,每个节点都同时向其相邻节点传递消息,消息的内容是该节点当前关于其割集中变量的边缘分布的信念.每个节点在接收到来自其他节点的消息后立即更新其信念:将自身的信念乘以新接收的消息,并除去上一次从相同节点接收到的消息.如果任一节点在收到其邻居节点的消息后自身的信念都不再发生变化,算法就收敛了.可以证明:对于团树上的信念传播,每对节点间传递两次消息后,算法就会收敛,且收敛于正确的分布(可能需要归一化).

2.2 基于优化的近似推理

在上一节中,我们介绍了用于精确推理的信念传播算法,其中使用到了团树这一数据结构.团树可以在对原始的图模型进行变量消去的过程中生成,团树上信念传播的复杂度是团树中最大团所含变量数目的指数量级.而如果我们对于在计算机视觉等领域常用的伊辛(Ising)模型生成团树(如图5所示,其中,灰色加粗的变量集合为变量X2,2的马尔可夫毯),设图模型的变量数量为Θ(N2),则一个团中将含有Ω(N)个变量,精确推理的复杂度是2Ω(N).因此,对于具有这类变量耦合性质的模型,团树上的信念传播算法就不适用了.

通过对团树信念传播算法的进一步分析人们发现:它可以表示成一个关于团节点信念的优化问题的求解算法,其约束就是节点信念关于割集中变量的边缘分布一致.可以证明,这也保证了联合分布整体的一致性.类似地,我们也可以把其他图模型(例如伊辛模型)中更困难的推理表示成优化问题,考虑其近似求解方案,对应地

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

2483 设计出推理算法.

Fig.5 Representation of graph models of Ising model

图5 伊辛(Ising)模型的图模型表示

2.2.1 环路信念传播

环路信念传播(loopy belief propagation,简称LBP [6])是团树信念传播方法的自然推广.从算法上看,LBP 与

团树算法的区别仅在于它放松了团树算法所要求的流动相交性这个性质,因此允许在有环图上执行算法.保留环路的结果,是从节点C i 到节点C j 关于X 变量的信息可能影响了C j 对Y 的信念,既而又传播回C i 并对其关于X 的信念造成反馈.这可能导致X 的信念无法收敛,或者收敛到错误的分布.

尽管环路信念传播的运行结果取决于具体模型及其参数,缺乏理论上好的保证,但在实际中其表现常常令

人满意.在编解码问题研究中,著名的Turbocode 解码算法就被证明与环路信念传播算法等价[15].

可以证明,在伊辛模型上直接运行环路信念传播算法,等价于求解原优化问题的一个近似[16]:目标函数等价

于优化Bethe 近似的能量函数,而约束条件仅要求割集变量的边缘分布一致.在环路图中,这并不保证联合分布的整体一致.

2.2.2 平均场近似

通过对可行域施加更多约束条件,平均场(mean field)算法简化优化目标函数,从另一个角度解决在类似伊

辛模型的高树宽模型中近似推理的问题.例如对于伊辛模型,原优化问题为

()()(,())sup M

A H p θμμθθμ∈=??+ (2) 其中,θ是模型参数;μ是对应的因子在该参数下的充分统计量的期望;M 称为边缘(概率)多面体剖分,是所有合理的边缘分布的集合;??,??为内积,H (?)是分布的熵函数,而p θ(μ)是充分统计量期望μ对应的模型参数θ所定义的分

布.平均场算法采用,?{:}u v u v

M μμμμ==替代实际可行域M ,这相当于在去掉原伊辛模型所有边连接的一类模型中,寻找伊辛模型的最佳近似.从而,其对应的熵函数化简为易于优化的形式:

()()(log (1)log(1))v v v v v V

H p θμμμμμ∈=?+??∑ (3)

新的优化问题对每个μv 分别是凹的,因此可以采用迭代地关于每个μv 进行优化的方法求解,得到μ的更新

方程为

()1

exp v v

u u u N v μθθμ∈=??????????∑ (4)

当算法收敛时,得到的μv 和A (θ)就是原问题解的平均场近似.

2.3 基于抽样方法的推理

当精确推理计算困难时,抽样方法提供了计算随机变量边缘(条件)分布和其他函数的另一种途径[17].抽样

方法的种类很多,包括拒绝性采样、重要性采样[18?20]、粒子滤波[21]、马尔可夫链蒙特卡罗(MCMC)[22,23]算法等.与变分推理方法不同,基于马尔可夫链的抽样推理方法在一定条件下,理论上能够渐近地收敛于真实分布;不仅如此,它还具有普遍的适用性.但对复杂的推理问题,马尔可夫链的混合时间通常无法估计,其实际效率也往往

2484

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

低于针对具体模型设计的变分优化推理算法.

2.3.1 拒绝性采样拒绝式采样意指与观测不一致的采样将被拒绝,它是贝叶斯网络中采样的最简单方法.考虑依条件概率分

布从图模型G 中抽样,则得到样本x 的概率为P (x ).若观测变量X e =x e ,查询变量X q ,则有: \{}()1[](|)()1[]q e e x X q e e e x P x X x P x x P x X x ===∑

∑ (5)

即在所有与观测一致的抽样中,查询变量X q =x q 的比例即其取值x q 的条件概率.注意到接受概率1[X e =x e ]关于观测变量的数目呈指数趋于0,因此,拒绝性采样不适用于连续变量以及有大量观测的模型.

2.3.2 重要性采样

重要性采样意指首先获得服从另一分布的样本,再根据重要性对样本加权,以使样本等效于来自目标分布.

考虑欲估计关于X 的函数f (X ),抽样分布q (X ),目标分布p (X ),则由 1()1()

(())()()d (), ()()M i

p i i i i i p X p X E f X f X q X X f X w w q X M q X ==≈=∑∫ (6)

可依分布q (x )抽样得到{X 1,…,X M },计算w i 进行重要性加权,即可得到E p (f (X ))的估计.对一般的图模型,往往只知道()(),()(),p q p

X p X Z q X q X Z == 而不知道其归一化常数.此时,可利用: ()()(())(), ()()q p p q q p q Z Z p X p X E f X E f X E Z q X Z q X ????==????????

, 得到: 11()()()()(())()()M q i i i p i q i p X E f X f X w q X E f X p X w E q X ==??????=≈??????

∑∑ (7) 其中,()()i i i p X w q X =

. 因此,同样可以从样本中获得关于目标分布的函数值估计.

在应用中,虽然只要求q (x )>0,x ∈{y :p (y )>0},但若q (x )与p (x )差别较大,估计的误差也往往较大.结合退火等

技术发展出的退火重要性采样(annealed importance sampling,简称AIS)可以减少估计误差.

似然度加权也是一种常用的图模型抽样算法.它可以看作重要性采样的一个特例.在似然度加权中,样本及

其权重按如下算法产生:

算法1. 似然度加权.

输入:观测集合(E ,x E ).

输出:样本x 以及重要性权值w .

(1) w ←1

(2) foreach 拓扑排序中的第i 个变量 do

(3) if i ∈E then

(4) X i ←x i

(5) w ←wp (x i |X π(i ))

(6) else

(7) 依X i ~p (X i |X N (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 抽样算法假定对任意变量X i ,我们可以从p (x i |x ?i )中抽样.算法的每一步依次选择一个变量,以其他变

量的当前值为条件,从该变量的条件分布中抽样更新其值.

Gibbs 抽样的优势在于算法简单,缺点在于一次只能更新一个变量,效率较低.改进的联锁(blocked)Gibbs 抽

样在每一步能够对相互条件独立的变量同时抽样.但当从p (x i |x ?i )中抽样比较困难时,Gibbs 抽样就不适用了. Gibbs 抽样可以看作下面介绍的Metropolis-Hastings 算法的一个特例.

? Metropolis-Hastings 算法

Metropolis-Hastings 算法具有更大的灵活性.它只假定我们可以产生遍历状态空间的马尔可夫链,并且能够

计算样本的生成概率和比较不同样本的似然比.我们可以为算法设计不同的建议分布(proposal distribution)Q ,通过控制接受概率(acceptance probability),使状态转移分布对目标分布满足细致平衡(detailed balance)性质.具体地,设Q (x →x ′)表示由状态转移函数从x 生成状态x ′的概率密度,A (x →x ′)表示状态转移x →x ′的接受概率,则由细致平衡原理有: ()()()()()()

A x x p x Q x x A x x p x Q x x ′′′→→=′′→→ (8) 取接受概率为()()()min 1,()()p x Q x x A x x p x Q x x ′′??→′→=??′→??

,即可使上式成立. 通常,我们希望建议分布Q 的选择能够使算法有较高的接受概率,同时又能较快而全面地探索状态空间的

不同区域.但实际中,算法的表现往往依赖于概率分布的复杂程度以及算法设计者对问题的理解.一些高级的MCMC 算法,例如推广的Swendsen-Wang 算法[24,25]以及Hamiltonian Monte Carlo [26]方法,针对不同的方面对基本算法进行了改进.

3 概率图模型的学习

对于复杂的、缺乏专家经验的概率模型,如果我们有一定数量的观测数据,通常希望能够从观测数据中获

得模型的参数甚至结构.这又分为几种不同的情况:贝叶斯网络或马尔可夫网络;所有变量都可观测的模型或只可观测部分变量的模型;结构已知的模型或结构未知的模型.不同的情况产生出一系列不同难度的问题.

在参数估计的不同准则中:一种常用的估计方法是最大似然估计(maximum likelihood estimation,简称

MLE),即在参数空间中寻找使观测数据的似然最大的参数;另一种称为最大后验(maximum a posteriori,简称MAP)的估计方法寻找参数空间中后验概率最大的参数.以下为叙述简单,我们只介绍最大似然估计的方法,对应的最大后验估计可通过相同方法导出.在有缺失数据的参数估计中,我们还将介绍视参数为潜在的随机变量,估计其后验分布的贝叶斯推断方法.

3.1 完全可观测模型的参数估计

由于已知的信息最多,完全可观测模型的学习问题是各类学习问题中最简单的.然而即使在这种情况下,贝

叶斯网络和马尔可夫网络的学习算法代价也有着本质的不同.我们将会看到:贝叶斯网络的参数估计问题是可分解的,因而容易求解;但是马尔可夫网络由于其因子缺少局部的归一化性质,由全局归一化常数带来的模型参数之间的耦合增大了学习的难度.

3.1.1 估计贝叶斯网络的参数

对于贝叶斯网络G ,记其变量集合为X ,参数为θ,观测样本为D ={X (1),…,X (N )},则似然函数为

2486

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

(

)()1(;)(|();)j N

i i j j j i X x L D p x u x θθ=∈=∏∏ (9)

最大化似然函数等价于最大化对数似然,即

()()1

max (;)max log (|();)j j N i i j j j X x i l D p x u x θθθθ∈==∑∑ (10) 由此可见,在完全可观测的贝叶斯网络中,最大似然参数估计问题可分解为对每个条件概率密度的参数估

计问题.

3.1.2 估计马尔可夫网络的参数

对于马尔可夫网络H ,一般研究一类称为对数线性模型(log-linear model)的模型比较方便.记其因子集合为

C ,参数为θ,对数线性模型的似然定义为 1(|)exp ()()T c c c p Z θθ?θ??=????

∑y y (11) 可以证明,完全可观测的对数线性模型的对数似然函数关于参数θ是凸的,因此可以采用梯度方法求解最

大似然估计问题.对数似然函数关于参数的偏导为 |()1()[()]c i y c i c l E N θθφφθ???=??????

∑y y (12) 其中,第1项可以从训练集的经验分布估计;第2项需要在当前模型中进行推理,对于低树宽的模型,可以采用精确推理的方法求得此项;而对于高树宽的模型,则需要采用上文介绍的近似推理方法.一种常用的方法是对模型中的目标变量进行抽样,以在抽样经验分布中的均值近似上式第2项,从而求得近似t 的梯度.对于大训练集,每次迭代求解上式第1项也有较大的时间开销,因此可以用小批训练样本(minibatch)诱导的分布近似整个训练集的经验分布求第1项.由于梯度下降第t 步与t +1步的参数一般差异不大,可以用第t 步的抽样初始化第t +1步的MCMC 算法,从而加快马尔可夫链的混合速度.随机最大似然方法综合了这些近似技巧.

另一种称为最大化伪似然的典型方法试图回避由归一化常数导致的参数估计的困难.该方法定义对数伪

似然为 ,11

1()log (|,)N D PL id i d i d l p y N θθ?===∑∑y (13) 修改参数估计的目标为最大化所有条件分布之积(又称组合似然).在新的目标函数下,可以与在贝叶斯网

络中类似地将参数估计问题分解为每个条件分布的参数估计问题.在高斯马尔可夫随机场中,最大伪似然与最大似然目标等价,然而这种等价性对一般模型并不成立.

算法2. 拟合MRF 的随机最大似然算法.

(1) 随机初始化权值θ

(2) k =0, η=1

(3) foreach 轮次 do

(4) foreach 大小为B 的小批训练样本 do

(5) foreach s =1:S do

(6) 抽样y s ,k ~p (y |θk ) (7) ,1

1?(())()S s k s E S φφ==∑y y (8) foreach 小批训练样本中的第i 个样本 do

(9) ?()(())ik i

E φφ=?g y y (10) 1k ik i B

B ∈=∑g g

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

(11) θk+1=θk?ηg k

(12) k=k+1

(13) 减小步长η

3.2 有缺失数据的参数估计

对于某一变量,数据缺失分为两种情况:部分训练样本的数据缺失以及数据完全缺失(隐变量).我们主要讨论模型含有隐变量的情况.在有缺失数据的情况下,即使对于贝叶斯网络,最大化数据集的似然函数的问题也不能分解成更小的问题.一般有如下两种参数估计的方法:

? 梯度上升算法是优化非线性目标函数的标准方法.算法迭代的每一步计算数据的似然关于模型参数的偏导,并在梯度方向上升.由于似然函数有界,算法将收敛于一个局部最优解.

? 期望-最大化算法(又称EM算法)是一种处理含有缺失数据的最大似然估计问题的专门方法.该方法的思路来源于两个较为简单的问题:给定模型真实参数和可观测变量,推理隐变量的分布,是标准的推理问题;给定可观测变量和隐变量的真实值,求最大似然参数估计,是标准的学习问题.基于以上想法,算法将求解最优参数的过程分解为交替进行的两个步骤:在“期望”步骤,我们根据模型参数的当前估计推理,求得隐变量的分布,以此获得(对数)似然函数关于隐变量分布的期望;在“最大化”步骤,我们求解最大化(对数)似然函数期望的模型参数,得到参数的新估计值.可以证明,每个步骤均能增大似然函数,因此,算法将收敛于一个局部最优解.

然而,与完全可观测模型的似然函数不同,在有隐变量的情况下,目标函数一般有多个局部极大值.为解决算法陷于局部极大值的问题,有时采用退火的方法,或者对训练数据加入扰动(pertubation).但是在实际中,依然无法保证算法能够找到最大似然估计的全局最优解.

对于部分训练样本缺失某变量数据的情形,还需要考虑数据缺失事件是随机发生的,还是与当前模型的其他变量有关:若为前者,则可以用对待隐变量的类似方法处理;若为后者,则需要做进一步的修正.

3.3 结构学习

从数据中推断变量之间的依赖关系(即图模型结构)的问题称为结构学习.结构学习可以用于发现变量之间的依赖关系,例如发现生物体不同基因表达的依赖关系.此外,通过结构学习获得数据的合理模型,还可以用来对数据做密度估计.具有稀疏性的结构有助于防止密度估计的过拟合问题.我们主要介绍贝叶斯网络的结构学习问题.马尔可夫网络的结构学习方法与之相近,可以参考文献[1]中第20章第7节的相关内容.

贝叶斯网络结构学习的方法大体可分为3类,下面分别进行介绍.

3.3.1 基于约束的方法

若数据产生于某真实模型G*,则对于G*中条件独立的变量(集合),在训练数据中也应当近似条件独立;相反,若G*完整地反映了数据的条件独立关系,则G*中条件依赖的变量在训练数据中也很可能是条件依赖的.这构成了基于约束的方法的依据.具体说来,在关于变量间条件独立性的统计测试基础上,该方法对训练数据集进行一系列的条件独立性查询.在一定的假设下[1],该方法能够使用多项式个关于有限多变量的条件独立性查询找到最优的图模型结构.

3.3.2 基于得分的方法

基于得分的方法将结构学习问题转化为最优化问题处理.该方法定义某种得分函数,根据训练样本为每一种候选结构打分,搜索得分较高的结构.选择得分函数时,我们首先可能会想到采用似然函数——例如对于图模型G,首先对参数做最大似然估计,用数据集的对数似然作为G的得分.然而,这种称为似然得分的方法会导致过拟合——一般来说,复杂的模型将获得更高的得分.

贝叶斯得分能够有效地避免过拟合训练数据的问题.该得分函数采用模型G,以证据x为条件的后验概率作为G的得分,为此,需要指定关于模型结构G和参数θG的先验分布,并对参数的所有取值求积分.因此,这一得分只在具有特定分布的简单模型上适用.

2488

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

贝叶斯信息准则(Bayesian information criterions,简称BIC)得分是贝叶斯得分的一种简化和近似,可以避免

计算对模型参数空间的多重积分.可以证明,若假设贝叶斯网络的变量都是离散的,且采用Dirichlet 分布作为参数的先验分布,则随着样本数量趋向无穷,BIC 得分: log ?(:)(:)[]2

BIC g M score G D l D Dim G θ=? (14) 与贝叶斯得分之差将趋向于一个常数.BIC 得分还具有统计一致性,即随着样本数量趋向无穷,真实的模型结构(以及与其有等价条件独立性质的结构)将获得最大的BIC 得分.

选定了打分规则,还需要解决搜索得分较高的图模型结构的问题.对于树结构的图模型,有O (n 2)时间的算

法找到最优树结构;对于给定了序关系的变量集合,找到最优结构的计算复杂度大致是图模型节点最大入度的指数;对于一般的图模型,则问题常常是NP-难的,一般采用启发式的方法近似求解.一种常用的称为爬山(hill-climbing)法的方法,通过反复试探增边、删边、逆转边的方向等基本操作,寻找具有更高得分的结构.

3.3.3 贝叶斯模型平均

如上所述,当训练样本趋于无穷时,模型的后验概率将集中于真实模型和它的等价模型;然而,当训练样本

较少时,模型结构的后验分布往往并不集中.这时,使用最大后验的模型来代表我们对模型后验的估计就未必合适了.我们可以采用MCMC 方法,构造在不同结构的图模型之间转换的马尔可夫链,设计Metropolis-Hastings 算法的接受概率,使其平稳分布恰好是模型结构的后验分布,利用马尔可夫链抽样的经验分布估计模型结构.

4 代表模型

本节中,我们将介绍两类在近10年中有较大学术影响且获得广泛应用的概率图模型:

? 条件随机场[27]是马尔可夫随机场的一种变体,其相对于马尔可夫随机场的优势在于不需要对输入进

行建模,可以综合各种特征、打分函数,因此能够方便地与特征提取、检测器、分类器等输出的中间结

果结合起来.

? 主题模型[28]是一类文档聚类和文本分析的概率模型.它提出了更合理的模型假设,弥补了传统聚类方

法的种种不足,提供了更精细的分析结果,且有有效的近似推理算法.

4.1 条件随机场

条件随机场(conditional random field,简称CRF)是一类判别式概率图模型,在句法分析和计算机视觉等问

题中有广泛的应用.具体来说,条件随机场是一种所有的势函数都以输入特征为条件的马尔可夫随机场: 1(|,)(|,)(,)c c c

p Z ψ=∏y x w y x w x w (15) 通常,我们假设势函数关于输入特征有对数线性的表示:

(

|,)exp((,))T c c c c ψφ=y x w w x y (16) 其中,?(x ,y c )是关于输入x 和标签y c 的特征向量.由此可以写出条件随机场的对数似然函数:

1()(,)log (,)T c c i i i i c l Z N φ???????

∑∑ w w y x w x (17) 以及梯度: 1[(,)[(,)]]c i i c i i

c l E N φφ?=??∑y x y x w (18) 注意到E [?c (y ,x i )]依赖于第i 个训练样本,因此在采用梯度方法训练的每一步,针对每一个训练样本都需要

在模型中进行推断.这一特点使得对于大小为N 的训练集,条件随机场的训练时间比马尔可夫随机场要大一个O (N )的因子.然而,这也为条件随机场带来不可替代的优势:因子以输入为条件(而不是包含输入),意味着我们可以向模型中加入全局特征,而不必担心变量相互耦合导致的推理困难.

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

2489

4.2 主题模型主题模型是一类生成式的贝叶斯模型,在文本分析、社交网络分析、计算机视觉等问题中有广泛的应用.

如图6所示,变分推断的目标是选择合适的变分参数,,,i il

q B π 使得图6(b)中πi ,q il ,B 的分布尽可能接近图6(a)中对应变量的后验分布.这里,我们从文本分析的角度介绍主题模型.假设语料库由K 个主题组成,每篇文档的内容是不同主题的混合,用K 项分布πi 表示.每个主题对应一个该主题的词库,b k 表示第k 个主题词库产生不同词汇的概率分布.文档的生成过程由算法3来描述.

算法3. 主题模型的文本生成方法.

输入:超参数α,γ,K ,V ,N ;

输出:文本语料库.

(1) for 第k ∈[1,…,K ]个主题 do

(2) 抽样词汇的概率分布b k |γ~Dir (γ1V )

(3) for 第i ∈[1,…,D ]篇文档 do

(4) 抽样第i 篇文档的主题分布πi |α~Dir (α1K )

(5) for 第l ∈[1,…,N i ]个单词 do

(6) 抽样该单词的主题q il |πi ~Cat (πi )

(7) 抽样单词y il |q il =k ,B ~Cat (b k )

Fig.6

图6

4.2.1 主题模型的推理

? (坍塌的)Gibbs 抽样[29]

我们从朴素的LDA 的Gibbs 抽样算法开始.首先,我们可以写出所有变量的完全条件分布: ,(|)exp[log log ]il ik k x il p q k b π=?∝+ (19)

(|)()i k il l p Dir I z k πα?????=+=?????

???∑ (20)

(|)(,)k v il il i l p b Dir I x v z k γ?????=+==?????

???∑∑ (21)

然而,由于πi 和b k 都服从狄利克雷(Dirichlet)分布,我们可以积分消去这些变量,导出坍塌的Gibbs 抽样(collapsed Gibbs sampling)[29,30]:

,,,,(|,,,)v k i k i l i l k i c c p q k c V L K γγα

αγα????++=∝++q y (22)

其中,记v =y il 表示第i 篇文档的第l 个单词,,v k c ?表示除文档i 的第l 个单词外所有被归入主题k 的语料库单词v

的数目,,i k c ?表示除文档i 的第l 个单词外所有被归入主题k 的文档i 的单词的数目,k c ?表示除文档i 的第l 个单

(a) 主题模型 (b) 主题模型的变分近似

2490 Journal of Software 软件学报 V ol.24, No.11, November 2013

词外所有被归入主题k 的单词的数目,而L i 表示第i 个文档的单词总数.该公式有直观的含义:文档i 的第l 个单词被归入主题k 的概率正比于该单词在主题k 中产生的概率(第1项)以及该主题在文档中使用的概率(第2项).

基于公式(22),我们可以实现坍塌的Gibbs 抽样算法(算法4).

算法4. 坍塌的Gibbs 抽样.

输入:文本语料库.

输出:文本语料库q il .

(1) 初始化:随机为每个单词指定一个主题q il ∈{1,…,K }

(2) for 第i ∈[1,…,D ]篇文档 do

(3) for 第l ∈[1,…,N i ]个单词 do

(4) 统计,,,v k i k k c c c ???和

(5) 按照公式(22)抽样该单词的主题q il

? 批量变分推断[28]

由于后验分布不易直接求解,可以采用变分推断方法,从一类独立性更强的图模型中寻找原模型的最优近

似.最简单的变分推断使用平均场近似,即假设待推断变量的联合后验分布可以完全因子化:

(,,)(|)(|,)(|)i i i iv iv iv k k

v k q c B B Mul c n c Dir b b πππ????=∏

∏ (23) 在这种假设下,我们最小化泛函q (πi ,c i ,B )与目标分布的KL-散度,将得到如下更新规则:

ik k iv ivk v n c πα=+∑ (24)

exp([log ][log ])ivk vk ik c E b E π∝+ (25) vk v ivk

i b c γ=+∑

(26) 由公式(24),我们得到批量变分推断的更新算法(算法5、算法6).

算法5. LDA 的批量变分近似推理.

输入:超参数αk ,γv ,K ,词汇统计n iv .

输出:πik ,c ivk ,b vk .

(1) 使用多项分布混合模型的EM 方法估计vk

b 的值 (2) 初始化计数n iv

(3) while 未收敛 do

(4) s vk =0

(5) for 第i ∈[1,…,D ]篇文档 do

(6) (,)(,,)i i i

c Estep n B πα= (7) vk vk iv ivk s s n c

=+ (8) for 第k ∈[1,…,K ]个主题 do

(9) vk v vk

b s γ=+ 算法6. (,,).i Estep n B

α 输入:超参数αk ,γv ,K ,词汇统计n iv .

输出:πik ,c ivk ,b vk .

(1) 初始化ik k π

α= (2) repeat

(3) ,old i i ik k ππ

πα??== (4) foreach 单词v ∈{1,…,V } do

(5) foreach 主题k ∈{1,…,K } do

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

2491

(6) exp(()())old ivk k v k i c b ψψπ??=+ (7) 归一化iv c

? (8) ik ik iv ivk n c π

π=+ (9) until 1||old ik ik k thresh K

ππ?<∑ ? 在线变分推断[31]

注意到在批量变分推断中,求期望的步骤需要遍历所有N 个文档,在文档集很大的情形下,这将花费太多的

时间.利用随机梯度下降的方法,在每次迭代中我们可以使用1个或数个数据的期望充分统计量代替整个数据集上的期望充分统计量,然后在最大化步骤中对B 的变分参数做部分更新.这样,就得到了LDA 的在线变分推断算法.

算法7. LDA 的在线变分近似推理.

输入:超参数αk ,γv ,K ,词汇统计n iv ,τ0,κ.

(1) 随机初始化vk

b (2) for t =1:∞ do

(3) 步长ρt =(τ0+t )?κ

(4) 选择小批文档i =i (t )

(5) (,)(,,)i i i

c Estep n B πα= (6) new vk

v iv ivk b Nn c ρ=+

(7) (1)new vk t vk t vk b b b ρρ=?+ 5 近似推理的加速

随着互联网、传感器网络等大规模应用的兴起,图模型的推理问题规模也迅速扩大.在这一类大规模图模

型应用中,如何迅速而有效地对图模型执行近似推理,是我们关心的核心问题.针对这一问题,目前的方法主要结合以下几种解决途径:设计好的消息传递调度方法,利用多核硬件实现并行和分布式推理,针对查询变量有选择地执行推理.

5.1 消息传递调度

设计消息更新调度是一种有效且广泛使用的提高信念传播计算效率的方法.在标准的环路信念传播中,每

次迭代将重新计算和更新所有的消息.然而多数情况下,只有少数消息在相继的两次更新中有较大变化,而大多数的消息更新几乎不改变计算结果,因此浪费了计算资源.

? 残余信念传播

Elidan [32]提出了一种称为残余信念传播(residual belief propagation)的消息更新调度算法.该算法的更新规

则是:每次只更新在标准环路信念传播算法的消息更新中改变最大的那个消息.

具体来说,残余信念传播算法为因子图的每个边记录两个消息:一个是当前消息();t j αν?一个是新消息,即给

定所有其他当前消息时信念传播的更新结果:

\()()()\\?()log (,)exp (()())i t t t i i i i j j j X j i x X x x x ααααααΓνψ?ν??∈??=??????

?∑∑

(27) 新消息与当前消息之间的差异称为残余r α?i : ()()||||t t i i i r ααανν???≡? (28)

在第t +1轮迭代,算法只更新有最大残余的消息.换言之,

2492

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

()(1)()()?, ()arg max , t i i t i E i t i i r ααααανανν??+?∈????=?=???其他情况

(29) 在更新να?i 后,只有与i 直接相关的因子β∈Γi 发送的新消息(1)?t j βν+?需要重新计算.算法伪代码如下:

算法8. 残余信念传播.

输入:G =({X ,F },T ).

(1) 定义优先队列M

(2) foreach (α?i )∈T do

(3) 初始化消息να?i

(4) foreach (α?i )∈T do

(5) 根据公式(27)、公式(28)计算?,i i r ααν

?? (6) 令边(α?i )在M 中的优先权为r α?i ,将(α?i )加入M

(7) while 消息未收敛 do

(8) 记M 的堆顶(α?i )

(9) 令να?i 为?i αν

? (10) 令(α?i )在M 中的优先权为0

(11) foreach β∈Γi \α do

(12) foreach j ∈Γβ\i do

(13) 根据公式(27)、公式(28)重新计算?,j j r ββν

?? (14) 令边(β?i )在M 中的优先权为r β?i

(15) 由公式()

()exp ()i

i i P x x ιααΓν?∈∝∑ 计算变量x ∈X 的边缘分步()P x (16) 返回()P x 直观上,残余信念传播总是更新最大残余的消息,因此,每单位计算量所获得的消息改变更多,从而在信念

空间中能够更快地趋向不动点.

5.2 并行和分布式推理

信念传播算法由于消息传递的局部性,自然适合于在多核机器上并行实现.然而,同步的并行信念传播算法

并不高效.Gonzalez 等人[33]提出的残余飞溅信念传播(residual splash belief propagation)算法是一种异步的信念传播方法.它通过设计消息更新顺序、合理分布计算任务,能够减少无用的计算,在多核机器上获得明显的性能提升.算法名称中的“飞溅”一词是对算法运行过程的直观描述:在算法运行过程中,消息更新总是在以某个顶点(称为根)为中心的一定直径的子图上进行,且消息首先由叶节点向根传播,再由根节点传向叶子,如同水面上溅起水花的过程.

该算法的设计受到了以下两点的启发:首先,在同一路径上变量之间的影响随着距离增大而减小,因而,为

了获得较为精确的近似,常常只需要考虑顶点周围的子图;其次,对于一个树状图模型,尽管容易设计同步的并行信念传播算法,但是对每个顶点而言,使得算法收敛的消息却要在其接受到其余邻居顶点的消息之后才能形成,因此在此之前的消息传递实际上都浪费了.于是,算法设计使得每个机器独自处理一个由宽度优先搜索生成的树状子图,对该子图采用串行的和-积算法执行推理(称为飞溅操作).在飞溅操作结束后,树状子图的内部将被标定,没有残余的消息;消息残余只存在于子图的叶节点.之后再分配机器对残余的消息执行飞溅操作,直到所有顶点有关的最大残余消息都小于某一阈值.若信念传播算法能够收敛于不动点,则某时刻消息与不动点的距离和残余消息同阶,因此,算法终止时能够获得较好的近似结果.

算法的主要伪代码参见算法9.

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

2493

算法9. 残余飞溅信念传播算法. 输入:飞溅操作的树深h ,残余消息阈值β.

(1) 初始化顶点优先队列Q

(2) 令所有消息残余为∞

(3) forall 处理器 in parallel

(4) while Q 中最大残余消息大于β do

(5) 记堆顶的顶点为v ,弹出堆顶

(6) 飞溅(v ,h )

(7) foreach 飞溅操作影响的顶点u do

(8) 在Q 中更新u 的消息残余

(9) 将(v ,v 的消息残余)推入堆Q

算法10. 飞溅(v ,h ).

输入:飞溅操作的树深h ,顶点v .

(1) 构造以v 为起点,深度为h 的广度优先搜索序(bfs-order)

(2) foreach i ∈逆bfs-order do

(3) 向v 的方向传递消息

(4) foreach i ∈bfs-order do

(5) 向背离v 的方向传递消息

5.3 针对查询的推理

在实际的应用中,我们常常并不关心所有变量的取值,而只求能够获得感兴趣的变量,即查询变量的条件分

布.因此,如果信念传播中的消息更新与我们的查询变量没有关系或者只存在微弱联系,那么所做的计算在我们看来就是浪费了.针对查询的推理,就是研究如何利用图模型的结构和变量依赖关系对查询变量进行有针对性的近似推理,以加快推理速度,适应大规模图模型推理的需求.

? 针对查询的信念传播

针对查询的信念传播目标就在于估计信念传播消息更新对于查询变量的分布的影响,只更新对查询变量

分布影响较大的消息,从而改善查询变量分布的计算效率[34].

具体来说,我们记因子图模型为G =({X ,F },T ),查询变量为q ≡i k ,一条影响查询变量的消息传播路径为

π=(β1→i 1→…→βk →q ).若固定所有不在路径π中的消息ν?π,应用环路信念传播的更新规则,则k

q βν?可以表示为11i βν?的函数11(,).i F πβπνν??因此,我们可以写出k q β

ν?关于11i βν?的变化的敏感性: 1111

11d d k k d d

k i i d q q i F ββπβββπννννν++???=??????≡=???∏ (30) 利用不等式放缩,我们可以得到如下关于11i βν?的变化对k q β

ν?的影响的界: 111111|||||||||sup d d k d d k i q i d i πββπβνβνΔνΔνν++?????=????∏≤ (31)

为此,定义一个有向路径π=(β1→i 1→…→βk →q )的敏感强度为 1111()sup

d d d d k i d i sensitivity πβνβνπν++???=??=?∏ (32)

其中,最大值的计算复杂度取决于范数的选择.利用Mooij 和Kappen [35]的结果,若取范数为对数动态范围,则公式(32)中的最大值可以解析地求出.为衡量消息α?i 对于查询变量x q 的影响,理论上需要考虑所有从α?i 指向q 的有向路径.然而,由于环路的存在,这样的路径有无穷多条,计算它们的影响之和是困难的.为此,我们可以采用对查询变量影响最大的路径来近似代替所有路径的影响.定义α?i 的最大敏感重要性值为

2494

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

(,)max (,)max ()i q sensitivity i q sensitivity πααπ∈???≡∏ (33)

其中,(,)i q α?∏是由所有从α?i 指向q 的有向路径组成的集合. 注意到[0,1)sup i j

ανβνν???∈?,因此,计算最大敏感重要性值的问题与计算最短路径问题一样具有贪心最优性质.因此,仿照求最短路径的Dijkstra 算法,我们可以得到计算边的重要性值的算法.

算法11. 计算边重要性.

输入:因子图G =({X ,F },T ),查询Q ∈X .

(1) 定义优先队列L =?,边的优先权ρα?i

(2) foreach (α?i )∈T do

(3) 令(α?i )的优先权为1, , i i Q αρ?∈?=??如果0其他

(4) 将(α?i )加入优先队列L

(5) while L ≠? do

(6) 记L 的堆顶为(α?i )

(7) 令w α?i 为ρα?i ,删除L 的堆顶元素(α?i )

(8) foreach β∈Γi \α do

(9) foreach j ∈Γβ\i do

(10) if (β?j )∈L then

(11) 令ρβ?j 为max ,sup i j i j αβανβνρρν??????????????

(12) 根据新的优先权维护优先队列L (13) 返回W ={w α?i |(α?i )∈T }——所有边的重要性值

有了算法11,对残余信念传播稍做修改,即可得到针对查询的信念传播算法(算法12).

算法12. 针对查询的信念传播.

输入:因子图G =({X ,F },T ),查询Q ∈X ;

(1) 定义优先队列M

(2) 令W 为算法11的返回值

(3) foreach (α?i )∈T do

(4) 初始化消息να?i

(5) foreach (α?i )∈T do

(6) 根据公式(27)、公式(28)计算?,i i r ααν

?? (7) 令边(α?i )在M 中的优先权为w α?i ×r α?i ,将(α?i )加入M

(8) while 消息未收敛 do

(9) 记M 的堆顶(α?i )

(10) 令να?i 为?i αν

? (11) 令(α?i )在M 中的优先权为0

(12) foreach β∈Γi \α do

(13) foreach j ∈Γβ\i do

(14) 根据公式(27)、公式(28)重新计算?,j j r ββν

?? (15) 令边(β?i )在M 中的优先权为r β?i

(16) 计算查询变量x ∈Q 的边缘分步()P

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

2495

(17) 返回()P

x ? 查询敏感的MCMC

考虑由以下两个步骤诱导的提议分布:

(1) 从当前状态开始,依定义于变量下标(1,2,...,n )上的分布p 抽样,选择一个变量x i ∈x ;

(2) 从某个定义在x i 值域上的分布q (X i )抽样x i 的新值,固定其余变量的值不变,返回新状态s ′.

简而言之,这一提议分布每次由当前状态s 更新一个变量的值得到新状态s ′.在传统的MCMC 推理中,我们

感兴趣的是所有变量的边缘分布,变量更新抽样通常采用固定的顺序,或者由1()p i n

=诱导的顺序.针对这类提议分布,Wick 和McCallum [36]提出了一种查询敏感的MCMC 算法.该算法的关键在于,注意到图模型的变量并非

对查询变量有相同的影响:查询变量的取值与某些变量的值有强依赖关系;而与另一些变量仅有微弱的依赖关系,甚至不相关.因此,一种更好的提议分布应当更频繁地抽样与查询变量依赖性强的变量.为此,可以定义变量间的影响的概念.设x 和y 是两个随机变量,其联合分布和边缘分布分别为π(x ,y ),π(x ),π(y ).令f (π1(?),π2(?)) r , r ∈R +为概率分布的散度,因而是实值、非负的.定义x 和y 的影响ι(x ,y )为

ι(x ,y )≡f (π(x ,y ),π(x )π(y )) (34) 取f 为总变差范数,得到ιtv (x ,y )≡P ||π(x ,y )?π(x )π(y )P tv ||.

然而,对于图模型中的任意两个变量,精确计算ιtv 需要在图模型上推理.为此,文献[36]进一步提出了影响路

径得分的概念.对于一条从查询变量x 0=x q 到任意变量x s =x s 的有效路径ρ=(x 0,x 1,…,x r ),设φ(x i ,x j )是由包含x i ,x j 的因子所定义的关于x i ,x j 的联合分布,作为真实的联合分布的近似,而φ(x i ),φ(x j )为其边缘分布,则有效路径ρ的影响路径得分为

111(,)((,),()())r q s i i i i i i i i x x f x x x x ρτφφφ?++=≡∏ (35)

令p (i )∝τρ(x q ,x i ),即得到查询敏感的提议分布.

对应的Metropolis-Hastings 算法称为查询敏感的MCMC(QAM). 6 未来工作研究与展望

概率图模型作为描述和处理具有条件独立结构的概率模型的一般框架,其研究在近年来已经取得了长足

的进展,获得了来自领域内外的持续关注,催生了丰富的应用.本文介绍了概率图模型的表示、推理和学习问题及主要进展,比较了不同的推理和学习算法的适用范围和执行的复杂度,简要介绍了近年来较为重要的两类概率图模型以及推理问题的最新研究进展.

从本文的介绍中可以看出:尽管在一般意义下概率图模型的推理是困难的,但是仍然有相当一部分模型和

推理算法能够在我们所关心的应用中取得较好的效果.然而,概率图模型的研究中还有许多问题值得在今后进一步探索:

(1) 概率图模型的表示

通常情况下,我们仍然需要针对具体问题设计特定的概率图模型.在设计中既要对所处理的问题中变量的

依赖关系做出合理抽象,又要权衡模型的推理代价或近似推理的难度,以在实际应用中获得推理精度和推理效率的折中.许多经典的图模型即反映出这种折中的理念.然而,一方面由于新的应用问题不断出现,另一方面由于从精确推理到近似推理、批量学习到在线学习有一系列可选的折中方案,可以期待新的概率图模型设计将会不断涌现.例如,为解决LDA 模型需要事先指定主题数量的问题,诞生出一系列基于贝叶斯非参数统计的模型.

(2) 概率图模型的学习和推理

大规模概率图模型的有效推理方法.目前,概率图模型应用规模逐渐扩大,例如Google Scholar 等学术搜索

应用需要识别区分同名作者,可考虑建立关于学术研究作者及其发表论文的概率模型,而这样的模型中随机变量的规模可达到百万量级.在大规模问题中,利用单机CPU 和传统推理方法进行的推理将因效率过低而失去实

机器学习 —— 概率图模型(推理：决策)

Koller 教授把决策作为一种单独的模块进行讲解，但我认为，决策和推理本质上是一样的，都是在假设已知CPD或者势函数的情况下对模型给出结论。 1、决策==逐利决策的基本思想很intuitive，并且非常有用。在赌博行为中，最后获得的钱与硬币的正反，赌注的大小有关。硬币的正反显然是随机变量，而赌注的大小却是决策量。显而易见的是，决策的最终目的是使得某个期望最大化。再举一个视觉中的例子，对于双目配准算法而言，左相机对应右相机的像素可以认为是随机变量。但是否将两个像素配在一起却可以认为是一个决策（假设像素一一对应，如果甲配了乙就不能配丙了，希望配准的最终结果是尽可能正确的）。故决策的数学表达为：其中，P(X|A)表示在给定决策下，随机变量X的概率。U(x,a)表示给定决策下，x发生所获得的收益。简单的决策如图所示：

2、决策的方法显然从上面的分析可知，我们要做的决策就是使得期望最大化的那个。换一个角度来看，如果每次的决策都是未知的，决策取决于已知信息，决策影响最终结果，如果决策也是随机变量，我们应该把获利最多的那个决策组作为我们所需采取的决策库。换而言之，凡事应有a,b,c三策，不同的策略对应不同的情况。显然，我们所需要采取的策略取决于已知的信息（Action的父节点）。而策略组本身就是一个随机变量。如图所示，如果变量真实值无法观测，只能通过一个传感器（survey）来进行推测时，决策应该取决于S的值。S的值又和其所有父节点（M）的值相关。MEU表示所选择的策略。

显然，我们需要P(S)deta(F|S)U(F,M)，然后P(S)需要对P(M,S)进行边际获得。故表达式如上。带入数据发现

概率图模型研究进展综述

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/15304200.html, Journal of Software,2013,24(11):2476?2497 [doi: 10.3724/SP.J.1001.2013.04486] https://www.wendangku.net/doc/15304200.html, +86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax: ? 概率图模型研究进展综述张宏毅1,2, 王立威1,2, 陈瑜希1,2 1(机器感知与智能教育部重点实验室(北京大学),北京 100871) 2(北京大学信息科学技术学院智能科学系,北京 100871) 通讯作者: 张宏毅, E-mail: hongyi.zhang.pku@https://www.wendangku.net/doc/15304200.html, 摘要: 概率图模型作为一类有力的工具,能够简洁地表示复杂的概率分布,有效地(近似)计算边缘分布和条件分布,方便地学习概率模型中的参数和超参数.因此,它作为一种处理不确定性的形式化方法,被广泛应用于需要进行自动的概率推理的场合,例如计算机视觉、自然语言处理.回顾了有关概率图模型的表示、推理和学习的基本概念和主要结果,并详细介绍了这些方法在两种重要的概率模型中的应用.还回顾了在加速经典近似推理算法方面的新进展.最后讨论了相关方向的研究前景. 关键词: 概率图模型;概率推理;机器学习中图法分类号: TP181文献标识码: A 中文引用格式: 张宏毅,王立威,陈瑜希.概率图模型研究进展综述.软件学报,2013,24(11):2476?2497.https://www.wendangku.net/doc/15304200.html,/ 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).https://www.wendangku.net/doc/15304200.html,/1000-9825/4486.htm Research Progress of Probabilistic Graphical Models: A Survey ZHANG Hong-Yi1,2, WANG Li-Wei1,2, CHEN Yu-Xi1,2 1(Key Laboratory of 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: hongyi.zhang.pku@https://www.wendangku.net/doc/15304200.html, 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

概率图模型中的推断

概率图模型中的推断王泉中国科学院大学网络空间安全学院 2016年11月

?推断问题回顾 ?精确推断：信念传播 –信念传播算法回顾 –信念传播在HMM中的应用?近似推断：吉布斯采样–吉布斯采样算法回顾 –吉布斯采样在LDA中的应用

?已知联合概率分布 P x 1,?,x n ，估计 –x Q 问题变量；x E 证据变量；x Q ∪x E =x 1,?,x n P R =1 P R =0 0 P R =1G =1= ? P B =0.001 P E =0.002 P A B ,E =0.95 P A B ,?E =0.94 P A ?B ,E =0.29 P A ?B ,?E =0.001 P J A =0.9 P J ?A =0.05 P M A =0.7 P M ?A =0.01 P B =1E =0,J =1=? P x Q x E =x Q ,x E x E

?已知联合概率分布 P x 1,?,x n ，估计 –x Q 问题变量；x E 证据变量；x Q ∪x E =x 1,?,x n P x Q x E =x Q ,x E x E 观测图片 y i 原始图片 x i y ?=argmax P y x 朴素贝叶斯 x ?=argmax P x y 图像去噪

?精确推断：计算P x Q x E的精确值 –变量消去 (variable elimination) –信念传播 (belief propagation) –计算复杂度随着极大团规模的增长呈指数增长，适用范围有限?近似推断：在较低的时间复杂度下获得原问题的近似解–前向采样 (forward sampling) –吉布斯采样 (Gibbs sampling) –通过采样一组服从特定分布的样本，来近似原始分布，适用范围更广，可操作性更强

读懂概率图模型：你需要从基本概念和参数估计开始

读懂概率图模型：你需要从基本概念和参数估计开始选自statsbot作者：Prasoon Goyal机器之心编译参与：Panda 概率图模型是人工智能领域内一大主要研究方向。近日，Statsbot 团队邀请数据科学家Prasoon Goyal 在其博客上分两部分发表了一篇有关概率图模型的基础性介绍文章。文章从基础的概念开始谈起，并加入了基础的应用示例来帮助初学者理解概率图模型的实用价值。机器之心对该文章进行了编译介绍。第一部分：基本术语和问题设定机器学习领域内很多常见问题都涉及到对彼此相互独立的孤立数据点进行分类。比如：预测给定图像中是否包含汽车或狗，或预测图像中的手写字符是0 到9 中的哪一个。事实证明，很多问题都不在上述范围内。比如说，给定一个句子「I like machine learning」，然后标注每个词的词性（名词、代词、动词、形容词等）。正如这个简单例子所表现出的那样：我们不能通过单独处理每个词来解决这个任务——「learning」根据上下文的情况既可以是名词，也可以是动词。这个任务对很多关于文本的更为复杂的任务非常重要，比如从一种语言到另一种语言的翻译、文本转语音等。使用标准的分类模型来处理这些问题并没有什么显而易见

的方法。概率图模型（PGM/probabilistic graphical model）是一种用于学习这些带有依赖（dependency）的模型的强大框架。这篇文章是Statsbot 团队邀请数据科学家Prasoon Goyal 为这一框架编写的一份教程。在探讨如何将概率图模型用于机器学习问题之前，我们需要先理解PGM 框架。概率图模型（或简称图模型）在形式上是由图结构组成的。图的每个节点（node）都关联了一个随机变量，而图的边（edge）则被用于编码这些随机变量之间的关系。根据图是有向的还是无向的，我们可以将图的模式分为两大类——贝叶斯网络（?Bayesian network）和马尔可夫网络（Markov networks）。贝叶斯网络：有向图模型贝叶斯网络的一个典型案例是所谓的「学生网络（student network）」，它看起来像是这样：这个图描述了某个学生注册某个大学课程的设定。该图中有5 个随机变量：课程的难度（Difficulty）：可取两个值，0 表示低难度，1 表示高难度学生的智力水平（Intelligence）：可取两个值，0 表示不聪明，1 表示聪明学生的评级（Grade）：可取三个值，1 表示差，2 表示中，3 表示优

索洛模型应用

网游中的索洛增长模型摘要网游是游戏的一种，但其仍有极其符合科学的经济学系统，或者说正是由于网游有着科学的经济体系，游戏才能毫无差错的运营下去，虽然其中参杂了运营商盈利的目的。有人说：生活是一面镜子。有了现实中的经济学这门镜子，我们才能认清网游中打怪升级的本质，才能不一昧沉迷于它。理性的看待任何问题，我想这是经济学给我们带来的启示。关键词：网游，索洛增长模型引言自从2001年的“传奇”以来，网游行业迅速发展。直至如今，已经形成了可谓之百花齐放的盛况。而网游的本质，是玩家与玩家之间的互动。常言道：有人的地方就有经济学。网游作为一个人与人之间的社交平台，必定也存在着各类的经济学现象。现象虽然各不相同，但究其本质，却毫无例外。现在，我将来探讨一下网络游戏中的索洛增长模型。网游中的索洛增长模型首先来讨论一个较为简单的情况，假设有一个网游，名字为A。在我们的假设中，我们先将其设定为一个封闭且固定的游戏，即玩家或其他外部力量不能对其进行经济上干预（如点卡充值等）且玩家不会升级且没有新玩家加入的游戏（类似于课本中的封闭模型）。其次，定义网络游戏中的几个行为。众所周知，网游中没有类似于工作的行为，玩家获得金币（即货币）的手段暂定为刷怪，即收入源自于刷怪。而刷怪中所获得的收益又可以分为两部分，其一，玩家刷怪时付出的肉体和精神上的劳动，与我们所学公式中的L相对应；其二，玩家刷怪所持装备和自身技能对于刷怪所付出的劳动，对应我们所学公式中的K。当玩家刷怪完后，玩家会获得自己金币上的收入，对应我们所学公式中的Y。对于这部分收入，玩家将有两个选择，储蓄与消费，分别对应我们所学公式中的S与C。储蓄即为将所得金币购买装备或暂时不用，消费即为将金币用于购买消耗性物品或者用于其他娱乐项目，这其中，用于购买装备所花费的资金我们称之为投资，用于对应公式中的I。在大部分网游中，对于装备都有一个耐久度的设定，即装备在用到一定次数之后就会损毁，此时只能对其进行维修或者购置新的装备，总之得花钱。而耐久度这一参数衍生出来的折损率我们对应公式中的&。在介绍完了各个参数之后，对他们进行分析。由于我们分析的是该网游总体的经济状况，因此我们将以上参数全部转化为人均值，即y,k,s,c,i.于是依照书上的公式，我们最后可以得出结论，在 sf(k)=&k 时，玩家的k达到最大。上面的公式得出的结论：当玩家刷怪刷到一定程度，装备发展到一个适当的阶段时，玩家将不再能进行装备更新。因为根据公式，在L不变时，这个阶段的I与&k是相等的。

经管类文献综述的写法及范文

文献综述的写法及范文文献综述是对某一方面的专题搜集大量情报资料后经综合分析而写成的一种学术论文，它是科学文献的一种。文献综述是反映当前某一领域中某分支学科或重要专题的最新进展、学术见解和建议的它往往能反映出有关问题的新动态、新趋势、新水平、新原理和新技术等等。要求同学们学写综述，至少有以下好处： ①通过搜集文献资料过程，可进一步熟悉科学文献的查找方法和资料的积累方法；在查找的过程中同时也扩大了知识面； ②查找文献资料、写文献综述是科研选题及进行科研的第一步，因此学习文献综述的撰写也是为今后科研活动打基础的过程； ③通过综述的写作过程，能提高归纳、分析、综合能力，有利于独立工作能力和科研能力的提高； ④文献综述选题范围广，题目可大可小，可难可易。对于毕业设计的课题综述，则要结合课题的性质进行书写。文献综述与“读书报告”、“文献复习”、“研究进展”等有相似的地方，它们都是从某一方面的专题研究论文或报告中归纳出来的。但是，文献综述既不象“读书报告”、“文献复习”那样，单纯把一级文献客观地归纳报告，也不象“研究进展”那样只讲科学进程，其特点是“综”，“综”是要求对文献资料进行综合分析、归纳整理，使材料更精练明确、更有逻辑层次；“述”就是要求对综合整理后的文献进行比较专门的、全面的、深入的、系统的论述。总之，文献综述是作者对某一方面问题的历史背景、前人工作、争论焦点、研究现状和发展前景等内容进行评论的科学性论文。写文献综述一般经过以下几个阶段：即选题，搜集阅读文献资料、拟定提纲（包括归纳、整理、分析）和成文。一、选题和搜集阅读文献撰写文献综述通常出于某种需要，如为某学术会议的专题、从事某项科研、为某方面积累文献资料等等，所以，文献综述的选题，作者一般是明确的，不象科研课题选题那么困难。文献综述选题范围广，题目可大可小，大到一个领域、一个学科，小到一种算法、一个方法、一个理论，可根据自己的需要而定。选定题目后，则要围绕题目进行搜集与文题有关的文献。关于搜集文献的有关方法，可以如看专著、年鉴法、浏览法、滚雪球法、检索法等等，在此不述。搜集文献要求越全越好，因而最常用的方法是用检索法。搜集好与文题有关的参考文献后，就要对这些参考文献进行阅读、归纳、整理，如何从这些文献中选出具有代表性、科学性和可靠性大的单篇研究文献十分重要，从某种意义上讲，所阅读和选择的文献的质量高低，直接影响文献综述的水平。因此在阅读文献时，要写好“读书笔记”、“读书心得”和做好“文献摘录卡片”。有自己的语言写下阅读时得到的启示、体会和想法，将文献的精髓摘录下来，不仅为撰写综述时提供有

概率图模型介绍与计算

概率图模型介绍与计算 01 简单介绍概率图模型是图论和概率论结合的产物，它的开创者是鼎鼎大名的Judea Pearl,我十分喜欢概率图模型这个工具，它是一个很有力的多变量而且变量关系可视化的建模工具，主要包括两个大方向：无向图模型和有向图模型。无向图模型又称马氏网络，它的应用很多，有典型的基于马尔科夫随机场的图像处理，图像分割，立体匹配等，也有和机器学习结合求取模型参数的结构化学习方法。严格的说他们都是在求后验概率:p(y|x)，即给定数据判定每种标签y的概率，最后选取最大的后验概率最大的标签作为预测结果。这个过程也称概率推理(probabilistic inference）。而有向图的应用也很广，有向图又称贝叶斯网络(bayes networks),说到贝叶斯就足以可以预见这个模型的应用范围咯，比如医疗诊断，绝大多数的机器学习等。但是它也有一些争议的地方，说到这就回到贝叶斯派和频率派几百年的争议这个大话题上去了，因为贝叶斯派假设了一些先验概率，而频率派认为这个先验有点主观，频率派认为模型的参数是客观存在的，假设先验分布就有点武断，用贝叶斯模型预测的结果就有点“水分”，不适用于比较严格的领域，比如精密制造，法律行业等。好吧，如果不遵循贝叶斯观点，前面讲的所有机器学习模型都可以dismiss咯，我们就通过大量数据统计先验来弥补这点“缺陷”吧。无向图和有向图的例子如（图一）所示：图一(a)无向图（隐马尔科夫）(b)有向图概率图模型吸取了图论和概率二者的长处，图论在许多计算领域中扮演着重要角色，比如组合优化，统计物理，经济等。图的每个节点都可看成一个变量，每个变量有N个状态（取值范围），节点之间的边表示变量之间的关系，它除了

运筹学答案_第_11_章__图与网络模型

第11章图与网络模型习题1 配送的最短距离。用解：这是一个最短路问题，要求我们求出从v1到v 7 Dijkstra算法求解可得到这问题的解为27。我们也可以用此书附带的管理运筹学软件进行计算而得出最终结果为：从节点1到节点7的最短路 ************************* 起点终点距离 ------------ 124 2312 356 575 此问题的解为:27 → 12357 习题2 解：这是一个最短路的问题，用Dijkstra算法求解可得到这问题的解为4.8，即在4年内购买、更换及运行维修最小的总费用为：4.8万元。最优更新策略为：第一年末不更新第二年末更新第三年末不更新第四年末处理机器我们也可以用此书附带的管理运筹学软件进行求解，结果也可以得出此问题的解为4.8。习题3 解：此题是一个求解最小生成树的问题，根据题意可知它要求出连接v1到v8的最小生成树。解此题可以得出结果为18。也可以使用管理运筹学软件，得出如下结果：此问题的最小生成树如下： ************************* 起点终点距离 ------------ 132 342 124 252 573

习题4 782 763此问题的解为:18 解：此题是一个求解最大流的问题，根据题意可知它要求出连接v1到 v6 的最大流量。解此题可以得出最大流量为出结果为： 22。使用管理运筹学软件，我们也可以得v1从节点1到节点6的最大流 ************************* 起点终点距离 ------------ 126 146 1310 240 256 345 365 455 466 5611 此问题的解为:22 即从v1到v6的最大流量为：22 习题5 解：此题是一个求解最小费用最大流的问题，根据题意可知它要求出连接v1到v6的最小费用最大流量。解此问题可以得出最大流为5，最小费用为39。使用管理运筹学软件，我们也可以得出结果如下：从节点1到节点6的最大流 ************************* 起点终点流量费用 ---------------- 1213 1341 2424 3211 3533 4624

宏观经济学课后习题-整理版2(重要)

提出的解决方法是依靠国家干预。国家调节经济不能主要依靠货币政策，而必须运用财政政策。财政政策是最有力、最重要的调节手段。第五章货币市场：通货膨胀 2.解释商业银行如何创造货币。答：举例说明：假设银行的法定准备金率为20%，甲在A银行存入1000元，银行系统就因此增加了1000元的准备金。A银行按法定准备金率保留200元作为准备金存入中央银行，其余800元全部贷出，假定是借给一家公司用来买机器，机器制造厂乙得到这笔贷款后全部存入与自己有业务往来的B银行，B银行得到这800元存款后留下160元作为准备金存入中央银行，然后再贷出640元。由此，不断存贷下去，各银行的存款总和是1000+800+640+……=5000元。在部分准备金银行制度下，在贷款和存款的多倍扩张过程之后，最初的1000元存款成倍增加到5000元，即总存款额。这就是银行体系的货币创造。这个倍数就是货币创造乘数。这个例子是简化了的，假如公众有部分现金保留在手中或者银行有超额准备金，货币创造乘数都会变小，但不会影响本质结果。 3.中央银行是如何影响货币供给量的？答：中央银行通过控制基础货币和法定准备金率来间接控制货币供给量。中央银行通过控制货币供给进而

影响经济运行的政策被称为货币政策。一般而言，中央银行有三种货币政策工具可以用于控制货币供给：公开市场业务、法定准备金率以及贴现率。当中央银行要增加货币供给量时，可以在公开市场上买进政府债券；降低法定准备金率；降低贴现率。反之，当中央银行要减少货币供给量时，可以在公开市场上卖出政府债券；提高法定准备金率；提高贴现率。第六章经济增长1-3理解 1.试解释索洛模型的稳态含义，在稳态中经济会增长吗？为什么说单纯的资本积累并不能实现一国经济的持续增长？答：索洛模型中的稳态指的是人均资本和人均产出均不随时间发生变化的状态，稳态代表经济的长期均衡。当经济处于稳态时，尽管人均资本和人均产出不再发生变化，但由于人口在增长，因此资本总量和总产出也仍然是增长的。索洛模型表明，无论经济初始的资本水平如何，它最终会到达稳态的资本水平，因此单纯的资本积累并不能实现一国经济的持续增长。 2.在索洛模型中，储蓄率是如何影响稳态收入水平和稳态增长率的？答：在索洛模型中，较高的储蓄率导致较高的稳态资本存量和稳态产出水平，较低的储蓄率导致较低的稳态

索洛模型详细推导

Solow 模型之详细推导参考资料：戴维·罗默《高级宏观经济学》龚六堂《经济增长理论》研究生一年级《高级宏观经济学》、《动态优化》课堂笔记 Solow 模型含四个变量：产出（Y ）、资本（K ），劳动（L ）、技术进步（A ）。生产函数的形式为： ()((),()())Y t F K t A t L t = 满足： ①二阶连续可微； (,)F ??②对变量非减且严格凹（即资本和劳动力的边际生产率都是递减的）； (,)F ??③生产函数是常数规模回报的，即对任意λ>0，有 (,)(,F K AL F K AL )λλλ=，（1）从而可得到欧拉（Euler ）方程： (,)(,)(,)F K L F K L F K L K L K L ??=+??； ④生产函数满足Inada 条件，即 00lim (,),lim (,)lim (,)0lim (,)0K L K L K L K L F K L F K L F K L F K L →→→∞→∞ =∞=∞==，。通常所讲的Cobbel-Douglas 生产函数满足此条件： ()()()()Y t A t K t L t αβ=，0,1αβ<<。规模报酬不变的假定使我们得以使用密集形式的生产函数。 11(,1)(,)K F F K AL Y AL AL AL ==，（2）令 K k AL =表示每单位有效劳动的平均资本数量， Y y AL =表示每单位有效劳动的平均产出那么可将（2）式写为： (,1)()y F k f k == 假定储蓄率为，资本折旧为s δ，人口增长率既定，为L n L =&，技术进步率也既

索罗余值法测算全要素生产率的文献综述

第46卷第8期 2019年8月天津科技 TIANJIN SCIENCE & TECHNOLOGY V ol.46 No.8Aug. 2019 基金项目：天津市重点招标项目“2017年天津市全要素生产率测算研究”(18ZLZDZF00210)。收稿日期：2019-07-18 科学与社会索罗余值法测算全要素生产率的文献综述孟媛，张弛 (天津市科技统计与发展研究中心天津300051) 摘要：国内外全要素生产率的测算方法很多，例如索罗余值法、随机前沿法、数据包络法等，其中应用较为普遍的是索罗余值法。通过简要梳理索罗余值法的推导过程，归纳较为普遍的关于该理论的基本假设(即规模效益不变和希克斯中性)的质疑，以及阐述全要素生产率与技术进步的关系，说明全要素生产率衡量技术进步是不完全准确的。关键词：全要素生产率索罗余值法技术进步中图分类号：F204；F224 文献标志码：A 文章编号：1006-8945(2019)08-0094-02 Literature Review on Measurement of Total Factor Productivity by Solow Residual Method MENG Yuan ，ZHANG Chi (Tianjin Science and Technology Statistic Center ，Tianjin 300051，China ) Abstract ：There are many measurement methods of total factor productivity at home and abroad, such as the Solow residual method, stochastic frontier method, data enveloping method and so on. The Solow residual method is widely used. The gen-eral doubts about its basic assumptions (namely, constant scale benefit and Hicks neutral) are summarized by briefly combing the derivation process of the Solow residual method. The relationship between total factor productivity and technical progress is discussed, indicating that the measurement of technical progress by total factor productivity is not completely accurate. Key words ：total factor productivity ；Solow residual method ；technical progress 十九大指出，我国经济已由高速增长阶段转向高质量发展阶段，并提出要提高全要素生产率。关于全要素生产率，国内外学者进行了较多研究，测算方法不一，包括索罗余值法、随机前沿法、数据包络法等，其中索罗余值法的应用范围较为广泛。本文通过文献综述，简要介绍索罗余值法测算全要素生产率的过程，根据其适用的前提条件探讨测算的局限性，进而阐述全要素生产率与技术进步的关系。 1 索罗余值法简介索罗[1]并不是第一个将生产函数与生产率联系起来的人，早在1942年Tinbergen 就探索过两者之间的关系，但是索罗的开创性贡献在于他在生产函数和指数方法之间建立了较为简洁且实用的理论联系。索罗余值法是基于柯布-道格拉斯生产函数(即CD 生产函数)得到的，以规模效益不变和希克斯中性(Hicks neutral )为基本假设前提。规模效益不变指的是在既定的技术水平下，要素价格不变时，产出增加的比例等于所有投入要素增加的比例。希克斯中性指的是投入要素资本和劳动的边际产出的比率不变。CD 生产函数为： (,)t t t t Q A F K L = (1) 式中：Q t 指的是产出，K t 指的是资本投入，L t 指的是劳动投入，希克斯A t 指的是在资本和劳动投入水平不变时产出增加的部分，即全要素生产率，经常被用以衡量“技术进步”。上述公式(1)变形，可以得到相对希克斯效率A t /A 0，即Q t /Q 0作分子，生产函数中要素积累的部分F (K t ，L t )/F (K 0，L 0)作分母。但是由于各投入要素的计量单位不同，这样并不能直接得到希克斯效率。索罗运用非参数指数法，将上述公式变形得到： t t t t t t t t t t t t Q K K L L A Q Q Q K Q K L Q L A ??=++?? (2)

机器学习 —— 概率图模型(推理：团树算法)

在之前的消息传递算法中，谈到了聚类图模型的一些性质。其中就有消息不能形成闭环，否则会导致“假消息传到最后我自己都信了”。为了解决这种问题，引入了一种称为团树（clique tree)的数据结构，树模型没有图模型中的环，所以此模型要比图模型更健壮，更容易收敛。 1.团树模型链模型是一种最简单的树模型，其结构如下图所示，假设信息从最左端传入则有以下式子。假设要对变量CD 进行推断，则应该求Belief(3) = deta 2->3 *deta 4->3 * phi(3). 从这里可以看出，团树算法是一种精确推断算法。它和变量消除算法在理论推导上是等价的。上面的例子只是一种非常简单的团树，团树的本质还是聚类图，只不过是一种特殊的聚类图。对于更一般的概率图，也可以生成团树图。

其中，每个cluster都是变量消除诱导图中的一个最小map。 2.团树模型的计算从上面分析可知，团树模型本质上和变量消除算法还有说不清道不明的关系（团树模型也是精确推理模型）。但是这个算法的优势在于，它可以利用消息传递机制达到收敛。之前提过，聚类图模型中的收敛指的是消息不变。除此之外，聚类图的本质是一种数据结构，它可以储存很多中间计算结果。如果我们有很多变量ABCDEF，那么我们想知道P(A)，则需要执行一次变量消除。如果要计算P(B)又要执行一次变量消除。如果中途得到了某个变量的观测，又会对算法全局产生影响。但是使用团树模型可以巧妙的避免这些问题。首先，一旦模型迭代收敛之后。所有的消息都是不变的，每个消息都是可以被读取的。每个团的belief，实际上就是未归一划的联合概率，要算单个变量的概率，只需要把其他的变量边际掉就行。这样一来，只需要一次迭代收敛，每个变量的概率都是可算的。并且算起来方便。其次，如果对模型引入先验知识比如A = a 时，我们需要对D 的概率进行估计。按照变量消除的思路又要从头来一次。但是如果使用团树结构则不用，因为A的取值只影

新经济增长理论——文献综述

新经济增长理论——文献综述西南交通大学《区域经济理论》课程论文新经济增长理论——一个文献的综述年级:2014级学生:张镨心学号:2014201491 课程:区域经济理论指导老师:骆玲 2015年1月7日新经济增长理论——一个文献的综述一、理论产生背景 1、现实背景 20 世纪 70 年代以后，第三次科技革命方兴未艾，科技与经济增长的关系日益紧密，许多经济学家提出，知识的积累和技术的革新对经济增长作用很大，甚至是决定性的。为更好地解释经济增长，必须将这些因素纳入模型。而分析工具和经济理论的进步，也为研究经济增长提供了更好的工具和思路。在此背景下，诞生了经济增长研究的新成果———新经济增长理论。 2、理论背景半个世纪以来,经济增长理论历经兴衰,出现了三次大的高潮。第一次高潮是第二次高潮是新古典增长模型的产生和发展;第哈罗德-多马模型的产生和发展; 三次高潮是新经济增长理论的产生和发展。三次大高潮都共同关注经济学中一个重要且令人困惑的问题:经济增长是否可以长期持续,如果可以,增长的根本原因

究竟是什么?哈罗德-多马模型和新古典增长模型虽然对经济增长的原因做出了重要的说明,但他们难以就人类漫长的经济增长史给出一致的、富有说服力的解释。因而,他们的理论不可避免地在上世纪60年代末衰落了。在20世纪80年代中期,以罗默(Romer, P.)、卢卡斯(Lucas, R.)等人为代表的一批经济学家,在对新古典增长理论重新思考的基础上,撰写了一系列以内生技术变化为核心的论文,探讨了经济长期增长的可能前景,掀起了一股新经济增长理论研究的潮流。二、相关理论分析 20世纪40年代末,英国经济学家哈罗德(Harrod,R.)和美国经济学家多马(Dormar, E.),根据凯恩斯收入决定论的思想,把凯恩斯理论动态化和长期化,分别推演出极为相似的长期经济增长模型,人们合称为哈罗德-多马模型。这一经济增长模型的提出不但带来了动态理论(古典经济增长理论)的复归,而且奠定了现代经济增长理论的基本框架。 1、哈罗德——多马模型哈罗德-多马模型突出了资本积累在经济增长中的决定性作用。在模型中,由于假定资本/产出比不变,因而经济增长唯一地决定于储蓄率,也就是资本积累率,从而为经济增长找到了一种似乎是合理的持久动力和源泉。同时，他们为经济增长理论的研究提供了一个科学的范式，即应用数理工具构建模型研究经济增长。按照哈罗德—多马模型的结论，经济稳态增长的条件是: G = Gw = Gn，即实际增长率、合意增长率和自然增长率相等，经济将长期繁荣。一旦出现偏离，经济不仅不能自行纠正“实际增长率”和“合意增长率”之间的偏离，而且由于乘数效应的作用，还具有将这种偏离积累型增大的效应，这使得哈罗德———多马模型提出的经济稳定增长的条件具有“刀刃”( knife , edge) 性质。经济的这种内在不稳定性，要求政府对经济实行永久性干预。但是这一理论模型也存在不少的缺陷,遭到以索罗为代表的新古典增长理论的批评。首先,资本/产出比不变的

概率图模型

概率图模型过去的一段时间里，忙于考试、忙于完成实验室要求的任务、更忙于过年，很长时间没有以一种良好的心态来回忆、总结自己所学的东西了。这几天总在想，我应该怎么做。后来我才明白，应该想想我现在该做什么，所以我开始写这篇博客了。这将是对概率图模型的一个很基础的总结，主要参考了《PATTERN RECOGNITION and MACHINE LEARNING》。看这部分内容主要是因为LDPC码中涉及到了相关的知识。概率图模型本身是值得深究的，但我了解得不多，本文就纯当是介绍了，如有错误或不当之处还请多多指教。 0. 这是什么？很多事情是具有不确定性的。人们往往希望从不确定的东西里尽可能多的得到确定的知识、信息。为了达到这一目的，人们创建了概率理论来描述事物的不确定性。在这一基础上，人们希望能够通过已经知道的知识来推测出未知的事情，无论是现在、过去、还是将来。在这一过程中，模型往往是必须的，什么样的模型才是相对正确的？这又是我们需要解决的问题。这些问题出现在很多领域，包括模式识别、差错控制编码等。概率图模型是解决这些问题的工具之一。从名字上可以看出，这是一种或是一类模型，同时运用了概率和图这两种数学工具来建立的模型。那么，很自然的有下一个问题 1. 为什么要引入概率图模型？对于一般的统计推断问题，概率模型能够很好的解决，那么引入概率图模型又能带来什么好处呢？ LDPC码的译码算法中的置信传播算法的提出早于因子图，这在一定程度上说明概率图模型不是一个从不能解决问题到解决问题的突破，而是采用概率图模型能够更好的解决问题。《模式识别和机器学习》这本书在图模型的开篇就阐明了在概率模型中运用图这一工具带来的一些好的性质，包括

宏观经济中校准法的文献综述

宏观经济中校准法的文献综述摘要：真实经济周期近年来已经成为宏观经济研究的主要方法，其中得到发展的校准法占有重要地位，并且在实际应用中取得了重要的成果。在介绍了校准的重要性以及含义之后，对实际经济周期理论中校准方法进行综述和评析，介绍国内外著名学者对于校准方法的研究以及发展，理清发展的脉络，并指明将是未来校准方法发展的一个有力工具。关键词：宏观经济；rbc模型；非参数校准导言 2004年诺贝尔经济学奖得主kydland和prescott创建的真实商业周期模型已成为诸多经济学家研究经济的主要工具。新古典的真实经济周期理论同传统的宏观经济学相比，其吸引力在于它保持了微观经济学与宏观经济学很好的一致性，正是在这一点上它动摇了凯恩斯主义的统治地位，并开拓了西方学者研究宏观经济学的新思路，使其宏观经济学建立在坚实的微观经济学基础之上。卢卡斯极力赞扬真实经济周期理论的方法论，“建立了一个最贴近现实的模型：一个被充分描述的随时间变化的人为经济，从而逼真的模拟实际经济的时间序列行为”，现代宏观经济学的研究方法实际上将宏观经济往前推进了一大步。对于真实经济周期的研究方法校准法是在对宏观计量模型不甚满意，想要模型更好的拟合实际经济而提出的，校准法对于数据的

要求较低并且具有容易简单性，该种方法已经从最初用于研究政策冲击的应用一般均衡模型到后来被学者们推广到研究经济周期的原因和结果的非货币型随机一般均衡模型中以及其他模型中的广泛应用。正如gregory和smith（1991）在对宏观经济学的应用文章一次调查后指明这种模型将在当代宏观经济学实证研究中占据主导地位，这足以说明校准在整个宏观经济发展中的重要作用。校准法来源于自然科学中测量设备的校验，在《大不列颠百科全书》中给出了简单的说明：校准相当于为测度工具进行初始点的设定以及尺度的选择，校准后的温度计，0度代表冰点，100度代表沸点，这样的温度计就可以用来测量温度。一个经济模型的校准，涉及到具体参数的设定以能够复制作为模型解的基准数据集。黄赜琳（2005）对真实经济周期模型的求解方法校准法给出具体的步骤：第一步是确定与构建分析框架理论模型，第二步是模型通过建立与时间经济度量相一致的指标变量以便能够从实际经济中获取数据来测算相应的参数值，第三步是设置一组与均衡条件相一致的参数。如果该模型被校准，它就可以被用于评估或模拟一些不可观察的或者反事实的政策或者参数变化对于经济体的冲击效应。我们来回顾国内外关于校准研究的文献以便能够从整体上把握校准的发展脉络，有助于在前人研究的基础上进行研究。一、校准方法的国外文献综述首先我们来看在校准法最初是怎样的形式进入到动态一般均衡

概率图模型理论及应用教学大纲

教学大纲统计推理和学习（Statistical Inference and Learning）是信号处理、模式识别、通信系统等工程应用中处理不确定性的一个重要方法。新兴的（概率）图模型是概率论与图论相结合的产物，为各种统计推理和学习提供了一个统一的灵活框架。本课程介绍图模型基本理论，包括：图论相关知识，图模型上条件独立性，有向图模型（贝叶斯网络）、无向图模型（马尔可夫随机场），图模型的统计推理算法，图模型的学习算法（参数学习和结构学习）等，以及图模型在语音识别、图像处理、计算机视觉、通信信道编码（Turbo-coding）等应用中的具体实例。具体包括如下内容：第一章引言统计推理和学习的概念第二章图模型图论相关知识（简介）图模型上条件独立性（d-separation，Bayes ball）有向图模型（贝叶斯网络），无向图模型（马尔可夫随机场）在图模型框架下介绍：多元高斯模型、主成分分析（PCA）、混合分布（Mixtures）、因子分析（FA）、隐马尔科夫模型（HMM）第三章图模型上的推理（Inference）图论知识深入：簇（Cliques）、可分解图（Decomposable graph），连接树（Junction tree），规范化（Moralization），三角化（Triangulation）等概念 Junction Tree算法对HMM的前向-后向算法、Viterbi算法，线性动态系统的Kalman滤波的统一描述 1

第四章图模型的参数学习（Parameter Learning）完整数据下的最大似然（ML）参数估计不完整数据（Incomplete Data）下的ML参数估计（EM算法）完整数据下的贝叶斯学习不完整数据下的贝叶斯学习第五章图模型的结构学习（Structure Learning）模型选取准则，包括最小描述长度（Minimum Description Length，MDL），贝叶斯信息准则（Bayesian Information Criterion，BIC）等结构EM算法（Structural EM）结构的贝叶斯学习第六章图模型的应用选讲图模型在语音识别应用中的实例图模型在图像处理应用中的实例图模型在计算机视觉应用中的实例图模型在通信信道编码（Turbo-coding）应用中的实例（前面各章中配合理论的讲解，相应有应用实例的介绍。） 2

宏观经济中校准法的文献综述

摘要：真实经济周期近年来已经成为宏观经济研究的主要方法，其中得到发展的校准法占有重要地位，并且在实际应用中取得了重要的成果。在介绍了校准的重要性以及含义之后，对实际经济周期理论中校准方法进行综述和评析，介绍国内外著名学者对于校准方法的研究以及发展，理清发展的脉络，并指明将是未来校准方法发展的一个有力工具。关键词：宏观经济；rbc模型；非参数校准导言 2004年诺贝尔经济学奖得主kydland和prescott创建的真实商业周期模型已成为诸多经济学家研究经济的主要工具。新古典的真实经济周期理论同传统的宏观经济学相比，其吸引力在于它保持了微观经济学与宏观经济学很好的一致性，正是在这一点上它动摇了凯恩斯主义的统治地位，并开拓了西方学者研究宏观经济学的新思路，使其宏观经济学建立在坚实的微观经济学基础之上。卢卡斯极力赞扬真实经济周期理论的方法论，“建立了一个最贴近现实的模型：一个被充分描述的随时间变化的人为经济，从而逼真的模拟实际经济的时间序列行为”，现代宏观经济学的研究方法实际上将宏观经济往前推进了一大步。对于真实经济周期的研究方法校准法是在对宏观计量模型不甚满意，想要模型更好的拟合实际经济而提出的，校准法对于数据的要求较低并且具有容易简单性，该种方法已经从最初用于研究政策冲击的应用一般均衡模型到后来被学者们推广到研究经济周期的

原因和结果的非货币型随机一般均衡模型中以及其他模型中的广泛应用。正如gregory和smith（1991）在对宏观经济学的应用文章一次调查后指明这种模型将在当代宏观经济学实证研究中占据主导地位，这足以说明校准在整个宏观经济发展中的重要作用。校准法来源于自然科学中测量设备的校验，在《大不列颠百科全书》中给出了简单的说明：校准相当于为测度工具进行初始点的设定以及尺度的选择，校准后的温度计，0度代表冰点，100度代表沸点，这样的温度计就可以用来测量温度。一个经济模型的校准，涉及到具体参数的设定以能够复制作为模型解的基准数据集。黄赜琳（2005）对真实经济周期模型的求解方法校准法给出具体的步骤：第一步是确定与构建分析框架理论模型，第二步是模型通过建立与时间经济度量相一致的指标变量以便能够从实际经济中获取数据来测算相应的参数值，第三步是设置一组与均衡条件相一致的参数。如果该模型被校准，它就可以被用于评估或模拟一些不可观察的或者反事实的政策或者参数变化对于经济体的冲击效应。我们来回顾国内外关于校准研究的文献以便能够从整体上把握校准的发展脉络，有助于在前人研究的基础上进行研究。一、校准方法的国外文献综述首先我们来看在校准法最初是怎样的形式进入到动态一般均衡模型中的。kydland和prescott （1982）采取季度这一时间单位来作为模型的一个时间段，之后运用战后美国的平均经济数据来确定平均资本产出率，平均季度利率，收入中资本利得所占的平均比