The Power of Comparisons for Actively Learning Linear Classifiers
arXiv:1907.03816
Abstract
In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced to explore whether adaptive labeling could learn concepts with exponentially fewer labeled samples. While previous results show that active learning performs no better than its supervised alternative for important concept classes such as linear separators, we show that by adding weak distributional assumptions and allowing comparison queries, active learning requires exponentially fewer samples. Further, we show that these results hold as well for a stronger model of learning called Reliable and Probably Useful (RPU) learning. In this model, our learner is not allowed to make mistakes, but may instead answer "I don't know." While previous negative results showed this model to have intractably large sample complexity for label queries, we show that comparison queries make RPU-learning at worst logarithmically more expensive in both the passive and active regimes.
References in corpus (6)
- Risk bounds for statistical learning
- Adaptively Learning the Crowd Kernel
- The Optimal Sample Complexity of PAC Learning
- Noise-adaptive Margin-based Active Learning and Lower Bounds under Tsybakov Noise Condition
- Generalized comparison trees for point-location problems
- Noise-tolerant, Reliable Active Classification with Comparison Queries