Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons

Dohyung Park, Joe Neeman, Jin Zhang, Sujay Sanghavi, Inderjit Dhillon
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1907-1916, 2015.

Abstract

In this paper we consider the collaborative ranking setting: a pool of users each provides a set of pairwise preferences over a small subset of the set of d possible items; from these we need to predict each user’s preferences for items s/he has not yet seen. We do so via fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) We show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(r \log^2 d) pairwise comparisons — essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and also matching a lower bound we establish here. (b) We develop a large-scale non-convex implementation, which we call AltSVM, which trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and other measures of ranking performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-park15, title = {Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons}, author = {Park, Dohyung and Neeman, Joe and Zhang, Jin and Sanghavi, Sujay and Dhillon, Inderjit}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1907--1916}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/park15.pdf}, url = {https://proceedings.mlr.press/v37/park15.html}, abstract = {In this paper we consider the collaborative ranking setting: a pool of users each provides a set of pairwise preferences over a small subset of the set of d possible items; from these we need to predict each user’s preferences for items s/he has not yet seen. We do so via fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) We show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(r \log^2 d) pairwise comparisons — essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and also matching a lower bound we establish here. (b) We develop a large-scale non-convex implementation, which we call AltSVM, which trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and other measures of ranking performance.} }
Endnote
%0 Conference Paper %T Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons %A Dohyung Park %A Joe Neeman %A Jin Zhang %A Sujay Sanghavi %A Inderjit Dhillon %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-park15 %I PMLR %P 1907--1916 %U https://proceedings.mlr.press/v37/park15.html %V 37 %X In this paper we consider the collaborative ranking setting: a pool of users each provides a set of pairwise preferences over a small subset of the set of d possible items; from these we need to predict each user’s preferences for items s/he has not yet seen. We do so via fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) We show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(r \log^2 d) pairwise comparisons — essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and also matching a lower bound we establish here. (b) We develop a large-scale non-convex implementation, which we call AltSVM, which trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and other measures of ranking performance.
RIS
TY - CPAPER TI - Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons AU - Dohyung Park AU - Joe Neeman AU - Jin Zhang AU - Sujay Sanghavi AU - Inderjit Dhillon BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-park15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1907 EP - 1916 L1 - http://proceedings.mlr.press/v37/park15.pdf UR - https://proceedings.mlr.press/v37/park15.html AB - In this paper we consider the collaborative ranking setting: a pool of users each provides a set of pairwise preferences over a small subset of the set of d possible items; from these we need to predict each user’s preferences for items s/he has not yet seen. We do so via fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) We show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(r \log^2 d) pairwise comparisons — essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and also matching a lower bound we establish here. (b) We develop a large-scale non-convex implementation, which we call AltSVM, which trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and other measures of ranking performance. ER -
APA
Park, D., Neeman, J., Zhang, J., Sanghavi, S. & Dhillon, I.. (2015). Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1907-1916 Available from https://proceedings.mlr.press/v37/park15.html.

Related Material