Abstract: A common approach to aggregate classification estimates in an ensemble of decision trees is to either use voting or to average the probabilities for each class. The latter takes uncertainty into account, but not the reliability of the uncertainty estimates (so to say, the "uncertainty about the uncertainty"). More generally, much remains unknown about how to best combine probabilistic estimates from multiple sources. In this paper, we investigate a number of alternative prediction methods. Our methods are inspired by the theories of probability, belief functions and reliable classification, as well as a principle that we call evidence accumulation. Our experiments on a variety of data sets are based on random decision trees which guarantees a high diversity in the predictions to be combined. Somewhat unexpectedly, we found that taking the average over the probabilities is actually hard to beat. However, evidence accumulation showed consistently better results on all but very small leafs.
1. Introduction: The Combination Problem
Ensemble methods like Random Forests typically aggregate predictions via majority voting or probability averaging. While effective, these methods often overlook the reliability of individual estimates. For instance, a leaf node with a 100% class frequency based on two samples is statistically less reliable than one with 80% based on a hundred samples. This paper investigates the "combination problem"—how to best aggregate probabilistic estimates while accounting for "uncertainty about the uncertainty" (epistemic uncertainty).
2. Methodology: Random Decision Trees
To test various aggregation strategies, the authors utilized Random Decision Trees (RDTs). Unlike standard decision trees that optimize splits for information gain, RDTs select split points randomly. This ensures high diversity and "unstable" individual predictions, providing a rigorous testbed for aggregation theories. The study evaluated these methods across 21 UCI and OpenML datasets, covering a wide range of scales, dimensionalities, and class balances.
3. Aggregation Strategies
The researchers compared several frameworks to address the limitations of simple averaging:
- Probability Averaging: The standard arithmetic mean of class probabilities.
- Laplace Smoothing: Adding a constant to counts to prevent zero probabilities, a common technique to handle low-evidence scenarios.
- Belief Functions: Drawing from Dempster-Shafer theory, these methods (including Dempster’s Rule and the Cautious Rule) assign "mass" to beliefs and combine them using specific logical rules.
- Evidence Accumulation (EVA): The primary contribution of this work. Inspired by Naive Bayes, EVA treats each tree as an independent source of evidence. Instead of averaging, it multiplies the class prior by factors representing the deviation of each tree's prediction from that prior.
4. Key Results and Insights
The experiments revealed that while probability averaging is a remarkably robust baseline, it can be surpassed by more sophisticated accumulation methods, particularly when leaf sizes are sufficient.
- The Robustness of Averaging: In large ensembles (e.g., 100 trees), simple averaging often compensates for the over-optimism of small, high-certainty leaves. As shown in Figure 1, standard probability scores stabilize as evidence increases.
- EVA Superiority: Evidence Accumulation (EVA) consistently outperformed other methods in terms of accuracy, particularly as the minimum leaf size increased. By treating trees as independent evidence sources, EVA effectively "accumulates" conviction rather than diluting it through averaging. Note the distinct scale of EVA scores in Figure 2, reflecting its multiplicative nature.
- Dempster’s Rule and Imbalance: While Dempster’s Rule performed well on balanced data, it struggled with imbalanced datasets, suggesting limitations in its current integration with class priors.
- The Pitfall of Laplace Smoothing: Surprisingly, Laplace smoothing was found to hinder performance in RDT ensembles, likely by washing out the distinct signals provided by the diverse trees.
5. Conclusion
The study demonstrates that treating ensemble members as independent sources of evidence via Evidence Accumulation (EVA) provides a significant accuracy boost over traditional averaging. While probability averaging remains competitive for ranking tasks (AUC), EVA offers a more principled and effective way to handle the "uncertainty about uncertainty" inherent in diverse ensembles like RDTs. Future work will explore the applicability of EVA to optimized ensembles like Random Forests and its performance in smaller ensembles.
Summary updated