Lookahead-based Algorithms for Anytime Induction of Decision Trees

Saher Esmeir and Shaul Markovitch. Lookahead-based Algorithms for Anytime Induction of Decision Trees. In Proceedings of The Twenty-First International Conference on Machine Learning, 257-264 Banff, Alberta, Canada, 2004.Morgan Kaufmann

Abstract

The majority of the existing algorithms for learning decision trees are greedy - a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Furthermore, these algorithms require a fixed amount of time and are not able to improve the learned tree if any additional time is available. To overcome this problem, we present a family of lookahead based algorithms for anytime induction of decision trees. Anytime algorithms allow a tradeoff between the solution quality and the consumed time resources. Two methods for looking ahead are introduced. The first one is depth-k lookahead, where k increases as the allocated time permits. The second method uses a novel strategy for evaluating candidate splits; a stochastic version of ID3 is invoked to estimate the size of the tree in which each split results, and the candidate that minimizes the expected size is preferred. Our algorithms were applied both on synthetic and real-world datasets. The experimental results indicate that for several hard concepts, our proposed approach has a good anytime behavior and yields significantly better decision trees when more time is available.

Keywords: Anytime Learning, Resource-Bounded Reasoning

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Esmeir:2004:LBA,
  Author = {Saher Esmeir and Shaul Markovitch},
  Title = {Lookahead-based Algorithms for Anytime Induction of Decision Trees},
  Year = {2004},
  Booktitle = {Proceedings of The Twenty-First International Conference on Machine Learning},
  Pages = {257--264},
  Address = {Banff, Alberta, Canada},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-icml2004.pdf},
  Keywords = {Anytime Learning, Resource-Bounded Reasoning},
  Secondary-keywords = {Anytime Induction, Decision Trees, Lookahead, Budgeted Learning, C4.5},
  Abstract = {
    The majority of the existing algorithms for learning decision
    trees are greedy - a tree is induced top-down, making locally
    optimal decisions at each node. In most cases, however, the
    constructed tree is not globally optimal. Furthermore, these
    algorithms require a fixed amount of time and are not able to
    improve the learned tree if any additional time is available. To
    overcome this problem, we present a family of lookahead based
    algorithms for anytime induction of decision trees. Anytime
    algorithms allow a tradeoff between the solution quality and the
    consumed time resources. Two methods for looking ahead are
    introduced. The first one is depth-k lookahead, where k increases
    as the allocated time permits. The second method uses a novel
    strategy for evaluating candidate splits; a stochastic version of
    ID3 is invoked to estimate the size of the tree in which each
    split results, and the candidate that minimizes the expected size
    is preferred. Our algorithms were applied both on synthetic and
    real-world datasets. The experimental results indicate that for
    several hard concepts, our proposed approach has a good anytime
    behavior and yields significantly better decision trees when more
    time is available.
  }

  }