Investigating the Sample Complexity of Active Learning Schemes
In the classical learning framework of the previous chapter (akin to PAC) examples were randomly drawn and presented to the learner. In this chapter, we consider the possibility of a more active learner who is allowed to choose his/her own examples. Our investigations can be divided into two natural parts. The first, is in a function approximation setting, and develops an adaptive sampling strategy (equivalent to adaptive approximation) motivated from the standpoint of optimal recovery (Micchelli and Rivlin, 1976). We provide a general formulation of the problem. This can be regarded as sequential optimal recovery. We demonstrate the application of this general formulation to two special cases of functions on the real line 1) monotonically increasing functions and 2) functions with bounded derivative. An extensive investigation of the sample complexity of approximating these functions is conducted yielding both theoretical and empirical results on test functions. Our theoretical results (stated in PAC-style), along with the simulations demonstrate the superiority of our active scheme over both passive learning as well as classical optimal recovery. The second part of this chapter is in a concept learning framework and discusses the idea of ∈-focusing: a scheme where the active learner can iteratively draw examples from smaller and smaller regions of the input space thereby gaining vast improvements in sample complexity.