Probabilistic graphical model

A probabilistic graphical model represents factorization and conditional-independence structure using a graph whose vertices are random variables.

A junction tree connects the maximal cliques of a chordal graph into a tree satisfying the running intersection property. Its edges carry separators equal to the intersections of the endpoint cliques. Assigning original factors to containing cliques permits exact sum-product belief propagation without summing independently over the entire collection of variables.

The junction tree algorithm performs exact inference in a finite probabilistic graphical model. First moralize a Bayesian network if necessary; then apply triangulation of an undirected graph, organize its maximal cliques into a junction tree, and assign each original factor to one containing clique. Inward and outward junction-tree sum-product messages compute the normalizing constant and marginal distributions. Its cost depends exponentially on the largest clique's number of variables, rather than necessarily on the total number of variables.

Assign each factor exactly once to a containing clique and multiply the factors there into ${\psi }_i$. The displayed sum-product belief propagation message sums out variables of $C_i$ outside the separator $S_{ij}=C_i\cap C_j$. By the running intersection property, eliminating all variables in the subtree on the $i$ side creates precisely this function of the separator. An inward pass computes the normalizing constant at the root; an outward pass produces marginal distributions. For pedigree likelihoods, observed genotypes and penetrance factors simply multiply the relevant potentials.

The running intersection property says that every variable belongs to a connected subtree of a junction tree. Equivalently, every clique along the path between two cliques contains their intersection. This ensures that eliminating variables on one side of a tree edge leaves a message depending only on its separator with the other side.

A Bayesian network consists of a Directed acyclic graph $G$ whose nodes are random variables, together with conditional distributions satisfying $p(x)={\prod }_{j}p(x_j\mid x_{{\mathrm{pa}}_G(j)})$. Its Directed acyclic graph encodes conditional independence constraints. For unrestricted binary variables it has ${\sum }_j{2}^{|{\mathrm{pa}}_G(j)|}$ free conditional probabilities. A Directed acyclic graph used this way need not have a causal interpretation.

For observations $\mathcal{D}$ and graph $G$, Bayes' theorem gives $p(G\mid \mathcal{D})\propto \pi (G)\int p(\mathcal{D}\mid {\theta }_G,G)\pi ({\theta }_G\mid G)d{\theta }_G$. Here $\pi (G)$ is the graph prior distribution and ${\theta }_G$ the local distribution statistical parameters. The integral is Bayesian model evidence; it averages over nuisance parameters with a proper statistical parameter prior distribution. For independent complete observations, the node-factorized likelihood function and independence of local statistical parameter prior distributions make the evidence factor over nodes; suitable conjugate priors can make the local integrals analytic. With missing node observations, integrating out unobserved values can couple the local parameters, so independence of local prior distributions alone does not guarantee this factorization. Proper priors and coherent hyperparameters matter for comparing different graphs.

A Gaussian Bayesian network specifies a linear normal conditional model at each node of a Bayesian network: $X_j\mid X_{\mathrm{pa}(j)}\sim N({\alpha }_j+{\gamma }_j^T{X}_{\mathrm{pa}(j)},{\sigma }_j^2)$. Independent local errors and an acyclic ordering generate a joint multivariate normal distribution. Positive conditional variances give a nonsingular joint multivariate normal distribution. The graph constrains regression coefficients and hence conditional independence.

Belief propagation passes local messages between factors or neighboring variables to compute marginal distributions or maximizing assignments. On a tree, two directed messages per edge give exact results in time linear in the number of vertices when state spaces are fixed.

The sum-product form of belief propagation sums over eliminated states in each message. On a tree it computes exact normalization constants and marginal distributions.

The max-product form of belief propagation replaces summation by maximization. On a tree, storing maximizing states while passing messages and then backtracking gives an exact maximum a posteriori estimate.

A Markov blanket of a variable is a set that makes it conditionally independent of every remaining variable. In a Directed acyclic graph, the parents, children, and other parents of the children form the standard Markov blanket.

Under faithfulness of a directed acyclic graph, every conditioning set screening a vertex from all remaining vertices contains its graphical Markov blanket. A missing adjacent vertex leaves a one-edge active path; a missing other parent of a child leaves the active path $k\to h\leftarrow u$, since the child $h$ is necessarily conditioned. Thus the graphical blanket is the unique smallest screening set.

In a Directed acyclic graph, let $B$ contain the parents, children, and other parents of children of vertex $k$. Then $k$ is D-separated from all remaining vertices by $B$. Every path out of $k$ meets a conditioned noncollider either at a parent, at a child, or at another parent just after a conditioned child-collider. The global Markov property for a directed acyclic graph gives $Z_k\perp Z_{(B\cup \{k\}{)}^c}\mid Z_B$.

A Markov random field is an undirected graphical model whose graph encodes conditional independence by vertex separation.

On a graph, a binary configuration has probability proportional to $\exp (\alpha {\sum }_v{x}_v+\beta {\sum }_{\{v,w\}}{x}_v{x}_w)$, with each edge counted once. The full conditional probability of a one is logistic with linear predictor $\alpha +\beta {\sum }_{w\sim v}{x}_w$. Local neighbor sums eliminate the need to evaluate the normalizing constant.

Independent unit-variance Gaussian observations with mean $x_v$ add $y_v-1/2$ to the local binary field. The posterior distribution conditional probability is $\mathrm{logistic}(\alpha +\beta z_v+y_v-1/2)$. The neighbor interaction is unchanged, so checkerboard conditional independence and the same Gibbs schemes remain valid.

A clique potential is a nonnegative function of the variables belonging to one clique. Products of clique potentials define the unnormalized density of a Markov random field.

The global Markov property says that graph separation of vertex sets $A$ and $B$ by $S$ implies conditional independence of the corresponding random vectors given the variables at $S$.