Reconciling Real Scores with Binary Comparisons: A Unified Logistic Model for Ranking

The problem of ranking arises ubiquitously in almost every aspect of life. A statistical model for ranking predicts how humans rank subsets $V$ of some universe $U$. In this work we define a statistical model for ranking that has the following desirable properties: (i) It is parametrized by a real valued function ("score") on $U$, (ii) The score parameters can be efficiently learnt from sample data consisting of a sequence of comparison bits (either "A precedes B" or "B precedes A"), (iii) For any subset $V$ of $U$, the ranking which sorts the elements by score is the mode (most probable outcome) of the model distribution, (iv) It predicts the empirical strong independence between human response to comparison questions and the context in which the questions are asked, and (v) It admits an efficient $O(n\log n)$ time sampling algorithm for subsets of size $n$. This is the first theoretical justification to the score based approach often found in machine learning ranking systems, most notably in information retrieval. In addition, it gives rise to a new promising logistic regression based approach to learning how to rank, for which the score and comparison based approaches are dual views. This offers a reconciliation between the two approaches, whereas in previous work on ranking the two were intermixed (e.g. by acquiring comparison labels and optimizing over scores) with only heuristic justification. Our model is built rigorously and axiomatically based on very simple desirable properties defined locally for comparisons, and automatically implies the existence of a global score function serving as a natural model parameter which can be efficiently fitted to data by solving a convex optimization problem.