Home | Publications | CS Home

Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach


Saher Esmeir and Shaul Markovitch. Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach. Journal of Artificial Intelligence Research, 33:1-31 2008.


Abstract

Machine learning techniques are gaining prevalence in the production of a wide range of classifiers for complex real-world applications with nonuniform testing and misclassification costs. The increasing complexity of these applications poses a real challenge to resource management during learning and classification. In this work we introduce ACT (anytime cost-sensitive tree learner), a novel framework for operating in such complex environments. ACT is an anytime algorithm that allows learning time to be increased in return 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 the cost of the subtree under each candidate split and favors the one with a minimal cost. As a stochastic algorithm, 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 ACT to the state-of-the-art cost-sensitive tree learners. The results show that for the majority of domains ACT produces significantly less costly trees. ACT also exhibits good anytime behavior with diminishing returns.


Keywords: Anytime Algorithms, Anytime Learning, Decision Tree Induction, Cost-Sensitive Learning
Secondary Keywords:
Online version:
Bibtex entry:
 @article{Esmeir:2008:AIL,
  Author = {Saher Esmeir and Shaul Markovitch},
  Title = {Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach},
  Year = {2008},
  Journal = {Journal of Artificial Intelligence Research},
  Volume = {33},
  Pages = {1--31},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-JAIR2008.pdf},
  Keywords = {Anytime Algorithms, Anytime Learning, Decision Tree Induction, Cost-Sensitive Learning},
  Secondary-keywords = {Hard Concepts, Lookahead},
  Abstract = {
    Machine learning techniques are gaining prevalence in the
    production of a wide range of classifiers for complex real-world
    applications with nonuniform testing and misclassification costs.
    The increasing complexity of these applications poses a real
    challenge to resource management during learning and
    classification. In this work we introduce ACT (anytime cost-
    sensitive tree learner), a novel framework for operating in such
    complex environments. ACT is an anytime algorithm that allows
    learning time to be increased in return 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 the cost of the subtree under each candidate split
    and favors the one with a minimal cost. As a stochastic algorithm,
    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 ACT to the state-of-the-art
    cost-sensitive tree learners. The results show that for the
    majority of domains ACT produces significantly less costly trees.
    ACT also exhibits good anytime behavior with diminishing returns.
  }

  }