[科普中国]-概率图模型

概率图模型

概率图模型是一类用图形模式表达基于概率相关关系的模型的总称。概率图模型结合概率论与图论的知识，利用图来表示与模型有关的变量的联合概率分布。近10年它已成为不确定性推理的研究热点，在人工智能、机器学习和计算机视觉等领域有广阔的应用前景。1

概率图理论共分为三个部分，分别为概率图模型表示理论，概率图模型推理理论和概率图模型学习理论。2

基本的概率图模型包括贝叶斯网络、马尔可夫网络和隐马尔可夫网络。

基本的Graphical Model 可以大致分为两个类别：贝叶斯网络(Bayesian Network)和马尔可夫随机场(Markov Random Field)。它们的主要区别在于采用不同类型的图来表达变量之间的关系：贝叶斯网络采用有向无环图(Directed Acyclic Graph)来表达因果关系，马尔可夫随机场则采用无向图(Undirected Graph)来表达变量间的相互作用。这种结构上的区别导致了它们在建模和推断方面的一系列微妙的差异。一般来说，贝叶斯网络中每一个节点都对应于一个先验概率分布或者条件概率分布，因此整体的联合分布可以直接分解为所有单个节点所对应的分布的乘积。而对于马尔可夫场，由于变量之间没有明确的因果关系，它的联合概率分布通常会表达为一系列势函数（potential function）的乘积。通常情况下，这些乘积的积分并不等于1，因此，还要对其进行归一化才能形成一个有效的概率分布——这一点往往在实际应用中给参数估计造成非常大的困难。

概率图模型有很多好的性质：它提供了一种简单的可视化概率模型的方法，有利于设计和开发新模型；用于表示复杂的推理和学习运算，可以简化数学表达。3

概率图模型表示理论概率图模型的表示方法，研究如何利用概率网络中的独立性来简化联合概率分布的方法表示。概率图模型能有效处理不确定性推理，从样本数据中准确高效地学习概率图模型是其在实际应用中的关键问题。概率图模型的表示由参数和结构两部分组成，PGM的分类如图1：

（1）根据边有无方向性分类；

根据边有无方向性，PGM可以分为三类

1.有向图模型，也称为贝叶斯网（BayesianNetwork，BN），其网络结构使用有向无环图；

2.无向图模型，也称为马尔可夫网（MarkovNetwork，MN），其网络结构为无向图；

3. 局部有向模型，即同时存在有向边和无向边的模型，包括条件随机场（ConditionalRandomField，CRF）和链图（ChainGraph）。

（2）根据表示的抽象级别不同分类。

根据表示的抽象级别不同，PGM可分两类：

1.基于随机变量的概率图模型，如贝叶斯网、马尔可夫网、条件随机场和链图等；

2.基于模板的概率图模型．这类模型根据应用场景不同又可分为两种：

a.为暂态模型，包括动态贝叶斯网（Dynamic Bayesian Network，DBN）和状态观测模型，其中状态观测模型又包括线性动态系统（Linear Dynamic System，LDS）和隐马尔可夫模型（Hidden Markov Model，HMM）；

b.为对象关系领域的概率图模型，包括盘模型（Plate Model，PM）、概率关系模型（Probabilistic Relational Model，PRM）和关系马尔可夫网（Relational Markov Network，RMN）。4

总结如下 ：

（1）单个节点上的条件概率分布的表示模型及其引起的独立性，包括表格CPD、确定性CPD、特定上下文CPD、因果影响CPD、高斯模型和混合模型，并把单个分布模型推广到指数分布族中。

（2）贝叶斯网络中的独立性以及图与概率分布的关系，高斯分布和指数分布族的贝叶斯网络表示理论。马尔可夫网络的参数化问题及其独立性，高斯分布和指数分布族的马尔可夫网络表示理论。

（3）两种局部有向图模型：条件随机场和链图。

（4）基于模板的概率模型表示，包括动态贝叶斯网络和状态观测模型这两种暂态模型。

（5）盘模型和概率关系模型这两种对象关系领域的有向概率模型，对象关系领域的无向表示。1

概率图模型学习理论概率图模型学习算法分为参数学习与结构学习。基于概率图模型学习分为概率网络的参数学习与结构学习算法，并根据数据集是否完备而分为确定性不完备，随机性不完备各种情况下的参数学习算法，针对结构学习算法特点的不同，结构学习算法归纳为基于约束的学习、基于评分搜索的学习、混合学习、动态规划结构学习、模型平均结构学习和不完备数据集的结构学习。

结构学习仍然是机器学习中一个极具挑战性的方向。结构学习并没有固定的形式，不同的研究者往往会采取不同的途径。比如，结构学习中一个非常重要的问题，就是如何去发现变量之间的内部关联。对于这个问题，人们提出了多种截然不同的方法：比如，你可以先建立一个完全图连接所有的变量，然后选择一个子图来描述它们的实际结构，又或者，你可以引入潜在节点(latent node)来建立变量之间的关联。

Probabilistic Graphical Model的另外一个重要的发展方向是非参数化。与传统的参数化方法不同，非参数化方法是一种更为灵活的建模方式——非参数化模型的大小（比如节点的数量）可以随着数据的变化而变化。一个典型的非参数化模型就是基于狄利克莱过程(Dirichlet Process)的混合模型。这种模型引入狄利克莱过程作为部件(component)参数的先验分布，从而允许混合体中可以有任意多个部件。这从根本上克服了传统的有限混合模型中的一个难题，就是确定部件的数量。在近几年的文章中，非参数化模型开始被用于特征学习。在这方面，比较有代表性的工作就是基于Hierarchical Beta Process来学习不定数量的特征。3

概率图模型的推理算法根据网络结构与查询问题类型的不同，概率图模型的推理算法有：

（1）贝叶斯网络与马尔可夫网络中解决概率查询问题的精确推理算法与近似推理算法,其中具体包括精确推理中的VE算法、递归约束算法和团树算法,以及近似推理中的变分近似推理和抽样近似推理算法；
（2）解决MAP查询问题的常用推理算法；
（3）混合网络的连续与混合情况阐述其推理算法；
（4）暂态网络的精确推理、近似推理以及混合情况下的推理。5

基于Graphical Model 的统计推断除了最简单的一些模型，统计推断在计算上是非常困难的。一般而言，确切推断(exact inference)的复杂度取决于模型的tree width。对于很多实际模型，这个复杂度可能随着问题规模增长而指数增长。于是，人们退而求其次，转而探索具有多项式复杂度的近似推断(approximate inference)方法。

主流的近似推断方法有三种：

（1）基于平均场逼近(mean field approximation)的variational inference。这种方法通常用于由Exponential family distribution所组成的贝叶斯网络。其基本思想就是引入一个computationally tractable的upper bound逼近原模型的log partition function，从而有效地降低了优化的复杂度。EM算法就属于这类型算法的一种特例。

（2）Belief propagation。这种方法最初由Judea Pearl提出用于树状结构的统计推断。后来人们直接把这种算法用于带环的模型（忽略掉它本来对树状结构的要求）——在很多情况下仍然取得不错的实际效果，这就是loop belief propagation。在进一步的探索的过程中，人们发现了它与Bethe approximation的关系，并由此逐步建立起了对loopy belief propagation的理论解释，以及刻画出它在各种设定下的收敛条件。值得一提的是，由于Judea Pearl对人工智能和因果关系推断方法上的根本性贡献，他在2011年获得了计算机科学领域的最高奖——图灵奖。

基于message passing的方法在最近十年有很多新的发展。Martin Wainwright在2003年提出Tree-reweighted message passing，这种方法采用mixture of trees来逼近任意的graphical model，并利用mixture coefficient和edge probability之间的对偶关系建立了一种新的message passing的方法。这种方法是对belief propagation的推广。Jason Johnson等人在2005年建立的walk sum analysis为高斯马尔可夫随机场上的belief propagation提供了系统的分析方法。这种方法成功刻画了belief propagation在高斯场上的收敛条件，也是后来提出的多种改进型的belief propagation的理论依据。Thomas Minka在他PhD期间所建立的expectation propagation也是belief propagation的在一般Graphical Model上的重要推广。

（3）蒙特卡罗采样(Monte Carlo sampling)。与基于优化的方法不同，蒙特卡罗方法通过对概率模型的随机模拟运行来收集样本，然后通过收集到的样本来估计变量的统计特性（比如，均值）。采样方法有三个方面的重要优点。第一，它提供了一种有严谨数学基础的方法来逼近概率计算中经常出现的积分（积分计算的复杂度随着空间维度的提高呈几何增长）。第二，采样过程最终获得的是整个联合分布的样本集，而不仅仅是对某些参数或者变量值的最优估计。这个样本集近似地提供了对整个分布的更全面的刻画。比如，你可以计算任意两个变量的相关系数。第三，它的渐近特性通常可以被严格证明。对于复杂的模型，由variational inference或者belief propagation所获得的解一般并不能保证是对问题的全局最优解。在大部分情况下，甚至无法了解它和最优解的距离有多远。如果使用采样，只要时间足够长，是可以任意逼近真实的分布的。而且采样过程的复杂度往往较为容易获得理论上的保证。

蒙特卡罗方法本身也是现代统计学中一个非常重要的分支。对它的研究在过去几十年来一直非常活跃。在机器学习领域中，常见的采样方法包括Gibbs Sampling, Metropolis-Hasting Sampling (M-H),Importance Sampling, Slice Sampling, 以及Hamiltonian Monte Carlo。其中，Gibbs Sampling由于可以纳入M-H方法中解释而通常被视为M-H的特例——虽然它们最初的motivation是不一样的。1