Learning Juntas in the Presence of Noise

Jan Arpe, Rüdiger Reischuk

Abstract

The combination of two major challenges in algorithmic learning is investigated: dealing with huge amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that only depend on a small fraction of their variables - so-called juntas - can be learned efficiently from uniformly distributed examples that are corrupted by random attribute and classification noise. We present solutions to cope with the manifold problems that inhibit a straightforward generalization of the noise-free case. Additionally, we extend our methods to non-uniformly distributed examples and derive new results for monotone juntas in this setting. We assume that the attribute noise is generated by a product distribution. Otherwise fault-tolerant learning is in general impossible which follows from the construction of a noise distribution P and a concept class C such that it is impossible to learn C under P-noise.

Original languageEnglish
Title of host publicationTAMC 2006: Theory and Applications of Models of Computation
Number of pages12
Volume3959 LNCS
PublisherSpringer Berlin Heidelberg
Publication date17.07.2006
Pages387-398
ISBN (Print)978-3-540-34021-8
ISBN (Electronic)978-3-540-34022-5
DOIs
Publication statusPublished - 17.07.2006
Event3rd International Conference on Theory and Applications of Models of Computation - Beijing, China
Duration: 15.05.200620.05.2006
Conference number: 67762

Cite this