nips nips2004 nips2004-23 nips2004-23-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sanjoy Dasgupta
Abstract: We abstract out the core search problem of active learning schemes, to better understand the extent to which adaptive labeling can improve sample complexity. We give various upper and lower bounds on the number of labels which need to be queried, and we prove that a popular greedy active learning rule is approximately as good as any other strategy for minimizing this number of labels. 1
[1] D. Angluin. Queries and concept learning. Machine Learning, 2:319–342, 1988.
[2] D. Angluin. Queries revisited. Proceedings of the Twelfth International Conference on Algorithmic Learning Theory, pages 12–31, 2001.
[3] E.B. Baum and K. Lang. Query learning can work poorly when a human oracle is used. International Joint Conference on Neural Networks, 1992.
[4] A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. Oriented matroids. Cambridge University Press, 1999.
[5] D. Cohn, Z. Ghahramani, and M. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 4:129–145, 1996.
[6] S. Dasgupta, P.M. Long, and W.S. Lee. A theoretical analysis of query selection for collaborative filtering. Machine Learning, 51:283–298, 2003.
[7] Y. Freund, S. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28:133–168, 1997.
[8] D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256–278, 1974.
[9] M.J. Kearns and U.V. Vazirani. An introduction to computational learning theory. MIT Press, 1993.
[10] A. McCallum and K. Nigam. Employing em and pool-based active learning for text classification. Fifteenth International Conference on Machine Learning, 1998.
[11] N. Roy and A. McCallum. Toward optimal active learning through sampling of error reduction. Twentieth International Conference on Machine Learning, 2003.
[12] J. Shawe-Taylor, P. Bartlett, R. Williamson, and M. Anthony. Structural risk minimization over data-dependent hierarchies. IEEE Transactions on Information Theory, 1998.
[13] S. Tong and D. Koller. Support vector machine active learning with applications to text classification. Journal of Machine Learning Research, 2001.
[14] X. Zhu, J. Lafferty, and Z. Ghahramani. Combining active learning and semi-supervised learning using gaussian fields and harmonic functions. ICML workshop, 2003.