前沿进展：在组合优化问题中重新审视采样

导语

在集智俱乐部「图神经网络与组合优化读书会」第一季最后一期，DeepMind 实验室资深科学家戴涵俊首先介绍了他们近期发表于 PMLR 的一项最新研究，“在组合优化问题中重新审视抽样”（Revisiting Sampling for Combinatorial Optimization）。

研究领域：图神经网络，组合优化，采样算法，离散空间

戴涵俊 | 讲者

刘明昊 | 整理

采样算法概述
高效的离散空间采样算法
采样算法与组合优化
采样算法与AI模型

1. 采样算法概述

采样算法在很多任务中扮演着关键的角色。例如，对于最近很火的大语言模型，其核心部分就是在从自回归模型里面进行采样，即在给定上下文的情况下对中间进行采样。在3D图像、AI4Science等领域，其背后也大量依赖采样算法。实际上，在自然语言处理、蛋白质结构、程序语言等领域，很多情况下数据的表达形式是离散和结构化的，因此需要对于离散空间的采样算法。即使对于一些可以在连续空间表征的数据（例如图像），也可以通过将其映射到离散空间进行处理，从而提升计算效率。然而，设计对离散空间的采样算法并不简单。难点在于离散数据是不可微的，因此在条件采样或非自回归模型等情况下将很难进行采样。

在此之前，有必要先回顾一下在连续空间的采样算法。Langevin Monte Carlo是一个经典的采样算法。考虑图1的一个飞机的3D点云模型，其概率函数为。如果对它运用Langevin Monte Carlo算法进行采样，就可以从部分数据迭代地生成一架完整的飞机。在采样过程中，很重要的一项是，也叫做打分函数，在扩散模型的反向过程中也有类似的应用。但是我们知道，在离散空间中并不存在这样的梯度，因此一个关键问题就是解释在离散空间中究竟对应着什么。

图1 基于Langevin Monte Carlo算法的3D点云采样

2. 高效的离散空间采样算法

传统的对离散空间的采样算法包括随机游走、Gibbs采样等，它们未能利用梯度信息，因此非常低效。那么，如何将Langevin Monte Carlo这样的算法应用到离散空间的采样中呢？一个比较好的切入点是考虑梯度下降算法，它实质上是定义了一个微分方程形式的梯度流，而不同的梯度下降算法变体，例如经典梯度下降、临近点算法（proximal point algorithm）等，都属于对该梯度流的近似模拟。根据文献，Langevin Monte Carlo算法也可以按照类似的思路进行理解。如图2，它实质上也是对于Langevin Dynamics这一微分方程的一种模拟。因此一个合理的思路就是，在离散空间中构造出相应的Fokker-Planck Equation（也叫做Wasserstein梯度流）和Langevin Dynamics，从而形成可用的算法。相信这个思路对于设计其它离散空间的算法同样有所帮助。

Sampling as first-order optimization over a space of probability measures [2022]. Anna Korba, Adil Salim.

The variational formulation of the Fokker-Planck equation [1998]. Richard Jordan et al.

图2 对Langevin Monte Carlo算法的理解

就实现细节而言，首先注意到连续空间和离散空间的概率函数空间定义是不同的。对于连续空间，概率函数可以定义为欧式空间中的一个点；但对于离散空间，则应将它定义为图（graph）上的一个结点。从已有文献的结论，可以推导出在离散空间中Wasserstein梯度流的公式。然而进一步推导离散Langevin Dynamics则是困难的，主要原因是此时状态空间为指数大小，例如最大割问题的状态空间是一个超立方、旅行商问题的状态空间是一个序列等。为此，作者借鉴了化学中电导率（conductance）的概念，定义了一种合适的权重公式，从而推导出离散Langevin Dynamics的形式：。进而，可以通过标准化模拟时间，计算转移概率矩阵，使用离散马尔科夫链的方法进行采样；也可以标准化每一步的汉明距离，使用称为Path Auxiliary Proposal的方法进行采样。图3展示了所提出的梯度下降采样算法与Gibbs这种算法相比的优势。

Fokker-Planck equations for a free energy functional or Markov process on a graph [2012]. Shui-Nee Chow et al.

Discrete Langevin sampler via Wasserstein gradient Flow [2023]. Haoran Sun et al.

Thermodynamics of stoichiometric biochemical networks in living systems far from equilibrium [2005]. Hong Qian, Daniel A Beard.

Path auxiliary proposal for MCMC in discrete space [2022]. Haoran Sun et al.

图3 梯度下降采样与Gibbs采样的对比示意图

3. 采样算法与组合优化

采样算法最初的应用是在很多物理模型中，例如Ising模型等。本工作提出的采样方法能够在这些非归一化分布的模型上发挥作用。进一步地，在组合优化中也完全用得上这种采样技术。考虑一般的组合优化问题，即min a(x), s.t. b(x)=0，将其转化为罚函数形式min f(x)=a(x)+λ·b(x)。定义温度τ下的概率分布，则可以对概率空间 (τ₀>τ₁…τ_T→0)作采样，来求解组合优化问题。前面提到的Path Auxiliary采样也可以用于组合优化问题，每步改变一个状态，从而在目标状态改变多个结点。

图4 在最大独立集问题上的实验结果

图5 在最大割问题上的实验结果

图6 在旅行商问题上的实验结果

在最大独立集问题上的实验结果（图4）显示，采样算法在很多实例上找到了比传统求解器和机器学习求解器更优的解，而且运行时间也相当有优势。而考虑到采样算法的轻量级、无需训练的特点，这样的结果无疑是非常有趣的。在最大割问题上的实验结果（图5）也显示，当图中的结点数较多时，采样算法得到的解将优于Gurobi。对于旅行商问题（图6），采样算法虽然不及LKH，但是也得到了相当好的结果，尤其是与需要大量训练的一系列机器学习方法对比也具有明显的优势。是时候在组合优化中重新审视采样算法了。

Revisiting Sampling for Combinatorial Optimization [2023]. Haoran Sun et al.

4. 采样算法与AI模型

除了比较经典的组合优化问题之外，在图像和文本生成等任务中，采样算法也能够得到一些非常有趣的结果。例如，可以给定一个能量模型，对图像进行采样生成；或是给句子去掉几个词，使用采样算法对去掉的词做出预测。图7显示，好的采样算法可以得到更具多样性的结果。另一个最近的尝试是“图生文”任务，即给定一张图像，预测它是用什么提示词生成的。如果将该任务看作一种组合优化问题，它甚至不能严格地计算出目标函数。如图8所示，作者提出的一种基于梯度下降的采样算法同样可以在该任务中表现良好。这些应用都体现出采样算法不仅适用于经典的组合优化，还能够在很多与基础模型有关的任务中发挥作用。

图7 采样算法在图像和文本生成中的应用

图8 采样算法在图“图生文”任务中的应用

扫描下方二维码观看读书会视频回放

学者简介

戴涵俊，Google DeepMind实验室资深科学家和研究经理，此前于佐治亚理工获得博士学位。研究方向：高效的生成模型，包括大语言模型，图像和结构化数据模型，及其采样和优化的底层算法

图神经网络与组合优化读书会

现实世界中大量问题的解决依赖于算法的设计与求解。传统算法由人类专家设计，而随着人工智能技术不断发展，算法自动学习算法的案例日益增多，如以神经网络为代表的的人工智能算法，这是算法神经化求解的缘由。在算法神经化求解方向上，图神经网络是一个强有力的工具，能够充分利用图结构的特性，实现对高复杂度算法的高效近似求解。基于图神经网络的复杂系统优化与控制将会是大模型热潮之后新的未来方向。

为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院副教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在 AI for Science 中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。欢迎感兴趣的朋友报名参与！