Extreme Learning to Rank via Low Rank Assumption

Minhao Cheng, Ian Davidson, Cho-Jui Hsieh
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:951-960, 2018.

Abstract

We consider the setting where we wish to perform ranking for hundreds of thousands of users which is common in recommender systems and web search ranking. Learning a single ranking function is unlikely to capture the variability across all users while learning a ranking function for each person is time-consuming and requires large amounts of data from each user. To address this situation, we propose a Factorization RankSVM algorithm which learns a series of k basic ranking functions and then constructs for each user a local ranking function that is a combination of them. We develop a fast algorithm to reduce the time complexity of gradient descent solver by exploiting the low-rank structure, and the resulting algorithm is much faster than existing methods. Furthermore, we prove that the generalization error of the proposed method can be significantly better than training individual RankSVMs. Finally, we present some interesting patterns in the principal ranking functions learned by our algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-cheng18a, title = {Extreme Learning to Rank via Low Rank Assumption}, author = {Cheng, Minhao and Davidson, Ian and Hsieh, Cho-Jui}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {951--960}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/cheng18a/cheng18a.pdf}, url = {https://proceedings.mlr.press/v80/cheng18a.html}, abstract = {We consider the setting where we wish to perform ranking for hundreds of thousands of users which is common in recommender systems and web search ranking. Learning a single ranking function is unlikely to capture the variability across all users while learning a ranking function for each person is time-consuming and requires large amounts of data from each user. To address this situation, we propose a Factorization RankSVM algorithm which learns a series of k basic ranking functions and then constructs for each user a local ranking function that is a combination of them. We develop a fast algorithm to reduce the time complexity of gradient descent solver by exploiting the low-rank structure, and the resulting algorithm is much faster than existing methods. Furthermore, we prove that the generalization error of the proposed method can be significantly better than training individual RankSVMs. Finally, we present some interesting patterns in the principal ranking functions learned by our algorithms.} }
Endnote
%0 Conference Paper %T Extreme Learning to Rank via Low Rank Assumption %A Minhao Cheng %A Ian Davidson %A Cho-Jui Hsieh %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-cheng18a %I PMLR %P 951--960 %U https://proceedings.mlr.press/v80/cheng18a.html %V 80 %X We consider the setting where we wish to perform ranking for hundreds of thousands of users which is common in recommender systems and web search ranking. Learning a single ranking function is unlikely to capture the variability across all users while learning a ranking function for each person is time-consuming and requires large amounts of data from each user. To address this situation, we propose a Factorization RankSVM algorithm which learns a series of k basic ranking functions and then constructs for each user a local ranking function that is a combination of them. We develop a fast algorithm to reduce the time complexity of gradient descent solver by exploiting the low-rank structure, and the resulting algorithm is much faster than existing methods. Furthermore, we prove that the generalization error of the proposed method can be significantly better than training individual RankSVMs. Finally, we present some interesting patterns in the principal ranking functions learned by our algorithms.
APA
Cheng, M., Davidson, I. & Hsieh, C.. (2018). Extreme Learning to Rank via Low Rank Assumption. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:951-960 Available from https://proceedings.mlr.press/v80/cheng18a.html.

Related Material