TL;DR
This paper introduces POLYRANK, a novel method for analyzing paired comparison data that relaxes the assumption of a known comparison function. By modeling the inverse comparison function as a polynomial, POLYRANK can simultaneously estimate item merits and the comparison function itself, offering a more flexible and robust approach than traditional methods.
What Problem Does This Paper Address?
In many fields, from sports rankings to product preference analysis, we encounter data where items are compared in pairs, and one is preferred over the other. The standard approach, often called Linear Stochastic Transitivity (LST), models the probability of item $i$ being preferred over item $j$ as $p_{ij} = F(\mu_i - \mu_j)$, where $\mu_i$ and $\mu_j$ are item merits and $F$ is a known, symmetric comparison function (like the logistic or normal distribution). The major limitation here is that $F$ is often assumed to be known in practice, which is unrealistic and can lead to poor model fits and erroneous conclusions. This paper tackles this by proposing a method that simultaneously estimates both the item merits ($\mu$) and the comparison function ($F$).
Methods
The core of the proposed method, POLYRANK, lies in relaxing the assumption that $F$ is known. Instead, the authors assume that the inverse comparison function, $F^{-1}$, can be represented by a polynomial of a certain degree $D$. This allows them to formulate the problem as a semi-definite programming (SDP) problem.
Here's a breakdown of the approach:
- Parametric Assumption: The comparison function $F$ is assumed to belong to a family where its inverse, $F^{-1}(p)$, is a polynomial of degree $D$. This family is rich enough to approximate many common comparison functions.
- Simultaneous Estimation: The method estimates both the item merits ($\mu$) and the polynomial coefficients ($\beta$) that define $F^{-1}$ simultaneously. This is achieved by minimizing a weighted least-squares objective function that penalizes the difference between the observed comparison probabilities (transformed by $F^{-1}$) and the predicted merit differences.
- Semi-Definite Programming (SDP): The optimization problem is formulated as an SDP, which can be solved efficiently in polynomial time using interior-point methods. This is a key computational advantage.
- Algorithm POLYRANK: The paper outlines an algorithm that leverages this SDP formulation. It involves preprocessing, functional estimation (estimating $\beta$), and merit estimation (estimating $\mu$).
Datasets
The authors evaluate their method using a large dataset of computer chess matches. This dataset consists of matches between 186 free single-CPU chess-engines, where each engine played approximately 32 matches against 40 opponents. The data was used to estimate the comparison function and compare it with existing models.
Key Insights and Ideas
- Flexibility is Key: The most significant insight is that assuming a known comparison function is a strong and often unrealistic constraint. By allowing the comparison function to be estimated, the method becomes much more flexible and adaptable to real-world data.
- Polynomials as a Powerful Proxy: Representing the inverse comparison function as a polynomial provides a computationally tractable yet flexible way to model a wide range of comparison functions.
- SDP for Tractability: Reformulating the estimation problem as an SDP is crucial for computational efficiency, allowing the method to scale to moderately sized problems.
- Empirical Evidence Against Standard Models: The analysis of the computer chess data suggests that commonly used comparison functions (like those in the Bradley-Terry-Luce model) may not be adequate for computer chess engines, highlighting the need for more flexible models.
Key Results
- Improved Estimation: Simulations show that POLYRANK performs comparably to or better than standard methods, especially when the true comparison function deviates from the assumed known function.
- Sensitivity Analysis: The paper provides theoretical bounds on the estimation errors, showing that POLYRANK is robust to noise in the input data and that the estimators are consistent.
- Computer Chess Findings: The analysis of the computer chess dataset revealed that the standard comparison functions used for rating systems do not fit the data well, suggesting that computer chess engines might have different preference structures than humans.
- Model Selection: Experiments suggest that model selection criteria like AIC and cross-validation can effectively guide the choice of the polynomial degree ($D$) for estimating the comparison function.
Limitations and Future Work
- Computational Complexity: While SDPs are polynomial-time solvable, the complexity can still be significant for very large numbers of items ($I$) or high polynomial degrees ($D$). The authors suggest developing more specialized solvers or distributed versions of POLYRANK.
- Model Misspecification: The paper explores scenarios where the true function is not a polynomial, but further work is needed to fully understand the performance under various misspecification scenarios.
- Statistical Properties: While theoretical guarantees are provided, the paper notes that further investigation into the asymptotic distributions of the estimated parameters is warranted.
- Extensions: The authors suggest several promising directions for future work, including:
- Exploring other basis functions for $F^{-1}$ (e.g., monotone splines).
- Incorporating covariates (like home advantage) into the model.
- Handling ties in comparisons.
- Extending the method to compare more than two items at a time.
- Developing online algorithms for real-time updates.
Summary updated