Home | Publications | CS Home

Anytime Learning of Anycost Classifiers

---

Saher Esmeir and Shaul Markovitch. Anytime Learning of Anycost Classifiers. Machine Learning, 82:445-473 2011.

---

Abstract

The classification of new cases using a predictive model incurs two types of costs--testing costs and misclassification costs. Recent research efforts have resulted in several novel algorithms that attempt to produce learners that simultaneously minimize both types. In many real life scenarios, however, we cannot afford to conduct all the tests required by the predictive model. For example, a medical center might have a fixed predetermined budget for diagnosing each patient. For cost bounded classification, decision trees are considered attractive as they measure only the tests along a single path. In this work we present an anytime framework for producing decision-tree based classifiers that can make accurate decisions within a strict bound on testing costs. These bounds can be known to the learner, known to the classifier but not to the learner, or not predetermined. Extensive experiments with a variety of datasets show that our proposed framework produces trees with lower misclassification costs along a wide range of testing cost bounds.

---

Keywords: Anytime Algorithms, Anytime Learning, Decision Tree Induction, Cost-Sensitive Learning

---

Secondary Keywords:

---

Online version:

---

Bibtex entry:

 @article{Esmeir:2011:ALA,
  Author = {Saher Esmeir and Shaul Markovitch},
  Title = {Anytime Learning of Anycost Classifiers},
  Year = {2011},
  Journal = {Machine Learning},
  Volume = {82},
  Number = {3},
  Month = {},
  Pages = {445--473},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-MLJ2011.pdf},
  Keywords = {Anytime Algorithms, Anytime Learning, Decision Tree Induction, Cost-Sensitive Learning},
  Abstract = {
    The classification of new cases using a predictive model incurs
    two types of costs--testing costs and misclassification costs.
    Recent research efforts have resulted in several novel algorithms
    that attempt to produce learners that simultaneously minimize both
    types. In many real life scenarios, however, we cannot afford to
    conduct all the tests required by the predictive model. For
    example, a medical center might have a fixed predetermined budget
    for diagnosing each patient. For cost bounded classification,
    decision trees are considered attractive as they measure only the
    tests along a single path. In this work we present an anytime
    framework for producing decision-tree based classifiers that can
    make accurate decisions within a strict bound on testing costs.
    These bounds can be known to the learner, known to the classifier
    but not to the learner, or not predetermined. Extensive
    experiments with a variety of datasets show that our proposed
    framework produces trees with lower misclassification costs along
    a wide range of testing cost bounds.
  }

  }