Learnability of constraint satisfaction problems CSPs?

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?

• 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
Apr 13, 2014 at 0:25
• @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. Apr 13, 2014 at 2:16
• there are many kinds of constraint satisfaction problems, true? how does SAT fit into this? are you looking for theoretical analysis or more applied results or either?
– vzn
Apr 13, 2014 at 4:11
• @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. Apr 13, 2014 at 4:21
• there are some results on hardness/complexity re AS answer, that seems not exactly to be what you are seeking...? consider also constraint learning
– vzn
Apr 13, 2014 at 15:35

You are probably looking for this paper:

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.

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/datamining eg:

• May 15 – 20, 2011, Dagstuhl Seminar 11201 / Constraint Programming meets Machine Learning and Data Mining

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 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 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.

• Learning CSPs and learning to solve CSPs seem very different questions. Apr 13, 2014 at 16:23
• 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). Apr 13, 2014 at 18:18
• 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
Apr 13, 2014 at 18:29