Preference Learning and Ranking by Pairwise Comparison
Inhaltsverzeichnis
Reference
Johannes Fürnkranz, Eyke Hüllermeier: Preference Learning and Ranking by Pairwise Comparison. In: Fürnkranz, J. and Hüllermeier, E.: Preference Learning, 2011, 65-82.
DOI
http://dx.doi.org/10.1007/978-3-642-14125-6_4
Abstract
This chapter provides an overview of recent work on preference learning and ranking via pairwise classification. The learning by pairwise comparison (LPC) paradigm is the natural machine learning counterpart to the relational approach to preference modeling and decision making. From a machine learning point of view, LPC is especially appealing as it decomposes a possibly complex prediction problem into a certain number of learning problems of the simplest type, namely binary classification. We explain how to approach different preference learning problems, such as label and instance ranking, within the framework of LPC. We primarily focus on methodological aspects, but also address theoretical questions as well as algorithmic and complexity issues.
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_4},
title={Preference Learning and Ranking by Pairwise Comparison},
url={http://dx.doi.org/10.1007/978-3-642-14125-6_4, http://de.evo-art.org/index.php?title=Preference_Learning_and_Ranking_by_Pairwise_Comparison },
publisher={Springer Berlin Heidelberg},
author={Fürnkranz, Johannes and Hüllermeier, Eyke},
pages={65-82},
language={English}
}
Used References
1. E.L. Allwein, R.E. Schapire, Y. Singer, Reducing multiclass to binary: A unifying approach for margin classifiers. J. Mach. Learn. Res. 1, 113–141 (2000)
2. C. Angulo, F.J. Ruiz, L. González, J.A. Ortega, Multi-classification by using tri-class SVM. Neural Process. Lett. 23(1), 89–101 (2006) http://dx.doi.org/10.1007/s11063-005-3500-3
3. R.A. Bradley, M.E. Terry, The rank analysis of incomplete block designs – I. The method of paired comparisons. Biometrika 39, 324–345 (1952)
4. K. Brinker, J. Fürnkranz, E. Hüllermeier, A unified model for multilabel classification and ranking, in Proceedings of the 17th European Conference on Artificial Intelligence (ECAI-06), ed. by G.Brewka, S.Coradeschi, A.Perini, P.Traverso (2006), pp. 489–493
5. O. Dekel, C.D. Manning, Y. Singer, Log-linear models for label ranking, in Advances in Neural Information Processing Systems (NIPS-03), ed. by S. Thrun, L.K. Saul, B. Schölkopf (MIT, Cambridge, MA, 2004), pp. 497–504
6. J. Fodor, M. Roubens, Fuzzy Preference Modelling and Multicriteria Decision Support (Kluwer, 1994)
7. E. Frank, M. Hall, A simple approach to ordinal classification, in Proceedings of the 12th European Conference on Machine Learning (ECML-01), ed. by L.De Raedt, P.Flach (Springer, Freiburg, Germany, 2001), pp. 145–156
8. J.H. Friedman, Another approach to polychotomous classification. Technical report, Department of Statistics, Stanford University, Stanford, CA, 1996
9. J. Fürnkranz, Round robin classification. J. Mach. Learn. Res. 2, 721–747 (2002)
10. J. Fürnkranz, Round robin ensembles. Intell. Data Anal. 7(5), 385–404 (2003)
11. J. Fürnkranz, E. Hüllermeier, Pairwise preference learning and ranking, in Proceedings of the 14th European Conference on Machine Learning (ECML-03), vol. 2837, Lecture Notes in Artificial Intelligence, ed. by N.Lavrač, D.Gamberger, H.Blockeel, L.Todorovski (Springer, Cavtat, Croatia, 2003), pp. 145–156
12. J. Fürnkranz, E. Hüllermeier, E. Loza Mencía, K. Brinker, Multilabel classification via calibrated label ranking. Mach. Learn. 73(2), 133–153 (2008) http://dx.doi.org/10.1007/s10994-008-5064-8
13. J. Fürnkranz, E. Hüllermeier, S. Vanderlooy, Binary decomposition methods for multipartite ranking, in Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD-09), vol. Part I, ed. by W.L. Buntine, M. Grobelnik, D. Mladenic, J. Shawe-Taylor (Springer, Bled, Slovenia, 2009), pp.359–374
14. S. Har-Peled, D. Roth, D. Zimak, Constraint classification: A new approach to multiclass classification, in Proceedings of the 13th International Conference on Algorithmic Learning Theory (ALT-02), ed. by N.Cesa-Bianchi, M.Numao, R.Reischuk (Springer, Lübeck, Germany, 2002), pp. 365–379 http://dx.doi.org/10.1007/3-540-36169-3_29
15. T. Hastie, R. Tibshirani, Classification by pairwise coupling, in Advances in Neural Information Processing Systems 10 (NIPS-97), ed. by M.I. Jordan, M.J. Kearns, S.A. Solla (MIT, 1998), pp. 507–513
16. C.-W. Hsu, C.-J. Lin, A comparison of methods for multi-class support vector machines. IEEE Trans. Neural Netw. 13(2), 415–425 (2002) http://dx.doi.org/10.1109/72.991427
17. J. Hühn, E. Hüllermeier, Is an ordinal class structure useful in classifier learning? Intl. J. Data Min. Model. Manage. 1(1), 45–67 (2008) http://dx.doi.org/10.1504/IJDMMM.2008.022537
18. J. Hühn, E. Hüllermeier, FR3: A fuzzy rule learner for inducing reliable classifiers. IEEE Trans. Fuzzy Syst. 17(1), 138–149 (2009) http://dx.doi.org/10.1109/TFUZZ.2008.2005490
19. E. Hüllermeier, K. Brinker, Learning valued preference structures for solving classification problems. Fuzzy Sets Syst. 159(18), 2337–2352 (2008) http://dx.doi.org/10.1016/j.fss.2008.01.021
20. E. Hüllermeier, J. Fürnkranz, Comparison of ranking procedures in pairwise preference learning, in Proceedings of the 10th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU-04), Perugia, Italy, 2004
21. E. Hüllermeier, J. Fürnkranz, On predictive accuracy and risk minimization in pairwise label ranking. J. Comput. Syst. Sci. 76(1), 49–62 (2010) http://dx.doi.org/10.1016/j.jcss.2009.05.005
22. E. Hüllermeier, J. Fürnkranz, W. Cheng, K. Brinker, Label ranking by learning pairwise preferences. Artif. Intell. 172, 1897–1916 (2008) http://dx.doi.org/10.1016/j.artint.2008.08.002
23. E. Hüllermeier, S. Vanderlooy, Combining predictions in pairwise classification: An optimal adaptive voting strategy and its relation to weighted voting. Pattern Recognit. 43(1), 128–142 (2010)
24. T. Joachims, Optimizing search engines using clickthrough data, in Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-02), (ACM, 2002), pp. 133–142
25. S. Knerr, L. Personnaz, G. Dreyfus, Single-layer learning revisited: A stepwise procedure for building and training a neural network, in Neurocomputing: Algorithms, Architectures and Applications, vol. F68, NATO ASI Series, ed. by F.Fogelman Soulié, J.Hérault (Springer, 1990), pp. 41–50
26. S. Knerr, L. Personnaz, G. Dreyfus, Handwritten digit recognition by neural networks with single-layer training. IEEE Trans. Neural Netw. 3(6), 962–968 (1992) http://dx.doi.org/10.1109/72.165597
27. D. Koller, M. Sahami, Hierarchically classifying documents using very few words, in Proceedings of the 14th International Conference on Machine Learning (ICML-97) (Nashville, 1997), pp. 170–178
28. U.H.-G. Kreßel, Pairwise classification and support vector machines, in Advances in Kernel Methods: Support Vector Learning, Chap.15, ed. by B.Schölkopf, C.J.C. Burges, A.J. Smola (MIT, Cambridge, MA, 1999), pp. 255–268
29. E. Loza Mencía, J. Fürnkranz, Efficient pairwise multilabel classification for large-scale problems in the legal domain, in Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Disocvery in Databases (ECML-PKDD-2008), Part II, ed. by W. Daelemans, B. Goethals, K. Morik (Springer, Antwerp, Belgium, 2008), pp. 50–65
30. E. Loza Mencía, S.-H. Park, J. Fürnkranz, Efficient voting prediction for pairwise multilabel classification, in Proceedings of the 11th European Symposium on Artificial Neural Networks (ESANN-09) (d-side publicationsBruges, Belgium, 2009), pp. 117–122
31. B.-L. Lu, M. Ito, Task decomposition and module combination based on class relations: A modular neural network for pattern classification. IEEE Trans. Neural Netw. 10(5), 1244–1256 (1999) http://dx.doi.org/10.1109/72.788664
32. M. Moreira, E. Mayoraz, Improved pairwise coupling classification with correcting classifiers, in Proceedings of the 10th European Conference on Machine Learning (ECML-98), ed. by C.Nédellec, C.Rouveirol (Springer, Chemnitz, Germany, 1998), pp. 160–171 http://dx.doi.org/10.1007/BFb0026686
33. G.H. Nam, Ordered pairwise classification. Master’s thesis, TU Darmstadt, Knowledge Engineering Group, 2007
34. S.-H. Park, J. Fürnkranz, Efficient pairwise classifciation, in Proceedings of 18th European Conference on Machine Learning (ECML-07), ed. by J.N. Kok, J.Koronacki, R.Lopez de Mantaras, S.Matwin, D.Mladenič, A.Skowron (Springer, Warsaw, Poland, 2007), pp.658–665
35. S.-H. Park, J. Fürnkranz, Efficient decoding of ternary error-correcting output codes for multiclass classification, in Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD-09), ed. by W.L.Buntine, M. Grobelnik, D. Mladenic, J. Shawe-Taylor, vol. Part I (Springer, Bled, Slovenia, 2009), pp. 189–204
36. J.C. Platt, N. Cristianini, J. Shawe-Taylor, Large margin DAGs for multiclass classification, in Advances in Neural Information Processing Systems 12 (NIPS-99), ed. by S.A. Solla, T.K.Leen, K.-R. Müller (MIT, 2000), pp. 547–553
37. D. Price, S. Knerr, L. Personnaz, G. Dreyfus, Pairwise neural network classifiers with probabilistic outputs, in Advances in Neural Information Processing Systems 7 (NIPS-94), ed. by G.Tesauro, D.Touretzky, T.Leen (MIT, 1995), pp. 1109–1116
38. T.L. Saaty, Decision Making for Leaders: The Analytic Hierarchy Process for Decisions in a Complex World (RWS Publications, Pittsburgh, Pennsylvania, 1999)
39. T.L. Saaty, Relative measurement and its generalization in decision making: Why pairwise comparisons are central in mathematics for the measurement of intangible factors – the analytic hierarchy/network process. Revista de la Real Academia de Ciencias Exactas Físicas y Naturales A Matemáticas (RACSAM) 102(2), 251–318 (2008)
40. M.S. Schmidt, H. Gish, Speaker identification via support vector classifiers, in Proceedings of the 21st IEEE International Conference Conference on Acoustics, Speech, and Signal Processing (ICASSP-96) (Atlanta, GA, 1996), pp. 105–108
41. J.F. Sima, Präferenz-Lernen für Hierarchische Multilabel Klassifikation. Master’s thesis, TU Darmstadt, Knowledge Engineering Group, 2007
42. J.-N. Sulzmann, J. Fürnkranz, E. Hüllermeier, On pairwise naive bayes classifiers, in Proceedings of 18th European Conference on Machine Learning (ECML-07), ed. by J.N. Kok, J.Koronacki, R.Lopez de Mantaras, S.Matwin, D.Mladenič, A.Skowron (Springer, Warsaw, Poland, 2007), pp. 371–381
43. L.L. Thurstone, A law of comparative judgement. Psychol. Rev. 34, 278–286 (1927)
44. T.-F. Wu, C.-J. Lin, R.C. Weng, Probability estimates for multi-class classification by pairwise coupling. J. Mach. Learn. Res. 5, 975–1005 (2004)
45. Y. Yang, An evaluation of statistical approaches to text categorization. Inf. Retr. 1, 69–90 (1999)
Links
Full Text
http://www.ke.tu-darmstadt.de/publications/papers/PLBook-Pairwise.pdf
