Age-Layered Expectation Maximization for Parameter Learning in Bayesian Networks

Avneesh Singh Saluja, Priya Krishnan Sundararajan, Ole J. MengshoelAISTATS 2012

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:

  1. Carstarts: 18 nodes, representing automotive diagnostics.
  2. 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.

Figure 6: Time comparison for the Alarm Bayesian network showing ALEM's significant speedup over traditional EM across various sample sizes.

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.

Figure 3: Time comparison for the Carstarts Bayesian network, illustrating consistent performance gains with ALEM.

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

BibTeX
@article{saluja2012age,
  author = {Avneesh Singh Saluja and Priya Krishnan Sundararajan and Ole J. Mengshoel},
  title = {{Age-Layered Expectation Maximization for Parameter Learning in Bayesian Networks}},
  journal = {AISTATS},
  year = {2012},
}
Figure