nips nips2007 nips2007-15 nips2007-15-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sanjoy Dasgupta, Claire Monteleoni, Daniel J. Hsu
Abstract: We present an agnostic active learning algorithm for any hypothesis class of bounded VC dimension under arbitrary data distributions. Most previous work on active learning either makes strong distributional assumptions, or else is computationally prohibitive. Our algorithm extends the simple scheme of Cohn, Atlas, and Ladner [1] to the agnostic setting, using reductions to supervised learning that harness generalization bounds in a simple but subtle manner. We provide a fall-back guarantee that bounds the algorithm’s label complexity by the agnostic PAC sample complexity. Our analysis yields asymptotic label complexity improvements for certain hypothesis classes and distributions. We also demonstrate improvements experimentally. 1
[1] D. Cohn, L. Atlas, and R. Ladner. Improving generalization with active learning. Machine Learning, 15(2):201–221, 1994.
[2] Y. Freund, H. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28(2):133–168, 1997.
[3] S. Dasgupta, A. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. In COLT, 2005.
[4] S. Dasgupta. Coarse sample complexity bounds for active learning. In NIPS, 2005.
[5] S. Hanneke. Teaching dimension and the complexity of active learning. In COLT, 2007.
[6] M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In COLT, 2007.
[7] R. Castro and R. Nowak. Upper and lower bounds for active learning. In Allerton Conference on Communication, Control and Computing, 2006.
[8] R. Castro and R. Nowak. Minimax bounds for active learning. In COLT, 2007.
[9] M.-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. In ICML, 2006.
[10] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. UCSD Technical Report CS2007-0898, http://www.cse.ucsd.edu/∼djhsu/papers/cal.pdf, 2007.
[11] M. K¨¨ri¨inen. Active learning in the non-realizable case. In ALT, 2006. aa a
[12] S. Hanneke. A bound on the label complexity of agnostic active learning. In ICML, 2007.
[13] C. Monteleoni. Learning with online constraints: shifting concepts and active learning. PhD Thesis, MIT Computer Science and Artificial Intelligence Laboratory, 2006.
[14] O. Bousquet, S. Boucheron, and G. Lugosi. Introduction to statistical learning theory. Lecture Notes in Artificial Intelligence, 3176:169–207, 2004.
[15] V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264–280, 1971.
[16] C. Monteleoni. Efficient algorithms for general active learning. In COLT. Open problem, 2006.
[17] V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise. In FOCS, 2006. 8