Efficient multiple constraint acquisition

DOI10.1007/S10601-020-09311-4zbMATH Open1483.90067arXiv2109.05920OpenAlexW3199018259MaRDI QIDQ823769FDOQ823769

Authors: Dimosthenis C. Tsouros, Kostas Stergiou 

Publication date: 16 December 2021

Published in: Constraints (Search for Journal in Brave)

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. %We also present a technique that boosts the performance of constraint acquisition by reducing the number of queries significantly. Then we turn our attention to query generation which is a significant but rather overlooked part of the acquisition process. We describe %in detail 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.

Full work available at URL: https://arxiv.org/abs/2109.05920

Recommendations

• Constraint acquisition
• Time-bounded query generator for constraint acquisition
• Classifier-based constraint acquisition
• Principles and Practice of Constraint Programming – CP 2004
• From eager or lazy constrained data acquisition: A general framework

zbMATH Keywords

learningmodelingconstraint acquisition

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50)

Cites Work

• Learning conjunctions of Horn clauses
• Queries and concept learning
• Exact learning Boolean functions via the monotone theory
• Fast learning of \(k\)-term DNF formulas with queries.
• Radio link frequency assignment
• The approximability of constraint satisfaction problems
• Asking questions to minimize errors
• Constraint acquisition
• Principles and Practice of Constraint Programming – CP 2004
• Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle
• On learning from queries and counterexamples in the presence of noise
• Malicious omissions and errors in answers to membership queries
• Progress towards the Holy Grail
• Time-bounded query generator for constraint acquisition
• Learning with errors in answers to membership queries
• Exact learning from an honest teacher that answers membership queries

Cited In (5)

• Learning constraints through partial queries
• Title not available (Why is that?)
• From eager or lazy constrained data acquisition: A general framework
• Constraint acquisition
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Efficient multiple constraint acquisition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q823769)