Intro:
Constriant programming is used to model and solve complex combinatorial problems.
Used in areas like resource allocation, scheduling, planning and design.

Constraint Acquisition:
Acquire the constraint networks from examples classified by the user.
The aim of constraint acquistion is to induce from examples a general constraint network that adequately represents the target problem.
This approach allows then to use the learned network with different initial domains in order to solve further tasks supplied by the user.
E.g. A learner tries to acquire a constraint network representing the sequences of elementary operations that constitute a valid action for a robot.

To put in simple words, if a user has a set of solutions(positive examples) and non-solutions(negative examples) of the problem the learner models the problem as a constraint network.
A user necessarily need not be a human user.

There are 2 constraint acquisition approaches: 
	Passive constraint acquisition, and the 
	Active constraint acquisition.

Passive constraint acquisition: 
Learner cannot ask queries to the user. 
Instead the goal of the learner is to inform the user about the state of it's version space and whether the version space has converged.

Active constraint acquisition: 
The learner can choose an example and ask whether it is a solution or not of the target problem.

Problem Statement: 
Starting from a bias, an initial training set and a query of some type, the goal is to find a polynomial sequence of queries leading to a constraint network representing the target problem.

Terminology:
language:The learner owns a language of relations from which it can build constraints on specified sets of variables.

Constraint basis: Set B of constraints built from the constraint language on the vocabulary

Vocabulary: A vocabulary is represented by a (finite) set X of variables and their domains D in the set of integers.
For the constraint acquisition process the user and learner needs to share a same vocabulary to communicate.

Constraints network: It is a set C of constraints on the vocabulary (X,D), X being the constraint scope and D being the domain.

Example: An example e is a (partial/complete) assignment on a set of variables.

Concept: Given a vocabulary, a concept is a Boolean function over the domain of the variables, assigning to each assignment a value in {0,1}.
It is a map that assigns to each example a value in {0,1}.

Target concept: The concept that returns a 1 for example e iff if e is a solution of the problem the user has in mind.
A target concept is represented by a constraint network.

Ask(e): A classification question asked to the user with variable(e) subset of X
The answer to Ask(e) is yes iff the target network accepts e.

Training set: It is a set of positive or negative examples.

Consistent concept: If the concept is consistent with every example in that training set.

Solution: An complete assignment e is a solution of C iff for all constraints c in C, the constraint does not reject the example e.
A set of constraints C accepts an assignment e iff if there does not exist any constraint from constraint set rejecting e.

Sol(c): The set of solutions of C

Membership query: A query where a user is required to classify an example as positive or negative.

Partial queries: Partial queries are assignments of only part of the variables of the problem.

Recommendation query / AskRec(c) : Asks a user whether or not a predicted constraint belongs to the target constraint network.

Equivalence query: The user is requested to decide whether a proposed concept is equivalent to the target.
In case of a negative answer the user should provide with an example to show the discrepency between the 2 models.
In a setting of constraint acquisition, asking a user equivalence query is unreasonable as the user may not be able to articulate the constraints of the target network directly.
Given any bias and any target concept representable by a Bias, the concept is learnable by equivalence queries.
These queries are helpful to characterize the complexity of learning.

Generalization query: Based on an aggregation of variables into types.
The user provides the variable types and based on these types, generalization queries ask the user whether or not a learned constraint can be generalized to other scopes of variables of the same type as those on the learned constraint.

Identification/Learnability: To find a sequence of queries of some type leading to the detection of a constraint network representing the function.
If the length of the sequence is polynomial in the number of constraints in the bias, the function is said to be learnable by the queries.

Complexity of constraint acquisition:
-The consistency problem can be solved in polynomial time.
	Given a bias and a training set, we compute the set of constraints that are not violated by any positive example in the training set.
	This is done by traversing all positive examples from the training set and removing all constraints violated by such an example.
	By traversing the negative examples and performing constraint checks for them.
	The learner's version space may converge but it may have more than one representative network.
-The convergence problem is much harder than the consistency problem. In fact the convergence problem is coNP-complete.
-There exists biases with fixed arity constraints, training sets and target concepts representable by the bias that are not learnable by membership queries even if the Training set contains a positive example.
-There exists at least a target concept in the subset of concepts composed of all concepts representable by networks composed of n constraints, requiring at least exponential number of queries for identifying it.

Constraint acquisition techniques that do not exploit the structure of the problem can lead the user to answer large number of queries.
Most systems either need an expert to valuate the learned model or need an exponential number of queries to converge on the target constraint network.
When the problem is highly structured and involves a large number of constraints the number of queries to learn the target constraint network is large.

CONACQ Architecture:
The CONACQ algorithm takes as input a bias Band, a training set E, and returns as output a clausal theory T, that encodes the version space.
The algorithm starts from the empty theory and iteratively expands it by encoding each example in the training set. 
If example is negative, we must discard from the version space all concepts that accept x(e).
This is done by expanding the theory with the clause consisting of all literals. 
Dually, if e is positive, we must discard from the version space all concepts that reject x(e). 
This is done by expanding the theory with a unit clause ¬a(c)for each constraint c in (x(e)). 
After encoding the example, a message is returned if the theory is no longer satisfiable. 
When all examples in the training set are processed, the algorithm calls a convergence procedure to determine whether is reduced to a singleton set, or not. 
Finally algorithm returns the resulting theory encoding together with the flag for convergence.

Given a bias and a training set, the clausal representation is the dual Horn formula.
The clausal encoding of a version space can be performed incrementally.
On each incoming example, encode the example as a set of clauses using set of constraints in the bias.
If the example is positive,  
	then discard from the version space all concepts that reject the set of clauses.
If the example is negative, 
	then discard from the version space all concepts that accept the set of clauses.
The resulting theory T is indeed a dual Horn formula because each clause contains at most one negative literal.

Convergence procedure:
A naive strategy for implementing the Convergence procedure is to start from the interpretation I, encoding the maximally specific network, 
and to explore the other models of the Theory in order to find an interpretation I for which the constraint networks are not equivalent.
Yet, due to the exponential number of models of dual Horn theories, and the complexity of constraint network equivalence, such an implementation will be too expensive in most cases. 
The maximally specific and the maximally general concepts are unique, and the convergence is simply testing whether they are both equal.

Building complete background knowledge is often too expensive, in terms of time and space.

QUACQ(Quick Acquisition):
-An active learning system.
-Solves a problem without modeling it even if the user does not have examples of past solutions.
-Reduces the search space by removing all constraints violated by the positive example.
-Iteratively generates membership queries and asks the user to classify them.
-Able to ask the user to classify partial queries.
-Reduces the search space by removing all violated constraints by the positive examples.
-In case of negative answer it focuses onto a constraint in a number of queries logarithmic in the size of the example.
-Allows to converge on teh constraint network in a number of queries logarithmic in the size of the example.

MULTIACQ:
-The paper extends the approach used in QUACQ by extending the number of constraints violated by negative example.
-Main difference between QUACQ and MULTIACQ is the fact that QUACQ learns and focuses on one constraint each time we have a negative example, 
 whereas MULTIACQ tries to learn more than one explanation (constraint) of why the user classifies a given example as negative.

BACKTRACK-E
-Simple backtrack procedure that asks the user about the validity of the assignment generated at a node of the search tree each time the currently learned constraints do not allow it to infer the answer.
-If the query is classified as positive we reduce the bias B, otherwise we learn a constraint using QUACQ principle.

BRANCH&LEARN:
-Simple backtrack search based on elicitation
-Similar to BACKTRACK-E in the way it explores assignments but differs in the way it learns the constraints
-Learns constraints using CONACQ instead of QUACQ.
-Each time example e is classified negative, this algorithm does not ask anything to teh user.
 It simply stores a disjunction representing the set of candidate constraints in Bias rejecting the example.
 At least one of them has to be in the target network.

Solving a CSP without Modeling it:
ASK&SOLVE:
-The idea is to try to extend step by step a scope on which we know at least one assignment accepted by the target network.
-Each time there is a chance that the assignment violates one of the constraints in the bias, the user is asked a query.
 If the answer to the query is negative then a procedure that learns a culprit constraint to avoid generating again and again an assignment rejected for the same reason.
-Elicitation based solver that tries to find the best tradeoff between learning and solving to converge on a solution.
-If we try to go to a complete assignment, this can lead to expensive constraint elicitation steps on long negative assignments when the problem is critically constrained.
 If we promote exploring first plenty of short assignments, this allows a fast and cheap learning of the constraints.
-Several strategies (variable ordering, Restart policies) are also proposed to speed up even more convergence on a solution.
	-Restart policies: Fixed cutoff, Geometric, and Luby(goal is to cut the search early enough to escape from bad subtrees)
	-Variable ordering: In what order to select variables in the search following immediately the restart.
	 Using Random, lexicographic, reverse lexicographic order(variables in the scope are reversed), continous-Lex(variant of the lexicographic order)

[Elicitation strategies for soft constraint problems with missing preferences,2010]
A preference elicitation mechanism solves soft constraint problems where some of the preferences are unspecified.
The idea is to combine a branch and bound search with elicitation steps where candidate solutions are presented to the user who provides missing preferences on the variables.
When restricted to hard constraint problems, this approach becomes very close to the matchmaker agent requiring the user to be able to express the constraints one by one.

PREDICT&ASK: Generic constraint recommender algorithm
An algorithm based on the prediction of missing constraints in the partial network learned so far.
Missing information can asked directly to the user though recommendation queries.
Given the constraint graph learned so far, can we infer which new constraints are more likely to belong to the target constraint network.
This can be attributed as Link prediction problem in the partial constraint graph learned so far.
It is a generic constraint recommender algoirthm that can be plugged into any constraint acquisition system.
The techniques that are used to predict missing constraints:
When a constraint network has some structure, variables of the same given type are often involved in constraints with the same relation.
When variable types are not known in advance, predicting type similarity or type proximity of variables could be done by prediction link techniques.
The techniques in link prediction can compute and assign a score to pairs of nodes based on the input graph and then produce a ranked list in the decreasing order of scores.
They can be viewed as computing a measure of proximity or similarity between nodes with respect to the network topology.
Most of these techniques are based on node neighbourhood or on path ensemble based techniques(Adamic Adar Index/Leicht-Holme-Newman Index).
Incorporating PREDICT&ASK into QUACQ gives a boosted version called P-QUACQ.

GENACQ:
Uses the structure of the problem in an opportunistic kind of query called "Generalization query"
Generalization queries require the aggregation of variables into types which is not always a simple task for non-expert users.
The aggregation of variables into types may not always be a straightforward task for the user especially when the problem under consideration has a hidden structure
The algorithm is able to learn types during the constraint acquisition process
The idea is to infer potential types by analyzing the structure of the current constraint network and to use the extracted types to ask generalization queries
By using such generalization queries, the number of queries needed to converge on the target constraint network can be significantly reduced
The variables of the same type are often connected with similar constriants whereas the variables of different types are connected in a weaker way.
The idea of detecting tightly connected sub-graphs occurs in social networks and its characteristic is community structure.
A network or a graph is said to have community structure, if the nodes of the network can be easily grouped into 
(potentially overlapping) sets of nodes such that the groups have more internal edges than outgoing edges. 
Each such group is called a community.
So potential types can be found out by finding communities in the constraint network.

MatchMaker:
The matchmaker agent is an interactive process where the user is able to provide one of the constraints of the target problem each time the system proposes an incorrect solution.

CONACQ or Modelseeker:
-Requires positive examples to learn.
-Assumption that the user is able to provide examples of solutions and non-solutions of the target problem or to answer membership queries.

CONACQ 1 learns a set of constraints that correctly classifies all the examples given so far.
CONACQ 2 proposes examples to the user to classify(membership queries).
User can give arguments to converge more rapidly.

Future scope:
Link prediction in dynamic graphs
RL to decide on the use of neighbourhood-based predictions or path-ensemble-based predictions.
[A Probabilistic Constraints Approach to Language Acquisition and Processing]

Random thoughts:
Decision trees as hypothesis space and generalizing to neural networks