Heuristic Search for Rank Aggregation with Application to Label Ranking

• URL: http://arxiv.org/abs/2201.03893v1
• Date: Tue, 11 Jan 2022 11:43:17 GMT
• Title: Heuristic Search for Rank Aggregation with Application to Label Ranking
• Authors: Yangming Zhou and Jin-Kao Hao and Zhen Li and Fred Glover
• Abstract summary: We propose an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem. The algorithm features a semantic crossover based on concordant pairs and a late acceptance local search reinforced by an efficient incremental evaluation technique. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on benchmark instances.
• Score: 16.275063634853584
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Rank aggregation aims to combine the preference rankings of a number of alternatives from different voters into a single consensus ranking. As a useful model for a variety of practical applications, however, it is a computationally challenging problem. In this paper, we propose an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and a late acceptance local search reinforced by an efficient incremental evaluation technique. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, which is an important machine learning task.

Related papers

• A Novel Ranking Scheme for the Performance Analysis of Stochastic Optimization Algorithms using the Principles of Severity [9.310464457958844]
  We provide a novel ranking scheme to rank the algorithms over multiple single-objective optimization problems. The results of the algorithms are compared using a robust bootstrapping-based hypothesis testing procedure.
  arXiv  Detail & Related papers  (2024-05-31T19:35:34Z)
• Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
  We propose a model agnostic post-processing framework xOrder for achieving fairness in bipartite ranking. xOrder is compatible with various classification models and ranking fairness metrics, including supervised and unsupervised fairness metrics. We evaluate our proposed algorithm on four benchmark data sets and two real-world patient electronic health record repositories.
  arXiv  Detail & Related papers  (2023-07-27T07:42:44Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  We propose a new algorithm selector leveraging special forests, combining the strengths of both approaches while alleviating their weaknesses. HARRIS' decisions are based on a forest model, whose trees are created based on optimized on a hybrid ranking and regression loss function.
  arXiv  Detail & Related papers  (2022-10-31T14:06:11Z)
• Rank-based Non-dominated Sorting [0.0]
  We introduce Rank Sort, a non-dominated sorting approach exploiting sorting stability and ordinal information to avoid expensive dominance comparisons. Two algorithmic variants are proposed: the first one, RankOrdinal (RO), uses ordinal rank comparisons in order to determine dominance and requires O(N) space; the second one, RankIntersect (RS), uses set intersections and bit-level parallelism and requires O(N2) space. We demonstrate the efficiency of the proposed methods in comparison with other state of the art algorithms in empirical simulations using the NSGA2 algorithm as well as synthetic benchmarks.
  arXiv  Detail & Related papers  (2022-03-25T13:59:42Z)
• 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)
• PiRank: Learning To Rank via Differentiable Sorting [85.28916333414145]
  We propose PiRank, a new class of differentiable surrogates for ranking. We show that PiRank exactly recovers the desired metrics in the limit of zero temperature.
  arXiv  Detail & Related papers  (2020-12-12T05:07:36Z)
• Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking Fairness and Algorithm Utility [54.179859639868646]
  Bipartite ranking aims to learn a scoring function that ranks positive individuals higher than negative ones from labeled data. There have been rising concerns on whether the learned scoring function can cause systematic disparity across different protected groups. We propose a model post-processing framework for balancing them in the bipartite ranking scenario.
  arXiv  Detail & Related papers  (2020-06-15T10:08:39Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)
• Improving Label Ranking Ensembles using Boosting Techniques [13.782477759025348]
  Boosting is a well-known and reliable ensemble technique that was shown to often outperform other learning algorithms. In this paper, we propose a boosting algorithm which was specifically designed for label ranking tasks. Extensive evaluation of the proposed algorithm on 24 semi-synthetic and real-world label ranking datasets shows that it significantly outperforms existing state-of-the-art label ranking algorithms.
  arXiv  Detail & Related papers  (2020-01-21T19:16:11Z)
• TopRank+: A Refinement of TopRank Algorithm [0.0]
  A novel online learning algorithm was proposed based on topological sorting. In this work, we utilize method of mixtures and expansions of certain implicit function to provide a tighter, iterated-log-like boundary for the inequalities.
  arXiv  Detail & Related papers  (2020-01-21T15:44:44Z)

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.