通过 Discrete Diffusions 获得分类 Markov 随机场的样本复杂度界

arXiv:2610.02128v1 公告类型：交叉领域 摘要：统计学、经济学和物理学中的许多应用都需要从具有局部依赖结构的高维分类分布中进行采样。例如，有限记忆语言模型、统计物理学和蛋白质折叠中的 Ising 和 Potts 系统等。在现代机器学习中，离散扩散已成为对这类数据进行采样的一种灵活方法，并展现出强大的实证性能。受此启发，我们针对具有局部依赖的均匀加噪离散扩散，开发了具有端到端样本复杂度界的学习方法，并通过低阶 Markov 随机场（MRF）对这种局部依赖进行建模。我们的主要技术洞见是对离散得分函数进行新的 \emph{钉扎分解}。该分解表明，与连续扩散不同，得分函数可以分解为若干组成部分，其中时间依赖与目标分布依赖以乘法形式相互分离。在此分解的基础上，我们提出了一种 \emph{权重共享神经得分学习器}，并将其与 $\tau$-leaping 相结合，从而获得端到端的采样过程。不同于现有采样分析中常见的将得分学习误差视为黑盒输入的方法，我们从有限数据出发研究得分学习误差，并推导出最优采样保证，明确刻画其对词汇表大小、MRF 的交互阶数以及样本量的依赖关系。此外，我们的策略在均匀噪声水平下训练单个得分网络，同时将采样离散化留待推理时选择。这使得同一个训练好的模型能够随着推理时计算预算的变化，在精度与计算成本之间进行权衡。在 Potts、Ising 和树结构模型上的数值实验表明，在长序列采样任务中，权重共享得分网络优于全连接网络。