概率图模型 Probabilistic Graphical Model（PGM） / 图模型 Graphical Model（GM）：用图结构来描述多元随机变量之间条件独立关系的概率模型，从而给研究高维空间中的概率模型带来了很大的便捷性
概率图模型最基本的假设：条件独立性

• 独立性假设是一种有效减少参数量的方法

K 维随机向量 ，假设每个变量有 M 个取值

• 其联合概率 为高维空间中的分布，一般难以直接建模
  • 不作任何独立性假设：需要 个参数才能表示其概率分布
  • 独立性假设：某些变量之间存在条件独立，则参数量可以大幅减少

例：
，每个变量有 2 个取值（二值变量）
联合概率

• 独立性未知（不作独立性假设）：需要 个参数
• 独立性假设：如图 11.1 所示，在已知 时 和 独立，在已知 和 时 和 独立
  • ，需要 个独立参数

图模型的三个基本问题：

• 模型表示问题：通过图结构（有向图、无向图）描述概率模型的变量之间的依赖关系
• 学习问题：图结构的学习、给定图结构时参数的学习（参数估计问题）

• 推断问题：已知部分变量时，计算其他变量的条件概率分布 图模型与机器学习：很多机器学习模型都可以归结为概率模型，即建模输入和输出之间的条件概率分布

• 优点：便于了解不同机器学习模型之间的联系，方便设计新模型

11.1 模型表示

概率图模型：

• 节点：表示一个/一组随机变量
• 边：表示随机变量之间的概率依赖关系 | 概率图模型 | 描述 | 含义 | | —- | —- | —- | | 有向图模型
  （贝叶斯网络、信念网络） | 有向非循环图 | 有向边表示因果关系：因→果，即不存在其它变量使得这两个节点对应的变量条件独立 | | 无向图模型
  （马尔可夫随机场） | 无向图 | 边代表两个变量之间的概率依赖关系（不一定为因果关系） |

11.1.1 有向图模型

局部马尔可夫性质：每个随机变量在给定父节点的情况下，条件独立于它的非后代节点

• , Z 为 的非后代变量

有向图模型（贝叶斯网络 / 信念网络）：用有向图描述随机向量概率分布的模型

• 贝叶斯网络，X 的联合概率分布 可以分解为每个随机变量 的局部条件概率分布 的连乘形式： ( 表示变量 的所有父节点变量的集合)

条件独立性：

11.1.2 常见的有向图模型

11.1.2.1 Sigmoid 信念网络 SBN

更复杂的深度信念网络：
第 12 章 深度信念网络

参数化模型：为了减少模型参数，可以使用参数化模型来建模有向图模型中的条件概率分布
Sigmoid 信念网络：一种简单的参数化模型

• 变量取值 {0, 1}
• 条件概率分布
• 参数数量：（假设变量 的父节点数量为 M）
  • 使用表格记录条件概率：个参数
  • 使用参数化模型：M+1 个参数（如果对不同变量的条件概率共享一个参数化模型，则参数数量还能大幅减少）

Sigmoid 信念网络和 Logistic 回归模型的区别：

• Logistic 回归模型中的 x 作为一种确定性的参数，而非变量
• Logistic 回归模型只建模条件概率 ，是一种判别模型；而 Sigmoid 信念网络建模联合概率 ，是一种生成模型

11.1.2.2 朴素贝叶斯分类器

贝叶斯公式：

朴素贝叶斯分类器：在强（朴素）独立性假设的条件下用贝叶斯公式计算每个类别的条件概率

• 条件概率分布 (样本X 有 M 维特征)

  • 若 为连续值， 可以用高斯分布建模
  • 若 为离散值， 可以用多项分布建模

• 缺点：朴素贝叶斯分类器的条件独立性假设太强

• 优点：实际在很多任务上能得到很好的结果，并且模型简单，可以有效防止过拟合

11.1.2.3 隐马尔可夫模型 HMM

隐马尔可夫模型：用来表示一种含有隐变量的马尔可夫过程

联合概率

• 方便起见， 表示

11.1.3 无向图模型

无向图 / 马尔可夫随机场 MRF / 马尔可夫网络：用无向图描述一组具有局部马尔可夫性质的随机向量 X 的联合概率分布的模型

• 随机向量
• K 个节点的无向图
• 构成马尔可夫随机场 → 满足局部马尔可夫性质，即一个变量 在给定它的邻居的情况下独立于所有其他变量：
  • 为变量 的邻居集合， 为除 外其他变量的集合

无向图的局部马尔可夫性质：，即一个变量 在给定它的邻居的情况下独立于所有其他变量

11.1.4 无向图模型的概率分解

无向图模型的联合概率可以分解为一些列定义在最大团上的非负函数（势能函数）的乘积形式 （Hammersley-Clifford 定理）

• 即分布 ，也称为吉布斯分布
• 是无向图 G 中的最大团集合
• 是定义在团 c 上的势能函数
  • 一般定义为
  • 能量函数
• 配分函数 ，用来将乘积归一化为概率形式

玻尔兹曼分布：将能量函数代入无向图的联合概率分布

11.1.5 常见的无向图模型

11.1.5.1 对数线性模型 / 最大熵模型

对数线性模型，也称为 最大熵模型、条件最大熵模型、Softmax 回归模型

• 势能函数
  • 为定义在 上的特征向量， 为权重向量
• 联合概率分布的对数形式
• 条件概率
  • 

11.1.5.2 条件随机场

条件随机场：条件概率 中 y 一般为随机向量，因此需对条件概率 进行因子分解

• 条件概率

线性链条件随机场：

• 条件概率
  • 状态特征 ，一般和位置 t 相关
  • 转移特征 ，一般可简化为 并使用状态转移矩阵来表示

11.1.6 有向图和无向图之间的转换

有向图和无向图可以相互转换

• 无向图 转换为 有向图：通常比较困难
• 有向图 转换为 无向图：实际应用，可以利用无向图上的精确推断算法

有向图转化为无向图：

• 无向图模型可以表示有向图模型无法表示的一些依赖关系，eg. 循环依赖
• 但无向图模型不能表示有向图模型的某些关系，eg. 因果关系
• 道德化：无向图转换为有向图的过程，原本有向图中的一些独立性会丢失

11.2 学习

11.2.1 不含隐变量的参数估计

如果图模型中不包含隐变量，即所有变量都是可观测的，那么网络参数一般可以直接通过最大似然进行估计

有向图模型：

• 给定 N 个训练样本
• 对数似然函数
• 最大化对数似然，只需分别最大化每个变量的条件似然来估计参数
  • 
• 若变量 x 是离散的：可以用参数化的模型（eg. Sigmoid 信念网络）表示各变量的条件概率
• 若变量 x 是连续的：可以用高斯函数表示条件概率分布，称为高斯信念网络
• 进一步减少参数量：让所有条件概率分布共享同一组参数

无向图模型：

• 以对数线性模型为例
• 
  • 经验分布
• 无向图的最大似然估计的优化目标等价于：对于每个团 c 上的特征 ，使得其在经验分布 下的期望等于其在模型分布 下的期望
• 往往很难计算，因此无向图的参数估计通常采用近似的方法：
  • 利用采样来近似计算这个期望
  • 采用坐标上升法，即固定其他参数，来优化一个势能函数的参数

无向图和有向图模型参数估计的差别：无向图模型的参数估计更复杂

• 有向图中，每个局部条件概率的参数是独立的
• 无向图中，所有的参数都是相关的，无法分解

11.2.2 含隐变量的参数估计

如果图模型中包含隐变量，即有部分变量是不可观测的，就需要用 EM 算法进行参数估计

11.2.2.1 EM 算法（期望最大化算法）

包含隐变量的图模型：

• 可观测变量集合 X
• 隐变量集合 Z
• 样本 x 的边际似然函数 / 证据：

• 整个训练集的对数边际似然：
• 样本 x 的对数边际似然函数：
  • 变分函数 ：是定义在隐变量 Z 上的分布
  • 证据下界 ：是对数边际似然函数 的下界
  • 仅当 时，

EM 算法的两个步骤：两步不断重复迭代，直到收敛到某个局部最优解
第 t 步更新迭代：

• E 步（Expectation Step）：固定参数 ，找到一个近似分布 使得
  • 等式成立当且仅当 ，但后验分布 很难计算，需使用变分推断近似估计
• M 步（Maximization Step）：固定 ，找到一组参数 最大化
  • 

11.2.2.2 高斯混合模型 GMM（EM 算法的应用例子）

高斯混合模型 GMM：是由多个高斯分布组成的模型，其总体密度函数为多个高斯密度函数的加权组合

• 如果一个连续随机变量或连续随机向量的分布比较复杂，那么通常可以用高斯混合模型来估计其分布情况

一维的情况（假设样本 x 服从第 k 个分布（无法直接观测到））

• 表示样本 x 由第 k 个高斯分布生成的概率
• 条件分布 为高斯分布：
  • 分别为第 k 个高斯分布的均值和方差
• ∴ 随机变量 x 的概率密度函数

从高斯混合模型中生成一个样本 x 的两步过程：

• 根据多项分布 （样本 x 由第 k 个高斯分布生成的概率）随机选取一个高斯分布
• 假设选中第 k 个高斯分布（z=k），再从高斯分布 中选取一个样本 x

参数估计：

• 样本 的对数边际分布
• EM 算法两步迭代估计参数：
  • E 步：固定参数 ，计算后验分布 （样本 x 属于第 k 个高斯分布的后验概率）
  • M 步：令
    • 
    • 参数估计
      • 
      • 
      • 

11.3 推断

推断：观测到部分变量 e 时计算其他变量的某个子集 q 的条件概率

• z：图模型中除变量 e、q 外的其余变量
• 
• 即 图模型的推断问题的关键为：求任意一个变量子集的边际概率分布问题

11.3.1 精确推断

精确推断算法：可以计算出条件概率 的精确解的算法

11.3.1.1 变量消除法

变量消除法：利用动态规划的思想，每次消除一个变量，来减少计算边际分布的计算复杂度

例：

求上图中的后验概率 ，需计算边际概率 和

• 
  • 每个变量 K 个取值，则需要 次加法和 次乘法
• 
  • 计算量减少到 次加法和 次乘法
  • 原理：乘法分配律

变量消除法的缺点：计算多个边际分布时存在很多重复的计算

11.3.1.2 信念传播算法 BP

信念传播算法 BP / 和积算法 / 消息传递算法：将变量消除法中的和积操作看作消息，并保存起来，节省大量的重复计算

链式结构图模型的消息传递过程：

• 依次计算前向传递的消息
• 以此计算反向传递的消息
• 在任意节点 t 上计算配分函数

计算所有变量的边际概率

树结构图模型的消息传递过程（若图结构中存在环路，可以使用联合树算法将图结构转换为无环图）：

• 从叶子节点到根节点，依次计算并传递消息
• 从根节点到叶子节点，依次计算并传递消息
• 在每个节点上计算所有接收消息的乘积（如果是无向图还需要归一化），就得到了所有变量的边际概率

11.3.2 近似推断

近似推断：适用于图模型结构复杂、精确推断计算开销大的情况 or 无法使用精确推断的情况

近似推断的主要方法：

• 环路信念传播：使得可以在据有环路的图上依然使用信念传播算法，即使得到不精确解，在某些任务上也可以得到近似精确解
• 变分推断：引入一个（比较简单的）变分分布来近似比较复杂的条件概率，然后通过迭代的方法进行计算
  • 首先是更新变分分布的参数来最小化变分分布和真实分布的差异（eg. 交叉熵 or KL 距离），然后再根据变分分布来进行推断
• 采样法：通过模拟的方式采集符合某个分布 p(x) 的一些样本，并用这些样本来估计和分布 p(x) 有关的运算（eg. 期望）

11.4 变分推断

泛函 ：函数的函数，即输入时函数，输出是实数，但要求输入的 满足一定的边界条件，并且具有连续的二阶导数

• eg. 熵：输入是一个概率分布 p(x)，输出是该分布的不确定性（熵）

变分法：研究变分问题，即泛函的极值问题。寻找一个 使得泛函 取得极大或极小值

设一个贝叶斯模型中，x 为一组观测变量，z 为一组隐变量（包含参数），推断问题为计算条件概率密度
变分推断 / 变分贝叶斯：寻找一个简单分布 来近似条件概率密度

• 推断问题转换为一个泛函优化问题
  • 为候选的概率分布族
• 变分推断可以处理 EM 算法不能精确推断 的情况（E 步中让 ）
• 优化问题转换为寻找一个简单分布 来最大化证据下界
  • 

11.5 基于采样法的近似推断

很多实际的机器学习任务中，推断某个概率分布后，还要基于这个概率分布进一步计算并作出决策，且通常这些计算和期望有关

• 要推断的概率分布
• 计算函数 的期望
• 当 比较复杂或难以精确推断时，可以通过采样法来近似计算期望 的解

11.5.1 采样法

采样法 / 蒙特卡罗方法 / 统计模拟方法，通过随机采样来近似估计一些计算问题数值解

• 随机采样：指从给定概率密度函数 中抽取出符合其概率分布的样本

• 采样法的难点：如何进行随机采样，即如何让计算机生成满足概率密度函数 的样本

  • 间接采样策略：先根据一个比较容易采样的分布进行采样，然后通过一些策略来间接得到符合 分布的样本
    • eg. 拒绝采样、重要性采样、马尔可夫链蒙特卡罗采样等 以上面提到的计算期望 为例：

• 从 中独立抽取 N 个样本

• 期望 可以用 N 个样本的均值 来近似
• 当 N 趋向于无穷大时，样本均值收敛于期望值

11.5.2 拒绝采样

拒绝采样 / 接受-拒绝采样：引入一个容易采样的 提议分布（参考分布），然后以某个标准拒绝一部分的样本，使得最终采集的样本服从分布

• 构建一个提议分布 和常数 k，使得 可以覆盖函数 ，即

• 对于每次抽取的样本 ，计算接受概率 ，并以概率 来接受样本

• 采样效率：用于判断一个拒绝采样方法的好坏，即总体的接受率
  • 提议分布 和 越接近，采样效率越高，但实际很难找到接近的提议分布

11.5.3 重要性采样

重要性采样：如果采样的目的是计算分布 下函数 的期望，那么可以直接通过采样提议分布 来估计期望

• 通过引入重要性权重，将分布 下 的期望变为在提议分布 下 的期望
• 期望 可以用从 随机抽取的 N 个样本的均值 来近似

11.5.4 马尔可夫链蒙特卡罗方法 MCMC

马尔可夫链蒙特卡罗方法的优点：

• 可以很容易地对高维变量进行采样（作为对比，拒绝采样和重要性采样的效率随空间维数的增加而指数降低）

马尔可夫链蒙特卡罗方法 MCMC：将采样过程看作一个马尔可夫链 ，第 t+1 次采样依赖于第 t 次抽取的样本 以及状态转移分布（即提议分布）。如果这个马尔可夫链的平稳分布为 ，那么在状态平稳时抽取的样本就是服从 的分布
MCMC方法的关键：如何构造出平稳分布为 的马尔可夫链，并且该马尔可夫链的状态转移分布 一般为比较容易采样的分布

• 当 x 是离散变量时， 可以是一个状态转移矩阵
• 当 x 是连续变量时， 可以是参数密度函数

使用 MCMC 方法采样时需要注意两点：

• 马尔可夫链需要经过一段时间（即预烧期）的随机游走才能达到平稳状态，预烧期内的采样点并不服从分布 ，需要丢弃
• 基于马尔可夫链抽取的相邻样本是高度相关的，而在机器学习中一般要抽取的样本是独立同分布的
  • 为了使得抽取的样本之间独立，可以每隔 M 次随机游走，抽取一个样本（如果 M 足够大，可以认为抽取的样本是独立的）

11.5.4.1 Metropolis-Hastings 算法

MH 算法：引入拒绝采样的思想来修正提议分布（状态转移分布） ，使得最终采样的分布为

• 假设第 t 次采样的样本为
• 根据提议分布 抽取一个样本 ，并以概率 来接受 作为第 t+1 次的采样样本
• 所以修正的马尔可夫链状态转移概率为 ，修正的马尔可夫链可以达到平稳状态，即平稳分布为

11.5.4.2 Metropolis 算法

在 MH 算法的基础上，若提议分布为对称的 ，即 ，则第 t+1 次采样的接受率可以简化为

11.5.4.3 吉布斯采样

吉布斯采样：是 MH 算法的特例，使用全条件概率作为提议分布来依次对每个维度进行采样，并设置接受率 A=1

11.6 总结和深入阅读

概率图模型提供了一个用图形来描述概率模型的框架，这种可视化方法使我们可以更容易地理解复杂模型的内在性质

概率图模型中最基本的假设：条件独立性

图模型与神经网络的关系：

• 网络结构：
  • 图模型的节点是随机变量，其图结构的主要功能是描述变量之间的依赖关系，一般是稀疏连接。使用图模型的好处是可以有效地进行统计推断。图模型中的每个变量一般有着明确的解释，变量之间的依赖关系一般是人工来定义
  • 神经网络中的节点是神经元，是一个计算节点。神经网络中的单个神经元没有直观的解释
  • 如果将神经网络中的每个神经元看作一个二值随机变量，那么神经网络就变成一个 Sigmoid 信念网络
• 判别模型 / 生成模型：
  • 神经网络是判别模型，用来分类。神经网络参数学习的目标函数为交叉熵或平方误差等损失函数
  • 图模型不但可以是判别模型，也可以是生成模型。生成模型不但可以用来生成样本，也可以通过贝叶斯公式用来做分类。图模型的参数学习的目标函数为似然函数或条件似然函数，若包含隐变量则通常通过 EM 算法来求解
• 神经网络和概率图模型的结合也越来越紧密;
  • 一方面可以利用神经网络强大的表示能力和拟合能力来建模图模型中的推断问题
    • eg. 变分自编码器、生成问题（eg. 生成对抗网络）、势能函数（eg. LSTM+CRF 模型）
  • 另一方面可以利用图模型的算法来解决复杂结构神经网络中的学习和推断问题
    • eg. 图神经网络 GNN、结构化注意力

习题

习题 11-1 根据贝叶斯网络的定义，证明图11.3中的四种因果关系

习题 11-2 证明公式(11.9)

习题 11-3 根据公式(11.37)，推导线性链条件随机场（ 参见公式(11.25)）的参数更新公式

习题 11-4 证明仅当𝑞(𝒛) = 𝑝(𝒛|𝒙; 𝜃)时，对数边际似然函数log 𝑝(𝒙; 𝜃)和其下界𝐸𝐿𝐵𝑂(𝑞, 𝒙; 𝜃)相等

习题 11-5 在高斯混合分布的参数估计中， 证明 M 步中的参数更新公式， 即公式(11.63)、公式(11.64)和公式(11.65)

习题 11-6 考虑一个伯努利混合分布， 即 ，其中 为伯努利分布。给定一组训练集合 ，若用 EM 算法来进行参数估计，推导其每步的参数更新公式

习题 11-7 在变分推断的目标公式(11.82)中， 试分析为什么使用的 KL 散度是KL (𝑞(𝒛)‖𝑝(𝒛|𝒙))而不是KL (𝑝(𝒛|𝒙)‖𝑞(𝒛))

习题 11-8 在图11.2a的有向图中， 分析按不同的消除顺序计算边际概率时的计算复杂度

习题 11-9 在树结构的图模型上应用信念传播算法时，推导其消息计算公式

习题 11-10 证明若分布𝑝(𝑥)存在累积分布函数的逆函数，且随机变量𝜉 为[0, 1]区间上的均匀分布， 则服从分布𝑝(𝑥)．