Acquisition de contraintes avec des requêtes partielles

Abstract : We learn constraint networks by asking the user par- tial queries. That is, we ask the user to classify assign- ments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. 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. Finally we evaluate our algorithm on some benchmarks.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01229549
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 10, 2019 - 1:43:53 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM

File

jfpc14-quacq.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01229549, version 1

Citation

Christian Bessière, Remi Coletta, Emmanuel Hébrard, George Katsirelos, Nadjib Lazaar, et al.. Acquisition de contraintes avec des requêtes partielles. JFPC: Journées Francophones de Programmation par Contraintes, Jun 2014, Angers, France. ⟨lirmm-01229549⟩

Share

Metrics

Record views

275

Files downloads

16