Enhanced statistical rankings via targeted data collection

Braxton Osting, Christoph Brune, Stanley Osher

Research output: Contribution to conferencePaperpeer-review

20 Citations (Scopus)


Given a graph where vertices represent alternatives and pairwise comparison data, yij is given on the edges, the statistical ranking problem is to find a potential function, defined on the vertices, such that the gradient of the potential function agrees with pairwise comparisons. We study the dependence of the statistical ranking problem on the available pairwise data, i.e., pairs (i, j) for which the pairwise comparison data yij is known, and propose a framework to identify data which, when augmented with the current dataset, maximally increases the Fisher information of the ranking. Under certain assumptions, the data collection problem decouples, reducing to a problem of finding an edge set on the graph (with a fixed number of edges) such that the second eigenvalue of the graph Laplacian is maximal. This reduction of the data collection problem to a spectral graph-theoretic question is one of the primary contributions of this work. As an application, we study the Yahoo! Movie user rating dataset and demonstrate that the addition of a small number of well-chosen pairwise comparisons can significantly increase the Fisher informativeness of the ranking.

Original languageEnglish
Number of pages9
Publication statusPublished - 1 Jan 2013
Externally publishedYes
Event30th International Conference on Machine Learning, ICML 2013 - Atlanta Marriott Marquis, Atlanta, United States
Duration: 16 Jun 201321 Jun 2013
Conference number: 30


Conference30th International Conference on Machine Learning, ICML 2013
Abbreviated titleICML 2013
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Enhanced statistical rankings via targeted data collection'. Together they form a unique fingerprint.

Cite this