Robust Loss Functions for Training Decision Trees with Noisy Labels

Jonathan Wilton, Nan YeAAAI 2024 · DOI

Introduction

Standard decision tree induction algorithms, such as CART or C4.5, are notoriously sensitive to label noise. By greedily minimizing impurities like Gini or Entropy, these models often overfit by creating deep branches to isolate noisy outliers. This paper addresses this gap by introducing a theoretical framework for distribution-based loss functions that naturally incorporate robustness and trigger "early stopping" during tree construction.

The Distribution Loss Framework and NE Loss

The authors propose a novel class of "conservative" losses. A key insight is that certain loss functions, when used as splitting criteria, inherently stop the growth of a tree if a split does not change the majority class of the resulting child nodes. This provides a mathematical "brake" that prevents the tree from chasing noise into deep, overfitted branches.

To systematically derive such losses, the paper introduces a framework based on Cumulative Distribution Functions (CDFs) of the prediction margin. A standout result is the Negative Exponential (NE) loss: $$\ell(y, \hat{y}) = \min\{1, \exp(-y\hat{y} - \mu)\}$$

Figure 1: The NE loss function (left) is capped at 1, effectively ignoring extreme outliers. The resulting impurity measures (right) vary with the robustness parameter λ, interpolating between standard Gini-like shapes and more robust forms.

As shown in Figure 1, the NE loss is "capped" at a maximum value of 1. This capping ensures that the algorithm ignores extreme outliers—likely noisy labels—that would otherwise distort the tree structure. By adjusting the robustness parameter $\lambda$, the NE impurity can interpolate between robust misclassification impurity and variants of Gini impurity, allowing the model to adapt to different noise levels.

Experimental Evaluation

The proposed Adaptive Negative Exponential (ANE) approach, where $\lambda$ is tuned via validation, was evaluated against standard baselines (Cross-Entropy, MSE) across diverse datasets including MNIST, CIFAR-10, 20News, and tabular data like Covertype.

Figure 6: Impact of the robustness parameter λ on test accuracy and tree complexity. Higher λ (lighter lines) leads to smaller trees (fewer leaf nodes) that maintain better accuracy under high label noise, demonstrating the "early stopping" effect.

The results in Figure 6 highlight the core mechanism: as label noise increases, robust $\lambda$ values (lighter lines) prevent the explosion of tree size. While standard trees grow massive to fit noise, robust trees remain compact (fewer leaf nodes) and achieve significantly higher test accuracy. In high-noise scenarios, such as 40% noise on MNIST, ANE consistently outperformed traditional methods by avoiding the overfitting trap.

Conclusion and Future Work

By bridging the gap between global loss minimization and greedy tree induction, this work provides a principled way to build noise-robust decision trees. The NE loss offers a tunable mechanism for early stopping, ensuring that model capacity is used to capture signal rather than noise. While the current approach relies on greedy local searches, future work could explore applying these robust impurities to gradient-boosted ensembles like XGBoost or CatBoost to further enhance performance in complex noise environments.

Summary updated

BibTeX
@inproceedings{wilton2024robust,
  author = {Jonathan Wilton and Nan Ye},
  title = {{Robust Loss Functions for Training Decision Trees with Noisy Labels}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i14.29516},
}
Figure