Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Learning Network Structure

Scores, search and causal discovery.

Ten variables admit about 4×10184\times10^{18} 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 G∗=arg max⁡Gscore(G:D)G^*=\argmax_G\mathrm{score}(G:\data). 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.

DerivationThe likelihood score in information-theoretic form
  1. ℓ(G:D)=∑i=1n∑xi,paiN(xi,pai)ln⁡N(xi,pai)N(pai)=−N∑i=1nH^(Xi∣Pai)\ell(G:\data)=\sum_{i=1}^n\sum_{x_i,\mathrm{pa}_i}N(x_i,\mathrm{pa}_i)\ln\frac{N(x_i,\mathrm{pa}_i)}{N(\mathrm{pa}_i)}=-N\sum_{i=1}^n\hat H(X_i\mid\mathrm{Pa}_i)

    Plug the maximum-likelihood CPTs θ^x∣pa=N(x,pa)/N(pa)\hat\theta_{x\mid\mathrm{pa}}=N(x,\mathrm{pa})/N(\mathrm{pa}) into the log-likelihood, and write P^\hat P for the empirical distribution:

  2. ℓ(G:D)=N∑i=1nI^(Xi;Pai)−N∑i=1nH^(Xi)\ell(G:\data)=N\sum_{i=1}^n\hat I(X_i;\mathrm{Pa}_i)-N\sum_{i=1}^n\hat H(X_i)

    Since H(X∣Y)=H(X)−I(X;Y)H(X\mid Y)=H(X)-I(X;Y), the score is a sum of empirical mutual informations between each node and its parents, minus entropies that do not depend on GG:

  3. I^(X;Y∣Pa)≥0⟹ℓ(G∪{Y→X}:D)≥ℓ(G:D)\hat I(X;Y\mid\mathrm{Pa})\ge0\quad\Longrightarrow\quad\ell(G\cup\{Y\to X\}:\data)\ge\ell(G:\data)

    Mutual information never decreases when a variable is added, I^(X;Pa∪{Y})=I^(X;Pa)+I^(X;Y∣Pa)\hat I(X;\mathrm{Pa}\cup\{Y\})=\hat I(X;\mathrm{Pa})+\hat I(X;Y\mid\mathrm{Pa}), so adding an edge never lowers ℓ\ell. 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, dim⁡G=∑i(ri−1)qi\dim G=\sum_i(r_i-1)q_i; it is the large-sample approximation of the Bayesian score (Schwarz, 1978):

BIC(G)=ℓ(G:D)−ln⁡N2dim⁡G.\mathrm{BIC}(G)=\ell(G:\data)-\frac{\ln N}{2}\dim G.

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 NijkN_{ijk} counts records with XiX_i in state kk and its parents in configuration jj:

P(D∣G)=∏i=1n∏j=1qiΓ(αij)Γ(αij+Nij)∏k=1riΓ(αijk+Nijk)Γ(αijk),αij=∑kαijk, Nij=∑kNijk.P(\data\mid G)=\prod_{i=1}^n\prod_{j=1}^{q_i}\frac{\Gamma(\alpha_{ij})}{\Gamma(\alpha_{ij}+N_{ij})}\prod_{k=1}^{r_i}\frac{\Gamma(\alpha_{ijk}+N_{ijk})}{\Gamma(\alpha_{ijk})},\qquad\alpha_{ij}=\sum_k\alpha_{ijk},\ N_{ij}=\sum_kN_{ijk}.

The BDeu choice αijk=α/(riqi)\alpha_{ijk}=\alpha/(r_iq_i), with an equivalent sample size α\alpha, 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 N→∞N\to\infty, the top-scoring structures are, with probability tending to one, exactly the DAGs in the true equivalence class, assuming faithfulness.

Check your understanding

With N=1000N=1000 records, you consider adding a second binary parent YY to a binary node XX that already has one binary parent PP. By how much must the empirical conditional mutual information I^(X;Y∣P)\hat I(X;Y\mid P) exceed zero for BIC to accept the edge?

  1. About 0.0020.002 nats
  2. About 6.96.9 nats
  3. About 0.690.69 nats
  4. About 0.00690.0069 nats
Show the answer

D. About 0.00690.0069 nats

The CPT grows from 2 to 4 free parameters, so the penalty rises by 2⋅ln⁡10002=ln⁡1000≈6.912\cdot\tfrac{\ln1000}{2}=\ln1000\approx6.91. The likelihood rises by N I^(X;Y∣P)N\,\hat I(X;Y\mid P), so the edge pays off when I^(X;Y∣P)>6.91/1000≈0.0069\hat I(X;Y\mid P)>6.91/1000\approx0.0069 nats. The threshold shrinks like (ln⁡N)/N(\ln N)/N, so ever weaker dependences are detected as data grow.

Searching: trees are easy, everything else is hard

Search methodSpaceGuarantee
Greedy hill climbing (add, delete or reverse an edge), with tabu lists and restartsDAGsa local optimum
Greedy equivalence search, GES (Chickering, 2002)equivalence classesthe true class in the large-sample limit, given a consistent score and faithfulness
Dynamic programming over subsets (Koivisto & Sood, 2004; Silander & Myllymäki, 2006)ordersexact, in O(n 2n)\order{n\,2^n} time: about 30 variables
Integer programming with cutting planes (Jaakkola et al., 2010; Cussens, 2011)parent setsexact with an optimality certificate, when parent sets are limited
The space is enormous: there are 543 DAGs on 4 nodes, 29,281 on 5, 3,781,503 on 6 and about 4.2×10184.2\times10^{18} on 10 (Robinson's recurrence). Decomposability is what makes local search affordable: a move changes one or two families, so only their terms are recomputed.

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.

text
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 B→CB\to C whenever A→B−CA\to B-C with AA and CC 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 n2(n−1)k−1/(k−1)!n^2(n-1)^{k-1}/(k-1)! tests when the maximum degree is kk: polynomial for sparse graphs.

Check your understanding

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. 1
  2. 3
  3. 4
  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 Xj=∑ibjiXi+εjX_j=\sum_{i}b_{ji}X_i+\varepsilon_j with independent, non-Gaussian noise, the full DAG is identifiable (LiNGAM; Shimizu et al., 2006), by independent component analysis.
  • Nonlinear additive noise. If Y=f(X)+εY=f(X)+\varepsilon with ε⊥ ⁣ ⁣ ⁣⊥X\varepsilon\indep X, 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 WW by a smooth equation, and fits WW by minimizing a loss subject to it:

h(W)=tr⁡(eW∘W)−d=0  ⟺  W is the adjacency matrix of a DAG.h(W)=\operatorname{tr}\big(e^{W\circ W}\big)-d=0\iff W\ \text{is the adjacency matrix of a DAG}.

It works because tr⁡((W∘W)k)\operatorname{tr}\big((W\circ W)^k\big) sums the weights of closed walks of length kk, so h(W)=∑k≥1tr⁡((W∘W)k)/k!h(W)=\sum_{k\ge1}\operatorname{tr}\big((W\circ W)^k\big)/k! vanishes exactly when there are no cycles.

Key takeaways

  • The maximized log-likelihood of a DAG is N∑iI^(Xi;Pai)N\sum_i\hat I(X_i;\mathrm{Pa}_i) minus a constant, so it always prefers more edges. BIC subtracts 12ln⁡N\tfrac12\ln N 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 nn.
  • 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.

Question 1

Why does maximizing the likelihood over structures, with no penalty, always select a complete DAG?

  1. Because real data are always generated by complete DAGs
  2. Because the likelihood score is N∑iI^(Xi;Pai)N\sum_i\hat I(X_i;\mathrm{Pa}_i) minus a constant, and adding a parent never decreases mutual information
  3. Because complete DAGs have the fewest parameters
  4. Because the BDeu prior favors dense graphs
Show the answer

B. Because the likelihood score is N∑iI^(Xi;Pai)N\sum_i\hat I(X_i;\mathrm{Pa}_i) minus a constant, and adding a parent never decreases mutual information

I^(X;Pa∪{Y})=I^(X;Pa)+I^(X;Y∣Pa)≥I^(X;Pa)\hat I(X;\mathrm{Pa}\cup\{Y\})=\hat I(X;\mathrm{Pa})+\hat I(X;Y\mid\mathrm{Pa})\ge\hat I(X;\mathrm{Pa}), and in finite samples the empirical conditional mutual information is almost always strictly positive, even when the true one is zero.

Question 2

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?

  1. Correlation coefficients; trees have no directions
  2. Conditional mutual informations given all other variables; orientation is fixed by the data
  3. BIC scores; the root is chosen by the largest entropy
  4. 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 N∑edgesI^(Xi;Xj)N\sum_{\text{edges}}\hat I(X_i;X_j) minus entropies. Every rooting gives each non-root node one parent, the same skeleton and no v-structures, so all rootings are equivalent.

Question 3

PC removed the edge X−YX-Y with sepset(X,Y)={W}\mathrm{sepset}(X,Y)=\{W\}. Both XX and YY remain adjacent to ZZ, and Z≠WZ\ne W. How does phase 2 orient the triple?

  1. X→Z←YX\to Z\leftarrow Y
  2. X←Z→YX\leftarrow Z\to Y
  3. X→Z→YX\to Z\to Y
  4. It stays undirected
Show the answer

A. X→Z←YX\to Z\leftarrow Y

X−Z−YX-Z-Y is unshielded and ZZ is not in the set that separated XX and YY. If ZZ were a chain or fork node, every separating set would have to contain it; so ZZ is a collider.

Question 4

Two variables follow Y=bX+εY=bX+\varepsilon with ε⊥ ⁣ ⁣ ⁣⊥X\varepsilon\indep X. In which case can observational data alone tell X→YX\to Y from Y→XY\to X?

  1. When XX and ε\varepsilon are Gaussian
  2. Never: two variables are always Markov equivalent in both directions
  3. When XX and ε\varepsilon are non-Gaussian
  4. Only when bb is larger than 1
Show the answer

C. When XX and ε\varepsilon are non-Gaussian

With non-Gaussian independent components, the backward regression residual is not independent of YY, 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).