TL;DR
This paper introduces ITBoost, a novel gradient boosting method that tackles the problem of noisy labels by evaluating sample "trustworthiness" based on the historical pattern of their prediction errors, rather than just the magnitude of the current error. This information-theoretic approach allows ITBoost to effectively down-weight noisy samples while still prioritizing genuinely hard-to-learn examples, leading to improved robustness and performance in noisy environments.
What Problem Does This Paper Address?
Gradient Boosting Decision Trees (GBDTs) are powerful tools for tabular data, but their performance significantly degrades when training data contains noisy labels. This is because GBDTs, by design, focus on samples with large errors (gradients). While this helps them learn difficult cases, it also makes them susceptible to being misled by mislabeled samples, which also produce large gradients. Standard GBDTs struggle to distinguish between truly challenging examples and erroneous ones, leading to fragmented decision boundaries and poor generalization. Existing methods often rely on robust loss functions or sample selection, but they still implicitly assume that gradient magnitude is the primary indicator of a sample's importance, failing to address the core issue of distinguishing noise from genuine difficulty.
Methods
The core innovation of ITBoost lies in its "information-theoretic trust" framework. Instead of solely relying on the current gradient magnitude, ITBoost analyzes the history of a sample's residuals (prediction errors) across boosting iterations.
Here's how it works:
- Residual History: For each sample, a time series of its binarized residuals (sign of the error) is maintained. Binarization discards the magnitude to focus on the direction of the error over time.
- Algorithmic Complexity: The Lempel-Ziv (LZ) complexity is used to measure the randomness or compressibility of these residual history sequences.
- Hard but Clean Samples: These tend to exhibit structured, compressible residual patterns (e.g., oscillations near the boundary, stable underestimation). They have low LZ complexity.
- Noisy Samples: Mislabeled samples, due to their conflict with the underlying data distribution, tend to produce erratic, unpredictable residual sequences. These have high LZ complexity.
- Trust Score: A "trust score" is computed for each sample, which is a combination of its current gradient magnitude and a "trust term." This trust term is an exponential penalty based on the normalized LZ complexity of its residual history. Samples with high complexity (noisy) receive a low trust score, and vice-versa.
- Weighted Learning: The weak learners in ITBoost are trained using these trust scores as weights. This effectively down-weights samples identified as untrustworthy (likely noisy) and up-weights reliable, informative samples.
Theoretically, the authors derive a tighter generalization error bound for ITBoost under label noise, demonstrating its robustness.
Datasets
The paper evaluates ITBoost on five publicly available datasets from the OpenML repository:
- Madelon
- Jasmine
- Bioresponse
- Creditcard
- OVA_Uterus
No new benchmarks were introduced.
Key Insights and Ideas
- History Matters More Than Magnitude: The most crucial insight is that the pattern of errors over time is a more reliable indicator of a sample's trustworthiness than the magnitude of a single error. Noisy samples exhibit chaotic error histories, while hard but clean samples show more structured patterns.
- Information Theory as a Noise Detector: Leveraging algorithmic complexity (specifically LZ complexity) provides a principled way to quantify the "randomness" of residual trajectories, effectively acting as a noise detector.
- Dynamic Trust Mechanism: The per-iteration normalization of LZ complexity allows ITBoost to adaptively penalize noisy samples, especially in the presence of outliers, while preserving the influence of genuine hard examples.
- Robustness Without Sacrificing Performance: ITBoost aims to achieve robustness against label noise without significantly compromising performance on clean data, a common trade-off with many robust methods.
Key Results
- Superior Robustness: ITBoost consistently outperformed leading boosting algorithms (GBDT, XGBoost, LightGBM, CatBoost, NGBoost) and a Transformer-based model (TabPFN) across various noise levels and types (symmetric, asymmetric, feature noise) on the Jasmine dataset.
- High Performance on Clean Data: ITBoost achieved the best or near-best performance across most datasets and metrics (Accuracy, F1-Score, AUC, Log Loss) even on clean data, demonstrating it doesn't sacrifice performance for robustness. For example, on the Madelon dataset, ITBoost achieved 92.04% accuracy, outperforming the best GBDT baseline (CAT at 84.38%) and TabPFN (90.50%).
- Theoretical Guarantees: The paper provides theoretical justification, showing ITBoost achieves a tighter generalization error bound under label noise.
- Ablation Study: Residual binarization was found to be crucial for ITBoost's robustness against label noise, outperforming a quantized variant that retained magnitude information.
- Visual Validation: A case study visualizing sample weights showed that noisy samples' weights decreased significantly over iterations, confirming the trust mechanism's effectiveness.
Limitations and Future Work
- Computational Overhead: The primary limitation acknowledged is the increased time complexity due to computing LZ complexity for each sample at every iteration, especially for large datasets and many boosting iterations. This leads to longer training times compared to highly optimized GBDT implementations.
- Future Work: The authors suggest improving scalability through approximate LZ complexity measures, sliding-window evaluations, and periodic trust updates. They also propose extending the information-theoretic trust concept to other areas like robust optimizers, curriculum learning, and online/continual learning for concept drift detection.
Summary updated