Learning Bayesian Networks from Incomplete Data

34 concepts24 papers1 proposal

Bayesian networks are powerful tools for mapping complex dependencies among variables. When our data is complete, learning the structure and parameters of these networks is straightforward. However, real-world datasets are frequently riddled with missing values or hidden variables.

When data is incomplete, the elegant mathematical properties that make Bayesian networks computationally tractable begin to break down. Overcoming this challenge requires a mix of structural expectation algorithms, geometric insights, and exact data augmentation techniques.

The Core Challenge: The Breakdown of Factorization

To understand why incomplete data paralyzes standard learning algorithms, we must first look at why complete data makes learning easy.

When a dataset is fully observed, the joint probability distribution of a Bayesian network factorizes neatly into a product of local conditional probabilities—each node depends only on its parents. For parameter learning, this factorization means the log-likelihood function decomposes into a sum of independent local terms. We can optimize the parameters of each node independently by simply counting frequencies in the data. For structure learning, scoring metrics like cross-entropy or marginal likelihood similarly decompose, allowing us to evaluate local edge changes (like adding or reversing an arrow) without re-evaluating the entire network, as shown by Cowell in Conditions Under Which Conditional Independence and Scoring Methods Lead to Identical Selection of Bayesian Network Models.

Complete Data:   [Node A] ---> [Node B]  (Factorizes perfectly; independent optimization)

Incomplete Data: [Node A] ---> [Node ?]  (Couples parameters; non-convex optimization surface)

When values are missing, this independence vanishes. If a parent or child node is unobserved, we must marginalize (sum out) the missing variable to compute the likelihood of our observed data. This summation couples parameters across different nodes that were previously isolated.

As a result, the log-likelihood surface loses its nice, concave shape and becomes a complex, non-convex landscape marred by many local optima, a geometric reality detailed by Settimi et al. in On the Geometry of Bayesian Graphical Models with Hidden Variables. Computing the marginal likelihood directly becomes mathematically intractable, as noted by Ramoni et al. in Learning Bayesian Networks from Incomplete Databases.

The Structural EM Paradigm

The traditional workhorse for parameter estimation with missing data is the Expectation-Maximization (EM) algorithm, which alternates between filling in missing values based on current parameter guesses (the E-step) and updating the parameters using this completed data (the M-step), as discussed by Bauer et al. in Update Rules for Parameter Estimation in Bayesian Networks.

But what happens if we do not know the network structure either? Running a full structure search inside every iteration of an EM algorithm would be computationally crushing.

To solve this, Friedman introduced The Bayesian Structural EM Algorithm. The core intuition is to flip the order of operations: instead of searching for structures using incomplete data, we use our current best guess of the model structure to compute the expected sufficient statistics of the data.

  +---------------------------------------------------------+
  |                                                         |
  v                                                         |
[E-Step] Compute expected sufficient statistics using      |
         the current structure and parameters.              |
  |                                                         |
  v                                                         |
[M-Step] Search for a NEW network structure that maximizes  |
         the expected Bayesian score.                       |
  |                                                         |
  +---------------------------------------------------------+

By maximizing this expected score during the M-step, the algorithm evaluates new candidate structures as if the data were complete. Because it optimizes a formal lower bound on the true Bayesian score, each structural change is guaranteed to improve (or maintain) the actual posterior probability of the model given the incomplete data.

Parameter Estimation as Network Inference

While EM is highly flexible, it treats parameter estimation as a generic optimization problem, completely ignoring the graph structure it is trying to parameterize. This blind spot can cause EM to converge slowly or get trapped in poor local maxima.

To exploit network structure directly, Choi et al. developed Edge-Deletion MAP-Learning (EDML) in EDML: A Method for Learning Parameters in Bayesian Networks. Instead of treating parameter estimation as a coordinate descent search, the authors reframed it as an approximate inference problem on the network itself.

Imagine treating the network's parameters themselves as hidden nodes in a meta-network. By conceptually deleting the edges that connect these parameter nodes to their corresponding variables, the parameters become conditionally independent given the data.

The authors demonstrate that we can then use standard message-passing algorithms (like belief propagation) to let different regions of the network talk to one another. Missing values in one part of the network naturally send probabilistic "messages" to update parameters in another part. This structural reasoning allows EDML to bypass the slow, iterative steps of EM, often finding optimal parameters in a single iteration for common missing-data patterns.

Non-Iterative Bounding and Exact Reductions

When datasets are massive or highly incomplete, iterative algorithms like EM or stochastic Markov Chain Monte Carlo searches—such as those proposed by Myers et al. in Learning Bayesian Networks from Incomplete Data with Stochastic Search Algorithms—can become too expensive. This has driven research into deterministic, non-iterative alternatives.

One prominent approach is the "Bound and Collapse" method introduced by Ramoni et al. in Learning Bayesian Networks from Incomplete Databases. Rather than trying to impute a specific value for a missing entry, the algorithm estimates the absolute upper and lower bounds of what that missing value could be ("Bound"). It then collapses these intervals into a single point estimate using an information-theoretic framework based on the available data ("Collapse"). This approach provides a deterministic, highly scalable estimation process that remains stable regardless of how much data is missing.

For structure learning, de Campos et al. uncovered a surprising theoretical property: the decision problem for structure learning with incomplete data shares the exact same NP-complete complexity class as learning with complete data (Learning Bayesian Networks with Incomplete Data by Augmentation).

Because the underlying computational complexity is identical, the authors showed that an incomplete dataset can be mathematically reduced to an augmented, complete dataset by introducing new indicator variables that explicitly model the missingness mechanism. This allows researchers to apply highly optimized, exact complete-data structure solvers directly to incomplete datasets, bypassing approximations entirely.

Rethinking the Logic of Independence

Missing data does not just complicate optimization; it fundamentally alters the mathematical rules governing probability distributions. In complete datasets, conditional independence (CI) statements follow a well-known set of rules called the semi-graphoid axioms. These axioms allow us to safely infer new independence relationships from existing ones.

However, Link demonstrated that when data is missing, these classical axioms partially break down (Reasoning about Saturated Conditional Independence Under Uncertainty: Axioms, Algorithms, and Levesque's Situations to the Rescue). For instance, the presence of missing values can invalidate the symmetry or decomposition rules we take for granted in standard Bayesian networks.

By mapping the behavior of "saturated" conditional independence under missing data to non-classical logics and database dependency theory, Link established a new, sound set of formal axioms. This logical foundation gives us a precise framework for understanding what can and cannot be mathematically inferred when our observations are incomplete, ensuring that future structure learning algorithms rest on a theoretically sound foundation.

Key Foundational Work

A Bayesian Method for Constructing Bayesian Belief Networks from Databases (1991) — contributed 1 concept elements to this direction.
aHUGIN: A System Creating Adaptive Causal Probabilistic Networks (1992) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_parameter_estimation_with_incomplete_dat_7bebfc6b,
  title = {parameter estimation with incomplete data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameter-estimation-with-incomplete-data/rdr_7bebfc6b97a64e658fd0d6d18beffe54},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_parameter_estimation_with_incomplete_dat_7bebfc6b_v1,
  title = {parameter estimation with incomplete data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameter-estimation-with-incomplete-data/rdr_7bebfc6b97a64e658fd0d6d18beffe54/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake