nips nips2010 nips2010-173 nips2010-173-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Wei Wang, Zhi-hua Zhou
Abstract: The sample complexity of active learning under the realizability assumption has been well-studied. The realizability assumption, however, rarely holds in practice. In this paper, we theoretically characterize the sample complexity of active learning in the non-realizable case under multi-view setting. We prove that, with unbounded Tsybakov noise, the sample complexity of multi-view active learning can be O(log 1 ), contrasting to single-view setting where the polynomial improveǫ ment is the best possible achievement. We also prove that in general multi-view setting the sample complexity of active learning with unbounded Tsybakov noise is O( 1 ), where the order of 1/ǫ is independent of the parameter in Tsybakov noise, ǫ contrasting to previous polynomial bounds where the order of 1/ǫ is related to the parameter in Tsybakov noise. 1
[1] M. Anthony and P. L. Bartlett, editors. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, UK, 1999.
[2] M.-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. In ICML, pages 65–72, 2006.
[3] M.-F. Balcan, A. Blum, and K. Yang. Co-training and expansion: Towards bridging theory and practice. In NIPS 17, pages 89–96. 2005.
[4] M.-F. Balcan, A. Z. Broder, and T. Zhang. Margin based active learning. In COLT, pages 35–50, 2007.
[5] M.-F. Balcan, S. Hanneke, and J. Wortman. The true sample complexity of active learning. In COLT, pages 45–56, 2008.
[6] A. Blum and T. Mitchell. Combining labeled and unlabeled data with co-training. In COLT, pages 92–100, 1998.
[7] R. M. Castro and R. D. Nowak. Upper and lower error bounds for active learning. In Allerton Conference, pages 225–234, 2006.
[8] R. M. Castro and R. D. Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):2339–2353, 2008.
[9] G. Cavallanti, N. Cesa-Bianchi, and C. Gentile. Linear classification and selective sampling under low noise conditions. In NIPS 21, pages 249–256. 2009.
[10] D. A. Cohn, L. E. Atlas, and R. E. Ladner. Improving generalization with active learning. Machine Learning, 15(2):201–221, 1994.
[11] S. Dasgupta. Analysis of a greedy active learning strategy. In NIPS 17, pages 337–344. 2005.
[12] S. Dasgupta. Coarse sample complexity bounds for active learning. In NIPS 18, pages 235– 242. 2006.
[13] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In NIPS 20, pages 353–360. 2008.
[14] S. Dasgupta, A. T. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. In COLT, pages 249–263, 2005.
[15] L. Devroye, L. Gy¨ rfi, and G. Lugosi, editors. A Probabilistic Theory of Pattern Recognition. o Springer, New York, 1996.
[16] Y. Freund, H. S. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28(2-3):133–168, 1997.
[17] S. Hanneke. A bound on the label complexity of agnostic active learning. In ICML, pages 353–360, 2007.
[18] S. Hanneke. Adaptive rates of convergence in active learning. In COLT, 2009.
[19] M. K¨ ari¨ inen. Active learning in the non-realizable case. In ACL, pages 63–77, 2006. a¨ a
[20] I. Muslea, S. Minton, and C. A. Knoblock. Active + semi-supervised learning = robust multiview learning. In ICML, pages 435–442, 2002.
[21] A. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166, 2004.
[22] L. Wang. Sufficient conditions for agnostic active learnable. In NIPS 22, pages 1999–2007. 2009.
[23] W. Wang and Z.-H. Zhou. On multi-view active learning and the combination with semisupervised learning. In ICML, pages 1152–1159, 2008. 9