无监督神经组合优化的扩散模型框架

Abstract

• 从离散集合的不可处理分布中进行采样，而不依赖相应的训练数据，是多个领域的核心问题，包括组合优化。
• 目前，流行的基于深度学习的方法主要依赖于能够提供精确样本概率的生成模型。本文提出了一种方法，打破了这种限制，并为使用诸如扩散模型等高度表达力的潜变量模型开辟了可能性。
• 我们的方法从概念上基于一种上界反向Kullback-Leibler散度的损失函数，从而避免了对精确样本概率的需求。

1. Introduction

从已知但不可处理的高维目标分布（如Boltzmann分布）中进行采样，在许多科学领域具有重要意义，例如分子构型预测（Noé和Wu, 2018）、物理学中的晶格模型（Wu等，2019）以及蒙特卡洛积分（Müller等，2019）。最近，Hibat-Allah等人（2021）和Sanokowski等人（2023）的研究表明，组合优化（CO）可以简洁地表示为一种分布学习问题，其中生成的样本对应于组合优化问题的解。在所有这些领域中，分布相关的能量函数是已知的，但获取无偏样本则是一个巨大的挑战。像CO或物理学中的晶格模型等问题的特点是离散目标分布。在这些应用中，目标分布的近似主要基于范畴分布的乘积或自回归模型。尽管乘积分布在计算上是方便的，但它们缺乏表达力，因为它们无法表示统计上的相互依赖关系。自回归模型依赖于顺序生成样本的各个组成部分。对于这些领域中经常遇到的高维分布，这种生成过程变得极其昂贵。此外，样本的组成部分之间通常没有自然的顺序。因此，自回归方法在这些问题中显得不太自然。直观上，自回归模型的问题在于一旦做出次优决策，就没有机会进行修正。从计算复杂性角度看，也可以证明自回归模型的表达力不如基于能量的模型或潜变量模型（Lin等，2021）。

利用潜变量的近似概率模型（如变分自编码器（VAE）（Kingma和Welling，2014）和扩散模型（Sohl-Dickstein等，2015；Ho等，2020；Song等，2021））通过数据样本进行训练，并基于证据下界（ELBO）的损失函数。这些模型的优点是它们在离散设置中更具表达力且更为适用。然而，对于这些模型，通常无法计算精确的样本概率。这一问题阻碍了它们在无需数据的目标分布近似问题中的应用，因为这些问题通常依赖于精确的样本概率。最近的研究提出了在无需数据的情况下应用扩散模型的方法，但这些研究仅限于连续设置（Berner等，2022；Richter等，2023；Vargas等，2023；2024）。据我们所知，离散设置尚未得到探索。

在本文中，我们在第3节中提出了一种方法，允许潜变量模型（如扩散模型）应用于离散分布的无需数据的近似问题。我们在该领域的典型问题上展示了我们的方法，展示了其在组合优化中的应用，并取得了最先进的性能。为了实现这一点，我们提出的无监督组合优化扩散方法（DiffUCO）使用了反向Kullback-Leibler散度的上界作为损失函数。我们展示了，随着训练中使用的扩散步骤的增加，模型的性能稳定提升。此外，我们发现，在推断过程中，使用比训练时更多的扩散步骤可以进一步提高解的质量（见第6.2节）。在第4.1节中，我们提出了一种更高效的常用采样策略“条件期望”（Conditional Expectation）的版本。我们展示了这一方法与扩散模型结合后，可以高效地生成高质量的组合优化问题解。该框架提供了一种高效且通用的方法，使得潜变量模型（如扩散模型）能够应用于无需数据的离散分布近似这一普遍挑战中。

2. Problem Description

根据Lucas（2014）的研究，我们将组合优化（CO）问题表示为相应的能量函数 H : { 0 , 1 } N → R H:\{0,1\}^N \rightarrow \R H:{0,1}N→R。该函数为给定解 X ∈ { 0 , 1 } N X∈\{0,1\}^N X∈{0,1}N分配一个标量值，称为能量。X的维度表示为N，称为问题规模。与 H 相关的Boltzmann分布定义为：

其中参数T称为温度，β=1/T称为逆温度。

NPO的常见方法是最小化相对于模型参数 θ 的反向Kullback-Leibler散度（KL散度）：

将该目标乘以T可得变分自由能$F_{\theta }(X,T)$的一个与之成比例的表达式：

要最小化这一目标，必须对生成模型的样本概率$q_{\theta }(X)$进行精确评估。这可以通过REINFORCE（Williams, 1992）梯度估计器来实现：

为了最小化这一目标，必须能够选择一个能够有效评估样本概率$q_{\theta }(X)$的生成模型。因此，使用潜在变量模型（如VAE或扩散模型）来优化这一目标是不可能的，因为这些模型无法对 $q_{\theta }(X)$ 进行精确评估。

在第3节中，我们提出了一种基于反向KL散度上界的目标函数来缓解这一问题。原则上，也可以使用其他散度来近似目标分布。例如，反向和正向KL散度是Rényi散度的特例（van Erven和Harremoes，2014），它们都需要精确评估$q_{\theta }(X)$。通过引入散度上界，我们避免了对$q_{\theta }(X)$的评估。选择何种散度取决于具体应用，因为Rényi散度要么偏向覆盖概率质量，要么偏向模式选择（Minka等人，2005）。本文我们重点讨论反向KL散度，但我们的框架同样适用于其他Rényi散度。

2.1 无监督神经组合优化

在组合优化（CO）中，任务是找到一个解 X ∈ { 0 , 1 } N X∈\{0,1\}^N X∈{0,1}N，使得目标函数 O : { 0 , 1 } N → R O:\{0,1\}^N \rightarrow\R O:{0,