The Bayesian Structural EM Algorithm

Nir FriedmanUAI 1998

TL;DR

This paper introduces the Bayesian Structural EM algorithm, a novel approach for learning the structure of probabilistic models (like Bayesian networks) directly from incomplete data. It extends previous work by optimizing the true Bayesian score, offering a principled way to incorporate prior knowledge and potentially leading to more accurate models than methods relying on approximations or complete data.

What Problem Does This Paper Address?

Learning the structure of probabilistic models, such as Bayesian networks, from data is a fundamental task in artificial intelligence. While significant progress has been made when the data is complete (i.e., all variables have observed values for each data point), learning from incomplete data (where some values are missing or hidden) remains a major challenge. Existing methods often struggle to effectively learn model structure when data is incomplete, either requiring complete data for training or relying on approximations of the true model score. This limitation hinders the application of these powerful models to real-world datasets, which frequently contain missing information. The paper aims to bridge this gap by developing an algorithm that can learn model structure directly from incomplete data using a theoretically grounded Bayesian approach.

Methods

The core of the paper is the Bayesian Structural EM algorithm. This algorithm iteratively refines a candidate model structure. At each step, it performs two main operations:

  • E-step (Expectation): It computes the expected log-score of potential model structures, given the current best model and the incomplete data. This involves dealing with missing values by effectively "completing" the data based on the current model's probabilistic estimates.
  • M-step (Maximization): It selects a new model structure that maximizes this expected log-score.

This process is inspired by the Expectation-Maximization (EM) algorithm but is adapted for structure learning. The paper also introduces the concept of factored models, a general class of probabilistic models that includes Bayesian networks, multinets, and decision trees. The algorithm is designed to work with these factored models, leveraging their decomposable structure.

Key to the algorithm's success are several assumptions about the models and their priors:

  1. Separable Factored Models: Models are composed of independent factors.
  2. Exponential Factors: Each factor belongs to the exponential family.
  3. Parameter Independence: Priors over parameters for different factors are independent.
  4. Parameter Modularity: Priors are consistent across similar factors.

The paper also discusses various approximations for computing the expected score, particularly for dealing with the integrals involved in Bayesian scoring with incomplete data. These include summation, integration, and Laplace's approximation, with a focus on how these approximations perform for Dirichlet priors commonly used with multinomial factors.

Datasets

The paper uses two real-world datasets for evaluation:

  • alarm: A network for intensive care patient monitoring with 37 variables.
  • insurance: A network for classifying car insurance applications with 26 variables.

Artificial training data was generated from these networks, with varying percentages of missing values introduced to simulate incomplete data scenarios. The experiments also involved learning models with varying numbers of hidden variables.

Key Insights and Ideas

  • Direct Bayesian Score Optimization: The algorithm's main innovation is its attempt to directly optimize the true Bayesian score, rather than relying on approximations like BIC/MDL or asymptotic forms. This offers a more principled way to model selection.
  • Structural EM for Bayesian Scores: Extending the Structural EM framework to handle Bayesian scores is a significant step, as Bayesian scores are generally considered superior for model selection and incorporating prior knowledge.
  • Handling Incomplete Data: The algorithm's ability to learn structure directly from incomplete data is crucial for real-world applications where complete data is rare. The "completion" step in the E-step is key to this.
  • Factored Models Generalization: Defining and working with "factored models" provides a unified framework for learning various probabilistic graphical models, not just standard Bayesian networks.
  • Approximation Trade-offs: The paper highlights that different approximations for computing the Bayesian score (summation, integration, Laplace, linear) have varying performance characteristics, with simpler approximations sometimes being surprisingly effective, especially in larger datasets.

Key Results

  • Improved Performance with Incomplete Data: Experiments showed that the Bayesian Structural EM algorithm consistently outperformed the BIC score-based Structural EM when learning from incomplete data, even with the same prior.
  • Approximation Performance: The summation approximation generally yielded the best results, followed by integration, while the linear approximation was sometimes competitive, especially on larger datasets. This suggests that simpler approximations can be effective when the data is sufficiently informative.
  • Hidden Variable Learning: The algorithm demonstrated its capability to learn models with hidden variables, although the performance was sensitive to the initial structure and the search procedure's ability to escape local optima.
  • Convergence Guarantees: The paper provides theoretical guarantees for the convergence of the abstract Bayesian Structural EM algorithm, ensuring progress towards better models at each iteration.

Limitations and Future Work

  • Local Maxima: Like many EM-based algorithms, the Structural EM algorithm can converge to local optima in the search space of model structures. The paper acknowledges this and suggests using random restarts and perturbations to mitigate this issue.
  • Computational Cost: Evaluating the expected score for each factor can be computationally intensive, especially with large datasets or complex models. This is identified as a bottleneck for scaling the algorithm.
  • Choosing the Number of Hidden Variables: The current method for selecting the number of hidden variables is described as a "blind approach" (trying different numbers and picking the best). Future work should focus on more intelligent methods for determining the optimal number of hidden variables.
  • Theoretical Understanding of Approximations: While empirical results are presented, further theoretical analysis is needed to fully characterize the conditions under which the various approximations (especially the linear one) are accurate.
  • Combining with Other Methods: The paper suggests exploring the combination of variational approaches with this learning framework and investigating Bayesian model averaging for learning committees of models.

Summary updated

BibTeX
@inproceedings{friedman1998bayesian,
  author = {Nir Friedman},
  title = {{The Bayesian Structural EM Algorithm}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1998},
}
Figure