TY - JOUR

T1 - Learning from comparisons and choices

AU - Negahban, Sahand

AU - Oh, Sewoong

AU - Thekumparampil, Kiran K.

AU - Xu, Jiaming

N1 - Funding Information:
SN acknowledges support from NSF Grant DMS 1723128. SO and KT acknowledge support from NSF grants CCF 1553452, CNS 1527754, CCF 1705007, and RI 1815535. The authors acknowledge Yu Lu and Ruoyu Sun for helpful and fruitful discussions.
Publisher Copyright:
© 2018 Sahand Negahban, Sewoong Oh, Kiran K. Thekumparampil, and Jiaming Xu.

PY - 2018/8/1

Y1 - 2018/8/1

N2 - When tracking user-specific online activities, each user's preference is revealed in the form of choices and comparisons. For example, a user's purchase history is a record of her choices, i.e. which item was chosen among a subset of offerings. A user's preferences can be observed either explicitly as in movie ratings or implicitly as in viewing times of news articles. Given such individualized ordinal data in the form of comparisons and choices, we address the problem of collaboratively learning representations of the users and the items. The learned features can be used to predict a user's preference of an unseen item to be used in recommendation systems. This also allows one to compute similarities among users and items to be used for categorization and search. Motivated by the empirical successes of the MultiNomial Logit (MNL) model in marketing and transportation, and also more recent successes in word embedding and crowdsourced image embedding, we pose this problem as learning the MNL model parameters that best explain the data. We propose a convex relaxation for learning the MNL model, and show that it is minimax optimal up to a logarithmic factor by comparing its performance to a fundamental lower bound. This characterizes the minimax sample complexity of the problem, and proves that the proposed estimator cannot be improved upon other than by a logarithmic factor. Further, the analysis identifies how the accuracy depends on the topology of sampling via the spectrum of the sampling graph. This provides a guideline for designing surveys when one can choose which items are to be compared. This is accompanied by numerical simulations on synthetic and real data sets, confirming our theoretical predictions.

AB - When tracking user-specific online activities, each user's preference is revealed in the form of choices and comparisons. For example, a user's purchase history is a record of her choices, i.e. which item was chosen among a subset of offerings. A user's preferences can be observed either explicitly as in movie ratings or implicitly as in viewing times of news articles. Given such individualized ordinal data in the form of comparisons and choices, we address the problem of collaboratively learning representations of the users and the items. The learned features can be used to predict a user's preference of an unseen item to be used in recommendation systems. This also allows one to compute similarities among users and items to be used for categorization and search. Motivated by the empirical successes of the MultiNomial Logit (MNL) model in marketing and transportation, and also more recent successes in word embedding and crowdsourced image embedding, we pose this problem as learning the MNL model parameters that best explain the data. We propose a convex relaxation for learning the MNL model, and show that it is minimax optimal up to a logarithmic factor by comparing its performance to a fundamental lower bound. This characterizes the minimax sample complexity of the problem, and proves that the proposed estimator cannot be improved upon other than by a logarithmic factor. Further, the analysis identifies how the accuracy depends on the topology of sampling via the spectrum of the sampling graph. This provides a guideline for designing surveys when one can choose which items are to be compared. This is accompanied by numerical simulations on synthetic and real data sets, confirming our theoretical predictions.

KW - Collaborative Ranking

KW - Multi-Nomial Logit Model

KW - Nuclear Norm Minimization

UR - http://www.scopus.com/inward/record.url?scp=85053333628&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053333628&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85053333628

SN - 1532-4435

VL - 19

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

ER -