Consider approximating the following integral: $$ \mathcal{Z} = \int h(x) \pi(x) dx $$ Where $\pi$ is known only up to a normalizing constant, that is, $\pi(x) = \hat{\pi}(x)/\mathcal{Z}_\pi$. We can simulate $\{x^{(i)}\}_{i=1}^m$ from an appropriate proposal distribution $q$ and use the ratio importance sampling estimator: $$ \mathcal{Z} \approx \sum_{i=1}^m w(x^{(i)})h(x^{(i)}) / \sum_{i=1}^m w(x^{(i)}) $$ Where $w(x^{(i)}) = \hat{\pi}(x^{(i)})/q(x^{(i)})$. This is a consistent estimator and actually even has lower asymptotic variance than the standard version (which can be used when $\pi$ is normalized) but it cannot be said to be unbiased. In the event that one needs provably unbiased samples could this be achieved through the use of the resampling bootstrap? That is, we collect our weighted samples as usual: $\{w^{(i)},x^{(i)}\}_{i=1}^m$ then proceed to a resampling stage to generate a set of unweighted samples: $\{\hat{x}^{(i)}\}_{i=1}^m$ which are distributed according to $\pi$. At this point we can use the standard empirical average to yield an unbiased estimate: $$ \mathcal{Z} \approx m^{-1} \sum_{i=1}^m h(\hat{x}^{(i)}) $$ Of course, this is not likely to be a practical approach since the bias in the original estimate is not typically a problem, my question is my attempt to settle an argument over the fact that the bias doesn't matter, and even if it does, it can be worked around in this way.
2 Answers
This is not possible because the weights are not normalised: in the resampling stage, you need first to normalise the $\omega_i$'s into $$ \bar \omega_i = \omega_i \bigg/ \sum_{j=1}^m \omega_j $$ to be able to sample the $(x_i,\omega_i)$...
-
$\begingroup$ Ah, yes, thank you very much. I see the resampling 'trick' is not doing anything magical, at the individual level it's really just replacing a continuous value with an a Bernoulli sample. Although this did bring up another question in my mind, in the population Monte Carlo work is the resampling stage really that fundamental? I mean one could define the next proposal (kernel mixture) using the continuous (normalized) importance weights just as well. Likewise, in the D-kernel variant, the individual kernel counts could be continuous values right? Not saying this is better, they seem the same. $\endgroup$– fairidoxMay 22, 2012 at 18:57
The fundamental idea behind importance sampling is to be able to estimate better the tails of the distribution. It is a variance reduction trick in Monte Carlo. Generally you need a large sample to get observations in the tale of the distribution. Importance sampling gives more weight to the tails or in general any part of the distribution that needs more attention than it would get from basic (sometimes called naive) Monte Carlo. The term is due to Hammersley and Handscombe who wrote a book on Monte Carlo and variance reduction techniques way back in the 1950s. Because you know how you biased the sampling with the weights you chose you can determine weights to get unbiased estimates. There is no free lunch though. While you gain accuracy for some estimates you will lose for others. For example if the distribution has a finite mean the adjusted unbiased estimate will have a larger variance than what you would have gotten taking an unweighted average using naive Monte Carlo. When talking about bootstrap you are usually referring to the process of drawing inference about a population based on the mechanism of sampling with replacement from the original data set. In theory it does not involve Monte Carlo. In practice you cannot usually get bootstrap estimates without a Monte Carlo approximation. I sense that your understanding of bootstrap may be fuzzy. To learn more about the bootstrap Tim Hesterberg's chapter in David Moore's introductory statistics book can be very helpful. Also the book by Efron and Tibshirani or one of mine explain the bootstrap well. Hesterberg's new Mathematical Statistics book also covers bootstrap.
-
$\begingroup$ Thanks for the comment, it's very useful to hear the opinions of a stats person on such topics as researchers in my field (machine learning) often have a different take on such ideas. You are right, my question stems (in part) from a lack of understanding of the theory behind bootstrapping so thanks for the references :) $\endgroup$– fairidoxMay 22, 2012 at 22:49
-
$\begingroup$ I appreciate your kindness and the fact that you are open to learning. I half expected you to take offense at my suggestions. A lot of people would. We all would be better off if we could be openminded and not let our egos get in the way of learning. Even old guysn like me have plenty left to learn. $\endgroup$ May 22, 2012 at 22:54