Efficient multiple constraint acquisition
- PDF / 3,017,115 Bytes
- 46 Pages / 439.642 x 666.49 pts Page_size
- 79 Downloads / 204 Views
Efficient multiple constraint acquisition Dimosthenis C. Tsouros1
· Kostas Stergiou1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
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. Keywords Constraint acquisition · Learning · Modeling
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 This paper is an extended version of paper [1] that appeared in the proceedings of CP-2018. Dimosthenis C. Tsouros
[email protected] Kostas Stergiou [email protected] 1
Dept. of Electrical & Computer Engineering, University of Western Macedonia, Kozani, Greece
Constraints
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 [2]. 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 [2–7]. 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
Data Loading...
