Approximate Inference in Large PGMs

While exact inference algorithms like the Junction Tree provide precise answers for probabilistic queries in PGMs, they often hit a computational wall. For graphs with high treewidth (densely connected structures) or models involving many continuous variables without convenient conjugate relationships, the computational cost of exact inference becomes prohibitive. Calculating marginal or conditional probabilities like $P(X_i | E)$ or $P(X_i, X_j | E)$ can require summing or integrating over an exponentially large state space. This is particularly true for the large, complex graphical models frequently encountered in modern machine learning applications.

When exact inference is intractable, we turn to approximate inference strategies. These methods trade theoretical exactness for computational feasibility, aiming to provide sufficiently accurate estimates of the desired posterior probabilities or expectations. The two dominant families of approximate inference techniques, which you've encountered in earlier chapters, are Markov Chain Monte Carlo (MCMC) methods and Variational Inference (VI). Let's see how they are adapted for large PGMs.

MCMC Methods for PGMs

MCMC methods approximate the target posterior distribution $P(X | E)$ (where $X$ represents the set of all unobserved variables and $E$ is the observed evidence) by constructing a Markov chain whose stationary distribution is the target posterior. After a sufficient "burn-in" period, samples drawn from the chain can be treated as (correlated) samples from $P(X | E)$, allowing us to estimate posterior marginals, expectations, or other quantities of interest.

Gibbs Sampling in PGMs

Gibbs sampling is particularly well-suited for PGMs because it uses the conditional independence relationships encoded in the graph structure. Recall that Gibbs sampling iteratively samples each variable $X_i$ from its conditional distribution given the current state of all other variables, $P(X_i | X_{-i}, E)$.

A significant simplification arises from the PGM structure: a variable $X_i$ is conditionally independent of all other variables given its Markov Blanket, denoted $MB(X_i)$. The Markov Blanket consists of its parents, its children, and its children's other parents (sometimes called "spouses"). Therefore, the sampling step simplifies to drawing from:

$$P(X_i | X_{-i}, E) = P(X_i | MB(X_i), E)$$

This local computation makes Gibbs sampling efficient if sampling from $P(X_i | MB(X_i), E)$ is easy. This is often the case for discrete PGMs or models with conjugate priors.

The Markov Blanket of node $X_i$ (red) includes its parents ($P_1, P_2$), its children ($C_1, C_2$), and its children's other parents ($S_1, S_2$), all highlighted in yellow. For Gibbs sampling, we only need the values of these nodes to sample a new state for $X_i$.

Practical Considerations for MCMC in PGMs:

• Mixing: The sampler needs to explore the state space effectively. Poor mixing (high autocorrelation between samples) reduces the effective sample size. Techniques like blocking (sampling groups of variables together) can sometimes help.
• Convergence: Assessing when the chain has reached its stationary distribution is important (using diagnostics like trace plots and $\hat{R}$ discussed in Chapter 2).
• Computational Cost: Each Gibbs sweep requires sampling every variable once. The cost depends on the size of the Markov Blankets and the complexity of sampling from the local conditionals. For very large graphs or slow.mixing chains, MCMC can still be computationally demanding.
• Non-conjugacy: If the conditional $P(X_i | MB(X_i), E)$ is not a standard distribution we can easily sample from (e.g., in models with non-conjugate priors or complex likelihoods), we might need to embed other sampling methods like Metropolis.Hastings within the Gibbs sampler (Metropolis.within.Gibbs).

Variational Inference for PGMs

Variational Inference reframes inference as an optimization problem. Instead of sampling, VI seeks to find the distribution $Q(X)$ within a predefined family $\mathcal{Q}$ that best approximates the true posterior $P(X | E)$. "Best" is typically measured by minimizing the Kullback.Leibler (KL) divergence, $KL(Q(X) || P(X | E))$, which is equivalent to maximizing the Evidence Lower Bound (ELBO), as detailed in Chapter 3.

Mean-Field Variational Inference

The most common choice for the approximating family $\mathcal{Q}$ is the mean-field family, where the distribution $Q(X)$ factorizes completely over the individual variables (or sometimes groups of variables):

$$Q(X) = \prod_{i=1}^{N} Q_i(X_i)$$

This factorization assumes independence among the variables in the approximating distribution, even though they might be dependent in the true posterior. While this is a strong assumption and a source of approximation error, it leads to tractable optimization algorithms like Coordinate Ascent Variational Inference (CAVI).

Under the mean-field assumption, the optimal update for a single factor $Q_j^*(X_j)$ is given by:

$$\log Q_j^*(X_j) \propto \mathbb{E}_{Q_{-j}} [\log P(X, E)]$$

Here, $\mathbb{E}_{Q_{-j}}[\cdot]$ denotes the expectation taken with respect to all other factors $Q_i(X_i)$ for $i \neq j$. The term $\log P(X, E)$ is the log of the joint probability of all variables (hidden $X$ and observed $E$), which can be readily obtained from the PGM definition (product of conditional probability distributions or factors).

Crucially, because of the PGM structure, the expectation $\mathbb{E}_{Q_{-j}} [\log P(X, E)]$ often simplifies. The terms in $\log P(X, E)$ that involve $X_j$ typically only depend on $X_j$ and its neighbours in the graph. The expectation only needs to be computed over the factors $Q_k(X_k)$ corresponding to these neighbouring variables. CAVI iteratively updates each $Q_j^*(X_j)$ using this rule until the ELBO converges.

Practical Considerations for VI in PGMs:

• Speed: VI is often significantly faster than MCMC, especially for large datasets, as it replaces sampling with iterative optimization steps. Stochastic Variational Inference (SVI) can further scale VI to massive datasets by using stochastic gradient ascent on the ELBO.
• Bias: The mean-field assumption (or any restriction on the family $\mathcal{Q}$) introduces bias. VI approximations, particularly mean-field, are known to underestimate the variance of the posterior distribution and may fail to capture multimodality.
• Implementation Complexity: Deriving the mean-field update equations requires calculating the relevant expectations, which can be mathematically involved, although libraries often automate this for standard models. Black Box Variational Inference (BBVI) can alleviate this by using automatic differentiation and Monte Carlo estimates of gradients.
• Local Optima: The optimization process for the ELBO might converge to a local optimum, not necessarily the global optimum.

Choosing Between MCMC and VI for Large PGMs

The choice between MCMC and VI depends heavily on the specific problem, the structure of the PGM, the size of the data, and the requirements for accuracy versus speed.

• Use MCMC when:
  • Accuracy is critical, and you need guarantees of asymptotic exactness.
  • The computational budget allows for potentially long run times.
  • You need to capture complex posterior shapes, including multimodality and accurate variance estimates.
  • Gibbs sampling is applicable (easy conditional sampling).
• Use VI when:
  • Speed and scalability are major concerns, especially with very large datasets.
  • An approximation to the posterior is acceptable.
  • You primarily need point estimates (like posterior means) or a rough characterization of uncertainty.
  • Deriving or implementing MCMC samplers is overly complex for the model.

In many practical scenarios involving large PGMs, VI (especially SVI or BBVI) provides a valuable tool for obtaining reasonably good inference results within acceptable timeframes, even if it doesn't achieve the theoretical guarantees of MCMC. Understanding the trade-offs between these powerful approximate inference techniques allows you to select the most appropriate method for your specific modeling task.