Stanford AA228 Decision Making Under Uncertainty | Autumn 2025 | Bayesian Structure Learning

Key Concepts

• Bayesian Networks: Probabilistic graphical models that represent a joint probability distribution over a set of variables by encoding conditional independence assumptions.
• Conditional Independence: A relationship between random variables where knowing the value of one variable provides no additional information about another variable, given the value of a third variable.
• Parameter Learning: The process of estimating the conditional probability distributions (parameters) of a Bayesian network from data, assuming the network structure is known.
• Structure Learning: The process of discovering the network structure (the directed acyclic graph) of a Bayesian network from data.
• Maximum Likelihood Estimation (MLE): A method for estimating parameters by finding the values that maximize the probability of the observed data.
• Bayesian Parameter Learning: A method that infers a distribution over parameters rather than a point estimate, incorporating prior beliefs.
• Dirichlet Distribution: A probability distribution that generalizes the beta distribution to multiple categories, often used as a prior for categorical distributions.
• Pseudo-counts: Parameters of the Dirichlet distribution that represent prior observations or beliefs.
• Structure Scoring: A method to evaluate the quality of a Bayesian network structure by calculating its probability given the observed data.
• Bayesian Score: A common scoring function for Bayesian networks, derived from Bayesian parameter learning.
• K2 Algorithm: A greedy algorithm for structure learning that iteratively adds parents to nodes to maximize a scoring function, respecting a predefined node ordering.
• Local Search: A structure learning algorithm that starts with an initial graph and iteratively moves to neighboring graphs (by adding, removing, or reversing edges) that improve the score.
• Markov Equivalence: A property of Bayesian networks where two graphs encode the same set of conditional independence assumptions.

Bayesian Networks: Review and Introduction to Learning

This lecture continues the discussion on Bayesian networks, focusing on parameter learning and structure learning. The course has progressively relaxed assumptions: initially, both parameters and structure were known; then, parameters were learned from data with a known structure; and now, the focus shifts to learning structure from data.

Resources

• Textbook: "Algorithms for Decision Making" (closely follows the lecture).
• Coler and Friedman Textbook: For in-depth understanding of Bayesian networks and graphical models.
• Jack's Course Notes: Available at jammoka.com, providing summaries of salient topics.
• Project 1 Videos: On the course website, offering tips for getting started.

Review of Bayesian Networks

Bayesian networks compactly represent a joint distribution by encoding conditional independence assumptions.

Definition of Conditional Independence: X is conditionally independent from Y given Z if $P(X, Y | Z) = P(X | Z) * P(Y | Z)$. This means that once Z is known, knowing X provides no additional information about Y.

Example: Consider three binary variables:

• $X_1$: Raining
• $X_2$: Wearing rain boots
• $X_3$: Carrying an umbrella

A network structure where $X_1$ (Raining) is a parent of $X_2$ (Rain boots) and $X_3$ (Umbrella) implies that $X_2$ and $X_3$ are conditionally independent given $X_1$. This makes intuitive sense: if you know it's raining, knowing someone has an umbrella doesn't significantly change your belief about whether they are wearing rain boots. However, without knowing if it's raining, knowing they have an umbrella would be informative about their rain boots.

Notation

• $X_1, ..., X_n$: Discrete random variables in the Bayesian network.
• $R_{subi}$: The number of possible instantiations (values) of node $X_{subi}$. For binary variables, $R_{subi} = 2$.
• $Q_{subi}$: The number of parental instantiations of $X_{subi}$.
  • If $X_{subi}$ has no parents, $Q_{subi} = 1$.
  • If $X_{subi}$ has parents, $Q_{subi}$ is the product of the $R$ values of its parents.
• $\pi_j$: The $j$-th parental instantiation of the parents of $X_i$. The ordering of these instantiations is arbitrary but must be consistent.

Parameter Learning

Previously, parameters were assumed known for inference. Now, we learn them from data.

Parameters: $\theta_{i, j, k}$: The probability that $X_i = k$ given the $j$-th parental instantiation of $X_i$. The total number of parameters is $\sum_{i=1}^{n} R_i * Q_i$. The number of independent parameters is $\sum_{i=1}^{n} (R_i - 1) * Q_i$.

Example Parameter: $\theta_{3, 2, 2}$: Probability of carrying an umbrella (node 3, value 2, assuming 1=False, 2=True) given the second parental instantiation (e.g., it is raining, node 1, value 1).

Maximum Likelihood Estimation (MLE)

Goal: Find $\hat{\theta}$ that maximizes $P(\text{Data} | \theta, G)$, where $G$ is the known graph structure.

Notation: $M_{i, j, k}$: The number of times $X_i = k$ given the $j$-th parental instantiation in the observed data.

Likelihood of the data: $P(\text{Data} | \theta, G) = \prod_{i=1}^{n} \prod_{j=1}^{Q_i} \prod_{k=1}^{R_i} \theta_{i, j, k}^{M_{i, j, k}}$

MLE Solution: $\hat{\theta}{i, j, k} = \frac{M{i, j, k}}{\sum_{k'=1}^{R_i} M_{i, j, k'}}$

Drawbacks of MLE:

• Zero Counts: If a specific event (e.g., carrying an umbrella when it's raining) is not observed in the data ($M_{i, j, k} = 0$), MLE will assign a probability of 0, which might be an unrealistic model of the world.

Bayesian Parameter Learning

Goal: Infer a distribution over parameters, $P(\theta | \text{Data}, G)$. The optimal parameters $\hat{\theta}$ are those that maximize the posterior probability, $P(\theta | \text{Data}, G)$ (MAP estimate).

$P(\theta | \text{Data}, G) \propto P(\text{Data} | \theta, G) * P(\theta | G)$

Prior: We assume a Dirichlet distribution for the parameters of each node, $P(\theta_j | G) \sim \text{Dirichlet}(\alpha_j)$, where $\theta_j$ is the vector of parameters for node $i$ and its parental instantiation $j$. $\alpha_j$ are pseudo-counts.

Dirichlet Distribution:

• Generalizes the beta distribution to multiple categories.
• Parameterized by $\alpha = (\alpha_1, ..., \alpha_n)$, where $\alpha_i > 0$.
• $P(\theta | \alpha) \propto \prod_{i=1}^{n} \theta_i^{\alpha_i - 1}$
• The normalization constant involves gamma functions: $\frac{\Gamma(\sum \alpha_i)}{\prod \Gamma(\alpha_i)}$.

Posterior Distribution: If the prior is Dirichlet and the data is observed counts, the posterior is also Dirichlet. $P(\theta_j | \text{Data}, G) \sim \text{Dirichlet}(\alpha_j + M_j)$, where $M_j$ are the observed counts for that parental instantiation.

MAP Estimate (using Dirichlet prior): $\hat{\theta}{i, j, k} = \frac{\alpha{i, j, k} + M_{i, j, k}}{\sum_{k'=1}^{R_i} (\alpha_{i, j, k'} + M_{i, j, k'})}$

Interpretation of $\alpha$: Higher $\alpha$ values indicate stronger prior confidence. Uniform priors (e.g., $\alpha_i = 1$ for all $i$) represent weak confidence.

Example of updating pseudo-counts: If $\alpha = (2, 2, 2)$ and we observe data counts $M = (5, 2, 3)$, the posterior parameters are $(2+5, 2+2, 2+3) = (7, 4, 5)$.

Structure Learning

We need a way to score graph structures to compare them. The goal is to find the probability of a graph given the data, $P(G | \text{Data})$.

Using Bayes' Rule: $P(G | \text{Data}) \propto P(\text{Data} | G) * P(G)$

Marginal Likelihood $P(\text{Data} | G)$: This is obtained by integrating over all possible parameters $\theta$: $P(\text{Data} | G) = \int P(\text{Data} | \theta, G) P(\theta | G) d\theta$

Assuming a Dirichlet prior for parameters and that the data is i.i.d., this integral can be computed analytically.

Bayesian Score Formula: $P(G | \text{Data}) = P(G) * \prod_{i=1}^{n} \frac{\prod_{j=1}^{Q_i} \prod_{k=1}^{R_i} \Gamma(\alpha_{i, j, k} + M_{i, j, k})}{\Gamma(\sum_{k'=1}^{R_i} \alpha_{i, j, k'} + \sum_{k'=1}^{R_i} M_{i, j, k'})} / \frac{\prod_{j=1}^{Q_i} \prod_{k=1}^{R_i} \Gamma(\alpha_{i, j, k})}{\Gamma(\sum_{k'=1}^{R_i} \alpha_{i, j, k'})}$

Where:

• $P(G)$ is the prior probability of the graph structure.
• $\alpha_{i, j, k}$ are the prior pseudo-counts for node $i$, parental instantiation $j$, and value $k$.
• $M_{i, j, k}$ are the observed counts.

Log Score: For numerical stability and to convert products to sums, we use the log of the score. This involves using the log-gamma function, which is computationally efficient.

Impact of Data Size on Score: The Bayesian score balances model complexity and data.

• With little data, simpler (less connected) graphs tend to score higher because complex models are penalized.
• As data increases, more complex structures that are supported by the data become favored.

Structure Learning Algorithms

1. K2 Algorithm:

• Approach: Greedy search.
• Initialization: Starts with a completely unconnected graph.
• Process: Iterates through nodes in a predefined order. For each node, it greedily adds parents that maximally increase the Bayesian score, ensuring no cycles are introduced.
• Constraints: Enforces a node ordering, preventing cycles. Can also enforce a maximum number of parents per node to manage computational complexity.
• Limitations: Prone to local optima; the result depends heavily on the initial node ordering. Randomizing the ordering can help explore more structures.

2. Local Search:

• Approach: Iterative improvement.
• Initialization: Starts with an initial graph (can be unconnected or pre-defined).
• Neighborhood: Defines the neighborhood of a graph as all graphs reachable by a single basic graph operation: adding an edge, removing an edge, or reversing an edge.
• Process: Scores all neighbors (that don't introduce cycles) and moves to the highest-scoring neighbor. Repeats until no neighbor has a better score (local optimum).
• Dealing with Local Optima:
  • Randomized Restarts: Start the local search from multiple random initial graphs.
  • Simulated Annealing: Occasionally accepts moves to lower-scoring neighbors with a probability that decreases over time, allowing escape from local optima.
  • Genetic Algorithms: Maintains a population of graph structures, using selection, recombination, and mutation to evolve towards better solutions.

Markov Equivalence

Definition: Two directed acyclic graphs (DAGs) are Markov equivalent if they encode the same set of conditional independence assumptions.

Conditions for Markov Equivalence: Two DAGs are Markov equivalent if and only if they:

1. Have the same underlying undirected edges (i.e., the same skeleton).
2. Have the same "immoral V structures." An immoral V structure is a V-structure ($A \to C \leftarrow B$) where the parents ($A$ and $B$) are not connected by an edge.

Significance: The space of Markov equivalence classes is much smaller than the space of all DAGs. Searching over these classes can be computationally more efficient. However, graphs within the same Markov equivalence class might have different scores, though this difference can be mitigated by specific prior choices.

Cycle Detection: The lecture mentions that code for cycle detection is often provided, and a simple check for cycles involves ensuring that for any element $(i, j)$ in an adjacency matrix, the element $(j, i)$ is not also present (for directed edges). More complex cycles require more sophisticated algorithms.

Project 1 Notes:

• Implementing the score function is a recommended starting point.
• Consider enforcing constraints like a maximum number of parents for computational efficiency.
• For prior beliefs about graph structure, one can enforce certain edges to always be present or absent.
• The log-gamma function is crucial for implementing the score function.
• The Bayesian score naturally balances model complexity and data fit.
• Searching over Markov equivalence classes is an advanced optimization but not strictly required for passing project tests.