提出在对称群上学习概率分布的新扩散模型，解决离散结构建模难题。
SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups
- 用 riffle shuffle 作为前向扩散，分解复杂分布学习任务
- 在 4 位数字 MNIST、拼图等任务上达顶尖性能
- 理论指导的去噪调度提升采样效率，适合离散优化场景
有限对称群 $S_n$ 在组合数学、物理和化学中至关重要。但由于其不可计算的规模和离散性，学习 $S_n$ 上的概率分布极具挑战。本文提出 SymmetricDiffusers，一种新型离散扩散模型，通过将复杂分布分解为更简单的逆向扩散转移来简化学习过程，采用 riffle shuffle 作为有效前向转移，并基于有限群上的随机游走理论提供扩散长度选择的实证指导。我们提出广义 Plackett-Luce (PL) 分布作为逆向转移，证明其表达能力强于传统 PL。此外，设计了理论支撑的“去噪调度”以提升采样与学习效率。大量实验表明，该模型在排序 4 位数字 MNIST、拼图和旅行商问题等任务上达到当前最优或相当水平。代码已开源：https://github.com/DSL-Lab/SymmetricDiffusers。
原文摘要 · Abstract (English)
Finite symmetric groups $S_n$ are essential in fields such as combinatorics, physics, and chemistry. However, learning a probability distribution over $S_n$ poses significant challenges due to its intractable size and discrete nature. In this paper, we introduce SymmetricDiffusers, a novel discrete diffusion model that simplifies the task of learning a complicated distribution over $S_n$ by decomposing it into learning simpler transitions of the reverse diffusion using deep neural networks. We identify the riffle shuffle as an effective forward transition and provide empirical guidelines for selecting the diffusion length based on the theory of random walks on finite groups. Additionally, we propose a generalized Plackett-Luce (PL) distribution for the reverse transition, which is provably more expressive than the PL distribution. We further introduce a theoretically grounded "denoising schedule" to improve sampling and learning efficiency. Extensive experiments show that our model achieves state-of-the-art or comparable performances on solving tasks including sorting 4-digit MNIST images, jigsaw puzzles, and traveling salesman problems. Our code is released at https://github.com/DSL-Lab/SymmetricDiffusers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。