Abstract
Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume users form clusters; users of the same cluster provide similar pairwise comparisons for the items according to the Bradley-Terry model. We propose an efficient algorithm to estimate the preference for each user: first, compute the net-win vector for each user using the comparisons; second, cluster the users based on the net-win vectors; third, estimate a single preference for each cluster separately. We show that the net-win vectors are much less noisy than the high dimensional vectors of pairwise comparisons, therefore our algorithm can cluster the users reliably. Moreover, we show that, when a cluster is only approximately correct, the maximum likelihood estimation for the Bradley-Terry model is still close to the true preference.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 449-450 |
| Number of pages | 2 |
| Journal | Performance Evaluation Review |
| Volume | 43 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jun 24 2015 |
| Event | ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 - Portland, United States Duration: Jun 15 2015 → Jun 19 2015 |
Fingerprint
Keywords
- Bradley-Terry model
- Clustering
- Inference
- Ranking
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Networks and Communications
Cite this
Clustering and inference from pairwise comparisons. / Wu, Rui; Xu, Jiaming; Srikant, Rayadurgam; Massoulié, Laurent; Lelarge, Marc; Hajek, Bruce.
In: Performance Evaluation Review, Vol. 43, No. 1, 24.06.2015, p. 449-450.Research output: Contribution to journal › Conference article
}
TY - JOUR
T1 - Clustering and inference from pairwise comparisons
AU - Wu, Rui
AU - Xu, Jiaming
AU - Srikant, Rayadurgam
AU - Massoulié, Laurent
AU - Lelarge, Marc
AU - Hajek, Bruce
PY - 2015/6/24
Y1 - 2015/6/24
N2 - Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume users form clusters; users of the same cluster provide similar pairwise comparisons for the items according to the Bradley-Terry model. We propose an efficient algorithm to estimate the preference for each user: first, compute the net-win vector for each user using the comparisons; second, cluster the users based on the net-win vectors; third, estimate a single preference for each cluster separately. We show that the net-win vectors are much less noisy than the high dimensional vectors of pairwise comparisons, therefore our algorithm can cluster the users reliably. Moreover, we show that, when a cluster is only approximately correct, the maximum likelihood estimation for the Bradley-Terry model is still close to the true preference.
AB - Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume users form clusters; users of the same cluster provide similar pairwise comparisons for the items according to the Bradley-Terry model. We propose an efficient algorithm to estimate the preference for each user: first, compute the net-win vector for each user using the comparisons; second, cluster the users based on the net-win vectors; third, estimate a single preference for each cluster separately. We show that the net-win vectors are much less noisy than the high dimensional vectors of pairwise comparisons, therefore our algorithm can cluster the users reliably. Moreover, we show that, when a cluster is only approximately correct, the maximum likelihood estimation for the Bradley-Terry model is still close to the true preference.
KW - Bradley-Terry model
KW - Clustering
KW - Inference
KW - Ranking
UR - http://www.scopus.com/inward/record.url?scp=84955576577&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84955576577&partnerID=8YFLogxK
U2 - 10.1145/2796314.2745887
DO - 10.1145/2796314.2745887
M3 - Conference article
AN - SCOPUS:84955576577
VL - 43
SP - 449
EP - 450
JO - Performance Evaluation Review
JF - Performance Evaluation Review
SN - 0163-5999
IS - 1
ER -