Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-065 | 24th May 2006 00:00

When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---


Authors: Jan Arpe, RĂ¼diger Reischuk
Publication: 28th May 2006 11:54
Downloads: 1178


Detecting the relevant attributes of an unknown target concept
is an important and well studied problem in algorithmic learning.
Simple greedy strategies have been proposed that seem to perform reasonably
well in practice if a sufficiently large random subset of examples of the target
concept is provided.

Introducing a new notion called Fourier-accessibility
allows us to characterize the class of Boolean functions precisely
for which a standard greedy learning algorithm successfully learns all relevant attributes.

Technically, this is achieved by deriving new relations between the learnability
of a function and its Fourier spectrum. We prove that if the target concept 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 concept is not Fourier-accessible,
then the error probability tends to one.

ISSN 1433-8092 | Imprint