Main navigation | Section navigation | Content

LAS Events « News « College of Liberal Arts & Sciences « University of Illinois


LAS Events


College of LAS Events

skip to events

calendar tabs

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

Event Detail Information

Event Detail Information

Communications Seminar: Iterative Ranking from Pair-wise Comparisons

Speaker Professor Sewoong Oh, IESE
Date Nov 26, 2012
Time 4:00 pm - 5:00 pm  
Location 141 Coordinated Science Lab
Sponsor Communications Seminar
Views 751
Originating Calendar CSL Communications Group Calendar
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
Bookmark and Share