Author: B. Natarajan
Source: SIAM Journal on Computing Vol. 29, No. 3, 1999, 712-727.
Abstract. An Occam approximation is an algorithm that takes as input a set of samples of a function and a tolerance $\epsilon$ and produces as output a compact representation of a function that is within $\epsilon$ 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. One consequence of our results is a general technique for the design and analysis of nonlinear filters in digital signal processing.
©Copyright 1999, Society for Industrial and Applied Mathematics.