Learning Lexicographic Preference Models
Inhaltsverzeichnis
Reference
Fusun Yaman, Thomas J. Walsh, Michael L. Littman, Marie desJardins: Learning Lexicographic Preference Models. In: Fürnkranz, J. and Hüllermeier, E.: Preference Learning, 2011, 251-272.
DOI
http://dx.doi.org/10.1007/978-3-642-14125-6_12
Abstract
Lexicographic preference models (LPMs) are one of the simplest yet most commonly used preference representations. In this chapter, we formally define LPMs and present learning algorithms for mining these models from data. In particular, we study a greedy algorithm that produces a “best guess” LPM that is consistent with the observations and two voting-based algorithms that approximate the target using the votes of a collection of consistent LPMs. In addition to our theoretical analyses of these algorithms, we empirically evaluate their performance under different conditions. Our results show that voting algorithms outperform the greedy method when the data is noise-free. The dominance is more significant when the training data is scarce. However, the performance of the voting algorithms quickly decays with even a little noise, whereas the greedy algorithm is more robust. Inspired by this result, we adapt one of the voting methods to consider the amount of noise in an environment and empirically show that the modified voting algorithm performs as well as the greedy approach even with noisy observations. We also introduce an intuitive yet powerful learning bias to prune some of the possible LPMs. We demonstrate how this learning bias can be used with variable and model voting and show that the learning bias improves learning performance significantly, especially when the number of observations is small.
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_12},
title={Learning Lexicographic Preference Models},
url={http://dx.doi.org/10.1007/978-3-642-14125-6_12, http://de.evo-art.org/index.php?title=Learning_Lexicographic_Preference_Models },
publisher={Springer Berlin Heidelberg},
author={Yaman, Fusun and Walsh, ThomasJ. and Littman, MichaelL. and desJardins, Marie},
pages={251-272},
language={English}
}
Used References
1. D.P. Bertsekas, J.N. Tsitsiklis, Parallel and distributed computation: numerical methods (Athena Scientific, 1997)
2. C. Boutilier, R.I. Brafman, C. Domshlak, H.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)MathSciNetMATH
3. W.W. Cohen, R.E. Schapire, Y. Singer, Learning to order things. J. Artif. Intell. Res. 10, 243–270 (1999)MathSciNetMATH
4. A.M. Colman, J.A. Stirk, Singleton bias and lexicographic preferences among equally valued alternatives. J. Econ. Behav. Organ. 40(4), 337–351 (1999) http://dx.doi.org/10.1016/S0167-2681(99)00058-X
5. G.B. Dantzig, A. Orden, P. Wolfe, The generalized simplex method for minimizing a linear form under linear inequality restraints. Pac. J. Math. 5, 183–195 (1955) http://dx.doi.org/10.2140/pjm.1955.5.183
6. R.M. Dawes, The robust beauty of improper linear models in decision making. Am. Psychol. 34, 571–582 (1979) http://dx.doi.org/10.1037/0003-066X.34.7.571
7. J. Dombi, C. Imreh, N. Vincze, Learning lexicographic orders. Eur. J. Oper. Res. 183(2), 748–756 (2007) http://dx.doi.org/10.1016/j.ejor.2006.10.029
8. P.C. Fishburn, Lexicographic orders, utilities and decision rules: A survey. Manage. Sci. 20(11), 1442–1471 (1974) http://dx.doi.org/10.1287/mnsc.20.11.1442
9. J. Kevin Ford, N. Schmitt, S.L. Schechtman, B.M. Hults, M.L. Doherty, Process tracing methods: contributions, problems and neglected research issues. Organ. Behav. Hum. Decis. Process. 43, 75–117 (1989)
10. A. Quesada, Negative results in the theory of games with lexicographic utilities. Econ. Bull. 3(20), 1–7 (2003)
11. R.L. Rivest, Learning decision lists. Mach. Learn. 2(3), 229–246 (1987)
12. M. Schmitt, L. Martignon, On the complexity of learning lexicographic strategies. J. Mach. Learn. Res. 7, 55–83 (2006)MathSciNetMATH
13. L. Torrey, J. Shavlik, T. Walker, R. Maclin, Relational macros for transfer in reinforcement learning, in Proceedings of the Seventeenth Conference on Inductive Logic Programming (Corvallis, Oregon, 2007)
14. M.R.M. Westenberg, P. Koele, Multi-attribute evaluation processes: methodological and conceptual issues. Acta Psychol. 87, 65–84 (1994) http://dx.doi.org/10.1016/0749-5978(89)90059-9
15. F. Yaman, T.J Walsh, M. Littman, M. desJardins, Democratic approximation of lexicographic preference models, 2009. Submitted to Artificial Intelligence
16. F. Yaman, T.J. Walsh, M.L. Littman, M. desJardins, Democratic approximation of lexicographic preference models, in Proceedings of the Twenty-Fifth International Conference (ICML 2008) (Helsinki, Finland, 2008), pp. 1200–1207
