RECORD
Ranking Recovery from Limited Comparisons using Low-Rank Matrix Completion
Machine Learning · Submitted 14 Jun 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim This work demonstrates the improvement of our proposed algorithm over the current state-of-the-art in both simulated scenarios and real data.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
This paper proposes a new method for solving the well-known rank aggregation problem from pairwise comparisons using the method of low-rank matrix completion. The partial and noisy data of pairwise comparisons is transformed into a matrix form. We then use tools from matrix completion, which has served as a major component in the low-rank completion solution of the Netflix challenge, to construct the preference of the different objects. In our approach, the data of multiple comparisons is used to create an estimate of the probability of object i to win (or be chosen) over object j, where only a partial set of comparisons between N objects is known. The data is then transformed into a matrix form for which the noiseless solution has a known rank of one. An alternating minimization algorithm, in which the target matrix takes a bilinear form, is then used in combination with maximum likelihood estimation for both factors. The reconstructed matrix is used to obtain the true underlying preference intensity. This work demonstrates the improvement of our proposed algorithm over the current state-of-the-art in both simulated scenarios and real data.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | This paper proposes a new method for solving the well-known rank aggregation problem from pairwise comparisons using the method of low-rank matrix completion. | contribution 1.00 | 0.85 | 0.11 | asserted 1.00 |
| s1 | The partial and noisy data of pairwise comparisons is transformed into a matrix form. | method 1.00 | 0.75 | 0.02 | asserted 0.99 |
| s2 | We then use tools from matrix completion, which has served as a major component in the low-rank completion solution of the Netflix challenge, to construct the preference of the different objects. | method 0.87 | 0.59 | 0.04 | asserted 0.99 |
| s3 | In our approach, the data of multiple comparisons is used to create an estimate of the probability of object i to win (or be chosen) over object j, where only a partial set of comparisons between N objects is known. | method 0.98 | 0.82 | 0.05 | asserted 1.00 |
| s4 | The data is then transformed into a matrix form for which the noiseless solution has a known rank of one. | method 1.00 | 0.72 | 0.03 | asserted 1.00 |
| s5 | An alternating minimization algorithm, in which the target matrix takes a bilinear form, is then used in combination with maximum likelihood estimation for both factors. | method 1.00 | 0.87 | 0.03 | asserted 0.99 |
| s6 | The reconstructed matrix is used to obtain the true underlying preference intensity. | method 0.94 | 0.83 | 0.06 | asserted 0.97 |
| s7 | This work demonstrates the improvement of our proposed algorithm over the current state-of-the-art in both simulated scenarios and real data. | result 0.98 | 0.95 | 0.88 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
This paper proposes a new method for solving the well-known rank aggregation problem from pairwise comparisons using the method of low-rank matrix completion. The partial and noisy data of pairwise comparisons is transformed into a matrix form. We then use tools from matrix completion, which has served as a major component in the low-rank completion solution of the Netflix challenge, to construct the preference of the different objects. In our approach, the data of multiple comparisons is used to create an estimate of the probability of object i to win (or be chosen) over object j, where only a partial set of comparisons between N objects is known. The data is then transformed into a matrix form for which the noiseless solution has a known rank of one. An alternating minimization algorithm, in which the target matrix takes a bilinear form, is then used in combination with maximum likelihood estimation for both factors. The reconstructed matrix is used to obtain the true underlying preference intensity. This work demonstrates the improvement of our proposed algorithm over the current state-of-the-art in both simulated scenarios and real data.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
Papers citing it
Cites it as background 1 paper
-
The recent work of Levy et al [ref] relies on matrix completion in the context of the rank aggregation problem from a small subset of noisy pairwise comparisons, wherein the user observes $L$ repeated comparisons between the same set of players.
Ranking and synchronization from pairwise measurements via SVD · Ranking literature · 0.98
What it cites
Compares with 1 paper
-
We compare Rank Centrality (RC) [ref] and Spectral MLE (SMLE) [ref] algorithms to our suggested MC-MLE algorithm.
Rank Centrality: Ranking from Pair-wise Comparisons · Comparison to current state-of-the-art · 1.00
Cites as background 1 paper
-
The framework of low-rank matrix completion has many powerful methods proposed for exact reconstruction from few entries [ref] based on convex relaxation [ref] even when the entries are corrupted by noise [ref] .
High-Rank Matrix Completion and Subspace Clustering with Missing Data · Introduction · 0.95
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.