Constraint Acquisition via Partial Queries

Christian Bessière 1 Remi Coletta 1 Emmanuel Hébrard 2 George Katsirelos Nadjib Lazaar 3 Nina Narodytska 4, 5 Claude-Guy Quimper 6 Toby Walsh 4, 5
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 LAAS-MOGISA
LAAS - Laboratoire d'analyse et d'architecture des systèmes
3 MSR - INRIA - Microsoft Research - Inria Joint Centre
4 NICTA - National ICT Australia [Sydney]
5 CSE - Computer Science and Engineering [Sydney]
6 GEL-GIF - Département de génie électrique et de génie informatique
Abstract : 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 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 [12 references]  Display  Hide  Download
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00830325
Contributor : Joël Quinqueton <>
Submitted on : Tuesday, June 4, 2013 - 4:52:25 PM
Last modification on : Friday, January 10, 2020 - 9:10:08 PM
Long-term archiving on: Tuesday, April 4, 2017 - 4:53:03 PM

File

ijcai13-quacq.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : lirmm-00830325, version 1

Collections

CNRS | INRIA | LAAS-ROC | LAAS | COCONUT | LIRMM | INSA-TOULOUSE | MIPS | UNIV-MONTPELLIER | INSA-GROUPE | UNIV-TLSE3 | UT1-CAPITOLE | UNIV-TLSE2

Citation

Christian Bessière, Remi Coletta, Emmanuel Hébrard, George Katsirelos, Nadjib Lazaar, et al.. Constraint Acquisition via Partial Queries. IJCAI: International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. pp.475-481. ⟨lirmm-00830325⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

1112

Files downloads

583

Contact

Informations

CCSD