A bound on the label complexity of agnostic active learning

By Steve Hanneke. International Conference on Machine Learning, 2007

326 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/c038e0e9ca986a53043a5ac5061dcb136377ff3a

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

Hierarchical sampling for active learning (2008, background): “Indeed, there are canonical examples in which active learning provably yields exponentially lower label complexity than supervised learning (Cohn et al., 1994; Freund et al., 1997; Dasgupta, 2005; Balcan et al., 2006; Balcan et al., 2007; Castro & Nowak, 2007; Hanneke, 2007; Dasgupta et al., 2007).”
Crowdsourced Data Management: Industry and Academic Perspectives (2015, background): “Papers focusing on the theory of active learning [56, 64, 111, 31, 92, 38, 37, 28, 63, 198, 136] show that the adaptive selection strategies proposed (i.”
The true sample complexity of active learning (2010, methodology): “Using previous results [2, 15], we know that P({x : min{|w · x + b1|, |w · x + b2|} ≤ πr/λ(h)}) ≤ 2π √ nr/λ(h) (since the probability mass contained within this distance of a hyperplane is maximized when the hyperplane passes through the origin).”
A General Agnostic Active Learning Algorithm (2007, methodology): “independently of 1/(ε + ν) in several cases previously considered in the literature [12].”
The power of localization for efficiently learning linear separators with noise (2013, background): “We note that the results from our theorems in this model translate immediately into similar guarantees for the agnostic model of [34] (used commonly both in passive and active learning (e.g., [31, 3, 28]).”
Alignment for Advanced Machine Learning Systems (2020, background): “Hanneke (2007) introduced the disagreement coeﬃcient to measure the overall probability of disagreement among a local ball in the concept space under the “probability of disagreement” pseudo-metric, which resembles a notion of “local ambiguity”; the disagreement coeﬃcient has been used to clarify…”
Active Learning for Convolutional Neural Networks: A Core-Set Approach (2017, methodology): “, 2013) or a data dependent measure of the concept space called disagreement coefficient (Hanneke, 2007).”
Agnostic Selective Classification (2011, unknown): “The disagreement set [4, 1] w.”
A compression technique for analyzing disagreement-based active learning (2014, background): “Perhaps the most well-known of these is for homogeneous linear separators in R k , where the marginal distribution of P over X is conﬁned to be the uniform distribution over the unit sphere, in which case θ ( r 0 ) is known to be within a factor of 4 of min { π √ k , 1 / r 0 } (Hanneke, 2007a).”
Active Learning Literature Survey (2009, background): “Hanneke (2007) extends this work by providing upper bounds on query complexity for the agnostic setting, and Dasgupta et al. (2008) propose a somewhat more efﬁcient query selection algorithm.”
Active and passive learning of linear separators under log-concave distributions (2012, methodology): “…and Koltchinskii, 2006) and the closely related disagreement coefﬁcient notion (Hanneke, 2007), which have been widely used to characterize the sample complexity of various (active and passive) algorithms (Hanneke, 2007; Koltchinskii, 2010; Gin´e and Koltchinskii, 2006; Beygelzimer et al., 2010).”
Two faces of active learning (2011, background): “…data Aggressive Query by committee [13] Splitting index [10] A 2 algorithm [2] Mellow Generic mellow learner [9] Disagreement coeﬃcient [15] Reduction to supervised [12] Importance-weighted approach [5] Figure 5: Some of the key results on active learning within the framework of…”
A theory of transfer learning with applications to active learning (2012, unknown): “As an example, consider training a speech recognizer.”
Agnostic active learning (2006, result): “Subsequent Work Following the initial publication of A2, Hanneke has further analyzed the A2 algorithm [ 26 ], deriving a general upper bound on the number of label requests made by A2. This bound is expressed in terms of par-”
Rates of convergence in active learning (2011, methodology): “The disagreement coefficient, introduced in [14], is a measure of the complexity of an active learning proble m, which has proven quite useful for analyzing the convergence rates of c ertain types of active learning algorithms: for example, the algorithms of [ 3, 5, 9, 10].”