§19.0–19.4Inference as Optimization · EM · MAP Inference · Variational Inference

§19.0 The other intractability

Chapter 18 fought the intractable partition function — the negative phase. This chapter fights the intractable posterior $p(\boldsymbol{h}\mid\boldsymbol{v})$ — the hard positive phase. Computing $p(\boldsymbol{h}\mid\boldsymbol{v})$, or expectations under it, is needed for maximum-likelihood learning but costs exponential time for most multi-layer models. The culprit is latent-variable interaction (fig 19.1):

Some models (an RBM, probabilistic PCA) do have a tractable $p(\boldsymbol{h}\mid\boldsymbol{v})$ — but most, including single-layer sparse coding, do not. Approximate inference approximate inference Techniques for the intractable posterior p(h|v) (or expectations under it) needed for learning; usually cast as approximately maximizing a lower bound on log p(v). defined in ch. 19 — open in glossary handles the rest.

§19.1 Inference is optimization

The unifying trick: bound $\log p(\boldsymbol{v})$ below by the evidence lower bound evidence lower bound (elbo) L(v,θ,q) = log p(v) − D_KL(q(h|v)‖p(h|v)) = E_{h∼q}[log p(h,v)] + H(q): a tractable lower bound on log p(v), tight iff q = p(h|v). Inference = maximize it over q. defined in ch. 19 — open in glossary (ELBO), also called the negative variational free energy variational free energy The negative of the ELBO; the 'free energy' name from statistical physics for the same quantity. defined in ch. 19 — open in glossary :

The magic is that $\mathcal{L}$ rearranges (eqs 19.2–19.6) into a form with no intractable posterior in it:

So inference = find the $q$ that maximizes $\mathcal{L}$. Exact inference searches a family rich enough to contain $p(\boldsymbol{h}\mid\boldsymbol{v})$; approximate inference either restricts the family or optimizes imperfectly. Drive the bound yourself — as $q$ approaches the posterior, the gap closes:

§19.2 Expectation maximization

EM is the classic algorithm built on this bound — coordinate ascent on $\mathcal{L}$, alternating which argument it climbs:

EM expectation maximization (em) Coordinate ascent on the ELBO: E-step sets q to the exact posterior at the current θ; M-step maximizes L over θ with q fixed. Learning with an approximate posterior, not approximate inference. defined in ch. 19 — open in glossary is learning with an approximate posterior, not approximate inference — the E-step e-step The expectation step of EM: set q(h|v) = p(h|v; θ⁰) using the current parameters (exact inference), making the ELBO tight. defined in ch. 19 — open in glossary is exact. Its signature move is reusing one $q$ across a big M-step m-step The maximization step of EM: maximize Σ L(v⁽ⁱ⁾,θ,q) over θ holding q fixed (possibly a large or analytic step). defined in ch. 19 — open in glossary jump in $\boldsymbol{\theta}$; in deep learning, posteriors are usually too complex for large analytic M-steps, so plain SGD (EM with a one-step M) is the norm.

§19.3 MAP inference and sparse coding

Instead of the whole posterior, compute only its peak — the single most likely latent value:

MAP inference map inference Compute the single most likely latent value h* = argmax_h p(h|v) instead of the whole posterior; equivalent to restricting q to a Dirac δ(h−µ) in the ELBO. The workhorse for sparse coding. defined in ch. 19 — open in glossary is exact-argmax, but as a source of $q$ it is approximate — a point instead of the true posterior. It is the engine of sparse coding (§13.4): a factorial Laplace prior plus Gaussian $p(\boldsymbol{v}\mid\boldsymbol{h})$ gives an intractable $p(\boldsymbol{h}\mid\boldsymbol{v})$ (every $h_i, h_j$ are co-parents of $\boldsymbol{v}$ → one giant clique under explaining away), so we learn by alternating MAP inference of $\boldsymbol{h}$ and a gradient step on $\boldsymbol{\theta}$, minimizing:

§19.4 Variational inference — and which KL

Variational inference maximizes $\mathcal{L}$ over a restricted family of $q$. The mean field mean field The variational approximation with a fully factorial q(h|v) = Πᵢ q(hᵢ|v); each latent is independent given v. defined in ch. 19 — open in glossary choice makes $q$ fully factorial, $q(\boldsymbol{h}\mid\boldsymbol{v}) = \prod_i q(h_i\mid\boldsymbol{v})$ (eq 19.17); structured variational inference structured variational inference Variational inference with any chosen graphical-model structure on q (richer than mean field's full factorization). defined in ch. 19 — open in glossary allows any chosen graph on $q$. The elegance: you specify only how $q$ factorizes — the optimization derives its optimal functional form.

Variational inference variational inference Maximize the ELBO over a RESTRICTED family of q (specifying only how q factorizes); the optimization derives q's optimal form. Minimizes the reverse KL D_KL(q‖p). defined in ch. 19 — open in glossary uses the reverse KL, so a simple $q$ fit to a multimodal posterior picks one mode and ignores the rest (fig 3.6). See both directions on a bimodal target:

Next: making this concrete for discrete latent variables — the mean-field fixed-point equations and binary sparse coding.