Occam Algorithms for Learning from Noisy Examples

Abstract

In the distribution-independent model of concept learning from examples introduced by Valiant [Va184], it has been shown that the existence of an Occam algorithm for a dass of concepts implies the computationally feasible (polynomial) learnability of that class $[BEHW87a, BEHW87b]$ .An Occam algorithm is a polynomial-time algorithm that produces, for any sequence of examples, a nearly minimum hypoth- esis consistent with the examples.These works, however, depend strongly on the assumption of perfect, noise-less examples.This assumption is generally unrealistic and in many situations of the real world there is always some chance that a noisy example is given to the learning algorithm.In this paper we present a practical extension to Occam algorithms in the Valiant learnability model: Occam algorithms that can tolerate the classification noise, a noise process introduced in [AL88] (clas- sifying the example is subject to independent random mistakes with some small probability), and it is shown that the noise-tolerant Occam algorithm is a powerful algorithmic tool to establish computationally feasibk learning that copes with the classification noise; the existence of a noise-tolerant Occam algorithm for a class of concepts is a sufficient condition for the polynomial learnability of that class in the presence of noise.