Learning Ordinal Preferences on Multiattribute Domains: The Case of CP-nets
Inhaltsverzeichnis
Reference
Yann Chevaleyre, Frédéric Koriche, Jérôme Lang, Jérôme Mengin, Bruno Zanuttini: Learning Ordinal Preferences on Multiattribute Domains: The Case of CP-nets. In: Fürnkranz, J. and Hüllermeier, E.: Preference Learning, 2011, 273-296.
DOI
http://dx.doi.org/10.1007/978-3-642-14125-6_13
Abstract
A recurrent issue in decision making is to extract a preference structure by observing the user’s behavior in different situations. In this paper, we investigate the problem of learning ordinal preference orderings over discrete multiattribute, or combinatorial, domains. Specifically, we focus on the learnability issue of conditional preference networks, or CP-nets, that have recently emerged as a popular graphical language for representing ordinal preferences in a concise and intuitive manner. This paper provides results in both passive and active learning. In the passive setting, the learner aims at finding a CP-net compatible with a supplied set of examples, while in the active setting the learner searches for the cheapest interaction policy with the user for acquiring the target CP-net.
Extended Abstract
Bibtex
@incollection{
year={2011},
isbn={978-3-642-14124-9},
booktitle={Preference Learning},
editor={Fürnkranz, Johannes and Hüllermeier, Eyke},
doi={10.1007/978-3-642-14125-6_13},
title={Learning Ordinal Preferences on Multiattribute Domains: The Case of CP-nets},
url={http://dx.doi.org/10.1007/978-3-642-14125-6_13, http://de.evo-art.org/index.php?title=Learning_Ordinal_Preferences_on_Multiattribute_Domains:_The_Case_of_CP-nets },
publisher={Springer Berlin Heidelberg},
author={Chevaleyre, Yann and Koriche, Frédéric and Lang, Jérôme and Mengin, Jérôme and Zanuttini, Bruno},
pages={273-296},
language={English}
}
Used References
1. D. Angluin, Queries and concept learning. Mach. Learn. 2(4), 319–342 (1988)
2. D. Angluin, Negative results for equivalence queries. Mach. Learn. 5, 121–150 (1990)
3. D. Angluin, M. Frazier, L. Pitt, Learning conjunctions of Horn clauses. Mach. Learn. 9, 147–164 (1992)
4. M. Anthony, N. Biggs, Computational Learning Theory (Cambridge University Press, 1992)
5. C. Boutilier, R. Brafman, C. Domshlak, H. Hoos, D. Poole, CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res. 21, 135–191 (2004)
6. R. Brafman, C. Domshlak, S. Shimony, On graphical modeling of preference and importance. J. Artif. Intell. Res. 25, 389–424 (2006)
7. D. Braziunas, C. Boutilier, Local utility elicitation in GAI models, in Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI) (2005), pp. 42–49
8. C.J.C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, G. Hullender, Learning to rank using gradient descent, in Proceedings of the 22nd International Conference on Machine Learning (ICML) (2005)
9. U. Chajewska, L. Getoor, J. Norman, Y. Shahar, Utility elicitation as a classification problem, in Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI) (1998), pp. 79–88
10. U. Chajewska, D. Koller, R. Parr, Making rational decisions using adaptive utility elicitation, in Proceedings of the 17th National Conference on Artificial Intelligence (AAAI) (2000),pp. 363–369
11. Y. Chevaleyre, A short note on passive learning of CP-nets. Rapport de recherche, Lamsade, mars 2009
12. Y. Dimopoulos, L. Michael, F. Athienitou, Ceteris paribus preference elicitation with predictive guarantees, in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009) (2009)
13. J. Dombi, C. Imreh, N. Vincze, Learning lexicographic orders. Eur. J. Oper. Res. 183, 748–756 (2007) http://dx.doi.org/10.1016/j.ejor.2006.10.029
14. C. Domshlak, T. Joachims, Efficient and non-parametric reasoning over user preferences. User Model. User-adapt. Interact. (UMUAI) 17(1-2), 41–69 (2007)
15. J. Doyle, Y. Shoham, M. Wellman, A logic of relative desire (preliminary report), in Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems (ISMIS) (Springer, 1991), pp. 16–31
16. Ch. Gonzales, P. Perny, GAI networks for utility elicitation, in Principles of Knowledge Representation and Reasoning: Proceedings of the 9th International Conference (KR) (2004), pp. 224–234
17. P. Green, V. Srinivasan, Conjoint analysis in consumer research: Issues and outlook. J. Consumer Res. 5(2), 103–123 (1978) http://dx.doi.org/10.1086/208721
18. V. Ha, P. Haddawy, Problem-focused incremental elicitation of multi-attribute utility models, in Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (UAI) (1997), pp. 215–222
19. M.J. Kearns, M. Li, L. Pitt, L.G. Valiant, On the learnability of boolean formulae, in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (1987), pp. 285–295
20. R. Keeney, H. Raiffa, Decision with Multiple Objectives: Preferences and Value Trade-offs (Wiley, 1976)
21. F. Koriche, B. Zanuttini, Learning conditional preference networks with queries, in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009) (2009)
22. J. Lang, J. Mengin, The complexity of learning ceteris paribus separable preferences, in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009) (2009)
23. J. Lang, J. Mengin, The complexity of learning separable ceteris paribus preferences. Rapport de recherche RR-2009-3-FR, IRIT, Université Paul Sabatier, Toulouse, mars 2009
24. N. Littlestone, From on-line to batch learning, in Proceedings of the Second Annual Workshop on Computational Learning Theory (Morgan Kaufmann, 1989), pp. 269–284
25. M. Sachdev, On learning of ceteris paribus preference theories. Master’s thesis, Graduate Faculty of North Carolina State University, 2007
26. T. Sandholm, C. Boutilier, Preference Elicitation in Combinatorial Auctions, Chap. 10, in Combinatorial Auctions, ed. by Cramton, Shoham, and Steinberg (MIT, 2006)
27. M. Schmitt, L. Martignon, On the complexity of learning lexicographic strategies. J. Mach. Learn. Res. 7, 55–83 (2006)
28. L.G. Valiant, A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984) http://dx.doi.org/10.1145/1968.1972
29. P. Viappiani, B. Faltings, P. Pu, Evaluating preference-based search tools: a tale fo two approaches, in Proceedings of the 21st National Conference on Artificial Intelligence (AAAI) (2006), pp. 205–210
30. P. Viappiani, B. Faltings, P. Pu, Preference-based search using example-critiquing with suggestions. J. Artif. Intell. Res. 27, 465–503 (2006)
31.N. Wilson, Extending CP-nets with stronger conditional preference statements, in Proceedings of the 19th National Conference on Artificial Intelligence (AAAI) (2004), pp. 735–741
32. F. Yaman, Th. Walsh, M. Littman, M. desJardins, Democratic approximation of lexicographic preference models, in Proceedings of the 35th International Conference in Machine Learning (ICML) (2008), pp. 1200–1207
Links
Full Text
http://www.lamsade.dauphine.fr/~lang/papers/cklmz09.pdf
