平方驱动的减法混合模型：表征与学习新方法

SUBTRACTIVE MIXTURE MODELS VIA SQUARING:REPRESENTATION AND LEARNING

平方驱动的减法混合模型：表征与学习新方法

https://openreview.net/pdf?id=xIHi5nxu9P

摘要
传统上，混合模型通过将多个分布作为成分相加来表示和学习。然而，如果允许混合模型减去概率质量或密度，则可以显著减少建模复杂分布所需的成分数量。但在此过程中，如何在保证函数非负的前提下学习这种减法混合模型是一项挑战。我们研究了如何通过对混合模型进行平方处理来学习并执行推理。我们在概率电路（probabilistic circuits）的框架下进行这一操作，这使我们能够表示张量化的混合模型，并推广多种其他减法模型。我们从理论上证明，允许减法的平方电路类比传统的加法混合模型具有指数级更强的表达能力；并通过一系列现实世界中的分布估计任务实证展示了这种增强的表达能力。

1 引言
有限混合模型（MMs）是概率机器学习中的基础方法，它提供了一种简单而优雅的方法——通过线性组合较简单的分布来建模复杂的分布（McLachlan 等，2019）。设计混合模型的经典方法是对输入成分计算凸组合。也就是说，一个表示随机变量集合 X = {X₁, X₂, ..., Xᴅ} 上的概率分布 p 的混合模型通常定义为：

其中，wᵢ 是混合参数，每个成分 pᵢ 是一个概率质量或密度函数。这种情况适用于广泛使用的混合模型（MMs），例如高斯混合模型（GMMs）和隐马尔可夫模型（HMMs），也适用于生成模型的混合，例如归一化流（normalizing flows，Papamakarios 等，2021），以及深度混合模型，如概率电路（PCs，Vergari 等，2019b）。

公式（1）中的凸性约束是最简单的充分条件，用于确保 p 是一个非负函数且积分等于 1，即是一个有效的概率分布，在实践中通常被假设。然而，这意味着成分 pᵢ 只能以相加的方式组合，因此会极大地影响它们高效估计分布的能力。例如，考虑在定义域中具有“空洞”的分布，比如左侧所示的一个二维环形分布（真实情况）。一个经典的加法混合模型，如 GMM 最终可以还原出这个分布，因为它是一个密度函数的通用逼近器（universal approximator，Nguyen 等，2019），但需要使用不必要的大量成分（显示为红色椭球体）。而允许负混合权重（即 wᵢ < 0）的混合模型，例如 NGMM（负高斯混合模型），则只需要两个成分即可实现：通过从外部高斯密度中减去一个内部高斯密度（见虚线椭球体）。我们将这类混合模型称为“减法型”或“非单调混合模型”（NMMs），与传统的加法型混合模型相对应，后者被称为“单调混合模型”（monotonic MMs，Shpilka & Yehudayoff, 2010）。

NMMs 的挑战在于确保建模的 p(X) 是一个有效的分布，因为此时凸性约束不再成立。这个问题在过去已被多种方式研究过，最简单的一种是通过对混合参数 wᵢ 施加临时约束，例如针对高斯分布和威布尔分布（Weibull distribution）等简单成分进行推导（Zhang & Zhang, 2005；Rabusseau & Denis, 2014；Jiang 等, 1999）。然而，不同的成分族需要制定不同的约束条件，这些约束是否存在闭合形式并不总是有保证的。

本文中，我们研究了一种更通用的设计 NMMs 的原则，这种方法绕过了上述限制，同时确保了所建模函数的非负性：对编码的线性组合进行平方处理。例如，上面提到的 NGMM 就是一个带有负混合参数的高斯密度平方组合。我们从理论上研究了平方型 NMMs 的表达效率（expressive efficiency），即其表达能力相对于模型规模的表现，并展示了如何在实践中有效地表示并学习它们。具体来说，我们在概率电路（PCs）框架下进行这一研究，这是一种可处理的模型，能够将经典浅层混合模型推广到作为结构化神经网络表示的深层混合模型。相比浅层混合模型，深层 PC 本身已经具有更高的表达效率，因为它们可以紧凑地编码具有指数数量成分的混合模型（Jaini 等, 2018；Vergari 等, 2019b）。然而，它们传统上是以非负参数表示的，因此只能编码深度虽深但仍是加法型的混合模型。相反，作为主要理论贡献之一，我们证明了我们的平方非单调概率电路（NPC²s）比其单调对应模型在参数使用上可以指数级更高效。

贡献。
i) 我们引入了一个通用框架，通过平方操作在张量化概率电路（tensorized PCs）的语言中表示非单调混合模型（NMMs）（见第2节），并展示了如何有效地学习NPC²模型并用于可处理的推理（第3节）。
ii) 我们展示了NPC²不仅能够推广单调概率电路，还能统一其他一些看似不同的允许负参数的模型，这些模型分别出现在不同领域中，例如信号处理中的密度平方根模型（Pinheiro & Vidakovic, 1997）、核方法中的半正定（PSD）模型（Rudi & Ciliberto, 2021）以及量子力学中的玻恩机（Born machines）（Orus´, 2013；Glasser 等，2019）（第4节）。这使我们能够通过PCs的特性导向框架理解为何它们能实现可处理的推理。
iii) 我们推导了单调概率电路在表示某些函数时的指数级下限，而这些函数可以被一个NPC²以紧凑方式编码（第4.1节），从而证明了NPC²（以及前述模型）在相同规模下具有更强的表达能力。
iv) 最后，我们提供了实证证据（第5节），表明在多种实验设置中，包括从真实数据中学习以及将不可处理的模型（如大语言模型）蒸馏为可处理模型以实现高效推理（Zhang 等，2023），NPC²比单调概率电路具有更好的分布逼近能力。

2 通过平方实现减法混合模型
我们首先形式化如何通过对 K 个简单函数的非凸组合进行平方操作来表示浅层非单调混合模型（NMMs）。类似于基于能量模型中的指数运算（LeCun 等，2006），平方操作可以确保我们模型的非负性，但与之不同的是，它还允许对模型进行可处理的重新归一化。一个平方型 NMM 将变量 X 上的一个（可能是未归一化的）分布 c²(X) 编码为：

计算 Z 相当于对 (K+1)⁄2 个成分乘积 cᵢ(X)cⱼ(X) 的积分进行求和。更一般地，在 X 中对任意变量子集进行边缘化可以在 O(K²) 时间内完成。然而，这要求选择的成分 cᵢ 来自某一函数族，使得它们的乘积 cᵢ(X)cⱼ(X) 可以高效积分，并且 Z 非零且有限。这对于许多参数族都成立，包括指数族（Seeger, 2005）。例如，两个高斯分布或两个分类分布的乘积在乘上一个常数因子后仍然是高斯分布（Rasmussen & Williams, 2005）或分类分布，并且可以在多项式时间内计算。

更广泛的成分选择。 注意，我们并不要求每个 cᵢ 都必须表示一个概率分布，例如，我们可能有 cᵢ(x) < 0。这使我们可以在平方型 NMMs 中使用更具表达能力的可处理函数作为基础成分，如样条函数（详见附录 E），甚至可能是小型神经网络（见附录 G 的讨论）。然而，如果这些基础成分本身已经足够灵活，则通过线性组合或平方操作混合它们可能不会显著提升其表达能力。例如，一个简单的分类分布已经可以表示任何有限支撑的离散分布，而对其进行（减法型）混合可能除了更容易学习之外并不会带来额外的表达能力提升。相反，二项分布的加法混合模型比单个二项分布更具表达能力，但预计其表达能力仍不及对应的减法版本（如第5节所示）。

平方型 NMM 的学习方法。 学习传统混合模型（公式(1)）的标准方法是最大似然估计（MLE），即最大化 Σₓ∈D log p(x)，其中 D 是一组独立同分布（i.i.d.）样本。对于平方型 NMM，MLE 目标为：

3 深度混合模型的平方化方法

到目前为止，我们讨论的是“浅层”混合模型，即可以表示为仅包含一个加权求和单元的简单计算图（例如，图1）。现在我们将它们推广到概率电路（PCs）的框架中（Vergari 等，2019b；Choi 等，2020；Darwiche，2001），因为该框架提供了一种基于性质驱动的语言来建模结构化的神经网络，从而实现可处理的推理。概率电路使我们能够在紧凑但深度较深的计算图中编码指数数量的混合成分。

概率电路通常由标量计算单元定义：求和、乘积和输入单元（见附录A）。与 Vergari 等（2019a）和 Mari 等（2023）的方法一致，我们将其形式化为张量化的计算图。也就是说，我们将多个计算单元分组为层次结构，这种方法有两个优势：第一，我们可以推导出一种简化的平方化算法，仅需线性代数运算，并能利用GPU加速（算法1）；第二，我们能够更方便地推广许多最新的概率电路架构（Peharz 等，2020b;a；Liu & Van den Broeck，2021），以及其它可处理的张量表示方法（见第4节）。图A.1展示了标量计算单元是如何映射到张量化层次结构中的。我们首先定义可以建模可能为负函数的深度计算图，统称为“电路”（Vergari 等，2021）。

图 2b 展示了一个以张量化形式表示的深度电路。为了通过电路对分布进行建模，我们首先要求计算图的输出是非负的。我们将这种电路称为概率电路（PC）。类似于浅层加性混合模型（公式（1）），确保输出非负的一个充分条件是使 PC 保持单调性，即用非负矩阵参数化所有求和层，并限制输入层编码非负函数（例如，概率质量或密度函数）。到目前为止，单调 PC 一直是表示和学习 PC 的标准方式（附录 G）。在定义 1 中，我们仅展示了计算哈达玛乘积的乘积层，以简化符号表示，因为这种实现选择在许多现有的 PC 架构中被广泛使用（Darwiche, 2009; Liu & Van den Broeck, 2021; Mari et al., 2023）。我们在定义 A.6 中对 PC 的处理进行了推广，以处理另一种流行的乘积层实现方式：克罗内克积（Peharz et al., 2020b;a; Mari et al., 2023）。除非另有说明，我们的结果对这两种类型的乘积层都成立。

3.1 构建可进行边缘化的可处理电路如果深度概率电路

（PCs）是平滑且可分解的 ，那么它们可以在一次前向传播中完成归一化并对任意 X 的子集进行边缘化：具体来说，每个求和层接收来自其作用域相同的层的输入，每个乘积层接收来自其作用域互不重叠的层的输入（Darwiche, 2001；Choi 等, 2020）。更多背景信息请见命题 A.1。在我们的定义1中，求和层通过设计保证了平滑性，因为它们恰好只有一个输入。确保可分解性的简单方法是构建一个遵循变量 X 的分层作用域划分的电路，这被称为区域图（region graph），形式化定义如下。

定义 2（区域图，Region Graph）（Dennis & Ventura, 2012）给定一组变量 X，区域图（RG）是一种二分且有根的图，其节点要么是表示 X 子集 R 的“区域”（regions），要么是描述某个区域如何被划分为其他区域的“划分”（partitions）。

图2a 展示了一个 RG 的例子。给定一个 RG，我们可以构建一个平滑且可分解的张量化电路，方法如下：首先，我们使用一个输入层对那些不再进一步划分的区域 R ⊆ X 进行参数化，该输入层编码 R 中变量的一些函数；然后，我们使用一个乘积层对该区域的划分 {Rᵢ}ᵢ=1ᴺ 进行参数化，其中每个 Rᵢ 对应一个输入层。每个乘积层之后紧接着一个求和层。图2a 和图2b 通过颜色编码区域及其对应的层展示了这种构造方式。正如我们将在第3.2节中展示的，这也为我们提供了一种高效地对深度电路进行平方操作的清晰策略。

关于概率电路（PCs）的研究文献中提供了多种构建 RG 的方法（Peharz 等, 2020b;a；Mari 等, 2023）。在我们的实验中（第5节），我们随机递归地划分变量集合，直到无法进一步划分为止（Peharz 等, 2020b）。此外，我们也尝试了逐个变量进行划分的 RG（例如图2a中的结构），因为它们与其它类型的模型相关（见第4节）。附录F进一步详细说明了这些 RG 的构建方法。

3.2 深度张量化电路的平方化方法

（平方型负）混合模型作为电路表示。可以看出，传统的浅层混合模型（公式(1)）可以很容易地表示为张量化的、平滑且可分解的概率电路（PC），其结构是一个输入层，用于编码 K 个成分 pᵢ，后接一个求和层，该求和层由一个非负行向量 W ∈ ℝ⁺¹×ᴷ 参数化，且其元素之和为1。平方型非单调混合模型（NMMs，见公式(2)）也可以用类似方式表示，只不过此时求和层由实数向量参数化，因为它们可以被视为在扩展后的成分空间上的混合（见图1和图A.1）。接下来，我们将讨论如何对深度张量化电路进行平方操作，以获得我们提出的 NPC² 模型类别。

张量化电路的平方（与归一化）
对一个张量化的非单调电路 c（可能编码负函数）进行平方的挑战在于，如何确保其平方结果 c² 可以被表示为具有多项式规模的平滑且可分解的概率电路（PC）。这是因为这两个性质是能够在一个前向传播中高效归一化 c² 的必要条件（Choi 等，2020）。通常情况下，即使是在保持平方后的电路可分解性的前提下对一个可分解电路进行平方操作，也可能是一个 #P 难问题（Shen 等，2016；Vergari 等，2021）。幸运的是，对于具有结构可分解性（structured-decomposable）的电路 c，我们可以高效地得到其平方后的可分解表示 c²（Pipatsrisawat & Darwiche, 2008；Vergari 等，2021）。直观来说，在一个张量化的结构可分解电路中，所有作用域相同的乘积层对其输入层的划分方式完全一致。我们在附录定义 A.3 中对该性质进行了形式化描述。

通过如前所述的方式，按照区域图（RG）堆叠层次结构的设计，可以轻松构建满足这一性质的张量化电路。此外，我们要求该 RG 是一棵树，即每个区域只能被唯一地划分，并且其输入区域之间的作用域不重叠。例如，图2a中的 RG 就是一棵树。从现在起，不失一般性，我们假设我们的树状 RG 是二叉树，即每次将一个区域划分为两个子区域。给定这样一个基于树状 RG 定义的张量化结构可分解电路 c，算法1可以高效地构造出一个平滑且可分解的张量化电路 c²。此外，设 L 为电路层数，M 为评估电路 c 中一层所需的最大时间，则以下命题成立：

命题1（平方电路的可处理边缘化）
设 c 是一个张量化的结构可分解电路，其中每个输入层所计算的函数乘积可以高效积分。则通过算法1获得的任何 c² 的边缘化操作所需的时间和空间复杂度均为 O(L · M²)。

见附录 B.2 中的证明。简而言之，这是可行的，因为算法 1 在电路 c 中递归地对每一层 ℓ 进行平方操作，即在 c² 中实现 ℓ² = ℓ ⊗ ℓ，其中 ⊗ 表示两个向量的克罗内克积。我们对电路的张量化处理使得 Vergari 等（2021）提出的更通用算法更加紧凑，后者是基于对标量计算单元进行平方操作定义的。同时，这也使我们能够推导出比通常针对结构可分解电路平方化所报告的更紧的最坏情况上界（Pipatsrisawat & Darwiche, 2008；Choi 等，2015；Vergari 等，2021），该上界为整个计算图中计算次数的平方，即 O(L² · M²)。

需要注意的是，当我们想要高效计算 c² 的归一化常数 Z 或对任意变量子集进行边缘化时，才需要显式构建 c²。因此，在使用最大似然估计（MLE，公式(4)）并通过批量梯度下降进行学习时，我们只需每个批次计算一次 c²，从而大幅摊销其计算成本。在附录 C 中，我们研究了在不同规模和不同数据维度下学习 NPC² 所需的时间和内存开销。最后，可处理的边缘化能力也使得可以从 NPC² 建模的分布中进行可处理的采样，详见附录 A.2 的讨论。

3.3 数值稳定的推理与学习

对深度概率电路（PCs）进行重新归一化很容易导致下溢（underflow）和/或上溢（overflow）。在单调型 PC 中，通常通过在对数空间中进行计算，并使用 log-sum-exp 技巧来解决这一问题（Blanchard 等，2021）。然而，这种方法不适用于非单调型 PC，因为其中间层可能计算出负值。因此，我们采用另一种方法：在电路计算过程中传播每层输出的绝对值对数 以及符号值 。然后，求和层通过一种考虑符号的 log-sum-exp 变体来进行计算。类似的思想已被用于在单调型 PC 中评估负函数的期望值（Mauá 等，2018；Correia & de Campos，2019）。附录 D 将该方法扩展到了张量化的非单调型电路中。

4 NPC² 的表达能力及其与其它模型的关系

电路（circuits）被用作一种“通用语言”来表示表面上不同但可处理的模型表示形式（Darwiche & Marquis, 2002；Shpilka & Yehudayoff, 2010），并用于研究这些模型在仅需多项式级模型规模增长的前提下，是否能够精确表示某些函数族的能力——这也被称为模型类的表达效率 （expressive efficiency，Martens & Medabalimi, 2014）或简洁性 （succinctness，de Colnet & Mengel, 2021）。这是因为电路的大小直接对应于执行推理所需的计算复杂度。

在我们扩展单调概率电路（PCs）的语言以包含负参数的背景下，本文提供了从多个应用领域中出现的、能够编码减法操作的可处理概率模型类到（深度）非单调概率电路（non-monotonic PCs）的多项式时间归约（polytime reductions）。通过这种方式，我们不仅揭示了这些模型为何是可处理的（通过明确指出它们作为电路所具有的结构特性），还解释了它们为何比传统的加法混合模型（MMs）更具表达能力。正如我们在第4.1节中所证明的那样，NPC² 可以在模型规模上实现指数级的紧凑表示。

如第1节所述，简单浅层非单调混合模型（NMMs）已经被针对有限的成分函数族进行了研究。值得注意的是，这种建模方式也可以通过对密度函数的平方根进行近似学习来实现，例如在信号处理中使用小波函数作为成分（Daubechies, 1992；Pinheiro & Vidakovic, 1997）或使用径向基函数（RBF）核函数，即以数据点为中心的未归一化高斯函数（Scholkopf & Smola, 2001），如 Hong & Gao（2021）所做的那样。正如第3节所讨论的，我们可以将这些 NMMs 表示为简单的 NPC²，其中核函数由输入层计算得出。

正定半（Positive Semi-Definite, PSD）模型（Rudi & Ciliberto, 2021；Marteau-Ferey 等, 2020）是来自核方法和优化文献中的一类新兴模型。给定一个核函数 κ（例如 Rudi & Ciliberto（2021）中的 RBF 核），以及一组 d 个数据点 x⁽¹⁾, ..., x⁽ᵈ⁾，令 κ(x) = [κ(x, x⁽¹⁾), ..., κ(x, x⁽ᵈ⁾)]⊤ ∈ ℝᵈ，并设 A 是一个实数 d×d 的 PSD 矩阵，则该模型定义了一个未归一化的分布：非负函数 f(x; A, κ) = κ(x)⊤Aκ(x)。尽管表面看起来不同，但这类模型可以在多项式时间内转换为 NPC²。

命题2（PSD 模型的归约）一个基于核函数 κ、定义在 d 个数据点上的 PSD 模型，并由一个 PSD 矩阵 A 参数化，可以在 O(d³) 时间内表示为平方型 NMMs（即 NPC²）的混合模型。

我们在附录 B.3 中给出了该命题的证明。需要注意的是，虽然 PSD 模型属于浅层非单调概率电路（PCs），但我们可以通过堆叠它们构建更深层的 NPC²，从而利用结构可分解性支持可处理的边缘化操作。

张量网络与玻恩规则。通过对一个可能为负的函数进行平方操作以获得一个未归一化的分布，这一做法与量子力学中的玻恩规则（Born rule）相关（Dirac, 1930），该规则通过对其波函数进行平方来描述粒子的分布（Schollwoeck, 2010；Orus´, 2013）。这类函数可以表示为一个在离散变量 X = {X₁, ..., Xᴅ} 上的大规模 D 维张量 T，其中每个变量取值为 {1, ..., m}，并通过张量网络（TN）紧凑地分解，例如矩阵乘积态（matrix-product state，MPS）（Perez-García 等，2007），也称为张量链（tensor-train）。给定一个变量赋值 x = ⟨x₁, ..., xᴅ⟩，一个秩为 r 的 MPS 对 T 的紧凑表示如下：

其中，索引为 {i₁, ..., iD−1}，并用方括号表示索引操作。为了编码分布 p(X)，可以对张量 Aⱼ 进行参数化使其非负（Glasser 等，2019），或者应用玻恩规则并对 T 进行平方，以建模 p(x) ∝ (T [x₁, ..., xᴰ])²。这样的张量网络（TN）被称为玻恩机（Born machine，BM）（Glasser 等，2019）。除了用于建模复杂的量子态外，像 BM 这样的 TN 也被探索作为经典的机器学习模型，用于学习离散分布（Stoudenmire & Schwab, 2016；Han 等, 2018；Glasser 等, 2019；Cheng 等, 2019），在量子机器学习中也有应用（Liu & Wang, 2018；Huggins 等, 2018），最近还通过引入基函数集合被扩展到连续域中，称为 TTDE（Novikov 等, 2021）。接下来我们展示它们是 NPC² 的一个特例。

命题3（从玻恩机的归约）一个通过平方秩为 r 的 MPS 来编码具有 m 个状态的 D 维张量的玻恩机（BM），可以在 O(D·k⁴) 的时间和空间复杂度内被精确表示为结构可分解的 NPC²，其中 k ≤ min{r², mr}。

我们在附录 B.4 中给出了该命题的证明，方法是展示其等价于定义在线性树状区域图（RG）上的 NPC²（例如图2a中的结构）。这一联系揭示了 BM 中之所以能够进行可处理的边缘化，是因为其具备结构可分解性（命题1），而据我们所知，这一性质此前并未在张量网络（TNs）中被研究过。此外，现在我们可以将 BM 视为 NPC² 并设计更灵活的树状 RG 结构，例如随机化的树结构（Peharz 等，2020b；Di Mauro 等，2017；Di Mauro 等，2021）、充分利用 GPU 并行计算能力的密集张量化结构（Peharz 等，2020a；Mari 等，2023），或通过启发式方法从数据中学习 RG 结构（Liu & Van den Broeck, 2021）。

4.1 NPC² 与结构化单调概率电路的指数级表达能力差异

通过算法1进行平方操作已经可以使一个张量化的（单调）概率电路（PC）更具表达能力，但这种提升仅是多项式级别的：我们使每层的大小成平方增长，同时保持可学习参数的数量不变（类似于平方型非单调混合模型NMMs在成分数量上的增加，见第2节）。然而，允许使用负参数可以带来指数级的优势 ，这一结论在某些特定电路中已有证明（Valiant, 1979），但要确认这一优势是否适用于我们提出的平方电路并不直接明显。

事实上，我们观察到对于某些类别的非单调且结构可分解的电路来说，并不存在任何表达能力上的优势。这些电路支持可处理的最大后验推理（maximum-a-posteriori inference，Choi 等，2020），并满足一个称为“确定性”（determinism）的附加性质（见 Darwiche（2001），定义 A.5）。对这些电路进行平方操作后输出的 PC 与其原始规模相同且为单调电路，如以下命题所述，并在附录 B.6 中给出了证明。

命题4（确定性电路的平方化）设 c 是一个平滑、可分解且具有确定性的电路，可能计算一个负函数。那么其平方电路 c² 是单调的，并且具有与 c 相同的结构（因此也是相同的规模）。

目前为止我们在第3节中构造的 NPC² 并不具有确定性。接下来我们证明，存在一些非负函数（即归一化前的概率分布）可以通过 NPC² 来表示，而如果用结构可分解的单调 PC 表示，则其所需规模会呈指数级增长。

定理1（NPC² 的表达效率）存在一类关于变量 X 的非负函数族 F，它们可以被紧凑地表示为浅层的平方型 NMM（即 NPC²），但对于该函数族中的任意函数 F ∈ F，最小的能够表示它的结构可分解单调 PC 的规模为 2^Ω(|X|)。

我们在附录 B.5 中通过展示一种独特的不交集问题（unique disjointness problem，Fiorini 等，2015）变体的结构可分解单调 PC 规模的非平凡下界来证明这一点。直观上，这说明在参数数量固定的前提下，NPC² 可能比结构可分解单调 PC（以及浅层加法混合模型）具有更强得多的表达能力。

我们进一步猜想，类似的下界也可以推广到一般的可分解单调 PC 上。此外，由于该结果可以直接扩展到 PSD 模型和玻恩机（BM）模型（见第4节），它在基于核方法和张量网络模型的研究领域中也开辟了有趣的理论联系。

5 实验

我们的目标是回答以下问题：(A) NPC² 是否比单调概率电路（PCs）具有更好的分布估计能力？(B) 由于平方操作带来的模型规模增长以及负参数的存在，这两个因素各自如何独立地影响 NPC² 的表达能力？(C) 输入层的选择以及区域图（RG）如何影响 NPC² 的性能？我们在合成数据和真实世界数据上进行了多个分布估计实验，并在下文用字母标记各段落，以对应上述问题。此外，请注意我们对 NPC² 和单调 PC 的比较是基于两者具有相同数量的可学习参数的前提下进行的。

(A, B) 合成连续数据。 按照 Wenliang 等（2019）的方法，我们在二维密度估计任务中评估单调概率电路（PCs）和 NPC² 的表现，因为这使我们能够直观了解所学习到的密度函数。为了区分平方操作与负参数各自的影响，我们还尝试了平方型单调 PCs。我们使用一种简单的树状区域图（RG）构建电路结构（详见附录 H.1）。对于 NPC²，我们使用样条函数作为输入层；而对于单调 PC，则强制输入层非负性（见附录 E）。图3显示，虽然平方操作提升了单调 PC 的性能，但要更好地捕捉复杂的密度目标函数，NPC² 中的负参数是必要的。

(C) 合成离散数据。 我们对前述二维数据集进行有限离散化后，估计其概率质量函数，以进一步理解在输入层已经具备足够表达能力的情况下，负参数是否仍能带来优势。首先，我们尝试了使用分类分布（categoricals）作为输入层的（平方型）单调 PC（对应地，NPC² 使用实值嵌入）。其次，我们采用了表达能力较弱但参数效率更高的二项分布（Binomials）。附录 H.2 列出了超参数设置。图3显示，在使用嵌入输入的 NPC² 与使用分类输入的 MPC² 之间没有明显优势差异的情况下，当使用二项分布时，NPC² 能更好地捕捉目标分布。这是因为分类分布（以及嵌入）本身已具备足够的参数来建模概率质量函数中的“空洞”。而二项分布引入了较强的归纳偏置，可能阻碍学习。我们认为这也是为什么根据一些初步结果，我们在图像分布估计任务中未观察到 NPC² 相比单调 PC 有明显提升的原因。

(A, B, C) 多元连续数据。 按照 Papamakarios 等（2017）的方法，我们在五个多变量数据集上评估更深的概率电路（PCs）用于密度估计的表现（见表 H.1）。我们评估了以张量化的形式构建的单调 PC 和 NPC²，这些模型基于随机线性树状区域图（RG）构建。具体来说，在某种变量排列下，我们构造了一个树状 RG，其中每个划分将一个区域分割为仅包含一个变量的子区域，并递归地对剩余变量进行因式分解。通过这种方式，我们得到了一种类似于玻恩机（BM）或 TTDE 的架构（见第4节）。此外，根据 Peharz 等（2020b）的方法，我们也尝试了将区域随机分成两半的二叉树 RG 结构。附录 H.3 详细描述了这些 RG 结构及所使用的超参数。

我们将其与以下模型进行了比较：全协方差高斯模型、归一化流模型 RealNVP（Dinh 等，2017）、MADE（Germain 等，2015）、MAF（Papamakarios 等，2017）、NSF（Durkan 等，2019）、输入层编码流模型的单调 PC（EiNet-LRS）（Sidheekh 等，2023），以及 TTDE（Novikov 等，2021）。图4显示，使用高斯输入层的 NPC² 在四个数据集上的对数似然值普遍高于单调 PC。图 H.3 显示，即使与平方型单调 PC 相比，NPC² 仍具有更高的似然值，这表明负参数带来的表达能力提升并不仅仅来自于平方操作本身。

在 RG 结构方面，二叉树结构通常比线性树结构表现更好，尤其是在 Gas 数据集上，使用二叉树结构的 NPC² 超过了 TTDE 的性能。

(A) 蒸馏不可处理模型。 单调 PC 已被用于近似不可处理模型（如大语言模型 LLMs），并在存在逻辑约束的情况下执行精确推理，例如在受限文本生成中（Zhang 等，2023）。由于生成性能与可处理模型对 LLM 的近似程度相关，我们感兴趣于相比单调 PC，NPC² 是否能更好地作为 GPT2 这类 LLM 的蒸馏目标。

按照 Zhang 等（2023）的方法，我们在一个采样句子数据集上最小化 GPT2 与我们的 PC 之间的 KL 散度（细节见附录 H.4）。由于句子是 token 变量的序列，张量化电路的结构是基于线性树状 RG 构建的：对于单调 PC 来说，这对应于一个非齐次隐马尔可夫模型（HMM）（见附录 B.4.1），而对于 NPC² 来说，则更类似于玻恩机（BM）。图5显示，NPC² 在蒸馏 GPT2 方面优于单调 PC，因为它们能够达到更接近 GPT2 计算出的对数似然值。

我们观察到，NPC² 对训练数据的拟合明显优于测试数据，尽管测试数据上的结果总体上仍然显著（见表 H.7）。虽然这是其更强表达能力的又一证据，但如何正则化 NPC² 仍有待进一步研究。

6 讨论与结论

通过本项工作，我们希望推广一种简单而有效的模型类别——通过平方实现的减法型混合模型（subtractive MMs），使其成为可处理的概率建模与推理工具包中的一种有力方法，并能与传统的加法型混合模型（MMs）相媲美。通过将其纳入“电路”（circuits）的框架中，我们展示了如何有效地表示和学习诸如 NPC² 这类深度减法型混合模型（见第3节），并说明它们如何可以推广其他模型类别，如 PSD 模型和张量网络模型（见第4节）。

我们的主要理论成果（见第4.1节）同样适用于这些模型，并解释了我们在实践中观察到的性能提升（见第5节）。本研究首次系统性地探讨了非单调概率电路（PCs）的表示与学习问题，并为未来的研究开辟了多个方向：

第一个方向 是为 NPC² 建立潜在变量解释。由于非单调 PC 中的负参数破坏了其子电路的概率解释（Peharz 等，2017），使得无法以传统方式学习其结构和参数（见附录 G），因此寻找新的结构学习方法是关键。

第二个方向 是改进 NPC² 的学习方法。这将进一步提升其在概率电路广泛应用领域中的表现，例如因果发现（Wang 等，2022）、变分推理（Shih & Ermon, 2020）以及神经符号人工智能（neuro-symbolic AI，Ahmed 等，2022），使更紧凑且更具表达能力的概率分布模型得以应用。

最后，通过将电路与张量网络进行形式上的连接，我们希望激发两个研究社区之间的知识迁移 ，例如借鉴更好的学习策略（Stoudenmire & Schwab, 2016；Novikov 等，2021），或发展更灵活的高维张量分解方法（Mari 等，2023）。

在附录 H 中，我们包含了第5节中展示的所有实验的详细信息。用于复现实验结果和图表的源代码、文档、数据集和脚本均可在以下网址获取：https://github.com/april-tools/squared-npcs 。

H 实验设置与补充结果 H.1 连续合成数据

按照 Wenliang 等（2019）的方法，我们在合成的连续二维数据集上进行了实验，包括 rings（环形）、cosine（余弦）、funnel（漏斗）和 banana（香蕉）四种类型，并使用单调概率电路（PCs）、其平方版本以及 NPC² 模型进行建模。我们为每个合成数据集生成了 10,000 条训练样本、1,000 条验证样本和 2,000 条测试样本。

在这些实验中，我们旨在研究 NPC² 是否在实践中具有更强的表达能力，而不对数据分布做任何假设，也不选择特定参数化分布作为成分。因此，我们选择了基于单变量样条函数（见附录 E）乘积构建的成分函数，在数据域内均匀选取 32 个节点。特别地，对于单调混合模型，我们限制样条系数为非负数。

学习与超参数设置：由于数据是双变量的，定义在其上的概率电路所依赖的区域图仅包含一个区域，并被划分为两部分。所有模型均通过批量化的随机梯度下降进行训练，使用默认学习率的 Adam 优化器（Kingma & Ba, 2015），批大小为 256。所有混合模型的参数初始化为在 [0, 1] 区间内均匀采样得到。此外，为了确保（平方型）概率电路的单调性，我们对参数进行了指数变换处理。

图3展示了当分别使用 8 和 12 个成分时，从 rings 和 cosine 数据集中估计出的密度函数。此外，图 H.1 报告了当使用 4 个成分时，从 funnel 和 banana 数据集中学习到的对数似然值及其他估计的密度函数。

H.2 离散合成数据

为了研究 NPC² 输入层的灵活性（第2节）在离散数据情况下的表现（见第5节），我们将附录 H.1 中报告的双变量连续合成数据集进行了量化处理。具体来说，我们使用 32 个均匀划分的区间对两个连续变量进行离散化。由此得到的目标分布是一个定义在两个有限离散变量上的概率质量函数。

我们尝试了两种类型的输入层结构用于单调 PC、其平方版本及 NPC² 的实验：

1. 灵活的输入层

   ：对于单调 PC 使用分类分布（categoricals），而对于 NPC² 使用实值嵌入（embeddings）。

2. 更紧凑但灵活性较低的输入层

   ：使用二项分布（Binomials）。

学习与超参数设置与连续数据实验相同（见附录 H.1）。图 H.2 显示，与使用分类成分的单调 PC 相比，使用减法操作的概率质量建模并未带来显著优势。然而，在使用灵活性较低的二项分布成分时，NPC² 明显更好地捕捉了目标分布。这一结论也通过未见过的数据上的对数似然值得到了验证，如图 H.2 所示。

H.3 UCI 连续数据

数据集。 在第5节中，我们评估了 NPC² 在五个多变量 UCI 数据集（Dua & Graff, 2017）上的密度估计性能：Power（Hebrail & Berard, 2012）、Gas（Fonollosa 等, 2015）、Hepmass（Baldi 等, 2016）、MiniBooNE（Roe 等, 2004）以及 BSDS300 patches（Martin 等, 2001）。我们采用了 Papamakarios 等（2017）的预处理方法。表 H.1 报告了这些数据集的基本统计信息。

模型。 我们比较了用于密度估计的单调概率电路（PCs）和 NPC² 模型，两者均采用张量化的形式（定义1）。两种模型的张量化架构均基于二叉树（BT）或线性树（LT）区域图（RG）构建（见附录 F）。此外，由于这两种 RG 是随机生成的，我们通过改变随机种子实例化了八种不同的 RG 结构。这样一来，我们的单调 PC 由多个定义在不同 RG 上的张量化单调 PC 组成的混合模型构成；而我们的 NPC² 则由多个通过平方机制构建于不同 RG 上的张量化 NPC² 组成的混合模型构成，其中每个 NPC² 的参数为非负。为了确保公平比较，单调 PC 和 NPC² 具有完全相同的结构，但 NPC² 通过平方机制允许参数为负（见第3节）。

超参数。 我们通过对单调 PC 和 NPC² 进行网格搜索来寻找最佳超参数。对于每个 UCI 数据集，表 H.2 和 H.3 报告了根据所选 RG 可能使用的每个超参数的取值范围。在输入层建模样条函数的情况下（见附录 E），我们使用二次样条，并在域空间中均匀选取 512 个节点。

参数初始化。 我们发现 NPC² 对参数初始化方式比单调 PC 更敏感。在文献中，单调 PC 的初始化影响尚未被深入研究，而对于允许参数为负的 NPC² 来说，这一问题更加不明确。在本实验中，我们尝试通过从正态分布中独立采样来初始化 NPC² 的参数。然而，我们发现如果仅使用非负参数进行初始化——即在 [0, 1] 区间内均匀采样，NPC² 能获得更高的对数似然值。不过，在附录 H.5 中我们展示了即使如此初始化，在收敛过程中 NPC² 仍会学习到负参数。需要注意的是，我们的工作是首次尝试在大规模数据上学习非单调 PC，因此也为未来的研究开辟了新的方向，例如如何初始化和训练 NPC²，以及如何对其正则化。

H.4 大语言模型蒸馏

数据集。 给定 GPT2 所建模的句子分布 p∗(x)，其中句子 x = [x₁, ..., xD] 的最大长度为 D，我们的目标是最小化 Kullback-Leibler 散度 KL[p∗ | p]，其中 p 由概率电路（PC）建模。最小化该散度等价于在 GPT2 采样的数据上使用最大似然估计来训练 PC。因此，按照 Zhang 等（2023）的实验设置，我们使用 GPT2 采样了一个包含 800 万条句子的数据集，且句子的最大长度 D 设为 32（即最多包含 32 个 token）。然后我们将这些句子划分为训练集、验证集和测试集，比例分别为 0.85 / 0.05 / 0.10。

模型。 我们随后学习一个单调概率电路（PC）和一个 NPC² 模型，它们均以张量化的形式构建，其架构由线性树状区域图（RG）（定义2）决定。具体来说，这种区域图递归地将每个有限离散变量集合 {Xᵢ, ..., Xᴰ} 划分为 {Xᵢ} 和 {Xᵢ₊₁, ..., Xᴰ}，其中 1 ≤ i ≤ D−1（例如见图2a）。我们选择这种结构是因为它有助于捕捉句子中词与词之间的序列依赖关系。通过强制单调性，我们可以发现单调 PC 相当于一个非齐次隐马尔可夫模型（HMM），而 NPC² 对应于一个玻恩机（Born machine）（详见附录 B.4.1）。

超参数。 所有概率电路均采用批量随机梯度下降进行训练，优化器为 Adam（Kingma & Ba, 2015），批大小为 4096。我们持续优化直到验证损失在连续三个周期内不再改善，或达到最大 200 个周期的预算。我们进行了多组实验，探索不同的学习率和初始化方法组合。对于单调 PC，我们尝试的学习率为 {5×10⁻³, 10⁻², 5×10⁻²}，并分别通过在 (0, 1) 区间内均匀采样、从标准对数正态分布采样以及从浓度值设为 1 的狄利克雷分布采样来初始化参数。类似地，对于 NPC²，我们也使用相同的 GPT2 学习率，但采用不同的初始化方式。由于平方操作相较于单调 PC 会产生更大的输出值，我们对 NPC² 的参数初始化采用了较小的幅度。具体而言，除了在 (0, 10⁻¹) 区间内均匀采样外，我们还使用均值为 0、标准差为 10⁻¹ 的正态分布进行初始化，使得正负参数数量大致相等。此外，我们还尝试了均值为 10⁻¹、标准差为 10⁻¹ 的正态分布初始化，以使更多参数为正值。

结果。 随着层维度的增长，我们将不同学习率和初始化方法的运行结果汇总在一起，并在图5中展示了所实现的对数似然值。此外，在层维度 K ≤ 256 的情况下，我们通过更换随机种子重复实验，从而获得双倍的对数似然点。随后我们进行了统计检验，评估 NPC² 在测试数据上的对数似然显著高于单调 PC 的显著性水平，并在表 H.7 中展示了对应的 p 值。

H.5 学得参数的直方图

在图 H.4 中，我们展示了在实验中学习到的单调概率电路（PCs）和 NPC² 的参数情况（见第5节），即在 UCI 数据集（表 H.1）以及从 GPT2 采样的句子上进行的分布估计实验。尽管我们在实验中对 NPC² 的参数进行了非负初始化（即通过在非负区域上的均匀分布进行采样），它们最终仍然学到了负参数。

具体来说，图 H.4 展示了在相同模型规模下（即层维度 K 相同）的 UCI 数据集上训练得到的单调 PC 和 NPC² 求和层参数的直方图：Power 和 Gas 数据集使用 K = 512，Hepmass 和 MiniBooNE 使用 K = 128，BSDS300 使用 K = 64。对于其他超参数，我们选择批大小为 512，学习率为 10⁻²，输入层使用二次样条函数，并构建了树状电路的混合模型（详见附录 H.3）。对于在 GPT2 句子上训练的模型，我们使用学习率 10⁻² 并采用非负均匀初始化（另见附录 H.4）。

需要注意的是，对于 NPC²，我们报告的是通过算法 1 进行平方处理后的电路参数，因此参数数量呈二次增长。

原文链接：https://openreview.net/pdf?id=xIHi5nxu9P