More Web Proxy on the site http://driver.im/

article

Label ranking by learning pairwise preferences

Authors:

Eyke Hüllermeier,

Johannes Fürnkranz,

Klaus BrinkerAuthors Info & Claims

Artificial Intelligence, Volume 172, Issue 16-17

Pages 1897 - 1916

https://doi.org/10.1016/j.artint.2008.08.002

Published: 01 November 2008 Publication History

Abstract

Preference learning is an emerging topic that appears in different guises in the recent literature. This work focuses on a particular learning scenario called label ranking, where the problem is to learn a mapping from instances to rankings over a finite number of labels. Our approach for learning such a mapping, called ranking by pairwise comparison (RPC), first induces a binary preference relation from suitable training data using a natural extension of pairwise classification. A ranking is then derived from the preference relation thus obtained by means of a ranking procedure, whereby different ranking methods can be used for minimizing different loss functions. In particular, we show that a simple (weighted) voting strategy minimizes risk with respect to the well-known Spearman rank correlation. We compare RPC to existing label ranking methods, which are based on scoring individual labels instead of comparing pairs of labels. Both empirically and theoretically, it is shown that RPC is superior in terms of computational efficiency, and at least competitive in terms of accuracy.

References

[1]

Aiolli, Fabio, A preference model for structured supervised learning tasks. In: Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM-05), IEEE Computer Society. pp. 557-560.

Digital Library

[2]

Allwein, Erin L., Schapire, Robert E. and Singer, Yoram, Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of Machine Learning Research. v1. 113-141.

Digital Library

[3]

Noga Alon, Ranking tournaments, SIAM Journal on Discrete Mathematics 20 (1), pp. 137--142

Digital Library

[4]

Balasubramaniyan, Rajarajeswari, Hüllermeier, Eyke, Weskamp, Nils and Kämper, Jörg, Clustering of gene expression data using a local shape-based similarity measure. Bioinformatics. v21 i7. 1069-1077.

[5]

Bartholdi III, John J., Tovey, Craig A. and Trick, Michael A., Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare. v6 i2. 157-165.

[6]

Catherine L. Blake, Christopher J. Merz, UCI repository of machine learning databases, 1998; Data available at http://www.ics.uci.edu/~mlearn/MLRepository.html

[7]

Boutilier, Craig, Brafman, Ronen, Domshlak, Carmel, Hoos, Holger and Poole, David, CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research. v21. 135-191.

[8]

Bradley, Ralph A. and Terry, Milton E., The rank analysis of incomplete block designs---I. The method of paired comparisons. Biometrika. v39. 324-345.

[9]

Brams, Steven J. and Fishburn, Peter C., Voting procedures. In: Arrow, K.J., Sen, A.K., Suzumura, K. (Eds.), Handbook of Social Choice and Welfare (vol. 1), Elsevier.

[10]

Brazdil, Pavel B., Soares, Carlos and da Costa, J.P., Ranking learning algorithms: Using IBL and meta-learning on accuracy and time results. Machine Learning. v50 i3. 251-277.

[11]

Klaus Brinker, Johannes Fürnkranz, Eyke Hüllermeier, A unified model for multilabel classification and ranking, in: Proceedings of the 17th European Conference on Artificial Intelligence (ECAI-06), 2006, pp. 489--493

[12]

Klaus Brinker, Johannes Fürnkranz, Eyke Hüllermeier, Label ranking by learning pairwise preferences, Technical Report TUD-KE-2007-01, Knowledge Engineering Group, TU Darmstadt, 2007

[13]

Cohen, William W., Schapire, Robert E. and Singer, Yoram, Learning to order things. Journal of Artificial Intelligence Research. v10. 243-270.

[14]

Don Coppersmith, Lisa Fleischer, and Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, in: Proceedings of the ACM--SIAM Symposium on Discrete Algorithms (SODA), 2006, pp. 776--782

[15]

Crammer, Koby and Singer, Yoram, Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research. v3. 951-991.

Digital Library

[16]

Crammer, Koby and Singer, Yoram, A family of additive online algorithms for category ranking. Journal of Machine Learning Research. v3. 1025-1058.

[17]

Dekel, Ofer, Manning, Christopher D. and Singer, Yoram, Log-linear models for label ranking. In: Thrun, S., Saul, L.K., Schölkopf, B. (Eds.), Advances in Neural Information Processing Systems 16 (NIPS-2003), MIT Press.

[18]

Dietterich, Thomas G. and Bakiri, Ghulum, Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research. v2. 263-286.

[19]

Doyle, Jon, Prospects for preferences. Computational Intelligence. v20 i2. 111-136.

[20]

Fodor, János and Roubens, Marc, Fuzzy Preference Modelling and Multicriteria Decision Support. 1994. Kluwer Academic Publishers.

[21]

Jerome H. Friedman, Another approach to polychotomous classification. Technical report, Department of Statistics, Stanford University, Stanford, CA, 1996

[22]

Fürnkranz, Johannes, Round robin classification. Journal of Machine Learning Research. v2. 721-747.

[23]

Fürnkranz, Johannes, Round robin ensembles. Intelligent Data Analysis. v7 i5. 385-404.

[24]

Fürnkranz, Johannes and Hüllermeier, Eyke, Pairwise preference learning and ranking. In: Lavrač, N., Gamberger, D., Blockeel, H., Todorovski, L. (Eds.), Lecture Notes in Artificial Intelligence, vol. 2837. Springer-Verlag.

[25]

Fürnkranz, Johannes and Hüllermeier, Eyke, Preference learning. Künstliche Intelligenz. v19 i1. 60-61.

[26]

Ha, Vu and Haddawy, Peter, Similarity of personal preferences: Theoretical foundations and empirical analysis. Artificial Intelligence. v146. 149-173.

Digital Library

[27]

Haddawy, Peter, Ha, Vu, Restificar, Angelo, Geisler, Benjamin and Miyamoto, John, Preference elicitation via theory refinement. Journal of Machine Learning Research. v4. 317-337.

[28]

Har-Peled, Sariel, Roth, Dan and Zimak, Dav, Constraint classification: A new approach to multiclass classification. In: Cesa-Bianchi, N., Numao, M., Reischuk, R. (Eds.), Proceedings of the 13th International Conference on Algorithmic Learning Theory (ALT-02), Springer. pp. 365-379.

[29]

Sariel Har-Peled, Dan Roth, Dav Zimak, Constraint classification for multiclass classification and ranking, in: Suzanna Becker, Sebastian Thrun, Klaus Obermayer (Eds.), Advances in Neural Information Processing Systems 15 (NIPS-02), 2003, pp. 785--792

[30]

Hastie, Trevor and Tibshirani, Robert, Classification by pairwise coupling. In: Jordan, M.I., Kearns, M.J., Solla, S.A. (Eds.), Advances in Neural Information Processing Systems 10 (NIPS-97), MIT Press. pp. 507-513.

[31]

Ralf Herbrich, Thore Graepel, Peter Bollmann-Sdorra, Klaus Obermayer, Supervised learning of preference relations, in: Proceedings des Fachgruppentreffens Maschinelles Lernen (FGML-98), 1998, pp. 43--47

[32]

Hsu, Chih-Wei and Lin, Chih-Jen, A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks. v13 i2. 415-425.

[33]

Eyke Hüllermeier, Johannes Fürnkranz, Ranking by pairwise comparison: A note on risk minimization, in: Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE-04), Budapest, Hungary, 2004

[34]

Eyke Hüllermeier, Johannes 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

[35]

Joachims, Thorsten, Optimizing search engines using clickthrough data. In: Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-02), ACM Press. pp. 133-142.

[36]

Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, Geri Gay, Accurately interpreting clickthrough data as implicit feedback, in: Proceedings of the 28th Annual International ACM Conference on Research and Development in Information Retrieval (SIGIR-05), 2005

[37]

Khardon, Roni and Wachman, Gabriel, Noise tolerant variants of the perceptron algorithm. The Journal of Machine Learning Research. v8. 227-248.

[38]

Kendall, Maurice G., Rank Correlation Methods. 1955. Charles Griffin, London.

[39]

Klement, Erich-Peter, Mesiar, Radko and Pap, Endre, Triangular Norms. 2002. Kluwer Academic Publishers.

[40]

Knerr, Stefan, Personnaz, Léon and Dreyfus, Gérard, Single-layer learning revisited: A stepwise procedure for building and training a neural network. In: Fogelman Soulié, F., Hérault, J. (Eds.), NATO ASI Series, vol. F68. Springer-Verlag. pp. 41-50.

[41]

Knerr, Stefan, Personnaz, Léon and Dreyfus, Gérard, Handwritten digit recognition by neural networks with single-layer training. IEEE Transactions on Neural Networks. v3 i6. 962-968.

[42]

Kreßel, Ulrich H.-G., Pairwise classification and support vector machines. In: Schölkopf, B., Burges, C.J.C., Smola, A.J. (Eds.), Advances in Kernel Methods: Support Vector Learning, MIT Press, Cambridge, MA. pp. 255-268.

[43]

Lehmann, Erich L. and D'Abrera, H.J.M., Nonparametrics: Statistical Methods Based on Ranks. 1998. rev. ed. Prentice-Hall, Englewood Cliffs, NJ.

[44]

Lu, Bao-Liang and Ito, Masami, Task decomposition and module combination based on class relations: A modular neural network for pattern classification. IEEE Transactions on Neural Networks. v10 i5. 1244-1256.

[45]

Marden, John I., Analyzing and Modeling Rank data. 1995. Chapman & Hall, London.

[46]

Michie, Donald, Spiegelhalter, David J. and Taylor, C.C., Machine Learning, Neural and Statistical Classification. 1994. Ellis Horwood.

[47]

Naessens, Helga, De Meyer, Hans and De Baets, Bernard, Algorithms for the computation of T-transitive closures. IEEE Trans. Fuzzy Syst. v10. 541-551.

Digital Library

[48]

Park, Sang-Hyeun and Fürnkranz, Johannes, Efficient Pairwise Classification. In: Proceedings of the 17th European Conference on Machine Learning (ECML-07), Springer-Verlag. pp. 658-665.

[49]

Edgar Pimenta, João Gama, André Carvalho, Pursuing the best ECOC dimension for multiclass problems, in: Proceedings of the 20th International Florida Artificial Intelligence Research Society Conference (FLAIRS-07), 2007, pp. 622--627

[50]

Platt, John, Probabilistic outputs for support vector machines and comparison to regularized likelihood methods. In: Smola, A.J., Bartlett, P., Schoelkopf, B., Schuurmans, D. (Eds.), Advances in Large Margin Classifiers, MIT Press. pp. 61-74.

[51]

Price, David, Knerr, Stefan, Personnaz, Léon and Dreyfus, Gérard, Pairwise neural network classifiers with probabilistic outputs. In: Tesauro, G., Touretzky, D., Leen, T. (Eds.), Advances in Neural Information Processing Systems 7 (NIPS-94), MIT Press. pp. 1109-1116.

[52]

Filip Radlinski, Thorsten Joachims, Learning to rank from implicit feedback, in: Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD-05), 2005

[53]

Rifkin, Ryan and Klautau, Aldebaro, In defense of one-vs-all classification. Journal of Machine Learning Research. v5. 101-141.

Digital Library

[54]

Michael S. Schmidt, Herbert Gish, Speaker identification via support vector classifiers, in: Proceedings of the 21st IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP-96), Atlanta, GA, 1996, pp. 105--108

Digital Library

[55]

Schweizer, B. and Sklar, A., Probabilistic Metric Spaces. 1983. North-Holland, New York.

[56]

Shalev-Shwartz, Shai and Singer, Yoram, Efficient learning of label ranking by soft projections onto polyhedra. Journal of Machine Learning Research. v7. 1567-1599.

[57]

Spearman, Charles, The proof and measurement of association between two things. American Journal of Psychology. v15. 72-101.

[58]

Tesauro, Gerald, Connectionist learning of expert preferences by comparison training. In: Touretzky, D. (Ed.), Advances in Neural Information Processing Systems 1 (NIPS-88), Morgan Kaufmann. pp. 99-106.

[59]

Usunier, Nicolas, Amini, Massih-Reza and Gallinari, Patrick, Generalization error bounds for classifiers trained with interdependent data. In: Weiss, Y., Schölkopf, B., Platt, J. (Eds.), Advances in Neural Information Processing Systems 18 (NIPS 2005), MIT Press. pp. 1369-1376.

[60]

Wang, Jun, Artificial neural networks versus natural neural networks: A connectionist paradigm for preference assessment. Decision Support Systems. v11. 415-429.

Digital Library

[61]

Witten, Ian H. and Frank, Eibe, Data Mining: Practical Machine Learning Tools with Java Implementations. 2000. Morgan Kaufmann, San Francisco.

[62]

Wu, Ting-Fan, Lin, Chih-Jen and Weng, Ruby C., Probability estimates for multi-class classification by pairwise coupling. Journal of Machine Learning Research. v5 iAug. 975-1005.

Cited By

Zhou YHao JLi Z(2024)Heuristic Search for Rank Aggregation with Application to Label RankingINFORMS Journal on Computing10.1287/ijoc.2022.001936:2(308-326)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0019
Grgić-Hlača NAli JGummadi KWortman Vaughan J(2024)(De)Noise: Moderating the Inconsistency Between Human Decision-MakersProceedings of the ACM on Human-Computer Interaction10.1145/36869878:CSCW2(1-38)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.1145/3686987
Diop AEl Malki NChevalier MPéninou AGeoffrey RTeste O(2024)Similarity Measures Recommendation for Mixed Data ClusteringProceedings of the 36th International Conference on Scientific and Statistical Database Management10.1145/3676288.3676302(1-10)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3676288.3676302
Show More Cited By

Index Terms

Label ranking by learning pairwise preferences

Recommendations

On predictive accuracy and risk minimization in pairwise label ranking

We study the problem of label ranking, a machine learning task that consists of inducing a mapping from instances to rankings over a finite number of labels. Our learning method, referred to as ranking by pairwise comparison (RPC), first induces ...
Multilabel classification via calibrated label ranking

Label ranking studies the problem of learning a mapping from instances to rankings over a predefined set of labels. Hitherto existing approaches to label ranking implicitly operate on an underlying (utility) scale which is not calibrated in the sense ...
Pairwise learning for the partial label ranking problem
Highlights
- The partial label ranking problem is an exciting learning scenario for non-standard supervised classification problems (e.g., multi-label).
Abstract
The partial label ranking problem is a particular preference learning scenario that focuses on learning preference models from data, such that they predict a complete ranking with ties defined over the values of the class variable for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 172, Issue 16-17

November, 2008

104 pages

ISSN:0004-3702

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2008.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 November 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

157
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou YHao JLi Z(2024)Heuristic Search for Rank Aggregation with Application to Label RankingINFORMS Journal on Computing10.1287/ijoc.2022.001936:2(308-326)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0019
Grgić-Hlača NAli JGummadi KWortman Vaughan J(2024)(De)Noise: Moderating the Inconsistency Between Human Decision-MakersProceedings of the ACM on Human-Computer Interaction10.1145/36869878:CSCW2(1-38)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.1145/3686987
Diop AEl Malki NChevalier MPéninou AGeoffrey RTeste O(2024)Similarity Measures Recommendation for Mixed Data ClusteringProceedings of the 36th International Conference on Scientific and Statistical Database Management10.1145/3676288.3676302(1-10)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3676288.3676302
Lyu HBai YLiang XDas UShi CGong LLi YSun MGe MMa X(2024)FARPLS: A Feature-Augmented Robot Trajectory Preference Labeling System to Assist Human Labelers’ Preference ElicitationProceedings of the 29th International Conference on Intelligent User Interfaces10.1145/3640543.3645145(344-369)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1145/3640543.3645145
Morinaga DAkimoto YLi XHandl J(2024)Sign-Averaging Covariance Matrix Adaptation Evolution StrategyProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654065(694-702)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654065
Teng ZCao PHuang MGao ZWang X(2024)Multi-label borderline oversampling techniquePattern Recognition10.1016/j.patcog.2023.109953145:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.patcog.2023.109953
Li HFang MLi HWang P(2024)Prototype selection for multi-label data based on label correlationNeural Computing and Applications10.1007/s00521-023-08617-736:5(2121-2130)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00521-023-08617-7
Kim JShin JKang DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Prefer to classifyProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619099(16807-16828)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619099
Mehmood FShahzadi RGhafoor HAsim MGhani MMahmood WDengel A(2023)EnML: Multi-label Ensemble Learning for Urdu Text ClassificationACM Transactions on Asian and Low-Resource Language Information Processing10.1145/361611122:9(1-31)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1145/3616111
Ma JSun HZhu T(2023)Multiview Multilabel Classification With Group-Based Feature and Label SelectionIEEE Transactions on Consumer Electronics10.1109/TCE.2023.327845770:1(3308-3317)Online publication date: 22-May-2023
https://dl.acm.org/doi/10.1109/TCE.2023.3278457
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents