Résumé
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.