<p>You are probably looking for this paper:</p>

<ul>
<li>Víctor Dalmau and Peter Jeavons, <em>Learnability of quantified formulas</em>, TCS <strong>306</strong> 485–511, 2003.  doi:<a href="http://dx.doi.org/10.1016/S0304-3975%2803%2900342-6">10.1016/S0304-3975(03)00342-6</a></li>
</ul>

<p>In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms.  This includes CSPs as a special case of more general quantified formulas (since a CSP instance is just an existentially quantified conjunctive formula).</p>

<p>For the Boolean case and also for two broad classes of non-Boolean formulas, there is a dichotomy between polynomially learnable (via the Generating Set algorithm, if the clone contains a "nice" operation) and not, subject to the hypothesis that there exists a public key cryptosystem secure against chosen ciphertext attacks.</p>

CC BY-SA 3.0
2014-04-11T11:30:12.490Z
2014-04-13T16:24:22.490Z
2014-04-13T16:24:22.490Z
András Salamon
<p>there are many old SAT search, variable ordering, backtracking etc heuristics that can be regarded as verging on learning algorithms and many are applicable/generalizable to CSPs, and exact boundaries here may be blurring. possibly these have generally traditionally been two different fields, machine learning and constraint satisfaction, but with increasing intersection in more recent times. here are a few research leads. this appears to be an emerging area with some crosspollination with <a href="http://en.wikipedia.org/wiki/Big_data" rel="nofollow noreferrer">big data</a>/<a href="http://en.wikipedia.org/wiki/Data_mining" rel="nofollow noreferrer">datamining</a> eg:</p>
<ul>
<li><p>May 15 – 20, 2011, Dagstuhl Seminar 11201 / <a href="http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=11201" rel="nofollow noreferrer">Constraint Programming meets Machine Learning and Data Mining</a></p>
<blockquote>
<p>The second goal was to study the use of machine learning and data mining in constraint programming. Practitioners of constraint programming have to formulate explicitly the constraints that underly their application. This is often a difficult task. Even when the right constraints are known, it can be challenging to formalize them in such a way that the constraint programming system can use them efficiently. This raises the question as to whether it is possible to (semi)- automatically learn such constraints or their formulations from data and experience. Again, some initial results in this direction exist, but we are away from a complete understanding of the potential of this approach.</p>
</blockquote>
</li>
<li><p><a href="http://research.microsoft.com/pubs/77780/lion2009.pdf" rel="nofollow noreferrer">Learning Adaptation to Solve Constraint Satisfaction Problems</a> Yuehua Xu, David Stern and Horst Samulowitz</p>
<blockquote>
<p>Abstract. Constraint-based problems are hard combinatorial problems and are usually solved by heuristic search methods. In this paper, we consider applying a machine learning approach to improve the performance of these search-based solvers. We apply reinforcement learning in the context of Constraint Satisfaction Problems (CSP) to learn a value function, which results in a novel solving strategy. The motivation underlying this approach is to solve previously unsolvable instances.</p>
</blockquote>
</li>
<li><p><a href="http://www.cs.hunter.cuny.edu/%7Eepstein/papers/Springer_online_AMAI.pdf" rel="nofollow noreferrer">Learning cluster-based structure to solve constraint satisfaction problems</a> Xingjian Li · Susan L. Epstein</p>
<blockquote>
<p>Abstract The hybrid search algorithm for constraint satisfaction problems described here first uses local search to detect crucial substructures and then applies that knowledge to solve the problem. This paper shows the difficulties encountered by traditional and state-of-the-art learning heuristics when these substructures are overlooked. It introduces a new algorithm, Foretell, to detect dense and tight substructures called clusters with local search. It also develops two ways to use clusters during global search: one supports variable-ordering heuristics and the other makes inferences adapted to them. Together they improve performance on both benchmark and real-world problems.</p>
</blockquote>
</li>
</ul>

CC BY-SA 3.0
2014-04-13T16:23:19.193Z
Learning CSPs and learning to solve CSPs seem very different questions.
Lev Reyzin
CC BY-SA 3.0
2014-04-13T18:18:14.010Z
As @LevReyzin stated. Most of the work use the word *learning* in the context of solving CSPs. For instance, learning variable ordering, Learning hardest constraints in the network (to relax them later).
seteropere
CC BY-SA 3.0
2014-04-13T18:29:16.487Z
LR ok, pt taken, thx for bringing out distinction; however from ML pov there may not be so much difference; refs cover both cases, 1st ref more relevant, mtg covering learning CSPs by multiple researchers...
vzn
CC BY-SA 3.0
2014-04-13T16:00:38.693Z
2014-04-13T16:00:38.693Z
2020-06-17T09:38:08.363Z
vzn
<p>This may sound more like a soft question but I am struggling to find an answer for it. </p>

<p>While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of machine learning and learning theory, there is almost nothing on learning CSPs. Given that CSP is a well known constraint formalism, I found this very weird. Am I missing something here? </p>

CC BY-SA 3.0
2014-04-13T00:25:55.983Z
could you be more specific, what kind of learnability are you referring to? learning a true/false function given examples? yes it does seem a gap here... CSP is more logic/boolean fns & have noticed this somewhat also, it seems there is not a lot of ML on boolean fns, its generally more continuous type fns... a lot of learning theory needs continuous fns eg gradient descent etc...
vzn
CC BY-SA 3.0
2014-04-13T02:16:40.513Z
@vzn I am interested in learning from examples. For instance, PAC learning and VC dimension. I also interested in algorithms for learning the structure (constraint graph) and the parameters (constraint relations). For instance, given a set of examples, try to find the best CSP structure that fits them.
seteropere
CC BY-SA 3.0
2014-04-13T04:11:34.057Z
there are many kinds of [constraint satisfaction problems](http://en.wikipedia.org/wiki/Constraint_satisfaction_problem), true? how does SAT fit into this? are you looking for theoretical analysis or more applied results or either?
vzn
CC BY-SA 3.0
2014-04-13T04:21:31.163Z
@vzn both; although my research is more applied (i.e., proposing a learning algorithm and test it on different datasets). I consider only binary CSPs.
seteropere
CC BY-SA 3.0
2014-04-13T15:35:06.453Z
there are some results on hardness/complexity re AS answer, that seems not exactly to be what you are seeking...? consider also [constraint learning](http://en.wikipedia.org/wiki/Constraint_learning)
vzn
<reference-request><machine-learning><lg.learning><csp>
Learnability of constraint satisfaction problems CSPs?
seteropere
# Learnability of constraint satisfaction problems CSPs?

(Asked by: username_0 on 2014-04-11)

This may sound more like a soft question but I am struggling to find an answer for it.

While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of machine learning and learning theory, there is almost nothing on learning CSPs. Given that CSP is a well known constraint formalism, I found this very weird. Am I missing something here?

**Tags:** reference-request, machine-learning, lg.learning, csp

> **Comments:**
> **username_1**: could you be more specific, what kind of learnability are you referring to? learning a true/false function given examples? yes it does seem a gap here... CSP is more logic/boolean fns & have noticed this somewhat also, it seems there is not a lot of ML on boolean fns, its generally more continuous type fns... a lot of learning theory needs continuous fns eg gradient descent etc...  
> **username_0**: @username_1 I am interested in learning from examples. For instance, PAC learning and VC dimension. I also interested in algorithms for learning the structure (constraint graph) and the parameters (constraint relations). For instance, given a set of examples, try to find the best CSP structure that fits them.  
> **username_1**: there are many kinds of [constraint satisfaction problems](http://en.wikipedia.org/wiki/Constraint_satisfaction_problem), true? how does SAT fit into this? are you looking for theoretical analysis or more applied results or either?  
> **username_0**: @username_1 both; although my research is more applied (i.e., proposing a learning algorithm and test it on different datasets). I consider only binary CSPs.  
> **username_1**: there are some results on hardness/complexity re AS answer, that seems not exactly to be what you are seeking...? consider also [constraint learning](http://en.wikipedia.org/wiki/Constraint_learning)  

---

## 2 answers

### Answer by username_2 on 2014-04-11. Score: 6

You are probably looking for this paper:

* Víctor Dalmau and Peter Jeavons, *Learnability of quantified formulas*, TCS **306** 485–511, 2003. doi:[10.1016/S0304-3975(03)00342-6](http://dx.doi.org/10.1016/S0304-3975%2803%2900342-6)

In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms. This includes CSPs as a special case of more general quantified formulas (since a CSP instance is just an existentially quantified conjunctive formula).

For the Boolean case and also for two broad classes of non-Boolean formulas, there is a dichotomy between polynomially learnable (via the Generating Set algorithm, if the clone contains a "nice" operation) and not, subject to the hypothesis that there exists a public key cryptosystem secure against chosen ciphertext attacks.


---

### Answer by username_1 on 2014-04-13. Score: -2

there are many old SAT search, variable ordering, backtracking etc heuristics that can be regarded as verging on learning algorithms and many are applicable/generalizable to CSPs, and exact boundaries here may be blurring. possibly these have generally traditionally been two different fields, machine learning and constraint satisfaction, but with increasing intersection in more recent times. here are a few research leads. this appears to be an emerging area with some crosspollination with [big data](http://en.wikipedia.org/wiki/Big_data)/[datamining](http://en.wikipedia.org/wiki/Data_mining) eg:

* May 15 – 20, 2011, Dagstuhl Seminar 11201 / [Constraint Programming meets Machine Learning and Data Mining](http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=11201)

  > The second goal was to study the use of machine learning and data mining in constraint programming. Practitioners of constraint programming have to formulate explicitly the constraints that underly their application. This is often a difficult task. Even when the right constraints are known, it can be challenging to formalize them in such a way that the constraint programming system can use them efficiently. This raises the question as to whether it is possible to (semi)- automatically learn such constraints or their formulations from data and experience. Again, some initial results in this direction exist, but we are away from a complete understanding of the potential of this approach.
* [Learning Adaptation to Solve Constraint Satisfaction Problems](http://research.microsoft.com/pubs/77780/lion2009.pdf) Yuehua Xu, David Stern and Horst Samulowitz

  > Abstract. Constraint-based problems are hard combinatorial problems and are usually solved by heuristic search methods. In this paper, we consider applying a machine learning approach to improve the performance of these search-based solvers. We apply reinforcement learning in the context of Constraint Satisfaction Problems (CSP) to learn a value function, which results in a novel solving strategy. The motivation underlying this approach is to solve previously unsolvable instances.
* [Learning cluster-based structure to solve constraint satisfaction problems](http://www.cs.hunter.cuny.edu/%7Eepstein/papers/Springer_online_AMAI.pdf) Xingjian Li · Susan L. Epstein

  > Abstract The hybrid search algorithm for constraint satisfaction problems described here first uses local search to detect crucial substructures and then applies that knowledge to solve the problem. This paper shows the difficulties encountered by traditional and state-of-the-art learning heuristics when these substructures are overlooked. It introduces a new algorithm, Foretell, to detect dense and tight substructures called clusters with local search. It also develops two ways to use clusters during global search: one supports variable-ordering heuristics and the other makes inferences adapted to them. Together they improve performance on both benchmark and real-world problems.

> **Comments:**
> **username_3**: Learning CSPs and learning to solve CSPs seem very different questions.  
> **username_0**: As @LevReyzin stated. Most of the work use the word *learning* in the context of solving CSPs. For instance, learning variable ordering, Learning hardest constraints in the network (to relax them later).  
> **username_1**: LR ok, pt taken, thx for bringing out distinction; however from ML pov there may not be so much difference; refs cover both cases, 1st ref more relevant, mtg covering learning CSPs by multiple researchers...  

---

