Learning conditionally lexicographic preference relations. (English) Zbl 1211.68223
Coelho, Helder (ed.) et al., ECAI 2010. 19th European conference on artificial intelligence, August 16–20, 2010 Lisbon, Portugal. Including proceedings of the 6th prestigious applications of artificial intelligence (PAIS-2010). Amsterdam: IOS Press (ISBN 978-1-60750-605-8/pbk; 978-1-60750-606-5/ebook). Frontiers in Artificial Intelligence and Applications 215, 269-274 (2010).
Summary: We consider the problem of learning a user’s ordinal preferences on a multiattribute domain, assuming that her preferences are lexicographic. We introduce a general graphical representation called LP-trees which captures various natural classes of such preference relations, depending on whether the importance order between attributes and/or the local preferences on the domain of each attribute is conditional on the values of other attributes. For each class we determine the Vapnik-Chernovenkis dimension, the communication complexity of preference elicitation, and the complexity of identifying a model in the class consistent with a set of user-provided examples.
For the entire collection see [Zbl 1207.68003].
For the entire collection see [Zbl 1207.68003].
MSC:
68Q32 | Computational learning theory |
68R10 | Graph theory (including graph drawing) in computer science |
68T05 | Learning and adaptive systems in artificial intelligence |