nips nips2010 nips2010-27 nips2010-27-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alina Beygelzimer, John Langford, Zhang Tong, Daniel J. Hsu
Abstract: We present and analyze an agnostic active learning algorithm that works without keeping a version space. This is unlike all previous approaches where a restricted set of candidate hypotheses is maintained throughout learning, and only hypotheses from this set are ever returned. By avoiding this version space approach, our algorithm sheds the computational burden and brittleness associated with maintaining version spaces, yet still allows for substantial improvements over supervised learning for classification. 1
[1] D. Cohn, L. Atlas, and R. Ladner. Improving generalization with active learning. Machine Learning, 15(2):201–221, 1994.
[2] S. Dasgupta. Coarse sample complexity bounds for active learning. In Advances in Neural Information Processing Systems 18, 2005.
[3] M.-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. In Twenty-Third International Conference on Machine Learning, 2006.
[4] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In Advances in Neural Information Processing Systems 20, 2007.
[5] A. Beygelzimer, S. Dasgupta, and J. Langford. Importance weighted active learning. In Twenty-Sixth International Conference on Machine Learning, 2009.
[6] S. Hanneke. Adaptive rates of convergence in active learning. In Twenty-Second Annual Conference on Learning Theory, 2009.
[7] V. Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. Manuscript, 2009.
[8] M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In Twentieth Annual Conference on Learning Theory, 2007.
[9] R. .S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
[10] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal of Computing, 32:48–77, 2002.
[11] M. Sugiyama, M. Krauledat, and K.-R. M¨ ller. Covariate shift adaptation by importance weighted cross u validation. Journal of Machine Learning Research, 8:985–1005, 2007.
[12] M. Sugiyama. Active learning for misspecified models. In Advances in Neural Information Processing Systems 18, 2005.
[13] F. Bach. Active learning for misspecified generalized linear models. In Advances in Neural Information Processing Systems 19, 2006.
[14] S. Hanneke. A bound on the label complexity of agnostic active learning. In Twenty-Fourth International Conference on Machine Learning, 2007.
[15] M. K¨ ari¨ inen. Active learning in the non-realizable case. In Seventeenth International Conference on a¨ a Algorithmic Learning Theory, 2006.
[16] A. B. Tsybakov. Optimal aggregation of classifiers in statistical learning. Annals of Statistics, 32(1):135– 166, 2004.
[17] R. Castro and R. Nowak. Upper and lower bounds for active learning. In Allerton Conference on Communication, Control and Computing, 2006.
[18] R. Castro and R. Nowak. Minimax bounds for active learning. In Twentieth Annual Conference on Learning Theory, 2007.
[19] T. Zhang. Data dependent concentration bounds for sequential prediction algorithms. In Eighteenth Annual Conference on Learning Theory, 2005.
[20] E. Friedman. Active learning for smooth problems. In Twenty-Second Annual Conference on Learning Theory, 2009.
[21] L. Wang. Sufficient conditions for agnostic active learnable. In Advances in Neural Information Processing Systems 22, 2009.
[22] S. Dasgupta and D. Hsu. Hierarchical sampling for active learning. In Twenty-Fifth International Conference on Machine Learning, 2008. 9