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

Learning Constraints through Partial Queries

Clement Carbonnel
Anton Dries
  • Function : Author
  • PersonId : 1024731
Nina Narodytska
  • Function : Author
  • PersonId : 1106711
Claude-Guy Quimper
  • Function : Author
  • PersonId : 845231
Kostas Stergiou
  • Function : Author
  • PersonId : 1125286
Toby Walsh
  • Function : Author
  • PersonId : 972947


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 : CC BY NC ND - Attribution - NonCommercial - NoDerivatives

Dates and versions

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



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



Gmail Facebook Twitter LinkedIn More