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

Jan Arpe; Rüdiger Reischuk

doi:10.1007/978-3-540-73545-8_30

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

Jan Arpe, Rüdiger Reischuk

Institute of Theoretical Computer Science

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.

Original language	English
Title of host publication	COCOON 2007: Computing and Combinatorics
Number of pages	11
Volume	4598 LNCS
Publisher	Springer Berlin Heidelberg
Publication date	01.12.2007
Pages	296-306
ISBN (Print)	978-3-540-73544-1
ISBN (Electronic)	978-3-540-73545-8
DOIs	https://doi.org/10.1007/978-3-540-73545-8_30
Publication status	Published - 01.12.2007
Event	13th Annual International Computing and Combinatorics Conference - Banff, Canada Duration: 16.07.2007 → 19.07.2007 Conference number: 70851

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-540-73545-8_30

Cite this

@inproceedings{2ff312c212d54276a438ec6a3472407d,

title = "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.",

author = "Jan Arpe and R{\"u}diger Reischuk",

year = "2007",

month = dec,

day = "1",

doi = "10.1007/978-3-540-73545-8_30",

language = "English",

isbn = "978-3-540-73544-1",

volume = "4598 LNCS",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "296--306",

booktitle = "COCOON 2007: Computing and Combinatorics",

note = "13th Annual International Computing and Combinatorics Conference <br/>, COCOON 2007 ; Conference date: 16-07-2007 Through 19-07-2007",

}

Arpe, J & Reischuk, R 2007, When Does Greedy Learning of Relevant Attributes Succeed? A Fourier-Based Characterization. in COCOON 2007: Computing and Combinatorics . vol. 4598 LNCS, Lecture Notes in Computer Science, vol. 4598 LNCS, Springer Berlin Heidelberg, pp. 296-306, 13th Annual International Computing and Combinatorics Conference
, Banff, Alberta, Canada, 16.07.07. https://doi.org/10.1007/978-3-540-73545-8_30

When Does Greedy Learning of Relevant Attributes Succeed? A Fourier-Based Characterization. / Arpe, Jan; Reischuk, Rüdiger.
COCOON 2007: Computing and Combinatorics . Vol. 4598 LNCS Springer Berlin Heidelberg, 2007. p. 296-306 (Lecture Notes in Computer Science; Vol. 4598 LNCS).

Research output: Chapters in Books/Reports/Conference Proceedings › Conference contribution › peer-review

TY - GEN

T1 - When Does Greedy Learning of Relevant Attributes Succeed?

T2 - 13th Annual International Computing and Combinatorics Conference <br/>

AU - Arpe, Jan

AU - Reischuk, Rüdiger

N1 - Conference code: 70851

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-37849001853&origin=inward&txGid=56b2ec9e13db2ab1d5b6e6cc2b50637e

U2 - 10.1007/978-3-540-73545-8_30

DO - 10.1007/978-3-540-73545-8_30

M3 - Conference contribution

SN - 978-3-540-73544-1

VL - 4598 LNCS

T3 - Lecture Notes in Computer Science

SP - 296

EP - 306

BT - COCOON 2007: Computing and Combinatorics

PB - Springer Berlin Heidelberg

Y2 - 16 July 2007 through 19 July 2007

ER -

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

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Robust learning methods and data compression

Cite this

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

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Projects

Robust learning methods and data compression

Cite this