Not Logged In

A Fast Way to Produce Optimal Fixed-Depth Decision Trees

Full Text: paper.pdf PDF

Decision trees play an essential role in many classification tasks. In some circumstances, we only want to consider fixed-depth trees. Unfortunately, finding the optimal depth-d decision tree can require time exponential in d. This paper presents a fast way to produce a fixed-depth decision tree that is optimal under the Naive Bayes (NB) assumption. Here, we prove that the optimal depth-d feature essentially depends only on the posterior probability of the class label given the tests previously performed, but not directly on either the identity nor the outcomes of these tests. We can therefore precompute, in a fast pre-processing step, which features to use at the final layer. This results in a speedup of O(n / log n), where n is the number of features. We apply this technique to learning fixed-depth decision trees from standard UCI repository datasets, and find this model improves the computational cost significantly. Surprisingly, this approach still yields relatively high clasfication accuracy, despite the NB assumption.

Citation

A. Farhangfar, R. Greiner, M. Zinkevich. "A Fast Way to Produce Optimal Fixed-Depth Decision Trees". International Symposium on Artificial Intelligence and Mathematics, November 2007.

Keywords: machine learning, reinforcement learning, policy, naive bayes
Category: In Conference

BibTeX

@incollection{Farhangfar+al:ISAIM07,
  author = {Alireza Farhangfar and Russ Greiner and Martin Zinkevich},
  title = {A Fast Way to Produce Optimal Fixed-Depth Decision Trees},
  booktitle = {International Symposium on Artificial Intelligence and
    Mathematics},
  year = 2007,
}

Last Updated: November 23, 2012
Submitted by Russ Greiner

University of Alberta Logo AICML Logo