Activized Learning: Transforming Passive to Active with Improved Label Complexity
arXiv:1108.1766
Abstract
We study the theoretical advantages of active learning over passive learning. Specifically, we prove that, in noise-free classifier learning for VC classes, any passive learning algorithm can be transformed into an active learning algorithm with asymptotically strictly superior label complexity for all nontrivial target functions and distributions. We further provide a general characterization of the magnitudes of these improvements in terms of a novel generalization of the disagreement coefficient. We also extend these results to active learning in the presence of label noise, and find that even under broad classes of noise distributions, we can typically guarantee strict improvements over the known results for passive learning.
References in corpus (7)
- 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
- Risk bounds for statistical learning
- Concentration inequalities and asymptotic results for ratio type empirical processes
- Agnostic Active Learning Without Constraints
- Asymptotic distribution and sparsistency for l1-penalized parametric M-estimators with applications to linear SVM and logistic regression
- MDL Convergence Speed for Bernoulli Sequences
- A note on active learning for smooth problems
Cited by in corpus (6)
- Surrogate Losses in Passive and Active Learning
- Asymptotic Analysis of Objectives based on Fisher Information in Active Learning
- Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound
- Learning with a Drifting Target Concept
- A Compression Technique for Analyzing Disagreement-Based Active Learning
- Refined Error Bounds for Several Learning Algorithms