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…
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,694 papers · 148 categories
Trend · papers per month
48 results for “pairwise comparison oracle”
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 .
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.
New oracle uses uncertainty for active classification with noisy feedback.
problem Improving query complexity in interactive binary classifier learning.
method Proposes a new pairwise comparison oracle that considers uncertainty and an adaptive labeling algorithm.
result Demonstrates improved performance and efficiency compared to existing methods.
Paper tackles noisy comparison oracle for robust clustering algorithms.
problem Finding robust clustering algorithms under noisy comparison oracle.
method Develops algorithms for k-center clustering and agglomerative hierarchical clustering using noisy comparison oracle.
result Proves robust algorithms achieve good approximation guarantees with high probability.
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…
There is increasing interest in learning algorithms that involve interaction between human and machine. Comparison-based queries are among the most natural ways to get feedback from humans. A challenge in designing comparison-based interactive learning algorithms is coping with noisy answers. The most common fix is to …
New algorithm learns permutations mixtures with optimal sample complexity.
problem Learning mixtures of permutations in high-dimensional settings.
method Combining groups of pairwise comparisons and combinatorial method of moments.
result Optimal sample complexity proportional to log(n) for high-dimensional data.
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…
Develops new oracle inequalities for Gaussian ranking estimators.
problem Lack of rigorous theoretical support for Gaussian ranking estimators.
method Novel oracle inequalities for regularized pairwise ranking.
result Derives fast learning rates under general dimension assumptions.
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 …
Semi-supervised active clustering (SSAC) utilizes the knowledge of a domain expert to cluster data points by interactively making pairwise "same-cluster" queries. However, it is impractical to ask human oracles to answer every pairwise query. In this paper, we study the influence of allowing "not-sure" answers from a w…
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…
We consider the problem of finding a target object using pairwise comparisons, by asking an oracle questions of the form \emph{"Which object from the pair is more similar to ?"}. Objects live in a space of latent features, from which the oracle generates noisy answers. First, we consider the {\em non-bli…
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 studies the problem of inferring a global preference based on the partial rankings provided by many users over different subsets of items according to the Plackett-Luce model. A question of particular interest is how to optimally assign items to users for ranking and how many item assignments are needed to a…
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.
Proposes a nonparametric model for dynamic team rankings.
problem Dynamic ranking of distinct teams over time.
method Kernel smoothing for nonparametric estimation in sparse settings.
result Time-varying oracle bounds for estimation and excess risk.
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.
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.
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.
Paper relaxes assumptions for non-parametric estimation in pairwise learning.
problem Generalization performance of non-parametric estimation for pairwise learning.
method Significantly relaxes restrictive assumptions, constructs structured deep ReLU neural network, and designs targeted hypothesis space.
result Establishes a sharp oracle inequality for empirical minimizer with general hypothesis space for Lipschitz continuous pairwise losses.
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.
Pairwise "same-cluster" queries are one of the most widely used forms of supervision in semi-supervised clustering. However, it is impractical to ask human oracles to answer every query correctly. In this paper, we study the influence of allowing "not-sure" answers from a weak oracle and propose an effective algorithm …
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…