Skip to Main content Skip to Navigation
Conference papers

Omissions in Constraint Acquisition

Dimosthenis Tsouros 1 Kostas Stergiou 1 Christian Bessière 2
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Interactive constraint acquisition is a special case of query-directed learning, also known as "exact" learning. It is used to assist non-expert users in modeling a constraint problem automatically by posting examples to the user that have to be classified as solutions or non-solutions. One significant issue that has not been addressed in the literature of constraint acquisition is the possible presence of uncertainty in the answers of the users. We address this by introducing Limited Membership Queries, where the user has the option of replying "I don't know", corresponding to "omissions" in exact learning. We present two algorithms for handling omissions. The first one deals with omissions that are independent events, while the second assumes that omissions are related to gaps in the user's knowledge. We present theoretical results about both methods and we evaluate them on benchmark problems. Importantly, our second algorithm can not only learn (a part of) the target network, but also the constraints that cause the user's uncertainty.
Document type :
Conference papers
Complete list of metadata
Contributor : Isabelle Gouat <>
Submitted on : Wednesday, December 2, 2020 - 3:04:53 PM
Last modification on : Monday, January 11, 2021 - 5:24:08 PM
Long-term archiving on: : Wednesday, March 3, 2021 - 7:34:47 PM


crc_ Omissions.pdf
Files produced by the author(s)




Dimosthenis Tsouros, Kostas Stergiou, Christian Bessière. Omissions in Constraint Acquisition. International Conference on Principles and Practice of Constraint Programming (CP), Sep 2020, Louvain-la-Neuve, Belgium. pp.935-951, ⟨10.1007/978-3-030-58475-7_54⟩. ⟨lirmm-03036103⟩



Record views


Files downloads