Online Learning to Rank with Feedback at the Top

Sougata Chaudhuri, Ambuj Tewari Tewari
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:277-285, 2016.

Abstract

We consider an online learning to rank setting in which, at each round, an oblivious adversary generates a list of m documents, pertaining to a query, and the learner ranks the documents according to assigned scores. The adversary then generates a relevance vector and the learner updates its ranker according to the feedback received. We consider the setting where the feedback is restricted to be the relevance levels of only the top k documents in the ranked list, for k ≪m. However, the performance of learner is judged based on the unrevealed full relevance vectors, using an appropriate learning to rank loss function. We develop efficient algorithms for well known losses in the pointwise, pairwise and listwise families. We also prove that no online algorithm can have sublinear regret, with top 1 feedback, for any loss that is calibrated with respect to NDCG. We apply our algorithms on benchmark datasets demonstrating efficient online learning of a ranking function from highly restricted feedback.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-chaudhuri16, title = {Online Learning to Rank with Feedback at the Top}, author = {Chaudhuri, Sougata and Tewari, Ambuj Tewari}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {277--285}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/chaudhuri16.pdf}, url = {https://proceedings.mlr.press/v51/chaudhuri16.html}, abstract = {We consider an online learning to rank setting in which, at each round, an oblivious adversary generates a list of m documents, pertaining to a query, and the learner ranks the documents according to assigned scores. The adversary then generates a relevance vector and the learner updates its ranker according to the feedback received. We consider the setting where the feedback is restricted to be the relevance levels of only the top k documents in the ranked list, for k ≪m. However, the performance of learner is judged based on the unrevealed full relevance vectors, using an appropriate learning to rank loss function. We develop efficient algorithms for well known losses in the pointwise, pairwise and listwise families. We also prove that no online algorithm can have sublinear regret, with top 1 feedback, for any loss that is calibrated with respect to NDCG. We apply our algorithms on benchmark datasets demonstrating efficient online learning of a ranking function from highly restricted feedback.} }
Endnote
%0 Conference Paper %T Online Learning to Rank with Feedback at the Top %A Sougata Chaudhuri %A Ambuj Tewari Tewari %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-chaudhuri16 %I PMLR %P 277--285 %U https://proceedings.mlr.press/v51/chaudhuri16.html %V 51 %X We consider an online learning to rank setting in which, at each round, an oblivious adversary generates a list of m documents, pertaining to a query, and the learner ranks the documents according to assigned scores. The adversary then generates a relevance vector and the learner updates its ranker according to the feedback received. We consider the setting where the feedback is restricted to be the relevance levels of only the top k documents in the ranked list, for k ≪m. However, the performance of learner is judged based on the unrevealed full relevance vectors, using an appropriate learning to rank loss function. We develop efficient algorithms for well known losses in the pointwise, pairwise and listwise families. We also prove that no online algorithm can have sublinear regret, with top 1 feedback, for any loss that is calibrated with respect to NDCG. We apply our algorithms on benchmark datasets demonstrating efficient online learning of a ranking function from highly restricted feedback.
RIS
TY - CPAPER TI - Online Learning to Rank with Feedback at the Top AU - Sougata Chaudhuri AU - Ambuj Tewari Tewari BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-chaudhuri16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 277 EP - 285 L1 - http://proceedings.mlr.press/v51/chaudhuri16.pdf UR - https://proceedings.mlr.press/v51/chaudhuri16.html AB - We consider an online learning to rank setting in which, at each round, an oblivious adversary generates a list of m documents, pertaining to a query, and the learner ranks the documents according to assigned scores. The adversary then generates a relevance vector and the learner updates its ranker according to the feedback received. We consider the setting where the feedback is restricted to be the relevance levels of only the top k documents in the ranked list, for k ≪m. However, the performance of learner is judged based on the unrevealed full relevance vectors, using an appropriate learning to rank loss function. We develop efficient algorithms for well known losses in the pointwise, pairwise and listwise families. We also prove that no online algorithm can have sublinear regret, with top 1 feedback, for any loss that is calibrated with respect to NDCG. We apply our algorithms on benchmark datasets demonstrating efficient online learning of a ranking function from highly restricted feedback. ER -
APA
Chaudhuri, S. & Tewari, A.T.. (2016). Online Learning to Rank with Feedback at the Top. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:277-285 Available from https://proceedings.mlr.press/v51/chaudhuri16.html.

Related Material