On the learnability of rich function classes
The probably approximately correct ( PAC) model of learning and its extension to real-valued function classes sets a rigorous framework based upon which the complexity of learning a target from a function class using a finite sample can be computed. There is one main restriction, however, that the function class have a finite VC-dimension or scale-sensitive pseudo-dimension. In this paper we present an extension of the PAC framework with which rich function classes with possibly infinite pseudo-dimension may be learned with a finite number of examples and a finite amount of partial information. As an example we consider learning a family of infinite dimensional Sobolev classes. (C) 1999 Academic Press.
partial information pac learning computational learning theory information-based complexity vc-theory approximation theory