Tanner-Wong (1987) The Calculation of Posterior Distributions by Data Augmentation

Summary

This is the paper that introduced data augmentation for Bayesian computation. When the observed-data posterior $p(\theta\mid y)$ is intractable but the augmented-data posterior $p(\theta\mid y,z)$ (with latent data $z$ ) is simple, Tanner and Wong compute the observed-data posterior by an iterative, stochastic algorithm that alternates an Imputation step (draw latent data from the current predictive distribution) and a Posterior step (update the posterior as a mixture of augmented-data posteriors). The method is explicitly the Bayesian, distribution-valued analogue of the EM algorithm — where EM exploits the simplicity of the complete-data likelihood to find a mode, data augmentation exploits the simplicity of the complete-data posterior to recover the entire posterior. It is the direct precursor of the Gibbs sampler and of the modern latent-variable MCMC that pervades Bayesian econometrics. (Journal of the American Statistical Association 82(398): 528–540.)

Key Claims

The setup. Write the observed data $y$ , latent data $z$ , and augmented data $x=(y,z)$ , chosen so that $p(\theta\mid y,z)$ is easy to sample. The goal is the intractable observed-data posterior $p(\theta\mid y)=\int p(\theta\mid y,z)\,p(z\mid y)\,dz$ .
The integral equation. The posterior satisfies a fixed-point (integral) equation, $p(\theta\mid y)=\int\!\!\int p(\theta\mid z,y)\,p(z\mid\phi,y)\,p(\phi\mid y)\,dz\,d\phi \equiv (T g)(\theta)$ , where the predictive $p(z\mid y)=\int p(z\mid\phi,y)\,p(\phi\mid y)\,d\phi$ mixes over the current posterior. The true posterior is the fixed point $g=Tg$ .
The Data Augmentation algorithm (successive substitution). Starting from any initial approximation $g_0(\theta)$ $g_{0} (θ)$ , iterate $g_{i+1}=T g_i$ $g_{i + 1} = T g_{i}$ in two steps:
- I-step (Imputation). Generate $m$ latent samples $z^{(1)},\dots,z^{(m)}$ from the current predictive $p(z\mid y)$ : for each, (a1) draw $\phi$ from the current posterior approximation $g_i$ , then (a2) draw $z$ from $p(z\mid\phi,y)$ .
- P-step (Posterior). Update the posterior approximation as the mixture of augmented-data posteriors over the imputed data, $g_{i+1}(\theta)=\frac{1}{m}\sum_{j=1}^{m}p(\theta\mid y,z^{(j)})$ .
The EM analogy. Data augmentation is to Bayesian posterior computation what EM (Dempster–Laird–Rubin 1977) is to maximum likelihood: the I-step parallels the E-step and the P-step parallels the M-step, but the output is the full posterior distribution (and a diagnostic for the adequacy of the normal/Laplace approximation), not just a mode and curvature. As in EM, one may artificially formulate a problem as an incomplete-data problem to gain tractability.
Multiple-imputation flavor and Dirichlet sampling. The I-step performs multiple imputation of the latent data (independently and concurrently paralleled by K.H. Li 1985); for cases where $p(\theta\mid y,z)$ is not exactly samplable (e.g. multinomial), a Dirichlet sampling scheme gives approximate draws. A few iterations already reveal whether the normal approximation to the MLE is adequate (illustrated on a genetic-linkage example).

Concepts Introduced or Extended

Entities Mentioned

Quotes

"The method we propose exploits the simplicity of the posterior distribution of the parameter given the augmented data, just as the EM algorithm exploits the simplicity of maximum likelihood estimation given the complete data."

"We will … use the term latent data ( $z$ ) to denote the unobserved supplementary data needed for the augmentation of $y$ so that the augmented data, $x=(y,z)$ , is straightforward to analyze."

My Take

This paper is the conceptual seed of modern Bayesian computation: the "introduce latent variables so the complete-data posterior is conjugate, then iterate" idea is exactly what powers the Albert–Chib probit sampler, Markov-switching state samplers, stochastic-volatility mixtures, and essentially every latent-variable Gibbs algorithm on the data-augmentation page. Historically it is the bridge from EM to the Gibbs sampler: Tanner–Wong's chained conditionals $p(\theta\mid y,z)$ and $p(z\mid\theta,y)$ are precisely the two Gibbs blocks that Gelfand–Smith (1990) three years later recognized as a special case of the Gibbs sampler. The original algorithm's multiple-imputation form (the mixture over $m$ imputations in the P-step) was soon streamlined to the single-imputation Markov-chain version we now call data augmentation, but the insight — that the observed-data posterior is the fixed point of an imputation/posterior integral operator — is the durable one.