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.
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:
- Tracking: Selecting optimal motion models for image features.
- Descriptor Matching: Choosing the best local image descriptor from 10 candidates.
- 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).
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