Ranking with ordered weighted pairwise classification

ABSTRACT

In ranking with the pairwise classification approach, the loss associated to a predicted ranked list is the mean of the pairwise classification losses. This loss is inadequate for tasks like information retrieval where we prefer ranked lists with high precision on the top of the list. We propose to optimize a larger class of loss functions for ranking, based on an ordered weighted average (OWA) (Yager, 1988) of the classification losses. Convex OWA aggregation operators range from the max to the mean depending on their weights, and can be used to focus on the top ranked elements as they give more weight to the largest losses. When aggregating hinge losses, the optimization problem is similar to the SVM for interdependent output spaces. Moreover, we show that OWA aggregates of margin-based classification losses have good generalization properties. Experiments on the Letor 3.0 benchmark dataset for information retrieval validate our approach.

REFERENCES

• 1: Antoine Bordes , Léon Bottou , Patrick Gallinari , Jason Weston, Solving multiclass support vector machines with LaRank, Proceedings of the 24th international conference on Machine learning, p.89-96, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273508]
• 2: Antoine Bordes , Nicolas Usunier , Léon Bottou, Sequence Labelling SVMs Trained in One Pass, Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87479-9_28]
• 3: Burges, C. J. C., Ragno, R., & Le, Q. V. (2006). Learning to rank with nonsmooth cost functions. Proc. of Adv. in Neural Inf. Processing Syst. (pp. 193--200).
• 4: Yunbo Cao , Jun Xu , Tie-Yan Liu , Hang Li , Yalou Huang , Hsiao-Wuen Hon, Adapting ranking SVM to document retrieval, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148205]
• 5: Zhe Cao , Tao Qin , Tie-Yan Liu , Ming-Feng Tsai , Hang Li, Learning to rank: from pairwise approach to listwise approach, Proceedings of the 24th international conference on Machine learning, p.129-136, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273513]
• 6: Cossock, D., & Zhang, T. (2006). Subset ranking using regression. Proc. of Comp. Learn. Theory (pp. 605--619).
• 7: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 8: Cucker, F., & Smale, S. (2002). On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 39, 1--49.
• 9: Do, C. B., Le, Q., Chapelle, O., & Smola, A. (2008). Tighter bounds for structured estimation. Proc. of Adv. in Neural Inf. Processing Syst. (pp. 281--288).
• 10: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 11: Har-Peled, S., Roth, D., & Zimak, D. (2002). Constraint classification for multiclass classification and ranking. Proc. of Adv. in Neural Inf. Processing Syst. (pp. 785--792).
• 12: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 13: Yanyan Lan , Tie-Yan Liu , Tao Qin , Zhiming Ma , Hang Li, Query-level stability and generalization in learning to rank, Proceedings of the 25th international conference on Machine learning, p.512-519, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390221]
• 14: Le, Q. V., & Smola, A. J. (2007). Direct optimization of ranking measures (Technical Report). NICTA.
• 15: Liu, T.-Y., & Lan, Y. (2008). Generalization analysis of listwise learning-to-rank algorithms using rademacher average (Technical Report MSR-TR-2008-155). Microsoft Res.
• 16: Liu, T.-Y., Xu, J., Qin, T., Xiong, W., & Li, H. (2007). Letor: Benchmark dataset for research on learning to rank for information retrieval. Proc. of SIGIR'07 workshop on Learning to Rank for Inf. Ret..
• 17: Christopher D. Manning , Prabhakar Raghavan , Hinrich Schtze, Introduction to Information Retrieval, Cambridge University Press, New York, NY, 2008
• 18: Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: a new explanation for the effectiveness of voting methods. Annals of Statistics, 26, 322--330.
• 19: Michael Taylor , John Guiver , Stephen Robertson , Tom Minka, SoftRank: optimizing non-smooth rank metrics, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341544]
• 20: Ioannis Tsochantaridis , Thorsten Joachims , Thomas Hofmann , Yasemin Altun, Large Margin Methods for Structured and Interdependent Output Variables, The Journal of Machine Learning Research, 6, p.1453-1484, 12/1/2005
• 21: Jun Xu , Hang Li, AdaRank: a boosting algorithm for information retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277809]
• 22: Jun Xu , Tie-Yan Liu , Min Lu , Hang Li , Wei-Ying Ma, Directly optimizing evaluation measures in learning to rank, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390355]
• 23: Ronald R. Yager, On ordered weighted averaging aggregation operators in multicriteria decisionmaking, IEEE Transactions on Systems, Man and Cybernetics, v.18 n.1, p.183-190, January/February 1988 [doi>10.1109/21.87068]
• 24: Yisong Yue , Thomas Finley , Filip Radlinski , Thorsten Joachims, A support vector method for optimizing average precision, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277790]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Experimentation, Performance, Theory