On the value of partial information for learning from examples

The PAC model of learning and its extension to real valued function classes provides a well-accepted theoretical framework for representing the problem of learning a target function g(x) using a random sample {(x(i), g(x(i)))}(i=1)(m). Based on the uniform strong law of large numbers the PAC model establishes the sample complexity, i.e., the sample size m which is sufficient for accurately estimating the target function to within high confidence. Often, in addition to a random sample, some form of prior knowledge is available about the target. It is intuitive that increasing the amount of information should have the same effect on the error as increasing the sample size. But quantitatively how does the rate of error with respect to increasing information compare to the rate of error with increasing sample size? To answer this we consider a new approach based on a combination of information-based complexity of Traub et al. and Vapnik-Chervonenkis (VC) theory. In contrast to VC-theory where function classes of finite pseudo-dimension are used only for statistical-based estimation, we let such classes play a dual role of functional estimation as well as approximation. This is captured in a newly introduced quantity, rho(d)(F), which represents a nonlinear width of a function class F. We then extend the notion of the nth minimal radius of information and define a quantity I-n,I-d(F) which measures the minimal approximation error of the worst-case target g is an element of F by the family of function classes having pseudo-dimension d given partial information on g consisting of values taken by n linear operators. The error rates are calculated which leads to a quantitative notion of the value of partial information for the paradigm of learning from examples. (C) 1997 Academic Press.