College of LAS Events

College of LAS Events

skip to events

If you need disability-related accommodations in order to participate in a program or event and cannot find an event contact listed, please contact MT Hudson at (217) 333-0885 or Early requests are strongly encouraged to allow sufficient time to meet your access needs.

calendar tabs

  •  All 
  • Month
  • Week
  • Day
  • (Selected tab) Detail

Event Detail Information

Communications Seminar: Iterative Ranking from Pair-wise Comparisons

SpeakerProfessor Sewoong Oh, IESE
Date Nov 26, 2012
Time 4:00 pm - 5:00 pm  
Location 141 Coordinated Science Lab
Sponsor Communications Seminar
Event type Other
Views 751

The question of aggregating pairwise comparisons to obtain a global ranking has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In addition to obtaining a ranking, finding 'scores' for each object is of interest for understanding the intensity of the preferences. In this talk, I will describe a new approach for discovering scores for objects (or items) from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the stationary probability of this random walk assigns a score to each objects. To establish the efficacy of our method, we consider the popular Bradley-Terry-Luce (BTL) model and provide an upper bound on the finite sample error rate. The number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, this leads to an order-optimal sample complexity. We also provide numerical results on real and synthetic data-sets to compare our approach to other popular approaches.

link for robots only