概率图模型理论与应用

主讲人: 董建家

清华大学自动化系博士、康奈尔大学访问学者

1. 什么是概率图模型

概率图模型

  • 概率论与图论相结合的产物，为统计推理和学习提供了一个统一的灵活框架。
  • 概率图模型用节点表示变量，节点之间的边表示局部变量间的概率依赖关系。在概率图模型的表示框架下，系统的联合概率分布表示为局部变量势函数的连乘积，该表示框架不仅避免了对复杂系统的联合概率分布直接进行建模，而且易于在图模型建模中引入先验知识。
  • 2012年图灵奖：UCLA 的 Judea Pearl 教授，开创性的工作 —— 贝叶斯网络和消息传递（贝叶斯网络属于有向的概率图模型，消息传递：是一种进行概率图计算推理的创新的机制，通过消息传递可以把全局的推理的转化为图上的局部变量之间的消息传递，大大的降低了推理的复杂度。）

  • 概率图模型统一了目前广泛应用的许多统计模型和方法：

    • 马尔科夫随机场（MRF，无向的概率图模型，在图像处理，统计物理等领域广泛应用）、条件随机场（CRF，在 NLP 领域应用广泛）
    • 隐马尔科夫模型（HMM）、多元高斯模型
    • Kalman 滤波、粒子滤波、变分推理等

以上这些不同的统计模型和方法都可以纳入到概率图模型这个框架之中，以上这些方法都是一些特殊的概率图模型。

  • 概率图模型提供了一个描述框架，是我们能够将不同领域的只是抽象为概率模型，将各种应用中的问题都归结为计算概率模型里某些变量的概率分布，从而将知识表示和推理分离开来。

img

概率图模型的例子

2. 概率图模型的发展历程

  • 历史上，曾经有来自不同学科的学者尝试使用图的形式表示高维分布的变量间的依赖关系。
  • 在人工智能领域，概率方法始于构造专家系统的早期尝试。
  • 到 20 世纪 80 年代末，在贝叶斯网络和一般的概率图模型中的推理取得重要进展。1988 年，人工智能领域著名学者 Pearl 提出了信念传播（Belief Propagation, BP）算法，BP 算法把全局的概率推理过程转变为局部变量间的消息传递，从而大大降低了推理的复杂度。（此处的 BP 算法和神经网络中的 BP反向传播算法是完全不同的算法，此处的 BP 算法是一个推理算法，他所做的事情是把全局的概率推理过程，转化为局部变量之间的消息传递）。
  • BP 算法引起了国际上学者的广泛关注，掀起了研究的热潮。
  • 2003年， Wainwright 等人提出了树重置权重信度传播（tree-reweighted belief propagation)算法，其主要思想是将一个有环概率图模型分解为若干生成树的加权和，从而将原复杂的推理问题转化为若干树状图模型的推理问题。
  • 2008 年，Globerson 和 Sontag 等人提出了基于线性规划松弛和对偶分解的推理算法。（这个推理算法框架的意义在于：把一个推理问题转化为一个优化问题；而且很多之前的推理算法都能够纳入到这个框架中）
  • 如今，经过近 30 余年的发展，概率图模型的推断和学习已经广泛应用于机器学习、计算机视觉、自然语言处理、医学图像处理、计算神经学、生物信息学等研究领域，成为人工智能相关研究中不可或缺的一门技术。

概率图模型的表示、推理、学习

概率图模型的理论包括三大部分：图模型的表示、推理、学习。

概率图模型的表示所要解决的问题是：如何在一个图上定义一个联合概率分布，它要解决的核心问题是：如何把联合概率分布表示成一些局部因子的连乘积的形式，为什么能够表示成这种形式，这是概率图模型表示部分所要解决的问题。概率图模型的表示其实也是一个建模问题。

第二大部分是：概率图模型的推理，推理是建立在表示的基础之上的。也就是说图模型的结构和参数已经给定了，我们需要对这个图模型进行一定的推理计算。主要的推理任务有：求边缘概率、最大后验概率状态，以及求归一化因子等等。

求边缘概率的任务是：已知联合概率分布求部分变量的边缘概率。

最大后验概率状态是：已知联合概率分布求这个分布里面的 x 取某个值的时候，使得整个联合概率分布的取值最大，我们求这个时候对应的 x 的取值。

推理其实就是一个模型的求解。

图模型的学习要解决的问题是：给定训练数据，我们要从训练数据中把图模型的结构和参数给学习出来。所谓结构就是：这个图模型有哪些节点，以及哪些节点之间有边连接。所谓参数就是：边之间的连接权重。

概率图模型的表示

  • 概率图模型的表示刻画了模型的随机变量在变量层面的依赖关系，反映出问题的概率结构，为推理算法提供了数据结构。概率图模型的表示方法主要有贝叶斯网络、马尔科夫随机场、因子图等。
  • 概率图模型表示主要研究的问题是，为什么联合概率分布可以表示局部势函数的联乘积形式，如何在图模型建模中引入先验知识等。（正是条件独立性，使得概率图模型的联合概率分布可以表示成局部势函数的联乘积的形式，也正是因为这种联乘积的形式，使得概率图模型建模的复杂度大大的降低）

概率图模型的推理

  • 概率图模型推理包括求边缘概率、求最大后验概率状态、求归一化因子等问题。
  • 概率图模型相当于模型的求解，在一般的图模型中，概率推理是 NP 难问题。(所以在很多的实际应用中，采用的推理算法一般是近似推理算法，在推理的准确度和推理的时间复杂度之间做一个平衡)
  • 概率推理是本课程的重点内容。（精确推理和近似推理，精确推理是近似推理的基础，实际大都采用近似推理）

概率图模型的学习

  • 对于复杂的、缺乏专家经验的概率模型，如果我们有一定数量的观测数据，通常希望能够从观测数据中获得模型的参数甚至结构。
  • 参数学习：已知图模型的结构，学习模型的参数；（参数是图模型中边的权重）
  • 结构学习：从数据中推断变量之间的依赖关系。（图模型的结构包括了图模型的节点和节点之间的边，图模型的结构决定了这个图模型有哪些点，以及这些点是如何相连的。）

概率图模型的应用

  • 图像分割

使用马尔科夫随机场（无向的概率图模型）对这个问题进行建模，左边图像的每一个像素点对应于图模型中的每一个节点。相邻像素点之间定义一条边，边上的参数定义为相邻像素的相似性。这样一个图像分割问题，在图模型的结构层面，我们采用的是：网格状的马尔科夫随机场，图模型的参数我们采用的是：相邻像素点的像素值具有连续性，具有相似性。把这个物理含义赋予概率意义，定义在概率图模型上。建模以后，我们就可以在这个图模型上进行推理，推理的结果是右边这幅分割的图像。

  • 立体视觉

立体视觉所要解决的任务是：给定两幅图像，输出这幅图像里面的每一个像素点对应的图像深度，所谓图像的深度是指：图像里面的每一个像素点对应的物体离我们的远近程度。这样一个问题同样可以使用概率图模型进行求解，图模型的每一个节点对应于图像里面的一个像素点，图模型节点之间的边对应于相邻像素点的相似性，图模型边上的概率的物理含义就代表了相邻像素的相似性和连续性。图模型建模完成以后，在这个图模型上进行推理，计算。在这个例子里面我们采用推理的是最大后验概率状态推理，推理、计算的结果就是求出了每一个像素点的图像的深度，就得出了右边这幅图像。

  • 图像去噪

图像去噪的任务是：对于给定的一副有噪声的自然图像，我们要做的事情是：进行去噪处理，将噪声进行一定程度的去除。对原图像进行一定程度的复原。这个图像处理问题，同样可以使用概率图模型建模求解。在建模的时候，同样的一个像素点对应于概率图模型的一个节点，相邻像素点上定义一条边，边上定义的概率值代表的含义是：相邻像素的相似性，如果相似性越高，它的概率值就会越大。相似度越低，它的概率值就会越小。结构和参数都定义完成之后，我们就完成了概率图模型的表示。推理计算的结果就是右边这幅去噪以后的图像。

  • 人体姿态估计

人体姿态估计的任务是：对于给定的一幅自然图像，我们要做的事情是：估计图像中的人物处于什么姿态，比如说：他是在打网球或者说是在踢足球。我们采用概率图模型对这个问题进行建模，首先我们对人体进行区块的划分，分成头部、躯干、手臂、上胳膊、胳膊、大腿、小腿。用这些区块把人体描述出来，图中的这些区块方块对应于概率图模型的一个节点。那么这样一个节点它有多个变量，比如说：头部的矩形，它的中心位置坐标，矩形块的角度等等。对应于概率图模型每个节点的变量。边的定义，我们引入了人体运动学的一些约束，比如说，这些躯干之间连在一起，是需要有一些约束的。比如，手臂和胳膊，头部和躯干这些都是需要连在一起的。我们就把这些运动学的约束通过概率的形式定义到图模型的边上。通过这种方式，我们完成了图模型的结构和参数的表示。图模型建模完成以后，我们同样进行概率推理。推理的结果就是人体姿态估计的结果。

  • 医学图像处理

  • 医学诊断

医学诊断采用的概率图模型是：贝叶斯网络，是一个有向的概率图模型。什么是医学诊断呢？它实在模拟医生来做专家的推断。医生在判断患者是否患病，需要观察患者的症状，通过分析结合经验来下结论。应用贝叶斯网络来做医学诊断也是这个原理，对于一个疾病，会给出和这个疾病很多相关的变量，变量之间会定义一些概率依赖关系。然后，有了贝叶斯网络之后，网络结构定下来之后，再将专家的经验通过概率赋值的方式输入到图模型上，完成建模。然后，进行推理和计算。推理和计算的过程，相当于在模拟医生的医学诊断的过程。

课程内容

  • 概率图模型理论：

    • 概率论与图论基础
    • 图模型的表示：贝叶斯网络、马尔科夫随机场、因子图
    • 图模型的推理：变量消元法、团树传播算法、信念传播算法、图切法等
    • 图模型的学习：结构学习、参数学习

  • 概率图模型应用：

    • 条件随机场在自然语言处理中的应用
    • 概率图模型在医学图像中的应用
    • 概率图模型在计算机视觉中的应用

课时安排

  • 第 1 章 概率图模型简介（1 学时）

    • 1.1 什么是概率图模型？
    • 1.2 概率图模型发展历程
    • 1.3 概率图模型的表示、推理、学习
    • 1.4 概率图模型的应用举例

  • 第 2 章 概率图模型的表示（4学时）

    • 2.1 概率论与图论基础
    • 2.2 贝叶斯网络
    • 2.3 马尔科夫随机场
    • 2.4 因子图

  • 第 3 章 概率图模型的精确推理（5学时）

    • 3.1 推理问题分类
    • 3.2 变量消元法
    • 3.3 团树传播算法
    • 3.4 信念传播算法（BP算法）
    • 3.5 二值图切法

  • 第 4 章 概率图模型的近似推理（4学时）

    • 4.1 BP算法的能量最小化解释
    • 4.2 基于图切法的近似推理算法

  • 第 5 章 概率图模型的学习（2学时）

    • 5.1 参数学习
    • 5.2 结构学习

  • 第 6 章 概率图模型的应用（3学时）

    • 6.1 条件随机场在自然语言处理中的应用
    • 6.2 概率图模型在医学图像中的应用
    • 6.3 概率图模型在计算机视觉中的应用

推荐教材及书籍

  • Koller D, Friedman N. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. :star::star::star: :star::star::star:
  • 王飞跃，韩素青的翻译版《概率图模型-原理与技术》
  • Christopher M. Bishop. "Pattern Recognition and Machine Learning". Springer 2006.
  • J. Pearl. "Probabilistic Reasonnig in Intelligent Systems: Networks of Plausible Inference". Morgan Kaufmann. 1988.

综述

  • Wainwright M J, Jordan M I. Graphical Models, Exponential Families, and Variational Inference. Found. Trends Mach. Learn. 2008, 1:1-305.
  • 程强等，概率图模型中的变分近似推理方法，自动化学报， 2014.
  • 张弘毅， 王立威， 陈瑜希。概率图模型研究进展综述， 软件学报， 2013.

相关网站

课程预期收获

  • 理解概率图模型的理论框架。
  • 熟悉概率图模型的表示原理，熟悉主流概率推理算法，了解概率图模型的学习。
  • 了解概率图模型的典型应用案例，包括自然语言处理（如命名实体识别）、计算机视觉（如图像分割、立体视觉、姿态估计等）。
  • 利用概率图模型解决一些实际问题。
Last modification：March 25th, 2020 at 08:12 pm
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏