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(概率推斷),并提出它的神經(jīng)網(wǎng)絡(參數(shù)化)版本杰妓，能夠?qū)W習有效的推理策略 for speci?c problem domains.
整個過程分為三個部分: Propagation, Decimation and Prediction, 傳播、剝離和預測 (PDP) ,
these operations can be implemented(實現(xiàn)) either as ?xed algorithms or as trainable neural networks.
框架同時學習最佳消息傳遞和抽取策略碘勉。
Introduction
定義域有限的約束滿足問題通常利用搜索方法來解決巷挥。最常用的技術(shù)是回溯法(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 speci?c domains based on data.
PDP優(yōu)勢:
- probabilistic inference in the latent space, 直接建立搜索策略
- 剝離過程非簡單greedy strategy
3.提出了一種基于能量最小化的無監(jiān)督，完全可區(qū)分的訓練機制胜嗓，該機制可以直接訓練PDP通過端到端的反
向傳播來求解SAT高职。
PDP Framework
鄰居信息聚合+迭代
The PDP framework can be seen as the generalization of the GMP-guided sequential decimation procedure
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的抽取步驟不是將邊緣的消息固定為某個值，而是僅攔截傳播消息并轉(zhuǎn)換為有狀態(tài)的方式辞州。
Result
the performance goes worse when α (N/M) grows
Nevertheless, the neural PDP can still learn ef?cient, domain-speci?c inference strategies.
(BP只在樹上比較好, 在圖上表現(xiàn)并不好,局部樹結(jié)構(gòu)不明顯)
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 ef?cient training in speci?c domains.
Word and Phrase
versatile framework 通用框架
deprive 奪去
myriad 無數(shù),多種多樣的
propagation, decimation and prediction 傳播怔锌、剝離和預測
constitute the cornerstone of 構(gòu)成...的基石
A is mutually exclusive with B Ａ與Ｂ互斥
To resolve this dilemma 為了解決這個難題
pursuing this direction, 朝著這個方向發(fā)展
In that vein 以這種方式
This would raise the question of...
實現(xiàn) achieve, realize, implement, bring about, comply
distinguish it from 區(qū)分開
the superiority of ...優(yōu)勢
concurrently == at the same time 同時
aforementioned issues 上述問題
replicate復制
