Robust bounds for classification via selective sampling

ABSTRACT

We introduce a new algorithm for binary classification in the selective sampling protocol. Our algorithm uses Regularized Least Squares (RLS) as base classifier, and for this reason it can be efficiently run in any RKHS. Unlike previous margin-based semi-supervised algorithms, our sampling condition hinges on a simultaneous upper bound on bias and variance of the RLS estimate under a simple linear label noise model. This fact allows us to prove performance bounds that hold for an arbitrary sequence of instances. In particular, we show that our sampling strategy approximates the margin of the Bayes optimal classifier to any desired accuracy ε by asking Õ (d/ε²) queries (in the RKHS case d is replaced by a suitable spectral quantity). While these are the standard rates in the fully supervised i.i.d. case, the best previously known result in our harder setting was Õ (d³/ε⁴). Preliminary experiments show that some of our algorithms also exhibit a good practical performance.

REFERENCES

• 1: Peter Auer, Using confidence bounds for exploitation-exploration trade-offs, The Journal of Machine Learning Research, 3, 3/1/2003
• 2: 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]
• 3: Balcan, M., Broder, A., & Zhang, T. (2007). Margin-based active learning. Proceedings of the 20th Annual Conference on Learning Theory (pp. 35--50).
• 4: Giovanni Cavallanti , Nicolò Cesa-Bianchi , Claudio Gentile, Tracking the best hyperplane with a simple budget Perceptron, Machine Learning, v.69 n.2-3, p.143-167, December 2007 [doi>10.1007/s10994-007-5003-0]
• 5: Cavallanti, G., Cesa-Bianchi, N., & Gentile, C. (2009). Linear classification and selective sampling under low noise conditions. In Advances in Neural Information Processing Systems 21 (pp. 249--256).
• 6: Nicolò Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Incremental Algorithms for Hierarchical Classification, The Journal of Machine Learning Research, 7, p.31-54, 12/1/2006
• 7: Nicolò Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Worst-Case Analysis of Selective Sampling for Linear Classification, The Journal of Machine Learning Research, 7, p.1205-1230, 12/1/2006
• 8: Les Atlas , David Cohn , Richard Ladner , M. A. El-Sharkawi , R. J. Marks, II, Training connectionist networks with queries and selective sampling, Advances in neural information processing systems 2, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 9: Dasgupta, S., Hsu, D., & Monteleoni, C. (2008). A general agnostic active learning algorithm. In Advances in Neural Information Processing Systems 21 (pp. 353--360).
• 10: Dasgupta, S., Kalai, A. T., & Monteleoni, C. (2005). Analysis of perceptron-based active learning. Proceedings of the 18th Annual Conference on Learning Theory (pp. 249--263).
• 11: Ofer Dekel , Shai Shalev-Shwartz , Yoram Singer, The Forgetron: A Kernel-Based Perceptron on a Budget, SIAM Journal on Computing, v.37 n.5, p.1342-1372, January 2008 [doi>10.1137/060666998]
• 12: Yoav Freund , H. Sebastian Seung , Eli Shamir , Naftali Tishby, Selective Sampling Using the Query by Committee Algorithm, Machine Learning, v.28 n.2-3, p.133-168, Aug./Sept. 1997 [doi>10.1023/A:1007330508534]
• 13: Lihong Li , Michael L. Littman , Thomas J. Walsh, Knows what it knows: a framework for self-aware learning, Proceedings of the 25th international conference on Machine learning, p.568-575, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390228]
• 14: Francesco Orabona , Joseph Keshet , Barbara Caputo, The projectron: a bounded kernel-based Perceptron, Proceedings of the 25th international conference on Machine learning, p.720-727, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390247]
• 15: Strehl, A., & Littman, M. (2008). Online linear regression and its application to model-based reinforcement learning. In Advances in Neural Information Processing Systems 20 (pp. 631--638).
• 16: Weston, J., Bordes, A., & Bottou, L. (2005). Online (and offline) on an even tighter budget. Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (pp. 413--420).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  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