2021/11/04 by Dimitris Fotakis, Fotakis, Dimitris, Alkis Kalavasis +3
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Rough Sets and Fuzzy Logic #cs.LG
paper · pdf · doi:10.48550/arxiv.2111.02749
openalex publication_date 2021/11/04 · arxiv created 2022/02/10 · arxiv updated 2022/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.