Learning Network Structure
Scores, search and causal discovery.
Ten variables admit about different DAGs. Which one generated your data? Scores turn the question into optimization, and the PC algorithm turns it into a sequence of independence tests. Both run into hard limits: the search is NP-hard, and observational data identify a graph only up to Markov equivalence, unless you are willing to assume more.
What you’ll learn
- Derive the mutual-information decomposition of the log-likelihood score, and the BIC and Bayesian (BDeu) scores with their consistency and score equivalence.
- Prove the Chow–Liu theorem, and state the NP-hardness of learning networks with two or more parents per node (Chickering, 1996).
- Run the PC algorithm with Meek's orientation rules, and state the assumptions under which it recovers the essential graph.
- Explain when the full DAG becomes identifiable (non-Gaussian or additive-noise models, interventions), and the pitfalls of continuous-optimization methods.
Scoring a structure
Score-based learning picks . With complete data, the parameters can be maximized in closed form (counting, as in the Hidden Layer lesson), and the resulting score reveals why likelihood alone cannot choose a structure.
Plug the maximum-likelihood CPTs into the log-likelihood, and write for the empirical distribution:
Since , the score is a sum of empirical mutual informations between each node and its parents, minus entropies that do not depend on :
Mutual information never decreases when a variable is added, , so adding an edge never lowers . Maximum likelihood always prefers a complete DAG, a pure overfit:
Two remedies penalize complexity. The BIC score subtracts half a log-sample-size per free parameter, ; it is the large-sample approximation of the Bayesian score (Schwarz, 1978):
The Bayesian score is the marginal likelihood itself. With independent Dirichlet priors on each CPT column it has a closed form (Cooper & Herskovits, 1992; Heckerman, Geiger & Chickering, 1995), where counts records with in state and its parents in configuration :
The BDeu choice , with an equivalent sample size , is score equivalent: Markov-equivalent DAGs get the same score, as they should, since no data can distinguish them. Both scores are decomposable (a sum of per-family terms, so a local change is rescored locally) and consistent: as , the top-scoring structures are, with probability tending to one, exactly the DAGs in the true equivalence class, assuming faithfulness.
With records, you consider adding a second binary parent to a binary node that already has one binary parent . By how much must the empirical conditional mutual information exceed zero for BIC to accept the edge?
- About nats
- About nats
- About nats
- About nats
Show the answer
D. About nats
The CPT grows from 2 to 4 free parameters, so the penalty rises by . The likelihood rises by , so the edge pays off when nats. The threshold shrinks like , so ever weaker dependences are detected as data grow.
Searching: trees are easy, everything else is hard
| Search method | Space | Guarantee |
|---|---|---|
| Greedy hill climbing (add, delete or reverse an edge), with tabu lists and restarts | DAGs | a local optimum |
| Greedy equivalence search, GES (Chickering, 2002) | equivalence classes | the true class in the large-sample limit, given a consistent score and faithfulness |
| Dynamic programming over subsets (Koivisto & Sood, 2004; Silander & Myllymäki, 2006) | orders | exact, in time: about 30 variables |
| Integer programming with cutting planes (Jaakkola et al., 2010; Cussens, 2011) | parent sets | exact with an optimality certificate, when parent sets are limited |
Constraint-based learning: the PC algorithm
The PC algorithm (Spirtes & Glymour, 1991) uses the facts proved in d-Separation & Independence: adjacent nodes are never d-separated, non-adjacent nodes are d-separated by a subset of either one's neighbors, and an unshielded triple is a collider exactly when its middle node is absent from the separating sets. It needs only conditional-independence tests.
function PC(variables V, test CI(X, Y | S)):
G ← complete undirected graph on V; ℓ ← 0
repeat # phase 1: skeleton
for each adjacent pair X — Y in G:
for each S ⊆ adj(X) − {Y} with |S| = ℓ:
if CI(X, Y | S):
remove X — Y; sepset(X, Y) ← S; break
ℓ ← ℓ + 1
until |adj(X) − {Y}| < ℓ for every adjacent pair X — Y
for each X — Z — Y with X, Y not adjacent: # phase 2: v-structures
if Z ∉ sepset(X, Y): orient X → Z ← Y
repeat Meek's rules until nothing changes # phase 3: compelled edges
return G # the essential graph (CPDAG)Meek's first rule orients whenever with and not adjacent; three rules suffice without background knowledge (Meek, 1995). With a perfect independence oracle, faithfulness and no hidden common causes, PC returns exactly the essential graph of the true DAG, using at most tests when the maximum degree is : polynomial for sparse graphs.
PC, run on data from the sprinkler network, returns its essential graph: Cloudy — Sprinkler, Cloudy — Rain undirected, and Sprinkler → WetGrass ← Rain. How many DAGs does this graph represent?
- 1
- 3
- 4
- 2
Show the answer
B. 3
Orienting the two undirected edges gives four candidates. Sprinkler → Cloudy ← Rain would create a new v-structure (Sprinkler and Rain are not adjacent), so it is excluded; the other three (Cloudy as a common cause, or either chain through Cloudy) are acyclic, have the same v-structures, and are all equivalent.
In finite samples, a wrong test early on deletes an edge for good and can trigger wrong orientations downstream, and the output can depend on the order in which pairs are tested; order-independent variants fix the latter (Colombo & Maathuis, 2014). For sparse, high-dimensional Gaussian models PC is uniformly consistent under a strengthened faithfulness assumption (Kalisch & Bühlmann, 2007). With hidden common causes, the FCI algorithm returns a partial ancestral graph instead.
Beyond Markov equivalence
Markov equivalence is the limit for nonparametric observational data, and for linear models with Gaussian noise. Extra assumptions break the symmetry:
- Non-Gaussian noise. In a linear model with independent, non-Gaussian noise, the full DAG is identifiable (LiNGAM; Shimizu et al., 2006), by independent component analysis.
- Nonlinear additive noise. If with , then generically no model of the same form exists in the backward direction, so even two variables can be oriented (Hoyer et al., 2009).
- Equal noise variances. Linear Gaussian models whose noises all have the same variance are identifiable too (Peters & Bühlmann, 2014).
- Interventions. Data from experiments split equivalence classes further (Hauser & Bühlmann, 2012).
A recent line of work replaces combinatorial search with continuous optimization. NOTEARS (Zheng et al., 2018) characterizes acyclicity of a weighted adjacency matrix by a smooth equation, and fits by minimizing a loss subject to it:
It works because sums the weights of closed walks of length , so vanishes exactly when there are no cycles.
Key takeaways
- The maximized log-likelihood of a DAG is minus a constant, so it always prefers more edges. BIC subtracts per parameter; the Bayesian Dirichlet score has a closed form, and BDeu is score equivalent. Both are decomposable and consistent.
- Chow–Liu finds the maximum-likelihood tree as a maximum spanning tree on mutual information. With two or more parents per node, structure search is NP-hard (Chickering, 1996), so practice uses local search, GES or exact methods for small .
- PC builds the skeleton from independence tests, orients v-structures from the separating sets and applies Meek's rules; with a perfect oracle, faithfulness and no hidden confounders it returns the essential graph (three DAGs for the sprinkler network).
- Beyond Markov equivalence, identifiability needs extra assumptions: non-Gaussian or additive noise, equal variances or interventions. Results that change under rescaling of the variables signal hidden assumptions.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why does maximizing the likelihood over structures, with no penalty, always select a complete DAG?
- Because real data are always generated by complete DAGs
- Because the likelihood score is minus a constant, and adding a parent never decreases mutual information
- Because complete DAGs have the fewest parameters
- Because the BDeu prior favors dense graphs
Show the answer
B. Because the likelihood score is minus a constant, and adding a parent never decreases mutual information
, and in finite samples the empirical conditional mutual information is almost always strictly positive, even when the true one is zero.
In the Chow–Liu algorithm, what are the edge weights of the spanning-tree problem, and why does the orientation of the resulting tree not matter?
- Correlation coefficients; trees have no directions
- Conditional mutual informations given all other variables; orientation is fixed by the data
- BIC scores; the root is chosen by the largest entropy
- Empirical mutual informations; all orientations of a tree without v-structures are Markov equivalent and have the same likelihood
Show the answer
D. Empirical mutual informations; all orientations of a tree without v-structures are Markov equivalent and have the same likelihood
The likelihood of a tree decomposes into minus entropies. Every rooting gives each non-root node one parent, the same skeleton and no v-structures, so all rootings are equivalent.
PC removed the edge with . Both and remain adjacent to , and . How does phase 2 orient the triple?
- It stays undirected
Show the answer
A.
is unshielded and is not in the set that separated and . If were a chain or fork node, every separating set would have to contain it; so is a collider.
Two variables follow with . In which case can observational data alone tell from ?
- When and are Gaussian
- Never: two variables are always Markov equivalent in both directions
- When and are non-Gaussian
- Only when is larger than 1
Show the answer
C. When and are non-Gaussian
With non-Gaussian independent components, the backward regression residual is not independent of , so only one direction admits an independent-noise linear model (LiNGAM). In the Gaussian case both directions fit equally well.
Further reading
- D. M. Chickering, "Learning Bayesian networks is NP-complete," in Learning from Data: Artificial Intelligence and Statistics V (Springer, 1996).
- D. Heckerman, D. Geiger & D. M. Chickering, "Learning Bayesian networks: The combination of knowledge and statistical data," Machine Learning 20(3), 197–243 (1995).
- C. K. Chow & C. N. Liu, "Approximating discrete probability distributions with dependence trees," IEEE Transactions on Information Theory 14(3), 462–467 (1968).
- D. M. Chickering, "Optimal structure identification with greedy search," Journal of Machine Learning Research 3, 507–554 (2002).
- P. Spirtes, C. Glymour & R. Scheines, Causation, Prediction, and Search, 2nd ed. (MIT Press, 2000).