Anytime Induction of Decision Trees: an Iterative Improvement Approach

Saher Esmeir and Shaul Markovitch. Anytime Induction of Decision Trees: an Iterative Improvement Approach. In Proceedings of the Twenty-First National Conference on Artificial Intelligence, 348-355 Boston, MA, 2006.

Abstract

Most existing decision tree inducers are very fast due to their greedy approach. In many real-life applications, however, we are willing to allocate more time to get better decision trees. Our recently introduced LSID3 contract anytime algorithm allows computation speed to be traded for better tree quality. As a contract algorithm, LSID3 must be allocated its resources a priori, which is not always possible. In this work, we present IIDT, a general framework for interruptible induction of decision trees that need not be allocated resources a priori. The core of our proposed framework is an iterative improvement algorithm that repeatedly selects a subtree whose reconstruction is expected to yield the highest marginal utility. The algorithm then rebuilds the subtree with a higher allocation of resources. IIDT can also be configured to receive training examples as they become available, and is thus appropriate for incremental learning tasks. Empirical evaluation with several hard concepts shows that IIDT exhibits good anytime behavior and significantly outperforms greedy inducers when more time is available. A comparison of IIDT to several modern decision tree learners showed it to be superior.

Keywords: Resource-Bounded Reasoning, Anytime Learning

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Esmeir:2006:AID,
  Author = {Saher Esmeir and Shaul Markovitch},
  Title = {Anytime Induction of Decision Trees: an Iterative Improvement Approach},
  Year = {2006},
  Booktitle = {Proceedings of the Twenty-First National Conference on Artificial Intelligence},
  Pages = {348--355},
  Address = {Boston, MA},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-aaai2006-AID.pdf},
  Keywords = {Resource-Bounded Reasoning, Anytime Learning},
  Secondary-keywords = {Decision Trees},
  Abstract = {
    Most existing decision tree inducers are very fast due to their
    greedy approach. In many real-life applications, however, we are
    willing to allocate more time to get better decision trees. Our
    recently introduced LSID3 contract anytime algorithm allows
    computation speed to be traded for better tree quality. As a
    contract algorithm, LSID3 must be allocated its resources a
    priori, which is not always possible. In this work, we present
    IIDT, a general framework for interruptible induction of decision
    trees that need not be allocated resources a priori. The core of
    our proposed framework is an iterative improvement algorithm that
    repeatedly selects a subtree whose reconstruction is expected to
    yield the highest marginal utility. The algorithm then rebuilds
    the subtree with a higher allocation of resources. IIDT can also
    be configured to receive training examples as they become
    available, and is thus appropriate for incremental learning tasks.
    Empirical evaluation with several hard concepts shows that IIDT
    exhibits good anytime behavior and significantly outperforms
    greedy inducers when more time is available. A comparison of IIDT
    to several modern decision tree learners showed it to be superior.
  }

  }