Estimating the Partition Function · Annealed Importance Sampling · Bridge Sampling

§18.7 When you actually need Z

The methods so far avoid the partition function. But sometimes we genuinely need its value — to report a normalized likelihood, monitor training, or compare models. Comparing two models is the gentlest case: it needs only the ratio of their partition functions, not either value.

Model comparison needs only the ratio (eq 18.39)

\sum_i \log p_A(\boldsymbol{x}^{(i)}) - \sum_i \log p_B(\boldsymbol{x}^{(i)}) = \sum_i \log \frac{\tilde{p}_A(\boldsymbol{x}^{(i)})}{\tilde{p}_B(\boldsymbol{x}^{(i)})} - m \log \frac{Z(\boldsymbol{\theta}_A)}{Z(\boldsymbol{\theta}_B)}

$\log \frac{\tilde{p}_A}{\tilde{p}_B}$	the per-example unnormalized log-ratio — Z-free and cheap to evaluate	scalar
$m \log \frac{Z(\boldsymbol{\theta}_A)}{Z(\boldsymbol{\theta}_B)}$	the only Z-dependent term, and it needs just the RATIO Z_A/Z_B — not either absolute value. m = test-set size	scalar

Why a ratio is so much easier than the value

An absolute $Z$ is a sum over every state — hopeless. But a ratio $Z_1/Z_0$ only asks “how much bigger is one normalizer than another,” and if the two distributions overlap you can answer that from a handful of samples. Every method below — importance sampling, annealed importance sampling, bridge sampling — estimates a ratio, never an absolute value. To get an actual $Z$ , estimate one ratio against a reference distribution whose $Z$ you already know.

The simplest estimator is plain importance sampling: draw from a tractable proposal $p_0$ (known $Z_0$ ) and reweight,

Importance-sampling estimate of Z (eq 18.44)

\hat{Z}_1 = \frac{Z_0}{K}\sum_{k=1}^{K} \frac{\tilde{p}_1(\boldsymbol{x}^{(k)})}{\tilde{p}_0(\boldsymbol{x}^{(k)})}, \qquad \boldsymbol{x}^{(k)} \sim p_0

$\tilde{p}_1 / \tilde{p}_0$	the importance weight — how much more probable each proposal sample is under the target than the proposal	scalar
$Z_0$	the KNOWN partition function of the proposal; the sum estimates Z₁/Z₀, then multiply by Z₀	scalar

This works only if $p_0 \approx p_1$ . When they differ, most proposal samples land where $p_1$ is negligible, a few carry enormous weight, and the variance (eq 18.46) explodes — exactly the failure you met in §17.2:

The importance-sampling variance problem, recalled from §17.2. Estimating Z₁ the same way, a proposal p₀ far from the target p₁ gives wildly varying weights and a useless estimate. Annealed importance sampling and bridge sampling exist precisely to bridge that gap.

μ = 0.0

s = P(x>3) = 0.00135

rel. error / sample:

= 27.4 (naive 27.4)

samples for 10% error ≈ 75,195

q: poor (naive-like)

At μ = 0 (naive Monte Carlo) almost no samples land in the tail, so the variance is enormous. Slide μtoward the tail and q overlaps p·f — the estimator's variance collapses. The dashed q\* ∝ p·|f| is the optimal (zero-variance) choice of eq 17.13; overshoot μ and the error creeps back up.

§18.7.1 Annealed importance sampling

When $D_\text{KL}(p_0 \| p_1)$ is large, annealed importance sampling (AIS) inserts a chain of intermediate distributions between them, so no single hop is a big jump:

Chain the ratios through intermediates (eqs 18.49–18.50)

\frac{Z_1}{Z_0} = \prod_{j=0}^{n-1} \frac{Z_{\eta_{j+1}}}{Z_{\eta_j}}, \qquad p_{\eta_j} \propto \tilde{p}_1^{\,\eta_j}\, \tilde{p}_0^{\,1-\eta_j}, \quad 0 = \eta_0 < \cdots < \eta_n = 1

$\prod_j \frac{Z_{\eta_{j+1}}}{Z_{\eta_j}}$	telescope the target ratio into many small ratios; each small ratio is estimated by simple importance sampling	product of n hops
$\tilde{p}_1^{\eta}\, \tilde{p}_0^{1-\eta}$	the standard intermediate: a weighted GEOMETRIC average of target and proposal — η sweeps from 0 (p₀) to 1 (p₁)	unnormalized
$\eta_j$	the annealing schedule; more/closer intermediates → each hop's distributions overlap → each ratio is low-variance	[0, 1]

Sampling walks $p_0 \to p_{\eta_1} \to \cdots \to p_1$ with transition operators $T_{\eta_j}$ (any MCMC — Gibbs, Metropolis–Hastings) that leave each $p_{\eta_j}$ invariant, chaining the per-hop importance weights (eq 18.52). It is provably valid — simple importance sampling on an extended state space (eqs 18.54–18.61). Add bridges and watch the estimator’s variance collapse:

Annealed importance sampling. With 1 hop (simple IS) the wide proposal p₀ barely overlaps the far bimodal target p₁, so the estimator relative variance is astronomical. Each bridge p_η ∝ p̃₁^η p̃₀^{1−η} (faint curves) overlaps its neighbors, so every hop's ratio is easy and the chained Z₁/Z₀ becomes reliable.

simple IS

bridges: 0 intermediates

estimator rel. variance

= 4.79

Ẑ₁/Ẑ₀: noisy

At 1 hop (simple importance sampling) p₀ barely overlaps the far target p₁, so the importance weights vary wildly and the estimate is useless. Each added bridge p_η ∝ p̃₁^η p̃₀^(1−η) makes consecutive distributions overlap, so every hop's ratio is easy — and the chained Z₁/Z₀ (a product of the small hop-ratios) becomes reliable.

AIS (Jarzynski 1997; Neal 2001) is the standard method for estimating the partition function of RBMs and deep belief networks, popularized by Salakhutdinov & Murray (2008).

§18.7.2 Bridge sampling

Bridge sampling takes the opposite tack: instead of a chain of intermediates, use a single bridge distribution $p_*$ that overlaps both $p_0$ and $p_1$ :

Bridge sampling (eq 18.62)

\frac{Z_1}{Z_0} \approx \frac{\sum_{k} \tilde{p}_*(\boldsymbol{x}_0^{(k)}) / \tilde{p}_0(\boldsymbol{x}_0^{(k)})}{\sum_{k} \tilde{p}_*(\boldsymbol{x}_1^{(k)}) / \tilde{p}_1(\boldsymbol{x}_1^{(k)})}

$\boldsymbol{x}_0^{(k)} \sim p_0,\ \boldsymbol{x}_1^{(k)} \sim p_1$	sample from BOTH distributions; the bridge weighs the two sample sets against each other	two sample sets
$p_*$	the bridge; optimal p_* ∝ p̃₀p̃₁/(r p̃₀ + p̃₁) with r = Z₁/Z₀ — circular, but solvable by starting from a coarse r and iterating	distribution

AIS vs bridge sampling. AIS spans a large gap with a chain of intermediates; bridge sampling spans a smaller gap with one well-placed bridge p_* overlapping both ends.

The two are complementary: if $p_0$ and $p_1$ are reasonably close, a single bridge beats AIS; if they are far, AIS’s many intermediates span the distance. Linked importance sampling (Neal 2005) uses bridges between AIS’s intermediates to get the best of both. AIS is too costly to run during training, but combining bridge sampling, short-chain AIS, and parallel tempering, Desjardins et al. (2011) tracked an RBM’s partition function throughout learning.

That closes the partition-function problem. But intractable $Z$ is only one obstacle to training generative models; the other is intractable inference — the hard positive phase — which is the next chapter.

Check yourself — estimating Z, AIS & bridge sampling

1.To decide which of two models assigns higher test likelihood, what do you actually need to know about their partition functions?

2.Why does simple importance sampling fail to estimate Z when the proposal p₀ is far from the target p₁?

3.How does annealed importance sampling overcome the distant-proposal problem?

4.How does bridge sampling differ from AIS, and when is each preferred?

5.Predict the outcome — in AISLab you raise the '# bridges' slider from 1 (simple IS) upward. What happens to the estimator's relative variance?

5 questions