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.