Predicting nearly as well as the best pruning of a planar decision graph

Eiji Takimoto; Manfred K. Warmuth

doi:10.1007/3-540-46769-6_28

Predicting nearly as well as the best pruning of a planar decision graph

Eiji Takimoto, Manfred K. Warmuth

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

We design efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees, we implicitly maintain one weight for each of the prunings (exponentially many). The method works for a large class of algorithms that update its weights multiplicatively. It can also be used to design algorithms that predict nearly as well as the best convex combination of prunings.

Original language	English
Title of host publication	Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings
Editors	Osamu Watanabe, Takashi Yokomori
Publisher	Springer Verlag
Pages	335-346
Number of pages	12
ISBN (Print)	3540667482, 9783540667483
DOIs	https://doi.org/10.1007/3-540-46769-6_28
Publication status	Published - 1999
Externally published	Yes
Event	10th International Conference on Algorithmic Learning Theory, ALT 1999 - Tokyo, Japan Duration: Dec 6 1999 → Dec 8 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1720
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th International Conference on Algorithmic Learning Theory, ALT 1999
Country/Territory	Japan
City	Tokyo
Period	12/6/99 → 12/8/99

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-46769-6_28

Cite this

Takimoto, E., & Warmuth, M. K. (1999). Predicting nearly as well as the best pruning of a planar decision graph. In O. Watanabe, & T. Yokomori (Eds.), Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings (pp. 335-346). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1720). Springer Verlag. https://doi.org/10.1007/3-540-46769-6_28

Predicting nearly as well as the best pruning of a planar decision graph. / Takimoto, Eiji; Warmuth, Manfred K.
Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings. ed. / Osamu Watanabe; Takashi Yokomori. Springer Verlag, 1999. p. 335-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1720).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Takimoto, E & Warmuth, MK 1999, Predicting nearly as well as the best pruning of a planar decision graph. in O Watanabe & T Yokomori (eds), Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1720, Springer Verlag, pp. 335-346, 10th International Conference on Algorithmic Learning Theory, ALT 1999, Tokyo, Japan, 12/6/99. https://doi.org/10.1007/3-540-46769-6_28

Takimoto E, Warmuth MK. Predicting nearly as well as the best pruning of a planar decision graph. In Watanabe O, Yokomori T, editors, Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings. Springer Verlag. 1999. p. 335-346. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-46769-6_28

Takimoto, Eiji ; Warmuth, Manfred K. / Predicting nearly as well as the best pruning of a planar decision graph. Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings. editor / Osamu Watanabe ; Takashi Yokomori. Springer Verlag, 1999. pp. 335-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c4adc25af6344135a20d4aaf7f800b16,

title = "Predicting nearly as well as the best pruning of a planar decision graph",

abstract = "We design efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees, we implicitly maintain one weight for each of the prunings (exponentially many). The method works for a large class of algorithms that update its weights multiplicatively. It can also be used to design algorithms that predict nearly as well as the best convex combination of prunings.",

author = "Eiji Takimoto and Warmuth, {Manfred K.}",

note = "Funding Information: ∗Corresponding author. Tel.: +81-22-217-7149; fax: +81-22-263-9414. E-mail address: t2@ecei.tohoku.ac.jp (E. Takimoto). 1This work was done while the author visited University of California, Santa Cruz. 2Supported by NSF grant CCR 9821087. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 10th International Conference on Algorithmic Learning Theory, ALT 1999 ; Conference date: 06-12-1999 Through 08-12-1999",

year = "1999",

doi = "10.1007/3-540-46769-6_28",

language = "English",

isbn = "3540667482",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "335--346",

editor = "Osamu Watanabe and Takashi Yokomori",

booktitle = "Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Predicting nearly as well as the best pruning of a planar decision graph

AU - Takimoto, Eiji

AU - Warmuth, Manfred K.

N1 - Funding Information: ∗Corresponding author. Tel.: +81-22-217-7149; fax: +81-22-263-9414. E-mail address: t2@ecei.tohoku.ac.jp (E. Takimoto). 1This work was done while the author visited University of California, Santa Cruz. 2Supported by NSF grant CCR 9821087. Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - We design efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees, we implicitly maintain one weight for each of the prunings (exponentially many). The method works for a large class of algorithms that update its weights multiplicatively. It can also be used to design algorithms that predict nearly as well as the best convex combination of prunings.

AB - We design efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees, we implicitly maintain one weight for each of the prunings (exponentially many). The method works for a large class of algorithms that update its weights multiplicatively. It can also be used to design algorithms that predict nearly as well as the best convex combination of prunings.

UR - http://www.scopus.com/inward/record.url?scp=84937394882&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937394882&partnerID=8YFLogxK

U2 - 10.1007/3-540-46769-6_28

DO - 10.1007/3-540-46769-6_28

M3 - Conference contribution

AN - SCOPUS:84937394882

SN - 3540667482

SN - 9783540667483

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 335

EP - 346

BT - Algorithmic Learning Theory - 10th International Conference, ALT 1999, Proceedings

A2 - Watanabe, Osamu

A2 - Yokomori, Takashi

PB - Springer Verlag

T2 - 10th International Conference on Algorithmic Learning Theory, ALT 1999

Y2 - 6 December 1999 through 8 December 1999

ER -

Predicting nearly as well as the best pruning of a planar decision graph

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this