TL;DR
Boosted decision trees are great at prediction but terrible at estimating probabilities. This paper shows why this happens and introduces three methods (Platt Scaling, Isotonic Regression, and Logistic Correction) to fix it. Calibrated boosted trees outperform other methods, even when those methods are also calibrated.
What Problem Does This Paper Address?
Boosting algorithms, particularly AdaBoost, are incredibly effective at building accurate predictive models. They achieve high scores in metrics like accuracy, precision, and ROC area. However, a critical weakness emerges when it comes to estimating the probability of an event. AdaBoost's outputs, while good for ranking, are poorly calibrated, meaning the predicted probabilities don't accurately reflect the true likelihood of an outcome. This leads to poor performance on metrics like squared error and cross-entropy, which are sensitive to probability accuracy. The paper aims to understand why boosting produces these distorted probabilities and to develop methods to correct them.
Methods
The paper explores several approaches to obtain well-calibrated probabilities from boosted models:
- Understanding the Distortion: The authors analyze why boosting distorts probabilities. They show that boosting can be viewed as an additive logistic regression model where the output is related to the logit of the true probabilities, not the probabilities themselves. This "shifting" of predicted values away from 0 and 1, especially in cases close to the decision boundary, is a key reason for poor calibration. They visualize this distortion using reliability diagrams, which show a characteristic sigmoid shape.
- Post-Training Calibration Methods:
- Logistic Correction: This method leverages the theoretical understanding of boosting as an additive model. It uses a sigmoid function whose parameters are derived from the theoretical analysis.
- Platt Scaling: This is a well-established method that uses a sigmoid function to map model outputs (like those from SVMs) to probabilities. The sigmoid parameters are learned from data using gradient descent on a separate calibration set.
- Isotonic Regression: This is a more general, non-parametric method that assumes probabilities are a monotonically increasing function of the model's output. It finds this function using the Pair-Adjacent Violators (PAV) algorithm.
- Boosting with Log-Loss: An alternative to post-training calibration is to modify the boosting algorithm itself to directly optimize for log-loss (cross-entropy) instead of the standard exponential loss.
Datasets
The paper uses several publicly available datasets for evaluation:
- UCI Repository: ADULT, COV_TYPE, and LETTER (split into LETTER.P1 and LETTER.P2 to create different class imbalances).
- Other sources: HS (IndianPine92 data set), SLAC (particle physics data), MEDIS, and MG (medical data sets).
The paper also mentions using 3-fold cross-validation for estimating sigmoid parameters and for creating independent calibration sets, a technique popularized by Platt.
Key Insights and Ideas
- The "Sigmoid Shift": The core insight is that boosting, especially with complex base learners like decision trees, tends to push predictions away from the extremes (0 and 1). This is visualized by the characteristic sigmoid shape in reliability diagrams, which directly motivates using sigmoid-based calibration methods.
- Base Learner Complexity Matters: The effectiveness of different calibration methods is highly dependent on the complexity of the base learners used in boosting.
- For weak learners (like decision stumps), Logistic Correction and optimizing for log-loss work well.
- For complex learners (like full decision trees), these methods fail because the training data becomes too easily separable, leading to probabilities of exactly 0 or 1.
- Platt Scaling and Isotonic Regression are Robust: These two methods are effective across a range of base learner complexities and significantly improve probability calibration for boosted trees.
- Calibration is Crucial for State-of-the-Art Probabilities: Even after calibration, boosted decision trees consistently outperform other methods (SVMs, neural nets, random forests, etc.) in terms of probability accuracy, suggesting they are a strong choice when precise probability estimates are needed.
- Log-loss Boosting is a Mixed Bag: While optimizing for log-loss directly is theoretically appealing, it only performs well with weak base learners. With complex trees, it suffers from the same separability issues as other methods.
Key Results
- Significant Improvement: Platt Scaling and Isotonic Regression improve cross-entropy by about 21% and squared error by about 13% for boosted trees. For boosted stumps, calibration reduces cross-entropy by about 23% and squared error by about 14%.
- Boosted Trees Outperform Stumps: Boosted decision trees, when calibrated, significantly outperform boosted stumps on most problems (13% lower squared error and 18% lower cross-entropy on average).
- Calibrated Boosted Trees are Top Performers: After calibration, boosted decision trees yield the best average squared error and cross-entropy compared to SVMs, random forests, neural nets, bagged decision trees, and KNNs, even when those methods are also calibrated.
- Calibration is Effective Even with Small Data: Learning curves show that calibration improves performance even with relatively small calibration set sizes. Platt Scaling is slightly more robust than Isotonic Regression with very small calibration sets.
- Logistic Correction Limitations: Logistic Correction is effective for boosted stumps but performs poorly with boosted full decision trees due to the issue of perfect separability.
Limitations and Future Work
- Overfitting: The paper acknowledges the potential for overfitting when fitting calibration models, especially with small calibration sets. They use techniques like 3-fold cross-validation and out-of-sample models (for Platt Scaling) to mitigate this.
- Base Learner Complexity: The paper highlights that Logistic Correction and log-loss boosting are only effective for simple base learners. Future work could explore how to adapt these methods for more complex learners.
- Comparison to Other Methods: While the paper compares calibrated boosted trees to many other methods, the authors suggest that a more detailed discussion on predicting well-calibrated probabilities with supervised learning could be beneficial.
- Specific Tree Types: The paper uses various tree types for boosting. While they aim to cover different styles, future work might explore the impact of even more diverse tree architectures.
Summary updated