# Efficient Multiple Constraint Acquisition111This paper is an extended
version of paper [38] that appeared in the proceedings of CP-2018.

Dimosthenis C. Tsouros  Dept. of Electrical & Computer Engineering,
University of Western Macedonia,
Kozani, Greece
<EMAIL_ADDRESS><EMAIL_ADDRESS>Kostas Stergiou  Dept. of Electrical &
Computer Engineering,
University of Western Macedonia,
Kozani, Greece
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Constraint acquisition systems such as QuAcq and MultiAcq can assist non-
expert users to model their problems as constraint networks by classifying
(partial) examples as positive or negative. For each negative example, the
former focuses on one constraint of the target network, while the latter can
learn a maximum number of constraints. Two bottlenecks of the acquisition
process where both these algorithms encounter problems are the large number of
queries required to reach convergence, and the high cpu times needed to
generate queries, especially near convergence. In this paper we propose
algorithmic and heuristic methods to deal with both these issues. We first
describe an algorithm, called MQuAcq, that blends the main idea of MultiAcq
into QuAcq resulting in a method that learns as many constraints as MultiAcq
does after a negative example, but with a lower complexity. A detailed
theoretical analysis of the proposed algorithm is also presented. Then we turn
our attention to query generation which is a significant but rather overlooked
part of the acquisition process. We describe how query generation in a typical
constraint acquisition system operates, and we propose heuristics for
improving its efficiency. Experiments from various domains demonstrate that
our resulting algorithm that integrates all the new techniques does not only
generate considerably fewer queries than QuAcq and MultiAcq, but it is also by
far faster than both of them, in average query generation time as well as in
total run time, and also largely alleviates the premature convergence problem.

##  1 Introduction

Constraint programming (CP) has made significant progress over the last
decades, and is now considered as one of the foremost paradigms for solving
combinatorial problems. The basic assumption in CP is that the user models the
problem and a solver is then used to solve it. Despite the many successful
applications of CP on combinatorial problems from various domains, there are
still challenges to be faced in order to make CP technology even more widely
used.

A major bottleneck in the use of CP is modeling. Expressing a combinatorial
problem as a constraint network requires considerable expertise in the field
[25]. To overcome this obstacle, several techniques have been proposed for
modeling a constraint problem automatically, and nowadays automated modeling
is regarded as one of the most important aspects of CP [25, 33, 27, 31, 24,
26]. Along these lines, an area of research that has started to attract a lot
of attention is that of constraint acquisition where the model of a constraint
problem is acquired (i.e. learned) using a set of examples that are posted to
a human user or to a software system [15, 24].

Constraint acquisition is an area where CP meets machine learning, as it can
be formulated as a concept learning task. Constraint acquisition can come in
various flavours depending on factors such as whether the learner can post
queries to the user dynamically, and the type of queries that can be posted
and answered. In passive acquisition, examples of solutions and non-solutions
are provided by the user. Based on these examples and their classification by
the user as positive (solutions) or negative (non-solutions), the system
learns a set of constraints that correctly classifies all the given examples.
A limitation of passive acquisition (and passive learning in general) is the
requirement, from the user’s part, to provide diverse examples of solutions
and non-solution to the system, especially in problems with irregular
structure.

In contrast, in active or interactive acquisition, the learner interacts with
the user dynamically while acquiring the constraint network. In such systems,
the basic query is to ask the user to classify an example as solution or not
solution. This ”yes/no” type of question is called membership query [3], and
this is the type of query that has received the most attention in active
constraint acquisition.

A state-of-the-art interactive acquisition algorithm is QuAcq [12]. For each
example that is classified as negative by the user, QuAcq is able to learn one
constraint of the target network by setting a series of partial queries to the
user. An alternative algorithm, called MultiAcq, finds all the constraints of
the target network violated by a generated example that is classified as
negative [7]. However, MultiAcq needs a linear number of queries in the size
of the example to learn each constraint, whereas QuAcq has a logarithmic
complexity.

In general, active acquisition has several advantages. First of all, it
decreases the number of examples necessary to converge to the target set of
constraints. In addition, it does not require the existence of diverse
examples of solutions or non-solutions to the problem. This is a significant
advantage especially if the problem has not already been solved. Another
advantage is that the user does not need to be human. It might be a previous
system developed to solve the problem. For example, active learning has been
used to automatically acquire CSPs which model the elementary actions of a
robot by asking queries to the simulator of the robot [35].

However, active learning still presents computational challenges regarding the
number of queries required and the cpu time needed to generate them. Despite
the good theoretical bound of QuAcq and QuAcq-like approaches in terms of the
number of queries required to learn a network, the generation of a membership
query is an NP-complete problem. Hence, it can be too time-consuming, and
therefore annoying, especially if the system interacts with a human user. For
example, QuAcq can take more than 30 minutes to generate a query for the model
acquisition of Sudoku puzzles near convergence.

In this work, we present methods to deal with the challenges of interactive
learning. We first introduce an algorithm, called MQuAcq, that blends the main
idea of MultiAcq into QuAcq, achieving a better complexity bound than
MultiAcq. This algorithm uses the reasoning of QuAcq when searching for
constraints to learn once a negative query is encountered, but instead of
focusing on one constraint, it learns a maximum number of constraints, just
like MultiAcq does. But whereas MultiAcq learns constraints of the target
network in a number of queries linear in the size of the example, our proposed
approach finds constraints in a logarithmic number of queries. We make a
detailed theoretical analysis of MQuAcq, proving its correctness and its
complexity in terms of required queries. We also propose an optimization on
the process of locating scopes that reduces the number of queries needed to
learn the target constraint network significantly. This is done by avoiding
posting redundant queries to the user.

Then we focus on the query generation process, which is an important step of
constraint acquisition that has not been discussed in detail in the
literature. We describe the query generation process of standard interactive
acquisition systems in detail, and we propose heuristics that can be applied
during query generation to boost the performance of constraint acquisition
algorithms.

First, we present a heuristic that generalizes the idea of allowing partial
queries to be posted to the user. Instead of using partial queries only when
trying to focus on one or more constraints after a complete example has been
classified as negative, we allow the generation of partial examples to be
posted as partial queries to the user. As experiments demonstrate, this can
reduce the time needed for the system to converge, resulting in avoidance of
premature convergence and reduced total run time for the acquisition process.
Next, we focus on the generation of more informative queries, i.e. queries
that can help to reduce the version space faster. We propose a variable
ordering heuristic for the query generation process, aiming at generating
queries with more information, and achieving to reduce the maximum cpu time
needed for query generation. We then propose a value ordering heuristic that
cuts down the number of queries required.

Experimental results with benchmark problems from various domains demonstrate
that the integration of our methods results in an algorithm that considerably
outperforms both QuAcq and MultiAcq as it generates significantly fewer
queries, it is up to one order of magnitude faster in average query generation
time, it is by far superior in total run time, and it largely alleviates the
premature convergence problem from which both QuAcq and MultiAcq suffer.

In addition, experiments show that our proposed algorithm scales up quite well
in terms of the number of queries required, while the time performance, being
highly dependant on the size of the target network, can rise sharply. Also, it
is shown that learning problems with expressive biases scales well with our
proposed algorithm, even when using a big language to construct the bias,
especially regarding the number of generated queries.

The rest of this paper is organized as follows. Related work is presented in
Section 2. Section 3 introduces the necessary background on constraint
acquisition. In Section 4 we review the algorithms QuAcq and MultiAcq. Section
5 describes the new algorithm that we propose. In Section 6 we describe the
optimization to the process of locating scopes. Section 7 details the query
generation process. In Section 8 we describe the proposed heuristics. An
experimental evaluation is presented at Section 9. In Section 10 we discuss
some important aspects of MQuAcq and point to future work, while Section 11
concludes the paper.

##  2 Related Work

An early approach to passive constraint acquisition is the algorithm ConAcq.1
[9, 10, 15]. Based on the examples of solutions and non-solutions provided by
the user, the system learns a set of constraints that correctly classifies all
examples given so far. A passive learning method based on inductive logic
programming was proposed in [30]. This system uses background knowledge on the
structure of the problem to learn a representation of the problem, correctly
classifying the examples given. Another approach to passive learning is the
ModelSeeker system [8]. In this approach, the user has to provide positive
examples to the system, which are then arranged as a matrix. Then the system
uses the global constraints catalog to identify specific global constraints
that are present in the model. ModelSeeker has been shown to be very effective
in extracting a model from highly structured problems, requiring only a few
positive examples to learn the model of problems such as Sudoku.

Concerning active acquisition, an early related work is the matchmaker agent
which interactively asks the user to explain why a proposed example is
considered as incorrect, by providing one of the constraints that are violated
[28]. An approach to interactive constraint acquisition using version spaces
is presented in [34]. With this approach, examples are provided by the user
that can be used to identify a version space of constraints and then the
system attempts to generalize the user’s examples by choosing a hypothesis
from the current version space. Another active learner presented in the
literature is ConAcq.2 [11, 15] and its extension [37]. Both these systems
acquire constraint models using membership queries that are posted to the user
[3].

A state-of-the-art interactive acquisition algorithm, again based on
membership queries, is QuAcq [12]. QuAcq is able to ask the user to classify
partial queries, i.e. incomplete variable assignments, which may be easier for
the user to answer. Also, asking partial queries gives the system the
capability to focus on the scope of a constraint that is violated and hence
learn the constraint. If the answer to a membership query posted by QuAcq is
positive, the system reduces the search space by removing the set of
constraints violated by this example. If the answer is negative, QuAcq asks a
series of partial queries to locate the scope of one of the violated
constraints of the target network.

An attempt to make QuAcq more efficient was presented by Arcangioli et. al
with the MultiAcq algorithm [7]. Given that the generation of a useful
membership query is not easy and that there may be several constraints that
can be learned by each query, it is very likely that the system can learn more
information from a negative query. So, instead of learning only one
constraint, MultiAcq finds all the constraints of the target network violated
by a generated example that is classified as negative. However, MultiAcq needs
a linear number of queries in the size of the example to learn a constraint.
On the other hand, QuAcq has a logarithmic complexity in terms of the number
of queries.

Attempts to reduce the time needed to generate a membership query were
presented in [2, 1]. Apart from membership queries, other types of queries
such as recommendation and generalization ones, have also been proposed to be
used in interactive constraint acquisition [23, 13]. The use of such queries
can reduce the total number of queries needed to learn a model, but the
drawback is that they require a higher level of expertise from the user’s
part.

Active constraint acquisition is a special case of query-directed learning,
also known as exact learning [19, 20]. Concept learning via queries has been
widely studied in the theoretical machine learning literature. There are well-
known results for several classes of concepts [21, 20], e.g. conjunctions of
Horn clauses [5], $k$-term DNF [17] (or CNF) formula, decision trees [19] etc.

In the learning model introduced in [3] and used by the most approaches to
exact learning, two types of queries are used. The membership query, mentioned
above, that requests the user to classify a given example as positive or
negative and the equivalence query, which asks the user to decide whether the
given concept is equivalent to the target concept. In case of a negative
answer, the user must then provide a counterexample that proves why the two
concepts are not equivalent.

As stated in [15], in the context of constraint acquisition, posting
equivalence queries to the user and expecting counterexamples to be returned
is not feasible from a practical point of view as the assumption is that the
user does not know the constraint network and does not have the skills to
model the target concept directly. However, in the theoretical case where the
user can answer equivalence queries, there exist theoretical results proving
that a constraint network is learnable by equivalence queries alone [15]. It
has to be noted that constraint networks are quite complex to acquire and the
results of generic concept learning algorithms cannot directly be compared to
constraint acquisition algorithms. Also, operating with a bias of bounded
arity constraints and without handling disjunctions of constraints, the
current constraint acquisition algorithms cannot be applied to learn most of
the boolean functions which have been studied in exact learning.

##  3 Background

###  3.1 Vocabulary and Constraint Networks

The vocabulary $(X,D)$ is a finite set of $n$ variables
$X=\\{x_{1},...,x_{n}\\}$ and a set of domains
$D=\\{D(x_{1}),...,D(x_{n})\\}$, where $D(x_{i})\subset\mathbb{Z}$ is the
finite set of values for $x_{i}$. The vocabulary is the common knowledge
shared by the user and the constraint acquisition system.

A constraint $c$ is a pair (rel($c$), scope($c$)), where scope($c$) $\subseteq
X$ is the scope of the constraint and rel($c$) is a relation between the
variables in scope($c$) that specifies which of their assignments are allowed.
$|scope(c)|$ is called the arity of the constraint. We denote by $c_{ij}$ a
binary constraint between variables $x_{i}$ and $x_{j}$, with $c$ being the
relation. A constraint network is a set $C$ of constraints on the vocabulary
$(X,D)$. A constraint network that contains at most one constraint for each
subset of variables (i.e. for each scope) is called a normalized constraint
network.

An example $e_{Y}$ is an assignment on a set of variables $Y\subseteq X$.
$e_{Y}$ is rejected by a constraint $c$ iff scope($c$) $\subseteq Y$ and the
projection $e_{scope(c)}$ of $e_{Y}$ on the variables in scope($c$) is not in
rel($c$). An assignment $e_{Y}$ is a partial solution iff it is accepted by
all the constraints $c\in C$ where $scope(c)\subseteq Y$. A complete
assignment that is accepted by all the constraints in $C$ is a solution to the
problem. $sol(C)$ denotes the set of solutions of $C$. A partial assignment
$e_{Y}$ which is accepted by $C$ is not necessarily part of a complete
solution.

A redundant or implied constraint $c\in C$ is a constraint that if removed
from the constraint network, the set of solutions $sol(C)$ remains the same.
In other words, if all the other constraints in $C$ are satisfied then $c$ is
also satisfied.

###  3.2 Interactive Learning

Using terminology from machine learning, a concept is a Boolean function over
$D^{X}=\prod_{x_{i}\in X}D(x_{i})$, that assigns to each example $e\in D^{X}$
a value in $\\{0,1\\}$, or in other words classifies it as negative or
positive. The target concept $f_{T}$ is a concept that assigns 1 to $e$ if $e$
is a solution of the problem and 0 otherwise. In constraint acquisition, the
target concept is the target constraint network $C_{T}$, such that
$sol(C_{T})=\\{e\in D^{X}\mid f_{T}(e)=1\\}$. Hereafter, following the
literature, we will assume that the target constraint network is normalized.

Besides the vocabulary, the learner has a language $\Gamma$ consisting of
bounded arity constraints. The constraint bias $B$ is a set of constraints on
the vocabulary $(X,D)$, built using the constraint language $\Gamma$, from
which the system can learn the target constraint network. $\kappa_{B}(e_{Y})$
represents the set of constraints in $B$ that reject $e_{Y}$.

The classification question asking the user to determine if an example $e_{X}$
is a solution to the problem that the user has in mind is called a membership
query $ASK(e)$. The answer to a membership query is positive if $f_{T}(e)=1$
and negative otherwise. A partial query $ASK(e_{Y})$, with $Y\subseteq X$,
asks the user to determine if $e_{Y}$, which is an assignment in $D^{Y}$, is a
partial solution or not, i.e. if it is accepted by all the constraints $c\in
C$ where $scope(c)\subseteq Y$. A classified assignment $e_{Y}$ is labelled as
positive or negative depending on the answer of the user to $ASK(e_{Y})$.
Following the literature, we assume that all queries are answered correctly by
the user. From now on, we will sometimes use the terms query and example
interchangeably.

A minimal scope in a negative example $e_{Y}$ is a subset of variables
$S\subseteq Y$ such that ASK($e_{S}$) = “no” and for all $x_{i}\in S$,
ASK($e_{S\setminus x_{i}}$) = “yes”. Thus, a minimal scope $S$ is the scope of
a violated constraint $c\in C_{T}$, such that there does not exist any
violated constraint $c^{\prime}\in C_{T}$ with $scope(c)\subset S$.

To better understand the terms presented, consider the following example,
which we use as a running example in the rest of the paper.

######  Example 1.

Consider a problem consisting of $8$ variables with domains $\\{1,...,8\\}$.
The vocabulary $(X,D)$ given to the system would be $X=\\{x_{1},...,x_{8}\\}$
and $D=\\{D(x_{1}),...,D(x_{8})\\}$ with $D(x_{i})=\\{1,...,8\\}$. Assume that
the problem the user has in mind has to satisfy the constraints $x_{1}\neq
x_{2}$, $x_{1}\neq x_{3}$ and $x_{3}\neq x_{4}$. Thus, the target network
$C_{T}$ would be the set $\\{\neq_{12},\neq_{13},\neq_{34}\\}$. Also, for
simplicity assume that the language $(\Gamma)$ given to the system by the user
contains only the relation $\\{\neq$}. In this case, the bias $B$ would
contain the given relation for all the possible scopes. As it is a binary
relation, $B=\\{\neq_{ij}$ $\mid$ $1\leq i<8\land i<j\leq 8\\}$. In addition,
given an example $e=\\{1,1,1,2,3,4,5,6\\}$,
$\kappa_{B}(e)=\\{\neq_{12},\neq_{13},\neq_{23}\\}$. The scopes
$\\{x_{1},x_{2}\\}$, $\\{x_{1},x_{3}\\}$, $\\{x_{2},x_{3}\\}$ are minimal
scopes, as there is no constraint in $C_{T}$ with a scope $S$ being a subset
of the scope of any of them. If $e$ is posted to the user to be classified as
positive or negative then ASK($e$) is a complete membership query. If only a
partial assignment, for instance $e_{Y}=\\{1,1,1,2,-,-,-,-\\}$ with
$Y=\\{x_{1},x_{2},x_{3},x_{4}\\}$, is posted to the user then $e_{Y}$ is a
partial query.

In interactive constraint acquisition the system generates a set $E$ of
complete and partial examples, which are labelled by the user as positive or
negative. A constraint network $C$ agrees with $E$ if $C$ accepts all examples
labelled as positive in $E$ and rejects those labelled as negative. The
learned network $C_{L}$ has to agree with $E$.

A (complete or partial) query $q=e_{Y}$ is called irredundant (or informative)
iff the answer to $q$ is not predictable. That is, $q$ is irredundant iff it
is not classified as positive by all the constraints in the bias $B$, which
means that $\kappa_{B}(e_{Y})$ is not empty. At the same time, $q$ should be
accepted by the learned network $C_{L}$ otherwise it will be classified as
negative. Considering Example 1, the query $q$ = ASK($e$) is irredundant as it
is not classified as positive by all the constraints from $B$. In this case, a
query $q$ = ASK($e$), with $e=\\{1,2,3,4,5,6,7,8\\}$, would be redundant as it
does not violate any constraint from $B$, thus it is surely positive.

The acquisition process has converged on the learned network $C_{L}\subseteq
B$ iff $C_{L}$ agrees with $E$ and for every other network $C\subseteq B$ that
agrees with $E$, we have $sol(C)=sol(C_{L})$. If the first condition is true
($C_{L}$ agrees with $E$) but the second condition has not been proved, we
have premature convergence. If there does not exist a constraint network
$C\subseteq B$ such that $C$ agrees with $E$ then the acquisition process has
collapsed. This happens when the target constraint network is not included in
the bias, i.e. $C_{T}\nsubseteq B$.

##  4 Algorithms for Interactive Constraint Acquisition

In this section we describe the state-of-the-art QuAcq and MultiAcq algorithms
for interactive constraint acquisition.

State-of-the-art constraint acquisition algorithms are based on the version
space learning paradigm. Initially, the system uses the given language
$\Gamma$ to construct the bias $B$, containing the “candidate” constraints.
Then the system iteratively posts a series of membership queries to the user
in order to learn the constraints of the target network. Each example posted
as a query must satisfy $C_{L}$, i.e. the network that has already been
learned so far, and violate at least one constraint from $B$. A query that
satisfies the above criteria is called informative, as whatever the user’s
answer is, the version space will be pruned. In case the answer is positive,
each constraint $c\in B$ that violates the posted example can be removed from
$B$ (i.e. all the constraint networks containing $c$ are removed from the
version space). In case the answer is negative, we know that one or more of
the violated constraints are certainly in $C_{T}$. So, the system will search
to find the scope of one or all of them, depending on the algorithm used. This
is done through a function called FindScope in QuAcq. A similar function,
called FindAllScopes, is used by MultiAcq. Once a scope has been located, the
function FindC [12] is used to learn the specific constraint (i.e. its
relation).

###  4.1 QuAcq

QuAcq learns one constraint via each generated negative query. Once a
generated example is classified as negative, QuAcq calls the recursive
function FindScope to discover the scope of one of the violated constraints,
as follows. It successively maps the problem of finding a constraint to a
simpler problem by removing entire blocks of variables from the query and
asking partial queries to the user. If after the removal of some variables the
answer of the user to the partial query posted is “yes”, then we know that the
removed block contains at least one variable from the scope of a violated
constraint. So, then FindScope focuses on this block. When, after repeatedly
removing variables, the size of the considered block becomes 1 (i.e. the block
contains a single variable), this variable certainly belongs to a violated
constraint. FindScope achieves a logarithmic complexity in terms of the number
of queries posted to the user by splitting the variables approximately in half
after each removal.

QuAcq (Algorithm 1) starts with an empty $C_{L}$ and a bias $B$ containing all
the possible constraints that can be built using the constraint language
$\Gamma$. The algorithm iteratively posts queries to the user, in the form of
complete assignments. According to the classification of each query, the
learned network $C_{L}$ is augmented with a new constraint from $B$ or some
constraints are removed from $B$. If the algorithm terminates having learned
the target network, it has converged. Otherwise, it has collapsed.

In more detail, QuAcq first checks if the currently learned network has at
least one solution. This is done in case the problem that the user has in mind
is unsolvable. If indeed it is, the acquisition process collapses (line 3).
Otherwise, QuAcq generates a complete assignment $e$ which satisfies the
currently built $C_{L}$ and is rejected by at least one constraint in $B$
(line 4). This is an important step that is not described in detail in the
literature. We focus on the query generation step in Section 7. If no such
example exists, then the system has converged to the target network. After
generating a suitable example $e$, this example is posted as a membership
query to the user. If $e$ is classified as positive (i.e. it is a solution)
then all constraints that violate it are removed from $B$ (line 6), as they
definitely cannot be part of the target network. If $e$ is negative, the
algorithm tries to find one constraint that is violated by $e$ to add to
$C_{L}$ by calling functions FindScope and FindC (line 8). Once the system
learns the constraint (line 10), if no collapse occurs (line 9), it returns to
the query generation step.

Algorithm 1 QuAcq: Quick Acquisition

1:$B$, $X$, $D$ ($B$: the bias, $X$: the set of variables, $D$: the set of
domains)

2:$C_{L}$ : a constraint network

3:$C_{L}\leftarrow\emptyset$;

4:while true do

5: if $sol(C_{L})=\emptyset$ then return “collapse”;

6: Generate $e$ in $D^{X}$ accepted by $C_{L}$ and rejected by $B$;

7: if $e$ = nil then return “$C_{L}$ converged”;

8: if $ASK(e)$ = “yes” then $B\leftarrow B\setminus\kappa_{B}(e)$;

9: else

10: $c\leftarrow FindC(e,FindScope(e,\emptyset,X,false))$;

11: if $c$ = nil then return “collapse”;

12: else $C_{L}\leftarrow C_{L}\cup\\{c\\}$;

FindScope (Algorithm 2) takes as parameters an example $e$ that violates at
least one constraint from the bias, two sets of variables $R$ and $Y$, and a
Boolean variable $ask\\_query$. In the first call to FindScope from QuAcq, $e$
is the example generated in line 4 of QuAcq that is classified as negative,
$R$ is the empty set and $Y$ the set of all the variables of the problem.
$ask\\_query$ is set to false as we already know that $e$ is a negative
example.

Algorithm 2 FindScope

1:$e$, $R$, $Y$, $ask\\_query$ ($e$: the example, $R$,$Y$: sets of variables,
$ask\\_query$: boolean)

2:$Scope$ : a set of variables, the scope of a constraint in $C_{T}$

3:function FindScope($e$, $R$, $Y$, $ask\\_query$)

4: if $ask\\_query$ then

5: if $ASK(e_{R})$ = “yes” then $B\leftarrow B\setminus\kappa_{B}(e_{R})$;

6: else return $\emptyset$;

7: if $|Y|=1$ then return $Y$;

8: split $Y$ into $<Y_{1},Y_{2}>$ such that $|Y_{1}|=\lceil|Y|/2\rceil$;

9: $S_{1}\leftarrow FindScope(e,R\cup Y_{1},Y_{2},true)$;

10: $S_{2}\leftarrow FindScope(e,R\cup S_{1},Y_{1},(S_{1}\neq\emptyset))$;

11: return $S_{1}\cup S_{2}$;

An invariant of FindScope is that the example $e$ violates at least one
constraint whose scope is a subset of $R\cup Y$. If FindScope is called with
$ask\\_query$ = true it asks the user if $e_{R}$ is positive or not (line 3).
If the answer is yes, it removes all the constraints from the bias that reject
$e_{R}$. Otherwise, it returns the empty set (line 3). FindScope reaches line
5 only in the case where $e_{R}$ does not violate any constraint. Hence,
because as mentioned above $e$ violates at least one constraint whose scope is
a subset of $R\cup Y$, if $Y$ is a singleton, the variable it contains surely
belongs to the scope of a constraint that is violated. That is because $e_{R}$
does not violate any constraint (because we have reached at this point), but
we know that $e_{R\cup Y}$ is a negative example. In this case the function
returns $Y$.

If none of the return conditions is satisfied, the set $Y$ is split in two
balanced parts (line 6) and the algorithm searches recursively in the sets of
variables built using these parts for the scope of a violated constraint, in a
logarithmic number of steps (lines 7-9). Function FindScope posts partial
queries to the user until it finds the scope of a constraint that is violated.
A potential deficiency is the fact that if a question to the user violates,
say 3 constraints from $B$, and the answer was negative, then after removing
some variables from $Y$, if the partial query is still violating 3 constraints
from $B$, FindScope will ask the user to classify the partial query again.
However, there is no need for this because it is certain that the partial
query will still be classified as negative. In Section 6 we propose a fix to
this problem.

After the system has located the scope of a violated constraint, it calls
function FindC (Algorithm 3) to find the violated constraint. FindC asks
partial queries to the user in the scope returned by FindScope to locate the
violated constraint. Function FindC takes as parameters $e$ and $Y$, with $e$
being the negative example in which FindScope found that there is a violated
constraint from the target network $C_{T}$, and $Y$ being the scope of that
constraint.

Algorithm 3 FindC

1:$e$, $Y$ ($e$: the example, $Y$: The scope to search)

2:$c$ : a constraint in $C_{T}$

3:function FindC($e$, $Y$)

4: $B\leftarrow B\setminus\\{c_{Y}\mid C_{L}\models c_{Y}\\}$;

5: $\Delta\leftarrow\kappa_{B}(e_{Y})$;

6: if $\Delta=\emptyset$ then return $\emptyset$;

7: while true do

8: Generate $e^{\prime}$ in $D^{Y}$ accepted by $C_{L}$ and rejected by
$\Delta$, with $\kappa_{\Delta}(e_{Y})\neq|\Delta|$;

9: if $e^{\prime}=nil$ then

10: if $\Delta=\emptyset$ then return $\emptyset$;

11: else return random $c$ in $\Delta$ ;

12: if $ASK(e^{\prime})$ = “yes” then

13: $B\leftarrow B\setminus\kappa_{B}(e^{\prime})$;

14: $\Delta\leftarrow\Delta\setminus\kappa_{\Delta}(e^{\prime})$;

15: else $\Delta\leftarrow\kappa_{\Delta}(e^{\prime})$;

In more detail, FindC first removes from the bias the constraints with scope
$Y$ that are implied by the learned network $C_{L}$ (line 2). Next, set
$\Delta$ is initialized to the candidate constraints, i.e. the constraints
from $B$ with scope $Y$ that are violated by $e$ (line 3). If there are no
candidate constraints then the empty set is returned (line 4) resulting in a
collapse for QuAcq. In line 5 it enters its main loop in which it posts
partial queries to the user. In line 6, a partial example $e^{\prime}$ is
generated that is accepted by $C_{L}$ and rejected by $\Delta$ but not by all
of its constraints. This is done to reduce the number of the candidate
constraints whatever the answer of the user may be. If no such example exists
(line 7), this means that any of these constraints could be in $C_{L}$, so one
constraint is randomly returned, except if $\Delta$ is empty (lines 8-9). If
an example was found then it is posted as a query to the user (line 10). If
the answer of the user is “yes” then all constraints rejecting it are removed
from $B$ and $\Delta$ (lines 11-12), otherwise all constraints accepting it
are removed from $\Delta$ (line 13).

Another version of the FindC function which fixes a problem of Algorithm 3 is
described in [14]. Namely, in case the target constraint network contains two
constraints with scopes $S$ and $S^{\prime}$ such that $S\subset S^{\prime}$
then Algorithm 3 is not correct. This is because if an example is classified
as negative, then when FindC removes from $\Delta$ all the constraints
accepting it, at line 13, it does this under the assumption that a constraint
in the scope it currently searches violates the example. However, the example
may have been rejected because of a constraint in a subscope and not by a
constraint in the current scope that is searched. In this case, the
constraints accepting the example should not be removed from $\Delta$, but
Algorithm 3 will remove them. The FindC function introduced in [14] fixes this
problem. These versions of FindC can deal only with normalized constraint
networks. In order to handle non-normalized constraints a different version of
FindC should be used. However, developing such a method is not within the
scope of this paper. Thus, we assume that the target constraint network is
normalized, following the literature.

###  4.2 MultiAcq

Given that there may be several constraints from the target network that are
violated by a generated membership query, it is very likely that the system
can learn more information from a negative generated example (i.e. acquire
more constraints). This is what MultiAcq tries to do, learning a maximum
number of constraints from each negative example [7]. This is done by using
function FindAllScopes. After a negative answer to a query $e_{Y}$, it posts a
series of partial queries by removing one variable from $Y$ for each query. In
case in all of these calls the example is positive then $Y$ is the scope of a
violated constraint. Otherwise, it focuses on all the negative partial queries
to find minimal scopes.

In more detail, MultiAcq (see Algorithm 4) takes as input a bias $B$ and
returns a constraint network $C_{L}$ equivalent to the target network $C_{T}$
like QuAcq does. It iteratively generates an example like QuAcq and then the
function FindAllScopes is called to learn a maximum number of constraints
violated by the specific example (line 8). Before the call of FindAllScopes,
it initializes the set $MSes$, in which it will store the minimal scopes
found, to the empty set.

Algorithm 4 MultiAcq: Multiple Acquisition

1:$B$, $X$, $D$ ($B$: the bias, $X$: the set of variables, $D$: the set of
domains)

2:$C_{L}$ : a constraint network

3:$C_{L}\leftarrow\emptyset$;

4:while true do

5: if $sol(C_{L})=\emptyset$ then return “collapse”;

6: Generate $e$ in $D^{X}$ accepted by $C_{L}$ and rejected by $B$;

7: if $e$ = nil then return “$C_{L}$ converged”;

8: else

9: $MSes\leftarrow\emptyset$;

10: $FindAllScopes(e,X,MSes)$

11: for each $Y\in MSes$ do

12: $c_{Y}\leftarrow FindC(e,Y)$;

13: if $c_{Y}$ = nil then return “collapse”;

14: else $C_{L}\leftarrow C_{L}\cup\\{c_{Y}\\}$;

The recursive function FindAllScopes (Algorithm 5) takes as input a complete
example $e$, a subset of variables $Y$ (equal to $X$ for the first call) and
the set of minimal scopes already found (the empty set in the first call). If
$Y$ is not a minimal scope already found (line 1) and does not contain a
minimal scope already learned (line 3) and $e_{Y}$ contains at least one
violated constraint from the bias (line 2), the system asks the user to
classify the (partial) example $e_{Y}$ (line 4). If the answer is “yes” the
constraints from $B$ violating the example are removed (line 5) and false is
returned (line 6), as $Y$ does not contain any minimal scope. If the answer is
“no”, it means that there still exist violated constraints from $C_{T}$ in
$Y$. So then FindAllScopes is called on each subset of $Y$ built by removing
one variable from $Y$ (lines 8-9). If in all of these calls the example is
positive then $Y$ is the scope of a violated constraint and it is added to the
set $MSes$ (line 10). Then FindAllScopes returns true, as it has found a
minimal scope. Function FindC is then called by MultiAcq to find the
constraint(s), like in QuAcq.

Algorithm 5 FindAllScopes

1:$e$, $Y$, $MSes$ ($e$: an example, $Y$: a set of variables, $MSes$: the set
of minimal scopes)

2:a boolean : if $e_{Y}$ contains a minimal scope

3:if $Y\in MSes$ then return true;

4:if $k_{B}(e_{Y})=\emptyset$ then return false;

5:if $\nexists M\in MSes$ $|$ $M\subset Y$ then

6: if $ASK(e_{Y})$ = “yes” then

7: $B\leftarrow B\setminus\kappa_{B}(e_{R})$;

8: return false;

9:$flag\leftarrow$ false;

10:for each $x_{i}\in Y$ do

11: $flag\leftarrow FindAllScopes(e,Y\setminus\\{x_{i}\\},MSes)\lor flag$

12:if $\neg flag$ then $MSes\leftarrow MSes\cup\\{Y\\}$;

13:return true;

So, instead of focusing on the scope of only one constraint, MultiAcq learns
all the constraints of the target network violated by a generated example.
However, a disadvantage of MultiAcq is that it needs a linear number of
queries in the size of the example to learn a constraint.

Now, we illustrate the behaviour of QuAcq and MultiAcq using our running
example from Section 3.2.

######  Example 2.

Recall that the vocabulary $(X,D)$ given to the system is
$X=\\{x_{1},...,x_{8}\\}$ and $D=\\{D(x_{1}),...,D(x_{8})\\}$ with
$D(x_{i})=\\{1,...,8\\}$, the target network $C_{T}$ is the set
$\\{\neq_{12},\neq_{13},\neq_{34}\\}$ and $B=\\{\neq_{ij}$ $\mid$ $1\leq
i<8\land i<j\leq 8\\}$. Assume that the example generated at line 4 of QuAcq
or MultiAcq is $e=\\{1,1,1,2,3,4,5,6\\}$.

QuAcq will directly post it as a query to the user. The answer will be “no” as
it violates the constraints $\\{\neq_{12},\neq_{13}\\}$ from the target
network. Next, FindScope is called to find the scope of a violated constraint.
Table 1 shows the recursive calls of FindScope. A dash (-) in columns $e_{R}$
and ASK means that no query is posted to the user, due to the condition at
line 2. Also recall that queries are always only on the variables in $R$. As
we can see, after 4 queries, FindScope will find the scope
$\\{x_{1},x_{2}\\}$. Then FindC will immediately return the constraint
$\\{\neq_{12}\\}$ as it is the only constraint in $B$ with this scope. After
the constraint is added to $C_{L}$, QuAcq will go back to line 3 and as no
collapse occurs, it will generate a new example.

Table 1: Recursive calls of FindScope in Example 2

call | $R$ | $Y$ | $e_{R}$ | ASK | return
---|---|---|---|---|---
0 | $\emptyset$ | $x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}$ | - | - | $\\{x_{1},x_{2}\\}$
1 | $x_{1},x_{2},x_{3},x_{4}$ | $x_{5},x_{6},x_{7},x_{8}$ | $\\{1,1,1,2,-,-,-,-\\}$ | “no” | $\emptyset$
2 | $\emptyset$ | $x_{1},x_{2},x_{3},x_{4}$ | - | - | $\\{x_{1},x_{2}\\}$
2.1 | $x_{1},x_{2}$ | $x_{3},x_{4}$ | $\\{1,1,-,-,-,-,-,-\\}$ | “no” | $\emptyset$
2.2 | $\emptyset$ | $x_{1},x_{2}$ | - | - | $\\{x_{1},x_{2}\\}$
2.2.1 | $x_{1}$ | $x_{2}$ | $\\{1,-,-,-,-,-,-,-\\}$ | “yes” | $\\{x_{2}\\}$
2.2.2 | $x_{2}$ | $x_{1}$ | $\\{-,1,-,-,-,-,-,-\\}$ | “yes” | $\\{x_{1}\\}$

After generating the same example $e$, MultiAcq will directly give it to the
function FindAllScopes. Table 2 presents the trace of its recursive calls.
After 8 queries it will find the scopes of both constraints from $C_{T}$. It
will need one more query to remove the constraint $\\{\neq_{23}\\}$ from the
bias and as no other constraint from $B$ is violated it will return. FindC
will return immediately each of the constraints $\\{\neq_{12}\\}$ and
$\\{\neq_{13}\\}$ as they are the only ones in $B$ with these scopes.

Table 2: Recursive calls of FindAllScopes in Example 2.

call | $Y$ | $e_{Y}$ | ASK | $MSes$ | return
---|---|---|---|---|---
0 | $x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{1,1,1,2,3,4,5,6\\}$ | “no” | $\emptyset$ | true
1 | $x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7}$ | $\\{1,1,1,2,3,4,5,-\\}$ | “no” | $\emptyset$ | true
1.1 | $x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}$ | $\\{1,1,1,2,3,4,-,-\\}$ | “no” | $\emptyset$ | true
1.1.1 | $x_{1},x_{2},x_{3},x_{4},x_{5}$ | $\\{1,1,1,2,3,-,-,-\\}$ | “no” | $\emptyset$ | true
1.1.1.1 | $x_{1},x_{2},x_{3},x_{4}$ | $\\{1,1,1,2,-,-,-,-\\}$ | “no” | $\emptyset$ | true
1.1.1.1.1 | $x_{1},x_{2},x_{3}$ | $\\{1,1,1,-,-,-,-,-\\}$ | “no” | $\emptyset$ | true
1.1.1.1.1.1 | $x_{1},x_{2}$ | $\\{1,1,-,-,-,-,-,-\\}$ | “no” | $\\{\\{x_{1},x_{2}\\}\\}$ | true
1.1.1.1.1.1.1 | $x_{1}$ | $\\{1,-,-,-,-,-,-,-\\}$ | - | $\\{\\{x_{1},x_{2}\\}\\}$ | false
1.1.1.1.1.1.2 | $x_{2}$ | $\\{-,1,-,-,-,-,-,-\\}$ | - | $\\{\\{x_{1},x_{2}\\}\\}$ | false
1.1.1.1.1.2 | $x_{1},x_{3}$ | $\\{1,-,1,-,-,-,-,-\\}$ | “no” | $\\{\\{x_{1},x_{2}\\},\\{x_{1},x_{3}\\}\\}$ | true
1.1.1.1.1.2.1 | $x_{1}$ | $\\{1,-,-,-,-,-,-,-\\}$ | - | $\\{\\{x_{1},x_{2}\\},\\{x_{1},x_{3}\\}\\}$ | false
1.1.1.1.1.2.2 | $x_{3}$ | $\\{-,-,1,-,-,-,-,-\\}$ | - | $\\{\\{x_{1},x_{2}\\},\\{x_{1},x_{3}\\}\\}$ | false
1.1.1.1.1.3 | $x_{2},x_{3}$ | $\\{-,1,1,-,-,-,-,-\\}$ | “yes” | $\\{\\{x_{1},x_{2}\\},\\{x_{1},x_{3}\\}\\}$ | false

In addition to the above, which are described in the relevant papers, QuAcq
and MultiAcq take some extra steps during query generation222Personal
communication with the authors of the algorithms.. We detail these in Section
7.

##  5 Efficient Multiple Constraint Acquisition

As explained, the main difference between QuAcq and MultiAcq is that the
latter tries to find multiple constraints that are violated once a query is
classified as negative. However, MultiAcq needs a linear number of queries in
the size of the example to locate the scope of each violated constraint. In
contrast, QuAcq requries a logarithmic number of queries but finds only one
violated constraint. Our intuition was to merge the idea of learning a maximum
number of constraints from each generated negative example with the QuAcq
reasoning of learning each constraint in a logarithmic number of steps. Our
resulting new algorithm, called Multi-QuAcq (MQuAcq for short), needs a
logarithmic number of queries to discover each violated constraint, achieving
the benefits of both QuAcq and MultiAcq.

###  5.1 Multi-QuAcq description

MQuAcq (Algorithm 6) is an active learning algorithm which is based on QuAcq
and extends it by incorporating the basic idea of MultiAcq. The main
difference between QuAcq and MQuAcq is the fact that QuAcq finds one
explanation (constraint) of why the user classified an example as negative,
whereas MQuAcq tries to learn all the violated constraints. This is done by
calling function FindScope (Algorithm 2) iteratively, while reducing the
search space by removing variables from the scopes already found. The main
difference between MQuAcq and MultiAcq is that the former uses the QuAcq
search method to find each scope through function FindScope, and in this way
avoids some redundant searches (which can be very time-consuming) as well as
queries that MultiAcq makes with function FindAllScopes. Besides this, there
are several other differences, particularly on how the algorithms operate to
locate irredundant queries after learning a constraint from a generated
negative example. As a result, our proposed algorithm has a better complexity
bound in terms of the number of queries.

MQuAcq finds all the violated constraints via the function FindAllCons. The
main idea is that after finding a constraint $c$, using QuAcq’s reasoning, we
exploit the fact that for any other violated constraint $c^{\prime}\in C_{T}$,
we have $scope(c)\setminus scope(c^{\prime})\neq\emptyset$. This is because
otherwise $scope(c)$ would not be a minimal scope. So, FindAllCons recursively
acquires all the violated constraints from $e_{Y\setminus\\{x\\}}$, for each
$x\in scope(c)$. Hence, the reasoning of QuAcq is recursively used in these
partial examples, in order to find multiple constraints, with the benefit
(inherited from QuAcq) of finding the scope of each constraint with a
logarithmic complexity.

Algorithm 6 The MQuAcq Algorithm

1:$B$, $X$, $D$ ($B$: the bias, $X$: the set of variables, $D$: the set of
domains)

2:$C_{L}$ : a constraint network

3:$C_{L}\leftarrow\emptyset$;

4:$collapse\leftarrow$ false;

5:while true do

6: if $sol(C_{L})=\emptyset$ then return “collapse”;

7: Generate $e$ in $D^{X}$ accepted by $C_{L}$ and rejected by $B$;

8: if $e$ = nil then return “$C_{L}$ converged”;

9: $FindAllCons(e,X,\emptyset)$;

10: if $collapse=$ true then return “collapse”;

MQuAcq starts by initializing the $C_{L}$ network to the empty set (line 1)
and the global variable $collapse$ to false (line 2). This variable is used
within function FindAllCons as explained below. Next, the algorithm enters its
main loop (line 3). If $C_{L}$ is unsatisfiable, the algorithm collapses (line
4). Otherwise, a complete assignment $e$ is generated (line 5), satisfying
$C_{L}$ and violating at least one constraint in $B$. This step is explained
in detail in Section 7. If such an example does not exist then we have
converged (line 6). Otherwise, the function FindAllCons is called to find all
the constraints that are violated by the example $e$ (lines 7). If findAllCons
has detected a collapse then the algorithm terminates (line 8).

The recursive function FindAllCons is presented in Algorithm 7. It takes as
parameters an example $e$, a set of variables $Y$ and a set $Scopes$, which
contains the scopes of the violated constraints on $e_{Y}$ already learned. It
returns the set $\operatorname{NScopes}$ consisting of the scopes of the
constraints acquired. FindAllCons adds to $C_{L}$ all the constraints that are
violated by $e$ in $Y$. The sets $Scopes$ and $\operatorname{NScopes}$ are
used to store all the scopes of the constraints that have been found in
$e_{Y}$ to avoid searching and asking partial queries with the scope of a
violated constraint that has been already learned. Specifically, the set
$Scopes$ stores the scopes of the constraints learned before the current call
of the function. On the other hand, the set $\operatorname{NScopes}$ stores
the scopes of the constraints learned from the current call (or any sub-call).
For example, if we have acquired 3 constraints from $e_{Y}$, 2 from a previous
call and 1 from the current call of FindAllCons, then the set $Scopes$ will
contain the scopes of the 2 constraints previously learned and the set
$\operatorname{NScopes}$ will contain the scope of the constraint learned from
the current call.

Our proposed approach is to search for partial queries in the given example
that do not contain any constraint already found, so that the answer will not
be predictable. To achieve this, from each scope $S$ already found we make
$|S|$ partial examples, one for each variable $x_{i}\in S$, with each such
example involving variables $Y^{\prime}=Y\setminus\\{x_{i}\\}$. When a partial
example that violates no constraint already learned but at least one from $B$
is found, FindAllCons uses FindScope, as in QuAcq, to learn a constraint from
$C_{T}$.

Algorithm 7 FindAllCons

1:$e,Y,Scopes$ ($e$: the example, $Y$: set of variables, $Scopes$: a set of
scopes already learned)

2:$\operatorname{NScopes}$ : the set of scopes learned

3:function FindAllCons($e$, $Y$, $Scopes$)

4: if $collapse=$ true then return $\emptyset$;

5: if $\nexists scope(c)\neq S$ $|$ $c\in\kappa_{B\setminus C_{L}}(e_{Y})\land
S\in Scopes$ then return $\emptyset$;

6: $\operatorname{NScopes}\leftarrow\emptyset$;

7: if $Scopes\neq\emptyset$ then

8: pick an $S\in Scopes$;

9: for each $x_{i}\in S$ do

10: $\operatorname{NScopes}\leftarrow\operatorname{NScopes}\cup
FindAllCons(e,Y\setminus\\{x_{i}\\},\operatorname{NScopes}\cup(Scopes\setminus\\{S\\}))$;

11: else

12: if ASK($e_{Y}$) = “yes” then $B\leftarrow B\setminus\kappa_{B}(e_{Y})$;

13: else

14: $scope\leftarrow FindScope(e,\emptyset,Y,false)$;

15: $c\leftarrow FindC(e,scope)$;

16: if $c$ = nil then

17: $collapse\leftarrow$ true;

18: return $\emptyset$;

19: else $C_{L}\leftarrow C_{L}\cup\\{c\\}$;

20: $\operatorname{NScopes}\leftarrow\operatorname{NScopes}\cup\\{scope\\}$;

21: $\operatorname{NScopes}\leftarrow\operatorname{NScopes}\cup
FindAllCons(e,Y,\operatorname{NScopes})$;

22: return $\operatorname{NScopes}$;

FindAllCons starts by checking if collapse has occurred. If this is the case
the empty set is returned (line 2). Then it checks if there exists any
violated constraint in $B$ to learn, with a scope different to those of the
constraints already acquired. If no constraint that can be learned exists, it
is implied that ASK($e_{Y}$) = “yes”. Thus, again we return the empty set
(line 3) because we assume that the bias is expressive enough to learn a
$C_{L}$ equivalent to the target network $C_{T}$. This check is important
because as the recursive calls to FindAllCons remove variables from $Y$ (as
explained below), we may end up in a case where $e_{Y}$ is surely positive and
no search for a violated constraint is needed. This is because if ASK($e_{Y}$)
= “yes” then for every $Y^{\prime}\subseteq Y$ we surely have
ASK($e_{Y^{\prime}}$) = “yes”. With this check the algorithm avoids a lot of
redundant searches, reducing the number of nodes in the tree of recursive
calls, and also avoids asking redundant queries. In the case that neither of
the two conditions is satisfied, FindAllCons will continue. At line 4, the set
$\operatorname{NScopes}$ is initialized to the empty set.

After that, FindAllCons checks if the set $Scopes$ is not empty (line 5). If
this is the case it means that we have not branched on all the scopes already
found and we still have in $e_{Y}$ the scope of at least one violated
constraint. So we call FindAllCons recursively on each subset of $Y$ created
by removing one of the variables of a scope $S\in Scopes$, removing the scope
$S$ in which we branched from the set $Scopes$ given to the recursive calls
(lines 6-8). We remove the scope in which we branched as this scope is no
longer included in the set of variables given to to the recursive calls. Also
we give to the function the set
$\operatorname{NScopes}\cup(Scopes\setminus\\{S\\})$ as although the set
$\operatorname{NScopes}$ is empty at the first call, it may contain scopes
found in the next recursive calls.

In the case that the set $Scopes$ is empty (line 9), it means that we have
finished with branching and we have a partial example $e_{Y}$ that does not
contain the scope of any violated constraint already learned. Hence, there
must exist a partial query $e_{Y}$ that violates at least one constraint of
$B$ (otherwise the algorithm would have returned at line 2) and no violated
constraint already found exists in $Y$. Therefore, the system asks again the
user to classify the partial example as positive or negative (line 10). If the
answer is positive then the constraints in $B$ that reject $e$ are removed.
Otherwise, function FindScope is called to find the scope of one of the
violated constraints (line 12). FindC will then select a constraint from $B$
with the discovered scope that is violated by $e_{Y}$ (line 13). If no
constraint is found then the algorithm collapses (line 14-16). Otherwise, the
constraint returned by FindC is added to $C_{L}$ (line 17) and its scope is
added to the set of found scopes (line 18). Then, we call again FindAllCons to
continue searching in the partial examples created by removing the variables
of the scope the function has just found.

We now illustrate the behavior of FindAllCons in a simple problem using our
running example.

######  Example 3.

Recall that the problem consists of $8$ variables and suppose that the
complete example $e=\\{1,1,1,1,2,3,4,5\\}$ is generated in line 5 of MQuAcq.
The constraints from $C_{T}$ that are violated by $e$ are $\neq_{12}$,
$\neq_{13}$ and $\neq_{34}$ (all the constraints from $C_{T}$ in this case).
Table 3 presents the trace of the recursive calls of FindAllCons.

Table 3: Recursive calls of FindAllCons in Example 3

call | $Y$ | $e_{Y}$ | ASK | $Scopes$ | return
---|---|---|---|---|---
0 | $x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{1,1,1,1,2,3,4,5\\}$ | “no” | $\emptyset$ | $\\{\\{x_{1},x_{2}\\},\\{x_{3},x_{4}\\},\\{x_{1},x_{3}\\}\\}$
1 | $x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{1,1,1,1,2,3,4,5\\}$ | - | $\\{\\{x_{1},x_{2}\\}\\}$ | $\\{\\{x_{3},x_{4}\\},\\{x_{1},x_{3}\\}\\}$
1.1 | $x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{-,1,1,1,2,3,4,5\\}$ | “no” | $\emptyset$ | $\\{\\{x_{3},x_{4}\\}\\}$
1.1.1 | $x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{-,1,1,1,2,3,4,5\\}$ | - | $\\{\\{x_{3},x_{4}\\}\\}$ | $\emptyset$
1.1.1.1 | $x_{2},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{-,1,-,1,2,3,4,5\\}$ | “yes” | $\emptyset$ | $\emptyset$
1.1.1.2 | $x_{2},x_{3},x_{5},x_{6},x_{7},x_{8}$ | $\\{-,1,1,-,2,3,4,5\\}$ | “yes” | $\emptyset$ | $\emptyset$
1.2 | $x_{1},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{1,-,1,1,2,3,4,5\\}$ | - | $\\{\\{x_{3},x_{4}\\}\\}$ | $\\{\\{x_{1},x_{3}\\}\\}$
1.2.1 | $x_{1},x_{4},x_{5},x_{6},x_{7},x_{8}$ | $\\{1,-,-,1,2,3,4,5\\}$ | “yes” | $\emptyset$ | $\emptyset$
1.2.2 | $x_{1},x_{3},x_{5},x_{6},x_{7},x_{8}$ | $\\{1,-,1,-,2,3,4,5\\}$ | “no” | $\emptyset$ | $\\{\\{x_{1},x_{3}\\}\\}$

In the first call (call 0) to FindAllCons, $e$ will be posted as a query to
the user. After the user answers “no”, the algorithm will find the constraint
$\neq_{12}$ using functions FindScope and FindC. Next, FindAllCons will be
called to continue searching for the remaining constraints that violate $e$.
In the next call (call 1) we have $Y=X$ and $Scopes=\\{\\{x_{1},x_{2}\\}\\}$.
As $Scopes\neq\emptyset$, we know that the answer to ASK($e_{Y}$) (with
$e_{Y}=e_{X}$) will be “no”. So, no query is posted to the user and
FindAllCons will be called recursively on each subset of $Y$ built by removing
one variable from a scope $S\in Scopes$ (i.e. $\\{x_{1},x_{2}\\}$ as this is
the only one), and removing this scope from the set given to the recursive
calls. Thus, in the first recursive call (call 1.1) we have
$Y^{\prime}=Y\setminus\\{x_{1}\\}$ and $Scopes=\emptyset$. This means that we
have branched on all scopes found until now. Hence, the example
$e_{Y^{\prime}}=\\{-,1,1,1,2,3,4,5\\}$ will be posted as a query to the user
and the constraint $\neq_{34}$ will be learned because it is the only
constraint from $C_{T}$ that is violated by $e_{Y^{\prime}}$. In the next call
(call 1.1.1) of FindAllCons in line 14 no further constraint will be found, as
no constraint from $C_{T}$ is violated.

So, we go back to the second call of line 5 (call 1.2). We have
$Y^{\prime}=Y\setminus\\{x_{2}\\}$ and $Scopes=\\{\\{x_{3},x_{4}\\}\\}$ (the
scope of the constraint learned from the call 1.1). As $Scopes\neq\emptyset$,
we have another scope in which we have to branch. Hence, FindAllCons will be
called recursively on each subset of $Y^{\prime}$ built by removing one
variable from a scope $S\in Scopes$ (i.e. $\\{x_{3},x_{4}\\}$ as this is the
only one). Also this scope is removed from the set of scopes given to the
recursive calls.

In call 1.2.1, we have $Y^{\prime\prime}=Y^{\prime}\setminus\\{x_{3}\\}$ and
$Scopes=\emptyset$. Because no constraint from $C_{T}$ is violated by
$e_{Y^{\prime\prime}}=\\{1,-,-,1,2,3,4,5\\}$, the answer from the user will be
“yes” and the empty set will be returned. In call 1.2.2, we have
$Y^{\prime\prime}=Y^{\prime}\setminus\\{x_{4}\\}$ and $Scopes=\emptyset$.
Thus, the example $e_{Y^{\prime\prime}}=\\{1,-,1,-,2,3,4,5\\}$ will be posted
to the user and then the constraint $\neq_{13}$ will be learned. No further
constraint will be found, as no other constraint from $C_{T}$ is violated by
$e_{Y}$.

###  5.2 Analysis

In this section we prove the correctness (i.e. soundness and completeness) of
MQuAcq. To obtain this proof we first prove some properties of functions
FindScope and FindC. We also study the complexity of MQuAcq in terms of the
number of queries it needs to converge to the target network.

######  Lemma 1.

If ASK($e_{Y}$) = “yes” then for any $Y^{\prime}\subseteq Y$ it holds that
ASK($e_{Y^{\prime}}$) = “yes”.

###### Proof.

We know that for every $Y^{\prime}\subseteq Y$, the set of constraints from
$C_{T}$ that are violated by $e_{Y^{\prime}}$ is a subset of the set of
constraints rejecting $e_{Y}$ (i.e.
$\kappa_{C_{T}}(e_{Y^{\prime}})\subseteq\kappa_{C_{T}}(e_{Y})$). Thus, if we
know that $\kappa_{C_{T}}(e_{Y})=\emptyset$ (ASK($e_{Y}$) = “yes”) then for
every $Y^{\prime}\subseteq Y$ it holds that
$\kappa_{C_{T}}(e_{Y^{\prime}})=\emptyset$ which means that
ASK($e_{Y^{\prime}}$) = “yes”. ∎

######  Lemma 2.

If ASK($e_{Y}$) = “no” then for any $Y^{\prime}\supseteq Y$ it holds that
ASK($e_{Y^{\prime}}$) = “no”.

###### Proof.

We know that for every $Y^{\prime}\supseteq Y$, the set of constraints from
$C_{T}$ that are violated by $e_{Y^{\prime}}$ is a superset of the set of
constraints rejecting $e_{Y}$ (i.e.
$\kappa_{C_{T}}(e_{Y^{\prime}})\supseteq\kappa_{C_{T}}(e_{Y})$). Thus, if we
know that $\kappa_{C_{T}}(e_{Y})\neq\emptyset$ (ASK($e_{Y}$) = “no”) then for
every $Y^{\prime}\supseteq Y$ it holds that
$\kappa_{C_{T}}(e_{Y^{\prime}})\neq\emptyset$ which means that
ASK($e_{Y^{\prime}}$) = “no”. ∎

Lemmas 1 and 2 have also been proved in [7], albeit slightly differently.

######  Proposition 1.

Given the assumption that $C_{T}$ is representable by $B$, if FindScope is
given an example $e_{Y}$ and returns a scope $S$, then there exists a violated
constraint $c\in C_{T}$ with $scope(c)=S$. Also $S$ is a minimal scope.

###### Proof.

Recall that an invariant of FindScope is that the example $e$ violates at
least one constraint whose scope is a subset of $R\cup Y$ (i.e. ASK($R\cup Y$)
= “no”). Also, it reaches line 5 only in the case that $e_{R}$ does not
violate any constraint from $C_{T}$ (i.e. ASK($e_{R}$) = “yes” from Lemma 1).
In addition, in FindScope variables are returned only at line 5, in the case
$Y$ is a singleton. Thus, for any $x_{i}\in S$ we know that ASK($S$) = “no”
and ASK($S\setminus x_{i}$) = “yes”. Hence, $S$ is a scope of a violated
constraint from the target network. Also, as we have ASK($S\setminus x_{i}$) =
“yes’ for any $x_{i}\in S$, it holds that $S$ is a minimal scope.

∎

######  Proposition 2.

Given an example $e$, the scope $Y$ of a violated constraint of $C_{T}$ and a
bias $B$ that can represent $C_{T}$, FindC will return a constraint $c\in
C_{T}$ with $scope(c)=Y$ under the assumption that $C_{T}$ does not contain
any other constraint with scope $Y^{\prime}\subseteq Y$.

###### Proof.

$\forall c\in\Delta$ we know that $c$ is violated by $e_{Y}$ as
$c\in\kappa_{B}(e_{Y})$ (line 2). Thus, as $B$ can represent $C_{T}$, if $Y$
is the scope of a violated constraint $c\in C_{T}$, this constraint is surely
included in $\Delta$. Now we will prove that this constraint is never removed
from $\Delta$ but the constraints not in $C_{T}$ are. Constraints are removed
from $\Delta$ only at lines 12,13. When the user’s answer to the generated
query is “yes” then the constraint that we seek is not violated (Lemma 1), so
$\Delta\leftarrow\Delta\setminus\kappa_{\Delta}(e^{\prime})$ does not remove
it. On the other hand, if the user’s answer is “no” then the constraint $c\in
C_{T}$ that we seek is surely violated as $C_{T}$ does not contain any other
constraint with a scope $Y^{\prime}\subseteq Y$. Therefore, the operation
$\Delta\leftarrow\kappa_{\Delta}(e^{\prime})$ does not remove it.

Thus, an invariant of FindC is that $\Delta$ surely includes a constraint that
made the user to classify as negative the example $e_{Y}$ given to the
function, as it is added to $\Delta$ and never removed from it. Hence, if an
example accepting some constraints in $\Delta$ and rejecting others cannot be
generated at line 6, all the constraints in $\Delta$ are equivalent wrt
$C_{L}$. Thus, whichever among them (if more than one) is returned, this
constraint $c$ is surely included in $C_{T}$.

∎

######  Theorem 1.

Given a bias $B$ built from a language $\Gamma$, with bounded arity
constraints, and a target network $C_{T}$ representable by $B$, MQuAcq is
correct.

###### Proof.

Soundness. MQuAcq learns constraints only via the function FindAllCons.
FindAllCons learns a constraint using the function FindC after finding the
scope of the constraint with the function FindScope. Given the assumption that
the user’s answers are correct and that the target network $C_{T}$ is
representable by $B$, FindScope returns the scope of a violated constraint
from $C_{T}$ (Proposition 1). Also, as FindC is called with the scope returned
from FindScope and the example classified as negative by the user, it will
return a violated constraint $c\in C_{T}$ (Proposition 2). Thus, FindAllCons
is sound, which means that MQuAcq is sound, as for every constraint $c$ added
to $C_{L}$ it holds that $c\in C_{T}$.

Completeness. MQuAcq learns constraints only via the function FindAllCons.
Thus, if given an example $e_{Y}$ FindAllCons can acquire any violated
constraint $c\in C_{T}$ then MQuAcq is complete. That is because MQuAcq
iteratively generates examples that violate constraints from $B$ and gives
them to FindAllCons. It stops only if no example can be generated at line 5.
If this is the case, it means that the system has converged as $C_{L}$ agrees
with $E$ and for every other network $C\subseteq B$ that agrees with E, we
have $sol(C)=sol(C_{L})$. Now we will prove that given an example $e_{Y}$
function FindAllCons can acquire any violated constraint $c\in C_{T}$.

Given the assumption that the target network $C_{T}$ is representable by $B$,
if the condition at line 3 is satisfied then we know that no constraint from
$C_{T}$ can be learned. Also, given an example $e_{Y}$, with $Y\subseteq X$,
we know that if ASK($e_{Y}$) = “yes” then for any $Y^{\prime}\subseteq Y$ it
is ASK($e_{Y^{\prime}}$) = “yes” (Lemma 1). Hence, in this case again no
constraint from $C_{T}$ is violated by $e_{Y}$. Thus, if a minimal scope $M$
exists in $Y$ then the condition at line 3 is not satisfied and the answer
from the user at line 10 will be “no”, as $Y\supseteq M$ (Lemma 2). Thus, if
function FindAllCons is given an example $e_{Y}$ violating a constraint from
$C_{T}$, it will reach lines 12-13 to learn the constraint using functions
FindScope and FindC. In addition, FindAllCons will surely search for any
minimal scope $M$ in a $Y\supseteq M$. We know that if a constraint with scope
$S$ is learned from an example, then FindAllCons will search for another
violated constraint from $C_{T}$ in $Y\setminus\\{x_{i}\\},\forall x_{i}\in
S$. Thus, in each $e_{Y\setminus\\{x_{i}\\}}$ it will search for minimal
scopes $M$ such that $x_{i}\not\in M$ and $M\subseteq
Y\setminus\\{x_{i}\\},\forall x_{i}\in S$. Generalizing this, function
FindAllCons will find all the minimal scopes $M$ such that $S\nsubseteq M$ and
$M\subseteq Y$. Hence, it will find all the minimal scopes in $Y$ and then
learn the constraints by calling FindC.

∎

We now analyse the complexity of MQuAcq in terms of the number of queries it
asks to the user.

######  Theorem 2.

Given a bias $B$ built from a language $\Gamma$, with bounded arity
constraints, and a target network $C_{T}$, MQuAcq uses
$O(|C_{T}|\cdot(log|X|+|\Gamma|))$ queries to find the target network or to
collapse and $O(|B|)$ queries to prove convergence.

###### Proof.

Queries are asked to the user in lines 10 of FindAllCons, 3 of FindScope and 9
of FindC. We know that a scope of a constraint from $C_{T}$ is found in
$O(|S|\cdot log|Y|)$ queries with the function FindScope, with $|S|$ being the
arity of the scope and $|Y|$ the size of the example given to the function
[12]. As $Y\subseteq X$, FindScope needs at most $|S|\cdot log|X|$ queries to
find the scope of a constraint, because in FindAllCons, in the worst case,
only one constraint from $C_{T}$ will be violated by any complete example.
Also, FindC needs at most $|\Gamma|$ queries to find a constraint from $C_{T}$
in the scope it takes as parameter, if one exists [12]. If none exists, the
system collapses. Hence, in the worst case, the number of queries necessary to
find each constraint is $O(|S|\cdot log|X|+|\Gamma|)$. Thus, the number of
queries for finding all the constraints in $C_{T}$ or collapsing is at most
$C_{T}\cdot(|S|\cdot log|X|+|\Gamma|)$ which is
$O(C_{T}\cdot(log|X|+|\Gamma|))$ because $|S|$ is bounded. Convergence is
proved when $B$ is empty or contains only redundant constraints. Constraints
are removed from $B$ when the answer from the user is “yes” in a query. In the
case that the example generated by the algorithm in line 5, contains only one
violated constraint from $B$, it leads to at least one constraint removal in
each query. This gives a total of $O(|B|)$ queries to prove convergence. ∎

The complexities of QuAcq and MultiAcq to find the target network are
$O(|C_{T}|\cdot(log|X|+|\Gamma|))$ and $O(|C_{T}|\cdot(|X|+|\Gamma|))$
respectively. Hence, we achieve the same bound as QuAcq but a better one than
MultiAcq, while discovering all the violated constraints from a negative
example.

##  6 FindScope-2

We now describe an optimization to function FindScope, aiming at asking fewer
queries to the user by avoiding posting redundant queries. This results in a
function we simply call FindScope-2, which can be used instead of FindScope
either inside QuAcq or inside our proposed algorithm MQuAcq.

Let us first consider a simple example to show a deficiency of FindScope.

######  Example 4.

Consider the behaviour of FindScope in the simple problem of the Example 2.
The recursive calls of FindScope are illustrated in Table 1. The negative
example given to FindScope is $e=\\{1,1,1,2,3,4,5,6\\}$. The constraints from
$B$ that it violates are $\kappa_{B}(e)=\\{\neq_{12},\neq_{13},\neq_{23}\\}$.
After the first call to FindScope, $R$ is equal to $x_{1},x_{2},x_{3},x_{4}$,
so the partial example $e_{R}$ that is then asked to the user is
$e_{R}=\\{1,1,1,2\\}$. As we can see, the constraints from $B$ that are
violated are still $\kappa_{B}(e)=\\{\neq_{12},\neq_{13},\neq_{23}\\}$.
Therefore, this partial example is negative as no violated constraint from
$B$, that could be included to $C_{T}$, is removed. Thus, there is no point in
posting it to the user.

In addition, given the assumption that the bias is expressive enough to learn
$C_{T}$, in cases where $|\kappa_{B}(e_{R})|=0$ (i.e. there is no violated
constraint in $B$), it is implied that ASK($e_{R}$) = “yes”. For example, see
the last two queries asked from FindScope in the current example. The are
queries that include only one variable, but the bias does not include any
unary constraint. Thus, it is implied that these are positive examples and
thus, these queries were redundant.

To avoid such redundant queries made by FindScope, we modify this function
(see Algorithm 8) adding a check that inspects if the number of violated
constraints from the bias is the same as in the last query asked. This is
implemented using a global variable $rej$ to store this number. This check is
done in line 3. If this is the case, it is implied that the answer will still
be no and therefore we return the empty set. Before the first call to
FindScope, $rej$ must be initialized to the number of constraints from $B$
that are violated by the complete query.

Algorithm 8 FindScope-2

1:$e$, $R$, $Y$, $ask\\_query$ ($e$: the example, $R$,$Y$: sets of variables,
$ask\\_query$: boolean)

2:$Scope$ : a set of variables, the scope of a constraint in $C_{T}$

3:function FindScope-2($e$, $R$, $Y$, $ask\\_query$)

4: if $ask\\_query\land|\kappa_{B}(e_{R})|>0$ then

5: if $rej\neq|\kappa_{B}(e_{R})|$ then

6: if ASK($e_{R}$) = “yes” then $B\leftarrow B\setminus\kappa_{B}(e_{R})$;

7: else

8: $rej\leftarrow|\kappa_{B}(e_{R})|$;

9: return $\emptyset$;

10: else return $\emptyset$;

11: if $|Y|=1$ then return $Y$;

12: split $Y$ into $<Y_{1},Y_{2}>$ such that $|Y_{1}|=\lceil|Y|/2\rceil$;

13: $S_{1}\leftarrow FindScope-2(e,R\cup Y_{1},Y_{2},true)$;

14: $S_{2}\leftarrow FindScope-2(e,R\cup S_{1},Y_{1},(S_{1}\neq\emptyset))$;

15: return $S_{1}\cup S_{2}$;

As a further improvement to FindScope, in cases where $|\kappa_{B}(e_{R})|=0$
no query is asked to the user as is implied that ASK($e_{R}$) = “yes”. So
another check is performed in line 2. If the bias is not expressive enough to
learn $C_{T}$, the system will collapse later, because it will not find any
constraint to learn.

###  6.1 FindScope-2 analysis

######  Proposition 3.

Given the assumption that $C_{T}$ is representable by $B$, if FindScope-2 is
given an example $e_{Y}$ and returns a scope $S$, then there exists a violated
constraint $c\in C_{T}$ with $scope(c)=S$. Also $S$ is a minimal scope.

###### Proof.

Let us first prove that the invariant of FindScope that the example $e$
violates at least one constraint whose scope is a subset of $R\cup Y$ (i.e.
ASK($R\cup Y$) = “no”) applies to FindScope-2 as well. The check added at line
2 does not affect this property, as in the case $|\kappa_{B}(e_{R})|=0$ we
know that for any $Y^{\prime}\subseteq Y$ it holds that ASK($e_{Y^{\prime}}$)
= “yes” (Lemma 1). Thus, it reaches line 9 only in the case that $e_{R}$ does
not violate any constraint from $C_{T}$. Focusing on the check added at line
3, in the case $rej=\kappa_{B}{e_{R}}$ it returns $\emptyset$, because we know
that the answer of the user would be negative.

Thus, for the same reason as in FindScope, for any $x_{i}\in S$, we know that
ASK($S$) = “no” and ASK($S\setminus x_{i}$) = “yes”. Hence, $S$ is a scope of
a violated constraint from the target network. Also, as we have
ASK($S\setminus x_{i}$) = “yes’ for any $x_{i}\in S$, it holds that $S$ is a
minimal scope.

∎

######  Proposition 4.

Given a negative example $e_{Y}$, FindScope-2 posts $\Theta(|S|\cdot log|Y|)$
queries in order to find the scope of a violated constraint, in the worst
case.

###### Proof.

The number of queries posted by FindScope-2 is equal to the number of nodes of
the tree of recursive calls in the worst case, in which a query is posted in
each node. Now we will find the number of nodes of this tree in this case. The
branches of the tree that will find a variable in $S$ will have $log|Y|$
depth. The tree of recursive calls to FindScope-2 will have $|S|$ such
branches. Thus, in such a case the number of nodes of these branches is
$n=|S|\cdot log|Y|$. FindScope-2 either makes two recursive calls in each call
or it returns $\emptyset$. Thus, for each node on a branch that finds a
variable in $S$, we have one sibling that is either a leaf, or starts another
branch that will find another variable in $S$. Hence, the leaves that do not
return a variable in $S$ will be $n-|S|$. As a result, the number of nodes
will be $2\cdot|S|\cdot log|Y|-|S|$. As a result, FindScope-2 posts
$\Theta(|S|\cdot log|Y|)$ queries to the user in the worst case.

∎

##  7 Query Generation in Constraint Acquisition

In constraint acquisition we would ideally want every generated query to
contain as much “information” to be learned as possible. That is, we would
like to generate queries that violate as many constraints as possible. To
acquire this information we want a constraint to be violated and then, via the
user’s answers, the algorithm will decide either to learn the constraint or to
remove it from the bias. We want to maximize the constraints from $B$ that
reject the generated example because this can reduce the number of queries
required to converge. That is because after a positive query, all the
constraints rejecting the example are removed from $B$. MQuAcq, like QuAcq,
has a worst case complexity in terms of the number of queries in
$O(|C_{T}|\cdot log|X|+O(|B|)$. Hence, it is desirable to prune from $B$ the
constraints that are not included in $C_{T}$ with as few queries as possible.
Ideally we want each positive query to violate a maximum number of constraints
from $B$. With this objective, as proved in [12], we can bridge the gap to
$O(|C_{T}|log|X|)$ queries for some simple languages, and avoid needing a
number of queries up to $|B|$ to prove convergence.

The standard technique for query generation in constraint acquisition systems,
such as QuAcq and MultiAcq, is based on the following basic idea: find a
solution of the learned constraint network ($C_{L}$) that violates a maximum
number of constraints from the bias. Although the query generation step is a
very important step of the acquisition process, it is not described in detail
in the literature. Here we focus on query generation and explain it in detail
for the first time. We then propose heuristics to enhance its efficiency.

Query generation it typically viewed as an optimization problem that includes
both hard and soft constraints. In general, a hard constraint represents a
requirement that cannot be violated. All hard constraints must be mandatorily
satisfied in a solution. Soft constraints are used to formalize desired
properties, preferences that should be satisfied as much as possible.

Query generation can be modelled in this way by considering the constraints
from $C_{L}$ as hard constraints. The soft constraints can either (and
equivalently) be the constraints from the bias or their complement (the set
$\\{\neg c$ $|$ $c\in B\setminus C_{L}$}). In case the soft constraints are
the complement of the constraints from $B$, the objective is to maximize the
number of such constraints that are satisfied. Otherwise, the objective is to
maximize the number of constraints from $B$ that are violated.

As CP solvers, whether they can handle soft constraints or not, cannot express
this objective naturally, we reformulate the problem as maximizing the the
number of satisfied constraint negations. Hence, we view the problem of query
generation as a MAX-CSP that includes hard constraints (the ones from $C_{L}$)
and soft ones (the complement of the constraints in $B$). Thus, this is a
simple case of (unweighted) MAX-CSP [29], with the requirement that hard
constraints must be satisfied, giving all the soft constraints the same
importance and the goal is to maximize the number of the satisfied soft
constraints. In the case of query generation there is also another
requirement, that is, at least one soft constraint must be satisfied. This is
because we want to generate an irredundant query, in which we do not already
know the answer.

This is also the approach taken by QuAcq and MultiAcq. When solving this
optimization problem, both these algorithms try to find a solution that
satisfies all the constraints in $C_{L}$ and maximizes the satisfaction of the
complementary constraints from $B$. This is known as the max heuristic [12,
7]. Except form the above, there are some extra steps in the query generation.
This is because the generation of a query that maximizes the violated
constraints from $B$ is an NP-hard problem, and therefore may be very time-
consuming. The query generation process (line 4 of QuAcq and MultiAcq, line 5
of MQuAcq and line 6 of FindC) is presented in Algorithm 9. We denote the
process described above as $QGen(C_{h},C_{s})$, with $C_{h}$ being the set of
hard constraints and $C_{s}$ the set of soft constraints.

Algorithm 9 IrrGen: Generate an Irredundant Query

1:$C_{L}$, $B$, $V$, $D$ ($C_{L}$: the learned network, $B$: the bias, $V$:
the variables, $D$: the domains of the variables)

2:$q$: an irredundant query

3:$C_{s}\leftarrow\\{\neg c$ $|$ $c\in B\setminus C_{L}\\}$;

4:$e\leftarrow QGen(C_{L},C_{s})$;

5:if $e\neq nil$ then return $e$;

6:else

7: for all $c\in C_{s}$ do

8: Generate $e$ in $sol(C_{L}\cap c)$;

9: if $e\neq nil$ then return $e$;

10:return nil;

First the set $C_{s}$ containing the soft constraints is initialized (line 1).
Next (line 2), an example is generated that is a solution to the learned
network $C_{L}$ and satisfies as many constraints as possible from $C_{s}$,
(i.e. violating as many as possible from the bias). There are two cutoffs
imposed in QGen, to make sure that the query generation will run in acceptable
time. We denote them as $cut_{min}$ and $cut_{max}$. If the query generator
has found a query violating at least one constraint and the first cutoff
($cut_{min}$) is triggered, the best query found is returned. If not, it tries
until the maximum time (defined by $cut_{max}$) has been reached.

If an irredundant query is found then it is returned (line 3). In case no
example is found within this time limit then the system tries again, taking
the constraints in $B$ one by one (lines 5-8). That is, for each constraint
$c\in C_{s}$, it tries to find a solution of $C_{L}$ satisfying $c$. The
second cutoff of QGen ($cut_{max}$) is again used for this process. This is
done until a query violating at least one constraint from $B$ is found.
However, setting any time limit to the query generation process means that the
algorithm may reach premature convergence. That is because it is quite likely
that no solution to $C_{L}$ that violates some constraints from $B$ is found
within the time limit, at some point of the algorithm’s execution, meaning
that it has not been proved that $sol(C)=sol(C_{L})$ for every other network
$C\subseteq B$ that agrees with $E$. As a result, all the algorithms suffer
from this problem. This is something that has only very recently been pointed
out [2, 38].

##  8 Heuristics for boosting query generation

In this section we propose heuristics to improve the performance of constraint
acquisition systems. In Section 8.1 we propose a heuristic for the generation
of partial queries by the algorithms. In Sections 8.2 and 8.3 we propose
heuristics for value and variable ordering when trying to generate queries.

###  8.1 Exploiting partial queries

Let us first note that although both QuAcq and MultiAcq allow for the use of
partial queries to focus on the violated constraint(s) after an example has
been classified as negative, they both always aim to generate complete
examples. However, as explained, generating a complete example requires
finding a complete variable assignment that satisfies all constraints in
$C_{L}$ and violates at least one constraint in $B$. Given that this is an NP-
complete problem, the process can be very time-consuming, especially as the
size of $C_{L}$ grows and the size of $B$ shrinks, i.e. when approaching
convergence.

Experimental results that we have obtained with both QuAcq and MultiAcq
demonstrate that when no time limit to the query generation process is set
then both algorithms can take several minutes (more than 30 minutes) to
generate a query as convergence is approached, even for small problems such as
the 9x9 Sudoku. This of course is unacceptable from the user’s point of view,
and therefore a time limit is necessary for the practical application of the
algorithms. However, setting a time limit to the query generation process
means that the algorithm may reach premature convergence, as explained before.

Another relevant issue is that of proving convergence in problems that contain
redundant constraints. As the system cannot always know beforehand if some of
the constraints in the bias are redundant, proving that no solution of $C_{L}$
violates at least one constraint in $B$ can be very time-consuming in the
presence of redundant constraints. This is because if near the end of the
process $B$ is left with redundant constraints only, no solution of $C_{L}$
can violate any of these constraints, simply because these constraints, being
implied, will be surely satisfied.

Given the importance of query generation in the acquisition process, it is of
primary importance that it is executed as efficiently as possible, and in a
way such that the problem of premature convergence is avoided as much as
possible. Towards this, we propose to exploit partial queries at this step of
the process. Both QuAcq and MultiAcq, and also our proposed algorithm, assume
that the user, be it human or machine, is able to answer partial queries, so
there is no reason to limit the use of partial queries to the case where a
complete query has been classified as negative.

Our proposal is to model the query generation problem as an optimization
problem, like in the previous section, in which we seek to find a (partial)
assignment of the variables that maximizes the number of violated constraints
in $B$. That is, we again have a MAX-CSP, with the difference being that the
optimal solution does not necessarily involve an assignment to all the
variables. This optimization problem can be formally stated as “search for
$(e_{Y}$, $Y)$ with $e_{Y}\in sol(C_{L}[Y])\land Y\subseteq X$, maximizing
$\kappa_{B}(e_{Y})$”. We call this heuristic maxB. This is related to but is
not the same as the max heuristic (described in the previous section) that was
also used within QuAcq [12]. As already explained, the max heuristic tries to
generate a complete solution of $C_{L}$ that violates a maximum number of
constraints from $B$. Hence, given a time limit, which is necessary for any
algorithm to run in reasonable times as explained above, max will focus on
finding complete assignments that satisfy all the constraints in $C_{L}$ and
violate as many as possible from $B$, while maxB will focus on violating as
many constraints as possible from $B$ without necessarily building a complete
variable assignment.

Of course, finding a partial assignment $e_{Y}$ on a set of variables
$Y\subseteq X$ not rejected by $C_{L}$ and violating constraints from the
bias, does not mean that $e_{Y}$ can be extended to a solution of $C_{L}$, but
this is not a problem under the assumption that the user can classify partial
queries correctly.

Although the difference between maxB and max may not seem substantial,
experimental results given below show that the use of maxB largely alleviates
the danger of premature convergence and can have a significant impact on the
total run time of the acquisition algorithm. This is because by using maxB,
the system can also learn redundant constraints, thus it does not have to
prove that a constraint cannot be violated. Learning the redundant constraints
is necessary if we want to guarantee that the system will always converge.

###  8.2 Variable ordering heuristic

Given that query generation is an optimization problem that is solved using a
CP solver, an important question that must be answered is which variable/value
ordering heuristic to use for this problem. One way is to simply apply the
default strategies of the CP solver used. For example, dom/wdeg [18] or a
simpler heuristic like dom/ddeg (or even dom) for variable ordering, and
random or lexicographic value ordering. This is the path taken by all
acquisition algorithms so far. The reasoning behind it is that standard
heuristics will help find a complete solution to $C_{L}$ quite fast, as this
problem is a typical CSP, and then the maximum number of violating constraints
in $B$ will be seeked within the time limit as a secondary requirement.

But, as explained before, in constraint acquisition we would ideally want
every generated query to contain as much “information” as possible. Given that
the focus of our proposed heuristic maxB, is on violating as many constraints
from $B$ as possible, and not on building a complete solution to $C_{L}$, it
is likely that traditional variable and value ordering heuristics, that are
efficient when seeking a solution to a CSP, are not the best choice. This is
because these heuristics focus on information (conflicts, degrees, domain
sizes) obtained from the variables and constraints of $C_{L}$. But since maxB
primarily focuses on the bias $B$, meaning that finding a complete solution to
$C_{L}$ is not paramount, it is reasonable to use a variable ordering
heuristic that exploits information obtained from the variables and
constraints of $B$. Towards this, we propose a simple variable ordering
heuristic that maximizes the constraint violations in $B$.

This heuristic, which we call bdeg (degree of variables in the bias $B$),
selects the variable which participates in the maximum number of constraints
present in $B\setminus C_{L}$. It can be seen as analogue to the classic
variable ordering heuristic deg for CSPs, which selects the variable with the
largest degree. But in contrast to standard CSPs where deg is not competitive
at all, bdeg is very efficient when used for query generation, especially near
convergence where it manages to drastically cut down the waiting times for the
user.

Comparing bdeg to heuristics like dom/wdeg, we note that bdeg prefers
variables belonging to the scope of many constraints from $B$, ignoring
$C_{L}$, whereas standard heuristics do not treat the constraints from $C_{L}$
and $B$ differently when computing their metric, or even focus only on
constraints from $C_{L}$. Hence, for example, a variable involved in many
constraint from $C_{L}$ and only few from $B$ is very likely to be preferred.

###  8.3 Value Ordering Heuristic

First recall that a generated query should violate a large number of
constraints from $B$ and some of these constraints may be added to $C_{L}$,
while others may be removed from $B$, depending on the answers of the user to
the partial queries posted by FindAllCons. So, using a value ordering
heuristic that picks values that are involved in a large number of conflicts
(i.e. violate many constraints) in $B$ makes sense for the query generation
step. This is because picking a value which violates many constraints from $B$
quickly leads to a (partial) assignment with a lot of information to be
extracted.

Hence, we propose the maxv heuristic for value ordering, which selects the
value that maximizes the number of conflicts (constraint violations) between
the currently selected variable and the variables that have been already
assigned. We consider instantiated variables only because if maxB is used then
the query generated may not include all the variables of the problem.

To better understand the practical effect of the maxv heuristic, let us
consider its behaviour when generating a query in the problem from our running
example.

######  Example 5.

For the purposes of this example, the variable ordering heuristic is not
important. Assume that variables are ordered lexicographically. In the
beginning of the query generation process, the use of maxv will not have any
effect at the first variable’s instantiation. Assume that the value selected
for the first variable is $x_{1}=1$. From now on, when choosing a value for
the following variables, maxv will keep on choosing value 1, as in this
example it is the only value that violates some constraints from $B$. Thus,
the generated example will be $e=\\{1,1,1,1,1,1,1,1\\}$, which in this case
violates all the constraints from the bias.

An important factor to consider about the effect of value ordering regards the
generation of the first query. In this case all the variables are involved in
the same number of constraints in $B$ (because nothing has been removed from
$B$ yet) and $C_{L}$ is empty. Thus, the variable ordering is not important.
On the other hand, value ordering seems to be very important. Experiments have
shown that using maxv for the generation of the first query often leads to a
query which violates all of the constraints from $C_{T}$. Also, when the
acquisition process is near convergence and only a few constraints are left in
$B$, we want queries that remove a maximum number of constraints after a
positive answer from the user. So, again the maxv heuristic is the best
choice.

Given the importance of selecting values that maximize constraint violations,
the lexico value ordering heuristic, which simply selects values in their
lexicographic order and is very commonly used by CP solvers, is not a good
idea because the values that maximize conflicts may appear in the middle or
near the end of a domain, meaning that values with low conflicts may be
preferred instead. On the other hand, random value ordering is a better idea
but still not as good as focusing on the values that maximize conflicts, as
maxv does. As a downside, maxv is more expensive to compute as the conflicts
caused by each value must be calculated before the selection is made.

##  9 Experimental Evaluation

To evaluate our proposed methods, we ran experiments on a system carrying an
Intel(R) Xeon(R) E5-2667 CPU, 2.9 GHz, with 8 Gb of RAM. We compared the
proposed methods to both QuAcq and MultiAcq, which were implemented as
efficiently as possible using the strategies described in [12, 7].

To be precise:

  * •

The “flawed” FindC function of [12] described in Section 4 is used in all our
methods. This does not affect our results as a situation in which it may fail
(analyzed in Section 4) does not appear in any of the studied benchmarks.
However, we have also implemented the corrected version of [14] to deal with
such cases when they arise.

  * •

In all our methods, and also in QuAcq and MultiAcq, we set the $cut_{max}$
cutoffs of the query generation step (described in Section 7) to 5 seconds.
This means that if no query is found within 5 seconds, Function QGen returns.
Also, we set the $cut_{min}$ cutoff to 1 second, returning the best example
found within this time limit, if any is found.

  * •

To maximize the performance of MultiAcq we used the heuristic proposed in [7]:
A cutoff of 5 seconds is used in function FindAllScopes. After triggering the
cutoff for the first time, FindAllScopes is called again on the same complete
example with a reverse order of the variables. If the cutoff is triggered for
a second time, we generate a new example and shuffle the variables’ order. To
ensure termination, FindAllScopes is forced to return at least one scope
before cutting off.

  * •

To evaluate our proposed variable and value ordering heuristics, we
implemented them within QuAcq and MQuAcq and ran experiments using benchmark
instances. We compared them with the use of dom/wdeg as variable ordering
heuristic and random for value ordering, which are the standard options for
existing acquisition algorithms.

  * •

In order to compare all the algorithms on the same scenario, all the
experiments concern the extreme case where no background knowledge is used and
thus $C_{L}$ is initially empty. This extreme scenario results in an overall
number of queries that may seem too large for human users to answer without
making errors. However, in real applications background knowledge can be used
either by giving a frame of basic constraints to the system or by using some
other method to extract some constraints from known solutions and non-
solutions of the problem, e.g. ModelSeeker [8].

  * •

Each method was run 10 times and the means are presented.

We used the following benchmarks in our study:

Sudoku. The Sudoku puzzle is a 9 $\times$ 9 grid. It must be completed in such
a way that all the rows, all the columns and the 9 non-overlapping 3 $\times$
3 squares contain the numbers 1 to 9. The vocabulary for this problem has 81
variables and domains of size 9. The target network has 810 binary $\neq$
constraints on rows, columns and squares. The bias was initialized with 12.960
binary constraints from the language $\Gamma=\\{=,\neq,>,<\\}$.

Greater than Sudoku (GTSudoku). This is a variant of Sudoku where instead of
having only cliques of $\neq$ constraints, some neighboring variables are
related via $>,<$ constraints. The number of variables and the maximum domain
size are the same as in Sudoku, but there are no prefilled squares (i.e.
assigned variables). We used the instance shown in Figure 1 and the same
language and bias as in Sudoku. What is interesting with GTSudoku is that the
introduction of inequality constraints breaks up the regular structure of
Sudoku.

Figure 1: Greater than Sudoku instance used in the experiments

Latin Square. The Latin square problem consists of a n $\times$ n table in
which each element occurs once in every row and column. In our experiments we
set n to 10, meaning that we have 100 variables with domains of size 10. The
target network has 900 binary $\neq$ constraints on rows and columns. The
system was initialized with a bias of 19.800 binary constraints created from
the language $\Gamma=\\{=,\neq,>,<\\}$.

Zebra. The Zebra problem has a single solution. The problem consists of 25
variables of domain size of 5. The target network contains 50 $\neq$
constraints and 12 additional constraints given in the description of the
problem. The bias was initialized with 1200 binary constraints from the
language $\Gamma=\\{=,\neq,>,<,x_{i}-x_{j}=1,|x_{i}-x_{j}|=1\\}$.

Murder. Someone was murdered and there are 5 suspects, each one having an
item, an activity and a motive for the crime. The problem is to find the
murderer. This problem consists of 20 variables (the 5 suspects and their
items, activities and motives) with domains of size 5. The target network
contains 4 cliques of $\neq$ constraints and 12 additional binary constraints,
given as clues in the description of the problem. The bias was initialized
with 760 constraints based on the language $\Gamma=\\{=,\neq,>,<\\}$.

Purdey’s general store [32]. Four families stopped by Purdey’s general store,
each one aiming to buy a different item and paying in a different way. Under a
set of additional constraints given in the description of the problem, the
goal is to match each family with the item they bought and how they paid for
it. It has a single solution. It is modelled with 12 variables (for families,
items and paying methods), with domains of size 4. The target network consists
of 27 constraints. The bias was initialized with 264 constraints based on the
language $\Gamma=\\{=,\neq,>,<\\}$.

Allergy. A problem crafted by the XCSP team. There are 4 people having
allergies, and 8 products are given in the description of the problem. Based
on the constraints given, the goal is to find who has an allergy on which
product. It consists of 12 variables with domains of size 4 and 26
constraints. The bias was initialized with 264 constraints based on the
language $\Gamma=\\{=,\neq,>,<\\}$.

Golomb rulers. The problem is to find a ruler where the distance between any
two marks is different from that between any other two marks. We built a
simplified version of a Golomb ruler with 12 marks, with the target network
consisting only of quaternary constraints333The ternary constraints derived
when $i=k$ or $j=l$ in $|x_{i}-x_{j}|\neq|x_{k}-x_{l}|$ were excluded from the
target network. In total $C_{T}$ consists of 495 constraints. The bias was
created with the language
$\Gamma=\\{=,\neq,>,<,|x_{i}-x_{j}|=|x_{k}-x_{l}|,|x_{i}-x_{j}|\neq|x_{k}-x_{l}|\\}$,
including binary and quaternary constraints. In total $B$ contained 1254
constraints.

Exam Timetabling Problem (Exam TT). We used a simplified version of the exam
timetabling problem of the Department of Electrical and Computer Engineering
of the University of Western Macedonia, Greece. We considered 24 courses and 2
weeks of exams, meaning that there are 10 possible days for each course to be
assigned. We assumed that there are 3 timeslots available in each day. This
resulted in a model with 24 variables and domains of size 30. There are $\neq$
constraints between any two courses, assuming that only one course is examined
during each time slot, i.e. there is only one available room for examination.
Also, there exist constraints prohibiting courses of the same semester being
examined on the same day. As we assumed that there are 3 timeslots in each
day, the constraint preventing 2 courses of the same semester being in the
same day was modeled as $|\lfloor x_{i}/3\rfloor-\lfloor x_{j}/3\rfloor|>0$.
Hence, the language use was $\Gamma=\\{=,\neq,>,<,|\lfloor
x_{i}/3\rfloor-\lfloor x_{j}/3\rfloor|>y\\}$, with 5 different values for $y$.
This resulted in a bias of 3864 constraints.

Radio Link Frequency Assignment Problem. The RLFAP is the problem of providing
communication channels from limited spectral resources [22]. We use a
simplified version of the problem, which consists of 50 variables with domains
of size 40. The target network contains 125 binary distance constraints. We
built the bias using a language of 2 basic distance constraints
($\\{|x_{i}-x_{j}|>y,|x_{i}-x_{j}|=y\\}$) with 5 different possible values for
$y$. This led to a language of 10 different distance constraints. In total,
$B$ contained 12250 constraints.

In our experiments we measure the size of the learned network $C_{L}$, the
total number of queries $\\#q$, the average size $\bar{q}$ of all queries, the
number of complete queries $\\#q_{c}$, the average waiting time $\bar{T}$ (in
secs) for the user, the maximum waiting time $T_{max}$ (in secs) for the user,
the time $T_{queries}$ taken from the start of the process until the last
query and the total time needed (to converge) $T_{total}$. The difference
between $T_{total}$ and $T_{queries}$ is the time needed to prove convergence
or to reach premature convergence (because of the cutoffs). The size of
$C_{L}$ in some cases is smaller than the size of the target network $C_{T}$
due to the presence of redundant constraints that some methods learn and
others do not. In addition, we counted the times each method triggers any of
the two cutoffs.

We first demonstrate the performance of MQuAcq and FindScope-2 on these
benchmarks, compared to the existing methods (Section 9.1). Then in Section
9.2 we evaluate the proposed heuristics. In Section 9.3 we evaluate the effect
of the size of the bias on the performance of MQuAcq. Finally, in Section 9.4
we investigate our algorithm’s scalability.

###  9.1 MQuAcq and FindScope-2 evaluation

For the experiments presented here all the methods compared, including QuAcq
and MultiAcq, use the max heuristic (described in Section 7) for the query
generation step, with dom/wdeg for variable ordering and random value
ordering. In Table 4 we evaluate our proposed algorithm MQuAcq and the new
function FindScope-2 and we compare them against the existing methods. Hence,
we give results from QuAcq, MultiAcq, MQuAcq, QuAcq with FindScope-2 instead
of FindScope and MQuAcq with FindScope-2.

We do not present results from the RLFAP benchmark for MultiAcq, as it did not
manage to converge after running for 24 hours. This was due not only to its
linear complexity in terms of the number of queries, but also because the bias
contains many constraints in each possible scope and thus the condition at
line 2 of FindAllScopes does not help to avoid redundant searches. The other
algorithms also suffer from high cpu times, but only when they are trying to
generate queries near convergence. The large number of constraints in each
scope, and particularly the existence of constraints that are implied by other
constraints (e.g. $\\{|x_{i}-x_{j}|>y_{1}$ implies $\\{|x_{i}-x_{j}|>y_{2}$ if
$y_{1}>y_{2}$) can cause the appearance of a large number of constraints in
the bias that cannot be violated, resulting in high convergence times. A
similar problem is present in GTSudoku, again because of implied constraints
that appear in the bias. As we explain in Section 9.2, our proposed heuristics
from Section 8 can alleviate this problem.

Table 4: Results of MQuAcq and FindScope-2

Benchmark | Algorithm | $|C_{L}|$ | $\\#q$ | $\bar{q}$ | $\\#q_{c}$ | $\bar{T}$ | $T_{max}$ | $T_{queries}$ | $T_{total}$
---|---|---|---|---|---|---|---|---|---
| QuAcq | 648 | 11529 | 35 | 659 | 0.061 | 1.14 | 708.76 | 1529.78
| MultiAcq | 796 | 14508 | 10 | 39 | 0.071 | 36.76 | 1034.52 | 1119.69
| MQuAcq | 803 | 14935 | 26 | 37 | 0.010 | 20.49 | 154.47 | 194.57
|  QuAcq + FindScope-2 | 648 | 5960 | 43 | 659 | 0.119 | 1.15 | 710.57 | 1531.58
Sudoku |  MQuAcq + FindScope-2 | 801 | 6865 | 32 | 40 | 0.026 | 15.33 | 175.14 | 225.15
| QuAcq | 634 | 11325 | 35 | 649 | 0.82 | 1140.45 | 9235.54 | 11217.63
| MultiAcq | 747 | 16324 | 15 | 70 | 0.78 | 1383.72 | 12522.16 | 13917.67
| MQuAcq | 732 | 13912 | 26 | 45 | 0.40 | 905.68 | 5564.73 | 6959.69
|  QuAcq + FindScope-2 | 636 | 5950 | 42 | 653 | 1.51 | 1582.52 | 8987.09 | 10920.54
GTSudoku |  MQuAcq + FindScope-2 | 742 | 6663 | 31 | 52 | 0.86 | 970.77 | 5720.09 | 7003.27
| QuAcq | 855 | 15489 | 46 | 870 | 0.066 | 10.17 | 1020.83 | 1251.22
| MultiAcq | 899 | 21079 | 11 | 52 | 0.163 | 20.27 | 3429.16 | 3439.18
| MQuAcq | 899 | 17842 | 37 | 49 | 0.010 | 5.23 | 171.75 | 181.77
|  QuAcq + FindScope-2 | 855 | 8115 | 55 | 873 | 0.127 | 10.15 | 1028.85 | 1259.23
Latin |  MQuAcq + FindScope-2 | 899 | 8228 | 46 | 50 | 0.023 | 10.30 | 189.34 | 199.38
| QuAcq | 60 | 775 | 11 | 60 | 0.069 | 1.03 | 53.68 | 53.69
| MultiAcq | 57 | 975 | 6 | 8 | 0.264 | 127.62 | 257.77 | 257.78
| MQuAcq | 59 | 783 | 8 | 8 | 0.006 | 1.03 | 4.37 | 4.37
|  QuAcq + FindScope-2 | 60 | 496 | 12 | 60 | 0.109 | 1.03 | 54.08 | 54.03
Zebra |  MQuAcq + FindScope-2 | 59 | 469 | 10 | 7 | 0.009 | 1.03 | 4.08 | 4.09
| QuAcq | 52 | 599 | 9 | 52 | 0.085 | 1.01 | 51.16 | 51.48
| MultiAcq | 52 | 704 | 5 | 8 | 0.025 | 3.65 | 17.34 | 17.65
| MQuAcq | 52 | 619 | 6 | 8 | 0.012 | 1.01 | 7.28 | 7.75
|  QuAcq + FindScope-2 | 52 | 356 | 10 | 52 | 0.144 | 1.01 | 51.31 | 51.63
Murder |  MQuAcq + FindScope-2 | 52 | 374 | 8 | 7 | 0.028 | 1.01 | 6.56 | 6.89
| QuAcq | 26 | 282 | 5 | 26 | 0.07 | 1.00 | 19.15 | 19.16
| MultiAcq | 27 | 234 | 4 | 5 | 0.01 | 1.01 | 2.21 | 2.22
| MQuAcq | 26 | 269 | 4 | 5 | 0.01 | 1.00 | 2.06 | 2.08
|  QuAcq + FindScope-2 | 26 | 170 | 6 | 26 | 0.11 | 1.00 | 19.23 | 19.25
Purdey |  MQuAcq + FindScope-2 | 26 | 149 | 5 | 5 | 0.01 | 1.00 | 2.13 | 2.14
| QuAcq | 26 | 283 | 5 | 26 | 0.06 | 1.00 | 17.83 | 17.85
| MultiAcq | 26 | 226 | 4 | 4.8 | 0.01 | 1.00 | 2.16 | 2.18
| MQuAcq | 26 | 267 | 4 | 5 | 0.01 | 1.00 | 1.94 | 2.06
|  QuAcq + FindScope-2 | 26 | 169 | 6 | 26 | 0.11 | 1.00 | 17.87 | 17.88
Allergy |  MQuAcq + FindScope-2 | 26 | 151 | 4 | 5 | 0.01 | 1.00 | 2.11 | 2.11
| QuAcq | 495 | 7585 | 6 | 496 | 0.069 | 1.17 | 525.98 | 526.08
| MultiAcq | 495 | 2368 | 6 | 64 | 0.029 | 1.18 | 68.82 | 68.92
| MQuAcq | 495 | 6350 | 5 | 72 | 0.012 | 1.18 | 78.76 | 78.86
|  QuAcq + FindScope-2 | 495 | 1552 | 9 | 496 | 0.338 | 1.18 | 524.97 | 525.07
Golomb-12 |  MQuAcq + FindScope-2 | 495 | 961 | 8 | 69 | 0.082 | 3.87 | 79.10 | 79.20
| QuAcq | 276 | 3856 | 11 | 277 | 0.07 | 1.14 | 281.11 | 576.17
| MultiAcq | 276 | 3086 | 7 | 35 | 0.73 | 341.76 | 2264.81 | 2553.40
| MQuAcq | 276 | 3747 | 9 | 36 | 0.08 | 126.13 | 311.70 | 592.94
|  QuAcq + FindScope-2 | 276 | 1451 | 14 | 277 | 0.19 | 1.04 | 281.66 | 576.86
Exam TT |  MQuAcq + FindScope-2 | 276 | 1222 | 11 | 36 | 0.24 | 100.57 | 296.69 | 584.93
| QuAcq | 102 | 1705 | 26 | 166 | 3.657 | 890.60 | 6,235.19 | 7,513.17
| MultiAcq | - | - | - | - | - | - | - | -
| MQuAcq | 122 | 2492 | 24 | 107 | 2.067 | 933.00 | 5,150.23 | 6,308.14
|  QuAcq + FindScope-2 | 102 | 1096 | 29 | 167 | 6.163 | 896.26 | 6,755.14 | 7,629.21
RLFAP |  MQuAcq + FindScope-2 | 122 | 1442 | 25 | 107 | 3.380 | 932.00 | 4,873.96 | 6,204.14

Looking at the performance of MQuAcq, and comparing it to QuAcq, we observe
that the use of FindAllCons to learn all the violated constraints from a
negative example reduces significantly the average waiting time per query for
the user and the total time of the execution in all benchmarks except RLFAP
and GTSudoku (due to the nature of the problems, as mentioned above), where
the time needed is still reduced but only by a little. Also, in Exam TT, QuAcq
and MQuAcq have similar performance in terms of average time and total time.
This is because although MQuAcq learns faster most of the constraints, it
needs a lot more time for the generation of the last queries, due to the
structure of the problem, as several constraints from the target network not
learned yet (i.e. they are still in the bias) are difficult to be violated
when the learned network is satisfied. This is confirmed by considering the
maximum time that the user had to wait for a query to be generated and posted.

Regarding the rest of the problems, QuAcq is 8 times slower than MQuAcq in
Sudoku and Allergy, 7 times in Latin square, 12 times in Zebra, 9 times in
Purdey, and 6.5 times in Murder and Golomb rulers. This is due to the fewer
generations of new examples in line 5 of MQuAcq, because the algorithm is able
to learn a maximum number of violated constraints from each negative example.
This is validated by looking at column $\\#q_{c}$, which shows that far fewer
complete queries are generated. As a downside, MQuAcq requires more queries in
total than QuAcq to converge in most cases, and the difference is more evident
on Sudoku, GTSudoku and Latin. However, as we can see on these problems MQuAcq
learns a greater number of constraints of the target network than QuAcq, and
the average size of the queries posted by MQuAcq is smaller. Also, we can
observe that in Golomb rulers, which contains quaternary constraints, the
queries posted to the user by MQuAcq were fewer.

Comparing MQuAcq to MultiAcq, it is clear that the redundant searches made by
MultiAcq greatly affect the average time per query and total time needed for
the system to converge. MQuAcq needs far less time to ask a query to the user,
and requires posting fewer queries to converge, on most problems. On the other
hand, on Golomb Rulers, MultiAcq displays better performance both in number of
queries and in total time. This can be explained as FindScope, that is used by
MQuAcq, posts a lot of redundant queries to the user and also the problem
consists of only 12 variables, so the branching of MultiAcq is not very time-
consuming.

Focusing on FindScope-2 when used inside QuAcq, we can see that the number of
queries posted to the user were significantly lower compared to standard QuAcq
with FindScope, because the former avoids asking several redundant queries. In
terms of the number of queries, FindScope-2 gives a gain of $35\%$ on the
RLFAP problem, $36\%$ on the Zebra problem, $40\%$ on Murder, Purdey and
Allergy, $48\%$ on Sudoku, GTSudoku and Latin square, $62\%$ on Exam TT and up
to $80\%$ on Golomb Rulers. Interestingly, it seems that the more variables
are present in a problem, the bigger is the gain in avoided queries. As a
downside, FindScope-2 increases the average waiting time between the queries,
but not the total time required to converge. The average time is increased
simply because some queries are not posted because they would be redundant. In
addition, as we can observe from the results from Golomb Rulers, the reduction
in the number of queries in problems with higher arity constraints is even
bigger.

The results obtained from MQuAcq with FindScope-2 show that the use of
FindScope-2 has the same effect on MQuAcq as on QuAcq, cutting down the number
of queries significantly, from $40\%$ (in Murder) up to $85\%$ (in Golomb).
Comparing to MultiAcq, now the number of queries posted to the user is
considerable lower, from $33\%$ (in Allergy) up to $61\%$ (in Latin squares).

Regarding the cutoffs, neither of the two cutoffs was triggered by any method
on Zebra, Murder, Purdey, Allergy and Golomb. On Sudoku, QuAcq (resp.
MultiAcq) triggered the first cutoff 2 (resp. 3) times on average and the
second 170 (resp. 26) times. On Latin squares these numbers were 9 and 46 for
QuAcq and 16 and 19 for MultiAcq. MQuAcq triggered the first cutoff 5 times on
average on Sudoku and the second also 5 times. On Latin square these numbers
were 11 and 5 respectively. Given that the triggering of the cutoffs is
associated with the problem of premature convergence, as we explain at the end
of Section 4, the lower numbers for MQuAcq indicate that it is less likely to
terminate with premature convergence. On the other hand, on Exam TT, QuAcq
triggered the first cutoff only once, while MQuAcq and MultiAcq triggered it 5
times. The second cutoff was triggered 57 times from QuAcq, 98 times from
MultiAcq and 104 from MQuAcq. On RLFAP and GTSudoku, the cutoffs were
triggered too many times due to the reasons explained above. On average, QuAcq
triggered the first cutoff 21 times and the second 1444 times on RLFAP (resp.
98 and 1757 on GTSudoku). The corresponding numbers for MQuAcq were 20 and
1195 on RLFAP (resp. 17 and 1356 on GTSudoku). MultiAcq triggered the first
cutoff 27 times and the second 2598 times on GTSudoku.

In the remainder of the experimental evaluation we will compare our methods
only against QuAcq, as it is clear that learning a maximum number of
constraints from each generated query using MQuAcq is more efficient than with
MultiAcq. Also, we will present the results of both QuAcq and MQuAcq with the
use FindScope-2 instead of FindScope.

###  9.2 Evaluation of heuristics

In this section we first evaluate the heuristic maxB for the query generation
step in tandem with bdeg for variable ordering. Next, we focus on the
performance of the proposed value ordering heuristic.

####  9.2.1 maxB for the query generation step

Recall that the objective of the maxB heuristic is to find a (partial)
assignment that maximizes the number of violated constraints from $B$ instead
of focusing on finding a complete solution of $C_{L}$ as max does. Hence, if
maxB is used to generate queries, the variable ordering heuristic should
comply with this objective. Our intuition behind the proposed variable
ordering heuristic bdeg is that standard heuristics like dom/wdeg are not
suitable for use in conjunction with maxB. On the other hand, such heuristics
are better suited to be used in tandem with max whose objective is to find a
complete solution of $C_{L}$ quickly.

We use Sudoku as a sample problem to confirm the above assumptions. In Figures
2 and 3 we report the cpu time performance of the QuAcq and MQuAcq algorithms
using max and maxB with bdeg and dom/wdeg. In all cases we use random value
ordering. Specifically, the figures depict the cpu time required by each
combination of heuristics to learn an increasing portion of the target network
(the x-axis gives the number of constraints learned).

The results confirm our intuition. When max is used for query generation
within QuAcq (Figure 2a), the algorithm is by far faster with dom/wdeg
compared to bdeg. In contrast, when maxB is used (Figure 2b) then the choice
of variable ordering heuristic does not affect the run time initially, but as
convergence is approached, bdeg speeds up the process considerably because
dom/wdeg takes too long to generate the last few queries compared to bdeg
which finds partial assignments really fast. Considering MQuAcq, when max is
used (Figure 3a), bdeg is slightly faster initially, but is outperformed by
dom/wdeg near convergence. On the other hand, when maxB is used (Figure 3b),
bdeg and dom/wdeg are very close initially, but the former is again faster
near convergence.

(a)

(b)

Figure 2: QuAcq using max and maxB with bdeg and dom/wdeg in the Sudoku
problem

(a)

(b)

Figure 3: MQuAcq using max and maxB with bdeg and dom/wdeg in the Sudoku
problem

For a closer look at the difference between bdeg and dom/wdeg near
convergence, Figure 4 displays the number of constraints from $B$ that are
violated (y-axis) during each of the last 20 generated queries (x-axis). This
data was obtained by applying MQuAcq with maxB on the Sudoku benchmark. It is
clear that bdeg, as a heuristic that orders the variables with information
obtained from $B$, violates considerably more constraints than dom/wdeg.
Hence, the queries generated using bdeg are more “informative”, which explains
its good performance near convergence when used in tandem with maxB.

Figure 4: Number of constraints from the Bias that are violated when MQuAcq
generates the last 20 queries in Sudoku.

To summarize, we have established that the use of maxB to generate queries
requires the use of bdeg for variable ordering in order to maximize the
performance of the acquisition algorithm, while if max is used to generate
queries then dom/wdeg is a better option. We now compare these two strategies
on all the considered benchmarks.

Table 5 displays the performance of maxB (with bdeg) when used inside QuAcq
and MQuAcq compared to max (with dom/wdeg). We can see that on small problems
(Zebra, Murder, Purdey, Allergy and Golomb) maxB has similar performance to
max. This is because such problems have only a few variables, meaning that in
most cases both maxB and max can find complete solutions to $C_{L}$ that
violate many constraints in $B$ within the time limit.

Table 5: Comparing maxB to max.

Benchmark | Algorithm | $|C_{L}|$ | $\\#q$ | $\bar{q}$ | $\\#q_{c}$ | $\bar{T}$ | $T_{max}$ | $T_{queries}$ | $T_{total}$
---|---|---|---|---|---|---|---|---|---
|  QuAcq max | 648 | 5960 | 43 | 659 | 0.119 | 1.15 | 710.57 | 1531.58
|  MQuAcq max | 801 | 6865 | 32 | 40 | 0.026 | 15.33 | 175.14 | 225.15
|  QuAcq maxB | 810 | 6657 | 38 | 510 | 0.131 | 1.15 | 869.67 | 869.68
Sudoku |  MQuAcq maxB | 810 | 6858 | 32 | 14 | 0.015 | 1.12 | 104.89 | 104.90
|  QuAcq max | 636 | 5950 | 42 | 653 | 1.51 | 1582.52 | 8987.09 | 10920.54
|  MQuAcq max | 742 | 6663 | 31 | 52 | 0.86 | 970.77 | 5720.09 | 7003.27
|  QuAcq maxB | 786 | 6493 | 24 | 278 | 0.19 | 5.37 | 1216.01 | 1219.98
GTSudoku |  MQuAcq maxB | 787 | 6813 | 29 | 12 | 0.11 | 5.28 | 735.99 | 738.67
|  QuAcq max | 855 | 8115 | 55 | 873 | 0.127 | 10.15 | 1028.85 | 1259.23
|  MQuAcq max | 899 | 8228 | 46 | 50 | 0.023 | 10.30 | 189.34 | 199.38
|  QuAcq maxB | 900 | 7946 | 54 | 793 | 0.126 | 1.19 | 999.17 | 999.18
Latin |  MQuAcq maxB | 900 | 8411 | 46 | 17 | 0.017 | 1.16 | 142.85 | 142.86
|  QuAcq max | 60 | 496 | 12 | 60 | 0.109 | 1.03 | 54.08 | 54.03
|  MQuAcq max | 59 | 469 | 10 | 7 | 0.009 | 1.03 | 4.08 | 4.09
|  QuAcq maxB | 60 | 481 | 12 | 56 | 0.110 | 1.03 | 52.84 | 52.84
Zebra |  MQuAcq maxB | 60 | 480 | 10 | 6 | 0.009 | 1.03 | 4.53 | 4.54
|  QuAcq max | 52 | 356 | 10 | 52 | 0.144 | 1.01 | 51.31 | 51.63
|  MQuAcq max | 52 | 374 | 8 | 7 | 0.028 | 1.01 | 6.56 | 6.89
|  QuAcq maxB | 52 | 370 | 10 | 47 | 0.136 | 1.01 | 50.23 | 50.44
Murder |  MQuAcq maxB | 52 | 357 | 8 | 4 | 0.019 | 1.01 | 6.82 | 7.07
|  QuAcq max | 26 | 170 | 6 | 26 | 0.11 | 1.00 | 19.23 | 19.25
|  MQuAcq max | 26 | 149 | 5 | 5 | 0.01 | 1.00 | 2.13 | 2.14
|  QuAcq maxB | 26 | 171 | 6 | 23 | 0.12 | 1.00 | 20.13 | 20.13
Purdey |  MQuAcq maxB | 26 | 152 | 5 | 3 | 0.02 | 1.00 | 2.29 | 2.30
|  QuAcq max | 26 | 169 | 6 | 26 | 0.11 | 1.00 | 17.87 | 17.88
|  MQuAcq max | 26 | 151 | 4 | 5 | 0.01 | 1.00 | 2.11 | 2.11
|  QuAcq maxB | 26 | 169 | 6 | 23 | 0.12 | 1.00 | 19.46 | 19.47
Allergy |  MQuAcq maxB | 26 | 150 | 4 | 3 | 0.01 | 1.00 | 2.13 | 2.13
|  QuAcq max | 495 | 1552 | 9 | 496 | 0.338 | 1.18 | 524.97 | 525.07
|  MQuAcq max | 495 | 961 | 8 | 69 | 0.082 | 3.87 | 79.10 | 79.20
|  QuAcq maxB | 495 | 1789 | 9 | 438 | 0.294 | 1.19 | 526.77 | 526.89
Golomb-12 |  MQuAcq maxB | 495 | 970 | 8 | 49 | 0.086 | 1.18 | 83.00 | 83.12
|  QuAcq max | 276 | 1451 | 14 | 277 | 0.19 | 1.04 | 281.66 | 576.86
|  MQuAcq max | 276 | 1222 | 11 | 36 | 0.24 | 100.57 | 296.69 | 584.93
|  QuAcq maxB | 276 | 1468 | 13 | 230 | 0.22 | 6.06 | 316.19 | 321.32
Exam TT |  MQuAcq maxB | 276 | 1237 | 11 | 14 | 0.08 | 5.90 | 94.04 | 100.56
|  QuAcq max | 102 | 1096 | 29 | 167 | 6.163 | 896.26 | 6,755.14 | 7,629.21
|  MQuAcq max | 122 | 1442 | 25 | 107 | 3.380 | 932.00 | 4,873.96 | 6,204.14
|  QuAcq maxB | 106 | 1094 | 26 | 77 | 0.242 | 6.63 | 264.62 | 268.32
RLFAP |  MQuAcq maxB | 124 | 1445 | 24 | 25 | 0.115 | 6.55 | 165.76 | 173.90

On the other hand, on the bigger and harder problems (Sudoku, GTSudoku, Latin,
Exam TT and RLFAP) the average and maximum time per query of both QuAcq and
MQuAcq are all reduced when maxB is used, and so is the number of complete
queries posted to the user. Also, the differences in the maximum time per
query are quite large. Another observation is that for both QuAcq and MQuAcq,
as column $|C_{L}|$ demonstrates, the use of maxB helps to not only learn the
complete target network, but also redundant constraints. Inadvertently, this
results in more queries being asked in some cases and greater $T_{queries}$
(e.g. QuAcq in Sudoku). On the other hand $T_{total}$ is significantly
reduced. We can see that the use of maxB in QuAcq (resp. in MQuAcq) reduces
the total time by $43\%$ ($53\%$) in Sudoku, $89\%$ ($89\%$) in GTSudoku,
$20\%$ ($24\%$) in Latin, $44\%$ ($83\%$) in Exam TT and $96\%$ ($97\%$) in
RLFAP.

These gains in average time per query and total cpu time can be explained
because in Sudoku and Latin, any method that used maxB never triggered any
cutoff, meaning that an irredundant query was always found in time.
Accordingly, in GTSudoku, Exam TT and RLFAP, when max is used the cutoffs are
triggered too many times, resulting in very high cpu times. On the other hand,
when maxB is used, the second cutoff was never triggered in any of these
problems while the first cutoff was triggered in average 40 times by QuAcq and
53 times by MQuAcq in GTSudoku only 7 times by both QuAcq and MQuAcq in EXAM
TT and 15 times by QuAcq and 11 times by MQuAcq on RLFAP.

An issue that is not clearly visible from the data in the table is that of
premature convergence. The difference between $T_{total}$ and $T_{queries}$ is
in fact the time needed to reach (premature) convergence, because of the
cutoffs. In general, the use of maxB alleviates the problem of premature
convergence, as in all the benchmarks both the algorithms proved convergence
because having learned the redundant constraints during the process, $B$ is
empty in the end, and therefore the system does not have to prove that no
solution of $C_{L}$ violates them.

####  9.2.2 maxv for value ordering

Now, let us focus on the use of the maxv value ordering heuristic. Table 6
illustrates the results obtained using random and maxv for value ordering
alongside bdeg for variable ordering, in tandem with maxB.

Table 6: Comparing random value ordering to maxv.

Benchmark | Algorithm | $|C_{L}|$ | $\\#q$ | $\bar{q}$ | $\\#q_{c}$ | $\bar{T}$ | $T_{max}$ | $T_{queries}$ | $T_{total}$
---|---|---|---|---|---|---|---|---|---
|  QuAcq rand | 810 | 6657 | 38 | 510 | 0.131 | 1.15 | 869.67 | 869.68
|  MQuAcq rand | 810 | 6858 | 32 | 14 | 0.015 | 1.12 | 104.89 | 104.90
|  QuAcq maxv | 810 | 7074 | 37 | 555 | 0.123 | 1.14 | 868.22 | 868.23
Sudoku |  MQuAcq maxv | 810 | 5101 | 4 | 3 | 0.215 | 1.30 | 1,095.18 | 1,095.20
|  QuAcq rand | 786 | 6493 | 24 | 278 | 0.19 | 5.37 | 1216.01 | 1219.98
|  MQuAcq rand | 787 | 6813 | 29 | 12 | 0.11 | 5.28 | 735.99 | 738.67
|  QuAcq maxv | 776 | 6598 | 23 | 259 | 0.18 | 5.37 | 1217.91 | 1223.17
GTSudoku |  MQuAcq maxv | 810 | 5144 | 4 | 2 | 0.29 | 5.18 | 1481.40 | 1486.71
|  QuAcq rand | 900 | 7946 | 54 | 793 | 0.126 | 1.19 | 999.17 | 999.18
|  MQuAcq rand | 900 | 8411 | 46 | 17 | 0.017 | 1.16 | 142.85 | 142.86
|  QuAcq maxv | 900 | 8309 | 51 | 817 | 0.120 | 1.20 | 996.92 | 996.93
Latin |  MQuAcq maxv | 900 | 6968 | 4 | 3 | 0.356 | 1.84 | 2,478.57 | 2,478.58
|  QuAcq rand | 60 | 481 | 12 | 56 | 0.110 | 1.03 | 52.84 | 52.84
|  MQuAcq rand | 60 | 480 | 10 | 6 | 0.009 | 1.03 | 4.53 | 4.54
|  QuAcq maxv | 60 | 494 | 12 | 59 | 0.112 | 1.03 | 55.21 | 55.21
Zebra |  MQuAcq maxv | 61 | 491 | 6 | 3 | 0.008 | 1.03 | 3.69 | 3.69
|  QuAcq rand | 52 | 370 | 10 | 47 | 0.136 | 1.01 | 50.23 | 50.44
|  MQuAcq rand | 52 | 357 | 8 | 4 | 0.019 | 1.01 | 6.82 | 7.07
|  QuAcq maxv | 52 | 367 | 10 | 49 | 0.138 | 1.01 | 50.76 | 51.00
Murder |  MQuAcq maxv | 52 | 365 | 4 | 3 | 0.007 | 1.01 | 2.67 | 2.67
|  QuAcq rand | 26 | 171 | 6 | 23 | 0.12 | 1.00 | 20.13 | 20.13
|  MQuAcq rand | 26 | 152 | 5 | 3 | 0.02 | 1.00 | 2.29 | 2.30
|  QuAcq maxv | 26 | 169 | 6 | 23 | 0.12 | 1.00 | 20.39 | 20.40
Purdey |  MQuAcq maxv | 27 | 146 | 3 | 2 | 0.01 | 1.00 | 1.66 | 1.66
|  QuAcq rand | 26 | 169 | 6 | 23 | 0.12 | 1.00 | 19.46 | 19.47
|  MQuAcq rand | 26 | 150 | 4 | 3 | 0.01 | 1.00 | 1.85 | 1.89
|  QuAcq maxv | 26 | 176 | 6 | 24 | 0.11 | 1.00 | 19.87 | 19.88
Allergy |  MQuAcq maxv | 26 | 149 | 3 | 3 | 0.01 | 1.00 | 1.72 | 1.72
|  QuAcq rand | 495 | 1789 | 9 | 438 | 0.294 | 1.19 | 526.77 | 526.89
|  MQuAcq rand | 495 | 970 | 8 | 49 | 0.086 | 1.18 | 83.00 | 83.12
|  QuAcq maxv | 495 | 1740 | 9 | 473 | 0.306 | 3.26 | 532.96 | 533.06
Golomb-12 |  MQuAcq maxv | 495 | 567 | 3 | 2 | 0.109 | 1.25 | 61.78 | 61.87
|  QuAcq rand | 276 | 1468 | 13 | 230 | 0.22 | 6.06 | 316.19 | 321.32
|  MQuAcq rand | 276 | 1237 | 11 | 14 | 0.08 | 5.90 | 94.04 | 100.56
|  QuAcq maxv | 276 | 1808 | 13 | 277 | 0.16 | 2.99 | 285.23 | 293.84
Exam TT |  MQuAcq maxv | 276 | 1268 | 7 | 14 | 0.01 | 1.05 | 18.06 | 29.16
|  QuAcq rand | 106 | 1094 | 26 | 77 | 0.242 | 6.63 | 264.62 | 268.32
|  MQuAcq rand | 124 | 1445 | 24 | 25 | 0.115 | 6.55 | 165.76 | 173.90
|  QuAcq maxv | 108 | 1073 | 23 | 91 | 0.152 | 8.00 | 163.33 | 170.04
RLFAP |  MQuAcq maxv | 123 | 1377 | 9 | 1 | 0.042 | 7.63 | 57.12 | 70.43

Comparing against the results of random value ordering, we can see that the
use of maxv does not affect the results of QuAcq significantly in terms of cpu
time, but it has a negative effect on the number of queries required for the
larger problems. This is because QuAcq does not use all the information
included in each generated query, learning only one violated constraint.

With respect to MQuAcq, we observe that in RLFAP, Exam TT, Zebra and Murder,
which include a small number of variables, the use of maxv reduces the total
time and the average time per query (up to $70\%$ in Exam TT). In addition, in
Golomb rulers the number of queries is reduced significantly ($42\%$) and the
total time of the acquisition process is also reduced. In Purdey and Allergy,
which are the smallest problems, there is no difference. In contrast, in the
other three benchmarks, which have a much larger $C_{T}$ (810 for Sudoku and
GTSudoku and 900 for Latin), we observe that although the number of queries
posted to the user is considerably reduced (by $25\%$ for Sudoku and GTSudoku
and $17.2\%$ for Latin), the total time of the acquisition process and the
average time per query are one order of magnitude higher compared to random
value ordering. However, it can be seen that the maximum time the user has to
wait for a query is not much higher. The total time and the average time per
query are increased because of the branching that FindAllCons performs.
Another observation is that the use of maxv significantly reduces the average
size per query as well as the number of complete queries posted to the user.

For a closer look at the behaviour of QuAcq and MQuAcq with different value
ordering heuristics for query generation, we evaluated their performance in
terms of the time elapsed and the size of the learned network $C_{L}$ in
relation to the number of queries posted to the user. Figures 5 and 6
illustrate the performance of the two algorithm on Sudoku and Latin when using
random value ordering, while Figures 7 and 8 illustrate their performance when
using maxv for value ordering.

(a)

(b)

Figure 5: The behaviour of QuAcq and MQuAcq in Sudoku, using the maxB
heuristic, bdeg for variable ordering and random value ordering.

(a)

(b)

Figure 6: The behaviour of QuAcq and MQuAcq in Latin, using the maxB
heuristic, bdeg for variable ordering and random value ordering.

(a)

(b)

Figure 7: The behaviour of QuAcq and MQuAcq in Sudoku, using the maxB
heuristic, bdeg for variable ordering and maxv for value ordering.

(a)

(b)

Figure 8: The behaviour of QuAcq and MQuAcq in Latin, using the maxB
heuristic, bdeg for variable ordering and maxv for value ordering.

In Figures 5 and 6 we can observe that using random value ordering QuAcq needs
fewer queries to learn a higher proportion of the target network than MQuAcq.
In contrast, MQuAcq needs far less time as it learns all the violated
constraints from the target network from each generated query. When using maxv
for value ordering, these results are reversed (Figures 7 and 8). That is,
MQuAcq takes more time than QuAcq as the process unfolds, but it requires
fewer queries to learn the target network. This reversal occurs because with
the maxv heuristic MQuAcq can acquire more information (i.e. more constraints)
from each generated query. This leads to fewer queries but at the same time it
needs more time due to the branching of FindAllCons as explained before.

A generic remark we can make regarding the value ordering heuristic in MQuAcq
is that it can be selected depending on which metric of the constraint
acquisition process is viewed as critical. If the only important factors are
the number of queries posted to the user and the size of the queries, the maxv
heuristic is a better option than random ordering. This is often the case when
the user is human. On the other hand, if speeding up the acquisition process
is more important, random value ordering should be preferred. This can occur
in cases where the user is an existing software system. Concerning QuAcq, we
can see that maxv does not improve the acquisition process in any metric. On
the contrary, it increases the number of queries, as locating the scope of a
violated constraint can end up in a lot small positive queries.

###  9.3 The effect of the size of the bias

We evaluated the effect of the size of the bias on MQuAcq, in terms of the
number of queries posted and the time needed to converge. We used the
constraint relations needed for each problem and increased the size of the
bias progressively using the language
$\\{=,\neq,>,<,\leq,\geq,x_{i}-x_{j}=1,|x_{i}-x_{j}|=1,|x_{i}-x_{j}|>y,|x_{i}-x_{j}|=y,|\lfloor
x_{i}/3\rfloor-\lfloor x_{j}/3\rfloor|>y\\}$. We used ExamTT (Figure 9), Latin
(Figure 10), Sudoku (Figure 11) and Golomb (Figure 12) to evaluate the effect
of the bias’ size in different problems.

(a)

(b)

Figure 9: Performance of MQuAcq in Exam Timetabling with bias of different
sizes.

(a)

(b)

Figure 10: Performance of MQuAcq in Latin squares with bias of different
sizes.

(a)

(b)

Figure 11: Performance of MQuAcq in Sudoku with bias of different sizes.

(a)

(b)

Figure 12: Performance of MQuAcq in Golomb rulers with bias of different
sizes.

Looking at the effect of the bias on the number of queries, we can observe
that it does not affect it considerably. In all the benchmarks, the number of
queries increases logarithmically as the size of the bias is increased. This
is more visible in Latin and Sudoku, where the increase in the bias size is
larger, because of the larger number of variables in these benchmarks. These
results agree with the corresponding results given in [12]. The increase in
the number of queries is very mild because although in the worst case each
positive query will remove only one constraint from $B$ (in which case the
increase in the number of queries would be substantial), in practice, each
positive query removes several constraints from $B$, even in the same scope.
Thus, as the number of constraints in $B$ increases, so does the average
number of constraints removed by each positive query, resulting in a mild