skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Efficient computation of rankings from pairwise comparisons
We study the ranking of individuals, teams, or objects, based on pairwise comparisons between them, using the Bradley-Terry model. Estimates of rankings within this model are commonly made using a simple iterative algorithm first introduced by Zermelo almost a century ago. Here we describe an alternative and similarly simple iteration that provably returns identical results but does so much faster -- over a hundred times faster in some cases. We demonstrate this algorithm with applications to a range of example data sets and derive a number of results regarding its convergence.  more » « less
Award ID(s):
2005899
PAR ID:
10537878
Author(s) / Creator(s):
Publisher / Repository:
JMLR, Inc. and Microtome Publishing (United States)
Date Published:
Journal Name:
Journal of Machine Learning Research
Volume:
24
ISSN:
1533-7928
Page Range / eLocation ID:
238
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, IEEE International Conference on Soft Robotics (RoboSoft))
    Because of the complex nature of soft robots, formulating dynamic models that are simple, efficient, and sufficiently accurate for simulation or control is a difficult task. This paper introduces an algorithm based on a recursive Newton-Euler (RNE) approach that enables an accurate and tractable lumped parameter dynamic model. This model scales linearly in computational complexity with the number of discrete segments. We validate this model by comparing it to actual hardware data from a three-joint continuum soft robot (with six degrees of freedom represented in a constant curvature kinematic model). The results show that this RNE-based model can be computed faster than real-time. We also show that with minimal system identification, a simulation performed using the dynamic model matches the real robot data with a median error of 3.15 degrees. 
    more » « less
  2. ; ; (, Stochastic Systems)
    null (Ed.)
    We propose a new simple and natural algorithm for learning the optimal Q-value function of a discounted-cost Markov decision process (MDP) when the transition kernels are unknown. Unlike the classical learning algorithms for MDPs, such as Q-learning and actor-critic algorithms, this algorithm does not depend on a stochastic approximation-based method. We show that our algorithm, which we call the empirical Q-value iteration algorithm, converges to the optimal Q-value function. We also give a rate of convergence or a nonasymptotic sample complexity bound and show that an asynchronous (or online) version of the algorithm will also work. Preliminary experimental results suggest a faster rate of convergence to a ballpark estimate for our algorithm compared with stochastic approximation-based algorithms. 
    more » « less
  3. ; ; (, Proceedings of the 35th International Conference on Machine Learning)
    The problem of rank aggregation from pairwise and multiway comparisons has a wide range of implications, ranging from recommendation systems to sports rankings to social choice. Some of the most popular algorithms for this problem come from the class of spectral ranking algorithms; these include the rank centrality (RC) algorithm for pairwise comparisons, which returns consistent estimates under the Bradley-Terry-Luce (BTL) model for pairwise comparisons (Negahban et al., 2017), and its generalization, the Luce spectral ranking (LSR) algorithm, which returns consistent estimates under the more general multinomial logit (MNL) model for multiway comparisons (Maystre & Grossglauser, 2015). In this paper, we design a provably faster spectral ranking algorithm, which we call accelerated spectral ranking (ASR), that is also consistent under the MNL/BTL models. Our accelerated algorithm is achieved by designing a random walk that has a faster mixing time than the random walks associated with previous algorithms. In addition to a faster algorithm, our results yield improved sample complexity bounds for recovery of the MNL/BTL parameters: to the best of our knowledge, we give the first general sample complexity bounds for recovering the parameters of the MNL model from multiway comparisons under any (connected) comparison graph (and improve significantly over previous bounds for the BTL model for pairwise comparisons). We also give a message-passing interpretation of our algorithm, which suggests a decentralized distributed implementation. Our experiments on several real-world and synthetic datasets confirm that our new ASR algorithm is indeed orders of magnitude faster than existing algorithms. 
    more » « less
  4. ; ; (, Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research)
    The problem of rank aggregation from pairwise and multiway comparisons has a wide range of implications, ranging from recommendation systems to sports rankings to social choice. Some of the most popular algorithms for this problem come from the class of spectral ranking algorithms; these include the rank centrality (RC) algorithm for pairwise comparisons, which returns consistent estimates under the Bradley-Terry-Luce (BTL) model for pairwise comparisons (Negahban et al., 2017), and its generalization, the Luce spectral ranking (LSR) algorithm, which returns consistent estimates under the more general multinomial logit (MNL) model for multiway comparisons (Maystre & Grossglauser, 2015). In this paper, we design a provably faster spectral ranking algorithm, which we call accelerated spectral ranking (ASR), that is also consistent under the MNL/BTL models. Our accelerated algorithm is achieved by designing a random walk that has a faster mixing time than the random walks associated with previous algorithms. In addition to a faster algorithm, our results yield improved sample complexity bounds for recovery of the MNL/BTL parameters: to the best of our knowledge, we give the first general sample complexity bounds for recovering the parameters of the MNL model from multiway comparisons under any (connected) comparison graph (and improve significantly over previous bounds for the BTL model for pairwise comparisons). We also give a message-passing interpretation of our algorithm, which suggests a decentralized distributed implementation. Our experiments on several real-world and synthetic datasets confirm that our new ASR algorithm is indeed orders of magnitude faster than existing algorithms. 
    more » « less
  5. ; ; ; ; (, 10th International Conference on Power Electronics-ECCE Asia)
    In this research, a Kalman filter-based Z-source inverter is proposed with an enhanced control algorithm for Maximum Power Pointer Tracking(MPPT) and this capacitor voltage stabilization. By implementing Unified Linear Kalman Filter Algorithm with Capacitor Voltage Control (CVC) algorithm for the Z-source inverter, the Kalman Filter can track Maximum Power Point (MPP) faster than traditional algorithm such as Perturb and Observation (P&O) algorithm, that has a minimum impact on rapidly changing atmospheric conditions. Thus, by using the Integrated Kalman Filter and CVC algorithm we can achieve faster, effective and capacitor voltage regulation at the same time. The effectiveness of this proposed Kalman Filter with CVC Algorithm for Z-source inverter is validated in MATLAB/Simulink and a hardware prototype has been built to verify the simulation and theoretical results. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email