Generative models for learning combinatorial structures have transformative impacts in many applications. However, existing approaches fail to offer efficient and accurate learning results. Because of the highly intractable nature of the gradient estimation of the learning objective subject to combinatorial constraints. Existing gradient estimation methods would easily run into exponential time/memory space, or incur huge estimation errors due to improper approximation. We develop NEural Lovasz Sampler (Nelson), a neural network based on Lov\'asz Local Lemma (LLL). We show it guarantees to generate samples satisfying combinatorial constraints from the distribution of the constrained Markov Random Fields model (MRF) under certain conditions. We further present a fully differentiable contrastive-divergence-based learning framework on constrained MRF (Nelson-CD). Meanwhile, Nelson-CD being fully differentiable allows us to take advantage of the parallel computing power of GPUs, resulting in great efficiency. Experimental results on three real-world combinatorial problems reveal that Nelson learns to generate 100% valid structures. In comparison, baselines either time out on large-size data sets or fail to generate valid structures, whereas Nelson scales much better with problem size. In addition, Nelson outperforms baselines in various learning metrics, such as log-likelihood and MAP scores.
翻译:学习组合结构的生成模型在许多应用中具有变革性影响。 但是,现有方法未能提供高效和准确的学习结果。 由于在组合制约下对学习目标的梯度估计非常棘手, 现有的梯度估计方法很容易进入指数时间/ 模拟空间, 或由于不适当近似而产生巨大的估计错误。 我们开发了Neural Lovasz样板( Nelson), 以Lov\'asz 局域Lemma (LLLLL) 为基础的神经网络。 我们展示了它能保证在特定条件下生成满足限制的Markov随机场模型(MRF)分布的组合限制的样本。 我们进一步展示了在限制的MRF(Nelson-CD) 上完全不同的对比性对比性差异性差异性强的学习框架。 同时, Nelson-CD 完全不同, 使我们能够利用GPUs的平行计算能力, 从而产生巨大的效率。 三个真实世界调理学问题的实验结果显示Nelsons学会了100%的有效结构。 相比之下,, 大尺度的基线是, 大尺度的数据显示, 或无法产生有效的基准级的模型, 。