Ms Elise Vareilles

Joel Gilles

Phillipe

Gaelle, Olivier Natasa

Nawfal, Adil, Mohamed Amine

Youssef K Abdelhak

Dr Abderrazak Daoudi

Keywords: Artificial Intelligence (AI), Constraint Programming (CP), Constraint Satisfaction Problems (CSP), Constraint Acquisition, Learning, Graph Community Detection, Recommendation Systems Intelligence Artificielle, Programmation par contraintes, Problèmes de satisfaction de contraintes, Acquisition de contraintes, Détection de communautés, Systèmes de recommandation Artificial Intelligence, Constraint Programming, Constraint Acquisition, Graph Community Detection, Recommendation Systems

Constraint Programming is a general framework used to model and to solve complex combinatorial problems. However, modeling a problem as a constraint network requires significant expertise in the field. Such level of expertise is a bottleneck to the broader uptake of the constraint technology. To alleviate this issue, several constraint acquisition systems have been proposed to assist the non-expert user in the modeling task. Nevertheless, in these systems the user is only asked to answer very basic questions. The drawback is that when no background knowledge is provided, the user may need to answer a large number of such questions to learn all the constraints. In this thesis, we show that using the structure of the problem under consideration may improve the acquisition process a lot. To this aim, we propose several techniques. Firstly, we introduce the concept of generalization query based on an aggregation of variables into types. Secondly, to deal with generalization queries, we propose a constraint generalization algorithm, named GENACQ, together with several strategies. Thirdly, to make the build of generalization queries totally independent of the user, we propose the algorithm MINE&ASK, which is able to learn the structure, during the constraint acquisition process, and to use the learned structure to generate generalization queries. Fourthly, toward a generic concept of query, we introduce the recommendation query based on the link prediction on the current constraint graph. Fifthly, we propose a constraint recommender algorithm, called PREDICT&ASK, that asks recommendation queries, each time the structure of the current graph has been modified. Finally, we incorporate all these new generic techniques into QUACQ algorithm leading to three boosted versions, G-QUACQ, M-QUACQ, and P-QUACQ. To evaluate all these techniques, we have made experiments on several benchmarks. The results show that the extended versions improve drastically the basic QUACQ.

Résumé

La Programmation par Contraintes est un cadre général utilisé pour modéliser et résoudre des problèmes combinatoires complexes. Cependant, la modélisation d'un problème sous forme d'un réseau de contraintes nécessite une bonne expertise dans le domaine. Ce niveau d'expertise est un obstacle majeur pour une large diffusion de la programmation par contraintes. Pour remédier à ce problème, plusieurs systèmes d'acquisition de contraintes ont été proposés pour aider l'utilisateur dans la tâche de modélisation. Dans ces systèmes, l'utilisateur ne répond qu'à des questions très simples. L'inconvénient est que lorsqu'aucune connaissance de base n'est fournie, l'utilisateur peut avoir besoin de répondre à un grand nombre de questions pour apprendre toutes les contraintes. Dans cette thèse, nous montrons que l'utilisation de la structure du problème peut améliorer considérablement le processus d'acquisition. Pour ce faire, nous proposons plusieurs techniques. Tout d'abord, nous introduisons le concept de requête de généralisation basée sur une agrégation de variables sous forme de types. Deuxièmement, pour faire face aux requêtes de généralisation, nous proposons un algorithme de généralisation de contraintes, nommé GENACQ, ainsi que plusieurs stratégies. Troisièmement, pour rendre la construction de requêtes de généralisation totalement indépendante de l'utilisateur, nous proposons l'algorithme MINE&ASK, qui est en mesure d'apprendre la structure au cours du processus d'acquisition, et d'utiliser la structure apprise pour générer des requêtes de généralisation. Quatrièmement, pour aller vers un concept générique de requête, nous introduisons la requête de recommandation basée sur la prédiction de liens dans le graphe de contraintes apprises jusqu'à présent. Cinquièmement, nous proposons un algorithme de recommandation de contraintes, appelé PREDICT&ASK, qui demande à l'utilisateur de classifier des requêtes de recommandation chaque fois que la structure du graphe courant a été modifiée. Enfin, nous intégrons toutes ces nouvelles techniques dans l'algorithme QUACQ, menant à trois nouvelles versions, à savoir G-QUACQ, M-QUACQ, et P-QUACQ. Pour évaluer toutes ces techniques, nous avons fait des expérimentations sur plusieurs jeux de données. Les résultats montrent que les versions étendues améliorent considérablement le QUACQ de base.

Introduction

Constraint Programming (CP) is a very active research area within Artificial Intelligence (AI), and its importance has increased dramatically within the last years. CP is a highly successful technology for solving a wide range of combinatorial problems, such as scheduling, resource allocation, and design. Nowadays, a number of companies, like ILOG and Dash Optimization, sell constraint programming toolkits, which are used by companies as diverse as Amazon.com, British Airways, Cisco, Ford, HP, SNCF, and Volvo.

Constraint programming is a declarative style of modeling combinatorial problems. The user identifies the decision variables, their possible domain of values, and specifies constraints over the allowed values. For instance, the constraint X 1 +X 2 ≤ X 3 specifies that any combination of values for variables X 1 , X 2 and X 3 has to be such that the sum of X 1 and X 2 less than or equals X 3 . Sophisticated AI search techniques like constraint propagation, which allow to prune irrelevant parts of the search tree, and chronological backtracking can then be used to find solutions.

Unfortunately, modeling a combinatorial problem as a constraint network remains limited to specialists in the field. However, it is well known that modeling a combinatorial problem in the constraint formalism requires significant expertise in constraint programming [START_REF] Freuder | Modeling: The final frontier[END_REF]Puget, 2004]. Such a level of knowledge prevents non-expert users from being able to use constraint networks without the help of an expert. Consequently, this has a negative effect on the uptake of constraint technology in the real-world by novices.

One answer to the task of modeling is constraint acquisition, which is an active research field that lies in the conjunction of two fields, namely Constraint Programming and Machine Learning. The idea behind constraint acquisition is to assist Introduction a non-expert user in modeling her problem as a constraint network. Several constraint acquisition systems have been introduced in the last decade [START_REF] Bessiere | A satbased version space algorithm for acquiring constraint satisfaction problems[END_REF][START_REF] Bessiere | Querydriven constraint acquisition[END_REF][START_REF] Lallouet | On learning constraint problems[END_REF][START_REF] Beldiceanu | A model seeker: Extracting global constraint models from positive examples[END_REF][START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. Unfortunately, Most of these constraint acquisition systems interact with the user by asking her to classify an example as positive or negative. Such queries do not use the structure of the problem and can thus lead the user to answer a large number of queries. Hence, it can be hard to put constraint acquisition in practice.

The propose of this thesis is to provide new approaches to constraint acquisition in order to make it more efficient in practice. However, we show that learning and using the structure of the problem under consideration may accelerate the process of learning a lot. To this end, we introduce two new concept of queries that use the structure of the problem. The first one, called generalization query, is an opportunistic query based on the aggregation of variables into types. Generalization query asks the user whether or not a learned constraint can be generalized on other variables of the same types as those of the learned constraint. The second query, called recommendation query, based on the analysis of the partial constraint graph learned so far, by using techniques borrowed from data mining and link prediction in dynamic graphs. Recommendation query asks the user whether or not a predicted constraint may belongs to the target network.

We propose several algorithms that manage these new concept of queries. First, we propose GENACQ algorithm, which is a generic algorithm that asks generalization queries. Second, we present MINE&ASK algorithm, which is able to learn types during the constraint acquisition process and to use the extracted types to build generalization queries. Third, we introduce PREDICT&ASK, which is a constraint recommender algorithm that uses the structure, of the constraint graph learned so far, to predict new constraints that may belong to the target network, and to ask the user to classify recommendation queries. Finally, all these generic algorithms are incorporated into QUACQ leading to three boosted versions, which are G-QUACQ (i.e, QUACQ+GENACQ), M-QUACQ (i.e, QUACQ+MINE&ASK), and P-QUACQ (i.e, QUACQ+ PREDICT&ASK). To show the efficiency of our new techniques, we experimentally evaluate their benefit on several benchmark problems. The results show that G-QUACQ, M-QUACQ and P-QUACQ dramatically improve the basic QUACQ algorithm in terms of number of queries.

The organization of this thesis is as follows. In chapter 2, we present the essential material to understand the technical presentation of this thesis. We present also the state of the art related to the constraint acquisition. In chapter 3, we introduce the concept of generalization query based on an aggregation of variables into types. We present a constraint generalization algorithm that can be plugged into any constraint acquisition system. We propose several strategies to make our approach more efficient in terms of number of queries. Finally, we experimentally compare the recent QUACQ system to an extended version boosted by the use of our generalization functionality. The results show that the extended version dramatically improves the basic QUACQ. This chapter is based on the research previously published in the following papers:

-C. Bessiere, R. Coletta, A. Daoudi In chapter 4, we present a new algorithm that is able to learn the structure of the problem 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. Our approach gives good results although no knowledge on the types is provided. Chapter 4 is based on the research previously published in the following paper:

-A. Daoudi In chapter 5, we propose PREDICT&ASK, an algorithm based on the prediction of missing constraints in the partial network learned so far. Such missing constraints are directly asked to the user through recommendation queries, a new, more informative kind of queries. PREDICT&ASK can be plugged in any constraint acquisition system. We experimentally compare the QUACQ system to an extended version boosted by the use of our recommendation queries. The results show that the extended version improves the basic QUACQ. Chapter 5 based on the the following paper:

-A. Daoudi, Y. Mechqrane, C. Bessiere, N. Lazaar, and E.H. Bouyakhf. Constraint acquisition using Recommendation Queries. In IJCAI 2016, New York City, USA.

In chapter 6, we conclude this thesis and give some perspective to constraint acquisition.

CHAPTER 2 Background Preamble

In this chapter, we present the essential material to understand the technical presentation of this thesis. We then present the state of the art related to the constraint acquisition.

Constraint Programming

This section introduces the formalism of constraint programming (CP), which can represent many academic and industrial problems. More details can be found in the text books [START_REF] Lecoutre | Constraint Networks: Targeting Simplicity for Techniques and Algorithms[END_REF]Rossi et al., 2006a;[START_REF] Dechter | Constraint processing[END_REF].

Constraint programming is a declarative paradigm. The basic idea underlying CP is to model a combinatorial problem as a constraint network. That is, to specify a set of variables, a set of domain values, and a set of constraints. Each constraint is a rule that impose a limitation on the values that a variable, or a combination of variables, may be assigned. A solution of the constraint network is an assignment of variables to domain values that satisfies all constraints in the network. The Constraint Satisfaction Problem (CSP) is, therefore, the problem of determining whether Background a solution exists, finding one or all solutions, finding whether or not a partial instantiation can be extended to a full solution. The CSP is not known to admit polynomial running time algorithms to solve its instances; hence, CSP is NP-hard.

After this brief overview of CP, we first start with formal definition of the central concepts.

Basic Definitions

Constraint satisfaction problems include two important components, namely variables with associated domains and constraints. Definition 2.1 (Variable and Domain). Variables are objects or items that can take on a variety of values. The set of possible values for a given variable is called its domain. In our context, the pair (X,D) is called the vocabulary, with X is a finite set {x 1 ,...,x n } of variables, and D = {D(x 1 ),...,D(x n )} are a finite subsets of Z named the domains.

The second component of a constraint satisfaction problem is the set of constraints themselves. For the purpose of clarity, we limit ourselves to binary constraints; that is, constraints with a scope involving only two variables. In the following, we use c ij to refer to the binary relation that specifies which pairs of values are allowed for the sequence 〈x i ,x j 〉. For instance, = 12 denotes the constraint specified on 〈x 1 ,x 2 〉 with the relation "not equal".

A model that includes variables, their domains, and constraints is called a constraint network.

Definition 2.3 (Constraint Network).

A constraint network over a given vocabulary (X,D) is a finite set C of constraints.

In real problems, variables often represent components of the problem that can be classified in various types. For instance, in a school time-tabling problem, variables can represent teachers, students, rooms, courses, or time-slots. Such types are often known by the user.

Definition 2.4 (Variable Type).

A type T i is a subset of variables defined by the user as having a common property. A variable x is of type T i if and only if x ∈ T i . A scope var = (x 1 ,...,x k ) of variables is said to belong to a sequence of types s = (T 1 ,...,T k ) (denoted by var ∈ s) if and only if x i ∈ T i for all i ≤ k. Consider s = (T 1 ,T 2 ,...,T k ) and s ′ = (T ′ 1 ,T ′ 2 ,...,T ′ k ) two sequences of types. We say that s ′ covers s (denoted by s ⊑ s ′ ) if and only if T i ⊆ T ′ i for all i ∈ 1..k. A relation r holds on a sequence of types s if and only if (var,r) ∈ C for all var ∈ s. A sequence of types s is maximal with respect to a relation r if and only if r holds on s and there does not exist s ′ covering s on which r holds.

When a variable is assigned a value from its domain, we say that the variable has been instantiated.

Definition 2.5 (Assignment/Example

). Given a vocabulary (X,D). Let Y = {x 1 ,...,x k } be a subset of X. An assignment is a vector e y = {v 1 ,...,v k } in D |Y| . This assignment is partial if and only if Y = X, complete otherwise (dented by e). e y is rejected by a constraint c (i.e., e y | = c) if and only if var(c) ⊆ var(e y ) and the projection e y [var(c)] of e y on var(c) is not in c. Otherwise we say that e y is accepted by c.

A solution of the constraint network is an assignment of variables to domain values that satisfies all constraints of the network.

Definition 2.6 (Solution of a Constraint Network).

A solution of a Constraint Network C is an assignment of each variable of the constraint network to a value in its domain such that all the constraints are simultaneously satisfied. Formally speaking, a complete assignment e of X is a solution of C if and only if for all c ∈ C, c does not reject e. We denote by sol(C) the set of solutions of C.

Definition 2.7 (Constraint Graph).

A constraint graph can be associated with a constraint graph G = (V,E), where vertices V represent variables X, and edges E represent constraints C.

Examples of Constraint Networks

In this section, we present some common examples of problems that can be intuitively modeled as constraint networks. The Description. The classic example used to illustrate a constraint satisfaction problem is the n-queens problem (see Figure 2.2). The problem is to place n queens on a n×n chessboard such that the placement of no queen constitutes an attack on any other. The Model. One possible constraint network formulation of the problem is as follows. There is a variable for each column of the chessboard. Variables: X = {x 1 ,...,x n }; Domains: D i = {1,...,n}; Constraints: -∀i, j ∈ {1,...,n} x i = x j (One queen each row.) -∀i, j ∈∈ 1,...,n |x ix j | = |i -j| (One queen diagonally.)

Queens Problem

Graph-coloring Problem

The Description. Another example of constraint network is the graph-coloring problem. In this problem, the goal is to color the nodes of a graph so that there is not a pair of linked nodes colored with the same color. Each node has a finite number of possible colors. This problem can be modeled as a constraint network by representing each node of the graph as a variable. The domain of each variable is defined by the possible colors that this variable can take. There exits a constraint between each pair of linked variables that forbids these variables to have the same color.

Sudoku Problem

The Description. Sudoku, originally called Number Place, is a logic-based combinatorial number-placement puzzle (Figure 2.4). The task is to fill a 9 × 9 grid with digits so that each column, each row, and each block contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution. The Model. The Sudoku puzzle can be modeled as follows.

Variables: X = {x 11 ,...,x 99 };

Domains: D = {D ij = {1,...,9} | ∀i, j ∈ 1,...,9}; Constraints: -∀i ∈ 1,...,9 AllDifferent(x ij | j ∈ 1,...,9); Background -∀j ∈ 1,...,9 AllDifferent(x ij | i ∈ 1,...,9);
-∀i, j ∈ 1,...,9 AllDifferent(x (3i+k)(3j+q) | k,q ∈ 1,...,3).

Solving Methods

Constraint satisfaction problems are solved using search techniques. The most used techniques are variants of backtracking, constraint propagation, and local search.

Backtracking Search

Backtracking is a recursive algorithm [START_REF] Knuth | The Art of Computer Programming, Volume I: Fundamental Algorithms[END_REF]Rossi et al., 2006b]. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it consecutively. For each value, the consistency of the partial assignment with the constraints is checked, and in case of consistency, a recursive call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. In the literature, several variants of backtracking have been proposed. Backmarking [START_REF] Gaschnig | A general backtrack algorithm that eliminates most redundant tests[END_REF] improves the efficiency of checking consistency. Backjumping [START_REF] Mark | Hybrid algorithms for the constraint satisfaction problem[END_REF] allows saving part of the search by backtracking "more than one variable" in some cases. Constraint learning [START_REF] Daoudi | Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition[END_REF] infers and saves new constraints that can be later used to avoid exploring part of the tree search. Look-ahead [START_REF] Haralick | Increasing tree search efficiency for constraint satisfaction problems[END_REF]] is also often used in backtracking to anticipate the effects of choosing a variable or a value, thus, sometimes determining in advance when a subproblem is satisfiable or unsatisfiable.

Propagation

Constraint propagation techniques are methods used to modify the structure of a constraint satisfaction problem [START_REF] Bessiere | Constraint propagation[END_REF]. More accurately, they are methods that enforce a form of local consistency, which are conditions related to the consistency of a group of variables and/or constraints. Constraint propagation has various uses. First, it change a problem into equivalent one, which is usually simpler to solve. Second, it may prove satisfiability or unsatisfiability of problems. This is not guaranteed to happen in general; however, it always happens for some forms of constraint propagation and for some certain kinds of problems. The most used form of local consistency are arc consistency, hyper-arc consistency, and path consistency. The most popular constraint propagation method is the AC -3 algorithm [START_REF] Mackworth | Consistency in networks of relations[END_REF], which enforces arc consistency.

Local search

Local search methods [START_REF] Holger | Local search methods[END_REF]] are incomplete satisfiability algorithms. They may find a solution of a problem, but they may fail even if the problem has a solution. They work by iteratively improving a complete assignment over the variables. At each step, it changes the values of some variables, with the overall purpose of increasing the number of constraints satisfied by this assignment. based in that principle, the min-conflicts algorithm [START_REF] Minton | Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems[END_REF]] is a local search algorithm dedicated for solving CSPs. In practice, local search appears to work well when these changes are also affected by random choices. Integration of backtracking search with local search has been developed, leading to hybrid algorithms [START_REF] Wallace | Finding the right hybrid algorithm -A combinatorial meta-problem[END_REF].

Constraint Language and Basis

In this section, we present two essential components for the constraint acquisition problem, which are constraint language and basis. A constraint language is a set of relations that restricts the type of constraints that are allowed when modeling a constraint satisfaction problem as a constraint network.

Definition 2.8 (Constraint Language).

A constraint language is a set Γ = {r 1 ,...,r t } of t relations over some subset of Z.

We are now ready to define the basis for the constraint acquisition problem. The basis is the set of all possible constraints that are candidate for being in the target constraint network. Background Definition 2.9 (Basis). Given a vocabulary (X,D) and a constraint language Γ . The basis for the constraint acquisition problem is the set B of all constraints c for which var(c) is a sequence of variables of X, and there exists a relation

r i in Γ such that rel(c) = r i ∩ D |var(c)| .
It is worth to notice that the building of a basis B using a constraint language of bounded arity k is polynomial in the input dimension; the size of B is bounded by n kt in the general case, and by n 2t in the case of binary constraint networks. However, if Γ contains global constraints, th size of B is no longer polynomial; as one global constraint gives rise to 2 n possible constraints in B.

Example 2.1. Consider the binary constraint language Γ = { =,≥,≤} over Z. Given the vocabulary defined by X = {x 1 ,x 2 ,x 3 } and D = {1,2,3,4}, we observe that the constraint network C = { = 12 ,≥ 12 ,≤ 23 } is indeed a subset of the basis B = { = 12 ,≥ 12 ,≤ 12 , = 13 ,≥ 13 ,≤ 13 , = 23 ,≥ 23 ,≤ 23 }.

Concept Learning

Inducing general functions from specific training examples is a main issue of machine learning [START_REF] Mitchell | Machine learning[END_REF]. Concept Learning consists on acquiring the definition of a general concept from positive and negative training examples of the target concept. Concept Learning can be seen as a problem of searching through a predefined space of potential hypotheses for the hypothesis that is consistent with the training examples. The hypothesis space has a general-to-specific ordering of hypotheses, and the search can be efficiently organized by taking advantage of a naturally occurring structure over the hypothesis space.

In our setting, which is acquiring constraints from examples, a general concept is a Boolean function over D X = Π x i ∈X D(x i ); that is, a map that assigns to each example e ∈ D X a value in {0,1}. A representation of a general concept f is a constraint network C for which f -1 (1) = sol(C). A general concept f is said to be representable by a basis B if there is a subset C of B such that C is a representation of f. We call target concept the concept f T that returns 1 for e if and only if e is a solution of the problem the user has in mind. The target concept is represented by a target constraint network denoted by C T .

Definition 2.10 (Membership query).

A membership query Ask(e), with var(e) ⊆ X, is a classification question asked to the user, where e is an assignment in D var(e) = Π x i ∈var(e) D(x i ). A set of constraints C accepts an assignment e if and only if there does not exist any constraint c ∈ C rejecting e. The answer to Ask(e) is yes if and only if C T accepts e.

Constraint Acquisition

In Constraint Programming, it is well known that the modeling task is a bottleneck [START_REF] Freuder | Modeling: The final frontier[END_REF]Puget, 2004]. This bottleneck has a negative effect on the uptake of CP technology on a large scale, especially in the industrial field. An answer to the modeling task is constraint acquisition, which lies in the conjunction of two research areas, namely Constraint Programming and Machine Learning. The idea behind that is to assist a non-expert user in modeling her problem as a constraint network. Several constraint acquisition systems have been proposed in the last decade; we will survey the existing systems in the following section. In this section, we formally define constraint acquisition. Constraint acquisition can be seen as an interplay between the user and the learner (see Figure 2.5). The learner has a combinatorial problem in her mind, noted C T . We suppose that the common knowledge between the user and the learner is the vocabulary (X,D). In one hand, the user has in her disposal a set of examples that represent both solutions and non-solutions of her problem. In the other hand, the learner owns a library of constraints L and a basis B that we suppose capturing the problem of the user. The objective of the learner is to induce a constraint network C L that best fits the training examples proposed by the user, and which is equivalent to C T (i.e, C L ≡ C T ). That is, a constraint network that accepts the positive examples and rejects the negative ones.

In the literature, there are two forms of constraint acquisition. The first form is a passive learning, and the second form is an active learning.

Passive Learning

In a passive constraint acquisition context, there is no interplay between the user and the learner. The user provides a set of positive and negative examples, and the learner tries to find a set of constraints that classifies the training examples.

Active Learning

By contrast, in an active setting, the user dialogs with the learner. The learner proposes informative examples, and the user classifies them as positive or negative. The benefit of such kind of learning is that it provides less of a burden on the user. Definition 2.12 (Active constraint acquisition problem). Given a basis B and an unknown user classification function f, the active constraint acquisition problem is to find a converging sequence Q = {q 1 ,...,q m } of queries. That is, a sequence such that q i+1 is a query relative to B and C L , where C L is the constraint network learned so far, i.e the learned constraint network after classifying q i . After the classification of the query q m , the learner converges on the target constraint network, i.e C L ≡ C T .

The general context underlying this thesis is the active constraint acquisition. Our objective is to make this kind of learning more efficient in practice despite the context of use.

Constraint Acquisition as a Search

Constraint acquisition can be seen as a form of search through a search space. The search space can be represented as a lattice (see Figure 2.6). Each node of the lattice is a possible constraint network. The top ⊤ of the lattice represents the general constraint network, which accepts all examples provided by the user. The specific born of the lattice is represented by all constraints of the basis B. The search space is explored via examples classified by the user. In the case of a positive example, we prune the search space by removing all constraints that reject the example. Hence, we generalize our learned constraint network, and we then go up through the lattice. In the case of a negative example, we learn at least one constraint that explains the rejection of that example. That is, we specify our learned constraint network, by going dawn through the lattice.

Existing Constraint Acquisition Systems

In this section, we survey the existing constraint acquisition systems proposed in the last years. Given an element e of E, f(e) = 1 if and only if e is a solution of the problem that the user has in mind. That is, e is a positive example noted e + . If e is a non-solution of the problem, therefore, f(e) = 0, and we say that the example is negative, noted e -.

We say that a constraint network C is consistent with the training data E f if and only if each example e + ∈ E f belongs to the set of solutions of C, and each e -∈ E f is a non-solution of C. Given a basis B and a set of training data E f , the problem of constraint acquisition consists on finding a constraint network C admissible for B and consistent with the training data E f . CONACQ.1 is a constraint acquisition system based on the version space introduced by Mitchel in [START_REF] Mitchell | Machine learning[END_REF]

C ij ∈ φ(I) iff C ij = {b p ij ∈ B | I(b p ij ) = 1} An interpretation I is a model of the clausal theory K if K is
true in I according to the standard propositional semantic. The set of all the models of K is noted Models(K).

The construction of K is as follows. For each training example e provided by the user, CONACQ.1 builds the set k(e), of literals corresponding to the constraints b ij ∈ B, that rejects e. Then, CONACQ.1 adds iteratively a set of clauses such that, for each interpretation I of Models(K), the network φ(I) classifies correctly the the training examples given so far, as well as the example e. The update of the clausal theory differs according to the learning class of e:

-If e is a negative example, then one of the constraints in k(e) explains the rejection of e. We then add to K the disjunction { b ij ∈k(e) b ij } of elements of k(e).

-If e is a positive example, then CONACQ.1 is ensured that no one of the constraints of k(e) belongs to the target network. Consequently, K is updated by adding the conjunction of the unitary clauses ¬b ij of k(e).

The analysis of positive instances of E f allows to simplify, with unitary propagation, the clauses that explain the rejection of negative examples. The correction of the algorithm CONACQ.1 is formulated by the theorem 2.1.

V B (E f ) = {φ(m) | m ∈ Models(K)}
Proof. The proof of the theorem 2.1 is given in [START_REF] Bessiere | A satbased version space algorithm for acquiring constraint satisfaction problems[END_REF].

CONACQ.1 has numerous advantages. Firstly, the formulation is generic; therefore, it can use any SAT solver as a basis for version space learning. Secondly, it can exploit powerful SAT concepts, such as unit propagation and backbone detection to improve learning rate. Finally, CONACQ.1 can easily incorporate domain-specific knowledge in constraint programming to improve the quality of the learned network. Specifically, for handling redundant constraints in constraint acquisition, two generic techniques have been developed. The first is based on the notion of redundancy rules, which can deal with some forms of redundancy. The second technique, based on backbone detection, is far more powerful.

Despite its distinct number of advantages, CONACQ.1 has also some limitations.

CONACQ.2

To overcome the limitations reproached to CONACQ.1, Bessiere et al. have proposed an active learning version, called CONACQ.2 [START_REF] Bessiere | Querydriven constraint acquisition[END_REF]. The system CONACQ.2 proposes examples to the user to classify as solutions or nonsolutions. Such questions are called membership queries [START_REF] Angluin | Queries and concept learning[END_REF].

Description of CONACQ.2

In order to generate queries, the authors proposed several approaches. First, a random affectation to the variables, which is a baseline approach. Second, a query with a small K(e). Finally, a query with a large k(e). It is worth to notice that using these approaches could generate useless queries. In fact, a query does not contain information if it is rejected by the version space. We then talk about redundant queries.

Definition 2.16 (A redundant query).

A redundant query is a query that do not allow us to learn new informations. Let e be an example, we have tow cases of redundant queries:

-Either k(e) = ∅ and in this case we automatically detect that e is a solution; -Or all constraints rejecting e are already in K; then, any constraint network in the version space accepts e.

Hence, redundant queries are useless, and it is not necessary asking the user to classify them.

To make CONACQ.2 more efficient in terms of number of queries, the authors propose some optimizations. They propose to break some clauses of K. That is, they propose to compute a query with k(e) containing a strict subset of literals present in Background the clause that they wish to break. If this query is classified as negative, they get a smaller clause that contains only literals existing in k(e). Otherwise, they decrease the size of the clause by setting all literals of k(e) to false. Note that if one seeks a query with a k(e) of size 1, and if the query is classified by the user as negative; then, the clause will be simplified to a single variable, which must therefore be true.

The last optimization, proposed by the authors, concerns a case occurring if they try to break clauses. This case arises when they force the not fixed variables to be true in order to such variables do not appear in k(e). In this case, it is possible that no query exists. They propose to extract a conflict set S of literals and to add the clause b ij ∈S ¬b ij forcing at least one of the variables to be false. In practice, there are several methods to produce such conflict sets. One method is, for each variable b ij ∈ k(e), to test whether to fix it to true; then, K becomes inconsistent. In this case, this variable must be false.

Even that CONACQ.2 is active and generates only informative examples, it remains exponentially large in terms of number of queries; it may require a large number of queries to get the target constraint network. Thus, it is hard to put CONACQ.2 in practice. An other weakness of CONACQ.2 is that it is not able to learn global constraints that are not decomposable.

MODELSEEKER

In [START_REF] Beldiceanu | A model seeker: Extracting global constraint models from positive examples[END_REF]

Description of MODELSEEKER

The general schema of MODELSEEKER is shown in Figure 2.7. Here, we will give a general overview of the different steps of the system. MODELSEEKER takes as input positive examples of the problem that we want to model as a constraint network. Transformation In the first step, MODELSEEKER tries to convert the format of input examples to other more appropriate representations. For instance, it tries to replace a boolean format with finite domain values. MODELSEEKER also converts different graph representations into the successor variable form used by the global constraints in the catalog. Candidate Generation The second step (Sequence Generation) tries to group the variables of the example into regular subsets. For instance, it interprets the input vector as a matrix and creates subsequences for all rows and all columns. In the Argument Creation step, MODELSEEKER creates call patterns for constraints from the subsequences. it can try each subsequence on its own, or combine pairs of subsequences, or use all subsequences together in a single collection. It also tries to add additional arguments based on functional dependencies of constraints, described as meta-data in the global constraint catalog. For each call pattern, MODELSEEKER then calls the Constraint Seeker to discover matching constraints, which satisfy all subsequences of each example. Only the highest ranking candidates are retained for further analysis. Candidate Simplification After the Constraint Seeker step, MODELSEEKER potentially has a very large list of possible candidate global constraints (up to 2 000 global constraints for some examples). The next step is to reduce this list as much as possible. first, MODELSEEKER applies a Dominance Check to remove all candidate constraints that are implied by other constraints in the candidate list. The dominance check is the core of modeling system, helping to remove useless constraints from the candidate list. In the last step before the final candidate list output, the system removes trivial constraints and simplifies some constraint pattern. At the end of this step, MODELSEEKER performs a ranking of the remaining candidates based on the constraint and sequence generator used. Code Generation As a side effect of the initial transformation in the first step, MODELSEEKER generates potential domains for the variables of the problem under Background consideration. In the default case, the system just creates variable domains using all values occurring in the examples. But, for some graph-based transformations a more accurate domain definition is used. At the last step, which is Code Generation, given the candidate list and domains for the variables, It can be easily to generate code for a model using the constraints. MODELSEEKER produces SICStus Prolog code using the call format of the catalog. The generated code can then be used to validate the provided examples or to find solutions for the learned constraint network.

MODELSEEKER remains the only system that deals with global constraints. The major drawback of MODELSEEKER is that it does not handle all global constraints in the catalog [START_REF] Beldiceanu | Global constraint catalogue: Past, present and future[END_REF]. It deals only with 67 global constraints. Another reproach to that system is that it learns only from positive examples; hence, it makes the system hard to put in practice, as the provide of such examples by a novice is not an obvious task.

QUACQ

QUACQ is a recent active learner system that is able to ask the user to classify partial queries [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. Using partial queries and given a negative example, QUACQ is able to find a constraint of the problem the user has in mind in a number of queries logarithmic in the size of the example. This key component of QUACQ allows it to always converge on the target set of constraints in a polynomial number of queries. However, even that good theoretical bound can be hard to put in practice. For instance, QUACQ requires the user to classify more than 8000 examples to get the complete Sudoku model.

Description of QUACQ

QUACQ takes as input a basis B on a vocabulary (X,D). It asks partial queries of the user until it has converged on a constraint network C L equivalent to the target network C T , or collapses. When a query is answered yes, constraints rejecting it are removed from B. When a query is answered no, QUACQ enters a loop (functions FindScope and FindC) that will end by the addition of a constraint to C L .

QUACQ (see Algorithm 1) initializes the network C L it will learn to the empty set (line 2). If C L is unsatisfiable (line 6), the space of possible networks collapses because there does not exist any subset of the given basis B that is able to correctly classify the examples already asked of the user. In line 8, QUACQ computes a complete assignment e satisfying C L but violating at least one constraint from B. If such an example does not exist (line 10), then all constraints in B are implied by C L , and we have converged. If we have not converged, we propose the example e to the user, who will answer by yes or no. If the answer is yes, we can remove from B the set κ B (e) of all constraints in B that reject e (line 12). If the answer is no, we are sure that e violates at least one constraint of the target network C T . We then call the function FindScope to discover the scope S of one of these violated constraints (line The recursive function FindScope (see Algorithm 2) takes as parameters an example e, two sets R and Y of variables, and a Boolean ask_query. An invariant of FindScope is that e violates at least one constraint whose scope is a subset of R ∪ Y. When FindScope is called with ask_query = false, we already know whether R contains the scope of a constraint that rejects e (line 3). If ask_qery = true we ask the user whether e[R] is positive or not (line 4). If yes, we can remove all the constraints that reject e[R] from the basis, otherwise we return the empty set (line 5). We reach line 6 only in case e[R] does not violate any constraint. We know that e[R ∪ Y] violates a constraint. Hence, as Y is a singleton, the variable it contains necessarily belongs to the scope of a constraint that violates e[R ∪ Y]. The function returns Y. If none of the return conditions are satisfied, the set Y is split in two balanced parts (line 7) and we apply a technique similar to QUICKXPLAIN ( [Junker, 2004a]) to elucidate the variables of a constraint violating e[R ∪ Y] in a logarithmic number of steps (lines 8-10).

The function FindC (see Algorithm 3) takes as parameter Y, the scope on which FindScope has found that there is a constraint from the target network C T . FindC first removes from B all constraints with scope Y that are implied by C L because there is no need to learn them (line 3). The set ∆ is initialized to all candidate constraints (line 4). In line

B ← B \ {c Y | C L | = c Y }; 4 ∆ ← {c Y | (c Y ∈ B[Y]);

Complexity of QUACQ

The complexity of QUACQ, in terms of queries, is given by Theorem 2.2. Proof. The proof of the theorem 2.2 is given in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF].

Illustrative Example Table 2.1 -The example call R Y ASK return 0 ∅ X 1 ,X 2 ,X 3 ,X 4 ,X 5 × X 3 ,X 4 1 X 1 ,X 2 ,X 3 X 4 ,X 5 yes X 4 1.1 X 1 ,X 2 ,X 3 ,X 4 X 5 no ∅ 1.2 X 1 ,X 2 ,X 3 X 4 × X 4 2 X 4 X 1 ,X 2 ,X 3 yes X 3 2.1 X 4 ,X 1 ,X 2 X 3 yes X 3 2.2 X 4 ,X 3 X 1 ,X 2 no ∅
We illustrate the behavior of QUACQ on a simple example. Consider the set of variables X 1 ,...,X 5 with domains {1..5}, a language Γ = {=, =}, a basis B = {= ij , = ij | i,j ∈ 1..5,i < j}, and a target network C T = {= 15 , = 34 }. Suppose the first example generated in line 8 of QUACQ is e 1 = (1,1,1,1,1). The trace of the execution of FindScope(e 1 ,∅,X 1 ...X 5 ,false) is in Table 2.1. Each line corresponds to a call to FindScope. Queries are always on the variables in R. '×' in the column ASK means that the previous call returned ∅, so the question is skipped. The queries in lines 1 and 2.1 in the table permit FindScope to remove the constraints = 12 , = 13 , = 23 and = 14 , = 24 from B. Once the scope (X 3 ,X 4 ) is returned, FindC requires a single example to return = 34 and prune = 34 from B. Suppose the next example generated by QUACQ is e 2 = (1,2,3,4,5). FindScope will find the scope (X 1 ,X 5 ) and FindC will return = 15 in a way similar to the processing of e 1 . The constraints = 12 ,= 13 ,= 14 ,= 23 ,= 24 are removed from B by a partial positive query on X 1 ,...,X 4 and = 15 by FindC.

Constraint Acquisition with Generalization Queries Preamble

In this chapter, we introduce the concept of generalization query based on an aggregation of variables into types. We present a constraint generalization algorithm that can be plugged into any constraint acquisition system. We propose several strategies to make our approach more efficient in terms of number of queries. Finally we experimentally compare the recent QUACQ system to an extended version boosted by the use of our generalization functionality. The results show that the extended version dramatically improves the basic QUACQ.

Introduction

Constraint programming (CP) is used to model and to solve combinatorial problems in many application areas, such as resource allocation or scheduling. However, building a CP model requires some expertise in constraint programming. This prevents the use of this technology by a novice and thus this has a negative effect on the uptake of constraint technology by non-experts.

Several techniques have been proposed for assisting the user in the modeling task. In [START_REF] Freuder | Suggestion strategies for constraintbased matchmaker agents[END_REF], Freuder and Wallace proposed the match-Constraint Acquisition with Generalization Queries maker agent, an interactive process where the user is able to provide one of the constraints of her target problem each time the system proposes a wrong solution.

In [Lallouet et By contrast, in an active learner like Conacq.2, the system proposes examples to the user to classify as solutions or non solutions [START_REF] Bessiere | Querydriven constraint acquisition[END_REF]. Such questions are called membership queries [START_REF] Angluin | Queries and concept learning[END_REF]. CONACQ introduces two computational challenges. First, how does the system generate a useful query? Second, how many queries are needed for the system to converge to the target set of constraints? It has been shown that the number of membership queries required to converge to the target set of constraints can be exponentially large [Bessiere and Koriche, February, 2012].

QUACQ is a recent active learner system that is able to ask the user to classify partial queries [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. Using partial queries and given a negative example, QUACQ is able to find a constraint of the problem the user has in mind in a number of queries logarithmic in the size of the example. This key component of QUACQ allows it to always converge on the target set of constraints in a polynomial number of queries. However, even that good theoretical bound can be hard to put in practice. For instance, QUACQ requires the user to classify more than 8000 examples to get the complete Sudoku model.

In this chapter, we propose a new technique to make constraint acquisition more efficient in practice by using variable types. In real problems, variables often represent components of the problem that can be classified in various types. For instance, in a school time-tabling problem, variables can represent teachers, students, rooms, courses, or time-slots. Such types are often known by the user. To deal with types of variables, we introduce a new kind of query, namely, generalization query. We expect the user to be able to decide if a learned constraint can be generalized to other scopes of variables of the same type as those in the learned constraint. We propose an algorithm, GENACQ for generalized acquisition, that asks such generalization queries each time a new constraint is learned. We propose several strategies and heuristics to select the good candidate generalization query. We plugged our generalization functionality into the QUACQ constraint acquisition system, leading to the G-QUACQ algorithm. We experimentally evaluate the benefit of our technique on several benchmark problems. The results show that G-QUACQ dramatically improves the basic QUACQ algorithm in terms of number of queries.

The rest of this chapter is organized as follows. Section Section 3.2 describes the generalization algorithm. In Section 3.3, several strategies are presented to make our approach more efficient. Section 3.4 presents the experimental results we obtained when comparing G-QUACQ to the basic QUACQ and when comparing the different strategies in G-QUACQ. Section 3.5 concludes the chapter and gives some directions for future research.

GENACQ Algorithm

In this section we present GENACQ, a generalized acquisition algorithm, The idea behind this algorithm is, given a constraint c learned on var(c), to generalize this constraint to sequences of types s covering var(c) by asking generalization queries AskGen(s,r). A generalization query AskGen(s,r) is answered yes by the user if and only if for every sequence var of variables covered by s the relation r holds on var in the target constraint network C T .

Algorithm 4: GENACQ (c,NonTarget)

2 2 Table ← {s | var(c) ∈ s} \ {var(c)} 4 4 G ← ∅ 6 6 #NoAnswers ← 0 8 8 foreach s ∈ Table do 10 10 if ∃(s ′ ,r) ∈ NegativeQ | rel(c) ⊆ r ∧ s ′ ⊑ s then 12 12 Table ← Table \ {s} 14 14 if ∃c ′ ∈ NonTarget | rel(c ′ ) = rel(c) ∧ var(c ′ ) ∈ s then 15
G ← G ∪ {s} \ {s ′ ∈ G | s ′ ⊑ s} 25 25 Table ← Table \ {s ′ ∈ Table | s ′ ⊑ s}

Description of GENACQ

The algorithm GENACQ (see Algorithm 4) takes as input a target constraint c that has already been learned and a set NonTarget of constraints that are known not to belong to the target network. It also uses the global data structure NegativeQ, which is a set of pairs (s,r) for which we know that r does not hold on all sequences of variables covered by s. c and NonTarget can come from any constraint acquisition mechanism or as background knowledge. NegativeQ is built incrementally by each call to GENACQ. GENACQ also uses the set In line 2, GENACQ initializes the set Table to all possible sequences s of types that contain var(c). In line 3, GENACQ initializes the set G to the empty set. G will contain the output of GENACQ, that is, the set of maximal sequences from Table on which rel(c) holds. The counter #NoAnswers counts the number of consecutive times generalization queries have been classified negative by the user. It is initialized to zero (line 6). #NoAnswers is not used in the basic version of GENACQ but it will be used in the version with cutoffs. (In other words, the basic version uses cutoffNo = +∞ in line 17).

The first loop in GENACQ (line 8) eliminates from Table all sequences s for which we already know the answer to the query AskGen(s,rel(c)). In lines 10-12, GENACQ eliminates from Table all sequences s such that a relation r entailed by rel(c) is already known not to hold on a sequence s ′ covered by s (i.e., (s ′ ,r) is in NegativeQ). This is safe to remove such sequences because the absence of r on some scope in s ′ implies the absence of rel(c) on some scope in s (see Lemma 3.1). In lines 14-15, GENACQ eliminates from Table all sequences s such that we know from NonTarget that there exists a scope var in s such that (var,rel(c)) ∉ C T .

In the main loop of GENACQ (line 17), we pick a sequence s from Table at each iteration and we ask a generalization query to the user (line 21). If the user says yes, s is a sequence on which rel(c) holds. We put s in G and remove from G all sequences covered by s, so as to keep only the maximal ones (line 23). We also remove from Table all sequences s ′ covered by s (line 25) to avoid asking redundant questions later. If the user says no, we remove from Table all sequences s ′ that cover s (line 30) because we know they are no longer candidate for generalization of rel(c) and we store in NegativeQ the fact that (s,rel(c)) has been answered no. The loop finishes when Table is empty and we return G (line 16).

Completeness and Complexity

We analyze the completeness and complexity of GENACQ in terms of number of generalization queries. Lemma 3.1. If AskGen(s,r) = no then for any (s ′ ,r ′ ) such that s ⊑ s ′ and r ′ ⊆ r, we have AskGen(s ′ ,r ′ ) = no.

Proof. Assume that AskGen(s,r) = no. Hence, there exists a sequence var ∈ s such that (var,r) ∉ C T . As s ⊑ s ′ we have var ∈ s ′ and then we know that (var,r) ∉ C T . As r ′ ⊆ r, we also have (var,r ′ ) ∉ C T . As a result, AskGen(s ′ ,r ′ ) = no. Lemma 3.2. If AskGen(s,r) = yes then for any s ′ such that s ′ ⊑ s, we have AskGen(s ′ ,r) = yes.

Proof. Assume that AskGen(s,r) = yes. As s ′ ⊑ s, for all var ∈ s ′ we have var ∈ s and then we know that (var,r) ∈ C T . As a result, AskGen(s ′ ,r) = yes. Proposition 3.1 (Completeness). When called with constraint c as input, the algorithm GENACQ returns all maximal sequences of types covering var(c) on which the relation rel(c) holds.

Proof. All sequences covering var(c) are put in

Illustrative Example

Let us take the Zebra problem to illustrate our generalization approach. The Lewis Carroll's Zebra problem has a single solution. The target network is formulated using 25 variables, partitioned in 5 types of 5 variables each. The types are thus color, nationality, drink, cigaret, pet, and the trivial type X of all variables. There is a clique of = constraints on all pairs of variables of the same non trivial type and 14 additional constraints given in the description of the problem.

Figure 3.1 shows the variables of the Zebra problem and their types. In this example, the constraint x 2 = x 5 has been learned between the two color variables x 2 and x 5 . This constraint is given as input of the GENACQ algorithm. GENACQ computes the Table of all sequences of types covering the scope (x 2 ,x 5 ). Table = {(x 2 ,color), (x 2 ,X),(color,x 5 ),(color,color),(color,X),(X,x 5 ),(X,color), (X,X)}. Suppose we pick s = (X,x 5 ) at line 19 of GENACQ. According to the user's answer (no in this case), the Table is reduced to Table = {(x 2 ,color),(x 2 ,X),(color,x 5 ),(color,color), (color,X)}. As next iteration, let us pick s = (color,color). The user will answer yes because there is indeed a clique of = on the color variables. Hence, (color,color) is added to G and the Table is reduced to Table = {(x 2 ,X),(color,X)}. If we pick (x 2 ,X), the user answers no and we reduce the Table to the empty set and return G = {(color,color)}, which means that the constraint x 2 = x 5 can be generalized to all pairs of variables in the sequence (color,color), that is, (x i = x j ) ∈ C T for all (x i ,x j ) ∈ (color,color).

Using Generalization in QUACQ

GENACQ is a generic technique that can be plugged into any constraint acquisition system. In this section we present G-QUACQ, a constraint acquisition algorithm obtained by plugging GENACQ into QUACQ, the constraint acquisition system presented in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF],

G-QUACQ is presented in Algorithm 5. We do not give the code of functions FindScope and FindC as we use them exactly as they appear in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. But let us say a few words on how they work. Given sets of variables S 1 and S 2 , FindScope(e,S 1 ,S 2 ,false) returns the subset of S 2 that, together with S 1 forms the scope of a constraint in the basis of possible constraints B that rejects e. Inspired from a technique used in QUICKXPLAIN [Junker, 2004b], FindScope requires a number of queries logarithmic in |S 2 | and linear in the size of the final scope returned. The function FindC takes as parameter the negative example e and the scope returned by FindScope. It returns a constraint from C T with the given scope that rejects e. For any assignment e, κ B (e) denotes the set of all constraints in B rejecting e.

G-QUACQ has a structure very similar to QUACQ. It initializes the set NonTarget and the network C L it will learn to the empty set (line 2). If C L is unsatisfiable (line 6), the space of possible networks collapses because there does not exist any subset of the given basis B that is able to correctly classify the examples already asked of the user. In line 8, QUACQ computes a complete assignment e satisfying C L but Algorithm 5: G-QUACQ =QUACQ +GENACQ . If the answer is yes, we can remove from B the set κ B (e) of all constraints in B that reject e (line 14) and we add all these ruled out constraints to the set NonTarget to be used in GENACQ (line 16). If the answer is no, we are sure that e violates at least one constraint of the target network C T . We then call the function FindScope to discover the scope of one of these violated constraints. FindC will select which one with the given scope is violated by e (line 20). If no constraint is returned (line 22), this is again a condition for collapsing as we could not find in B a constraint rejecting one of the negative examples. Otherwise, we know that the constraint c returned by FindC belongs to the target network C T . This is here that the algorithm differs from QUACQ as we call GENACQ to find all the maximal sequences of types covering var(c) on which rel(c) holds. They are returned in G (line 26). Then, for every sequence of variables var belonging to one of by these sequences in G, we add the constraint (var,rel(c)) to the learned network C L (line 28).

Strategies

GENACQ learns the maximal sequences of types on which a constraint can be generalized. The order in which sequences are picked from Table in line 19 of Algorithm 4 is not specified by the algorithm. As shown on the following example, different orderings can lead more or less quickly to the good (maximal) sequences Constraint Acquisition with Generalization Queries on which a relation r holds. Let us come back to our example on the Zebra problem (Section 3.2.3). In the way we developped the example, we needed only 3 generalization queries to empty the set Table and converge on the maximal sequence (color,color) on which = holds:

1. AskGen((X,x 5 ), =) = no 2. AskGen((color,color), =) = yes 3. AskGen((x 2 ,X), =) = no Using another ordering, GENACQ needs 8 generalization queries:

1. AskGen((X,X), =) = no 2. AskGen((X,color), =) = no 3. AskGen((color,X), =) = no 4. AskGen((X,x 5 ), =) = no 5. AskGen((x 2 ,X), =) = no 6. AskGen((x 2 ,color), =) = yes 7. AskGen((color,x 5 ), =) = yes 8. AskGen((color,color), =) = yes If we want to reduce the number of generalization queries, we may wonder which strategy to use. In this section we propose two techniques. The first idea is to pick sequences in the set Table following an order given by a heuristic that will try to minimize the number of queries. The second idea is to put a cutoff on the number consecutive negative queries we accept to face, leading to a non complete generalization startegy: the output of GENACQ will no longer be guaranteed to be the maximal sequences.

Query Selection Heuristics

We propose some query selection heuristics to decide which sequence to pick next from Table . We first propose optimistic heuristics, which try to take the best from positive answers:

-max_CST: This heuristic selects a sequence s maximizing the number of possible constraints (var,r) in the basis such that var is in s and r is the relation we try to generalize. The intuition is that if the user answers yes, the generalization will be maximal in terms of number of constraints.

-max_VAR: This heuristic selects a sequence s involving a maximum number of variables, that is, maximizing | T ∈s T |. The intuition is that if the user answers yes, the generalization will involve many variables.

Dually, we propose pessimistic heuristics, which try to take the best from negative answers:

-min_CST: This heuristic selects a sequence s minimizing the number of possible constraints (var,r) in the basis such that var is in s and r is the relation we try to generalize. The intuition is to maximize the chances to receive a yes answer. If, despite this, the user answers no, a great number of sequences are removed from Table (see Lemma 3.1).

-min_VAR: This heuristic selects a sequence s involving a minimum number of variables, that is, minimizing | T ∈s T |. The intuition is to maximize the chances of a yes answer while focusing on smaller sets of variables than min_CST. Again, a no answer leads to a great number of sequences removed from Table.

As a baseline for comparison, we define a random selector.

random: It picks randomly a sequence s in Table.

Using Cutoffs

The idea here is to exit GENACQ before having proved the maximality of the sequences returned. We put a threshold cutoffNo on the number of consecutive negative answers to avoid using queries to check unpromising sequences. The hope is that GENACQ will return near-maximal sequences of types despite not proving maximality. This cutoff strategy is implemented by setting the variable cutoffNo to a predefined value. In lines 27 and 34 of GENACQ, a counter of consecutive negative answers is respectively reset and incremented depending on the answer from the user. In line 17, that counter is compared to cutoffNo to decide to exit or not.

Experimentations

We made some experiments to evaluate the impact of using our generalization functionality GENACQ in the QUACQ constraint acquisition system. We implemented GENACQ and plugged it in QUACQ, leading to the G-QUACQ version. We first present the benchmark problems we used for our experiments. Then, we report the results of several experiments. The first one compares the performance of G-QUACQ to the basic QUACQ. The second reports experiments evaluating the different strategies we proposed (query selection heuristics and cutoffs) on G-QUACQ. The third evaluates the performance of our generalization approach when our knowledge of the types of variables is incomplete.

Benchmark Problems

Zebra problem. As introduced in section 3.2.3, the Lewis Carroll's Zebra problem is formulated using 5 types of 5 variables each, with 5 cliques of = constraints and 14 additional constraints given in the description of the problem. We fed QUACQ and G-QUACQ with a basis B of 4450 unary and binary constraints taken from a language with 24 basic arithmetic and distance constraints. Sudoku. The Sudoku model is expressed using 81 variables with domains of size 9, and 810 = binary constraints on rows, columns and squares. In this problem, the types are the 9 rows, 9 columns and 9 squares, of 9 variables each. We fed QUACQ and G-QUACQ with a basis B of 6480 binary constraints from the language Γ = {=, =}. Latin Square. The Latin square problem consists of an n × n table in which each element occurs once in every row and column. For this problem, we use 25 variables with domains of size 5 and 100 binary = constraints on rows and columns. Rows and columns are the types of variables (10 types). We fed QUACQ and G-QUACQ with a basis of constraints based on the language Γ = {=, =}. Radio Link Frequency Assignment Problem. The RLFAP problem is to provide communication channels from limited spectral resources [START_REF] Cabon | Warners. Radio link frequency assignment[END_REF]]. Here we build a simplified version of RLFAP that consists in distributing all the frequencies available on the base stations of the network. The constraint model has 25 variables with domains of size 25 and 125 binary constraints. We have five stations of five terminals (transmitters/receivers), which form five types. We fed QUACQ and G-QUACQ with a basis of 1800 binary constraints taken from a language of 6 arithmetic and distance constraints Purdey. Like Zebra, this problem has a single solution. Four families have stopped by Purdey's general store, each to buy a different item and paying differently. Under a set of additional constraints given in the description, the problem is how can we match family with the item they bought and how they paid for it. The target network of Purdey has 12 variables with domains of size 4 and 30 binary constraints. Here we have three types of variables, which are family, bought and paid, each of them contains four variables.

Results

For all our experiments we report, the total number #Ask of standard queries asked by the basic QUACQ, the total number #AskGen of generalization queries, and the numbers #no and #yes of negative and positive generalization queries, respectively, where #AskGen = #no+#yes. The time overhead of using G-QUACQ rather than QUACQ is not reported. Computing a generalization query takes a few milliseconds.

Our first experiment compares QUACQ and G-QUACQ in its baseline version, G-QUACQ +rand, on our benchmark problems. Table 3.1 reports the results. We observe that the number of queries asked by G-QUACQ is dramatically reduced compared to QUACQ. This is especially true on problems with many types involving many variables, such as Sudoku or Latin square. G-QUACQ acquires the Sudoku with 260 standard queries plus 166 generalization queries, when QUACQ acquires it in 8645 standard queries.

Let us now focus on the behavior of our different heuristics in G-QUACQ. Table 3.2(top) reports the results obtained with G-QUACQ using min_VAR, min_CST, max_VAR, and max_CST to acquire the Sudoku model. (Other problems showed similar trends.) The results clearly show that max_VAR, and max_CST are very bad heuristics. They are worse than the baseline random. On the contrary, min_VAR and min_CST significantly outperform random. They respectively require 90 and 132 generalization queries instead of 166 for random. Notice that they all ask the same number of standard queries (260) as they all find the same maximal sets of sequences for each learned constraint. At the bottom of Table 3.2 we compare the behavior of our two best heuristics (min_VAR and min_CST) when combined with the cutoff strategy. We tried all values of the cutoff from 1 to 3. A first observation is that min_VAR remains the best whatever the value of the cutoff is. Interestingly, even with a cutoff equal to 1, min_VAR requires the same number of standard queries as the versions of G-QUACQ without cutoff. This means that using min_VAR as selection heuristic in Table, G-QUACQ is able to return the maximal sequences despite being stopped after the first negative generalization answer. We also observe that the number of generalization queries with min_VAR decreases when the cutoff becomes smaller (from 90 to 39 when the cutoff goes from +∞ to 1). By looking at the last two columns we see that this is the number #no of negative answers which decreases. The good performance of min_VAR + cutoff=1 can thus be explained by the fact that min_VAR selects first queries that cover a minimum number of variables, which increases the chances to have a yes answer. Finally, we observe that the heuristic min_CST does not have the same nice characteristics as min_VAR. The smaller the cutoff, the more standard queries are needed, not compensating for the saving in number of generalization queries (from 260 to 837 standard queries for min_CST when the cutoff goes from +∞ to 1). This means that with min_CST, when the cutoff becomes too small, GENACQ does not return the maximal sequences of types where the learned constraint holds. In Table 3.3, we report the performance of G-QUACQ with random, min_VAR and min_VAR +cutoff=1 on all the other problems. We see that min_VAR +cutoff=1 significantly improve the performance of G-QUACQ on all problems. As in the case of Sudoku, we observe that min_VAR +cutoff=1 does not lead to an increase in the number of standard queries. This means that on all these problems min_VAR +cutoff=1 always returns the maximal sequences while asking less generalization queries with negative answers.

From these experiments we see that G-QUACQ with min_VAR +cutoff=1 leads to tremendous savings in number of queries compared to QUACQ: 257+23 instead of 638 on Zebra, 260+39 instead of 8645 on Sudoku, 117+20 instead of 1129 on Latin square, 151+22 instead of 1653 on RLFAP, 82+12 instead of 173 on Purdey.

In our last experiment, we show the effect on the performance of G-QUACQ of a lack of knowledge on some variable types. We took again our 5 benchmark problems in which we have varied the amount of types known by the algorithm. This simulates a situation where the user does not know that some variables are from the same type. For instance, in Sudoku, the user could not have noticed that variables are arranged in columns. Figure 3.2 shows the number of standard queries and generalization queries asked by G-QUACQ with min_VAR +cutoff=1 to learn the RLFAP model when fed with an increasingly more accurate knowledge of types. We observe that as soon as a small percentage of types is known (20%), G-QUACQ reduces drastically its number of queries. Table 3.4 gives the same information for all other problems. Constraint Acquisition with Generalization Queries

Conclusion

We have proposed a new technique to make constraint acquisition more efficient by using information on the types of components the variables in the problem represent. We have introduced generalization queries, a new kind of query asked to the user to generalize a constraint to other scopes of variables of the same type where this constraint possibly applies. Our new technique, GENACQ, can be called to generalize each new constraint that is learned by any constraint acquisition system. We have proposed several heuristics and strategies to select the good candidate generalization query. We have plugged GENACQ into the QUACQ constraint acquisition system, leading to the G-QUACQ algorithm. We have experimentally evaluated the benefit of our approach on several benchmark problems, with and without complete knowledge on the types of variables. The results show that G-QUACQ dramatically improves the basic QUACQ algorithm in terms of number of queries.

The drawback of generalization queries is that they require types of variables of the learned constraint to be generated. To overcome this weakness, and in order to make the build of such queries totally independent of the user, we propose in the next chapter to learn types of variables during the constraint acquisition process, and then to use the learned types to generate generalization queries.

CHAPTER

Detecting Types of Variables for Constraint Generalization Preamble

In this chapter, we propose a new algorithm that 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. Our approach gives good results although no knowledge on the types is provided.

Introduction

Constraint programming (CP) is a paradigm that allows effective solving of combinatorial problems in many areas, such as planning and scheduling. However, modeling a combinatorial problem using constraints requires significant expertise in CP [START_REF] Freuder | Modeling: The final frontier[END_REF].

To alleviate this issue, several constraint acquisition systems have been introduced [START_REF] Bessiere | A satbased version space algorithm for acquiring constraint satisfaction problems[END_REF][START_REF] Bessiere | Querydriven constraint acquisition[END_REF][START_REF] Beldiceanu | A model seeker: Extracting global constraint models from positive examples[END_REF][START_REF] Lallouet | On learning constraint problems[END_REF]Bessiere et al., 2014b;[START_REF] Shchekotykhin | Argumentation based constraint acquisition[END_REF][START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. Most of these systems interact with the user by asking her to classify simple examples. The drawback is that when the problem has a lot of constraints, the user may have to classify a large number of such questions to learn them all.

To make constraint acquisition systems more efficient in practice, an opportunistic kind of query that uses the structure of the problem has been introduced in [Bessiere et al., 2014a] with the GENACQ algorithm. This kind of query, named "generalization query", is 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. By using such queries over existing constraint acquisition systems, the number of queries needed to converge on the target constraint network can be significantly reduced.

Nevertheless, 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. In this chapter, we propose to learn the potential types during the constraints acquisition process. The idea is to analyze the structure of the partial constraint network learned so far in order to detect potential types and to build generalization queries.

Indeed, when one looks more closely at the constraint network of a given problem, the variables of the same type are often tightly connected with similar constraints whereas the variables of different types are connected in a weaker way. To illustrate this point, let us consider the well known Lewis Carroll's Zebra problem. The constraint network of this problem is usually formulated using 25 variables, partitioned into 5 types of 5 variables each. The types are color, nationality, drink, cigaret and pet. There is a clique of = constraints on all pairs of variables of the same type and 14 additional constraints, among which 3 are unary, given in the description of the problem. Figure 4.1 shows the constraint network of the Zebra problem. In this example, it is clear that types have dense internal links but there are only a lower density of external links between different types.

The idea of detecting tightly connected sub-graphs arose in the study of networks such as social networks [START_REF] Wasserman | Social network analysis: Methods and applications[END_REF]] and biochemical networks [START_REF] Ito | A comprehensive two-hybrid analysis to explore the yeast protein interactome[END_REF]]. An important characteristic that commonly occurs in such networks is community structure. Informally, 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.

Given the similarity between the structure of a type and that of a community, we propose in this chapter to detect potential types by finding communities in the constraint network during the constraint acquisition process. Several methods for community finding have been proposed in the literature. We have considered three different techniques in this chapter. The first one is based on the concept of modularity [Newman and [START_REF] Mark | Hybrid algorithms for the constraint satisfaction problem[END_REF]] which provides information on the strength of division of a network into communities. Networks with high modularity have dense connections between the nodes within communities but sparse connections between nodes in different communities. The second technique exploits the notion of edge betweenness [START_REF] Girvan | Community structure in social and biological networks[END_REF], which is a measure that assigns a score to each edge. The edges that lie "between" many pairs of nodes have high scores which enables their easier identification. Removing these edges will leave behind just the communities themselves. The third technique is more straightforward. It is based on the assumption that the variables of the same type will tend to form quasi-cliques during the constraint acquisition process. That is, this technique finds sub-graphs with an edge density exceeding a threshold parameter.

In this chapter we propose an algorithm, named MINE&ASK, that makes use of the extracted potential types to ask the user to classify generalization queries. We plugged MINE&ASK into the QUACQ constraint acquisition system, to obtain the boosted version M-QUACQ algorithm. We experimentally evaluate the benefit of our technique on several benchmark problems. The results show that M-QUACQ improves the basic QUACQ algorithm in terms of number of queries although no knowledge on the types is provided.

The outline of this chapter is as follows. The algorithm MINE&ASK is presented in Section 4.2. We illustrate the idea behind our approach with an example in section 4.3. Section 4.4 gives more details on the techniques used to extract potential types. The experimental results we obtained when comparing MINE&ASK with the different techniques to the basic QUACQ are given in section 4.5. Section 4.6 concludes the chapter.

MINE&ASK Algorithm

In this section we present the MINE&ASK algorithm. The idea behind this algorithm is to mine the partial graph of the current constraint network in order to get potential types and then ask the user to classify generalization queries.

Description of MINE&ASK Algorithm 6: MINE&ASK

Input: C: a set of constraints, r: a relation, mine ∈ {modularity,betweenness,γ-clique}: a mine strategy, GQ max : the maximum number of generalization queries Output: L: a set of learned constraints The algorithm MINE&ASK takes as argument the set of constraints C learned so far, a relation r, the operator mine that corresponds to the strategy used for extracting potential types and the maximum number of generalization queries GQ max that we are allowed to ask. The algorithm uses a global data structure NegativeQ, which is a set of pairs (Y,r) for which we know that r does not hold. MINE&ASK also uses the local data structure Table which contains all potential types that are candidates for generalization.

1 L ← ∅; #GQ ← 0 2 X ′ ← var(c) s.t. c ∈ C ∧ rel(c) = r 3 G C ← G(X ′ ,E), E = {{x,y} | x,y ∈ var(c) ∧ x = y ∧ c ∈ C ∧ rel(c) = r} 4 Table ← {Y | Y ∈ component(G C ) ∧ ¬isClique(G C (Y))} 5 while Table = ∅ ∧ #GQ ≤ GQ max do 6 pick Y in Table 7 generalized ← false 8 if ( ∃(Y ′ ,r ′ ) ∈ NegativeQ | Y ′ ⊆ Y ∧ r ⊆ r ′ ) ∧ ( ∃var ∈ Y |r| | (var,
MINE&ASK starts by initializing L to the empty set and the number of generalization queries #GQ to zero (line 1). The set L will contain the output of MINE&ASK, that is all learned constraints. In line 3, we build the constraint graph G(X ′ ,E), noted G C and restricted to the relation r. This step is important because it helps to 4.2 MINE&ASK Algorithm 49 reveal the structure of the network. To illustrate what this means, let us consider the example given in Figure 4.2(a). This problem consists of 12 variables and 66 binary constraints which means that the constraint network of this problem is a complete graph (i.e. clique). Two relations are used in the constraints namely = and ≥. Although the constraint network is a clique, no learned constraint can be generalized to the other scopes in this clique as the links connecting the variables of the clique come from different relations. On the contrary, as shown in Figure 4.2(b), when we focus on the only = relation, useful types can be easily detected. all connected components of G whilst excluding the already formed cliques (line 4). At each iteration, MINE&ASK picks a potential type Y from this table (line 6) and asks a generalization query on (Y,r) (line 9) if the answer cannot be deduced. That is, the answer to an AskGen(Y,r) is negative if the user already classifies as negative a query on a sub-type of Y (line 8). A negative answer can also be deduced in the case of the unsatisfiability of the resulting network where in such case the answer cannot be positive (line 9). Such satisfiability tests allow us to avoid asking unnecessary queries. For instance, trying to generalize a noncommutative relation to a clique, or asking if a clique of difference applies on a set of 4 variables with the same domain of size 3. Now, if the answer of the user to AskGen(Y,r) is yes, this means that r holds on the type Y. Thus, we add all inferred constraints on Y to the set L (line 10). In the case of a negative answer, we add (Y,r) to NegativeQ with intent to avoid asking redundant queries afterwards. When no generalization happened on (Y,r) (line 15), this means that Y is not a type on which r can be generalized. Here, we call the operator mine to extract potential types from the subgraph G(Y). The resulting potential types are added to Table to be taken into account later. The main loop (line Detecting Types of Variables for Constraint Generalization 5) terminates when all potential types in Table are processed, or when the number of generalization queries exceeds a given threshold GQ max .

M-QUACQ Algorithm

MINE&ASK is a generic technique that can be plugged into any constraint acquisition system. In this section we present M-QUACQ (Algorithm 7) where we plugged MINE&ASK into the QUACQ system [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF].

M-QUACQ initializes the constraint network C L to the empty set (line 1). When C L is unsatisfiable (line 3), the space of possible networks collapses because there does not exist any subset of the given basis B that is able to correctly classify the examples already asked to the user. In line 4, M-QUACQ computes a complete assignment e satisfying C L and violating at least one constraint from B. If such an example does not exist (line 5), then all constraints in B are implied by C L , and the algorithm has converged. Otherwise, we propose the example e to the user, who will answer by yes or no (line 6). If the answer is yes, we can remove from B the set κ B (e) of all constraints in B that reject e (line 7). If the answer is no, we are sure that e violates at least one constraint of the target network C T . We then call the function FindScope to discover the scope of one of these violated constraints. Here, FindScope acts in a dichotomous manner and asks a number of queries logarithmic in the size of the example. Afterwards, FindC will select which constraint with the given scope is violated by e (line 9). If no constraint is returned (line 10), this is a condition for collapsing as we could not find in B a constraint rejecting one of the negative examples. Otherwise, we know that the constraint c returned by FindC belongs to the target network C T , then we add it to the learned network C L (line 12). Note that FindScope and FindC functions are used exactly as they appear in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. Afterwards, we call MINE&ASK to mine the learned constraint network C L in order to extract potential types and to ask generalization queries. M-QUACQ updates C L by adding all learned constraints (line 13).

An Illustrative Example

In this section we illustrate on an example the idea of extracting potential types during the constraint acquisition process. Let us consider the example given in Figure 4.3. The part (a) of Figure 4.3 shows the constraint network of the problem that the user has in mind. This problem consists in 15 variables and 39 binary constraints. Two relations are used, noted r 1 and r 2 in Figure 4.3. The part (b) of Figure 4.3 shows the constraint network learned, at a given point, using QUACQ system. Suppose that the last constraint learned using QUACQ was ((x 1 ,x 2 ),r 1 ). Now, we want to extract potential types on which the relation r 1 can be generalized. To this end, MINE&ASK restricts the constraint network to the constraints that use r 1 (part (c) in Figure 4.3). Suppose now that MINE&ASK algorithm finds three potential types T 1 = {x 1 ,...x 5 }, T 2 = {x 6 ,...

C L ← C L ∪ {c}; 13 C L ← C L ∪ MINE&ASK(C L ,mine,rel(c),GQ max ); 14 return C L ;
classified as negative whereas the ones on T 1 and T 2 will be classified as positive. Nine constraints will be, in one shot, added to the current constraint network (see part (d) of Figure 4.3).

Extraction of Potential Types

MINE&ASK extracts variable types by finding communities in the current graph of learned constraints. The way in which the operator mine finds communities at line 15 of Algorithm 6 is described in this section.

Optimizing Modularity

One of the most effective approaches for detecting communities in networks is based on the optimization of the measure known as modularity [Newman and [START_REF] Mark | Hybrid algorithms for the constraint satisfaction problem[END_REF]]. Given a partition of vertices of a network into disjoint communities, modularity reflects the concentration of edges within communities compared with random distribution of links between all nodes regardless of communities.

More formally, let G = (X,E) be a graph, with X = {x 1 ,...,x n } the set of vertices and let A be the adjacency matrix of G. That is, A ij = 1 if there exists an edge between vertices x i and x j and A ij = 0 otherwise. Suppose the vertices are divided into communities such that vertex x i belongs to community c(x i ) and let deg(x i ) denotes the degree of x i . Then the modularity Q is given by the following formula: Detecting Types of Variables for Constraint Generalization

Q = i,j [ A ij 2m - deg(x i )×deg(x j ) 4m 2 ]δ(c(x i ),c(x j ))
where m is the total number of edges in the network, and δ(c(x i ),c(x j )) = 1 if x i and x j belong to the same community (i.e., c(x i ) = c(x j )) and 0 otherwise. High values of the modularity correspond to good partitions of a network into communities [Newman and [START_REF] Mark | Hybrid algorithms for the constraint satisfaction problem[END_REF]. Hence one should be able to find such good partitions by searching through the possible candidates for ones with high modularity. Unfortunately, finding the global maximum modularity over all possible divisions is NP-hard, but reasonably good solutions can be found with approximate optimization techniques. In this chapter, we have used the algorithm introduced in [START_REF] Aaron | Finding community structure in very large networks[END_REF] and implemented in the igraph software package [START_REF] Csardi | The igraph software package for complex network research[END_REF]. This algorithm uses a greedy optimization where, starting with a partition where each vertex is the unique member of a community, it repeatedly joins together the two communities whose fusion produces the largest increase in Q.

Edge Betweenness Centrality

Recently, the concept of edge betweenness was introduced [START_REF] Girvan | Community structure in social and biological networks[END_REF] as a measure that provides information on edges centrality in networks. This measure can be implemented in several ways but the most common way is the one based on shortest paths. Formally speaking, let x i and x j be two nodes in the network. Let σ ij denotes the number of shortest paths between nodes x i and x j and σ ij (e) denotes the number of shortest paths between x i and x j which go through the edge e. The Betweenness centrality of e, denoted by B(e), is defined as follows:

B(e) = ij σ ij (e) σ ij
If two communities are joined by only a few inter-community edges, then all paths through the network from vertices of one community to vertices of the other must pass through one of those few edges. Thus, the edge betweenness scores for inter-community edges are expected to be larger than the ones for intra-community edges. The betweeness based algorithm to find community structure is used as it appears in [START_REF] Girvan | Community structure in social and biological networks[END_REF]. The idea behind this algorithm is to iteratively calculate the betweenness score for each edge and to remove the one with the highest score. That is, removing edges with high betweenness scores allows us to isolate the communities. This algorithm is also available in the igraph software package [START_REF] Csardi | The igraph software package for complex network research[END_REF]].

Quasi-cliques Detection

Mining the constraint network for dense subgraphs may be a possible way for discovering communities. Cliques are the densest form of subgraphs. A graph is a clique if there is an edge between every pair of the vertices. This requirement is not desirable in our case because the idea is to anticipate the formation of complete cliques in order to be able to infer some constraints. Therefore, instead of mining cliques, our goal is to extract γcliques (i.e. quasi-cliques), which are sub-graphs with an edge density exceeding a given threshold parameter γ ∈ [0,1]. , with q = |K|. Algorithm 8: FindQCliques (G,A,B,K,γ)

1 if A = ∅ then 2 report K as a quasi-clique; 3 while A = ∅ do 4 choose x ∈ A; 5 K ′ ← K ∪ {x}; 6 A ′ ← {y | y ∈ X \ K ′ ∧ K ′ ∪ {y} is a γ -clique}; 7 A ′ ← A ′ \ A ′ ∩ B; 8 FindQCliques(G,A ′ ,B,K ′ ,γ) ; 9 A ← A \ {x}; 10 B ← B ∪ {x};
We propose an incomplete recursive algorithm (Algorithm 8) for finding γ-cliques in an undirected graph G. This algorithm is an adaptation of the basic form of the well-known Bron-Kerbosch's algorithm [START_REF] Bron | Finding all cliques of an undirected graph (algorithm 457)[END_REF]] for finding maximal cliques in a graph. Algorithm 8 is based on the recursive function FindQCliques that takes as arguments an undirected graph G, a set A of candidates, a set B of vertices to exclude from consideration to avoid generating the same quasi-clique several times, the quasi-clique K being constructed and a parameter γ ∈]0, 1[ which specifies the minimum edge density of quasi-cliques. The recursion is initiated by setting B and K to be the empty set and A to be the vertex set of the graph. Each time a new element is added to the current quasi-clique (line 5 ), we calculate a new set A ′ of candidates. A vertex y is an element of A ′ if and only if when it is added to the current quasi-clique we obtain a new quasi-clique (line 6). This condition is not a necessary condition to lead to a new quasi-clique. Consequently, Algorithm 8 is incomplete. When the candidate set becomes empty (line 1), a new quasi-clique is reported and a backtrack to the last choice is performed. Then, the last choice is added to the set B to exclude it from consideration in future quasi-cliques.

Experimentations

We performed some experiments to evaluate the impact of using MINE&ASK in constraint acquisition. We implemented MINE&ASK and plugged it in QUACQ system, leading to the M-QUACQ version. We first present the benchmark problems we used for our experiments. Then, we report the results of acquiring these problems with the basic version of QUACQ [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF], our version M-QUACQ and G-QUACQ version. The G-QUACQ version includes the generalization process with GENACQ algorithm and the user provides all variable types [Bessiere et al., 2014a]. The experiments evaluate also the different ways in which our approach extracts potential types, namely the modularity, the betweenness and the γ-clique. Our tests were conducted on an Intel Core i5-3320M CPU @ 2.60GHz × 4 with 4 Gb of RAM.

Benchmark Problems

Zebra problem. The Lewis Carroll Zebra problem is formulated using 5 types of 5 variables each, with 5 cliques of = constraints and 14 additional constraints given in the description of the problem. We fed QUACQ, G-QUACQ and M-QUACQ with a basis B of 4450 unary and binary constraints taken from a language with 24 basic arithmetic and distance constraints. Latin Square. The Latin square problem consists of an n × n table in which each element occurs once in every row and column. For this problem, we use 36 variables with domains of size 6 and 180 binary = constraints on rows and columns. Rows and columns are the types of variables (10 types). We fed QUACQ, G-QUACQ and M-QUACQ with a basis B of 1260 constraints based on the language Γ = {=, =}. Purdey. Like Zebra, this problem has a single solution. Four families have stopped by Purdey's general store, each to buy a different item and paying differently. Under a set of additional constraints given in the description, the problem is how can we match family with the item they bought and how they paid for it. The target network of Purdey has 12 variables with domains of size 4 and 30 binary constraints. Here we have three types of variables, which are family, bought and paid, each of them contains four variables. We fed QUACQ, G-QUACQ and M-QUACQ with a basis B of 396 constraints based on the language Γ = {=, =}. PlaceNumPuzzle. The PlaceNumPuzzle problem is to place numbers 1 through N on nodes of a given graph such that each number appears exactly once and no connected nodes have consecutive numbers. For this problem, we use 25 variables with domains of size 25 and 64 binary constraints. The problem has three types which are the cliques of the graph. We fed QUACQ, G-QUACQ and M-QUACQ with a basis B of 1260 binary constraints taken from a language of 4 arithmetic and distance constraints. Murder. Someone was murdered last night, and you are summoned to investigate the murder. The objects found on the spot that do not belong to the victim include: a pistol, an umbrella, a cigarette, a diary, and a threatening letter. There are also witnesses who testify that someone had argued with the victim, someone left the house, someone rang the victim, and some walked past the house several times about the time the murder occurred. The suspects are: Miss Linda Ablaze, Mr. Tom Burner, Ms. Lana Curious, Mrs. Suzie Dulles, and Mr. Jack Evilson. Each suspect has a different motive for the murder, including: being harassed, abandoned, sacked, promotion and hate. Other clues are given below. Under a set of additional clues given in the description, the problem is who was the Murderer? And what was the motive, the evidence-object, and the activity associated with each suspect.

Detecting Types of Variables for Constraint Generalization

The target network of Murder has 20 variables with domains of size 5 and 53 binary constraints. Here we have four types of variables, which are suspect, motive, object, and activity, each of them contains five variables. We fed QUACQ, G-QUACQ and M-QUACQ with a basis B of 380 constraints based on the language Γ = {=, =}. Sudoku. The Sudoku model is expressed using 81 variables with domains of size 9, and 810 = binary constraints on rows, columns and squares. In this problem, the types are the 9 rows, 9 columns and 9 squares, of 9 variables each. We fed QUACQ, G-QUACQ and M-QUACQ with a basis B of 6480 binary constraints from the language Γ = {=, =}.

Results

For all our experiments we report, the total number #Ask of standard queries asked by the basic QUACQ, the total number #AskGen of generalization queries, and the numbers #no and #yes of negative and positive generalization queries, where #AskGen = #no + #yes. The time overhead of using M-QUACQ rather than QUACQ is not reported since computing a generalization query takes a few milliseconds.

First of all, it should be noted that the parameter γ specifying the minimum edge density of quasi-cliques may have an influence on the performance of M-QUACQ. Indeed, the lower γ, the greater the number of extracted quasi-cliques. This means that the probability that extracted types do not correspond to real types increases when γ is small and therefore, the number of negative answers to generalization queries may become important. This phenomenon can be more or less controlled by adjusting the value of γ. That being said, the value of γ was fixed to 0.8 after a few preliminary tests. Now, with the results reported in table 4.1, we aim at comparing the performance of the basic QUACQ, G-QUACQ where the types are provided by the user and the three versions of M-QUACQ where types are learned during the acquisition process.

Not surprisingly, we notice that M-QUACQ is always better than QUACQ but still less efficient than G-QUACQ. Furthermore, the number of queries (#Ask + #AskGen) that were asked using M-QUACQ is often closer to the number of queries asked using G-QUACQ. For instance, to learn the PlaceNumPuzzle QUACQ needs 3746 queries. Providing the types to G-QUACQ reduced the number of queries to 390. Now, using our approach, M-QUACQ needed only 662 queries although no knowledge on types was provided.

In addition, Table 4.1 reports the performance of the three versions of M-QUACQ. What is noticeable about the three different ways for extracting potential types is that modularity clearly outperforms the two other techniques and improves significantly the performance of M-QUACQ on all considered problems. Indeed, the combination of M-QUACQ with modularity leads to tremendous savings in the number of queries compared to QUACQ: 627+35 (-82%) instead of 3746 on PlaceNumPuzzle, 272+12 (-41%) instead of 483 on Murder, 410+14 (-39%) instead of 694 on Zebra, 140+8 (-28%) instead of 205 on Purdey, 7963+57 (-28%) instead of 9593 on Sudoku. We also notice that the betweenness outperforms the γ-clique on all problems except for the Latin Square. This can be explained by the fact that the types overlap (rows and columns) in Latin Square and that γ-clique is likely more able to detect overlapping types than betweenness.

In conclusion we can say that when modularity is used to extract the types, the algorithm M-QUACQ performs very well and is very close to G-QUACQ although no knowledge on types is provided. Furthermore, since modularity was introduced to find communities in very large networks, we think that the performance of M-QUACQ with modularity can be more significant when the size of the problem increases. For instance, Figure 4.4 shows the gain of M-QUACQ with modularity compared to QUACQ on the Latin Square when fed with an increasing number of variables. It is clear in this figure that the gain significantly increases with the size of the problem.

Conclusion

We have proposed MINE&ASK, a generalization based algorithm that is able to mine partial graphs of constraint networks and to generalize, on potential types, constraints learned by any constraint acquisition system. MINE&ASK acts when no knowledge is provided on the variable types. We have detailed and tested three tech- niques to extract potential types, namely the modularity, the betweenness and the γ-clique techniques. We have plugged our MINE&ASK into the QUACQ constraint acquisition system, leading to the M-QUACQ algorithm. We have experimentally evaluated the benefit of our approach on several benchmark problems. The results show that M-QUACQ significantly improves the basic QUACQ algorithm and they are quite close to the results when variable types are provided.

The advantage of such an approach is that, despite we lose in performance, there is no need for the user to provide the types. Nevertheless, generalization queries do not work for all problems. They work only for high structured problems that their variables can be grouped into types. In the following chapter, we introduce a generic kind of query based on the link prediction on dynamic graphs. The advantage of such queries is that they work for a wide range of problems, and they do not need any background knowledge from the user.

CHAPTER

Constraint Acquisition with Recommendation Queries Preamble

In this chapter, we propose PREDICT&ASK, an algorithm based on the prediction of missing constraints in the partial network learned so far. Such missing constraints are directly asked to the user through recommendation queries, a new, more informative kind of queries. PREDICT&ASK can be plugged in any constraint acquisition system. We experimentally compare the QUACQ system to an extended version boosted by the use of our recommendation queries. The results show that the extended version improves the basic QUACQ.

Contents

Introduction

Constraint programming (CP) allows effective solving of combinatorial problems in many areas, such as planning and scheduling. However, modeling a combinatorial problem using constraints is a fastidious task that requires significant expertise in CP [START_REF] Freuder | Modeling: The final frontier[END_REF].

To make constraint programming accessible to novices, several constraint acquisition systems have been introduced in the last decade [START_REF] Bessiere | A satbased version space algorithm for acquiring constraint satisfaction problems[END_REF][START_REF] Bessiere | Querydriven constraint acquisition[END_REF][START_REF] Beldiceanu | A model seeker: Extracting global constraint models from positive examples[END_REF][START_REF] Lallouet | On learning constraint problems[END_REF][START_REF] Shchekotykhin | Argumentation based constraint acquisition[END_REF]. These systems either need an expert to validate the learned model or need an exponential number of queries to converge on the target constraint network [START_REF] Bessiere | Solve a constraint problem without modeling it[END_REF]. Recently, a system polynomial in terms of queries, called QUACQ, has been proposed [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. QUACQ iteratively generates partial queries (that is, partial assignments of the variables) and asks the user to classify them. When the answer of the user is yes, QUACQ reduces the search space by removing constraints that reject the positive example. In the case of a negative answer, QUACQ focuses on a constraint in a number of queries logarithmic in the size of the example. This key component allows QUACQ to converge on the target network in a polynomial number of queries. Despite this good theoretical bound, QUACQ may require a lot of queries to learn the target constraint network, especially when the problem is highly structured and involves a large number of constraints. For instance, the user has to classify more than 8000 queries to get the Sudoku model.

The next challenge to constraint acquisition is to reduce the dialog length between the user and the learner or, in other words, to reduce the number of asked queries to get the target model. This chapter presents a generic approach to constraint acquisition which is centered on the following question: Given the constraint graph learned so far, can we infer which new constraints are more likely to belong to the target constraint network? We formalize this question as a link prediction problem in the partial constraint graph learned so far. Furthermore, we introduce a new concept of query, called recommendation query. Borrowing techniques from the link prediction field, a recommendation query asks the user whether or not a predicted constraint belongs to the target constraint network. To deal with recommendation queries, we propose a new constraint recommender algorithm called PREDICT&ASK, which we plugged into the QUACQ constraint acquisition system leading to the P-QUACQ algorithm. We experimentally evaluated the benefit of our approach on several benchmark problems. The results show that P-QUACQ significantly improves the basic QUACQ algorithm in terms of number of queries.

The rest of the chapter is organized as follows. Section 5.2 describes the constraint recommender algorithm. We illustrate the idea behind our constraint recommender algorithm through an example in Section 5.3. In Section 5.4, several predictor techniques are presented. Section 5.5 presents the experimental results we obtained when comparing P-QUACQ to the basic QUACQ. Section 5.6 presents the related work. Section 5.7 concludes the chapter.

PREDICT&ASK Algorithm

In this section, we present our constraint recommender PREDICT&ASK algorithm. The idea behind this algorithm is to predict missing constraints in the partial net-5.2 PREDICT&ASK Algorithm 61 work learned so far, and then to recommend the predicted constraints to the user through a new kind of query, recommendation queries. A recommendation query AskRec(c) asks the user whether or not the constraint c belongs to the target constraint network C T . It is answered yes if and only if c belongs to C T .

Description of PREDICT&ASK

The algorithm PREDICT&ASK takes as argument the set of constraints C learned so far, a relation r, and the predictor score that corresponds to the strategy used to assign a cost to a candidate constraint for recommendation. The algorithm uses the local data structure ∆ which contains all constraints that are candidate for recommendation.

PREDICT&ASK starts by initializing L to the empty set (line 1). The set L will contain the output of PREDICT&ASK, that is all constraints learned by prediction plus recommendation query. In line 4, we build the constraint graph G = (Y,E) restricted to the relation r. The counter #No counts the number of consecutive times recommendation queries have been classified negative by the user. It is initialized to zero at line 5. We put in ∆ all constraints that are candidate for recommendation.

In the main loop of PREDICT&ASK (line 7), for each iteration, we pick a constraint from ∆ such that its score is maximum (line 8). A constraint with a high score means

L ← ∅; 2 Y ← var(c) s.t. (c ∈ C ∧ rel(c) = r) 3 E ← {(x,y) | c ∈ C ∧ rel(c) = r ∧ var(c) = (x,y)} 4 G ← (Y,E) 5 #No ← 0 6 ∆ ← {((x,y),r) ∈ B | (x,y) ∈ Y 2 \ E} 7 while ∆ = ∅ ∧ #No < α do 8 pick ((x,y),r) in ∆ that maximizes score((x,y),G) 9 if AskRec((x,y),r) = yes then 10 L ← L ∪ {((x,y),r)} 11 E ← E ∪ (x,y) 12 #No ← 0 13 else 14 B ← B \ {((x,y),r ′ ) | r ⊆ r ′ } 15 #No + + 16 return L;
that it is likely that this constraint belongs to the target constraint network. Hence, PREDICT&ASK asks a recommendation query on ((x,y),r) (line 9). If the user says 'yes', ((x,y),r) is a constraint of the target network. Hence, we put ((x,y),r) in L (line 10). We also add the edge (x,y) to E to be taken into account in the next iteration when computing the score. In line 12, we reinitialize #No to zero. If the user says 'no', we remove from B the constraint ((x,y),r) (line 14) and we increment #No (line 15). The loop ends when ∆ is empty or when #No reaches the given threshold α, and we return L (line 16).

Using Recommendation in QUACQ

PREDICT&ASK is a generic constraint recommender algorithm that can be plugged into any constraint acquisition system. In this section, we present P-QUACQ (Algorithm 10) where we incorporate PREDICT&ASK into the QUACQ system. P-QUACQ initializes the constraint network C L to the empty set (line 1). When C L is unsatisfiable (line 3), the space of possible networks collapses because there does not exist any subset of the given basis B that is able to correctly classify the examples already asked to the user. In line 4, P-QUACQ computes a complete assignment e satisfying C L and violating at least one constraint from B. If such an example does not exist (line 5), then all constraints in B are implied by C L , and the algorithm has converged. Otherwise, we propose the example e to the user, who will answer by yes or no (line 6). If the answer is yes, we can remove from B the set κ B (e) of all constraints in B that reject e (line 7). If the answer is no, we are sure that e violates at least one constraint of the target network C T . We then call the function FindScope to discover the scope of one of these violated constraints. Here, FindScope acts in a dichotomous manner and asks a number of queries logarithmic in the size of the example. FindC selects which constraint with the given scope is violated by e (line 9). If no constraint is returned (line 10), this is a condition for collapsing as we could not find in B a constraint rejecting one of the negative examples. Otherwise, we know that the constraint c returned by FindC belongs to the target network C T , we then add it to the learned network C L (line 12). Note that FindScope and FindC functions are used exactly as they appear in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. Afterwards, we call PREDICT&ASK to mine the learned constraint network C L in order to predict and recommend missing constraints that may belong to the target network. P-QUACQ updates C L by adding all learned constraints (line 13).

Complexity Analysis

Let us now give the theoretical upper bound of the new constraint acquisition system P-QUACQ. Theorem 5.1. Given a constraint basis B built from a language Γ of bounded arity, and a target network C T , P-QUACQ uses O(C T .(log|X| + Γ ) + |B|) queries to prove convergence or to collapse.

At the end, thanks to PREDICT&ASK three (out of four) constraints are added to the current constraint network (see Figure 5.1(d)).

Prediction Strategies

The way PREDICT&ASK computes the score has not been detailed in Section 5.2. In this section, we present the two techniques that we have used to predict missing constraints. Bessiere et al. (2014a) have shown that when a constraint network has some structure, variables of the same given type are often involved in constraints with the same relation. Hence, we expect that when variable types are not known in advance, predicting type similarity or type proximity of variables could be done by prediction link techniques.

Link prediction in dynamic graphs is an important research field in data mining. Link prediction can be used for recommendation systems [START_REF] Li | Recommendation as link prediction: a graph kernelbased machine learning approach[END_REF]], security domain [START_REF] Valdis | Uncloaking terrorist networks[END_REF], social networks [START_REF] Liben | The link prediction problem for social networks[END_REF], and many other fields. Several techniques have been proposed in the literature for link prediction. All these techniques compute and assign a score to pairs of nodes (x, y), based on the input graph and then produce a ranked list in a decreasing order of scores. They can be viewed as computing a measure of proximity or similarity between nodes x and y, with respect to the network topology. Most of these techniques are based either on node neighborhood or on path ensemble [START_REF] Lu | Link prediction in complex networks: A survey[END_REF]. In our experiments we selected one link prediction technique representative of node-neighborhood-based techniques (Adamic/Adar -AA), and one representative of path-ensemble-based techniques (Leicht-Holme-Newman Index -LHN). Both of these techniques have a time complexity in O(n 3 ). We will see in our experiments that this never takes more than a few milliseconds.

Adamic-Adar Index (AA)

Adamic and Adar (2003) proposed a measure in the context of deciding when two personal home pages are strongly "related". They compute features of the pages and define the similarity index between two pages to be:

z:Z 1 log(frequency(z))
where Z is the set of features shared by x and y. This refines the simple counting of common features by weighting rarer features more heavily. This suggests the measure score(x,y) = where N(x) denotes the neighborhood of x, that is, the set of variables with whom it shares a constraint.

Leicht-Holme-Newman Index (LHN)

Leicht-Holme-Newman (2006) proposed to compute vertex similarity, or proximity, based on the concept that two nodes are similar when their neighbors are similar. This index can be expressed into a matrix form as:

S = 2mλ 1 D -1 (I - φA λ 1 ) -1 D -1
where m is the number of links in the network, λ 1 is the largest Eigenvalue of the adjacency matrix A, D is a diagonal degree matrix, I is the identity matrix, and φ (0 < φ < 1) is a free parameter that assigns higher weights to shorter paths if it is closer to 0 and to longer paths if it is closer to 1 [START_REF] Lu | Link prediction in complex networks: A survey[END_REF]. In all our experiments we have set φ to 0.5 to assign the same weight to both shorter and longer paths.

Experimental Evaluation

We made experiments to evaluate the impact of using PREDICT&ASK in constraint acquisition. We first present the benchmark problems we used for our experiments. Then, we report the results of acquiring these problems with the basic version of QUACQ, with a brute-force algorithm using only recommendation queries (denoted by ONLYREC), and with our P-QUACQ using the Adamic/Adar (AA) and Leicht-Holme-Newman (LNH) indexes to recommend constraints to the user. ON-LYREC makes a brute-force use of recommendation queries: it asks recommendation queries on constraints from B and removes redundant constraints from B each time a new constraint is learned, until convergence is reached. Our tests were conducted on an Intel Core i5-3320M CPU @ 2.60GHz × 4 with 4 Gb of RAM.

Benchmark Problems

Radio Link Frequency Assignment Problem. The RLFAP is to provide communication channels from limited spectral resources [START_REF] Cabon | Warners. Radio link frequency assignment[END_REF]]. Here we build a simplified version of RLFAP that consists in distributing all the frequencies available on the base stations of the network. The constraint model has 36 variables with domains of size 36, and 210 binary constraints. We fed QUACQ and P-QUACQ with a basis of 1800 binary constraints taken from a language of 6 arithmetic and distance constraints. Vessel Loading. Supply vessels transport containers from site to site. The deck area is rectangular. Containers are cuboid, and are laid out in a single layer. All containers are positioned parallel to the sides of the deck. The contents of the containers determine their class. Certain classes of containers are constrained to be separated by minimum distances either along the deck or across the deck. The constraint model has 25 variables with domains of size 25, and 210 binary constraints.

We fed QUACQ and P-QUACQ with a basis of 2610 binary constraints taken from a language of 6 arithmetic and distance constraints. Murder. Someone was murdered last night, and you are summoned to investigate the murder. The objects found on the spot that do not belong to the victim include: a pistol, an umbrella, a cigarette, a diary, and a threatening letter. There are also witnesses who testify that someone had argued with the victim, someone left the house, someone rang the victim, and some walked past the house several times about the time the murder occurred. The suspects are: Miss Linda Ablaze, Mr. Tom Burner, Ms. Lana Curious, Mrs. Suzie Dulles, and Mr. Jack Evilson. Each suspect has a different motive for the murder, including: being harassed, abandoned, sacked, promotion and hate. Under a set of additional clues given in the description, the problem is who was the Murderer? And what was the motive, the evidence-object, and the activity associated with each suspect. The target network of Murder has 20 variables with domains of size 5, and 53 binary constraints. We fed QUACQ and P-QUACQ with a basis B of 1140 binary constraints based on the language Γ = {=, =,≥,<,≤,>}. Zebra problem. The Lewis Carroll's Zebra problem is formulated using 25 variables, with 5 cliques of = constraints and 14 additional constraints given in the description of the problem. We fed QUACQ and P-QUACQ with a basis B of 4450 unary and binary constraints taken from a language with 24 basic arithmetic and distance constraints.

Results

We compare QUACQ, ONLYREC, and P-QUACQ. For P-QUACQ we report results when predicting links with AA or LHN, without cutoff (i.e, α = +∞) and also with four values for the cutoff α (from 1 to 4). We also report results when predicting links with a Random strategy, which serves as baseline selector as it randomly picks a candidate constraint from ∆, and recommends it to the user. For all our experiments we report the number of (standard) queries asked by the basic QUACQ, the number of (recommendation) queries asked by ONLYREC, and the number of queries asked by P-QUACQ. For P-QUACQ we report the number #Ask of standard queries, the number #AskRec of recommendation queries, the numbers #no and #yes of negative and positive recommendation queries (i.e., #AskRec = #no + #yes), and the total number #query of queries (i.e., #query = #Ask + #AskRec). The time overhead of computing scores and generating recommendation queries is not reported because it takes a few milliseconds.

Table 5.1 reports the results of acquiring the RLFAP problem. We first observe that the number of queries asked by P-QUACQ is always significantly lower than with QUACQ or ONLYREC, whatever the way we predict links in P-QUACQ. We also observe that AA and LHN outperform Random for all values of α, which means that their predictions are correlated to the probability of having a constraint at the selected link. When predicting links with AA, we observe that cutoffs hurt the acquisition: the smaller the cuttoff, the greater the number of queries required Such a structure is perfectly well detected both by AA and LHN. This explains that they behave the same and that the shorter the cutoff, the better.

This experimental analysis clearly shows that the use of prediction strategies with recommendation queries can significantly reduce the number of queries asked to the user. The brute-force use of recommendation queries (ONLYREC) is always close to the worst case (i.e., close to |B| queries). The AA prediction strategy seems to be particularly well-suited to problem containing cliques of constraints, whereas the LHN can be highly efficient to predict biclique structures.

Related Work

Several papers have already proposed to use the structure of the constraint graph to decrease the number of examples needed to learn the target constraint network. Beldiceanu and Simonis (2012) have proposed MODELSEEKER, a passive constraint acquisition system devoted to problems having a regular structure. MODELSEEKER To overcome this weakness, [START_REF] Daoudi | Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition[END_REF] have proposed to learn types of variables during the constraint acquisition process, and then to use the learned types to generate generalization queries. The advantage of such an approach is that there is no need for the user to provide the types. Of course learning the types requires extra queries that were not needed when types are given for free at the beginning of the learning process. In addition, generalization queries do not work on all problems. They work only for the problems for which variables can be grouped into types. By contrast, in our work, recommendation queries are generic and do not require any background knowledge to be generated. By using techniques borrowed from link prediction in dynamic graphs, we infer constraints that are more likely to belong to the target constraint network, and that are validated by asking recommendation queries to the user.

Conclusion

We have proposed a new kind of queries, called recommendation queries. To deal with these queries, we have proposed a generic constraint recommender algorithm, PREDICT&ASK, which uses techniques borrowed from link prediction to predict constraints that are likely to belong to the target network. Finally, we have plugged PREDICT&ASK into QUACQ to have a boosted version called P-QUACQ. Our experiments on several benchmark problems show that our new technique outperforms the basic QUACQ. An interesting direction would be to use a reinforcement learning to decide on the use of neighborhood-based predictions or path-ensemble-based predictions.

CHAPTER

Conclusion & Perspectives

We have proposed a new technique to make constraint acquisition more efficient by using information on the types of components the variables in the problem represent. We have introduced generalization queries, a new kind of query asked to the user to generalize a constraint to other scopes of variables of the same type where this constraint possibly applies. Our new technique, GENACQ, can be called to generalize each new constraint that is learned by any constraint acquisition system. We have proposed several heuristics and strategies to select the good candidate generalization query. We have plugged GENACQ into the QUACQ constraint acquisition system, leading to the G-QUACQ algorithm. We have experimentally evaluated the benefit of our approach on several benchmark problems, with and without complete knowledge on the types of variables. The results show that G-QUACQ dramatically improves the basic QUACQ algorithm in terms of number of queries.

The drawback of generalization queries is that they require types of variables of the learned constraint to be generated. To overcome this weakness, and in order to make the build of such queries totally independent of the user, we have proposed to learn types of variables during the constraint acquisition process, and then to use the learned types to generate generalization queries. We have proposed MINE&ASK, a generalization based algorithm that is able to mine partial graphs of constraint networks and to generalize, on potential types, constraints learned by any constraint acquisition system. MINE&ASK acts when no knowledge is provided on the variable types. We have detailed and tested three techniques to extract potential types, namely the modularity, the betweenness and the γ-clique techniques. We have plugged our MINE&ASK into the QUACQ constraint acquisition system, leading to the M-QUACQ algorithm. We have experimentally evaluated the benefit of our approach on several benchmark problems. The results show that M-QUACQ signif-Conclusion & Perspectives icantly improves the basic QUACQ algorithm and they are quite close to the results when variable types are provided.

The advantage of such an approach is that, despite we lose in performance, there is no need for the user to provide the types. Nevertheless, generalization queries do not work on all problems; they work only for high structured problems that their variables can be grouped into types. Toward a generic concept of query, we have introduced a new kind of query, recommendation queries based on the link prediction in dynamic graphs. The advantage of such queries is that they work for a wide range of problems, and they do not need any background knowledge from the user. To deal with that kind of queries, we have proposed a generic constraint recommender algorithm, named PREDICT&ASK, which uses techniques borrowed from the link prediction in dynamic graphs to predict constraints that are more likely to belong to the target network, and then asks the user to classify recommendation queries. Finally, We have plugged PREDICT&ASK into QUACQ system to have a boosted version called P-QUACQ. To evaluate the benefit of recommendation queries, we have made experiments on several benchmarks. The results show that our new technique outperform drastically the basic QUACQ.

Our framework opens up two general areas for further work. First, the framework can be applied as it stands to other disciplines, such as criteria weight elicitation and preference learning. Second, the framework can be extended and improved in several ways. First, we plan to learn the structure of the problem in order to choose the appropriate prediction technique. We know that the performance of a prediction technique depends on the topology of the constraint network. We think that a multi-armed bandit technique may be useful for the choice of the appropriate technique during the acquisition process. Second, we plan to recommend not only one constraint that may belongs to the target network, but also to recommend a part of that network or, why not, the entire network. Third, we plan to incorporate in one system all the proposed techniques. In other words, we will make all our new generic techniques collaborating in order to get the target network as quickly as possible. That is, using at the same time the three kind of queries, namely basic queries, generalization queries, and recommendation queries. The question that we will try to answer is, which query to ask at a given step in the learning process? One answer to that question may be the use of the enforcing learning towards an adaptive constraint acquisition. Forth, so far we deal just with binary constraints; so we plan to extend our framework to deal also with constraints of different arities. And also to be able to learn global constraints. Finally, as a perspective of that work, we plan also to propose a distributed constraint acquisition system to learn problems, which may involve a large number of constraints, by several users; that is, a collaborative learning by users that may have to model the same problem.

Résumé

La plupart des systèmes d'acquisition de contraintes existants interagissent avec l'utilisateur en lui demandant de classer un exemple comme positif ou négatif. Ces requêtes n'utilisent pas la structure du problème ce qui peut entraîner l'utilisateur à répondre à un grand nombre de questions pour apprendre toutes les contraintes. Dans cette thèse, nous montrons que l'utilisation de la structure du problème peut améliorer considérablement le processus d'acquisition. Pour ce faire, nous introduisons deux nouveaux concepts de requêtes utilisant la structure du problème. Le premier concept est celui de requête de généralisation basée sur une agrégation des variables sous forme de types. Le deuxième concept est celui de requête de recommandation basée sur la prédiction des contraintes manquantes dans le graphe courant de contraintes. En outre, nous proposons plusieurs algorithmes et stratégies pour faire face à ces nouveaux types de requêtes. Enfin, nous intégrons ces nouveaux algorithmes dans le système d'acquisition de contraintes QUACQ, menant à trois nouvelles versions, à savoir G-QUACQ, P-QUACQ, et M-QUACQ. Les résultats montrent que les versions étendues améliorent considérablement le système QUACQ de base.

Mots clefs :

Intelligence Artificielle, Programmation par contraintes, Acquisition de contraintes, Détection de communautés, Systèmes de recommandation.

Definition 2 . 2 (

 22 Constraint). Constraints are rules that impose a limitation on the values that a variable, or a combination of variables, may be assigned. Formally speaking, a constraint c is a pair (var(c),rel(c), where var(c) is a sequence of variables of X, called the constraint scope of c, and rel(c) is a relation over D |var(c)| , called the constraint relation of c. For each constraint c, the tuples of rel(c) indicate the allowed combinations of simultaneous value assignments for the variables in var(c). The arity of a constraint c is given by the size |var(c)| of its scope.

Figure 2 . 1 -

 21 Figure 2.1 -An example of constraint graph

Figure 2 . 2 -

 22 Figure 2.2 -An example of 8-Queens problem

Figure 2 . 3 -

 23 Figure 2.3 -An example of graph-coloring problem

Figure 2 . 4 -

 24 Figure 2.4 -An example of sudoku problem.

Figure 2 . 5 -

 25 Figure 2.5 -Constraint acquisition.

Definition 2 . 11 (

 211 Passive constraint acquisition problem). Given a vocabulary (X,D), an unknown constraint network C, a basis B, a constraint language L, a set of solu-20 Background tions E + , and an other set of non-solutions E -of the problem the user has in mind, the constraint acquisition problem is, therefore, to find C such that: -C ⊆ B -For each e ∈ E + , e satisfies all constraints in C -For each e ∈ E -, e rejected by at least one constraint in C

Figure 2 . 6 -

 26 Figure 2.6 -Search space in constraint acquisition

Definition 2 .

 2 13 (Training Data). The set E f of training examples provided to CONACQ.1 is composed of a set E of instances and a classification function f : E -→ {0,1}.

Theorem 2 . 1 (

 21 Correctness of CONACQ.1). Let E f be a set of training examples and B a basis. The clausal theory built by CONACQ.1 for E f and B is such that:

  , Beldiceanu and Simonis proposed Model Seeker, another passive learning approach. Positive examples are provided by the user. The system arranges these examples as a matrix, or any other data structure, and identifies constraints in the global constraints catalog ([Beldiceanu et al., 2007]) that are satisfied by rows or columns of all examples.

Figure 2 . 7 -

 27 Figure 2.7 -General schema of MODELSEEKER.

Algorithm 1 : 6 if 7 else 8 S

 1678 QUACQ: Acquiring a constraint network C T with partial queries 1 C L ← ∅; 2 while true do 3 if sol(C L ) = ∅ then return "collapse"; 4 choose e in D X accepted by C L and rejected by B ; 5 if e = nil then return "convergence on C L "; ASK(e) = yes then B ← B \ κ B (e) ; ← FindScope(e,∅,X,false); 9 c S ← FindC(S); 10 if c S = nil then return "collapse"; 11 else C L ← C L ∪ {c S }; 20). FindC will return a constraint of C T whose scope is in S (line 9). If no constraint is returned (line 22), this is again a condition for collapsing as we could not find in B a constraint rejecting one of the negative examples. Otherwise, the constraint returned by FindC is added to the learned network C L (line 28).

5 while true do 6 choose 7 if e = nil then 8 if ∆ = ∅ then return nil; 9 else 11 B

 678911 e in sol(C L [Y]) such that ∃c Y ,c ′ Y ∈ ∆,e | = c Y and e | = c ′ Y ; pick c Y in ∆; return c; 10 if ASK(e) = yes then ← B \ κ B (e); ∆ ← ∆ \ κ B (e); 12 else 13 if ∃c S ∈ κ B (e) | S Y then 14 return FindC(FindScope(e,∅,Y,false)); 15 else ∆ ← ∆ ∩ κ B (e) ; example e does not violate constraints with scope strictly included in Y (line 13). If yes, we recursively call FindScope and FindC to find that smaller arity constraint before the one having scope Y (line 14). If no, we remove from ∆ all constraints accepting that example e (line 15) and we continue the loop of line 5.

Theorem 2 . 2 (

 22 Complexity). Given a basis B built from a language Γ of bounded arity constraints, and a target network C T , QUACQ uses O(C T .(log|X| + |Γ |)) queries to find the target network or to collapse and O(|B|) queries to prove convergence.

  Finally, examples e 3 = (1,1,1,2,1) and e 4 = (3,2,2,3,3), both positive, will prune = 25 , = 35 ,= 45 and = 25 ,= 35 , = 45 from B respectively, leading to convergence. CHAPTER 3

Figure 3 . 1 -

 31 Figure 3.1 -Variables and types for the Zebra problem.

2 2 C 6 if 8 c

 268 L ← ∅, NonTarget ← ∅; 4 4 while true do 6 sol(C L ) = ∅ then return"collapse"; 8 choose e in D X accepted by C L and rejected by B 10 10 if e = nil then return "convergence on C L "; ← FindC(e,FindScope(e,∅,X,false)) 22 22 if c = nil then return "collapse"; ← C L ∪ {(var,rel(c)) | var ∈ s} violating at least one constraint from B. If such an example does not exist (line 10), then all constraints in B are implied by C L , and we have converged. If we have not converged, we propose the example e to the user, who will answer by yes or no (line 12)

Figure 3 . 2 -

 32 Figure 3.2 -G-QUACQ on RLFAP when the percentage of provided types increases.

Contents 4 . 1

 41 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 MINE&ASK Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 An Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4 Extraction of Potential Types . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5 Experimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Figure 4 . 1 -

 41 Figure 4.1 -The constraint graph of the Zebra problem.

r) ∈ B) then 9 if 10 L 11 generalized ← true 12 else

 9101112 Sol(C L ∪ {(var,r) | var ∈ Y |r| }) = ∅ and AskGen(Y,r) = Yes then ← L ∪ {(var,r) | var ∈ Y |r| } NegativeQ ← NegativeQ ∪ {(Y,r)};

Figure 4 . 2 -

 42 Figure 4.2 -A constraint network with a hidden structure

6 if 7 B 8 else 9 c

 6789 x 10 } and T 3 = {x 11 ,...x 15 }. According to what the user has in mind (part (a) of Figure 4.3), a generalization query on T 3 will be Algorithm 7: M-QUACQ = QUACQ + MINE&ASK Input: mine ∈ {modularity,betweenness,γ-clique}: a mine strategy, GQ max : the maximum number of generalization queries Output: C L : a set of learned constraints 1 C L ← ∅ ; 2 while true do 3 if sol(C L ) = ∅ then return"collapse"; 4 choose e in D X accepted by C L and rejected by B 5 if e = nil then return "convergence on C L "; Ask(e) = yes then ← B \ κ B (e); ← FindC(e,FindScope(e,∅,X,false)); 10 if c = nil then return "collapse"; 11 else 12

Figure 4 . 3 -

 43 Figure 4.3 -Illustrative Example

Definition 4 . 1 .

 41 (γclique) Let G = (X,E) be a graph with X the set of vertices, E the set of edges, and a parameter γ∈ [0,1]. A γclique is a subset of vertices K ⊆ X suchDetecting Types of Variables for Constraint Generalization that the induced subgraph G(K) is a connected component and |E∩K×K| ≥ γ q(q-1) 2

Figure 4 . 4 -

 44 Figure 4.4 -The gain of M-QUACQ on Latin Square when the number of variables increases.

Algorithm 9 :

 9 PREDICT&ASK Input: C: a set of constraints, r: a relation, score ∈ {AA,LHN}: a prediction strategy Output: L: a set of predicted constraints 1

Figure 5 . 2 -

 52 Figure 5.2 -Constraint graphs of our problems.

  , N. Lazaar, Y. Mechqrane, and E.H. Bouyakhf. Boosting constraint acquisition via generalization queries. In ECAI 2014 -21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic -Including Prestigious Applica-tions of Intelligent Systems (PAIS 2014), pages 99-104, 2014. -C. Bessiere, R. Coletta, A. Daoudi, N. Lazaar, Y. Mechqrane, and E.H. Bouyakhf. Acquisition de contraintes par requêtes de généralisation. In Dixièmes Journées Francophones de Programmation par Contraintes (JFPC'14), Angers, France, 2014.

-C. Bessiere, R. Coletta, A. Daoudi, E. Hebrard, G. Katsirelos, N. Lazaar, Y. Mechqrane, N. Narodytska, C. Quimper, and T. Walsh. New Approaches to Constraint Acquisition. In ICON Book, Lecture Notes in Artificial Intelligence, April 2016.

Definition 2.14 (Interpretation

  the version space is the set of hypotheses of H that are consistent with the training examples. In the setting of constraint acquisition, the version space V B (E f ), of a constraint acquisition problem, is the set of all constraint networks admissible by B and consistent with the training examples E f . In the SAT-based formulation of CONACQ.1, the version space is encoded by the clausal theory K, where each model of this theory is a constraint network of V B (E f ).If B is the basis, a literal is either an atom b ij of B or its negation ¬b ij . It is wroth to stress that ¬b ij is not a constraint, but it point out that b ij does not belong to the learned constraint network. A clause is a disjunction of literals, and the clausal theory K is a conjunction of clauses. ). Let B be a basis. An interpretation I over B is a function that assigns to each literal b ij in B a value I(b ij ) in {0,1}

	Background
	learning technique that aims at acquiring a target concept from positive and nega-
	tive examples. Formally speaking, given a set of hypotheses H and a set of training
	examples E,
	. The version space is a supervised machine

Definition 2.15 (Transformation

  ). Let B be a basis. A transformation is a function φ that assigns to each interpretation I of B the constraint network φ(I) admissible by B and such that:

  Firstly, It cannot acquire global constraints. Secondly, it may require a number exponential of examples to get the target network [Bessiere and Koriche, February, 2012]. Thirdly, and finally, CONACQ.1 needs positive examples to learn constraints; why modeling a problem if we have already, at our disposal, solutions for it?

  [START_REF] Mine&ask | [END_REF], an example e is chosen in such a way that ∆ contains both constraints rejecting e and constraints satisfying e. If no such example exists (line 7), this means that all constraints in ∆ are equivalent wrt C L [Y]. Any of them is returned except if ∆ is empty (lines 8-9). If a suitable example was found, it is proposed to the user for classification (line 10). If classified positive, all constraints rejecting it are removed from B and ∆ (line 11). Otherwise we test whether the

Background Algorithm 2: Function FindScope: returns the scope of a constraint in C T 1 function FindScope(in e: example, R,Y: scopes, ask_query: Boolean): scope; 2 begin 3 if ask_query then 4 if ASK(e[R]) = yes then B ← B \ κ B (e[R]) ; 5 else return ∅;

6 if |Y| = 1 then return Y; 7 split Y into < Y 1 ,Y 2 > such that |Y 1 | = ⌈|Y|/2⌉ ; 8 S 1 ← FindScope(e,R ∪ Y 1 ,Y 2 ,true); 9 S 2 ← FindScope(e,R ∪ S 1 ,Y 1 ,(S 1 = ∅));

10 return S 1 ∪ S 2 ; Algorithm 3: Function FindC: returns a constraint of C T with scope Y 1 function FindC(in Y: scope): constraints; 2 begin 3

  al., 2010], Lallouet et al. proposed a system based on inductive logic programming that uses background knowledge on the structure of the problem to learn a representation of the problem correctly classifying the examples. In [Bessiere et al., 2004, 2005], Bessiere et al. made the assumption that the only thing the user is able to provide is examples of solutions and non-solutions of the target problem. Based on these examples, the Conacq.1 system learns a set of constraints that correctly classifies all examples given so far. This type of learning is called passive learning. In [Beldiceanu and Simonis, 2012], Beldiceanu and Simonis proposed Model Seeker, another passive learning approach. Positive examples are provided by the user. The system arranges these examples as a matrix and identifies constraints in the global constraints catalog ([Beldiceanu et al., 2007]) that are satisfied by rows or columns of all examples.

Table ← Table

 ←

\ {s} ;

17 17 while Table = ∅ ∧ #NoAnswers < cutoffNo

do 19 19 pick s in Table 21 21 if

AskGen(s,rel(c)) = yes

then 23 23

Table ← Table

 ← \ {s ′ ∈ Table | s ⊑ s ′ }

	32 32 34 34	NegativeQ ← NegativeQ ∪ {(s,rel(c))} #NoAnswers + +
	36 36 return G;

  Table as local data structure. Table will contain all sequences of types that are candidates for generalizing c.

  Table. A sequence in Table is either asked for generalization or removed from Table in lines 12, 15, 25, or 30. We know from Lemma 3.1 that a sequence removed in line 12, 15, or 30 would necessarily lead to a no answer. We know from Lemma 3.2 that a sequence removed in line 25 is subsumed and less general than another one just added to G. Given a learned constraint c and its associated Table, GENACQ uses O(|Table|) generalization queries to return all maximal sequences of types covering var(c) on which the relation rel(c) holds. For each query on s ∈ Table asked by GENACQ, the size of Table strictly decreases regardless of the answer. As a result, the total number of queries is bounded above by |Table|.

	Proposition 3.2. Proof.

Table 3 .

 3

		1 -QUACQ vs G-QUACQ.
		QUACQ G-QUACQ +random
		#Ask	#Ask	#AskGen
	Zebra	638	257	67
	Sudoku	8645	260	166
	Latin square	1129	117	60
	RFLAP	1653	151	37
	Purdey	173	82	31

Table 3 .

 3 2 -G-QUACQ with heuristics and cutoff strategy on Sudoku.

		cutoff #Ask #AskGen #yes #no
	random			166	42 124
	min_VAR			90	21	69
	min_CST	+∞	260	132	63	69
	max_VAR			263	63 200
	max_CST			247	21 226
		3		75	21	54
	min_VAR	2	260	57	21	36
		1		39	21	18
		3	626	238 112 126
	min_CST	2	679	231 132	99
		1	837	213 153	60

Table 3 .

 3

	3 -G-QUACQ with random, min_VAR, and cutoff=1 on Zebra, Latin square,
	RLFAP, and Purdey.
		#Ask #AskGen #yes #no
		Zebra
	Random		67	10	57
	min_VAR	257	48	5	43
	min_VAR +cutoff=1		23	5	18
		Latin square
	Random		60	16	44
	min_VAR	117	34	10	24
	min_VAR +cutoff=1		20	10	10
		RLFAP
	Random		37	16	21
	min_VAR	151	41	14	27
	min_VAR +cutoff=1		22	14	8
		Purdey
	Random		31	5	26
	min_VAR	82	24	3	21
	min_VAR +cutoff=1		12	3	9

Table 3 .

 3

		0	638	0
		20	619	12
	Zebra	40 60	529 417	20 27
		80	332	40
		100	257	48
		0	8645	0
	Sudoku 9 × 9	33 66	3583 610	232 60
		100	260	39
		0	1129	0
	Latin Square	50	469	49
		100	117	20
		0	173	0
	Purdey	33 66	111 100	8 10
		100	82	12

4 -G-QUACQ when the percentage of provided types increases.

% of types #Ask #AskGen

Table ← Table

 ←

∪ mine(G(Y))

16 return L;

Table 4 .

 4 1 -M-QUACQ with modularity, betweenness and γ-clique on Pla-ceNumPuzzle, Murder, Zebra, Purdey and Sudoku.

		QUACQ G-QUACQ		M-QUACQ
	Strategies	#Ask #Ask #AskGen #Ask #AskGen #no #yes
			Latin Square
	modularity				987	61	26 35
	betweenness	2058 129	68	1674	22	5 17
	γ-clique				1172	35	1 34
			PlaceNumPuzzle
	modularity				627	35	4 31
	betweenness	3746 351	39	655	33	2 31
	γ-clique				688	33	2 31
				Murder
	modularity				272	12	2 10
	betweenness	483 230	55	272	12	2 10
	γ-clique				342	13	3 10
				Zebra
	modularity				410	14	0 14
	betweenness	694 257	67	410	14	0 14
	γ-clique				410	14	0 14
				Purdey
	modularity				140	8	0	8
	betweenness	205	93	39	140	8	0	8
	γ-clique				140	8	0	8
			Sudoku
	modularity				7963	57	20 37
	betweenness	9593 260	166	8960	50	18 32
	γ-clique				9461 117 104 13

  5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 PREDICT&ASK Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.3 An Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.4 Prediction Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.5 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Table 5 .

 5 4 -P-QUACQ on Zebra.

		α #query #Ask #AskRec #no #yes
	QUACQ	-	694 694	-	-	-
	ONLYREC	-4142	-	4142	-	-
		+∞ 675 423	252 221 31
		4	679 496	183 163 20
	P-QUACQ +Random	3	660 505	155 132 23
		2	711 593	118 106 12
		1	693 625	68	60 8
		+∞ 675 423	252 221 31
		4	602 431	171 141 30
	P-QUACQ +AA	3	576 434	142 112 30
		2	524 417	107	77 30
		1	498 428	70	40 30
		+∞ 675 423	252 221 31
		4	602 431	171 141 30
	P-QUACQ +LHN	3	576 434	142 112 30
		2	524 417	107	77 30
		1	498 428	70	40 30

Acknowledgments

Acknowledgments

under the financial support of the scholarship Averroès funded by the European Commission.

Firstly, I would like to express my deepest gratitude to my supervisors Professor El Houssine Bouyakhf and Professor

Proof. By construction, P-QUACQ inherits the correctness of QUACQ, and thus, it always finishes by proving convergence or collapsing. As for its complexity, P-QUACQ asks partial queries (line 6 of P-QUACQ) and recommendation queries (line 9 of PREDICT&ASK). By construction, the number of partial queries in P-QUACQ is bounded above by the number of partial queries of pure QUACQ, that is, O(C T .(log|X| + Γ ) + |B|) [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. Concerning recommendation queries, we know that they are asked on constraints that are in B and not in C L (Algorithm 9, lines 6 and 8). Furthermore, a recommendation query cannot be asked twice on the same constraint as, whatever the answer, the constraint is put in C L (yes answer, Algorithm 9, line 10 and Algorithm 10, line 13) or removed from B (no answer, Algorithm 9, line 14). As a result the number of recommendation queries asked by PREDICT&ASK is in O(|B|) and the number of queries asked by P-QUACQ is in O(C T .(log|X| + Γ ) + |B|).

An Illustrative Example

In this section, we illustrate our constraint recommender algorithm PRE-DICT&ASK through an example. then computes the set ∆ of all candidate constraints that may belong to the target network. ∆ = {((x 1 ,x 3 ),r 1 ),((x 1 ,x 4 ),r 1 ),((x 2 ,x 3 ),r 1 ), ((x 2 ,x 4 ),r 1 ),((x 2 ,x 5 ),r 1 ),((x 3 ,x 5 ),r 1 )}. Then, PREDICT&ASK assigns to each candidate constraint in ∆ a score. We sort the elements of ∆ in decreasing order of their score. Suppose that we have the following order 〈((x 1 ,x 4 ),r 1 ),((x 2 ,x 4 ),r 1 ),((x 2 ,x 5 ),r 1 ), ((x 2 ,x 3 ),r 1 ),((x 3 ,x 5 ),r 1 ),((x 1 ,x 3 ),r 1 )〉. Suppose that α = 1, which means that we have to exit PREDICT&ASK after one negative answer. We pick the first constraint ((x 1 ,x 4 ),r 1 ) in ∆, and we ask the user the recommendation query AskRec((x 1 ,x 4 ),r 1 ), which will be answered yes, as the constraint ((x 1 ,x 4 ),r 1 ) belongs to the target network. The other questions are as follows: -AskRec((x 2 ,x 4 ),r 1 ) = yes

Prediction Strategies

Constraint Acquisition with Recommendation Queries for convergence. On the contrary, P-QUACQ +LHN is better with cutoff: it reaches its lower number of queries to learn the RLFAP network when α = 2 (851 queries instead of 1653 for basic QUACQ and 1575 for ONLYREC). The good performance of LHN on RLFAP can be explained by the structure of that problem. The RLFAP structure contains bicliques and cliques. The constraints that belong to the same clique can be easily predicted by both the neighborhood-based method, AA, or the path-ensemble-based method, LHN. However, constraints in bicliques cannot be predicted by AA because variables of the same constraint do not share any neighbor (see Figure 5.2a). Table 5.2 reports the results on the Vessel Loading problem. The structure of this problem is quite similar to the structure of RLFAP. Thus, the results follow the same trend as on the RLFAP (P-QUACQ +LHN with α = 2 is the best). However, we see that as opposed to the RLFAP, P-QUACQ +AA benefits from the cutoffs.

Table 5.3 reports the results on the Murder problem. The structure of that problem is essentially composed of cliques, as we can see in Figure 5.2b. In this case, we observe that P-QUACQ +AA with a cutoff equal to 1 is the best. It requires 367 queries to get the model instead of 585 queries for QUACQ and 1050 for ON-LYREC. The good performance of the AA predictor can be explained by the fact that neighborhood-based predictors are effective in detecting cliques.

Table 5.4 reports the results on the Zebra problem. Again, P-QUACQ with AA or LHN predictors outperforms QUACQ, ONLYREC, and P-QUACQ +Random. When comparing AA to LHN, we observe that, interestingly, P-QUACQ +AA and P-QUACQ +LHN give exactly the same results for all values of the cutoff α. This can be explained by the fact that only the relation = shows a structure in the network, and that structure is such that all cliques are isolated, as illustrated in Figure 5.2c.

Constraint Acquisition with Recommendation Queries

List of Algorithms

List of Figures