Bayesian Networks and Graphical Models

A joint probability distribution over n binary variables requires, in the worst case, 2^n − 1 numbers to specify - a table that becomes unmanageable well before n reaches even a few dozen. Graphical models solve this by exploiting conditional independence: most variables in a realistic domain do not interact directly with most other variables, and encoding exactly which variables do interact lets the joint distribution be rebuilt from a product of much smaller local pieces. A Bayesian network represents this structure as a directed acyclic graph (DAG) in which each node is a random variable and each node's conditional probability distribution is defined only in terms of its parents. This licenses the chain-rule factorization P(X1, ..., Xn) = the product over all i of P(Xi | parents(Xi)). A network with modest in-degree per node can therefore represent a joint distribution over many variables using a number of parameters that grows linearly rather than exponentially in n, while still capturing the dependencies that matter.

The graph's edges are not automatically causal claims - a Bayesian network is fundamentally a compact factorization of a joint distribution, and the same distribution can often be encoded, with different edge directions, by more than one DAG. What the structure does guarantee precisely is a set of conditional independence relationships, readable off the graph via a criterion called d-separation. One especially important pattern is the converging connection, or v-structure: two variables with no edge between them that share a common child. Judea Pearl's foundational analysis of belief networks showed that such variables, though marginally independent, become dependent once their shared child is observed - the "explaining away" effect, in which evidence for the effect makes each possible cause partially compete with the others as an explanation. This is a genuinely different independence pattern from the one produced by a chain or a diverging (common-cause) connection, and it is part of why directed graphs carry more structure than an edge list alone would suggest.

Undirected graphical models, or Markov random fields, represent a joint distribution differently: as a product of nonnegative potential functions defined over cliques (fully connected subsets) of an undirected graph, normalized by a partition function. They express symmetric interactions naturally - useful for domains like image pixels or spatial fields where there is no natural direction of influence - but cannot represent a v-structure's explaining-away pattern without additional machinery. Factor graphs, formalized by Kschischang, Frey, and Loeliger, unify both representations: a factor graph is a bipartite graph with variable nodes and factor nodes, where an edge connects a variable to every factor whose function depends on it. Any Bayesian network or Markov random field can be rewritten as a factor graph, and doing so matters because it is the substrate on which a single general-purpose message-passing algorithm, the sum-product algorithm, can perform inference - regardless of whether the original model was directed or undirected.

Building a graphical model is only useful if it supports answering queries: computing a marginal probability, or a conditional probability given some variables observed as evidence. Naively, this means summing the full joint distribution over every variable not of interest - exponential in the number of variables, exactly the problem the graph's structure was meant to avoid. Variable elimination exploits the graph's factorization instead: because the joint is a product of local factors, and because summation distributes over multiplication for any factor not involving the variable being summed out, marginalizing one variable at a time - eliminating it by multiplying together only the factors that mention it and then summing over its values - can be far cheaper than summing over the whole joint at once. The order in which variables are eliminated matters enormously: a good ordering keeps the intermediate factors small, while a bad one can recreate the exponential blow-up the method was meant to avoid. The size of the largest intermediate factor produced under the best possible elimination ordering defines the graph's treewidth, which turns out to be the fundamental quantity governing how hard exact inference on that structure can be.

For singly connected networks - polytrees, where there is at most one undirected path between any two nodes - Pearl showed that exact inference can be organized as local message passing between neighboring nodes, with each node combining messages arriving from its neighbors and passing updated messages onward to the neighbors it has not yet heard from. Because there are no loops, this belief propagation procedure converges in a number of steps proportional to the network's diameter and computes exact marginals everywhere, using computation that scales linearly rather than exponentially in the number of nodes. Each node's outgoing message summarizes everything that side of the network has to say about the node's possible values, so a node can compute its own posterior marginal simply by combining the incoming messages from every direction, without ever needing to reconstruct the full joint distribution. The elegance of the result is that a globally correct inference computation emerges from purely local, parallelizable updates - each node needs to know only what its immediate neighbors tell it, never the network's structure as a whole. This same message-passing logic reappears, in a more general form, as the sum-product algorithm operating on a cycle-free factor graph, of which Pearl's polytree propagation is a special case restricted to models expressed as Bayesian networks.

Most realistic networks are not singly connected, however, and belief propagation's simple convergence guarantee does not extend to networks with loops. The junction tree algorithm, introduced by Lauritzen and Spiegelhalter, restores exactness for arbitrary DAGs by first triangulating the graph and grouping variables into overlapping clusters (cliques), then arranging those clusters into a tree obeying the running intersection property, on which an analogous message-passing procedure computes exact marginals. The cost is that each clique's local computation scales exponentially in the number of variables within it, which is precisely why the network's treewidth - the size of its largest clique under an optimal triangulation - determines whether junction tree inference stays practical. Both belief propagation and the junction tree algorithm are, in fact, instances of the sum-product algorithm operating on the network's factor graph, one exact for cycle-free structures and the other exact after restructuring a looped graph into a cycle-free tree of clusters.

Treewidth is not a property a modeler gets to choose freely - it is a consequence of which variables the domain actually requires to interact, and many realistic domains (densely connected sensor networks, grid-structured image models, richly interacting biological or social systems) have treewidth far too large for junction tree inference to be practical, even though the algorithm remains exact in principle. Exact inference in general graphical models is, in the worst case, computationally intractable regardless of which exact algorithm is used, since the cost of any exact method is ultimately tied to the same underlying structural quantity. Adding more evidence, more variables, or denser interaction patterns to a model does not just make computation slower in a mild sense; it can push the required computation from feasible to utterly infeasible with no gradual middle ground. This reality motivates approximate inference: methods that deliberately trade exactness for tractability, aiming to compute a marginal or posterior that is close enough to correct to be genuinely useful, at a computational cost that does not explode as treewidth grows.

Two broad families dominate practice. Sampling-based methods are stochastic: they generate a sequence of samples from (or converging toward) the distribution of interest and estimate marginals from those samples' empirical frequencies, rather than computing any marginal in closed form. Gibbs sampling, applied by Geman and Geman to the problem of Bayesian image restoration via a simulated-annealing variant, exemplifies this approach in the graphical-model setting - it repeatedly resamples each variable from its full conditional distribution given the current values of all other variables, and under mild conditions this Markov chain's samples converge to the true joint distribution regardless of how large the network's treewidth is. Sampling methods are asymptotically exact - given enough samples, the answer is arbitrarily close to correct - but convergence can be slow and hard to diagnose in practice, and the variance of any finite-sample estimate is itself a real source of error that a practitioner has to account for when deciding how much computation to spend.

Variational methods take a different route: they are deterministic optimization procedures rather than stochastic simulations. Jordan, Ghahramani, Jaakkola, and Saul's synthesis of variational methods for graphical models frames approximate inference as choosing the member of some tractable family of distributions (for instance, one that assumes independence across variables, known as a mean-field approximation) that is closest to the true posterior, typically by minimizing a Kullback-Leibler divergence or, equivalently, maximizing a lower bound on the log-evidence. This produces a single deterministic answer, often quickly, but the answer inherits a systematic bias from whatever simplifying assumptions the chosen family makes - it is not asymptotically exact the way sampling is. The choice between these approaches, and increasingly between engineering systems that automate one or the other, is a running theme for the remainder of this domain: sequential state-space models often rely on sampling-based filters when they are not exactly solvable in closed form, and modern probabilistic programming systems typically default to one family or a hybrid of both depending on the scale of the model.