|
NeuroCOLT
Technical Report NC-TR-96-050
Learning from
Examples and Side Information
Joel
Ratsaby
Technion
Israel
Vitaly
Maiorov
Technion
Israel
Abstract
We set up a theoretical framework for learning from examples and side
information which enables us to compute the tradeoff between the sample
complexity and information complexity for learning a target function
in a Sobolev functional class $\cal F$. We use the notion of the $n^{th}$
minimal radius of information of Traub et. al. and combine
it with VC-theory to define a new quantity $I_{n,d}({\cal F})$ which
measures the minimal approximation error of a target $g\in {\cal F}$
by the family of function classes with pseudo-dimension $d$ under
a given side information which consists of any $n$ measurements on
the target function $g$ constrained to being linear operators. By
obtaining almost tight upper and lower bounds on $I_{n,d}({\cal F})$
we find an information operator $\hat{N}_n$ which yields a worst-case
error no larger than a logarithmic factor in $n$ and $d$ than the
lower bound on $I_{n,d}({\cal F})$. Hence to within a logarithmic
factor it is the most efficient way of providing side information
about a target $g$ under the constraint that the information operator
must be linear and that the approximating class has pseudo-dimension
$d$.
Download Compressed
Postscript
|