Generalization error bounds in semi-supervised classification under the cluster assumption

Abstract

We consider semi-supervised classification when part of the available data is unlabeled. These unlabeled data can be useful for the classification problem when we make an assumption relating the behavior of the regression function to that of the marginal distribution. Seeger (2000) proposed the well-known "cluster assumption" as a reasonable one. We propose a mathematical formulation of this assumption and a method based on density level sets estimation that takes advantage of it to achieve fast rates of convergence both in the number of unlabeled examples and the number of labeled examples.

References in corpus (2)

• Fast learning rates for plug-in classifiers
• Fast learning rates for plug-in classifiers under the margin condition

Cited by in corpus (20)

• Optimal rates for plug-in estimators of density level sets
• Self-Training: A Survey
• Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data
• Generalized density clustering
• Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm
• Understanding Self-Training for Gradual Domain Adaptation
• Video Unsupervised Domain Adaptation with Deep Learning: A Comprehensive Survey
• A Simple Algorithm for Semi-supervised Learning with Improved Generalization Error Bound
• Improvability Through Semi-Supervised Learning: A Survey of Theoretical Results
• Self-training Avoids Using Spurious Features Under Domain Shift
• Negative sampling in semi-supervised learning
• Disambiguation of weak supervision with exponential convergence rates
• Target-Embedding Autoencoders for Supervised Representation Learning
• Gradient Descent in RKHS with Importance Labeling
• On minimal variations for unsupervised representation learning
• Adaptive Hausdorff estimation of density level sets
• Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning
• Multi-class Probabilistic Bounds for Self-learning
• Optimal rates for F-score binary classification
• Density-based Clustering with Best-scored Random Forest