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.
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.
Key Findings:
- Massive Speedups: On the
alarmnetwork, 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