Abstract
Bipartite ranking refers to the problem of learning a ranking function from a training set of positively and negatively labeled examples. Applied to a set of unlabeled instances, a ranking function is expected to establish a total order in which positive instances precede negative ones. The performance of a ranking function is typically measured in terms of the AUC. In this paper, we study the problem of multipartite ranking, an extension of bipartite ranking to the multi-class case. In this regard, we discuss extensions of the AUC metric which are suitable as evaluation criteria for multipartite rankings. Moreover, to learn multipartite ranking functions, we propose methods on the basis of binary decomposition techniques that have previously been used for multi-class and ordinal classification. We compare these methods both analytically and experimentally, not only against each other but also to existing methods applicable to the same problem.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allwein, E., Schapire, R., Singer, Y.: Reducing multiclass to binary: A unifying approach for margin classifiers. JMLR 1, 113–141 (2001)
Asuncion, A., Newman, D.: UCI machine learning repository (2007), http://www.ics.uci.edu/~mlearn/MLRepository.html
Ben David, A.: Ordinal real-world data sets repository (2008), http://www.cs.waikato.ac.nz/ml/weka/index_datasets.html
Cardoso, J., da Costa, J.P.: Learning to classify ordinal data: The data replication method. JMLR 8, 1393–1429 (2007)
Chu, W., Keerthi, S.: New approaches to support vector ordinal regression. In: Proceedings ICML, pp. 145–152. ACM, New York (2005)
Demsar, J.: Statistical comparisons of classifiers over multiple data sets. JMLR 7, 1–30 (2006)
Fawcett, T.: An introduction to ROC analysis. Pattern Recognition Letters 27(8), 861–874 (2006)
Frank, E., Hall, M.: A simple approach to ordinal classification. In: Flach, P.A., De Raedt, L. (eds.) ECML 2001. LNCS (LNAI), vol. 2167, pp. 145–156. Springer, Heidelberg (2001)
Fürnkranz, J.: Round robin classification. JMLR 2, 721–747 (2002)
Fürnkranz, J.: Round robin ensembles. Intelligent Data Analysis 7(5), 385–404 (2003)
Gnen, M., Heller, G.: Concordance probability and discriminatory power in proportional hazards regression. Biometrika 92(4), 965–970 (2005)
Hand, D., Till, R.: A simple generalization of the area under the ROC curve for multiple class problems. Machine Learning 45(2), 171–186 (2001)
Herbrich, R., Graepel, T., Obermayer, K.: Large margin rank boundaries for ordinal regression. In: Advances in Large Margin Classifiers, pp. 115–132. MIT Press, Cambridge (2000)
Higgins, J.: Introduction to Modern Nonparametric Statistics. Duxbury Press (2004)
Hühn, J., Hüllermeier, E.: Is an ordinal class structure useful in classifier learning? Int. J. Data Mining, Modelling and Management 1(1), 45–67 (2009)
Hüllermeier, E., Fürnkranz, J., Cheng, W., Brinker, K.: Label ranking by learning pairwise preferences. Artificial Intelligence 172, 1897–1917 (2008)
Joachims, T.: Optimizing Search Engines Using Clickthrough Data. In: Proceedings ACM SIGKDD, Edmonton, Alberta, Canad, pp. 133–142. ACM Press, New York (2002)
Joachims, T.: Training linear SVMs in linear time. In: Proceedings ACM SIGKDD, Philadelphia, PA, USA, pp. 217–226. ACM Press, New York (2006)
Kramer, S., Widmer, G., Pfahringer, B., De Groeve, M.: Prediction of ordinal classes using regression trees. Fundamenta Informaticae 34(1-2), 1–15 (2000)
Rajaram, S., Agarwal, S.: Generalization bounds for k-partite ranking. In: Proceedings of the NIPS 2005 Workshop on Learning to Rank, Whistler, BC, Canada, pp. 28–23 (2005)
Shashua, A., Levin, A.: Ranking with large margin principle: Two approaches. In: Advances in NIPS, vol. 15, pp. 937–944. MIT Press, Cambridge (2002)
Waegeman, W., Baets, B.D., Boullart, L.: ROC analysis in ordinal regression learning. Pattern Recognition Letters 29(1), 1–9 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fürnkranz, J., Hüllermeier, E., Vanderlooy, S. (2009). Binary Decomposition Methods for Multipartite Ranking. In: Buntine, W., Grobelnik, M., Mladenić, D., Shawe-Taylor, J. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2009. Lecture Notes in Computer Science(), vol 5781. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04180-8_41
Download citation
DOI: https://doi.org/10.1007/978-3-642-04180-8_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04179-2
Online ISBN: 978-3-642-04180-8
eBook Packages: Computer ScienceComputer Science (R0)