Acquisition de contraintes avec des requêtes partielles - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2014

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.
Nous apprenons des réseaux de contraintes en utilisant des requêtes partielles. Autrement dit, nous demandons à l’utilisateur de classer une affectation de sous-ensembles de variables comme positive ou négative. Nous fournissons un algorithme qui, étant donné un exemple complet négatif, apprend une contrainte du réseau cible avec un certain nombre de requêtes partielles, logarithmique en taille de l’exemple. Nous présentons une étude théorique sur les bornes inférieures en termes de requêtes pour apprendre certaines classes de réseaux de contraintes et montrons l’optimalité de notre algorithme générique dans certains cas. Enfin, nous évaluons expérimentalement notre algorithme.
Fichier principal
Vignette du fichier
jfpc14-quacq.pdf (416.01 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01229549 , version 1 (10-10-2019)

Identifiers

  • HAL Id : lirmm-01229549 , version 1

Cite

Christian Bessiere, Remi Coletta, Emmanuel Hébrard, George Katsirelos, Nadjib Lazaar, et al.. Acquisition de contraintes avec des requêtes partielles. 10èmes Journées Francophones de Programmation par Contraintes (JFPC 2014), Jun 2014, Angers, France. ⟨lirmm-01229549⟩
220 View
52 Download

Share

Gmail Facebook X LinkedIn More