A boosting algorithm for learning bipartite ranking functions with partially labeled data

ABSTRACT

This paper presents a boosting based algorithm for learning a bipartite ranking function (BRF) with partially labeled data. Until now different attempts had been made to build a BRF in a transductive setting, in which the test points are given to the methods in advance as unlabeled data. The proposed approach is a semi-supervised inductive ranking algorithm which, as opposed to transductive algorithms, is able to infer an ordering on new examples that were not used for its training. We evaluate our approach using the TREC-9 Ohsumed and the Reuters-21578 data collections, comparing against two semi-supervised classification algorithms for ROCArea (AUC), uninterpolated average precision (AUP), mean precision@50 (TP) and Precision-Recall (PR) curves. In the most interesting cases where there are an unbalanced number of irrelevant examples over relevant ones, we show our method to produce statistically significant improvements with respect to these ranking measures.

REFERENCES

• 1: Shivani Agarwal, Ranking on graph data, Proceedings of the 23rd international conference on Machine learning, p.25-32, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143848]
• 2: Massih-Reza Amini , Patrick Gallinari, The use of unlabeled data to improve supervised learning for text summarization, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564397]
• 3: M.-R. Amini and P. Gallinari. Semi-Supervised Learning with Explicit Misclassification Modeling. In Proceedings of the 18th International Joint Conference on Artificial Intelligence, pages 555--560, 2003.
• 4: P. L. Bartlett, M. I. Jordan and Jon D. McAuliffe. Large Margin Classifiers: convex Loss, Low Noise and Convergence Rates. In Advances in Neural Information Processing Systems 16, pages 1173--1180, 2004.
• 5: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 6: A.P. Bradley. The use of the Area under the ROC curve in the Evaluation of Machine Learning Algorithms. Pattern Recognition, 30:1145--1159, 1997.
• 7: Rich Caruana , Alexandru Niculescu-Mizil, Data mining in metric space: an empirical analysis of supervised learning performance criteria, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014063]
• 8: O. Chapelle, B. Schölkopf and A. Zien. Semi-Supervised Learning, MIT Press, Cambridge, MA, 2006
• 9: C. Cortes and M. Mohri. AUC optimization vs. error rate minimization. In Advances in Neural Information Processing Systems 16, pages 313--320, 2004.
• 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: E. Gaussier and C. Goutte. Learning with Partially Labelled Data - with Confidence. In ICML'05 Workshop on Learning from Partially Classified Training Data (ICML'05-LPCT), pages 29--36, 2005.
• 12: William Hersh , Chris Buckley , T. J. Leone , David Hickam, OHSUMED: an interactive retrieval evaluation and new large test collection for research, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.192-201, July 03-06, 1994, Dublin, Ireland
• 13: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 14: E.L. Lehmann. Nonparametric Statistical Methods Based on Ranks. McGraw-Hill, New York, 1975.
• 15: D. D. Lewis. Reuters-21578, distribution 1.0 http://www.daviddlewis.com/resources/testcollections/reuters21578/. January 1997.
• 16: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 17: S. Robertson and D.A. Hull. The TREC-9 Filtering Track Final Report. In Proceedings of the 9th Text REtrieval Conference (TREC-9). pages 25--40, 2001.
• 18: Ian Soboroff , Stephen Robertson, Building a filtering test collection for TREC 2002, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860481]
• 19: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 20: Jean-Noël Vittaut , Massih-Reza Amini , Patrick Gallinari, Learning Classification with Both Labeled and Unlabeled Data, Proceedings of the 13th European Conference on Machine Learning, p.468-479, August 19-23, 2002
• 21: Christopher C. Vogt , Garrison W. Cottrell, Fusion Via a Linear Combination of Scores, Information Retrieval, v.1 n.3, p.151-173, October 1999 [doi>10.1023/A:1009980820262]
• 22: J. Weston, R. Kuang, C. Leslie and W.S. Noble. Protein ranking by semi-supervised network propagation. BMC Bioinformatics, special issue, 2006.
• 23: D. Zhou, J. Weston, A. Gretton, O. Bousquet and B. Schölkopf. Ranking on Data Manifolds. In Advances in Neural Information Processing Systems 16, pages 169--176, 2004.
• 24: Dengyong Zhou , Christopher J. C. Burges , Tao Tao, Transductive link spam detection, Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, May 08-08, 2007, Banff, Alberta, Canada [doi>10.1145/1244408.1244413]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.m Miscellaneous

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Theory

Keywords:
boosting, information routing, learning to rank with partially labeled data