Efficient Active Learning of Halfspaces: an Aggressive Approach

Abstract

We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches. Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings.

Full version of: Gonen, Sabato and Shalev-Shwartz, "Efficient Active Learning of Halfspaces: an Aggressive Approach", ICML 2013

References in corpus (1)

• Tight Sample Complexity of Large-Margin Learning

Cited by in corpus (9)

• Active Learning for Convolutional Neural Networks: A Core-Set Approach
• Active Nearest-Neighbor Learning in Metric Spaces
• Interactive algorithms: from pool to stream
• Auditing: Active Learning with Outcome-Dependent Query Costs
• Exact Recovery of Mangled Clusters with Same-Cluster Queries
• Flattening a Hierarchical Clustering through Active Learning
• A Structured Perspective of Volumes on Active Learning
• Beating the Minimax Rate of Active Learning with Prior Knowledge
• Frugal Machine Learning