Yisong Yue
Filip Radlinski
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.
- B. T. Bartell, G. W. Cottrell, and R. K. Belew. Automatic combination of multiple ranked retrieval systems. In Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR), 1994. Google Scholar
Digital Library
- C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to rank using gradient descent. In Proceedings of the International Conference on Machine Learning (ICML), 2005. Google ScholarDigital Library
- 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.Google Scholar
- Y. Cao, J. Xu, T.-Y. Liu, H. Li, Y. Huang, and H.-W. Hon. Adapting ranking SVM to document retrieval. In Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR), 2006. Google ScholarDigital Library
- B. Carterette and D. Petkova. Learning a ranking from pairwise preferences. In Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR), 2006. Google ScholarDigital Library
- R. Caruana, A. Niculescu-Mizil, G. Crew, and A. Ksikes. Ensemble selection from libraries of models. In Proceedings of the International Conference on Machine Learning (ICML), 2004. Google ScholarDigital Library
- J. Davis and M. Goadrich. The relationship between precision-recall and ROC curves. In Proceedings of the International Conference on Machine Learning (ICML), 2006. Google ScholarDigital Library
- D. Hawking. Overview of the TREC-9 web track. 2000.Google Scholar
- D. Hawking and N. Craswell. Overview of the TREC-2001 web track. Nov. 2001.Google Scholar
- R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. Advances in large margin classifiers, 2000. Google ScholarDigital Library
- A. Herschtal and B. Raskutti. Optimising area under the ROC curve using gradient descent. In Proceedings of the International Conference on Machine Learning (ICML), 2004. Google ScholarDigital Library
- K. Jarvelin and J. Kekalainen. Ir evaluation methods for retrieving highly relevant documents. In Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR), 2000. Google ScholarDigital Library
- T. Joachims. A support vector method for multivariate performance measures. In Proceedings of the International Conference on Machine Learning (ICML), pages 377--384, New York, NY, USA, 2005. ACM Press. Google ScholarDigital Library
- J. Lafferty and C. Zhai. Document language models, query models, and risk minimization for information retrieval. In Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR), pages 111--119, 2001. Google ScholarDigital Library
- Y. Lin, Y. Lee, and G. Wahba. Support vector machines for classification in nonstandard situations. Machine Learning, 46:191--202, 2002. Google ScholarDigital Library
- D. Metzler and W. B. Croft. A markov random field model for term dependencies. In Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 472--479, 2005. Google ScholarDigital Library
- K. Morik, P. Brockhausen, and T. Joachims. Combining statistical learning with a knowledge-based approach. In Proceedings of the International Conference on Machine Learning, 1999. Google ScholarDigital Library
- S. Robertson. The probability ranking principle in ir. journal of documentation. Journal of Documentation, 33(4):294--304, 1977.Google ScholarCross Ref
- I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research (JMLR), pages 1453--1484, 2005. Google ScholarDigital Library
- V. Vapnik. Statistical Learning Theory. Wiley and Sons Inc., 1998. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- A support vector method for optimizing average precision
Recommendations
An overview on twin support vector machines
Twin support vector machines (TWSVM) is based on the idea of proximal SVM based on generalized eigenvalues (GEPSVM), which determines two nonparallel planes by solving two related SVM-type problems, so that its computing cost in the training phase is 1/...
Self-Universum support vector machine
In this paper, for an improved twin support vector machine (TWSVM), we give it a theoretical explanation based on the concept of Universum and then name it Self-Universum support vector machine (SUSVM). For the binary classification problem, SUSVM takes ...
Incremental training of support vector machines using hyperspheres
In the conventional incremental training of support vector machines, candidates for support vectors tend to be deleted if the separating hyperplane rotates as the training data are added. To solve this problem, in this paper, we propose an incremental ...
Comments