Abstract
Learning the structure of Bayesian Networks (BNs) is a fundamental challenge in machine learning, particularly when data is scarce or incomplete. Standard scoring methods often overfit to noise in small samples, leading to poor generalization. This paper introduces Bagged Structural EM (BSEM), a method that applies bootstrap aggregation (bagging) to model selection. By reducing the variance of structural decisions, BSEM produces a single, coherent density model that significantly outperforms standard approaches in generalization.
The Challenge: Overfitting in Small Samples
Deciding which variables should be connected in a Bayesian Network is notoriously difficult with limited data. Standard tools like the Bayesian Information Criterion (BIC) or the Bayesian score frequently "overfit" to noise, making incorrect local structural decisions that compromise the entire model.
While the Bootstrap method has been used to estimate confidence in specific network features, it typically does not yield a final, usable model for density estimation. Moreover, when data is missing, combining bootstrap methods with the Expectation-Maximization (EM) algorithm is often computationally prohibitive.
Proposed Method: Bagged Structural EM (BSEM)
The paper proposes two primary innovations to address these issues:
- Bagged Objective Function: Instead of selecting a structure based on a single score from the training data, BSEM calculates the average score across $B$ different bootstrap datasets. This bagging approach reduces the variance of the score, filtering out structural moves that appear beneficial only due to random fluctuations in small samples.
- Efficient EM Integration: To handle missing data, BSEM introduces a modified EM procedure. Rather than performing expensive probabilistic inference $B$ times per iteration, BSEM performs inference once on the original data to compute "expected statistics" and then re-weights these for each bootstrap sample. This optimization makes the algorithm practical, running only ~10x slower than standard learning rather than 100x slower.
Key Insights: Variance is the Enemy
A central insight of this work is that in scarce data scenarios, the variance of the log-likelihood is a much greater threat to model quality than its bias. By treating each bootstrap dataset as an "expert," the bagged objective leverages a "wisdom of crowds" effect. This consensus prevents greedy searches from getting trapped in poor local maxima driven by noise.
Experimental Results
BSEM was evaluated on several high-dimensional, small-sample datasets, including synthetic medical diagnostics (Alarm), sensor data (Temperature), and gene expression data (Rosetta & Gasch).
Key findings include:
- Superior Generalization: BSEM consistently outperformed BIC and Bayesian scores. In some instances, it improved performance by "half a bit per instance," making test data orders of magnitude more likely under the BSEM model.
- Robustness to Priors: Unlike the standard Bayesian score, which is sensitive to the choice of "equivalent sample size" (ESS), BSEM maintained consistent performance across a wide range of prior strengths.
- Computational Viability: Despite the overhead of bagging, the optimized implementation ran only 7–12 times longer than standard structure learning.
Conclusion and Future Work
BSEM provides a robust framework for learning Bayesian Network structures from limited or incomplete data. While current theoretical guarantees for improvement at each iteration are asymptotic, empirical results demonstrate strong performance even on very small datasets. Future research could explore integrating bagging into more sophisticated search algorithms beyond standard greedy hill-climbing.
Summary updated