Abstract
The Expectation Maximization (EM) algorithm is a standard tool for training Bayesian networks but suffers from slow convergence and susceptibility to local optima. To mitigate these issues, practitioners often employ multiple random restarts, which is computationally expensive. This paper presents Age-Layered EM (ALEM), a novel strategy that organizes parallel EM runs into a tiered tournament structure. By aggressively culling underperforming runs in early stages, ALEM achieves a 2x to 4x speedup with negligible impact on accuracy.
Introduction
Bayesian networks are essential for modeling complex dependencies in machine learning. When dealing with missing or hidden data, the Expectation Maximization (EM) algorithm is typically used for parameter estimation. However, EM is a greedy algorithm prone to getting stuck in local optima. The standard solution—running EM hundreds of times from different initializations—is computationally grueling, especially as many of these runs converge slowly toward suboptimal solutions.
The primary challenge addressed here is efficiency: how to identify and terminate "loser" runs early to focus computational resources on the most promising initializations.
Methodology: Age-Layered EM (ALEM)
ALEM is inspired by the Age-Layered Population Structure (ALPS) from genetic algorithms. It treats the "age" of an EM run as its iteration count and organizes runs into multiple layers, each with an increasing age limit.
The core of ALEM is its Culling Mechanism. When a run reaches the age limit of its current layer, it must compete to move to the next. It is only promoted if its log-likelihood exceeds the worst-performing run in the target layer; otherwise, it is discarded. By using exponential aging ($β_i = a \cdot 2^{i-1}$), ALEM filters out poor initializations very quickly while allowing high-performing "finalists" to converge fully.
Experimental Setup
The algorithm was evaluated using two benchmark Bayesian networks:
- Carstarts: 18 nodes, representing automotive diagnostics.
- Alarm: 37 nodes, representing medical monitoring in an intensive care unit.
Synthetic datasets ranging from 100 to 4,000 samples were used, testing various configurations of hidden variables to ensure robustness.
Results and Analysis
ALEM demonstrated a significant reduction in computational overhead across all test cases. The average number of iterations was reduced by a factor of 2 to 4. Crucially, this reduction in iterations translated directly into wall-clock time savings, particularly for larger datasets.
As shown in the figures, the time savings become more pronounced as the sample size increases. In the Alarm network (Figure 6), ALEM consistently outperforms traditional EM, often completing in less than half the time. Similar trends were observed in the Carstarts network.
Despite the aggressive culling, ALEM maintained high accuracy, finding solutions within 0.007% of the global maximum identified by exhaustive traditional EM. This suggests that early log-likelihood is a reliable predictor of final convergence quality.
Discussion and Conclusion
A key insight from this work is the "Slow Loser" phenomenon: runs destined for poor local optima often converge more slowly than those heading toward the global maximum. ALEM exploits this by focusing resources on "fast winners."
While ALEM introduces new hyperparameters, such as the age gap and minimum runs per layer, the authors found that standard values work well across different networks. Future work may explore dynamic tuning of these parameters using techniques like simulated annealing or testing on even larger-scale "big data" networks. In conclusion, ALEM offers a practical and effective way to scale Bayesian network parameter learning without sacrificing model quality.
Summary updated