Bayesian Networks: Structure Learning

Learning the structure of a Bayesian Network (BN) from data is a fundamental, yet challenging, task in probabilistic modeling. Unlike parameter learning, where we assume the conditional dependencies (the graph structure) are known and aim to estimate the parameters of the Conditional Probability Distributions (CPDs), structure learning attempts to discover these dependencies directly from observations. This process aims to find a Directed Acyclic Graph (DAG) $G$ that best represents the dependencies present in a dataset $D$.

The core idea is to identify which variables directly influence others, forming the directed edges of the graph. This is distinct from simply finding correlations; structure learning seeks conditional independencies, which are more informative about the underlying data generating process. However, inferring causality solely from observational data is often impossible without further assumptions or interventional data. Structure learning typically identifies structures within the same Markov equivalence class, meaning graphs that encode the same set of conditional independencies.

Why Learn Structure?

In many scenarios, the true dependency structure among variables isn't known beforehand. Domain expertise might provide some prior knowledge, but data-driven structure discovery can:

1. Reveal unexpected relationships: Automatically identify dependencies that might not be obvious to experts.
2. Adapt models to data: Build models that are tailored to the specific patterns observed in a dataset.
3. Provide insights: The learned graph structure itself can be a valuable output, offering a qualitative understanding of the system being modeled.

The Challenge of Structure Learning

Discovering the optimal graph structure is computationally hard. The number of possible DAGs grows super-exponentially with the number of variables $n$. Specifically, the number of DAGs $f(n)$ satisfies the recurrence:

$$f(n) = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} 2^{k(n-k)} f(n-k)$$

This combinatorial explosion makes exhaustive search infeasible for all but the smallest networks (e.g., $n > 5$). Therefore, practical structure learning relies on heuristic search strategies or methods based on conditional independence tests.

Major Approaches to Structure Learning

Two primary families of algorithms dominate BN structure learning:

1. Constraint-Based Methods

These methods work by performing statistical tests of conditional independence (CI) on the data. They try to identify pairs of variables $(X, Y)$ that are independent given a set of other variables $S$, denoted as $(X \perp Y | S)$. The pattern of observed independencies constrains the possible graph structures.

A common CI test for discrete data is the Chi-squared ($\chi^2$) test or the G-test (likelihood ratio test). For continuous data assuming Gaussian distributions, tests based on partial correlation can be used.

Example Algorithm: PC Algorithm (Peter-Clark)

The PC algorithm is a well-known constraint-based method. It starts with a fully connected undirected graph and iteratively removes edges based on CI tests of increasing order (conditioning set size).

1. Initialization: Start with a complete undirected graph connecting all variables.
2. Edge Removal:
   • For each pair of variables $(X, Y)$ connected by an edge, test if $(X \perp Y)$. If true, remove the edge.
   • For each pair $(X, Y)$ still connected, test if $(X \perp Y | Z)$ for all single neighbors $Z$. If true for any $Z$, remove the edge.
   • Continue increasing the size of the conditioning set $S$ (e.g., $|S|=2, 3, \dots$) and test $(X \perp Y | S)$ for adjacent $X, Y$. Remove the edge if independence is found.
3. Orientation: Orient edges based on the discovered separation sets (the $S$ that made $X, Y$ independent) to avoid creating new v-structures ($X \rightarrow Z \leftarrow Y$) unless required by the independencies. Further orientation rules are applied to ensure acyclicity and consistency.

Limitations:

• Data Intensive: CI tests require substantial data to be reliable, especially with large conditioning sets.
• Test Sensitivity: Results can be sensitive to the choice of CI test and the significance threshold ($\alpha$) used. Errors in early tests (small conditioning sets) can propagate.
• Faithfulness Assumption: These methods assume the true distribution is faithful to some DAG, meaning all observed independencies are implied by the graph structure and vice-versa.

2. Score-Based Methods

These methods frame structure learning as an optimization problem. A scoring function $Score(G, D)$ is defined, which measures how well a candidate graph structure $G$ fits the observed data $D$. The goal is to find the graph $G^*$ that maximizes this score.

$$G^* = \arg \max_{G \in \mathcal{G}} Score(G, D)$$

Where $\mathcal{G}$ is the space of all possible DAGs. Since exhaustive search is intractable, heuristic search algorithms are employed:

• Greedy Hill-Climbing: Start with an initial graph (e.g., empty or random). Iteratively make local changes (add, delete, or reverse a single edge) that yield the largest increase in the score, ensuring acyclicity. Stop when no local change improves the score. Prone to local optima.
• Tabu Search: A metaheuristic that enhances hill-climbing by keeping a "tabu list" of recently visited structures or moves to avoid cycles and escape local optima.
• Simulated Annealing: A probabilistic optimization technique that allows moves that decrease the score with a certain probability, decreasing over time, helping to escape local optima.
• Genetic Algorithms: Maintain a population of candidate structures, using operators like crossover and mutation to evolve towards higher-scoring graphs.

Common Scoring Functions:

• Bayesian Information Criterion (BIC): A penalized likelihood score that trades off model fit with complexity. $$Score_{BIC}(G, D) = \log P(D | \hat{\theta}_G, G) - \frac{\text{dim}(G)}{2} \log N$$ Where $\hat{\theta}_G$ are the maximum likelihood parameters for graph $G$, $\text{dim}(G)$ is the number of independent parameters in the model, and $N$ is the number of data points. BIC is computationally efficient and consistent (finds the true structure asymptotically).
• Akaike Information Criterion (AIC): Similar to BIC but with a different penalty term. $$Score_{AIC}(G, D) = \log P(D | \hat{\theta}_G, G) - \text{dim}(G)$$
• Bayesian Scores (e.g., BDeu - Bayesian Dirichlet equivalent uniform): These scores compute the marginal likelihood $P(D | G) = \int P(D | \theta_G, G) P(\theta_G | G) d\theta_G$, integrating out the parameters $\theta_G$. This naturally incorporates a penalty for complexity and aligns well with the Bayesian framework. Calculating the marginal likelihood is often feasible if using conjugate priors (like Dirichlet priors for multinomial variables). The BDeu score makes assumptions about prior parameter equivalence and uniformity.

Example: Greedy Hill-Climbing Visualization

Imagine the search space where height represents the score. Hill-climbing starts at one point and always moves uphill.

An illustration of greedy hill-climbing search. Starting from an initial graph (red circle), the algorithm follows score improvements (blue dashed arrows) until it reaches a local optimum (red filled circle), where no single edge change improves the score. The global optimum (green double circle) might be missed.

Advantages & Disadvantages:

• Flexibility: Can incorporate prior knowledge easily via the initial graph or score penalties.
• Global Perspective: Scores evaluate the entire graph structure.
• Local Optima: Heuristic search methods can get stuck in suboptimal solutions.
• Computational Cost: Evaluating scores and searching the space can still be computationally demanding, though often more scalable than constraint-based methods for dense graphs.

3. Hybrid Methods

These approaches combine constraint-based and score-based techniques to leverage their respective strengths. For example, a constraint-based method might be used initially to prune the search space by identifying definite independencies (removing edges), followed by a score-based search within the restricted space.

Bayesian Structure Learning

A fully Bayesian approach treats the graph structure $G$ itself as a random variable with a prior distribution $P(G)$. The goal is then to compute the posterior distribution over structures given the data:

$$P(G | D) = \frac{P(D | G) P(G)}{P(D)} = \frac{P(D | G) P(G)}{\sum_{G' \in \mathcal{G}} P(D | G') P(G')}$$

Here, $P(D | G)$ is the marginal likelihood used in score-based methods (often the Bayesian score). $P(G)$ allows encoding prior beliefs about structures (e.g., penalizing dense graphs).

Computing the full posterior $P(G | D)$ is usually intractable due to the normalization constant $P(D)$, which requires summing over all possible DAGs. Common strategies include:

• Finding the Maximum a Posteriori (MAP) structure: $G_{MAP} = \arg \max_G P(G | D)$, which is equivalent to maximizing $P(D | G) P(G)$. This is often tackled using score-based search heuristics.
• Bayesian Model Averaging: Instead of selecting a single best graph, average predictions over multiple high-scoring graphs, weighted by their posterior probabilities. This can be approximated using MCMC methods (like Markov Chain Monte Carlo over structures) to sample graphs from the posterior $P(G | D)$.

Practical Notes

• Equivalent Structures: Observational data alone cannot distinguish between graphs in the same Markov equivalence class. For example, $X \rightarrow Y$ and $X \leftarrow Y$ are statistically indistinguishable without further information. Learned structures often represent the equivalence class.
• Latent Variables: The presence of unobserved (latent) variables can induce spurious dependencies between observed variables, complicating structure learning.
• Data Quality: Missing data and noise significantly impact the reliability of learned structures.
• Evaluation: Assessing the quality of a learned structure is non-trivial. Metrics include comparing against a known ground truth (in simulations), evaluating the likelihood of hold-out data, or assessing the structural difference (e.g., Structural Hamming Distance) from a reference graph.

Structure learning remains an active area of research, particularly concerning scalability, handling mixed data types, incorporating causal assumptions, and dealing with latent variables. While challenging, the ability to learn network structures from data provides a powerful tool for understanding complex systems and building adaptive probabilistic models.