Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
- URL: http://arxiv.org/abs/2307.00642v1
- Date: Sun, 2 Jul 2023 19:26:58 GMT
- Title: Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
- Authors: Nataly Brukhim, Amit Daniely, Yishay Mansour, Shay Moran
- Abstract summary: We give a simple and efficient boosting algorithm, that does not require realizability assumptions.
We present a new result on boosting for list learners, as well as provide a novel proof for the characterization of multiclass PAC learning.
- Score: 72.71096438538254
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a generalization of boosting to the multiclass setting. We introduce
a weak learning condition for multiclass classification that captures the
original notion of weak learnability as being "slightly better than random
guessing". We give a simple and efficient boosting algorithm, that does not
require realizability assumptions and its sample and oracle complexity bounds
are independent of the number of classes.
In addition, we utilize our new boosting technique in several theoretical
applications within the context of List PAC Learning. First, we establish an
equivalence to weak PAC learning. Furthermore, we present a new result on
boosting for list learners, as well as provide a novel proof for the
characterization of multiclass PAC learning and List PAC learning. Notably, our
technique gives rise to a simplified analysis, and also implies an improved
error bound for large list sizes, compared to previous results.
Related papers
- A Hard-to-Beat Baseline for Training-free CLIP-based Adaptation [121.0693322732454]
Contrastive Language-Image Pretraining (CLIP) has gained popularity for its remarkable zero-shot capacity.
Recent research has focused on developing efficient fine-tuning methods to enhance CLIP's performance in downstream tasks.
We revisit a classical algorithm, Gaussian Discriminant Analysis (GDA), and apply it to the downstream classification of CLIP.
arXiv Detail & Related papers (2024-02-06T15:45:27Z) - AdaBoost is not an Optimal Weak to Strong Learner [11.003568749905359]
We show that the sample complexity of AdaBoost, and other classic variations thereof, are sub-optimal by at least one logarithmic factor in the desired accuracy of the strong learner.
arXiv Detail & Related papers (2023-01-27T07:37:51Z) - Synergies between Disentanglement and Sparsity: Generalization and
Identifiability in Multi-Task Learning [79.83792914684985]
We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations.
Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
arXiv Detail & Related papers (2022-11-26T21:02:09Z) - Optimal Weak to Strong Learning [12.999258817707412]
We present a new algorithm that constructs a strong learner from a weak learner but uses less training data than AdaBoost.
A sample complexity lower bound shows that our new algorithm uses the minimum possible amount of training data and is thus optimal.
arXiv Detail & Related papers (2022-06-03T13:37:12Z) - Chaos is a Ladder: A New Theoretical Understanding of Contrastive
Learning via Augmentation Overlap [64.60460828425502]
We propose a new guarantee on the downstream performance of contrastive learning.
Our new theory hinges on the insight that the support of different intra-class samples will become more overlapped under aggressive data augmentations.
We propose an unsupervised model selection metric ARC that aligns well with downstream accuracy.
arXiv Detail & Related papers (2022-03-25T05:36:26Z) - PRBoost: Prompt-Based Rule Discovery and Boosting for Interactive
Weakly-Supervised Learning [57.66155242473784]
Weakly-supervised learning (WSL) has shown promising results in addressing label scarcity on many NLP tasks.
Our proposed model, named PRBoost, achieves this goal via iterative prompt-based rule discovery and model boosting.
Experiments on four tasks show PRBoost outperforms state-of-the-art WSL baselines up to 7.1%.
arXiv Detail & Related papers (2022-03-18T04:23:20Z) - Quantum Boosting using Domain-Partitioning Hypotheses [0.9264464791978363]
Boosting is an ensemble learning method that converts a weak learner into a strong learner in the PAC learning framework.
We show that Q-RealBoost provides a speedup over Q-AdaBoost in terms of both the bias of the weak learner and the time taken by the weak learner to learn the target concept class.
arXiv Detail & Related papers (2021-10-25T10:46:13Z) - Class-Incremental Learning with Generative Classifiers [6.570917734205559]
We propose a new strategy for class-incremental learning: generative classification.
Our proposal is to learn the joint distribution p(x,y), factorized as p(x|y)p(y), and to perform classification using Bayes' rule.
As a proof-of-principle, here we implement this strategy by training a variational autoencoder for each class to be learned.
arXiv Detail & Related papers (2021-04-20T16:26:14Z) - MP-Boost: Minipatch Boosting via Adaptive Feature and Observation
Sampling [0.0]
MP-Boost is an algorithm loosely based on AdaBoost that learns by adaptively selecting small subsets of instances and features.
We empirically demonstrate the interpretability, comparative accuracy, and computational time of our approach on a variety of binary classification tasks.
arXiv Detail & Related papers (2020-11-14T04:26:13Z) - Prototypical Contrastive Learning of Unsupervised Representations [171.3046900127166]
Prototypical Contrastive Learning (PCL) is an unsupervised representation learning method.
PCL implicitly encodes semantic structures of the data into the learned embedding space.
PCL outperforms state-of-the-art instance-wise contrastive learning methods on multiple benchmarks.
arXiv Detail & Related papers (2020-05-11T09:53:36Z)
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.