用随机约束问题揭示扩散模型生成离散数据的规律与反直觉现象
Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems
- 基于随机k-SAT问题设计生成实验，研究离散分布生成机制
- 连续扩散模型优于掩码离散扩散，且学习后可逼近理论最优精度
- 变量排序策略显著提升效果，但不依赖常见启发式方法
从离散分布生成数据在文本、表格和基因组数据等应用中至关重要。近期多个研究团队将随机k-满足性问题（k-SAT）作为新型生成技术的合成基准。本文表明，随机约束满足问题的理论洞察对生成技术的表现有可观测影响（有时与直觉相悖）。我们研究了生成给定随机k-SAT或k-XORSAT公式均匀随机解的问题。主要发现包括：(i) 连续扩散模型优于掩码离散扩散；(ii) 学习得到的扩散模型可达到理论上的‘理想’准确率；(iii) 变量的智能排序能显著提升准确率，尽管其方式并不遵循主流启发式规则。
原文摘要 · Abstract (English)
Generating data from discrete distributions is important for a number of application domains including text, tabular data, and genomic data. Several groups have recently used random $k$-satisfiability ($k$-SAT) as a synthetic benchmark for new generative techniques. In this paper, we show that fundamental insights from the theory of random constraint satisfaction problems have observable implications (sometime contradicting intuition) on the behavior of generative techniques on such benchmarks. More precisely, we study the problem of generating a uniformly random solution of a given (random) $k$-SAT or $k$-XORSAT formula. Among other findings, we observe that: $(i)$~Continuous diffusions outperform masked discrete diffusions; $(ii)$~Learned diffusions can match the theoretical `ideal' accuracy; $(iii)$~Smart ordering of the variables can significantly improve accuracy, although not following popular heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。