Ranking with Confidence for Large Scale Comparison Data

• URL: http://arxiv.org/abs/2202.01670v1
• Date: Thu, 3 Feb 2022 16:36:37 GMT
• Title: Ranking with Confidence for Large Scale Comparison Data
• Authors: Filipa Valdeira, Cl\'audia Soares
• Abstract summary: In this work, we leverage a generative data model considering comparison noise to develop a fast, precise, and informative ranking from pairwise comparisons. In real data, PD-Rank requires less computational time to achieve the same Kendall algorithm than active learning methods.
• Score: 1.2183405753834562
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we leverage a generative data model considering comparison noise to develop a fast, precise, and informative ranking algorithm from pairwise comparisons that produces a measure of confidence on each comparison. The problem of ranking a large number of items from noisy and sparse pairwise comparison data arises in diverse applications, like ranking players in online games, document retrieval or ranking human perceptions. Although different algorithms are available, we need fast, large-scale algorithms whose accuracy degrades gracefully when the number of comparisons is too small. Fitting our proposed model entails solving a non-convex optimization problem, which we tightly approximate by a sum of quasi-convex functions and a regularization term. Resorting to an iterative reweighted minimization and the Primal-Dual Hybrid Gradient method, we obtain PD-Rank, achieving a Kendall tau 0.1 higher than all comparing methods, even for 10\% of wrong comparisons in simulated data matching our data model, and leading in accuracy if data is generated according to the Bradley-Terry model, in both cases faster by one order of magnitude, in seconds. In real data, PD-Rank requires less computational time to achieve the same Kendall tau than active learning methods.

Related papers

• Efficient computation of rankings from pairwise comparisons [0.0]
  We describe an alternative and similarly simple iteration that provably returns identical results but does so much faster. We demonstrate this algorithm with applications to a range of example data sets and derive a number of results regarding its convergence.
  arXiv  Detail & Related papers  (2022-06-30T19:39:09Z)
• Learning with Neighbor Consistency for Noisy Labels [69.83857578836769]
  We present a method for learning from noisy labels that leverages similarities between training examples in feature space. We evaluate our method on datasets evaluating both synthetic (CIFAR-10, CIFAR-100) and realistic (mini-WebVision, Clothing1M, mini-ImageNet-Red) noise.
  arXiv  Detail & Related papers  (2022-02-04T15:46:27Z)
• Toeplitz Least Squares Problems, Fast Algorithms and Big Data [1.3535770763481905]
  Two recent algorithms have applied randomized numerical linear algebra techniques to fitting an autoregressive model to big time-series data. We investigate and compare the quality of these two approximation algorithms on large-scale synthetic and real-world data. While both algorithms display comparable results for synthetic datasets, the LSAR algorithm appears to be more robust when applied to real-world time series data.
  arXiv  Detail & Related papers  (2021-12-24T08:32:09Z)
• Dictionary Learning Using Rank-One Atomic Decomposition (ROAD) [6.367823813868024]
  Dictionary learning aims at seeking a dictionary under which the training data can be sparsely represented. Road outperforms other benchmark algorithms for both synthetic data and real data.
  arXiv  Detail & Related papers  (2021-10-25T10:29:52Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  In rank aggregation problems, users exhibit various accuracy levels when comparing pairs of items. We propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons. We prove that our algorithm can return the true ranking of items with high probability.
  arXiv  Detail & Related papers  (2021-10-08T13:51:55Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Active Sampling for Pairwise Comparisons via Approximate Message Passing and Information Gain Maximization [5.771869590520189]
  We propose ASAP, an active sampling algorithm based on approximate message passing and expected information gain. We show that ASAP offers the highest accuracy of inferred scores compared to the existing methods.
  arXiv  Detail & Related papers  (2020-04-12T20:48:10Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)
• Noise-tolerant, Reliable Active Classification with Comparison Queries [25.725730509014355]
  We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label. We provide the first time and query efficient algorithms for learning non-homogeneous linear separators robust to bounded (Massart) noise.
  arXiv  Detail & Related papers  (2020-01-15T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.