Efficient Algorithms for Bayesian Network Parameter Learning from Incomplete Data

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

Introduction

Learning parameters for Bayesian Networks (BNs) is a fundamental task in probabilistic machine learning. However, real-world datasets are often plagued by missing values. While the Expectation-Maximization (EM) algorithm is the standard approach for handling incomplete data, it suffers from significant computational bottlenecks, particularly as datasets scale. This paper presents a family of closed-form, non-iterative algorithms that bypass the need for expensive probabilistic inference, offering a faster and more robust alternative to traditional methods.

The Challenge of Incomplete Data

Traditional parameter learning from incomplete data relies on iterative optimization. Methods like EM or gradient descent require multiple passes over the dataset. More critically, they necessitate probabilistic inference to "fill in" missing values during each iteration. For complex, high-treewidth networks, this inference is NP-hard, making learning computationally intractable. Furthermore, these iterative approaches are prone to converging on local optima, often failing to find the globally optimal parameter set.

Inference-Free Learning Methods

The authors propose a paradigm shift: "inference-free" learning. By leveraging missingness graphs, which explicitly model the causal mechanisms behind missing data, they derive closed-form estimators that can be computed in a single pass.

Missingness graphs and data tables illustrating observed (ob), missing (mi), and unobserved (unob) states.

Three primary strategies are introduced:

  1. Direct Deletion: A re-weighting scheme for Missing At Random (MAR) data that ensures consistency without inference.
  2. Factored Deletion: This method utilizes a factorization lattice to break the distribution into smaller components. It maximizes data utility by using any record where at least one variable in a node's "family" (the node and its parents) is observed.
  3. Informed Deletion: When the specific missingness mechanism is known, this algorithm targets a minimal subset of observed variables to improve data efficiency.

By eliminating the inference step, these algorithms decouple the complexity of the network structure from the learning process, allowing for efficient training even on massive datasets.

Experimental Results

The proposed algorithms (D-MAR and F-MAR) were evaluated against EM on several benchmark networks, ranging from small tractable models like "Fire Alarm" to large, high-treewidth networks like "Munin 1" and "Grid 90-20-1".

Performance metrics for the Fire Alarm and Alarm networks, comparing KL divergence, log-likelihood vs. size, and log-likelihood vs. time across different algorithms.

Key Findings:

  • Computational Speed: The new methods are orders of magnitude faster than EM. In many instances, EM timed out after 25 minutes, whereas the proposed algorithms finished in seconds.
  • Scalability: The algorithms successfully learned parameters for intractable networks where EM failed due to the complexity of internal inference.
  • Accuracy: On large datasets, the closed-form solutions often achieved lower Kullback-Leibler (KL) divergence than EM. Because they are not iterative, they avoid the local optima traps that frequently degrade EM's performance.
  • Data Efficiency: Factored deletion strategies significantly outperformed direct deletion by making better use of partially observed records, particularly in sparse data scenarios.

Conclusion

This research demonstrates that the primary bottleneck in learning from incomplete data is not the data volume itself, but the requirement for inference during training. By adopting closed-form, inference-free estimators, researchers can achieve significant speedups and better convergence properties. While EM may still hold an advantage on very small datasets where global model structure can help "guess" missing values, these new algorithms provide a scalable, consistent, and efficient solution for modern big-data applications.

Summary updated

BibTeX
@inproceedings{broeck2015efficient,
  author = {Guy Van den Broeck and Karthika Mohan and Arthur Choi 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