Probabilistic Graphical Model

A probabilistic graphical model (PGM) is a mathematical representation in which a graph expresses the factorization and conditional-independence structure of a probability distribution. Nodes usually denote random variables, while edges or factor nodes specify which variables interact directly in the chosen representation. The graph and its local probability functions together define a global distribution. This combination gives probability theory a structural language and gives graph algorithms access to probabilistic calculations.^[1][2]

PGM is an umbrella term, not a single model or inference procedure. It includes directed Bayesian networks, undirected Markov random fields, and bipartite factor graphs, as well as sequence, spatial, conditional, and hybrid models built from those representations. A Hidden Markov Model, for example, is a directed graphical model with repeated chain structure. A conditional random field is an undirected model of a conditional distribution. Factor graphs can express the factorizations behind both.^[1][8][17]

The framework separates three questions. Representation asks which joint or conditional distributions a graph can express. Inference asks for quantities such as marginal probabilities, conditional probabilities, likelihoods, or most probable assignments. Learning estimates local parameters, graph structure, or both from data. These questions are related: learning with unobserved variables usually calls an inference algorithm, and a representation that is compact may still make inference difficult.^[1][11]

The existing Bayesian network article covers directed acyclic models, d-separation, causal Bayesian networks, and Bayesian-network-specific algorithms in detail. This article treats Bayesian networks as one member of the larger PGM framework and concentrates on concepts shared across directed, undirected, and factorized representations.

Mathematical foundation

Let X = (X_1, ..., X_n) be a collection of random variables. A full joint distribution assigns a probability or density to every joint configuration x. A graphical model replaces an unstructured specification of that distribution with local pieces whose scopes are shown by a graph. When the graph is sparse and the local pieces are small, the representation may require far fewer parameters than a table over all joint configurations. Sparsity can also make inference easier, although it does not guarantee tractability.^[1][2]

Conditional independence

Conditional independence is the central semantic concept. Variables or sets of variables A and B are conditionally independent given C if, whenever the relevant conditional probabilities are defined,

p(a, b | c) = p(a | c) p(b | c).

The notation is often written as A ⟂ B | C. This is stronger than zero correlation and different from marginal independence. Conditioning may remove an association, create an association, or leave it unchanged, depending on the graph and the distribution.^[3][4]

A graph encodes a collection of such statements through a separation rule. In an undirected graph, if every path from a set A to a set B passes through C, then the global Markov property entails A ⟂ B | C. In a directed acyclic graph, ordinary path separation is replaced by d-separation because the direction of arrows changes how chains, forks, and colliders respond to conditioning.^[4][7]

The graph generally describes a family of distributions. A particular member of that family can have additional independencies not visible in the graph, for example because two parameter effects cancel. A graph that entails only valid independencies is called an independence map, or I-map, for the distribution. A perfect map captures the distribution's independencies exactly. Structure-learning and causal-discovery methods often use a faithfulness assumption, under which the distribution has no extra conditional independencies caused by special parameter values.^[1][3]

Local and global structure

The local Markov property describes a variable in relation to a neighborhood. In a Bayesian network, a node is conditionally independent of its nondescendants given its parents. In a Markov random field, a node is conditionally independent of all nonneighbors given its neighbors. A Markov blanket is a set that makes a variable independent of the remaining variables. For a DAG node, it consists of its parents, its children, and the other parents of its children. For an undirected node, its neighbors form a Markov blanket.^[1][3]

Local, pairwise, and global Markov properties are not interchangeable without conditions. For strictly positive distributions on an undirected graph, the Hammersley-Clifford theorem connects the global Markov property to factorization over graph cliques. If zeros are allowed, a distribution can satisfy graph-separation statements without admitting the corresponding positive clique-potential factorization. The positivity qualification is therefore part of the theorem, not a technical detail that can always be omitted.^[6][7]

Main representations

The common representations emphasize different aspects of the same modeling problem.

Scroll sideways for more →

Directed models

For a DAG G, each variable X_i has a set of parents pa(i). A Bayesian-network distribution factorizes as

p(x_1, ..., x_n) = product_i p(x_i | x_pa(i)).

Each local term is a normalized conditional distribution. The acyclic ordering makes the product globally normalized without a separate partition function. Directed edges specify the factorization and associated conditional-independence constraints. They do not, by themselves, establish causal effects. Causal interpretation requires additional assumptions about interventions, omitted common causes, and how the graph relates to the data-generating process.^[1][4]

Directed graphical models include Naive Bayes, hidden Markov models, state-space models, mixture models with latent assignment variables, and many hierarchical Bayesian models. Plate notation is often used to show repeated variables and factors without drawing every copy. These forms differ in their local distributions and repeated structure, but they retain the DAG product of conditionals.^[1]

Undirected models

A Markov random field uses an undirected graph G = (V, E). For a positive discrete distribution, a common parameterization is

p(x) = (1 / Z) product_C psi_C(x_C),
Z = sum_x product_C psi_C(x_C).

The scopes C may be maximal cliques or another collection of subsets compatible with the graph. Each potential psi_C is a nonnegative compatibility function. It need not be a marginal probability or a conditional probability. The partition function Z sums or integrates the unnormalized product over all configurations so that p is a valid distribution.^[3][6][7]

Undirected edges suit interactions without a natural ordering, such as neighboring image pixels, sites in a lattice, or mutually coupled binary variables. The Ising model, Gaussian graphical models, Boltzmann machines, and many spatial models fit this family. In a Gaussian graphical model, zeros in the precision matrix correspond to conditional-independence constraints under the multivariate normal model.^[3][11]

An undirected model can also define a conditional distribution. A conditional random field models p(y | x) with an undirected graph over output variables y and potential functions that may depend on observed inputs x. This permits rich features of the input without requiring a joint generative model for x. Lafferty, McCallum, and Pereira introduced CRFs for sequence segmentation and labeling in 2001, partly to avoid restrictive observation-independence assumptions in generative sequence models.^[17]

Factor graphs

A factor graph represents a product

f(x_1, ..., x_n) = product_a f_a(x_a)

as a bipartite graph. One node class represents variables and the other represents factors. A variable is connected to a factor when it appears in that factor's scope. If f is a normalized probability distribution, or an unnormalized distribution with a finite normalizer, the factor graph represents a PGM. Factor graphs can also represent indicator functions, transforms, and other nonprobability functions, so a factor graph is more general than a probabilistic model.^[8]

The factorization is not unique. A high-order factor can sometimes be split by introducing auxiliary variables, and several factors can be multiplied into one without changing the global function. The selected graph therefore records a computational decomposition as well as a statistical one. Kschischang, Frey, and Loeliger's 2001 tutorial showed how algorithms from coding, signal processing, and probabilistic inference can be written as instances of the same sum-product rule on suitable factor graphs.^[8]

Relations among representations

Directed, undirected, and factor-graph forms overlap, but they are not interchangeable without consequences. A fully connected DAG or undirected graph can represent any distribution in a finite discrete domain, given suitable parameters. Sparse graphs are more selective. Some conditional-independence structures have a compact DAG representation but no exact undirected representation on the same variables, while others favor an undirected graph.^[7]

A Bayesian network can be converted to an undirected form for inference by moralization: connect co-parents, discard arrow directions, and then triangulate when constructing a junction tree. These operations preserve a factorization usable by the inference algorithm but may add edges and hide some directed separation information. The resulting undirected graph should not be read as an exact restatement of every d-separation relation in the original DAG.^[7][9]

Both a Bayesian network and a Markov random field can be converted to factor-graph form by creating a factor node for each local conditional distribution or potential. This makes local computation explicit. The reverse operation is not always unique because factor scopes do not specify an arrow ordering, and different graphs can encode the same product.^[8]

Graphical equivalence is also distinct from parameter equivalence. Two DAGs can encode the same set of d-separation statements and belong to one Markov-equivalence class. Even then, their local conditional parameters have different forms. Likewise, multiplying an undirected potential by a function and compensating in another potential can leave the global distribution unchanged. Such nonuniqueness matters when parameters are interpreted rather than used only for prediction.^[1][3]

Inference

Inference computes properties of the distribution after the model structure and parameters have been specified. Let Q denote query variables, E observed evidence, and H the remaining hidden variables. A posterior marginal has the form

p(x_Q | x_E = e) =
    sum_x_H p(x_Q, x_H, e) / p(e).

Other common queries include the evidence likelihood p(e), the marginal p(x_Q), a maximum a posteriori assignment for selected variables, and a most probable joint configuration. Marginal and maximum queries use related graph operations but are not always interchangeable because summation and maximization obey different ordering rules.^[1][11]

Exact methods

Variable elimination repeatedly multiplies factors that contain a selected variable and then sums or maximizes that variable out. It is an application of the distributive law: calculations are performed on local factors instead of first constructing the full joint table. The elimination order determines the sizes of intermediate factors, so two orders on the same graph can have very different costs.^[1][11]

Belief propagation, also called sum-product message passing for marginal queries, sends local summaries between neighboring factors or clusters. On a cycle-free factor graph, a finite inward and outward pass computes exact marginals under the standard conditions. Chain-specific algorithms such as forward-backward and several filtering recursions are instances of this calculation.^[8]

For graphs with cycles, the junction-tree method first clusters variables into a tree whose nodes satisfy a running-intersection property. Message passing on that cluster tree is exact. Lauritzen and Spiegelhalter's 1988 scheme developed this local-computation approach for probabilistic expert systems, using operations commonly described as moralization, triangulation or filling in, and propagation over cliques.^[9]

Scroll sideways for more →

The width of the largest induced cluster, often summarized by treewidth, governs many exact discrete algorithms. A graph may contain many nodes and still permit efficient exact inference when its induced width and variable cardinalities are small. Conversely, a modest graph can be hard if elimination creates a large clique. Cooper proved in 1990 that probabilistic inference in general Bayesian networks is NP-hard, a worst-case result that motivates restricted graph families and approximate algorithms.^[10]

Approximate methods

Approximate inference is used when exact clusters or factors are too large. The main approaches make different compromises.

Markov Chain Monte Carlo constructs samples whose limiting distribution is the target. Gibbs sampling updates a variable or block from a conditional distribution, often using a Markov blanket. More general Metropolis-Hastings transitions can work when direct conditional sampling is unavailable. Monte Carlo estimates can be asymptotically consistent under appropriate conditions, but finite-run error, slow mixing, and convergence diagnosis remain practical issues.^[11]

Variational inference selects a tractable family q and turns inference into optimization, commonly by minimizing a divergence or maximizing an evidence lower bound. Mean-field methods use a strongly factorized q; structured methods retain selected dependencies. Variational procedures are deterministic once initialized and can be faster than sampling, but their approximation is restricted by the chosen family and objective.^[11][12]

Loopy belief propagation applies tree message updates directly to a graph with cycles. It has produced useful approximations in several domains, but ordinary loopy propagation need not converge, and a converged result need not equal the true marginals. Murphy, Weiss, and Jordan's 1999 study evaluated this behavior empirically rather than establishing a universal guarantee.^[13]

Approximate algorithms should be checked against exact calculations on smaller instances when possible. Other checks include multiple Monte Carlo chains, sensitivity to initialization, lower or upper bounds where available, and comparison among approximation families. A numerical result without an error assessment can conceal poor mixing, a bad variational family, or a message-passing fixed point far from the desired marginal.^[11][12]

Learning

Learning a PGM can mean estimating parameters for a fixed graph, selecting a graph, or placing a distribution over both. The difficulty depends on what is observed, whether the model is directed or undirected, and whether the chosen score requires inference.^[1]

Parameter learning

For a fully observed discrete Bayesian network with fixed structure, maximum likelihood estimation decomposes by node and parent configuration. Each conditional probability table can be estimated from the corresponding local counts. Conjugate priors, such as Dirichlet priors for multinomial conditional tables, permit local Bayesian updates as well. This decomposition follows from the product of normalized conditional distributions.^[1]

Hidden variables or missing entries couple the local problems. The Expectation-Maximization algorithm alternates between computing expectations of missing sufficient statistics under the current parameters and maximizing an expected complete-data log likelihood. Dempster, Laird, and Rubin established EM as a general maximum-likelihood procedure for incomplete data and proved its monotone likelihood behavior under the stated conditions. In a large graphical model, the expectation step can itself require approximate inference.^[14]

Undirected learning has a different obstacle. The partition function Z depends on all model parameters, so the log likelihood generally does not split into independent clique-level optimizations. Gradients in exponential-family Markov random fields involve expectations under the current global model. Exact likelihood learning can therefore be as difficult as inference. Approximate partition functions, Monte Carlo estimates, variational objectives, pseudolikelihood, and other surrogate criteria are used when exact normalization is unavailable.^[11]

Structure learning

Structure learning searches for an independence pattern supported by data and modeling assumptions. Score-based methods optimize a criterion that balances fit and complexity. Constraint-based methods test conditional independencies and seek a graph consistent with the test results. Hybrid methods restrict a score search using an estimated neighborhood or skeleton. Latent variables, selection effects, limited sample size, and multiple equivalent structures can make the result uncertain.^[1]

The unrestricted search space grows rapidly. Chickering proved NP-completeness for a defined Bayesian-network structure-learning decision problem using the BDe score even when each node has a bounded number of parents.^[15] This is a worst-case statement about that search problem, not a claim that all graph learning is intractable.

Restricted families can be tractable. The Chow-Liu method finds the tree-structured discrete distribution that minimizes information divergence from a target distribution by selecting a maximum-weight tree using pairwise mutual information. Applied to empirical data from a tree-dependence distribution, the procedure gives a maximum-likelihood estimate.^[16]

Undirected structure can be learned by selecting interactions or conditional-dependence terms, while directed structure requires both an adjacency pattern and an acyclic orientation. In either case, regularization or prior structure is often needed when the number of possible edges is large relative to the data. A learned edge reports what the fitted model retained under its assumptions; it does not automatically identify a physical mechanism or causal relation.^[1][3]

Applications

PGMs are used when variables have repeated, spatial, temporal, relational, or hierarchical structure and uncertainty must be propagated across that structure. The same application can admit several representations, chosen according to the queries and available algorithms.^[1][20][21]

Scroll sideways for more →

Geman and Geman's 1984 image-restoration work connected Gibbs distributions, local image interactions, and stochastic relaxation, helping establish MRF methods in image analysis.^[18] Lafferty, McCallum, and Pereira's 2001 CRF paper applied conditional graphical modeling to sequence segmentation and labeling.^[17] Friedman and colleagues used Bayesian-network learning to study dependencies in gene-expression measurements in 2000.^[19] In communication theory, factor graphs expose the local parity constraints that permit iterative sum-product decoding.^[8]

These examples do not imply that one graph family is tied to one field. Images can be modeled with directed latent-variable models, sequence models can be undirected or directed, and biological networks can use either. The modeling choice depends on whether the distribution is joint or conditional, whether interactions have a meaningful ordering, which variables are observed, and which inferences must be repeated.^[1][2]

Historical development

Graphical probability models grew from several lines of work rather than one invention. Statistical physics supplied Gibbs distributions for locally interacting systems. Spatial statistics and image analysis developed Markov random fields. Besag's 1974 paper connected conditional specifications, lattice interactions, and the Hammersley-Clifford theorem in a statistical treatment.^[3][6]

Darroch, Lauritzen, and Speed used the term graphical models for a class of log-linear contingency-table models in 1980 and showed how conditional-independence interpretations could be read from an undirected graph.^[5] During the 1980s, Pearl developed directed belief networks, d-separation, and local propagation methods for artificial intelligence.^[4] Lauritzen and Spiegelhalter then connected directed expert-system models to exact clique-based local computation in 1988.^[9]

The factor-graph view brought several message-passing traditions into a common notation. Kschischang, Frey, and Loeliger's 2001 tutorial related factor graphs to Tanner graphs and showed that forward-backward, Viterbi, Kalman filtering, Pearl belief propagation, and iterative decoding can all be expressed through product-and-marginalization messages on appropriate graphs.^[8]

Later work connected graphical models to exponential families, convex analysis, and variational optimization. Wainwright and Jordan's 2008 monograph organized these relationships around log partition functions, marginal sets, and variational representations, providing a common mathematical account of inference and learning in many directed and undirected models.^[11]

Interpretation and limitations

A PGM makes assumptions visible, but visibility does not make those assumptions true. Missing edges encode conditional-independence restrictions within the selected graph semantics. Data may violate them, hidden variables may induce dependencies among observed variables, and a graph learned from one population may not describe another. Model checking should therefore examine predictive behavior, relevant conditional relationships, and the fitted graph.^[1][3]

Computational gains also depend on structure. A compact list of local factors can still produce large intermediate factors, an intractable partition function, or a slowly mixing sampler. Approximate inference adds another modeling layer because its result depends on an approximation family, transition kernel, schedule, or initialization.^[10][11]

Direction and causation must be kept separate. A DAG can encode an observational factorization without being a causal model. Interventional claims need assumptions and semantics beyond ordinary probabilistic factorization, as discussed in causal inference. Likewise, an undirected edge is a compatibility relation under a model, not a statement that two variables exert symmetric physical forces on each other.^[1][4]

PGMs remain a general language within machine learning because they identify which variables interact, which independencies are assumed, and which local computations can be reused. The underlying questions of factorization, independence, normalization, inference, and learning remain the same across specific model families.^[1][11]

References

1. ^Koller, Daphne, and Nir Friedman. *Probabilistic Graphical Models: Principles and Techniques*. MIT Press, 2009. MIT Press.
2. ^Koller, Daphne, Nir Friedman, Lise Getoor, and Ben Taskar. *Graphical Models in a Nutshell*. In *Introduction to Statistical Relational Learning*, MIT Press, 2007. Stanford author PDF.
3. ^Lauritzen, Steffen L. *Graphical Models*. Oxford University Press, 1996. Oxford Academic.
4. ^Pearl, Judea. *Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference*. Morgan Kaufmann, 1988. Google Books bibliographic record.
5. ^Darroch, J. N., Steffen L. Lauritzen, and T. P. Speed. *Markov Fields and Log-Linear Interaction Models for Contingency Tables*. *The Annals of Statistics* 8(3), 1980, pp. 522-539. DOI.
6. ^Besag, Julian. *Spatial Interaction and the Statistical Analysis of Lattice Systems*. *Journal of the Royal Statistical Society, Series B* 36(2), 1974, pp. 192-225. DOI.
7. ^Massachusetts Institute of Technology. *6.438 Algorithms for Inference, Lecture 3: Undirected Graphical Models*. MIT OpenCourseWare, Fall 2014. Lecture PDF.
8. ^Kschischang, Frank R., Brendan J. Frey, and Hans-Andrea Loeliger. *Factor Graphs and the Sum-Product Algorithm*. *IEEE Transactions on Information Theory* 47(2), 2001, pp. 498-519. Author PDF.
9. ^Lauritzen, Steffen L., and David J. Spiegelhalter. *Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems*. *Journal of the Royal Statistical Society, Series B* 50(2), 1988, pp. 157-224. DOI.
10. ^Cooper, Gregory F. *The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks*. *Artificial Intelligence* 42(2-3), 1990, pp. 393-405. DOI.
11. ^Wainwright, Martin J., and Michael I. Jordan. *Graphical Models, Exponential Families, and Variational Inference*. *Foundations and Trends in Machine Learning* 1(1-2), 2008, pp. 1-305. UC Berkeley PDF.
12. ^Jordan, Michael I., Zoubin Ghahramani, Tommi S. Jaakkola, and Lawrence K. Saul. *An Introduction to Variational Methods for Graphical Models*. *Machine Learning* 37(2), 1999, pp. 183-233. DOI.
13. ^Murphy, Kevin P., Yair Weiss, and Michael I. Jordan. *Loopy Belief Propagation for Approximate Inference: An Empirical Study*. In *Proceedings of UAI 1999*, pp. 467-475. Hebrew University research record.
14. ^Dempster, A. P., N. M. Laird, and D. B. Rubin. *Maximum Likelihood from Incomplete Data via the EM Algorithm*. *Journal of the Royal Statistical Society, Series B* 39(1), 1977, pp. 1-22. DOI.
15. ^Chickering, David Maxwell. *Learning Bayesian Networks is NP-Complete*. In *Learning from Data: Artificial Intelligence and Statistics V*, 1996, pp. 121-130. Microsoft Research.
16. ^Chow, C. K., and C. N. Liu. *Approximating Discrete Probability Distributions with Dependence Trees*. *IEEE Transactions on Information Theory* 14(3), 1968, pp. 462-467. IBM Research.
17. ^Lafferty, John, Andrew McCallum, and Fernando C. N. Pereira. *Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data*. In *Proceedings of ICML 2001*, pp. 282-289. University of Pennsylvania repository.
18. ^Geman, Stuart, and Donald Geman. *Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images*. *IEEE Transactions on Pattern Analysis and Machine Intelligence* PAMI-6(6), 1984, pp. 721-741. Brown University author page.
19. ^Friedman, Nir, Michal Linial, Iftach Nachman, and Dana Pe'er. *Using Bayesian Networks to Analyze Expression Data*. *Journal of Computational Biology* 7(3-4), 2000, pp. 601-620. DOI.
20. ^Jordan, Michael I. *Graphical Models*. *Statistical Science* 19(1), 2004, pp. 140-155. DOI.
21. ^Stanford University. *CS228: Probabilistic Graphical Models*. 2017-2018 course materials. Course page.