用自监督Transformer迭代优化约束问题解法，无需标注数据。
Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
- 用可微分近似替代约束条件，实现无需标签的自监督训练。
- 在数独、图着色等任务上，通过多步迭代提升解的质量。
- 适合处理分布外的约束问题，部署灵活且不依赖复杂奖励设计。
我们提出一种基于Transformer的约束满足问题（CSP）求解框架ConsFormer。CSP广泛应用于各类场景，利用机器学习加速求解具有重要意义。现有方法多依赖有标签的可行解或强化学习，但前者难以获取，后者需大量训练资源与复杂的奖励设计。为此，ConsFormer采用自监督范式，以Transformer作为解的迭代优化器，模拟局部搜索过程逐步构建解。不同于使用可行解作为监督信号，我们设计了约束的可微分近似来指导模型训练。模型仅需在单步中改进随机初始赋值，但在测试时可反复迭代应用，避开监督与强化学习的瓶颈。在数独、图着色、护士排班和MAXCUT任务上的实验表明，该方法仅通过增加迭代次数即可有效解决分布外的CSP问题。
原文摘要 · Abstract (English)
We present a Transformer-based framework for Constraint Satisfaction Problems (CSPs). CSPs find use in many applications and thus accelerating their solution with machine learning is of wide interest. Most existing approaches rely on supervised learning from feasible solutions or reinforcement learning, paradigms that require either feasible solutions to these NP-Complete CSPs or large training budgets and a complex expert-designed reward signal. To address these challenges, we propose ConsFormer, a self-supervised framework that leverages a Transformer as a solution refiner. ConsFormer constructs a solution to a CSP iteratively in a process that mimics local search. Instead of using feasible solutions as labeled data, we devise differentiable approximations to the discrete constraints of a CSP to guide model training. Our model is trained to improve random assignments for a single step but is deployed iteratively at test time, circumventing the bottlenecks of supervised and reinforcement learning. Experiments on Sudoku, Graph Coloring, Nurse Rostering, and MAXCUT demonstrate that our method can tackle out-of-distribution CSPs simply through additional iterations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。