Revisiting Example Dependent Cost-Sensitive Learning with Decision Trees

Typical approaches to classification treat class labels as disjoint. For each training example, it is assumed that there is only one class label that correctly describes it, and that all other labels are equally bad. We know however, that good and bad labels are too simplistic in many scenarios, hurting accuracy. In the realm of example dependent cost-sensitive learning, each label is instead a vector represent-ing a data point’s affinity for each of the classes. At test time, our goal is not to minimize the misclassification rate, but to maximize that affinity. We propose a novel exam-ple dependent cost-sensitive impurity measure for decision trees. Our experiments show that this new impurity measure improves test performance while still retaining the fast test times of standard classification trees. We compare our ap-proach to classification trees and other cost-sensitive meth-ods on three computer vision problems, tracking, descriptor matching, and optical flow, and show improvements in all three domains. 1