Learning Juntas in the Presence of Noise


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.

TitelTAMC 2006: Theory and Applications of Models of Computation
Band3959 LNCS
Herausgeber (Verlag)Springer Berlin Heidelberg
ISBN (Print)978-3-540-34021-8
ISBN (elektronisch)978-3-540-34022-5
PublikationsstatusVeröffentlicht - 17.07.2006
Veranstaltung3rd International Conference on Theory and Applications of Models of Computation - Beijing, China
Dauer: 15.05.200620.05.2006
Konferenznummer: 67762