Learning Conditional Preference Networks with Queries - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2009

Learning Conditional Preference Networks with Queries

Frédéric Koriche

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.
No file

Dates and versions

lirmm-00413702 , version 1 (04-09-2009)

Identifiers

  • HAL Id : lirmm-00413702 , version 1

Cite

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⟩
74 View
0 Download

Share

More