On-line algorithm to predict nearly as well as the best pruning of a decision tree

Akira Maruoka, Eiji Takimoto

Research output: Chapter in Book/Report/Conference proceedingChapter


We review underlying mechanisms of the multiplicative weight-update prediction algorithms which somehow combine experts' predictions to obtain its own prediction that is almost as good as the best expert's prediction. Looking into the mechanisms we show how such an algorithm with the experts arranged on one layer can be naturally generalized to the one with the experts laid on nodes of trees. Consequently we give an on-line prediction algorithm that, when given a decision tree, produces predictions not much worse than the predictions made by the best pruning of the given decision tree.

Original languageEnglish
Title of host publicationProgress in Discovery Science
PublisherSpringer Verlag
Number of pages11
ISBN (Print)3540433384, 9783540433385
Publication statusPublished - 2002
Externally publishedYes

Publication series

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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On-line algorithm to predict nearly as well as the best pruning of a decision tree'. Together they form a unique fingerprint.

Cite this