Interruptible Anytime Algorithms for Iterative Improvement of Decision Trees
Saher Esmeir and Shaul Markovitch. Interruptible Anytime Algorithms for Iterative Improvement of Decision Trees. In Proceedings of the 1st international workshop on Utility-based data mining, 78-85 Chicago, Illinois, 2005.
Abstract
Finding a minimal decision tree consistent with the examples is an NP-complete problem. Therefore, most of the existing algorithms for decision tree induction use a greedy approach based on local heuristics. These algorithms usually require a fixed small amount of time and result in trees that are not globally optimal. Recently, the LSID3 contract anytime algorithm was introduced to allow using extra resources for building better decision trees. A contract anytime algorithm needs to get its resource allocation a priori. In many cases, however, the time allocation is not known in advance, disallowing the use of contract algorithms. To overcome this problem, in this work we present two interruptible anytime algorithms for inducing decision trees. Interruptible anytime algorithms do not require their resource allocation in advance and thus must be ready to be interrupted and return a valid solution at any moment. The first interruptible algorithm we propose is based on a general technique for converting a contract algorithm to an interruptible one by sequencing. The second is an iterative improvement algorithm that repeatedly selects a subtree whose reconstruction is estimated to yield the highest marginal utility and rebuilds it with higher resource allocation. Empirical evaluation shows a good anytime behavior for both algorithms. The iterative improvement algorithm shows smoother performance profiles which allow more refined control.
Keywords: Anytime Learning, Resource-Bounded Reasoning
Secondary Keywords:
Online version:
Bibtex entry:
@inproceedings{Esmeir:2005:IAA,
Author = {Saher Esmeir and Shaul Markovitch},
Title = {Interruptible Anytime Algorithms for Iterative Improvement of Decision Trees},
Year = {2005},
Booktitle = {Proceedings of the 1st international workshop on Utility-based data mining},
Pages = {78--85},
Address = {Chicago, Illinois},
Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-2005-KDD.pdf},
Keywords = {Anytime Learning, Resource-Bounded Reasoning},
Secondary-keywords = {Anytime Induction, Decision Trees, Lookahead, Budgeted Learning, C4.5},
Abstract = {
Finding a minimal decision tree consistent with the examples is an
NP-complete problem. Therefore, most of the existing algorithms
for decision tree induction use a greedy approach based on local
heuristics. These algorithms usually require a fixed small amount
of time and result in trees that are not globally optimal.
Recently, the LSID3 contract anytime algorithm was introduced to
allow using extra resources for building better decision trees. A
contract anytime algorithm needs to get its resource allocation a
priori. In many cases, however, the time allocation is not known
in advance, disallowing the use of contract algorithms. To
overcome this problem, in this work we present two interruptible
anytime algorithms for inducing decision trees. Interruptible
anytime algorithms do not require their resource allocation in
advance and thus must be ready to be interrupted and return a
valid solution at any moment. The first interruptible algorithm we
propose is based on a general technique for converting a contract
algorithm to an interruptible one by sequencing. The second is an
iterative improvement algorithm that repeatedly selects a subtree
whose reconstruction is estimated to yield the highest marginal
utility and rebuilds it with higher resource allocation. Empirical
evaluation shows a good anytime behavior for both algorithms. The
iterative improvement algorithm shows smoother performance
profiles which allow more refined control.
}
}