MOB-ESP and other Improvements in Probability Estimation

Rodney D. NielsenUAI 2004

TL;DR

This paper introduces MOB-ESP, a novel ensemble method for estimating class probabilities that significantly outperforms existing techniques like Bagged Probability Estimation Trees (B-PETs) and their enhanced versions (EB-PETs). By leveraging out-of-bag (OB) examples and conditioning estimates on ensemble classifications, MOB-ESP achieves superior accuracy in predicting class probabilities, making it a valuable tool for decision-making under uncertainty.

What Problem Does This Paper Address?

In many machine learning applications, simply predicting a class label isn't enough. We often need to know the probability of each class to make informed decisions, especially in domains like medicine or finance where the cost of errors can be high. Traditional methods for estimating these probabilities, particularly those based on decision trees, suffer from several issues:

  • Bias towards extremes: Estimates tend to be too close to 0 or 1, especially when based on limited data.
  • Small leaf sizes: Leaves in decision trees often contain few training examples, leading to unreliable probability estimates.
  • Region-wide estimates: A single probability is assigned to an entire region of the input space, ignoring potential variations within that region.

While techniques like smoothing and bagging help, they don't fully resolve these problems. This paper aims to develop an algorithm that excels in average prediction accuracy, provides good probability rankings, and maintains reasonable computational costs.

Methods

The paper presents two main algorithmic contributions:

  • Enhanced Bagged Probability Estimation Trees (EB-PETs): This is an improved version of standard Bagged PETs. Key enhancements include:
  • Including Out-of-Bag (OB) Examples: OB examples (those not used to train a specific tree in the ensemble) are incorporated into the probability estimation process at the leaves. This increases the effective number of examples and reduces bias from training data.
  • Omission of Smoothing: The authors explore removing Laplace smoothing, hypothesizing that other enhancements might provide sufficient regularization.
  • Random Feature Selection: At each node, only a random subset of attributes is considered for splitting. This injects diversity and can lead to more specific probability estimates.
  • Mean Out-of-Bag Example-Specific Probability Estimator (MOB-ESP): This is the paper's core novel contribution. It addresses the estimation problem more directly by:
  • Using OB Classifications: MOB-ESP uses the true class of OB examples and their classifications from OB trees to estimate conditional probabilities.
  • Conditioning on Ensemble Classification: Crucially, MOB-ESP conditions probability estimates on the ensemble's classification of a given example. The rationale is that examples classified similarly by the ensemble are likely to be in more similar regions of space, thus having more similar true class probabilities. This allows for more "example-specific" probability estimates.

Datasets

The algorithms were evaluated on 20 benchmark UCI datasets. The paper notes that for multi-class datasets, only two classes were selected for prediction, often based on having a higher number of examples or a higher confusion rate. No new datasets were introduced.

Key Insights and Ideas

  • OB examples are powerful: Incorporating out-of-bag examples into probability estimation significantly boosts performance, suggesting that data not directly involved in tree construction provides a more unbiased view.
  • Ensemble classification as a proxy for similarity: Conditioning probability estimates on the ensemble's prediction for an example is a surprisingly effective way to group similar instances and improve probability estimates. This is the core idea behind MOB-ESP.
  • Smoothing might not always be necessary: The experiments suggest that with sufficient ensemble diversity (from bagging and random feature selection), explicit smoothing might be detrimental or at least not always required for good performance.
  • Different metrics capture different aspects: The paper highlights that no single metric is universally best. While MOB-ESP excels in accuracy (0/1-MSE, AvLL), EB-PETs performed better on probability ranking (AULC), indicating trade-offs.

Key Results

  • MOB-ESP significantly outperforms B-PETs and EB-PETs: Across all tested metrics (0/1-MSE, AvLL, AULC, ∆Acc), MOB-ESP showed superior performance compared to both baseline B-PETs and the enhanced EB-PETs.
  • MOB-ESP excels in average prediction accuracy: It achieved substantially better results on 0/1-MSE and AvLL, indicating more accurate probability estimates.
  • EB-PETs shows improvements over B-PETs: The enhancements in EB-PETs (OB examples, no smoothing, random features) collectively led to significant improvements over the baseline B-PETs.
  • MOB-ESP's advantage over EB-PETs: MOB-ESP demonstrated a notable win rate over EB-PETs, particularly in accuracy metrics (0/1-MSE and AvLL). However, EB-PETs performed better on the Area Under the Lift Chart (AULC).

Limitations and Future Work

  • AULC performance of MOB-ESP: The paper notes that MOB-ESP's performance on the AULC metric was surprisingly lower than EB-PETs, and this is identified as an area for future investigation.
  • Number of trees (T): For MOB-ESP, the number of OB examples used for estimation is 0.37T. The authors suggest that increasing T might lead to better results, as it's unlikely that 0.37T is always sufficient for peak performance.
  • Weighting factor (α): The weighting factor α in MOB-ESP's probability estimation was set to 1. The paper suggests that automatically choosing a more appropriate value for α, potentially favoring OB examples, could be beneficial.
  • Generalization to multi-class: The current implementation was restricted to 2-class problems. Extending MOB-ESP to handle multi-class datasets more robustly is a natural next step.
  • Unknown attribute values and nominal attributes: The implementation did not explicitly handle these, which could be addressed in future work.
  • Pruning and smoothing interactions: The paper mentions that pruning might be beneficial when smoothing is disabled, and Ferri et al. (2003) are cited for improving AUC with smoothing, suggesting further exploration of these interactions.

Summary updated

BibTeX
@inproceedings{nielsen2004mob,
  author = {Rodney D. Nielsen},
  title = {{MOB-ESP and other Improvements in Probability Estimation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2004},
}
Figure