Paper Info
Title
Efficient algorithms for general active learning
Abstract
Selective sampling, a realistic active learning model, has received recent attention in the learning theory literature. While the analysis of selective sampling is still in its infancy, we focus here on one of the (seemingly) simplest problems that remain open. Given a pool of unlabeled examples, drawn i.i.d. from an arbitrary input distribution known to the learner, and oracle access to their labels, the objective is to achieve a target error-rate with minimum label-complexity, via an efficient algorithm. No prior distribution is assumed over the concept class, however the problem remains open even under the realizability assumption: there exists a target hypothesis in the concept class that perfectly classifies all examples, and the labeling oracle is noiseless. As a precise variant of the problem, we consider the case of learning homogeneous half-spaces in the realizable setting: unlabeled examples, xt, are drawn i.i.d. from a known distribution D over the surface of the unit ball in ℝdand labels ytare either –1 or +1. The target function is a half-space ux ≥0 represented by a unit vector u ∈ℝdsuch that yt(uxt) 0 for all t. We denote a hypothesis v’s prediction as v(x)=SGN(v ·x).
Year
DOI
Venue
2006
10.1007/11776420_47
COLT
Keywords
Field
DocType
concept class,realistic active learning model,target function,arbitrary input distribution,general active learning,unlabeled example,prior distribution,hypothesis v,known distribution,selective sampling,efficient algorithm,target error-rate,active learning,error rate,learning theory,unit ball
Computer science,Oracle,Artificial intelligence,Discrete mathematics,Active learning,Existential quantification,Concept class,Algorithm,Prior probability,Realizability,Machine learning,Unit sphere,Unit vector
Conference
Volume
ISSN
ISBN
4005
0302-9743
3-540-35294-5
Citations 
PageRank 
References 
2
0.54
12
Authors
1
Name
Order
Citations
PageRank
Claire Monteleoni132724.15