On the Relationship Between Monotone and Squared Probabilistic Circuits

从单调到平方：概率电路的关系探秘

https://arxiv.org/pdf/2408.00876

摘要
概率电路是一种将函数表示为加权和与乘积的计算图的统一体。它们的主要应用在于概率建模，其中具有非负权重的概率电路（单调电路）可以用来表示和学习密度/质量函数，并且能够进行可追踪的边缘推理。最近，有人提出将密度表示为电路函数的平方（平方电路），这种方法允许使用负权重同时保持可追踪性，并且在表达效率上可能比单调电路指数级更高效。然而，我们发现反过来也成立，这意味着单调电路和平方电路在一般情况下是无法比较的。这引发了一个问题：我们是否可以调和这两种建模方法，并且确实能改进它们？通过提出Inception PCs，一种新型的电路模型，我们给出了肯定的回答。Inception PCs自然地包含了单调电路和平方电路作为特例，并采用了复数参数。从实验上，我们验证了Inception PCs可以在多种表格数据和图像数据集上优于单调电路和平方电路。

代码 — https://github.com/wangben88/InceptionPCs

1 引言

可追踪概率建模（tractable probabilistic modeling）的理念主张通过设计支持对各种概率查询进行精确且高效推理的模型架构，来建模高维概率分布。这一特性使得它们在概率推理中极为有用；例如，可追踪模型已被广泛应用于增强和控制不可追踪生成模型（Zhang 等，2023；Liu, Niepert 和 Van den Broeck，2024），神经符号人工智能（Ahmed 等，2022；Ahmed, Chang 和 Van den Broeck，2023），以及因果发现与推理（Wang, Wicker 和 Kwiatkowska，2022；Wang 和 Kwiatkowska，2023）。

可追踪模型的通用语言是概率电路框架（Probabilistic Circuits，简称 PC）（Choi, Vergari 和 Van den Broeck，2020），该框架使用加法和乘法的计算图来定义函数，统一了许多先前的可追踪模型，如算术电路（Arithmetic Circuits）（Darwiche，2003）、和积网络（Sum-Product Networks）（Poon 和 Domingos，2011）以及割集网络（Cutset Networks）（Rahman, Kothalkar 和 Gogate，2014）。标准的建模方法是直接使用一个PC来表示概率分布（密度/质量函数）。为了确保PC输出的非负性，通常限制其参数为非负值；这些被称为单调PC（Monotone PCs）（Darwiche，2003；Poon 和 Domingos，2011）。然而，最近的研究表明，存在许多可追踪的概率分布类别是无法用这种方式表达的（Zhang, Holtzen 和 Van den Broeck，2020；Yu, Trapp 和 Kersting，2023；Broadrick, Zhang 和 Van den Broeck，2024）。

这促使人们探索新的实用方法来构建和学习广义的可追踪模型。为此，Loconte 等人（2024b）最近提出了平方电路（Squared Circuits），其中概率分布被定义为（正比于）电路函数的平方。在这种形式下，PC可以使用实数（甚至负数）参数，同时仍然定义一个有效的概率分布。理论上已经证明，在某些分布类别上，这种方法相比单调PC具有指数级的表达效率优势。

在本文中，我们重新审视了单调电路和（结构可分解的）平方电路，并表明它们在一般情况下是不可比较的：任一者都可能比另一者在表达效率上指数级更优。受此观察启发，我们借鉴了PCs的潜在变量解释（Peharz 等，2016），并揭示了这两种电路之间的一种优雅联系：它们分别对应于将潜变量求和操作放在平方外部或内部，即“深度的和的平方”或“平方的和”。通过结合这两类潜变量，我们提出了一种新型的可追踪模型——深度的和的平方的平方（deep sum-of-square-of-sums），我们称之为 Inception PC（IncPC），它严格地推广并扩展了（结构可分解的）单调PC和平方PC。

我们进一步研究了如何有效地大规模学习Inception PC。沿袭PC学习的最新趋势（Peharz 等，2020b,a；Liu 和 Van den Broeck，2021；Mari, Vessio 和 Vergari，2023），我们设计了一个高效的张量化实现方案，能够统一处理张量化的（结构可分解的）单调PC和平方PC。实验结果验证了Inception PC在密度估计基准任务中表现出了更高的表达效率。

我们的贡献可以总结如下：

  • 理论上，我们展示了一个简单的分布类别，在该类别中单调电路可能比平方电路小指数级，这意味着在表达效率方面，单调电路和平方电路在一般情况下是不可比较的（第3节）；

  • 我们从潜在变量视角对单调电路和平方电路进行了分析，表明它们分别可以被解释为“深度的和的平方”（sums-of-squares）和“平方的和”（squares-of-sums）。在此基础上，我们提出了一种新型的可追踪电路模型——Inception PCs（IncPC），它将这两种电路统一起来并加以扩展，形成一种“深度的和的平方的平方”（deep sum-of-square-of-sums）结构，并可以使用复数参数（第4节）；

  • 我们为 Inception PC 提出了一个高效的张量化架构设计，使其能够应用于大规模数据集（第5节）；

  • 实验上，我们展示了：(i) 结合两种类型的潜变量并引入复数参数可以提升模型性能；(ii) 在包括降尺度版 ImageNet 在内的多个具有挑战性的基准任务上，即使考虑计算时间归一化的情况下，Inception PC 也能优于单调电路和平方电路（第7节）。

在同期的研究工作中，Loconte、Mengel 和 Vergari（2025）也使用类似的函数族证明了单调电路与平方电路之间的指数级差异（即我们的定理2）。他们还提出了两种新的模型类别——SOCS 和 µSOCS，用于推广平方电路。我们在附录A中详细讨论了这些模型与我们的 Inception PC 的联系。

2 预备知识

记号：我们使用大写字母表示变量，小写字母表示它们的赋值/取值（例如，X，x）。我们使用粗体字母（例如，X，x）表示变量集合或赋值集合。

概率电路是一种计算图，用于表示通过加权和与乘积的层次化组合所构建的函数。

其中每个和节点具有一组权重 {θₙ,ₙᵢ}ₙᵢ∈in(n)，其中 θₙ,ₙᵢ ∈ ℝ。每个节点 n 都表示关于一组变量 sc(n) 的函数，我们称 sc(n) 为该节点的作用域（scope）；对于内部节点，其作用域定义为 sc(n) = ∪ₙᵢ∈in(n) sc(nᵢ)。整个概率电路 f_C 所表示的函数，即为其根节点所表示的函数。一个概率电路 |C| 的大小定义为其有向无环图（DAG）中的边的数量。

在本文中，我们假设和节点与积节点是交替出现的；这一假设不失一般性，因为可以通过最多线性增加电路大小的方式，使任意概率电路满足这一性质。

概率电路的和-积结构的一个关键特性是，它允许高效地（线性时间）计算边缘分布，例如配分函数，前提是电路是平滑（smooth）且可分解（decomposable）的：

定义 2（平滑性，可分解性）：一个概率电路是平滑的，如果对于每一个和节点 n，它的输入节点 ni 具有相同的作用域（scope）。一个概率电路是可分解的，如果对于每一个积节点 n，它的输入节点具有互不重叠的作用域。

我们还需要一种更强的可分解性形式，它使得多个电路可以被高效地相乘（Pipatsrisawat 和 Darwiche，2008；Vergari 等，2021）：

定义 3（结构化可分解性）：一个平滑且可分解的概率电路被称为结构化可分解的，如果任意两个作用域相同的积节点 n 和 n′ 以相同的方式进行分解。

在从数据中学习概率电路时（Liu 和 Van den Broeck，2021），以及从其他模型（如贝叶斯网络）编译生成电路时（Choi, Kisa 和 Darwiche，2013），通常都会施加结构化可分解性的约束。

3 单调与平方结构化可分解电路的表达效率

概率电路的一个主要应用是作为概率分布的可追踪表示。因此，我们通常要求电路输出的函数值为非负实数。实现这一要求的常用方法是对权重和输入函数施加非负性约束：

定义 4（单调 PC）：一个概率电路被称为单调电路（Monotone PC），如果其所有权重均为非负实数，并且所有输入函数的输出也为非负实数。

这或许有些令人惊讶，因为对概率电路进行平方操作会生成具有可能为负的权重的结构化电路，这表明它们应该比单调结构化的概率电路更通用。

关键在于，并非所有表示正函数的电路（甚至并非所有单调结构化的电路）都可以通过对某个函数平方来生成。

综合来看，这些结果有些令人不满意，因为我们知道存在一些分布更适合用未平方的单调 PC 来表示，而另一些分布则更适合用平方后的实值 PC 来表示。

在下一节中，我们将探讨如何调和这些不同的概率分布建模方法。

4 朝向深度和的平方的平方的统一模型

在本节中，我们深入探讨单调电路与平方电路之间的关系。首先，我们展示如何为平方电路引入复数参数化（命题1）。其次，我们从一个新的角度解释单调电路与平方电路：它们是边缘化潜在变量的不同方式（图1）；并在此基础上提出一种新的可追踪模型——Inception PCs，将这两种方法结合起来（定理3）。

4.1 复数参数

我们首先指出，除了简单的负参数之外，我们还可以允许使用复数权重和输入函数²，即取值在复数域 ℂ 中。为了确保平方电路的非负性，我们将一个电路与其复共轭相乘。也就是说：

由于复共轭是复数域 ℂ 的一个域同构映射（field isomorphism），对一个电路取复共轭，就如同对其中的每一个权重和输入函数分别取复共轭，同时保留原电路相同的有向无环图（DAG）结构。这使得我们能够高效地将概率分布 表示为一个（平滑且结构化可分解的）电路：

4.2 深度和的平方的平方：一种潜在变量视角

在概率电路的潜在变量解释（Latent Variable Interpretation, LVI）中（Peharz 等人，2016），对于每一个和节点（sum node），我们分配一个分类潜变量（categorical latent variable），其中该潜变量的每一个状态对应和节点的一个输入；我们在图1a中展示了一个示例。在这种解释下，当在概率电路中进行推理时，我们事先对所有潜变量进行边缘化（marginalize over）。

在电路具有结构化可分解性的前提下，我们可以为电路中出现的变量作用域（即变量集合）分配对应的潜变量。具体来说，对于两个具有相同作用域 sc(n) = sc(n′) 的和节点 n 和 n′，它们共享同一个潜变量 Zsc(n)。设 Z 为所有潜变量的集合，则概率电路所表示的函数可以表达为：

其中，对于任意 z 的取值，fC(V,z) 是输入函数的乘积。

换句话说，给定一个潜变量 z 的取值后，概率电路所表示的分布是完全可分解的（fully factorized）。

然而，当我们考虑由平方电路定义的概率分布时，对这些潜变量的解释就变得复杂了。关键问题是：我们是在平方之前还是之后对潜变量进行边缘化？

我们在图1b和图1c中展示了这两种情况：

  • 在图1b中，我们在边缘化潜变量 Z之前进行平方。在这种情况下，每个和节点的权重都与其共轭相乘，结果得到一个具有非负实数参数的和节点。

  • 另一方面，如果我们在平方之前就对潜变量进行边缘化（如图1c所示），那么我们将面对一个具有四个子节点且权重为复数的和节点。

有趣的是，前一种情况与直接构造一个单调PC非常相似，而后一种情况则更像是在没有潜变量的情况下进行显式的平方操作。

这表明，我们可以通过决定是否将潜变量的求和放在平方的内部或外部，来在单调PC与平方PC之间切换。

基于这一视角，我们提出了以下模型，它显式地将两种类型的潜变量引入到电路中，从而生成一个深度的和的平方的平方（deep sum-of-square-of-sums）结构：

由于U-潜变量（U-latents）位于平方之外，而W-潜变量（W-latents）位于平方之内，我们将它们分别称为1-范数潜变量和2-范数潜变量。

接下来的定理表明，给定一个 Inception PC，我们可以高效地将其“具体化”为一个仅作用于观测变量 V 上的可追踪概率电路，该电路表示 Inception PC 的分布：

在图2中，我们展示了一个示例性的 Inception PC（的一部分），以及通过定理3进行“具体化”后的形式。在本文的其余部分，我们将这种形式称为materialized Inception PC（具体化的 Inception PC）。关键在于：我们可以通过对 materialized IncPC 使用标准的 PC 推理过程，来高效地对 Inception PC 的分布进行推理。

虽然这不是必须的，但我们假设（与单调PC和平方PC的LVI一致）W 和 U 是分类变量（categoricals），并且作用域覆盖这些变量的输入节点是指示函数（indicator），例如

然而，当我们同时使用两种类型的潜变量时，我们就得到了一个广义的PC模型，其表达效率严格优于单独使用任一类型。

推论 1（Inception PCs 的表达效率）：
Inception PCs 在表达效率上严格优于（结构化可分解的）单调PC和平方PC。

5 张量化 Inception PCs

到目前为止，我们已经描述了 Inception PCs 的一个通用形式，它只要求电路具有平滑性和结构化可分解性。在实际应用中，我们希望设计特定的电路架构以用于学习与推理。

本节的目的有两个：

(i) 提出一种适合在 GPU 上进行学习与推理的 Inception PC 架构；
(ii) 从另一个角度——即层级张量收缩（hierarchical tensor contractions）——来重新理解 Inception PCs。

我们在图3中展示了这一和节点区域的结构。从高层次来看，图3中各节点组之间的连接可以看作是一个标准的单调PC；特别是，每个和节点组的值就是其子节点的加权和。然而，与传统的标量节点之间的加权边不同，这里的每条加权边连接的是两组二维的“平方”节点（"squared" nodes）。

前向传播的复杂度可以从公式（5）中的张量收缩中推导出来。在表1中，我们比较了单调PC、平方PC和Inception PC在每个区域上的参数数量（即内存开销）以及前向传播时间复杂度，其中 B 表示数据批次的大小。

可以看出，当设置 ，Inception PC 的参数数量 / 复杂度分别与单调PC和平方PC相同，只是在平方PC的情况下复杂度略有不同：这是因为在这一特殊情况下，平方操作可以在每批次中仅执行一次（Loconte 等人，2024b）。

与之前的工作（Peharz 等人，2020a）一样，我们将电路组织成层（即可以同时计算的一组区域），以进一步利用GPU的并行计算能力。在训练过程中，我们对训练集的负对数似然使用梯度下降法进行优化。在使用复数参数的情况下，我们采用Wirtinger 导数（Kreutz-Delgado, 2009）来优化复数权重和输入函数。为了实现数值稳定性，我们使用了一种针对复数的 log-sum-exp 技巧的变体，具体描述见附录D。

6 相关工作

概率模型的空间可以通过可追踪性（tractability）和表达效率（expressive efficiency）的视角来有效刻画（Choi, Vergari 和 Van den Broeck，2020）。可追踪性是一个连续谱系，从不可追踪的模型（如扩散模型 Ho, Jain 和 Abbeel，2020；变分自编码器 Kingma 和 Welling，2014），到允许可追踪似然的模型（如归一化流 Papamakarios 等人，2021），再到允许可追踪边缘分布及更复杂查询的模型（如概率电路 Vergari 等人，2021；Wang 等人，2024）。

然而，由于计算图中施加了特定结构，概率电路在实践中通常比那些可追踪性较低的模型表达能力弱。因此，已有大量研究致力于在保持可追踪性的前提下提升概率电路的表达效率（Sidheekh 和 Natarajan，2024）。

我们的工作建立在电路领域长期的研究基础上，这些研究考察了放宽电路中单调性条件的影响。理论上已知，在算术电路中引入负参数可以在简洁性上带来指数级的提升（Valiant，1979），尽管这一结论并不适用于所有类型的子电路（de Colnet 和 Mengel，2021）。在实际应用中，近期的研究也尝试在概率建模中利用负参数（Zhang, Holtzen 和 Van den Broeck，2020；Zhang, Juba 和 Van den Broeck，2021；Sladek, Trapp 和 Solin，2023；Loconte 等人，2024b）。

Yu、Trapp 和 Kersting（2023）设计了用于表示分布特征函数的电路，该函数可以取复数值（特别是使用复数叶子节点）。与我们工作同期，Loconte、Mengel 和 Vergari（2025）提出使用多个平方电路的和来克服我们在本文中观察到的类似限制。

此外，还存在一系列其他采用负参数化和/或平方机制的概率模型：

  • 张量网络

    （tensor networks），例如流行的矩阵乘积态（Matrix Product States, MPS）（Perez-Garcia 等人，2007），通过稀疏张量收缩紧凑地编码函数。它们常用于建模量子态，其中观测的概率是通过对波函数平方得到的（即 Born 规则，Dirac，1981）；最近也被用于概率建模（Cheng 等人，2019；Glasser 等人，2019）。

  • 在核方法文献中，半正定模型（positive semidefinite models）（Rudi 和 Ciliberto，2021）使用浅层的平方和来定义未归一化的分布。

  • Tsuchida、Ong 和 Sejdinovic（2023, 2024）最近提出了平方神经族（squared neural families），其密度函数中使用了神经网络的平方 L2 范数，并严格推广了指数族模型。

我们在附录A中详细讨论了这些模型与我们提出的 Inception PC 的技术联系。

7 实验

在我们的实验中，我们旨在回答以下研究问题：

  1. Inception PCs 是否在表达能力和建模性能上优于单调PC和平方PC？

  2. 在建模性能和计算成本之间，1-范数潜变量（one-norm latents）与2-范数潜变量（two-norm latents）的数量权衡如何？

  3. Inception PCs 的复数参数化与非负参数化和实数参数化相比表现如何？

在所有实验中，我们都使用了隐藏 Chow-Liu 树（Hidden Chow-Liu Trees, HCLT）作为概率电路的 vtree（Liu 和 Van den Broeck，2021），因为它满足所需的结构化可分解性，并且已被证明可以为概率电路提供最先进的似然性能。

更多实验细节请参见附录 E。

7.1 二值数据集

我们首先在20 个二值数据集上进行评估，这些数据集被广泛用作密度估计的基准测试数据（Rooshenas 和 Lowd，2014；Peharz 等人，2020b）。

我们的目标是研究在这组数据集中：

  1. 非负参数化、实数参数化和复数参数化

    之间有何差异；

  2. Inception PCs

    是否能够有效利用两种类型的潜变量，通过与单调PC和平方PC的对比来验证这一点。

具体来说，我们为不同模型设定了以下参数规模：

  • 单调 PC：(N₁, N₂) = (8, 1)

  • 平方 PC：(N₁, N₂) = (1, 8)

  • Inception PC：(N₁, N₂) = (8, 8)

我们使用 Adam 优化器（Kingma 和 Ba，2015），以学习率 0.01，对每个模型训练 100 轮，优化其负对数似然。每种配置下我们都进行了 5 次实验并取平均结果。

实验结果见表2。可以看到，在 20 个数据集中，Inception PCs 在 14 个上取得了最佳似然表现，这证实了它相比仅使用平方机制具有更强的建模能力。

与现有模型相比，Inception PCs 的表现也非常优异，包括可追踪模型如 RAT-SPNs（Peharz 等人，2020b），以及不可追踪模型如重要性加权自编码器（IWAE）（Burda, Grosse 和 Salakhutdinov，2016）。

有趣的是，即使平方PC使用的是非负参数，它们的表现也优于具有相同参数数量的单调PC——这一现象也在 Loconte 等人（2024b）图3中被观察到。

更值得注意的是，尽管边缘权重的复数参数化严格地推广了实数和非负参数化，但在性能上并没有明显的优势趋势。在许多情况下，非负参数化反而能取得与实数或复数参数化相当甚至更好的似然表现。

我们发现，这（至少部分原因）是因为复数和负参数化更容易过拟合（参见附录F中的训练似然结果）。

7.2 扩展到大规模图像数据集

在本节中，我们在大规模图像数据集上进行实验，特别是将 ImageNet（Deng 等人，2009）降尺度为32×32和64×64的版本。

我们遵循近期在这些图像数据集上构建概率电路模型的相关工作（Liu, Zhang 和 Van den Broeck，2023；Liu 等人，2023；Liu, Ahmed 和 Van den Broeck，2024），使用有损的YCoCg 色彩空间变换对原始 RGB 数据进行转换。需要注意的是，因此在 YCoCg 转换后的数据上获得的似然值不能直接与原始 RGB 数据上的似然值进行比较。

此外，为了提高训练效率，我们仅在原始图像的16×16 像素块上进行训练，使得每个 PC 模型建模16×16×3 = 768 个变量，每个变量具有256 个类别（对应像素颜色值）。

我们仍然使用 Adam 优化器以学习率 0.01 来最小化负对数似然函数进行训练，并使用测试集上的每维度比特数（bits-per-dimension,bpd）作为评估指标。

我们首先考察两种潜变量之间的权衡关系。为此，在图4中，我们在 ImageNet32 数据集上绘制了不同 (N₁, N₂) 配置下的测试 bpd 曲线。这些配置是基于对 N₁, N₂ ∈ {1, 2, 4, 8, 16, 32, 64} 的搜索结果确定的，同时受限于每个区域最多允许2¹⁸ = 262,144 FLOPS（浮点运算次数/秒）的计算预算（参见表1）。

可以看出，在这些限制条件下最优的配置是(N₁ = 32, N₂ = 4)，对应的测试 bpd 为4.19。该配置结合了1-范数潜变量和2-范数潜变量，而不是单纯使用单调结构（N₂ = 1）或平方结构（N₁ = 1）。

在表3中，我们总结了在ImageNet32和ImageNet64数据集上的实验结果：

  • MPC

    表示一个单调PC，配置为 (N₁, N₂) = (64, 1)

  • SQC

    表示一个平方PC，配置为 (N₁, N₂) = (1, 64)

  • IncPC

    表示一个张量化的 Inception PC，在给定计算时间约束下采用最优配置 (N₁, N₂)

作为对比，我们还列出了使用期望最大化算法（EM）训练的单调 HCLT PC，以及使用潜变量蒸馏（LVD）方法训练的模型——后者通过从现有的深度生成模型中提取信息来指导 PC 的潜空间学习（Liu, Zhang 和 Van den Broeck，2023）。

实验结果显示：通过 Adam 初始化即可有效地训练可追踪的概率电路模型，其 bpd 性能可以达到当前最先进的水平。

8 结论

总而言之，我们展示了两类重要的可追踪概率模型——单调结构化可分解PC与平方实数结构化可分解PC——在表达效率上通常是不可比较的。因此，我们提出了一种新的概率电路模型——Inception PCs，它基于“深度和的平方的平方”（deep sums-of-squares-of-sums）结构，统一并推广了上述两种方法，并且可以使用复数参数。

我们还通过实验验证了 Inception PCs 在多种表格数据集和图像数据集上能够提供更优的性能。

未来值得探索的方向包括：改进 Inception PCs 中复数参数的优化方法；以及通过设计更高效的架构来降低训练的计算成本。

原文链接：https://arxiv.org/pdf/2408.00876