5
$\begingroup$

I was stuck with the function 17.13 in the open source book deep learning on page 590.

For short, the question is that, For the importance sampling estimator: $$\hat s_q = \frac{1}{n}\sum_{i=1, x^{i}\sim q}\frac{p(x^{(i)})f(x^{(i)})}{q(x^{(i)})}$$

and its variance can be represented as: $$Var[\hat s ] = Var[\frac{p(x)f(x)}{q(x)}]/n$$

I am not clear that why the minimum occurs when q is:

$$q^*(x)=\frac{p(x)|f(x)|}{Z},$$

where $Z$ is the normalization constant, chosen so that $q^∗(x)$ sums or integrates to 1 as appropriate.

Any suggestions are highly appreciated. Thanks very much!

$\endgroup$
2
  • $\begingroup$ $Var[\frac{p(x)f(x)}{q(x)}] = \int \frac{p^2(x)f^2(x)}{q(x)}\mathrm{d}x - \mu^2 = \int \frac{((p(x)f(x) - \mu q(x))^2}{q(x)}\mathrm{d}x $ $\endgroup$
    – Kuo
    Commented Feb 27 at 6:23
  • $\begingroup$ Check theorem 1 $\endgroup$
    – Kuo
    Commented Feb 27 at 6:30

2 Answers 2

3
$\begingroup$

An intuitive explanation is that we want $q$ to be large whenever either $p$ or $|f|$ is large. Otherwise, our estimate of $E_p[f]$ might have a lot of error, since we're "missing out" on sampling the most influential regions of the real number line. A proof is below:

So we want to minimize

$$\begin{align} \text{Var}_q\left[ \frac{p(x)f(x)}{q(x)} \right] &= E_q\left[ \left( \frac{p(x)f(x)}{q(x)} \right)^2 \right] - E_q\left[\frac{p(x)f(x)}{q(x)} \right]^2 \\ \end{align}$$

The second term is constant with respect to $q$. In fact, it comes out to exactly $E_p[f(x)]^2$, so we can drop it from the optimization, which leaves with

$$\begin{align} E_q\left[ \left( \frac{p(x)f(x)}{q(x)} \right)^2 \right] &= \int \frac{p(x)^2 f(x)^2}{q(x)} dx \end{align}$$

We also have the constraint that $\int q(x) dx = 1$. Since this is a constrained optimization problem, we can write the lagrangian:

$$\begin{align} L(q, \lambda) &= \int \frac{p(x)^2 f(x)^2}{q(x)} dx + \lambda \left( \int q(x) dx - 1 \right) \end{align}$$

We want the functional derivative with respect to $q$:

$$\begin{align} \frac{\partial L(q, \lambda)}{\partial q(x)} &= \lim_{\epsilon \rightarrow 0} \frac{\partial}{\partial \epsilon} \left[ \int \frac{p(x)^2 f(x)^2}{q(x) + \epsilon \eta(x)} dx + \lambda \left( \int (q(x)+\epsilon \eta(x)) dx - 1 \right) \right] \end{align}$$ for any arbitrary $\eta$.

This comes out to $$\begin{align} &\lim_{\epsilon \rightarrow 0} \left[ \int -\frac{p(x)^2 f(x)^2}{(q(x) + \epsilon \eta(x))^2} \eta(x)\ dx + \lambda \int \eta(x) dx \right] \\ &= \int -\frac{p(x)^2 f(x)^2}{q(x)^2} \eta(x)\ dx + \lambda \int \eta(x) dx \\ &= \int \eta(x)\left( \lambda -\frac{p(x)^2 f(x)^2}{q(x)^2}\right) dx \\ \end{align}$$

Since we want the derivative to be $0$ for all $\eta(x)$, then we must have

$$\begin{align} 0 &=\lambda -\frac{p(x)^2 f(x)^2}{q(x)^2} \\ \lambda &= \frac{p(x)^2 f(x)^2}{q(x)^2} \\ q(x)^2 &= \frac{p(x)^2 f(x)^2}{\lambda} \\ q(x) &= \frac{p(x)|f(x)|}{\sqrt{\lambda}} \end{align}$$

And it must be the case that $\sqrt{\lambda} = Z$.

$\endgroup$
2
  • $\begingroup$ Thanks for your derivation. But how does the first limitation becomes the second? It seems that the divisor is squared unknowingly... $\endgroup$ Commented Jan 25, 2018 at 1:24
  • $\begingroup$ It is because the derivative of $1/f(\epsilon)$ is $-\frac{f'(\epsilon)}{f(\epsilon)^2}$ by the chain rule, where in this case, $f(\epsilon) = q(x) + \epsilon \eta(x)$ $\endgroup$
    – shimao
    Commented Jan 25, 2018 at 1:29
2
$\begingroup$

An easiest and intuitive answer [in addition to the earlier one that is completely to the point!] is that, when $f$ is a positive function, the variance of the resulting optimum is$$\text{var}[\hat s_q ] = \text{var}\left\{\frac{p(x)f(x)}{p(x)f(x)/Z}\right\}\frac{1}{n}=\frac{\text{var}[Z]}{n}=0$$since $Z$ is a constant. It thus cannot be beaten and rightly so since the resulting optimal estimator is $$\hat s_q \stackrel{x^{i}\sim q^\star}{=} \dfrac{1}{n}\sum_{i=1}^n\frac{ p(x^{(i)})f(x^{(i)}) }{ \left\{\dfrac{ p(x^{(i)})f(x^{(i)})}{Z}\right\} }=Z$$ which is indeed perfect since it returns the exact (if unknown) numerical value of the integral!

Remark: If $f$ takes positive and negative values, it can be written as $$f(x)=\max(f(x),0)-\max(-f(x),0)\stackrel{\text{def}}{=}f^+(x)-f^-(x)$$ Therefore, if one defines two importance functions, $$q^+(x)=\dfrac{p(x)f^+(x)}{Z^+}\quad\text{and}\quad q^-(x)=\dfrac{p(x)f^-(x)}{Z^-}$$one can produce a zero variance estimator as $$\hat{s}=\frac{1}{n^+}\sum_{i=1}^{n^+} \dfrac{p(x_i)f^+(x_i)}{q^+(x_i)}-\frac{1}{n^-}\sum_{i=1}^{n^-} \dfrac{p(y_i)f^-(y_i)}{q^-(y_i)}$$ based on two samples of sizes $n^+$ and $n^-$ (although $n^+=n^-=1$ is enough).

$\endgroup$
2
  • $\begingroup$ But sometimes $f$ may be negative.. $\endgroup$ Commented Jan 25, 2018 at 1:28
  • $\begingroup$ This is why this is an intuitive answer that only tackles that case. $\endgroup$
    – Xi'an
    Commented Jan 25, 2018 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.