Home | Publications | CS Home

Anytime Induction of Cost-sensitive Trees


Saher Esmeir and Shaul Markovitch. Anytime Induction of Cost-sensitive Trees. In Proceedings of The 21st Conference on Neural Information Processing Systems (NIPS-2007), Vancouver, Canada, 2007.


Abstract

Machine learning techniques are increasingly being used to produce a wide-range of classifiers for complex real-world applications that involve nonuniform testing costs and misclassification costs. As the complexity of these applications grows, the management of resources during the learning and classification processes becomes a challenging task. In this work we introduce ACT (Anytime Cost-sensitive Trees), a novel framework for operating in such environments. ACT is an anytime algorithm that allows trading computation time for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques ACT approximates for each candidate split the cost of the subtree under it and favors the one with a minimal cost. Due to its stochastic nature ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare the performance of ACT to that of the state of the art cost-sensitive tree learners. The results show that for most domains ACT produces trees of significantly lower costs. ACT is also shown to exhibit good anytime behavior with diminishing returns.


Keywords: Decision Tree Induction, Anytime Algorithms, Anytime Learning, Cost-Sensitive Learning
Secondary Keywords:
Online version:
Bibtex entry:
 @inproceedings{Esmeir:2007:AIC,
  Author = {Saher Esmeir and Shaul Markovitch},
  Title = {Anytime Induction of Cost-sensitive Trees},
  Year = {2007},
  Booktitle = {Proceedings of The 21st Conference on Neural Information Processing Systems (NIPS-2007)},
  Pages = {},
  Address = {Vancouver, Canada},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-NIPS2007.pdf},
  Keywords = {Decision Tree Induction, Anytime Algorithms, Anytime Learning, Cost-Sensitive Learning},
  Secondary-keywords = {Lookahead},
  Abstract = {
    Machine learning techniques are increasingly being used to produce
    a wide-range of classifiers for complex real-world applications
    that involve nonuniform testing costs and misclassification costs.
    As the complexity of these applications grows, the management of
    resources during the learning and classification processes becomes
    a challenging task. In this work we introduce ACT (Anytime Cost-
    sensitive Trees), a novel framework for operating in such
    environments. ACT is an anytime algorithm that allows trading
    computation time for lower classification costs. It builds a tree
    top-down and exploits additional time resources to obtain better
    estimations for the utility of the different candidate splits.
    Using sampling techniques ACT approximates for each candidate
    split the cost of the subtree under it and favors the one with a
    minimal cost. Due to its stochastic nature ACT is expected to be
    able to escape local minima, into which greedy methods may be
    trapped. Experiments with a variety of datasets were conducted to
    compare the performance of ACT to that of the state of the art
    cost-sensitive tree learners. The results show that for most
    domains ACT produces trees of significantly lower costs. ACT is
    also shown to exhibit good anytime behavior with diminishing
    returns.
  }

  }