Learning Lexicographic Preference Models

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


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.




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


booktitle={Preference Learning},
editor={Fürnkranz, Johannes and Hüllermeier, Eyke},
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},

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


Full Text

intern file

Sonstige Links