We study the problem of ranking from crowdsourced pairwise comparisons. Answers to pairwise tasks are known to be affected by the position of items on the screen, however, previous models for aggregation of pairwise comparisons do not focus on modeling such kind of biases. We introduce a new aggregation model factorBT …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “pairwise comparison”
In this study, a pairwise comparison matrix is generalized to the case when coefficients create Lie group , non necessarily abelian. A necessary and sufficient criterion for pairwise comparisons matrices to be consistent is provided. Basic criteria for finding a nearest consistent pairwise comparisons matrix (extend…
Develops a statistical framework to measure uncertainty in model rankings based on human preferences.
problem Uncertainty in model rankings based on human preferences due to mismatch between human and model preferences.
method Statistical framework using pairwise comparisons by humans and models to provide rank-sets for each model.
result Rank-sets constructed using only pairwise comparisons by strong models often do not cover the true ranking of human preferences.
This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of objects can be identified by standard sorting methods using pairwise comparisons. We are interested in natural situations in which relationships among the o…
Recent work by Locatello et al. (2018) has shown that an inductive bias is required to disentangle factors of interest in Variational Autoencoder (VAE). Motivated by a real-world problem, we propose a setting where such bias is introduced by providing pairwise ordinal comparisons between instances, based on the desired…
Paper establishes statistical inference for pairwise comparison models.
problem Statistical inference for pairwise comparison models when the number of subjects diverges.
method Identifies Fisher information matrix as a weighted graph Laplacian for asymptotic normality.
result Near-optimal asymptotic normality result for maximum likelihood estimator.
Rank regression from pairwise comparisons requires many comparisons to accurately learn model parameters.
problem Learning model parameters for rank regression from noisy pairwise comparisons.
method Uniform random pairwise comparisons to estimate model parameters with a given accuracy.
result Learning model parameters requires a number of comparisons proportional to .
Optimal privacy-preserving ranking from noisy comparisons.
problem Protecting individual privacy in ranking from noisy comparisons.
method Differentially private ranking algorithms under edge and individual differential privacy.
result Achieved minimax optimal rates of convergence under privacy constraints.
A faster algorithm for ranking from pairwise comparisons.
problem Efficiently ranking individuals or objects from pairwise comparisons.
method An alternative and simpler iterative algorithm for ranking that converges faster.
result The new algorithm is over 100 times faster in some cases.
New model for pairwise comparisons without stochastic transitivity.
problem Suboptimal performance of models assuming stochastic transitivity in real-world scenarios.
method Proposes a general family of statistical models using a skew-symmetric matrix.
result Achieves minimax-rate optimality and adapts to data sparsity.
Study on deep neural networks for reward modeling with pairwise comparison data.
problem Reward modeling with deep neural networks in non-parametric settings.
method Established a non-asymptotic regret bound for deep reward estimators, introduced a margin-type condition.
result Improved regret bound for deep reward estimators, highlighting the importance of clear human beliefs.
Paper proposes Pcomp classification for binary classification with pairwise confidence comparisons.
problem Lack of pointwise labels due to privacy, confidentiality, or security reasons.
method Developed Pcomp classification, derived an unbiased risk estimator (URE), and improved it using correction functions and consistency regularization.
result Demonstrated the effectiveness of Pcomp classification methods.
This paper provides a block coordinate descent algorithm to solve unconstrained optimization problems. In our algorithm, computation of function values or gradients is not required. Instead, pairwise comparison of function values is used. Our algorithm consists of two steps; one is the direction estimate step and the o…
Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume that there are …
Study learns linear utility functions from comparisons, showing learnability gaps between passive and active learning.
problem Learn linear utility functions from pairwise comparison queries.
method Analyzes passive and active learning settings, considering noise-free and noisy query responses.
result Efficient learnability of linear utilities in passive learning, but not for utility parameters without strong assumptions.
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder bu…
Active sampling algorithm improves accuracy of inferred scores from pairwise comparisons.
problem Inference of accurate scores from time-consuming pairwise comparisons.
method Approximate message passing and expected information gain maximization.
result ASAP offers the highest accuracy of inferred scores compared to existing methods.
The paper designs tests for comparing ranked preference data and finds significant differences.
problem Comparing pairwise comparison and ranking data in various applications.
method Developed two-sample tests for pairwise comparison and ranking data, proving upper and lower bounds.
result Upper and lower bounds show tightness of the proposed tests, and significant differences in preferences were found.
This paper optimizes the number of comparisons needed to find the best k items from pairwise comparisons.
problem Finding the best k items from pairwise comparisons with limited comparisons.
method Developed algorithms for finding probably approximately correct and exact best k items under stochastic conditions.
result Upper and lower bounds on the number of comparisons for finding the best k items, with matching upper bounds for PAC best k items.
In this paper, we propose an active learning algorithm and models which can gradually learn individual's preference through pairwise comparisons. The active learning scheme aims at finding individual's most preferred choice with minimized number of pairwise comparisons. The pairwise comparisons are encoded into probabi…
New model accounts for scale variation and noise in pairwise comparisons.
problem Nonreciprocal pairwise comparisons in decision analysis.
method Additive model with structured matrix and random perturbation.
result Explicit estimators and probability assessments of admissible ranking regions.
We describe a mathematical link between aspects of information theory, called pairwise comparisons, and discretized gauge theories. The link is made by the notion of holonomy along the edges of a simplex. This correspondance leads to open questions in both field.
Optimizes identifying top-k items from comparisons with minimal comparisons.
problem Finding the top-k items from pairwise comparisons with a fixed error rate.
method Developed an asymptotically optimal algorithm using primal-dual procedure and adaptive comparison allocation.
result Proves the algorithm is asymptotically optimal for top-k identification.
Comparison data arises in many important contexts, e.g. shopping, web clicks, or sports competitions. Typically we are given a dataset of comparisons and wish to train a model to make predictions about the outcome of unseen comparisons. In many cases available datasets have relatively few comparisons (e.g. there are on…
We describe a seriation algorithm for ranking a set of items given pairwise comparisons between these items. Intuitively, the algorithm assigns similar rankings to items that compare similarly with all others. It does so by constructing a similarity matrix from pairwise comparisons, using seriation methods to reorder t…
We consider sequential or active ranking of a set of n items based on noisy pairwise comparisons. Items are ranked according to the probability that a given item beats a randomly chosen item, and ranking refers to partitioning the items into sets of pre-specified sizes according to their scores. This notion of ranking …
GNNRank uses neural networks to learn global rankings from competition match data.
problem Learning global rankings from pairwise comparisons in directed graphs.
method Proposes GNNRank, a trainable GNN-based framework with digraph embedding and new objectives.
result GNNRank achieves competitive and superior performance compared to baselines.
A common problem in machine learning is to rank a set of n items based on pairwise comparisons. Here ranking refers to partitioning the items into sets of pre-specified sizes according to their scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defi…
We consider data in the form of pairwise comparisons of n items, with the goal of precisely identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We analyze the Copeland counting algorithm that ranks the items in order of the number of pairwise comparisons won, an…
Bayesian model infers strengths from noisy tennis match outcomes.
problem Ranking tennis players from match outcomes.
method Bayesian approach to infer unobserved strengths and mapping function.
result Bayesian approach robust to different model specifications.
RL-LOW algorithm achieves exponential simple regret in offline RLHF with pairwise comparisons.
problem Offline reinforcement learning from human feedback with pairwise comparisons.
method Proposes RL-LOW algorithm to minimize simple regret with exponential convergence.
result Achieves an exponential form of simple regret of \(\exp ( - Ω(n/H) )\).
Statistical framework improves LLM chatbot ranking.
problem Improving evaluation of LLM-based chatbots through pairwise comparisons.
method Factored tie model, covariance modeling, and parameter constraints.
result Substantial improvements in modeling pairwise comparison data.
Uncoupled regression is the problem to learn a model from unlabeled data and the set of target values while the correspondence between them is unknown. Such a situation arises in predicting anonymized targets that involve sensitive information, e.g., one's annual income. Since existing methods for uncoupled regression …
Study embeds PC matrices into Grassmannian manifold for geometric interpretation.
problem Understanding algebraic consistency of pairwise comparisons matrices.
method Leverages Plücker coordinates and geometric interpretation of Grassmannian manifold.
result Algebraic consistency condition is equivalent to geometric consistency in .
There is a growing need for discrete choice models that account for the complex nature of human choices, escaping traditional behavioral assumptions such as the transitivity of pairwise preferences. Recently, several parametric models of intransitive comparisons have been proposed, but in all cases the maximum likeliho…
Study metric learning from limited preference comparisons, showing how low-dimensional structure can still reveal metric information.
problem Learning metric from limited pairwise preference comparisons.
method Ideal point model, divide-and-conquer approach for low-dimensional structure.
result Metric can be jointly identified even with limited comparisons when items exhibit low-dimensional structure.
Exact pairwise ranking is achievable but not possible under noisy comparisons.
problem Recovering the exact rank of items from noisy pairwise comparisons.
method Information-theoretic upper and lower bounds using the SST model and combinatorial arguments.
result Sharp information-theoretic bounds match in the parametric limit and outperform previous methods.
This paper tackles bandit optimization with a new pairwise comparison oracle for unknown strongly concave functions.
problem Maximizing an unknown strongly concave function over T periods with a biased pairwise comparison oracle.
method Introduced a discretization technique and local polynomial approximation to relate the problem to linear bandits. Developed a tournament successive elimination technique to localize the discretized cell and run LinUCB algorithm on cells.
result Established optimal regret bounds and improved state-of-the-art results in operations management problems.
Statistical inference using pairwise comparison data is an effective approach to analyzing large-scale sparse networks. In this paper, we propose a general framework to model the mutual interactions in a network, which enjoys ample flexibility in terms of model parametrization. Under this setup, we show that the maximu…
The report studies ranking from pairwise comparisons in graphs, achieving optimal error bounds and proposing efficient algorithms.
problem Ranking items from pairwise comparisons in general graphs and graphs with locality.
method Maximum likelihood estimation (MLE) and preconditioned gradient descent for general graphs; divide-and-conquer algorithms for graphs with locality.
result MLE achieves optimal error bounds in general graphs and identifies conditions for locality.
New methods rank players using covariates and comparisons, outperforming existing algorithms.
problem Ranking players based on incomplete and noisy pairwise comparisons.
method Three spectral ranking methods incorporating player covariates.
result Proposed methods outperform existing algorithms in simulations.
Paper quantifies uncertainty in pairwise comparison models.
problem Uncertainty quantification in sparse Bradley-Terry-Luce models.
method Unified proof strategy for MLE and spectral estimator.
result Sharp and uniform non-asymptotic expansions for estimators.
We study methods for aggregating pairwise comparison data in order to estimate outcome probabilities for future comparisons among a collection of n items. Working within a flexible framework that imposes only a form of strong stochastic transitivity (SST), we introduce an adaptivity index defined by the indifference se…
Inspired by applications in sports where the skill of players or teams competing against each other varies over time, we propose a probabilistic model of pairwise-comparison outcomes that can capture a wide range of time dynamics. We achieve this by replacing the static parameters of a class of popular pairwise-compari…
Data in the form of pairwise comparisons arises in many domains, including preference elicitation, sporting competitions, and peer grading among others. We consider parametric ordinal models for such pairwise comparison data involving a latent vector that represents the "qualities" of the ite…
New method uses model comparison signals to improve LLM evaluation accuracy.
problem Limited benchmark sizes and model stochasticity in evaluating LLMs' mathematical reasoning.
method Combines standard labeled outcomes with model comparison signals to design a statistically efficient evaluation framework.
result Semiparametric estimator achieves the semiparametric efficiency bound and substantially improves ranking accuracy.
New algorithm ranks players from partial comparisons with optimal rate.
problem Ranking players from partial pairwise comparisons.
method Divide-and-conquer approach, local MLE within groups.
result Optimal ranking algorithm with minimax rate.
Recommender systems are one of the most pervasive applications of machine learning in industry, with many services using them to match users to products or information. As such it is important to ask: what are the possible fairness risks, how can we quantify them, and how should we address them? In this paper we offer …