Authors: Joel Ratsaby, and Vitaly Maiorov
Source: Journal of Computer and System Sciences Vol. 58, No. 1, 1999, 183 - 192.
Abstract. 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.
©Copyright 1999, Academic Press