Efficient Algorithms for Bayesian Network Parameter Learning from Incomplete Data

Guy Van den Broeck, Karthika Mohan, Arthur Choi, Adnan Darwiche, Judea Pearl

Introduction

In real-world applications, datasets are rarely complete. Values are frequently missing due to sensor failures, skipped survey responses, or unperformed medical tests. To learn the parameters of a Bayesian network from such incomplete data, practitioners typically rely on the Expectation-Maximization (EM) algorithm or gradient-based optimization. However, these standard tools suffer from significant drawbacks: they are iterative and slow for large datasets, prone to getting stuck in local optima, and require computationally expensive probabilistic inference.

Researchers from UCLA have developed a new family of algorithms that bypass these bottlenecks. By leveraging "missingness graphs," these algorithms provide closed-form, mathematically consistent estimates that are orders of magnitude faster than EM, enabling parameter learning on massive networks where traditional methods fail.

The Missingness Graph Framework

The core of this approach is the explicit modeling of the missingness mechanism. By adding variables to the Bayesian network that represent the reason data is missing (e.g., a variable $R_y$ indicating whether $Y$ is observed), the problem of learning from incomplete data is transformed into a causal inference task. This perspective allows for the derivation of closed-form equations that "undo" the bias introduced by missing values without needing iterative loops.

Proposed Algorithms

The authors introduce three tiers of algorithms based on this framework:

  • Direct Deletion (D-MCAR/D-MAR): A generalized version of available-case analysis. It estimates probabilities using only the subsets of data where the required variables are observed. This method is proven to be mathematically consistent for data that is Missing Completely At Random (MCAR) or Missing At Random (MAR).
  • Factored Deletion (F-MCAR/F-MAR): This is the paper's primary innovation. Instead of relying on a single subset, it breaks a probability query into a "lattice" of different factorizations and aggregates estimates from across these views.
The lattice of factorizations allows Factored Deletion to aggregate information from multiple views of the data.

This aggregation allows the algorithm to utilize almost every row in the dataset, even those with missing values, significantly improving accuracy over simple deletion.

  • Informed Deletion (I-MAR/IF-MAR): These algorithms incorporate expert knowledge about the missingness mechanism (specifically its Markov blanket) to focus on relevant variables, leading to more precise estimates with less data.

Experimental Results and Performance

The algorithms were evaluated against well-known Bayesian network benchmarks, ranging from small models like alarm to complex networks like munin1 and a 400-variable synthetic grid.

Performance comparison showing KL Divergence relative to dataset size and computation time.

Key Findings:

  • Massive Speedups: On the alarm network, the proposed algorithms were orders of magnitude faster than EM. While EM required tens of seconds to converge, the new methods finished in milliseconds.
  • Superior Scalability: On large networks like munin1, EM and its variants often failed to complete even a single iteration within time limits. In contrast, Factored Deletion handled these complex structures with ease.
  • Accuracy and Convergence: While EM can be more statistically efficient on very small datasets, the proposed algorithms quickly catch up as the dataset size grows. On large datasets, F-MAR often outperformed EM because it avoids the local optima that frequently trap iterative methods.

Conclusion and Future Work

By treating missingness as a causal process, this research demonstrates that inference—the primary bottleneck in traditional parameter learning—is often unnecessary. The resulting closed-form algorithms offer a scalable, robust alternative to EM for big data applications. Future work includes extending these techniques to "Missing Not At Random" (MNAR) scenarios and applying efficient deletion methods to the problem of structure learning.

Summary updated

Abstract

We propose an efficient family of algorithms to learn the parameters of a Bayesian network from incomplete data. In contrast to textbook approaches such as EM and the gradient method, our approach is non-iterative, yields closed form parameter estimates, and eliminates the need for inference in a Bayesian network. Our approach provides consistent parameter estimates for missing data problems that are MCAR, MAR, and in some cases, MNAR. Empirically, our approach is orders of magnitude faster than EM (as our approach requires no inference). Given sufficient data, we learn parameters that can be orders of magnitude more accurate.
BibTeX
@inproceedings{broeck2015efficient,
  author = {Guy Van den Broeck and Karthika Mohan and Arthur Choi and Adnan Darwiche and Judea Pearl},
  title = {{Efficient Algorithms for Bayesian Network Parameter Learning from Incomplete Data}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=UfuxTrf9Ya},
}
Figure