Mach Learn (2011) 82: 445–473
DOI 10.1007/s10994-010-5228-1
Anytime learning of anycost classif i ers
Saher Esmeir · Shaul Markovitch
Received: 4 July 2009 / Revised: 24 October 2010 / Accepted: 30 October 2010 /
Published online: 25 November 2010
(c) The Author(s) 2010
Abstract The classif i cation of new cases using a predictive model incurs two types of
costs—testing costs and misclassif i cation 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 f i xed predetermined
budget for diagnosing each patient. For cost bounded classif i cation, decision trees are con-
sidered attractive as they measure only the tests along a single path. In this work we present
an anytime framework for producing decision-tree based classif i ers that can make accurate
decisions within a strict bound on testing costs. These bounds can be known to the learner,
known to the classif i er but not to the learner, or not predetermined. Extensive experiments
with a variety ofdatasets show that our proposed framework produces trees with lower mis-
classif i cation costs along a wide range of testing cost bounds.
Keywords Decision trees · Cost-sensitive learning · Resource-bounded reasoning ·
Anytime algorithms
1 Introduction
Assume that a hardware manufacturer has decided to use a machine-learning based tool
for assuring the quality of produced chips (e.g., Wang 2010). In realtime, each chip in the
pipeline is scanned and several features can be extracted from the image. The features vary
in their computation time. The manufacturer trains the component using thousands of chips
whose validity is known. Because the training is done off l ine, the manufacturer can provide
Editor: Johannes Fürnkranz.
S. Esmeir (  ) · S. Markovitch
Computer Science Department, Technion—Israel Institute of Technology, Haifa, Israel
e-mail: esaher@cs.technion.ac.il
S. Markovitch
e-mail: shaulm@cs.technion.ac.il