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.
Type de document :
Communication dans un congrès
Craig Boutilier. IJCAI'09: 21st International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, CA, United States. IJCAI/AAAI Press, 174 (11), pp.685-703, 2009
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00413702
Contributeur : Frédéric Koriche <>
Soumis le : vendredi 4 septembre 2009 - 20:05:43
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Identifiants

  • HAL Id : lirmm-00413702, version 1

Collections

Citation

Frédéric Koriche. Learning Conditional Preference Networks with Queries. Craig Boutilier. IJCAI'09: 21st International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, CA, United States. IJCAI/AAAI Press, 174 (11), pp.685-703, 2009. 〈lirmm-00413702〉

Partager

Métriques

Consultations de la notice

56