Revisiting Example Dependent Cost-Sensitive Learning with Decision Trees

Oisin Mac Aodha, Gabriel J. BrostowICCV 2013 · OpenReview

Abstract

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 representing 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 example 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 approach to classification trees and other cost-sensitive methods on three computer vision problems, tracking, descriptor matching, and optical flow, and show improvements in all three domains.

Introduction

In many machine learning problems, classification is treated as a multiple-choice test where only one answer is correct and all others are equally incorrect. However, in real-world computer vision applications, labels are rarely binary. For instance, when selecting an algorithm for object tracking, several options might perform reasonably well, while others might fail catastrophically.

Standard classifiers assume classes are disjoint. This paper addresses Example-Dependent Cost-Sensitive (ECS) learning, where the cost of misclassification varies for every data point. The primary challenge is that traditional decision tree split criteria, such as Gini Impurity or Entropy, are not designed to handle vectors of continuous performance scores for every training example.

Pairwise Cost-Sensitive Random Forests (PWCSRF)

The core contribution of this work is a new node impurity measure, $I_{cs}$, designed for Random Forests. While a simple approach like GCSRF weights class probabilities by task scores, it often fails to account for the "gap" between the best and second-best options.

The proposed PWCSRF focuses on the pairwise differences between task scores. A split is only favored if there is a significant difference in the suitability of different "specialists" (classes) for the given data points. If all algorithms perform similarly on a subset of data, the impurity remains low, preventing unnecessary splits.

Comparison of the proposed cost-sensitive impurity measure $I_{cs}$ against standard Gini impurity $I_{gini}$ and other variants across different node configurations.

The impurity measure $I_{cs}$ is calculated based on "pairwise specialist empirical frequency," which uses squared truncated positive differences between scores. This ensures the tree minimizes the "regret" associated with sub-optimal choices.

Experimental Evaluation

The authors evaluated PWCSRF on three distinct computer vision tasks:

  1. Tracking: Selecting optimal motion models for image features.
  2. Descriptor Matching: Choosing the best local image descriptor from 10 candidates.
  3. Optical Flow: Selecting the best flow algorithm per pixel across Middlebury and MPI Sintel benchmarks.

Performance and Efficiency

In the optical flow task, PWCSRF achieved a 10% improvement in End Point Error (EPE) over standard classification forests. In descriptor matching, it achieved a precision of 0.5878, outperforming standard forests (0.5675). While a complex SVM-based regressor (OSSVR) was slightly more accurate (0.5922), PWCSRF was nearly 800x faster at test time (0.06ms vs 47.61ms).

Decision boundary generated by the proposed PWCSRF method, demonstrating a smooth transition between classes that avoids overfitting to noisy performance differences.

Key Insights

  • Continuous Scores: Retaining continuous task scores rather than quantizing them into "best" vs "rest" allows the model to distinguish between "good enough" and "critical" choices.
  • Robust Boundaries: By ignoring noisy differences between similar-performing classes, PWCSRF often produces simpler, more robust decision boundaries that are less prone to overfitting than standard classification trees.
  • Test-Time Speed: Despite more complex training logic, the test-time performance remains identical to standard Random Forests, making it ideal for real-time vision applications.

Conclusion

PWCSRF offers a powerful framework for algorithm selection in computer vision. By focusing on the relative performance gap between classes during training, it achieves higher accuracy and maintains the efficiency required for practical deployment. Future work may explore incorporating spatial consistency in pixel-wise tasks to further refine results.

Summary updated

Abstract

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 representing 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 example 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 approach to classification trees and other cost-sensitive methods on three computer vision problems, tracking, descriptor matching, and optical flow, and show improvements in all three domains.
BibTeX
@inproceedings{aodha2013revisiting,
  author = {Oisin Mac Aodha and Gabriel J. Brostow},
  title = {{Revisiting Example Dependent Cost-Sensitive Learning with Decision Trees}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=ByVeEWGObH},
}
Figure