Skip to Main content Skip to Navigation
Conference papers

Learning Conditional Preference Networks with Queries

Frédéric Koriche 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We investigate the problem of eliciting CP-nets in the well-known model of exact learning with equivalence and membership queries. The goal is to identify a preference ordering with a binary-valued CP-net by guiding the user through a sequence of queries. Each example is a dominance test on some pair of outcomes. In this setting, we show that acyclic CP-nets are not learnable with equivalence queries alone, while they are learnable with the help of membership queries if the supplied examples are restricted to swaps. A similar property holds for tree CP-nets with arbitrary examples. In fact, membership queries allow us to provide attribute-efficient algorithms for which the query complexity is only logarithmic in the number of attributes. Such results highlight the utility of this model for eliciting CP-nets in large multi-attribute domains.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00413702
Contributor : Frédéric Koriche <>
Submitted on : Friday, September 4, 2009 - 8:05:43 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM

Identifiers

  • HAL Id : lirmm-00413702, version 1

Collections

Citation

Frédéric Koriche. Learning Conditional Preference Networks with Queries. IJCAI'09: 21st International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, CA, United States. pp.685-703. ⟨lirmm-00413702⟩

Share

Metrics

Record views

96