Importance Weighting Problem

Let

$f:\{1,\dots ,K\}\to \mathbb{R}$ be a scalar function over

$K$ values.

Let

$\theta$ be parameters of a

$K$-dimensional Dirichlet distribution, and

$\pi$ a draw from it. (the sample from the Dirichlet,

$\pi$, is therefore a probability distribution over

$K$ outcomes, such that

$\sum _{k=1}^K{\pi }_k=1$).

$$\pi \sim \mathcal{Dir}(\theta )$$

Let

$a$ be a sample from

$\pi$, that is

$$a\sim \pi$$

It's not diffuclt to see that the marginal distribution of

$a$ is

$$\begin{array}{rl}p(a|\theta )& =\int p(a|\pi )p(\pi |\theta )\text{d}\pi \\ & ={\mathbb{E}}_{\pi \sim \mathcal{Dir}(\theta )}{\pi }_a\\ & =\frac{{\theta }_a}{\sum _{k=1}^K{\theta }_k}\end{array}$$

Estimating expectation

I'm interested in estimating

$$F(\theta )={\mathbb{E}}_{a\sim p(a|\theta )}f(a)$$

If I could sample from

$p(a|\theta )$, this would be easy to estimate as a Monte Carlo average.

$$F(\theta )={\mathbb{E}}_{a\sim p(a|\theta )}f(a)\approx \frac{1}{N}\sum _{n=1}^{N}f(a_n)$$

where

$$\begin{array}{rl}{\pi }_n& \sim \mathcal{Dir}(\theta ),\text{i.i.d.}\\ a_n& \sim {\pi }_n\end{array}$$

Importance sampling

However, I will assume that I can't sample from

$p(\theta )$, only from

$p(\tilde{\theta })$. So my samples are:

$$\begin{array}{rl}{\tilde{\pi }}_n& \sim \mathcal{Dir}(\tilde{\theta }),\text{i.i.d.}\\ {\tilde{a}}_n& \sim {\tilde{\pi }}_n\end{array}$$

Using importance sampling I can estimate my quantity of interest as follows:

$$\begin{array}{rl}F(\theta )& ={\mathbb{E}}_{a\sim p(a|\theta )}\\ & =\sum _{a=1}^{K}p(a|\theta )f(a)\\ & =\sum _{k=1}^{K}p(a|\tilde{\theta })\frac{p(a|\theta )}{p(a|\tilde{\theta })}f(a)\\ & ={\mathbb{E}}_{a\sim p(a|\tilde{\theta })}\frac{p(a|\theta )}{p(a|\tilde{\theta })}f(a)\end{array}$$

Now I have expressed my quantity of interest as an expectation over

$p(a|\tilde{\theta })$, so I can use my samples

${\tilde{a}}_n$, as follows:

$$\begin{array}{rl}F(\theta )& ={\mathbb{E}}_{a\sim p(a|\tilde{\theta })}\frac{p(a|\theta )}{p(a|\tilde{\theta })}f(a)\\ & \approx \frac{1}{N}\sum _{n=1}^N\frac{p({\tilde{a}}_n|\theta )}{p({\tilde{a}}_n|\tilde{\theta })}f({\tilde{a}}_n).\end{array}$$

So, instead of simply averaging

$f(a)$ over the samples, I weight each sample by the importance weight

$w(a)=\frac{p(a|\theta )}{p(a|\tilde{\theta })}$.

This is a widely used method for estimating expectations under distributions when you only have samples from another distribution. The problem with it, it is a high variance estimator.

Let's call this estimator

${\tilde{F}}_{IS}(\theta )$

Alternative importance sampling

In this example, we sample

$a$ in a two-stage process: first we sample

$\pi$ and then we sample

$a$. The IS estimator above doesn't exploit this, it completely ignores

$\pi$. We can construct a similar estimator that does take

$\pi$ into account:

$$\begin{array}{rl}F(\theta )& ={\mathbb{E}}_{a\sim p(a|\theta )}\\ & =\sum _{a=1}^{K}p(a|\theta )f(a)\\ & =\sum _{a=1}^K\int p(a,\pi |\theta )f(a)\text{d}\pi \\ & =\sum _{k=1}^K\int p(a|\tilde{\theta })\frac{p(a,\pi |\theta )}{p(a,\pi |\tilde{\theta })}f(a)\pi \\ & ={\mathbb{E}}_{a\sim \pi ,\pi \sim \mathcal{Dir}(\theta )}\frac{p(a,\pi |\theta )}{p(a,\pi |\tilde{\theta })}f(a)\end{array}$$

Based on this, an empirical estimator can be constructed:

$$\begin{array}{rl}F(\theta )& ={\mathbb{E}}_{a\sim p(a|\theta )}f(a)\\ & ={\mathbb{E}}_{a\sim \pi ,\pi \sim \mathcal{Dir}(\theta )}\frac{p(a,\pi |\theta )}{p(a,\pi |\tilde{\theta })}f(a)\\ & \approx \frac{1}{N}\sum _{n=1}^N\frac{p({\tilde{a}}_n,{\tilde{\pi }}_n|\theta )}{p({\tilde{a}}_n,{\tilde{\pi }}_n|\tilde{\theta })}f(a)\end{array}$$

Let's call this estimator

${\tilde{F}}_{IS2}(\theta )$.

Note that this estimator is very similar to the previous one, except that the importance weights now depend not just on

$a$ but on

$\pi$ also.

Questions

Closed form importance weights in each estimator

Which estimator is better?

How do the importance weights behave in the two estimators?

Which estimator has lower variance?