Label Ranking through Nonparametric Regression

• URL: http://arxiv.org/abs/2111.02749v1
• Date: Thu, 4 Nov 2021 10:59:46 GMT
• Title: Label Ranking through Nonparametric Regression
• Authors: Dimitris Fotakis, Alkis Kalavasis and Eleni Psaroudaki
• Abstract summary: Label Ranking corresponds to the problem of learning a hypothesis that maps features to rankings over a finite set of labels. We introduce a generative model for Label Ranking, in noiseless and noisy nonparametric regression settings. We complement our theoretical contributions with experiments, aiming to understand how the input regression noise affects the observed output.
• Score: 5.994412766684843
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Label Ranking (LR) corresponds to the problem of learning a hypothesis that maps features to rankings over a finite set of labels. We adopt a nonparametric regression approach to LR and obtain theoretical performance guarantees for this fundamental practical problem. We introduce a generative model for Label Ranking, in noiseless and noisy nonparametric regression settings, and provide sample complexity bounds for learning algorithms in both cases. In the noiseless setting, we study the LR problem with full rankings and provide computationally efficient algorithms using decision trees and random forests in the high-dimensional regime. In the noisy setting, we consider the more general cases of LR with incomplete and partial rankings from a statistical viewpoint and obtain sample complexity bounds using the One-Versus-One approach of multiclass classification. Finally, we complement our theoretical contributions with experiments, aiming to understand how the input regression noise affects the observed output.

Related papers

• Robust Learning under Hybrid Noise [24.36707245704713]
  We propose a novel unified learning framework called "Feature and Label Recovery" (FLR) to combat the hybrid noise from the perspective of data recovery.
  arXiv  Detail & Related papers  (2024-07-04T16:13:25Z)
• Coordinated Sparse Recovery of Label Noise [2.9495895055806804]
  This study focuses on robust classification tasks where the label noise is instance-dependent. We propose a method called Coordinated Sparse Recovery (CSR) CSR introduces a collaboration matrix and confidence weights to coordinate model predictions and noise recovery, reducing error leakage. Based on CSR, this study designs a joint sample selection strategy and constructs a comprehensive and powerful learning framework called CSR+.
  arXiv  Detail & Related papers  (2024-04-07T03:41:45Z)
• PLReMix: Combating Noisy Labels with Pseudo-Label Relaxed Contrastive Representation Learning [7.556169113399857]
  We propose an end-to-end textbfPLReMix framework by introducing a Pseudo-Label Relaxed (PLR) contrastive loss. The proposed PLR loss is pluggable and we have integrated it into other LNL methods, observing their improved performance.
  arXiv  Detail & Related papers  (2024-02-27T15:22:20Z)
• Generalized Oversampling for Learning from Imbalanced datasets and Associated Theory [0.0]
  In supervised learning, it is quite frequent to be confronted with real imbalanced datasets. We propose a data augmentation procedure, the GOLIATH algorithm, based on kernel density estimates. We evaluate the performance of the GOLIATH algorithm in imbalanced regression situations.
  arXiv  Detail & Related papers  (2023-08-05T23:08:08Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Robust Meta-learning with Sampling Noise and Label Noise via Eigen-Reptile [78.1212767880785]
  meta-learner is prone to overfitting since there are only a few available samples. When handling the data with noisy labels, the meta-learner could be extremely sensitive to label noise. We present Eigen-Reptile (ER) that updates the meta- parameters with the main direction of historical task-specific parameters.
  arXiv  Detail & Related papers  (2022-06-04T08:48:02Z)
• Scalable Penalized Regression for Noise Detection in Learning with Noisy Labels [44.79124350922491]
  We propose using a theoretically guaranteed noisy label detection framework to detect and remove noisy data for Learning with Noisy Labels (LNL) Specifically, we design a penalized regression to model the linear relation between network features and one-hot labels. To make the framework scalable to datasets that contain a large number of categories and training data, we propose a split algorithm to divide the whole training set into small pieces.
  arXiv  Detail & Related papers  (2022-03-15T11:09:58Z)
• 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)
• Learning by Minimizing the Sum of Ranked Range [58.24935359348289]
  We introduce the sum of ranked range (SoRR) as a general approach to form learning objectives. A ranked range is a consecutive sequence of sorted values of a set of real numbers. We explore two applications in machine learning of the minimization of the SoRR framework, namely the AoRR aggregate loss for binary classification and the TKML individual loss for multi-label/multi-class classification.
  arXiv  Detail & Related papers  (2020-10-05T01:58:32Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning. Proximal gradient methods are used as standard approaches to solve OWL regression. We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
  arXiv  Detail & Related papers  (2020-06-29T23:35:53Z)

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.