Learning Conditional Preference Networks - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Artificial Intelligence Year : 2010

Learning Conditional Preference Networks

Frédéric Koriche
Bruno Zanuttini
  • Function : Author
  • PersonId : 952903

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.
Fichier principal
Vignette du fichier
kz10.pdf (243.74 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00485498 , version 1 (14-02-2014)

Identifiers

Cite

Frédéric Koriche, Bruno Zanuttini. Learning Conditional Preference Networks. Artificial Intelligence, 2010, 174 (11), pp.685-703. ⟨10.1016/j.artint.2010.04.019⟩. ⟨lirmm-00485498⟩
411 View
444 Download

Altmetric

Share

More