nach oben

Erschienen in:

2011 | OriginalPaper | Buchkapitel

Label Ranking Algorithms: A Survey

verfasst von : Shankar Vembu, Thomas Gärtner

Erschienen in: Preference Learning

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Preference Optimization Based Unifying Framework for Supervised Learning Problems

Nächstes Kapitel Preference Learning and Ranking by Pairwise Comparison

A. Agarwal, S. Chakrabarti, Learning random walks to rank nodes in graphs, in Proceedings of the Twenty-Fourth International Conference on Machine Learning (2007)

S. Agarwal, Ranking on graph data, in Proceedings of the Twenty-Third International Conference on Machine Learning (2006)

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)

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)

D. Aldous, Random walks on finite groups and rapidly mixing markov chains. Séminaire de probabilités de Strasbourg 17, 243–297 (1983)MathSciNet

Y. Altun, T. Hofmann, M. Johnson, Discriminative learning for label sequences via boosting, in Advances in Neural Information Processing Systems, vol.15 (2002)

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)CrossRef

S. Boyd, L. Vandenberghe, Convex Optimization (Cambridge Univeristy Press, 2004)

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)MathSciNetMATH

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)MathSciNetMATH

19.

M. Collins, R.E. Schapire, Y. Singer, Logistic regression, AdaBoost and Bregman distances. Mach. Learn. 48(1–3), 253–285 (2002)MATHCrossRef

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)MATHCrossRef

22.

K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, Y. Singer, Online passive-aggressive algorithms. J. Mach. Learn. Res. 7, 551–585 (2006)MathSciNetMATH

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)MathSciNetMATH

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)MathSciNetMATHCrossRef

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)MathSciNetMATH

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)CrossRef

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)CrossRef

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)MathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

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)MathSciNetCrossRef

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)MathSciNetMATH

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)MathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

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)CrossRef

60.

N.J. Nilsson, Learning Machines: Foundations of Trainable Pattern-Classifying Systems (McGraw-Hill, New York, NY, USA, 1965)MATH

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)MathSciNetMATHCrossRef

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)MathSciNetCrossRef

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)MATHCrossRef

67.

S. Shalev-Shwartz, Y. Singer, Efficient learning of label ranking by soft projections onto polyhedra. J. Mach. Learn. Res. 7, 1567–1599 (2006)MathSciNetMATH

68.

S. Shalev-Shwartz, Y. Singer, A primal-dual perspective of online learning algorithms. Mach. Learn. 69(2–3), 115–142 (2007)CrossRef

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)CrossRef

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)MathSciNetCrossRef

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)MathSciNetMATH

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)

Titel: Label Ranking Algorithms: A Survey
verfasst von: Shankar Vembu
Thomas Gärtner
Verlag: Springer Berlin Heidelberg
Buch: Preference Learning
Print ISBN: 978-3-642-14124-9

Electronic ISBN: 978-3-642-14125-6

Copyright-Jahr: 2011
DOI: https://doi.org/10.1007/978-3-642-14125-6_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner