PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers

Abstract

it is not clear how the search strategy in the learned models actually works. So propose a generic neural framework to solve CSP( constraint satisfaction problems) in a fully unsupervised manner via energy minimization.

PyTorch implementation of the PDP framework :
https://github.com/Microsoft/PDP-Solver

This work takes the formulation of solving CSPs as probabilistic inference(概率推断),并提出它的神经网络(参数化)版本，能够学习有效的推理策略 for specific problem domains.
整个过程分为三个部分: Propagation, Decimation and Prediction, 传播、剥离和预测 (PDP) ,
these operations can be implemented(实现) either as fixed algorithms or as trainable neural networks.
框架同时学习最佳消息传递和抽取策略。

Introduction

image.png

定义域有限的约束满足问题通常利用搜索方法来解决。最常用的技术是回溯法(backtracking)、约束传递constraint propagation，以及局部搜索local search的改良。

The main motivation is that by incorporating Machine Learning, we will have one generic solver that can be specialized for specific domains based on data.

PDP优势:

1. probabilistic inference in the latent space, 直接建立搜索策略
2. 剥离过程非简单greedy strategy
   3.提出了一种基于能量最小化的无监督，完全可区分的训练机制，该机制可以直接训练PDP通过端到端的反
   向传播来求解SAT。

PDP Framework

image.png

image.png

邻居信息聚合+迭代

image.png

A)In the GMP-guided sequential decimation, a decimation step is executed only after GMP is converged. We relax this requirement in PDP by interleaving the propagation and the decimation steps. PDP的抽取步骤不是将边缘的消息固定为某个值，而是仅拦截传播消息并转换为有状态的方式。

image.png

Result

the performance goes worse when α (N/M) grows
Nevertheless, the neural PDP can still learn efficient, domain-specific inference strategies.
(BP只在树上比较好, 在图上表现并不好,局部树结构不明显)
This framework can be interpreted as a neural extension of probabilistic message passing and inference techniques on graphical models and as such its search strategy can be explained in the probabilistic terms.
Unsupervised: This also opens the door to the further question of how to generate unlabeled training streams for efficient training in specific domains.

Word and Phrase

versatile framework 通用框架

deprive 夺去

myriad 无数,多种多样的

propagation, decimation and prediction 传播、剥离和预测

constitute the cornerstone of 构成...的基石

A is mutually exclusive with B Ａ与Ｂ互斥

To resolve this dilemma　为了解决这个难题

pursuing this direction, 朝着这个方向发展

In that vein 以这种方式

This would raise the question of...

实现 achieve, realize, implement, bring about, comply

distinguish it from 区分开

the superiority of ...优势

concurrently == at the same time 同时

aforementioned issues 上述问题

replicate复制