HP Labs Technical Reports

On Learning Functions from Noise-Free and Noisy Samples via Occam's Razor

Natarajan, Balas K.

HPL-94-112

Keyword(s):

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 non-linear filters in digital signal processing.

Back to Index