Analysis of Perceptron-Based Active Learning

By Sanjoy Dasgupta, Adam Tauman Kalai, Claire Monteleoni. 2009

300 citations recorded by the source corpus.

We start by showing that in an active learning setting, the Perceptron algorithm needs Ω(1/∈ 2 ) labels to learn linear separators within generalization error ∈. We then present a simple selective sampling algorithm for this problem, which combines a modification of the perceptron update with an adaptive filtering rule for deciding which points to query. For data distributed uniformly over the unit sphere, we show that our algorithm reaches generalization error e after asking for just O(d log 1/∈) labels. This exponential improvement over the usual sample complexity of supervised learning has previously been demonstrated only for the computationally more complex query-by-committee algorithm.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Incremental Learning from Scratch for Task-Oriented Dialogue Systems (2019, background): “This is similar to active learning (Balcan et al., 2009; Dasgupta et al., 2005).”
Importance weighted active learning (2008, background): “…special cases, where the number of labels needed to learn actively has been shown to be logarithmic in the usual sample complexity of passive learning; such cases include thresholds on a line, and linear separators with a spherically uniform unlabeled data distribution (Dasgupta et al., 2005).”
Margin Based Active Learning (2007, methodology): “We consider here a commonly studied setting in the active learning literature [7–9].”
Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations (2012, result): “Our results mirror the observation in active learning that noise free and large margin learning of half spaces can be achieved much more rapidly than identifying a linear separator in the noisy case (Bshouty & Wattad, 2006; Dasgupta et al., 2009).”
The true sample complexity of active learning (2010, background): “Since C1 trivially has sample complexity 1, and (C2,D) is known to be learnable at an exponential rate (Dasgupta 2005; Balcan et al. 2007; Hanneke 2007a; Dasgupta et al. 2005), combined with Theorem 2, this would imply the result.”
Agnostic active learning (2006, background): “There are several other papers that assume only realizability [21, 24 ].”
Active Learning Literature Survey (2009, background): “The few analyses performed on efﬁcient algorithms have assumed uniform or near-uniform input distributions (Balcan et al., 2006; Dasgupta et al., 2005), or severely restricted hypothesis spaces.”
Active and passive learning of linear separators under log-concave distributions (2012, methodology): “in the unit ball (Balcan et al., 2007; Dasgupta et al., 2005; Freund et al., 1997); even for this special case, our analysis improves by a multiplicative log log(1/ε) factor the results of (Balcan et al.”
A General Agnostic Active Learning Algorithm (2007, background): “Subsequently, Dasgupta, Kalai, and Monteleoni [8] showed that a simple variant of the perceptron algorithm also achieves this label complexity, even for a worst-case (non-Bayesian) choice of target hypothesis.”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “From this, we obtain E [(cid:13) r 22 ] ≤ 4 e − da 2 / 2 as claimed.”
A brief introduction to weakly supervised learning (2018, background): “For example, it has been proven that for realizable cases (where there exists a hypothesis perfectly separating the data in the hypothesis class), exponential improvement in sample complexity can be obtained by active learning [22, 24].”
Query by Committee Made Real (2005, methodology): “Two other notable algorithms are the greedy active learning algorithm [11] and the perceptron based active learning algorithm [12].”
Understanding the risk factors of learning in adversarial environments (2011, background): “[5] note that the above probability over the uniform distribution is simply given by”
Coarse sample complexity bounds for active learning (2005, background): “So far the most encouraging theoretical results in this field are [7, 6], which show that if the hypothesis class is that of homogeneous (i.”
Active Learning as Non-Convex Optimization (2009, methodology): “Variations of some of these algorithms and objective functions have been previously proposed (Dasgupta et al., 2005; Cesa-Bianchi et al., 2006; Monteleoni and Kaariainen, 2007) without noting this connection.”