Importance Sampling over Discrete Structures

Importance sampling is a general inference method for estimating posterior expectations. While its validity in $\mathbb{R}^n$ is straightforward, when considering discrete structural choices that change the set and number of continuous parameters, we may wonder if importance weights still yield a valid estimate of the posterior given the varying dimensionality.

Define a probabilistic model under which a discrete structure $k \sample p(\cdot)$ is chosen. Conditioned on this branch, a corresponding set of continuous parameters $\bm{\theta} \sample p(\cdot | k)$ of length $N_k$ are sampled, so that $\bm{\theta} \in \Theta_k = \mathbb{R}^{N_k}$. Finally an observation is generated $\mathcal{D} \sample p(\cdot | k, \bm{\theta})$. The full joint distribution is

Computing expectations of test functions here is generally intractable, as we must sum over all discrete choices and integrate over the corresponding continuous parameters. Even the normalizing constant, the marginal likelihood of the data, has this form:

Note that each inner integral lives entirely within one branch, over a space of fixed dimension $N_k$. We give it a name, the branch marginal likelihood:

so that $p(\mathcal{D}) = \sum_k p(k) Z_k$. The strategy is to show that importance sampling estimates each $Z_k$ in the ordinary fixed-dimensional way, and that the overall estimate is simply a weighted sum of these. At no point will we need to compare densities across spaces of different dimension.

Importance sampling introduces a proposal $q$, which we factor in the same way as the model, $q(k, \bm{\theta}) = q(k)q(\bm{\theta}|k)$, and takes a set of $N$ latent variables $\brace{(k_i,\bm{\theta}_i)}_{i=1}^N \sample q(\cdot,\cdot)$, assigning corresponding importance weights

The weight factors into a ratio of probabilities over the discrete choice and a ratio of densities within a single branch, both taken over the same space. We require the usual support conditions: $q(k) > 0$ whenever $p(k)Z_k > 0$, and within each such branch $q(\bm{\theta}|k) > 0$ whenever $p(\bm{\theta}|k)p(\mathcal{D}|k,\bm{\theta}) > 0$.

Theorem 1. The expected value of the importance weights under a chosen branch is the marginal likelihood of its continuous distribution.

Proof. Fix a branch $k$. Then

where the support condition ensures that dividing by $q(\bm{\theta}|k)$ loses no mass. This is ordinary importance sampling in $\mathbb{R}^{N_k}$.

$\Box$

Theorem 2. The expected value of the importance weights is a finite sum of continuous marginal likelihoods.

Proof. Conditioning on the sampled branch,

using Theorem 1 in the third line. The sum is finite when there are finitely many structures. With countably many, it is a series of nonnegative terms, so exchanging the sum and expectation is still justified (Tonelli's theorem) and the series converges to $p(\mathcal{D})$.

$\Box$

Theorem 2 says the estimator $\hat{p}(\mathcal{D}) = \frac{1}{N}\sum_{i=1}^N w(k_i, \bm{\theta}_i)$ is unbiased. Since the weights are i.i.d. with finite mean, the strong law of large numbers makes it consistent as well: $\hat{p}(\mathcal{D}) \to p(\mathcal{D})$ almost surely. Sampling a branch and then its parameters is therefore equivalent, in expectation, to enumerating every branch and estimating each $Z_k$ separately.

To estimate posterior expectations, we use the weights to form the self-normalized importance sampling estimator of a test function $f$:

Theorem 3. The self-normalized importance sampling estimator is a consistent estimator of the expected value of the test function under the posterior, provided that expectation exists.

Proof. Divide the numerator and denominator by $N$. By the strong law of large numbers, the denominator converges almost surely to $\E_q\bracket{w(k, \bm{\theta})} = p(\mathcal{D}) > 0$ by Theorem 2, and the numerator converges almost surely to $\E_q\bracket{w(k, \bm{\theta})f(k, \bm{\theta})}$, which is finite when $\E_{p(\cdot,\cdot|\mathcal{D})}\bracket{|f|} < \infty$. The ratio of two almost surely convergent sequences converges to the ratio of their limits, so it suffices to show

Following the same steps as Theorem 2,

Dividing by the limit of the denominator, $\hat{\mu}_f \to \E_{p(\cdot,\cdot|\mathcal{D})}\bracket{f(k, \bm{\theta})}$ almost surely. Note that $\hat{\mu}_f$ is biased for finite $N$; only its limit is exact.

$\Box$

The question we started with is now a special case. Choosing the indicator $f(k, \bm{\theta}) = \mathbb{I}[k = k^*]$ gives an estimate of the posterior probability of a single structure:

Corollary. The estimator

converges almost surely to the posterior marginal over structures,

Proof. The indicator is bounded, so Theorem 3 applies. Its posterior expectation is $\sum_k \int_{\Theta_k} p(k, \bm{\theta}|\mathcal{D})\, \mathbb{I}[k = k^*]\ d\bm{\theta} = p(k^*|\mathcal{D})$, and by Bayes' rule $p(k^*|\mathcal{D}) = p(k^*)p(\mathcal{D}|k^*)/p(\mathcal{D}) = p(k^*)Z_{k^*}/\sum_k p(k)Z_k$.

$\Box$

For every $N$, these estimates are nonnegative and sum to exactly one across structures, so they always form a proper distribution over branches, and that distribution converges to the true posterior marginal.

We were able to avoid a measure-theoretic analysis by exploiting the factorization of the distribution. Because the importance weight splits into a ratio over the discrete choice and a ratio of densities within a single branch, every density ratio we ever form compares two densities over the same space $\Theta_k$. Each branch is ordinary importance sampling in $\mathbb{R}^{N_k}$, and the discrete choice only reweights branches against one another. Consistency is an asymptotic guarantee, though. When the proposal over branches or parameters is poorly matched to the posterior, the variance of the weights can make the number of samples needed impractically large.