Learning Conditional Preference Networks

Frédéric Koriche 1 Bruno Zanuttini 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 Equipe MAD - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : Conditional preference networks (CP-nets) have recently emerged as a popular language capable of representing ordinal preference relations in a compact and structured manner. In this paper, we investigate the problem of learning CP-nets in the well-known model of exact identification with equivalence and membership queries. The goal is to identify a target preference ordering with a binary-valued CP-net by interacting with the user through a small number of queries. Each example supplied by the user or the learner is a preference statement on a pair of outcomes. In this model, we show that acyclic CP-nets are not learnable with equivalence queries alone, even if the examples are restricted to swaps for which dominance testing takes linear time. By contrast, acyclic CP-nets are what is called attribute-efficiently learnable when both equivalence queries and membership queries are available: we indeed provide a learning algorithm whose query complexity is linear in the description size of the target concept, but only logarithmic in the total number of attributes. Interestingly, similar properties are derived for tree-structured CP-nets in the presence of arbitrary examples. Our learning algorithms are shown to be quasi-optimal by deriving lower bounds on the VC-dimension of CP-nets. In a nutshell, our results reveal that active queries are required for efficiently learning CP-nets in large multi-attribute domains.
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00485498
Contributeur : Frédéric Koriche <>
Soumis le : vendredi 14 février 2014 - 15:13:30
Dernière modification le : mardi 5 juin 2018 - 10:14:42
Document(s) archivé(s) le : jeudi 15 mai 2014 - 09:41:09

Fichier

kz10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Frédéric Koriche, Bruno Zanuttini. Learning Conditional Preference Networks. Artificial Intelligence, Elsevier, 2010, 174 (11), pp.685-703. 〈10.1016/j.artint.2010.04.019〉. 〈lirmm-00485498〉

Partager

Métriques

Consultations de la notice

519

Téléchargements de fichiers

223