Label Ranking Algorithms: A Survey
Inhaltsverzeichnis
Reference
Shankar Vembu, Thomas Gärtner: Label Ranking Algorithms: A Survey. In: Fürnkranz, J. and Hüllermeier, E.: Preference Learning, 2011, 45-64.
DOI
http://dx.doi.org/10.1007/978-3-642-14125-6_3
Abstract
Label ranking is a complex prediction task where the goal is to map instances to a total order over a finite set of predefined labels. An interesting aspect of this problem is that it subsumes several supervised learning problems, such as multiclass prediction, multilabel classification, and hierarchical classification. Unsurprisingly, there exists a plethora of label ranking algorithms in the literature due, in part, to this versatile nature of the problem. In this paper, we survey these algorithms.
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_3},
title={Label Ranking Algorithms: A Survey},
url={http://dx.doi.org/10.1007/978-3-642-14125-6_3, http://de.evo-art.org/index.php?title=Label_Ranking_Algorithms:_A_Survey },
publisher={Springer Berlin Heidelberg},
author={Vembu, Shankar and Gärtner, Thomas},
pages={45-64},
language={English}
}
Used References
1. A. Agarwal, S. Chakrabarti, Learning random walks to rank nodes in graphs, in Proceedings of the Twenty-Fourth International Conference on Machine Learning (2007)
2. S. Agarwal, Ranking on graph data, in Proceedings of the Twenty-Third International Conference on Machine Learning (2006)
3. N. Ailon, Aggregation of partial rankings, p-ratings and top-m lists, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2007)
4. N. Ailon, M. Charikar, A. Newman, Aggregating inconsistent information: Ranking and clustering, in Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (2005)
5. D. Aldous, Random walks on finite groups and rapidly mixing markov chains. Séminaire de probabilités de Strasbourg 17, 243–297 (1983)
6. Y. Altun, T. Hofmann, M. Johnson, Discriminative learning for label sequences via boosting, in Advances in Neural Information Processing Systems, vol.15 (2002)
7. N. Balcan, N. Bansal, A. Beygelzimer, D. Coppersmith, J. Langford, G. Sorkin, Robust reductions from ranking to classification. Mach. Learn. J. 72(1–2), 139–153 (2008) http://dx.doi.org/10.1007/s10994-008-5058-6
8. S. Boyd, L. Vandenberghe, Convex Optimization (Cambridge Univeristy Press, 2004)
9. L.M. Bregman, The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Comput. Mathe. Math. Phys. 7, 200–217 (1967)
10. K. Brinker, E. Hüllermeier, Case-based label ranking, in Proceedings of the Seventeenth European Conference on Machine Learning (2006)
11. K. Brinker, E. Hüllermeier, Case-based multilabel ranking, in Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (2007)
12. C.J.C. Burges, R. Ragno, Q.V. Le, Learning to rank with nonsmooth cost functions, in Advances in Neural Information Processing Systems, vol.19 (2006)
13. 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 Twenty-Second International Conference on Machine Learning (2005)
14. W. Cheng, J.C. Huhn, E. Hüllermeier, Decision tree and instance-based learning for label ranking, in Proceedings of the Twenty-Sixth Annual International Conference on Machine Learning (2009)
15. W. Cheng, E. Hüllermeier, Instance-based label ranking using the Mallows model, in Proceedings of the Preference Learning Workshop at the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (2008)
16. W. Chu, Z. Ghahramani, Gaussian processes for ordinal regression. J. Mach. Learn. Res. 6, 1019–1041 (2005)
17. W. Chu, S.S. Keerthi, New approaches to support vector ordinal regression, in Proceedings of the Twenty-Second International Conference on Machine Learning (2005)
18. W.W. Cohen, R.E. Schapire, Y. Singer, Learning to order things. J. Artif. Intell. Res. 10, 243–270 (1999)
19. M. Collins, R.E. Schapire, Y. Singer, Logistic regression, AdaBoost and Bregman distances. Mach. Learn. 48(1–3), 253–285 (2002) http://dx.doi.org/10.1023/A%3A1013912006537
20. C. Cortes, V. Vapnik, Support-vector networks. Mach. Learn. 20(3), 273–297 (1995)MATH
21. T.M. Cover, J.A. Thomas, Elements of information theory (Wiley-Interscience, New York, NY, USA, 1991) http://dx.doi.org/10.1002/0471200611
22. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, Y. Singer, Online passive-aggressive algorithms. J. Mach. Learn. Res. 7, 551–585 (2006)
23. K. Crammer, Y. Singer, Pranking with ranking, in Advances in Neural Information Processing Systems, vol.14 (2001)
24. K. Crammer, Y. Singer, A family of additive online algorithms for category ranking. J. Mach. Learn. Res. 3, 1025–1058 (2003)
25. K. Crammer, Y. Singer, Loss bounds for online category ranking, in Proceedings of the Eighteenth Annual Conference on Learning Theory (2005)
26. H. Daumé III, Practical Structured Learning Techniques for Natural Language Processing. PhD thesis, University of Southern California, Los Angeles, CA, August 2006
27. O. Dekel, C.D. Manning, Y. Singer, Log-linear models for label ranking, in Advances in Neural Information Processing Systems, vol.16 (2003)
28. A. Dempster, N. Laird, D. Rubin, Maximum likelihood from incomplete data via the EM algorithm. J.R. Stat. Soc. B Methodological 39(1), 1–38 (1977)
29. C. Dwork, R. Kumar, M. Naor, D.Sivakumar, Rank aggregation methods for the web, in Proceedings of the Tenth International World Wide Web Conference (2001)
30. A. Elisseeff, J. Weston, A kernel method for multi-labelled classification, in Advances in Neural Information Processing Systems, vol.14 (2001)
31. R. Fagin, R. Kumar, M. Mahdian, D.Sivakumar, E. Vee, Comparing and aggregating rankings with ties, in Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (2004)
32. Y. Freuend, R. Iyer, R.E. Schapire, Y. Singer, An efficient boosting algorithm for combining preferences. J. Mach. Learn. Res. 4, 933–969 (2003)
33. Y. Freund, R.E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55(1), 119–139 (1997) http://dx.doi.org/10.1006/jcss.1997.1504
34. G. Fung, R. Rosales, B. Krishnapuram, Learning rankings via convex hull separation, in Advances in Neural Information Processing Systems, vol.18 (2005)
35. J. Fürnkranz, Round robin classification. J. Mach. Learn. Res. 2, 721–747 (2002)
36. J. Fürnkranz, E. Hüllermeier, Pairwise preference learning and ranking, in Proceedings of the Fourteenth European Conference on Machine Learning (2003)
37. J. Fürnkranz, E. Hüllermeier, E.L. 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
38. T. Gärtner, S. Vembu, Learning to predict combinatorial structures, in Proceedings of the NIPS Workshop on Structured Inputs and Structured outputs (2008)
39. T. Gärtner, S. Vembu, On structured output training: Hard cases and an efficient alternative. Mach. Learn. J. 76(2–3), 227–242 (2009) http://dx.doi.org/10.1007/s10994-009-5129-3
40. S. Har-Peled, D. Roth, D. Zimak, Constraint classification: A new approach to multiclass classification, in Proceedings of the Thirteenth International Conference on Algorithmic Learning Theory (2002)
41. S. Har-Peled, D. Roth, D. Zimak, Constraint classification for multiclass classification and ranking, in Advances in Neural Information Processing Systems, vol.15 (2002)
42. R. Hassin, S. Rubinstein, Approximations for the maximum acyclic subgraph problem. Inf. Process. Lett. 51(3), 133–140 (1994) http://dx.doi.org/10.1016/0020-0190(94)00086-7
43. R. Herbrich, T. Graepel, K. Obermayer, Support vector learning for ordinal regression,. in Proceedings of the Ninth International Conference on Artificial Neural Networks (1999)
44. R. Herbrich, T. Graepel, K. Obermayer, Large margin rank boundaries for ordinal regression, In Advances in Large Margin Classifiers, ed. by P.J. Bartlett, B. Schölkopf, D. Schuurmans, A.J. Smola (MIT Press, Cambridge, MA, 2000), pp. 115–132
45. M. Huber, Fast perfect sampling from linear extensions. Discrete Math. 306(4), 420–428 (2006) http://dx.doi.org/10.1016/j.disc.2006.01.003
46. E. Hüllermeier, J. Fürnkranz, W. Cheng, K. Brinker, Label ranking by learning pairwise preferences. Artif. Intell. 178, 1897–1916 (2008)
47. J.Bartholdi III, C.A. Tovey, M.A. Trick, Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6(2), 157–165 (1989) http://dx.doi.org/10.1007/BF00303169
48. M. Jerrum, A. Sinclair, The Markov chain Monte Carlo method: An approach to approximate counting and integration, in Hochbaum DS(ed) Approximation Algorithms for NP-hard Problems (PWS Publishing, Boston, Mass., 1996), pp. 482–520
49. M.R. Jerrum, L.G. Valiant, V.V. Vazirani, Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 32, 169–188 (1986) http://dx.doi.org/10.1016/0304-3975(86)90174-X
50. T. Joachims, Optimizing search engines using clickthrough data, in Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2002)
51. M. Kendall, A new measure of rank correlation. Biometrika 30, 81–89 (1938)
52. C. Kenyon-Mathieu, W. Schudy, How to rank with few errors: A PTAS for weighted feedback arc set on tournaments, in Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (2007)
53. J. Kivinen, M.K. Warmuth, Exponentiated gradient versus gradient descent for linear predictors. Inf. Comput. 132(1), 1–63 (1997) http://dx.doi.org/10.1006/inco.1996.2612
54. J. Langford, B. Zadrozny, Estimating class membership probabilities using classifier learners, in Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (2005)
55. Q.V. Le, A. Smola, Direct optimization of ranking measures. Technical report, NICTA, Canberra, Australia, 2007
56. G. Lebanon, J. Lafferty, Boosting and maximum likelihood for exponential models, in Advances in Neural Information Processing Systems, vol.14 (2001)
57. C. Mallows, Non-null ranking models. Biometrika 44(1/2), 114–130 (1957) http://dx.doi.org/10.2307/2333244
58. R.T. McDonald, K. Crammer, F.C.N. Pereira, Online large-margin training of dependency parsers, in Proceedings of the Forty-Third Annual Meeting of the Association for Computational Linguistics (2005)
59. N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, E. Teller, Equation of state calculation by fast computing machines. J. Chem. Phys. 21, 1087–1092 (1953) http://dx.doi.org/10.1063/1.1699114
60. N.J. Nilsson, Learning Machines: Foundations of Trainable Pattern-Classifying Systems (McGraw-Hill, New York, NY, USA, 1965)
61. J.G. Propp, D.B. Wilson, Exact sampling with coupled markov chains and applications to statistical mechanics. Random Struct. Algorithms 9(1–2), 223–252 (1996) http://dx.doi.org/10.1002/(SICI)1098-2418(199608/09)9%3A1/2%3C223%3A%3AAID-RSA14%3E3.0.CO%3B2-O
62. R. Rifkin, Everything Old Is New Again: A Fresh Look at Historical Approaches in Machine Learning. PhD thesis, Sloan School of Management Science, MIT, 2002
63. F. Rosenblatt, The perceptron: A probabilistic model for information storage and organization in the brain. Psychol. Rev. 65(6), 386–408 (1958) http://dx.doi.org/10.1037/h0042519
64. C. Rudin, Ranking with a p-norm push, in Proceedings of the 19th Annual Conference on Learning Theory (2006)
65. R.E. Schapire, Y. Singer, Improved boosting algorithms using confidence-rated predictions, in Proceedings of the Eleventh Annual Conference on Learning Theory (1998)
66. R.E. Schapire, Y. Singer, Boostexter: A boosting-based system for text categorization. Mach. Learn. 39(2/3), 135–168 (2000) http://dx.doi.org/10.1023/A%3A1007649029923
67. S. Shalev-Shwartz, Y. Singer, Efficient learning of label ranking by soft projections onto polyhedra. J. Mach. Learn. Res. 7, 1567–1599 (2006)
68. S. Shalev-Shwartz, Y. Singer, A primal-dual perspective of online learning algorithms. Mach. Learn. 69(2–3), 115–142 (2007) http://dx.doi.org/10.1007/s10994-007-5014-x
69. S. Shalev-Shwartz, Y. Singer, A unified algorithmic approach for efficient online label ranking, in Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (2007)
70. C. Spearman, The proof and measurement of association between two things. Am. J. Psychol. 15, 72–101 (1904) http://dx.doi.org/10.2307/1412159
71. J.A.K. Suykens, Multiclass least squares support vector machines, in Proceedings of the International Joint Conference on Neural Networks (1999)
72. J.A.K. Suykens, J.Vandewalle, Least squares support vector machine classifiers. Neural Process. Lett. 9(3), 293–300 (1999) http://dx.doi.org/10.1023/A%3A1018628609742
73. B. Taskar, V. Chatalbashev, D. Koller, C. Guestrin, Learning structured prediction models: A large margin approach, in Proceedings of the Twenty-Second International Conference on Machine Learning (2005)
74. B. Taskar, C. Guestrin, D. Koller, Max-margin Markov networks, in Advances in Neural Information Processing Systems, vol.16 (2003)
75. I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, Large margin methods for structured and interdependent output variables. J. Mach. Learn. Res. 6, 1453–1484 (2005)
76. A. van Zuylen, D.P. Williamson, Deterministic algorithms for rank aggregation and other ranking and clustering problems, in In Proceedings of the Fifth International Workshop on Approximation and Online Algorithms (2007)
77. S. Vembu, T. Gärtner, M. Boley, Probabilistic structured predictors, in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (2009)
78. S. Vembu, T. Gärtner, S. Wrobel, Semidefinite ranking on graphs, in Proceedings of the Fifth International Workshop on Mining and Learning with Graphs (2007)
Links
Full Text
http://www-kd.iai.uni-bonn.de/pubattachments/399/VembuG09Book.pdf
