Anytime Learning of Cost-sensitive Trees
Motivation
Brain tumor diagnosys
Many false negatives Accurate but costly
Changes in speech

N I P S ' 0 7 Spotlight ID Number T35 Saher Esmeir and Shaul Markovitch Computer Science Dept. Technion-IIT {esaher|shaulm}@cs.technion.ac.il

The ACT Algorithm
Average % Standard Cost

Results
60 50 40 30 20 10 100 C4.5 EG2 DTMC ICET ACT 1000 Misclassification Cost 10000

MRI

 Build a tree top-down  Sample subtrees under splits  For each subtree T  estimate test costs
train set

-

+

-

+

 estimate error costs
Focal Signs Changes in speech

1  TestCost (e) |E | eE

error cost

Average Cost

MRI

 Prefer a split with minimal total costs a b + 2.2$

1  E x pect ed E rror(l ) · mc |E | l Leaves(T )
100 90 80 70 60 50 40 30 20 0 1

EG2 DTMC ICET ACT

MRI

$ 7.7

4.5$
+
Cost-sensitive tree

4.1$

2

3 Time [sec]

4

5

6

-

cost(a)=2.2$

cost(b)=4.1$