Learning to Learn in Interactive Constraint Acquisition
Dimos Tsouros Senne Berden Tias Guns
Constraint Programming (CP) has been successfully used to model and solve
complex combinatorial problems. However, modeling is often not trivial and
requires expertise, which is a bottleneck to wider adoption. In Constraint
Acquisition (CA), the goal is to assist the user by automatically learning the
model. In (inter)active CA, this is done by interactively posting queries to
the user, e.g., asking whether a partial solution satisfies their (unspecified)
constraints or not. While interac tive CA methods learn the constraints, the
learning is related to symbolic concept learning, as the goal is to learn an
exact representation. However, a large number of queries is still required to
learn the model, which is a major limitation. In this paper, we aim to
alleviate this limitation by tightening the connection of CA and Machine
Learning (ML), by, for the first time in interactive CA, exploiting statistical
ML methods. We propose to use probabilistic classification models to guide
interactive CA to generate more promising queries. We discuss how to train
classifiers to predict whether a candidate expression from the bias is a
constraint of the problem or not, using both relation-based and scope-based
features. We then show how the predictions can be used in all layers of
interactive CA: the query generation, the scope finding, and the lowest-level
constraint finding. We experimentally evaluate our proposed methods using
different classifiers and show that our methods greatly outperform the state of
the art, decreasing the number of queries needed to converge by up to 72%.