Preference Learning and Ranking by Pairwise Comparison

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche

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

intern file

Sonstige Links