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

Institut für Theoretische Informatik

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.

Originalsprache	Englisch
Titel	COCOON 2007: Computing and Combinatorics
Seitenumfang	11
Band	4598 LNCS
Herausgeber (Verlag)	Springer Berlin Heidelberg
Erscheinungsdatum	01.12.2007
Seiten	296-306
ISBN (Print)	978-3-540-73544-1
ISBN (elektronisch)	978-3-540-73545-8
DOIs	https://doi.org/10.1007/978-3-540-73545-8_30
Publikationsstatus	Veröffentlicht - 01.12.2007
Veranstaltung	13th Annual International Computing and Combinatorics Conference - Banff, Kanada Dauer: 16.07.2007 → 19.07.2007 Konferenznummer: 70851

UN SDGs

Dieser Output leistet einen Beitrag zu folgendem(n) Ziel(en) für nachhaltige Entwicklung

Dokumente

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

Weitere Links

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

Robuste Lernverfahren und Datenkomprimierung
Reischuk, R. (Projektleiter*in (PI))
01.01.04 → 31.12.08
Projekt: DFG-Projekte › DFG Einzelförderungen (Sachbeihilfen)

Zitieren

@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 . Bd. 4598 LNCS, Lecture Notes in Computer Science, Bd. 4598 LNCS, Springer Berlin Heidelberg, S. 296-306, 13th Annual International Computing and Combinatorics Conference
, Banff, Alberta, Kanada, 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 . Band 4598 LNCS Springer Berlin Heidelberg, 2007. S. 296-306 (Lecture Notes in Computer Science; Band 4598 LNCS).

Publikation: Kapitel in Büchern/Berichten/Konferenzbänden › Konferenzbeitrag › Begutachtung

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

Dokumente

Weitere Links

Fingerprint

Projekte

Robuste Lernverfahren und Datenkomprimierung

Zitieren