Constraint Acquisition via Partial Queries

Christian Bessière 1 Remi Coletta 1 Emmanuel Hébrard 2 George Katsirelos 3 Nadjib Lazaar 4 Nina Narodytska 5, 6 Claude-Guy Quimper 7 Toby Walsh 5, 6
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 [Toulouse]
3 LEO
INRA Toulouse - Institut national de la recherche agronomique [Toulouse]
4 MSR - INRIA - Microsoft Research - Inria Joint Centre
5 NICTA - National ICT Australia [Sydney]
6 School of Computer Science and Engineering [Sydney]
7 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.
Type de document :
Communication dans un congrès
IJCAI'2013: 23rd International Joint Conference on Artificial Intelligence, Beijing, China. pp.7, 2013
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00830325
Contributeur : Joël Quinqueton <>
Soumis le : mardi 4 juin 2013 - 16:52:25
Dernière modification le : mercredi 28 février 2018 - 10:23:11
Document(s) archivé(s) le : mardi 4 avril 2017 - 16:53:03

Fichier

ijcai13-quacq.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : lirmm-00830325, version 1

Collections

INRIA | LAAS-ROC | LAAS | INRA | LAAS-DECISION-ET-OPTIMISATION | UNIV-TLSE3 | COCONUT | LIRMM | INSA-TOULOUSE | MIPS | UNIV-MONTPELLIER

Citation

Christian Bessière, Remi Coletta, Emmanuel Hébrard, George Katsirelos, Nadjib Lazaar, et al.. Constraint Acquisition via Partial Queries. IJCAI'2013: 23rd International Joint Conference on Artificial Intelligence, Beijing, China. pp.7, 2013. 〈lirmm-00830325〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

692

Téléchargements de fichiers

369

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD