Does ordinary EM learn network edges?

Standard parameter EM keeps the chosen structure fixed; structural EM extends learning to structure changes.

Are expected counts always whole numbers?

No. Missing records can contribute probability-weighted amounts to multiple possible combinations.

Does the method guarantee the globally best graph?

No. Search choices, local optima, initialization, and approximations limit what can be concluded.

AI Glossary / Graphs and symbolic AI / Advanced

Structural EM

Definition

Structural EM is a framework for learning the structure of a probabilistic model from incomplete data by combining expectation-maximization with structure search. Ordinary EM adjusts parameters within a chosen model structure. Structural EM can also change that structure, such as the edges of a Bayesian network, while using the current model to reason about missing or hidden values.

What it means

A Bayesian network has both a graph and numerical probabilities. The graph specifies which variables directly condition others; the parameters quantify those relationships. When data contain gaps, evaluating every candidate graph by fitting it from scratch can be expensive.

Structural EM uses the current model's explanation of the missing information to support comparisons between candidate structures. It alternates revising that explanation with improving the model. The name refers to probabilistic model learning, not civil engineering, and “EM” here means expectation-maximization rather than a structural equation model.

How it works

Begin with an initial structure and parameter estimates. In an expectation step, infer distributions over missing values conditional on the observed records and current model. For suitable models, summarize these distributions as expected sufficient statistics, such as fractional counts of variable combinations.

In a structural maximization step, search allowed candidate graphs using a chosen expected-data objective, with an appropriate complexity penalty or prior. Re-estimate parameters as required and repeat the inference and search steps. Bayesian networks must remain acyclic, and domain restrictions may forbid particular edges.

Different structural EM variants use different scores and approximations. Computing a score from expected counts is not universally identical to taking the expectation of a nonlinear score. Exact theoretical improvement guarantees therefore should not be transferred casually to sampling-based inference, hard imputations, or altered search procedures. Convergence is not a guarantee of a globally best structure.

Three practical examples

Operational diagnosis: explore dependencies among observed equipment indicators when some measurements are absent, while treating missingness assumptions as part of the model.
Behavioral research: build probabilistic descriptions of partially completed questionnaires, comparing predictive usefulness without interpreting every learned arrow as causal.
Simulated-data studies: hide known values deliberately and examine how initialization, missing-data patterns, and permitted network structures affect the recovered model.

Think of it this way

Think of reconstructing a partially erased map while also reconsidering which roads belong on it. Your current map helps guess missing details; those guesses help compare revised maps. The analogy is limited because structural EM uses distributions and numerical objectives, not freehand guessing. Inferred values remain uncertain and do not become newly observed facts.

Worked example

Take an original toy dataset with binary variables A and B and four records: (0,0), (1,1), (1,missing), and (0,missing). Suppose the current model gives P(B=1 | A=1)=0.8 and P(B=1 | A=0)=0.2. These are stipulated starting probabilities, not estimates already justified by four records.

The incomplete A=1 record contributes expected counts 0.8 to (1,1) and 0.2 to (1,0). The incomplete A=0 record contributes 0.2 to (0,1) and 0.8 to (0,0). Including the observed records gives counts n00=1.8, n01=0.2, n10=0.2, and n11=1.8. They total four, preserving the dataset's size.

Compare an independent model P(A)P(B) with a model P(A)P(B|A). Fitting these expected counts gives P(A=1)=P(B=1)=0.5 for independence. The dependent model instead gives P(B=1|A=0)=0.1 and P(B=1|A=1)=0.9.

Using natural logarithms, their maximized expected complete-data log-likelihoods are approximately −5.545 and −4.073. For an illustrative BIC-style structural objective Q − (k/2) ln(4), the parameter counts are two and three. The scores are approximately −6.931 and −6.152, respectively, favoring the dependent candidate in this comparison.

This is one expected-count structure comparison, not a completed learning run or an exact Bayesian marginal-likelihood calculation. A new expectation step would use the updated model. The tiny example does not justify a causal interpretation of A→B.

Illustrative case study

Fictional case: an analytics team studies incomplete service logs with a Bayesian network. An initial model assumes several indicators are independent. Rather than delete every incomplete row, the team evaluates structural EM with documented initial graphs and restrictions on possible relationships.

Several starting points yield different fitted graphs, so the team compares held-out prediction and stability instead of publishing one graph as the true operating mechanism. The fictional case illustrates interpretation and model review; it supplies no measured improvement and does not establish that the missing values are ignorable.

Common misconceptions and mistakes

Structural EM is not simply ordinary EM with a different label: structure selection is part of the procedure. Filling every blank once and then forgetting uncertainty is not the general expectation-based method. Fractional counts represent expectations, not fractions of people or newly collected observations.

A learned edge is not automatically a causal link. A higher training objective does not ensure better future predictions. Data that are missing because of their unobserved values can require explicit modeling of the missingness process; the algorithm does not remove that concern merely by accepting incomplete inputs.

Business use

The method is useful when interpretable probabilistic structure matters and missing data prevent straightforward complete-data learning. Budget for repeated inference and graph search, and document the score, constraints, initialization, stopping rule, and approximation choices.

Retain the original observed-versus-missing distinction in downstream records. Evaluate predictions on data withheld from fitting and test sensitivity to alternative starts. If the business question is causal intervention, obtain an appropriate causal design and assumptions rather than treating structure search as sufficient evidence.

Check your understanding

One missing binary value has posterior probability 0.7 of being one. Must the expectation step replace it permanently with one?

Answer: No. A soft expected-count calculation contributes 0.7 to the one case and 0.3 to the zero case, preserving uncertainty.

Related terms

Learn next

Practice one ordinary EM update before allowing graph changes. Reproduce the toy expected counts, then compare how a stronger complexity penalty changes candidate selection. Study missingness mechanisms and the distinction between predictive and causal graphs.

Causal graphs

Sources

Nir Friedman, The Bayesian Structural EM Algorithm: https://ai.stanford.edu/~nir/Papers/Fr2.pdf Marco Scutari, bnlearn structural EM example and approximation caveats: https://www.bnlearn.com/examples/missing-score/ The arithmetic and fictional case are original. The worked objective illustrates penalised expected complete-data fitting, not every structural EM variant.

Previous: Structural causal model Next: Structural equation modeling