Error-Correcting Tournaments

We present a family of pairwise tournaments reducing k-class classification to binary classification. These reductions are provably robust against a constant fraction of binary errors, and match the best possible computation and regret up to a constant.

• Publication year

  2009

• Venue

  International Conference on Algorithmic Learning Theory

• Publication date

  2009-02-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-04414-4_22arXiv 0902.3176
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multi-Label Prediction via Compressed Sensing

  2009cited by this paper
• TrueSkillTM: A Bayesian Skill Rating System

  2006cited by this paper
• Sensitive Error Correcting Output Codes

  2005cited by this paper
• Estimating Class Membership Probabilities using Classifier Learners

  2005cited by this paper
• Cost-sensitive learning by cost-proportionate example weighting

  2003influential reference
• Review of An R and S-PLUS companion to applied regression by J. Fox, Sage Publications, Thousand Oaks, California 2002

  2003cited by this paper
• Multicategory Support Vector Machines, Theory, and Application to the Classification of Microarray Data and Satellite Radiance Data

  2002cited by this paper
• Reducing multiclass to binary: a unifying approach for margin classifiers

  2001cited by this paper
• Reliable Minimum Finding Comparator Networks

  2000cited by this paper
• Multiclass learning, boosting, and error-correcting codes

  1999cited by this paper
• Classi cation by Pairwise Coupling

  1998cited by this paper
• UCI Repository of machine learning databases

  1998cited by this paper
• Applied Regression Analysis, Linear Models, and Related Methods

  1997cited by this paper
• Classification by Pairwise Coupling

  1997cited by this paper
• Selection in the presence of noise: the design of playoff systems

  1994cited by this paper
• Solving Multiclass Learning Problems via Error-Correcting Output Codes

  1994cited by this paper
• Comparison-based search in the presence of errors

  1993cited by this paper
• Searching in the presence of linearly bounded errors

  1991cited by this paper
• Computing with unreliable information

  1990cited by this paper
• A personal communication

  1989cited by this paper
• On Selecting the Largest Element in Spite of Erroneous Information

  1987cited by this paper
• On Fault-Tolerant Networks for Sorting

  1979cited by this paper
• Applied Regression Analysis

  1968cited by this paper

• Robust Offline Policy Learning with Observational Data from Multiple Sources

  2024cites this paper
• Theory and algorithms for learning with rejection in binary classification

  2023cites this paper
• Federated Offline Policy Learning

  2023influential citation
• Making Decisions under Outcome Performativity

  2022cites this paper
• Rowan Digital Works Rowan Digital Works

  2021cites this paper
• Enterprise-Scale Search: Accelerating Inference for Sparse Extreme Multi-Label Ranking Trees

  2021cites this paper
• Ensemble Learning using Error Correcting Output Codes: New Classification Error Bounds

  2021cites this paper
• Softmax Tree: An Accurate, Fast Classifier When the Number of Classes Is Large

  2021cites this paper
• Probabilistic Label Trees for Extreme Multi-label Classification

  2020influential citation
• Efficient Contextual Bandits with Continuous Actions

  2020influential citation
• Strategic Exploration in Reinforcement Learning - New Algorithms and Learning Guarantees

  2020cites this paper
• Extreme Multiclass Classification Criteria

  2019cites this paper
• Advances in Cost-sensitive Multiclass and Multilabel Classification

  2019cites this paper
• On the computational complexity of the probabilistic label tree algorithms

  2019cites this paper
• On Calibration of Nested Dichotomies

  2019cites this paper
• On the Calibration of Nested Dichotomies for Large Multiclass Tasks

  2018cites this paper
• Ensembles of Nested Dichotomies with Multiple Subset Evaluation

  2018cites this paper
• Learning Representations of Text through Language and Discourse Modeling: From Characters to Sentences

  2018cites this paper
• A Deep Model With Local Surrogate Loss for General Cost-Sensitive Multi-Label Learning

  2018cites this paper
• Using complexity measures to determine the structure of directed acyclic graphs in multiclass classification

  2018cites this paper
• On Oracle-Efficient PAC Reinforcement Learning with Rich Observations

  2018cites this paper
• On Oracle-Efficient PAC RL with Rich Observations

  2018cites this paper
• A no-regret generalization of hierarchical softmax to extreme multi-label classification

  2018cites this paper
• Label Filters for Large Scale Multilabel Classification

  2017influential citation
• Candidates v.s. Noises Estimation for Large Multi-Class Classification Problem

  2017influential citation
• Progressive random k-labelsets for cost-sensitive multi-label classification

  2017cites this paper
• An Easy-to-hard Learning Paradigm for Multiple Classes and Multiple Labels

  2017cites this paper
• Aggressive Sampling for Multi-class to Binary Reduction with Applications to Text Classification

  2017cites this paper
• Gradient-based Hierarchical Clustering

  2017cites this paper
• Scalable algorithms for large-scale machine learning problems : Application to multiclass classification and asynchronous distributed optimization. (Algorithmes d'apprentissage pour les grandes masses de données : Application à la classification multi-classes et à l'optimisation distribuée asynchron

  2017cites this paper
• A Hierarchical Tree Distance Measure for Classification

  2017cites this paper
• A Novel Uncertainty Sampling Algorithm for Cost-Sensitive Multiclass Active Learning

  2016cites this paper
• Efficient Large Scale Image Classification via Prediction Score Decomposition

  2016cites this paper
• Analysis of Classification-based Policy Iteration Algorithms

  2016cites this paper
• Cost-Sensitive Reference Pair Encoding for Multi-Label Learning

  2016influential citation
• Consistency of Probabilistic Classifier Trees

  2016influential citation
• On the boosting ability of top-down decision tree learning algorithm for multiclass classification

  2016cites this paper
• Simultaneous Learning of Trees and Representations for Extreme Classification and Density Estimation

  2016cites this paper
• Reduction based similarity learning for high dimensional problems

  2016cites this paper
• Cost-Sensitive Random Pair Encoding for Multi-Label Classification

  2016cites this paper
• Learning Taxonomy Adaptation in Large-scale Classification

  2016cites this paper
• Sparse Output Coding for Scalable Visual Recognition

  2016cites this paper
• Logarithmic Time One-Against-Some

  2016cites this paper
• Learning Reductions That Really Work This paper summarizes the mathematical and computational techniques that have enabled learning reductions to effectively address a wide class of tasks.

  2016cites this paper
• Analysis of Classication-bas ed Policy Iteration Algorithms

  2016cites this paper
• Structured machine learning methods for microbiology : mass spectrometry and high-throughput sequencing. (Méthodes d'apprentissage structuré pour la microbiologie : spectrométrie de masse et séquençage haut-débit)

  2015cites this paper
• Learning Reductions That Really Work

  2015influential citation
• Large-scale machine learning for metagenomics sequence classification

  2015cites this paper
• Rapidly Scaling Dialog Systems with Interactive Learning

  2015cites this paper
• Tight risk bounds for multi-class margin classifiers

  2015cites this paper
• Everyone Likes Shopping! Multi-class Product Categorization for e-Commerce

  2015cites this paper
• Active Imitation Learning: Formal and Practical Reductions to I.I.D. Learning

  2015cites this paper
• On Binary Reduction of Large-Scale Multiclass Classification Problems

  2015cites this paper
• Maximum Margin Multiclass Nearest Neighbors

  2014cites this paper
• Reduction from Cost-Sensitive Multiclass Classification to One-versus-One Binary Classification

  2014influential citation
• Selected machine learning reductions

  2014cites this paper
• Condensed Filter Tree for Cost-Sensitive Multi-Label Classification

  2014influential citation
• Towards Scalable Analysis of Images and Videos

  2014cites this paper
• Hierarchical Feature Hashing for Fast Dimensionality Reduction

  2014cites this paper
• Logarithmic Time Online Multiclass prediction

  2014influential citation
• Reinforcement and Imitation Learning via Interactive No-Regret Learning

  2014cites this paper
• University Pierre et Marie Curie

  2014cites this paper
• Logarithmic Time Prediction

  2013cites this paper
• Interactive Learning for Sequential Decisions and Predictions

  2013cites this paper
• Label Partitioning For Sublinear Ranking

  2013cites this paper
• Find the Best Path: An Efficient and Accurate Classifier for Image Hierarchies

  2013cites this paper
• Team chemistry: the missing link in skill assessment for teams

  2013cites this paper
• Extreme Multi Class Classification

  2013cites this paper
• Discriminative Probabilistic Prototype Learning

  2012cites this paper
• Generic subset ranking using binary classifiers

  2012cites this paper
• Efficient Discriminative Learning of Class Hierarchy for Many Class Prediction

  2012cites this paper
• DCMSVM: Distributed parallel training for single-machine multiclass classifiers

  2012cites this paper
• Computer Vision – ACCV 2012

  2012influential citation
• Hierarchical Maximum Margin Learning for Multi-Class Classification

  2011influential citation
• Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity

  2011cites this paper
• Multiclass Learnability and the ERM principle

  2011cites this paper
• New Learning Frameworks for Information Retrieval

  2011cites this paper
• Reducing Position-Sensitive Subset Ranking to Classification

  2011cites this paper
• Efficient Optimal Learning for Contextual Bandits

  2011cites this paper
• Game theory and optimization in boosting

  2011cites this paper
• A theory of multiclass boosting

  2010cites this paper
• Label Embedding Trees for Large Multi-Class Tasks

  2010influential citation
• Robust Efficient Conditional Probability Estimation.

  2010cites this paper
• A Hierarchical Classifier Applied to Multi-way Sentiment Detection

  2010cites this paper
• Machine Learning Techniques—Reductions Between Prediction Quality Metrics

  2008cites this paper