When Does Greedy Learning of Relevant Attributes Succeed? A Fourier-Based Characterization

Abstract

We introduce a new notion called Fourier-accessibility that allows us to precisely characterize the class of Boolean functions for which a standard greedy learning algorithm successfully learns all relevant attributes. If the target function is Fourier-accessible, then the success probability of the greedy algorithm can be made arbitrarily close to one. On the other hand, if the target function is not Fourier-accessible, then the error probability tends to one. Finally, we extend these results to the situation where the input data are corrupted by random attribute and classification noise and prove that greedy learning is quite robust against such errors.

OriginalspracheEnglisch
TitelCOCOON 2007: Computing and Combinatorics
Seitenumfang11
Band4598 LNCS
Herausgeber (Verlag)Springer Berlin Heidelberg
Erscheinungsdatum01.12.2007
Seiten296-306
ISBN (Print)978-3-540-73544-1
ISBN (elektronisch)978-3-540-73545-8
DOIs
PublikationsstatusVeröffentlicht - 01.12.2007
Veranstaltung13th Annual International Computing and Combinatorics Conference
- Banff, Kanada
Dauer: 16.07.200719.07.2007
Konferenznummer: 70851

Fingerprint

Untersuchen Sie die Forschungsthemen von „When Does Greedy Learning of Relevant Attributes Succeed? A Fourier-Based Characterization“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren