Journal of Computers, Vol 6, No 11 (2011), 2302-2309, Nov 2011
doi:10.4304/jcp.6.11.2302-2309

A Co-Ranking Algorithm for Learning Listwise Ranking Functions from Unlabeled Data

Hai-jiang He

Abstract


In this paper, we propose a co-ranking algorithm that trains listwise ranking functions using unlabeled data simultaneously with a small number of labeled data. The co-ranking algorithm is based on the co-training paradigm that is a very common scheme in the semi-supervised classification framework. First, we use two listwise ranking methods to construct base ranker and assistant ranker, respectively, by learning from the current labeled set. Then we score documents of unlabeled query set by these rankers. For each newly labeled query, two ideal document permutations are obtained with different ranking functions. Thus, likelihood loss is employed to evaluate the similarity of two document permutations. At last we remove those queries having lower likelihood of document permutations from unlabeled set to labeled one. The former three steps are iterated until the ranking performance of base ranker begins to decrease on validation set. In this method, we assume that the unlabeled data follows the same generative distribution as the labeled data. The effectiveness of the presented co-ranking algorithm is demonstrated by experimental results on the benchmark datasets LETOR.


Keywords


information retrieval; learning to rank; semi-supervised learning; unlabeled data; listwise; likelihood loss

References


K. Dave, S. Lawrence, and D. M. Pennock, Mining the peanut gallery: opinion extraction and semantic classification of product reviews, Proceedings of the 12th International Conference on World Wide Web, Budapest, Hungary, 2003, pp. 519-528.

S. Verberne, H. van Halteren, D. Theijssen, S. Raaijmakers, and L. Boves, Learning to rank QA data, Proceedings of the Learning to Rank Workshop at SIGIR 2009, Boston, USA, 2009, pp. 41-48.

X. J. Zhu, Semi-supervised learning literature survey, Technical report, Computer Sciences, University of Wisconsin-Madison, 2008.

T.-Y. Liu, Learning to rank for information retrieval, Foundation and Trends on Information Retrieval, vol. 3, no 3, pp. 225-331, 2009.
http://dx.doi.org/10.1561/1500000016

F. Xia, T.-Y. Liu, J. Wang, and H. Li, Listwise approach to learning to rank: theory and algorithm, Proceedings of the 25th International Conference on Machine Learning, Helsinki, Finland, 2008, pp. 1192-1199.
http://dx.doi.org/10.1145/1390156.1390306

H.-J. He and J.-K. Zhu, A reduced listwise approach of learning to rank, Proceedings of 2nd International Conference on Computer Engineering and Technology, Chengdu, China, 2010, pp. V4 660-664.

T. Qin, T.-Y. Liu, J. Xu, and H. Li, LETOR: a benchmark collection for research on learning to rank for information retrieval, Information Retrieval, vol. 13, no 4, pp. 346-374, 2010.
http://dx.doi.org/10.1007/s10791-009-9123-y

P. Li, C. J. C. Burges, and Q. Wu, McRank: learning to rank using multiple classification and gradient boosting, Advances in Neural Information Processing Systems 2007, Vancouver, Canada, 2007, pp. 845-852.

W. Chu and S. S. Keerthi, Support vector ordinal regression, Neural Computation, vol. 19, no 3, pp. 792-815, 2007.
http://dx.doi.org/10.1162/neco.2007.19.3.792
PMid:17298234

Z. Sun, T. Qin, Q. Tao, and J. Wang, Robust sparse rank learning for non-smooth ranking measures, Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, Boston, USA, 2009, pp. 259-266.

N. Usunier, D. Buffoni, and P. Gallinari, Ranking with ordered weighted pairwise classification, Proceedings of the 26th International Conference on Machine Learning, Montreal, Canada, 2009, pp. 1057-1064.

H.-J. He, Smooth ranking support vector machine adapting to Web retrieval, Moshi Shibie yu Rengong Zhineng/Pattern Recognition and Artificial Intelligence, vol. 22, no 6, pp. 891-897, 2009. (in Chinese)

M. N. Volkovs and R. S. Zemel, BoltzRank: learning to maximize expected ranking gain, Proceedings of the 26th International Conference on Machine Learning, Montreal, Canada, 2009, pp. 1089-1096.

G. Haffari and A. Sarkar, Analysis of semi-supervised learning with the Yarowsky algorithm, Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence, Vancouver, BC, pp. 19-22, 2007.

Z.-H. Zhou and M. Li, Semi-supervised learning by disagreement. Knowledge and Information Systems, vol. 24, no 3, pp. 415-439, 2010.
http://dx.doi.org/10.1007/s10115-009-0209-z

M. R. Amini, T. V. Truong, and C. Goutte, A boosting algorithm for learning bipartite ranking functions with partially labeled data, Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Singapore, 2008, pp. 99-106.
http://dx.doi.org/10.1145/1390334.1390354

K. Duh and K. Kirchhoff, Learning to rank with partially-labeled data, Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Singapore, 2008, pp. 251-258.
http://dx.doi.org/10.1145/1390334.1390379

M. Li, H. Li, and Z.-H. Zhou, Semi-supervised document retrieval, Information Processing & Management, vol. 45, no 3, pp. 341-355, 2009.
http://dx.doi.org/10.1016/j.ipm.2008.11.002

B. Long, O. Chapelle, Y. Zhang, Y. Chang, Z.H. Zheng, and B. Tseng, Active learning for ranking through expected loss optimization, Proceeding of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval, Geneva, Switzerland, 2010, pp. 267-274.

N. Usunier, V. Truong, M. R. Amini, and P. Gallinari Ranking with unlabeled data: A first study, Proceedings of the NIPS 2005 Workshop on Learning to Rank, B.C., Canada, 2005, pp. 24-28.

Y.-X. Yuan, Step-sizes for the gradient method, Proceeding of the Third International Congress of Chinese Mathematicians, Hong Kong, China, 2004, pp. 785-796.

C. X. Zhai, Statistical language models for information retrieval: a critical review, Foundations and Trends in Information Retrieval, vol. 2, no 3, pp. 137–213, 2008.
http://dx.doi.org/10.1561/1500000008

K. Järvelin and J. Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems, vol. 20, no 4, pp. 422-226, 2002.
http://dx.doi.org/10.1145/582415.582418


Full Text: PDF


Journal of Computers (JCP, ISSN 1796-203X)

Copyright @ 2006-2012 by ACADEMY PUBLISHER – All rights reserved.