C08. 图模型

使用图形表示概率分布对于分析很有好处，这种概率分布的图形表示被称为概率图模型 (Probabilisticc Graphical Models, PGM)。

• 概率图模型的优点：
  • 提供了一种简单的方式将概率模型的结构可视化，方便设计新的模型；
  • 通过观察图形，可以更深刻地认识模型的性质，包括：条件独立性质；
  • 高级模型的推断和学习中的复杂计算可以根据图计算来表达，图隐式地承载了背后的数学公式。
• “图” 的基本元素
  • 结点 (nodes)，也被称为端点 (vertices)。
  • 链接 (links)，也被称为边 (edges) 或弧 (arcs)，用于连接结点。
  • 有向图 (directed graphical)：图中的链接有一个特定的方向，使用箭头表示。
    • 有向无环图 (Directed Acyclic Graph, DAG)：不能存在有向环 (directed cycle)。在图中不能存在这样的路径：从某个结点开始，沿着链接中箭头的方向运动，结点为起点。
  • 无向图 (undirected graphical): 图中的链接没有箭头，没有方向性质。
  • 全连接图 (fully connected)：每对结点之间都存在一个链接。
  • 团块 (clique)：图中结点的一个子集，使得在这个子集中的每对结点之间都存在链接，即团块中的结点是全连接的。
    • 最大团块：不可能将图中的任何一个其他的结点包含到这个团块中而不破坏团块的性质。
• “概率图” 的基本元素
  • 每个结点表示一个随机变量（或一组随机变量）
  • 每条链接表示这些变量之间的概率关系。
  • 概率图描述了在所有随机变量上联合概率分布能够分解为一组因子的乘积的方式
    • 每个因子只依赖于对应的一个子集
  • 有向图模型，也叫贝叶斯网络。用于表达随机变量之间的因果关系。
  • 无向图模型，也叫 Markov 随机场。用于表达随机变量之间的软限制。
  • 因子图 (factor graph)：将有向图和无向图转化为因子图，用于求解推断问题。

前言

• 重点
  • 贝叶斯网络 [^张连文，2006]
  • Markov 随机场 [^Kindermann, 1980]
  • d- 划分
  • 因子图
• 难点
  • 伦理图：有向图转化为无向图
  • 图模型中的推断
    • 链推断
    • 加和—乘积算法
    • 最大加和算法
• 学习基础
  • 图论
  • 概率与统计
• 学习要点

S8.1. 贝叶斯网络

• 多项式回归（掌握有向概率图模型的表示）
• 生成式模型（掌握有向概率图模型表示生成式模型的方法）
• 指数族概率分布（掌握有向概率图模型表示共轭结点对的方法）
  • 离散变量（表达成概率图模型后的观察可得）
    • 对于 M 个变量的任意一个联合概率分布，需要确定的参数的数量为 $K^M-1$ 个，即参数的数量随着变量的数量指数增长。
    • 减少参数数量的方法
      • 删除结点之间链接的方式；
      • 减少模型中独立参数数量，即参数共享 (sharing)，也叫参数捆扎 (tying)。
    • 引入参数的 Dirichlet 先验，可以将离散变量上的图模型转化为贝叶斯模型
  • 高斯变量
    • 协方差矩阵的计算
      • 图中不存在链接，表示独立的一元高斯分布组成的集合；
      • 全连接的图，对应于一般的对称协方差矩阵。
    • 超先验 (hyperprior)：在超参数上定义一个先验概率分布，后验依然还是高斯分布。不断延伸到任意层次，即层次贝叶斯模型 (hierarchical Bayesian model)。

S8.2. 条件独立

• 联合概率分布的条件独立性可以直接在图中表示出来，不用进行任何计算。完成这件事的通用框架被称为 “d—划分”(d-separation)，其中 “d” 表示 “有向 (directed)”。
• 图的三个例子（条件独立性的不同解读，需要理解并记忆，方便后面的学习）
• d—划分
  • 使用条件独立性假设来简化朴素贝叶斯模型的图结构
  • Markov 毯或者 Markov 边界：由父结点、子结点、同父结点组成的结点集合。

S8.3. Markov 随机场

• Markov 随机场 (Markov Random Field)，也叫 Markov 网络（Markov Network），或者无向图模型（Undirected Graphical Model）。包含一组结点，每个结点都对应着一个变量或一组变量，结点之间的链接是无向的（即不含有箭头）。
• 条件独立性质
  • 联合概率分布可以表示为图中最大团块的势函数 (potential function) 的乘积的形式。$p(\mathbf{x})=\frac{1}{Z}\underset{C}{\prod}\psi_C(\mathbf{x}_C)$
    • 划分函数 (partition function)：$Z$是一个归一化常数。
      • 能量函数 (energy function)：$E(X_C)$
      • 指数表示被称为玻尔兹曼分布 (Boltzmann distribution)
      • 联合概率分布定义为势函数的乘积，因此总的能量可以通过将每个团块的能量相加得到。
    • 势函数可以表示为指数的形式 $\psi_C(X_C)=\exp{-E(X_C)}$
• 图像去噪（如果无法理解，直接参考 Markov 随机场的论文）
• 与有向图之间的关系
  • 伦理 (moralization)：使父结点结合在一起。
    • 过程增加了最少的额外链接，保持了最大的条件独立性质
  • 通过伦理过程，将有向图去掉箭头后生成的无向图称为道德图 (moral graph)。
  • 有向图转化为无向图的过程
    • 将图中每个结点的所有父结点之间添加额外的无向链接，然后去掉原始链接的箭头，得到道德图
    • 将道德图的所有团块势函数初始化为 1
    • 拿出原始有向图中所有的条件概率分布因子，将它乘以团块势函数
  • 将有向图转化为无向图是精确推断的重要基础，例如：联合树算法
  • 将无向图转化为有向图用途较少，通常表示归一化限制中出现的问题。
• 概率分布的 D 图：如果一个概率分布中的所有条件独立性质都通过一个图反映出来，那么这个图被称为概率分布的 D 图，即依赖图 (dependency map)。
  • 因此一个完全非连接的图（不存在链接）是任意概率分布的平凡 D 图。
• 概率分布的 I 图：如果一个图的每个条件独立性质都可以由一个具体的概率分布满足，那么这个图被称为概率分布的 I 图，即独立图 (independence map)。
  • 一个完全连接的图是任意概率分布的平凡 I 图。
• 完美图：如果概率分布的每个条件独立性质都可以由图反映出来，那么这个图被称为概率分布的完美图 (perfect map)。
  • 一个完美图既是 I 图，也是 D 图。
• 链图 (Chain graphs)：是一种相容方式的图框架，能够同时包含有向链接和无向链接的图。
  • 依然存在某些概率分布，即使使用链图也无法表达成完美图。

S8.4. 图模型中的推断

• 图模型中的推断问题：图中的一些结点被限制为观测值，需要利用图结构找到高效的推断算法，计算其他结点中的一个或者多个子集的后验概率分布。

  • 精确推断（S8.4）
    • 一般图的精确推断
  • 近似推断（C10）

• 链推断（精确推断的基础）

  • 对势函数的求和式进行分组
  • 使用图中局部信息传递的思想，信息采用递归计算的方法
  • 完成了计算边缘概率分布所需要的信息传递，就可以直接得到每个势函数中的所有变量上的联合概率分布。（P277 E8.58）

• 树

  • 在无向图中，树的任意一对结点之间有且只有一条路径；因此这样的图没有环。
  • 在有向图中，树拥有一个没有父结点的结点，被称为根，其他所有的结点都有一个父结点。
    • 如果有向图中存在具有多个父结点的结点，但是在任意两个结点仍然只有一条路径，那么称为多树 (polytree)
  • 如果把有向图转化为无向图，经过 “伦理” 步骤后不会增加任何链接，因为所有的结点至多只有一个父结点，从而对应的道德图就是一个无向图。
  • 如果局部信息可以在一种称为树的图中传递，那么推断地执行会更加高效
    • 将有向树或者无向树转化为因子图后还是树
    • 在有向多树的图中，转化后的因子图仍然是树
      • 对于有向多树的图，由于 “伦理” 步骤的存在，转化为无向图会引入环

• 因子图（用于推导加和—乘积算法）

  • 有向图和无向图都使得若干个变量的一个全局函数能够表示为这些变量的子集上的因子的乘积。
    • 因子图可以显式地表示出这个分解。
    • 在表示变量的结点的基础上，引入额外的结点表示因子本身
    • 因子图也使分解的细节表示得更加清晰。
    • 无向图表示为因子图。对应原始的无向图构造变量结点，对应最大团块构造额外的因子结点，因子被设置为与团块势函数相等
      • 同一个无向图可能存在不同的因子图
    • 有向图表示为因子图。对应原始的有向图构造变量结点，对应条件概率分布构造额外的因子结点，添加上合适的链接
      • 同一个有向图可能存在不同的因子图
  • 因子图由两类不同的结点组成，且所有的链接都位于两类不同的结点之间，因此因子图被称为二分的 (bipartite)

• 加和—乘积算法 (sum-product algorithm)（计算结点或者结点子集上的局部边缘概率分布）

  • 算法适用于模型中所有的变量都是离散的，因此求边缘概率对应于求和的过程。
  • 算法也适用于线性高斯模型，因此求边缘概率对应于求积分的过程。
  • 假设原始的图是一个无向树或者有向树或者多树，从而对应的因子图有一个树结构。
    • 将原始的图转化为因子图
    • 利用图的结构实现的目标
      • 得到一个高效的精确推断算法来寻找边缘概率
      • 需要求解多个边缘概率的时候，计算可以高效的共享
    • 算法的具体步骤（先推导公式，再看（P284）例子，最后看文字会更容易明白）
      • 对于特定的变量结点，寻找边缘概率
        • 边缘概率通过对所有结点（除特定的变量结点之外）的变量上的联合概率分布进行求和得到
      • 利用因子图的表达式替换掉联合概率分布
      • 交换加和和乘积的顺序，得到一个高效的算法
      • 引入两类信息
        • 一类信息是从因子结点到变量结点的信息
          • 需要求解的边缘概率分布等于所有输入信息的乘积
        • 一类信息是从变量结点到因子结点的信息
          • 所有进入因子结点的其他链接的输入信息的乘积，乘以那个结点关联的因子，然后对所有与输入信息关联的变量进行求和
    • 算法的总结
      • 将变量结点看成因子图的根结点
      • 递归地应用信息传递步骤，直到信息被沿着每个链接传递完毕，并且根结点收到所有相信结点的信息
      • 需要求解的边缘概率分布就可以依据公式 (P282 E8.63) 计算。

• 最大加和算法 (max-sum algorithm)（寻找概率的最大状态）

  • 图模型的两个常见任务

    1. 找到变量的具有最大概率的一个设置
    2. 找到这个概率的值

    这两个任务可以通过一个算法完成，即最大加和算法，是动态规划在图模型中的应用

  • 最大加和算法在 HMM 模型中的应用是 Viterbi 算法

    （这节文字太多，不容易理解，建议参考 HMM 模型中的 Viterbi 算法介绍 [^Rabiner, 1989]）

• 联合树算法 (junction tree algorithm)

  信息传递框架可以被推广到任意的图拓扑结构，得到一个精确的推断步骤。

• 近似推断

  • 变分 (variational) 方法（C10）
  • 取样 (sampling) 方法，也叫蒙特卡罗 (Monte Carlo) 方法（C11）
  • 循环置信传播 (loopy belief propagation)（有向无环图的近似推断）
    • 等价于加和—乘积算法的一个具体形式。
    • 对于特定类型的误差修正编码的最好解码算法等价于循环转储传播算法。

• 学习图结构

  • 目标：从数据中推断图的结构
  • 定义
    • 一个所有可能出现的图结构的空间
    • 用于对每个图结构评分的度量

S08. 小结

图模型是模型构建和模型推断的理论基础。