Clustering and inference from pairwise comparisons

Rui Wu, Jiaming Xu, Rayadurgam Srikant, Laurent Massoulié, Marc Lelarge, Bruce Hajek

Research output: Contribution to journalConference article

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 languageEnglish (US)
Pages (from-to)449-450
Number of pages2
JournalPerformance Evaluation Review
Volume43
Issue number1
DOIs
StatePublished - Jun 24 2015
EventACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015

Fingerprint

Maximum likelihood estimation

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 journalConference article

Wu, Rui ; Xu, Jiaming ; Srikant, Rayadurgam ; Massoulié, Laurent ; Lelarge, Marc ; Hajek, Bruce. / Clustering and inference from pairwise comparisons. In: Performance Evaluation Review. 2015 ; Vol. 43, No. 1. pp. 449-450.
@article{422ab8925bcb48f8b553219f56b502b5,
title = "Clustering and inference from pairwise comparisons",
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.",
keywords = "Bradley-Terry model, Clustering, Inference, Ranking",
author = "Rui Wu and Jiaming Xu and Rayadurgam Srikant and Laurent Massouli{\'e} and Marc Lelarge and Bruce Hajek",
year = "2015",
month = "6",
day = "24",
doi = "10.1145/2796314.2745887",
language = "English (US)",
volume = "43",
pages = "449--450",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

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 -