Importance weighted active learning

ABSTRACT

We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process.

REFERENCES

• 1: Naoki Abe , Hiroshi Mamitsuka, Query Learning Strategies Using Boosting and Bagging, Proceedings of the Fifteenth International Conference on Machine Learning, p.1-9, July 24-27, 1998
• 2: Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 68, 357--367.
• 3: Bach, F. (2007). Active learning for misspecified generalized linear models. In Advances in neural information processing systems 19. Cambridge, MA: MIT Press.
• 4: Maria-Florina Balcan , Alina Beygelzimer , John Langford, Agnostic active learning, Proceedings of the 23rd international conference on Machine learning, p.65-72, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143853]
• 5: Beygelzimer, A., Dasgupta, S., & Langford, J. (2008). Importance weighted active learning. arXiv:0812.4952v2 {cs.LG}.
• 6: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 7: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 8: Sanjoy Dasgupta , Daniel Hsu, Hierarchical sampling for active learning, Proceedings of the 25th international conference on Machine learning, p.208-215, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390183]
• 9: Dasgupta, S., Hsu, D., & Monteleoni, C. (2008). A general agnostic active learning algorithm. In Advances in neural information processing systems, vol. 20, 353--360.
• 10: Dasgupta, S., Kalai, A. T., & Monteleoni, C. (2005). Analysis of perceptron-based active learning. Proceedings of the Annual Conference on Learning Theory (pp. 249--263).
• 11: Devroye, L., Gyorfi, L., & Lugosi, G. (1996). A probabilistic theory of pattern recognition. Springer.
• 12: Steve Hanneke, A bound on the label complexity of agnostic active learning, Proceedings of the 24th international conference on Machine learning, p.353-360, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273541]
• 13: Kääriäinen, M. (2006). Active learning in the non-realizable case. Proceedings of 17th International Conference on Algorithmic Learning Theory (pp. 63--77).
• 14: John Langford, Tutorial on Practical Prediction Theory for Classification, The Journal of Machine Learning Research, 6, p.273-306, 12/1/2005
• 15: Slud, E. (1977). Distribution inequalities for the binomial law. Annals of Probability, 5, 404--412.
• 16: Sugiyama, M. (2006). Active learning for misspecified models. In Advances in neural information processing systems, vol. 18, 1305--1312. Cambridge, MA: MIT Press.
• 17: Bianca Zadrozny , John Langford , Naoki Abe, Cost-Sensitive Learning by Cost-Proportionate Example Weighting, Proceedings of the Third IEEE International Conference on Data Mining, p.435, November 19-22, 2003

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory