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)\}$$
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.
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