Learning Constraints through Partial Queries - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Artificial Intelligence Year : 2023

Learning Constraints through Partial Queries

Clement Carbonnel
Anton Dries
Nina Narodytska
  • Function : Author
  • PersonId : 1106711
Claude-Guy Quimper
Toby Walsh
  • Function : Author
  • PersonId : 972947

Abstract

Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcq2, that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcq2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcq2 in practice, especially in the case where QuAcq2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcq2 requires significantly fewer queries to learn a network than its predecessor QuAcq1.
Fichier principal
Vignette du fichier
v66-13-03-2023-cb-authors-version.pdf (640.87 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Licence

Dates and versions

lirmm-04028358 , version 1 (14-03-2023)

Licence

Identifiers

Cite

Christian Bessiere, Clement Carbonnel, Anton Dries, Emmanuel Hebrard, George Katsirelos, et al.. Learning Constraints through Partial Queries. Artificial Intelligence, 2023, 319, pp.103896. ⟨10.1016/j.artint.2023.103896⟩. ⟨lirmm-04028358⟩
232 View
243 Download

Altmetric

Share

More