Learning by Pairwise Comparison for Problems with Structured Output Spaces

• Applicants: Professor Dr. Johannes Fürnkranz; Professor Dr. Eyke Hüllermeier
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2007 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 39338330

• Final Report Year: 2014

Final Report Abstract

The goal of this project was a thorough investigation of pairwise decomposition techniques for a wide variety of machine learning tasks. The underlying motivation is the general observation that a pairwise comparison of two competing options and an indication of a preference between them is typically easier than the assessment of each of the individual option in terms of an absolute degree of utility. In the project, we have shown that many complex tasks in machine learning, such as label and instance ranking, multilabel classification, ordered classification, or hierarchical classification can be solved effectively based on the idea of pairwise decomposition. This is not only of theoretical interest but also of great practical relevance, because a decomposition of that kind allows one to solve these complex tasks with the help of binary classifiers, that is, to reduce them to binary classification, which by now constitutes the most basic and best understood machine learning problem. We have also developed a formal framework for the field of preference learning, which is based on such binary preference relations, and contributed to the rapid development of this field in recent years via a large number of scientific events, such as workshops, tutorials, invited talks, and, most importantly, through an edited volume on this topic, published by Springer in 2010.

Publications

• Binary decomposition methods for multipartite ranking. In W. L. Buntine, M. Grobelnik, D. Mladenić , and J. Shawe-Taylor, editors, Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD-09), Part I, pages 359–374, Bled, Slovenia, 2009. Springer-Verlag. 2009
  J. Fürnkranz, E. Hüllermeier, and Stijn Vanderlooy
  
• Combining instance-based learning and logistic regression for multilabel classification. Machine Learning, 76(2–3):211–225, 2009
  W. Cheng and E. Hüllermeier
  
• Combining predictions in pairwise classification: An optimal adaptive voting strategy and its relation to weighted voting. Pattern Recognition, 43(1):128–142, 2010
  E. Hüllermeier and S. Vanderlooy
  
• Efficient voting prediction for pairwise multilabel classification. Neurocomputing, 73(7-9):1164 – 1176, March 2010
  E. Loza Mencia, S.-H. Park, and J. Fürnkranz
  
• On exploiting hierarchical label structure with pairwise classifiers. SIGKDD Explorations, 12(2):21–25, 2010. Special Issue on Mining Unexpected Results
  J. Fürnkranz and Jan Frederik Sima
  
• On predictive accuracy and risk minimization in pairwise label ranking. Journal of Computer and System Sciences, 76(1):49–62, February 2010
  E. Hüllermeier and J. Fürnkranz
  
• Predicting partial orders: Ranking with abstention. In J. L. Balcázar, F. Bonchi, A. Gionis, and M. Sebag, editors, Proceedings of the Euorpean Conference on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD-10), Part I, pages 215–230, Barcelona, Spain, 2010. Springer
  W. Cheng, M. Rademaker, B. De Baets, and E. Hüllermeier
  
• Preference Learning. Springer-Verlag, 2010
  J. Fürnkranz and E. Hüllermeier, editors
  
• An exact algorithm for F-measure maximization. In Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS-11), Granada, Spain, 2011
  K. Dembczynski, W. Waegeman, W. Cheng, and E. Hüllermeier
  
• Consistent multilabel ranking through univariate losses. In Proceedings of the 29th International Conference on Machine Learning (ICML-12), Edinburgh, Scotland, UK, 2012. icml.cc / Omnipress
  K. Dembczynski, W. Kotlowski, and E. Hüllermeier
  
• Efficient prediction algorithms for binary decomposition techniques. Data Mining and Knowledge Discovery, 24(1):40–77, 2012
  S.-H. Park and J. Fürnkranz
  (See online at https://doi.org/10.1007/s10618-011-0219-9)
• Grouping, overlap, and generalized bientropic functions for fuzzy modeling of pairwise comparisons. IEEE Transactions on Fuzzy Systems, 20(3):405–415, 2012
  H. Bustince, M. Pagola, R. Mesiar, E. Hüllermeier, and F. Herrera
  (See online at https://doi.org/10.1109/TFUZZ.2011.2173581)
• Label ranking with partial abstention based on thresholded probabilistic models. In P. L. Bartlett, F. C. N. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS-12), pages 2510–2518, Lake Tahoe, Nevada, United States, 2012
  W. Cheng, E. Hüllermeier, W. Waegeman, and V. Welker
  
• On label dependence and loss minimization in multi-label classification. Machine Learning, 88(1-2):5–45, 2012
  K. Dembczynski, W. Waegeman, W. Cheng, and E. Hüllermeier
  (See online at https://doi.org/10.1007/s10994-012-5285-8)
• Probability estimation for multi-class classification based on label ranking. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD-12), Bristol, UK, 2012
  W. Cheng and E. Hüllermeier