Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm

Abstract

We propose Rademacher complexity bounds for multiclass classifiers trained with a two-step semi-supervised model. In the first step, the algorithm partitions the partially labeled data and then identifies dense clusters containing $\kappa$ predominant classes using the labeled training examples such that the proportion of their non-predominant classes is below a fixed threshold. In the second step, a classifier is trained by minimizing a margin empirical loss over the labeled training set and a penalization term measuring the disability of the learner to predict the $\kappa$ predominant classes of the identified clusters. The resulting data-dependent generalization error bound involves the margin distribution of the classifier, the stability of the clustering technique used in the first step and Rademacher complexity terms corresponding to partially labeled training data. Our theoretical result exhibit convergence rates extending those proposed in the literature for the binary case, and experimental results on different multiclass classification problems show empirical evidence that supports the theory.

arXiv comment26 pages, 6 figures

References in corpus (7)

• Consistency of spectral clustering
• Empirical Bernstein Bounds and Sample Variance Penalization
• Generalization error bounds in semi-supervised classification under the cluster assumption
• Transductive Rademacher Complexity and its Applications
• Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms
• Tight Risk Bounds for Multi-Class Margin Classifiers
• Permutational Rademacher Complexity: a New Complexity Measure for Transductive Learning

Cited by in corpus (5)

• Self-Training: A Survey
• Multi-class Classification with Fuzzy-feature Observations: Theory and Algorithms
• Semi-supervised Vector-valued Learning: Improved Bounds and Algorithms
• Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Model
• Multi-class Probabilistic Bounds for Self-learning