Theory Seminar
B. K. Natarajan
Hewlett Packard Laboratories
Learning Functions via Occam's Razor
with Application to Filtering
Friday March 25, 1994
Wean Hall 7220 2:30-4:00
Abstract
An Occam approximation is an algorithm that constructs sparse but
approximate interpolants, i.e., it takes as input a set of samples of
a function and an approximation tolerance E, and produces as output a
compact representation of a function that is within E of the given
samples. We show that the existence of an Occam approximation is
sufficient to guarantee the probably approximate learnability of
classes of functions on the reals even in the presence of arbitrarily
large but random additive noise. Specifically, we show that setting
the tolerance E equal to the strength of the noise causes the noise
and the approximation error to cancel rather than add. A practical
consequence of this result is a general technique for the construction
of non-linear filters for random noise.