Machine Learning-Guided Interactive Constraint Acquisition

Abstract

Background: 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 of CP. As a result, the field of Constraint Acquisition (CA) has emerged with the aim to (semi-)automate the modeling process. In 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.

Objectives: However, a large number of queries is required to learn the model, which is a major limitation of state-of-the-art CA, especially for human users. We believe this is due to the search-based learning of interactive CA, which is based on symbolic concept learning, being mostly uninformed. During learning, the system is not aware of any patterns that may appear in the constraints acquired so far, which could be used to guide the rest of the process.

Methods: In this paper, we aim to alleviate this limitation by, for the first time, utilizing statistical Machine Learning (ML) in the context of interactive CA. We propose to use probabilistic classification models to guide interactive CA to generate more informative queries. Specifically, we propose a probability-based objective function to use in the query generation process across all components of interactive CA: the top-level query generation, the scope finding, and the lowest-level constraint finding. To ease the guiding of the scope-finding process, we also propose a novel FindScope function, which includes an explicit query generation step. Effective guidance, however, relies on (probabilistic) estimates of whether candidate expressions belong to the problem or not. To this end, we propose a framework for the training of ML classifiers within the interactive CA process, as well as an expressive feature representation of constraints.

Results: We experimentally evaluate our proposed methods on 7 different problem classes, using different classifiers and feature representations, and show that our methods greatly outperform the state of the art, decreasing the number of queries needed to converge by up to 75%.

Conclusions: Our findings confirm that statistical ML methods can detect patterns in constraint models, while they are being learned, and can be successfully used within the search-based interactive CA for reducing the number of queries needed.