A support vector method for optimizing average precision

ABSTRACT

Machine learning is commonly used to improve ranked retrieval systems. Due to computational difficulties, few learning techniques have been developed to directly optimize for mean average precision (MAP), despite its widespread use in evaluating such systems. Existing approaches optimizing MAP either do not find a globally optimal solution, or are computationally expensive. In contrast, we present a general SVM learning algorithm that efficiently finds a globally optimal solution to a straightforward relaxation of MAP. We evaluate our approach using the TREC 9 and TREC 10 Web Track corpora (WT10g), comparing against SVMs optimized for accuracy and ROCArea. In most cases we show our method to produce statistically significant improvements in MAP scores.

REFERENCES

• 1: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 2: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 3: C. J. C. Burges, R. Ragno, and Q. Le. Learning to rank with non-smooth cost functions. In Proceedings of the International Conference on Advances in Neural Information Processing Systems (NIPS), 2006.
• 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: Ben Carterette , Desislava Petkova, Learning a ranking from pairwise preferences, 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.1148289]
• 6: Rich Caruana , Alexandru Niculescu-Mizil , Geoff Crew , Alex Ksikes, Ensemble selection from libraries of models, Proceedings of the twenty-first international conference on Machine learning, p.18, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015432]
• 7: Jesse Davis , Mark Goadrich, The relationship between Precision-Recall and ROC curves, Proceedings of the 23rd international conference on Machine learning, p.233-240, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143874]
• 8: D. Hawking. Overview of the TREC-9 web track. 2000.
• 9: D. Hawking and N. Craswell. Overview of the TREC-2001 web track. Nov. 2001.
• 10: Alexander J. Smola , Peter J. Bartlett, Advances in Large Margin Classifiers, MIT Press, Cambridge, MA, 2000
• 11: Alan Herschtal , Bhavani Raskutti, Optimising area under the ROC curve using gradient descent, Proceedings of the twenty-first international conference on Machine learning, p.49, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015366]
• 12: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 13: Thorsten Joachims, A support vector method for multivariate performance measures, Proceedings of the 22nd international conference on Machine learning, p.377-384, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102399]
• 14: John Lafferty , Chengxiang Zhai, Document language models, query models, and risk minimization for information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-119, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383970]
• 15: Yi Lin , Yoonkyung Lee , Grace Wahba, Support Vector Machines for Classification in Nonstandard Situations, Machine Learning, v.46 n.1-3, p.191-202, 2002 [doi>10.1023/A:1012406528296]
• 16: Donald Metzler , W. Bruce Croft, A Markov random field model for term dependencies, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076115]
• 17: Katharina Morik , Peter Brockhausen , Thorsten Joachims, Combining Statistical Learning with a Knowledge-Based Approach - A Case Study in Intensive Care Monitoring, Proceedings of the Sixteenth International Conference on Machine Learning, p.268-277, June 27-30, 1999
• 18: S. Robertson. The probability ranking principle in ir. journal of documentation. Journal of Documentation, 33(4):294--304, 1977.
• 19: 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
• 20: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 21: L. Yan, R. Dodier, M. Mozer, and R. Wolniewicz. Optimizing classifier performance via approximation to the Wilcoxon-Mann-Witney statistic. In Proceedings of the International Conference on Machine Learning (ICML), 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Experimentation, Theory

Keywords:
machine learning for information retrieval, ranking, support vector machines