4
$\begingroup$

Consider approximating the following expectation: $$\mathbb{E}[h(x)] = \int h(x)\pi(x) dx$$

Where $h(x)$ is an arbitrary function and $\pi(x)$ is a distribution for which the normalizing constant is not known. Also, assuming the above integral is highly variable and high dimensional the standard approach would be to use MCMC methods to sample points $\{x^{(i)}\}_{i=1}^N$ that are distributed according to $\pi(x)$ and return the sample average:

$$ \mathbb{E}[h(x)] \approx \frac{1}{N} \sum_{i=1}^N \ h(x^{(i)}) $$

My question is, if the function $h(x)$ happens to be highly variable as well, that is, $\pi(x)$ is very different from the optimal sampling distribution $q^*(x) = |h(x)|\pi(x)/Z$, is there a straightforward way to modify MCMC methods to improve the variance of the estimate? That is, how can MCMC (and related methods) take into account the variability (or sparsity, etc.) of $h(x)$?

Also, I asked a related question earlier about whether one could use Monte Carlo methods for sampling from $q^*(x)$ and use the weighted importance sampling estimator to compensate for the fact the normalizer is not known. The answer was basically that this is not a good idea, since it requires estimating the harmonic mean of $h(x)$ under $q^*(x)$ which, in practice, is likely to have infinite variance. So, at the least, let's put aside this approach for now.

Edit: The keywords "variance reduction MCMC" are actually useful in finding methods that address this issue, I've found a few methods using control variates, antithetic variates, and some adaptive methods like zero variance Monte Carlo. Perhaps someone is able to comment on the viability of these methods or to add more to my list. Thanks.

Edit: In response to Xi'an's answer I thought I would update the question.

First of all, it appears that my first question where I asked how MCMC could be used to sample from $q^*(x)$ in the case where the normalizer for $\pi(x)$ was known is addressed in the literature primarily as the problem of computing the normalization constant, or equivalently: model evidence, partition function, or energy function.

It appears there are a number of different methods for doing this with MCMC and I found chapter 4 of Iain Murray's PhD thesis to be an excellent overview of the main ideas. Also, the very recent paper cited in Xian's answer details a method, MCIS, that offers some particular advantages over these existing methods. However, after reviewing many of these papers I would have to conclude none of these ideas have turned out to be as "straightforward" as I would have hoped.

Regarding this question, the answer is essentially: no, there is no straightforward way to solve this problem other than estimating the normalizing constant for $\pi(x)$ separately. That is, if we let: $\hat\pi(x) = \pi(x)/Z$ denote our unnormalized distribution and $I = \int h(x)\hat\pi(x) dx$ denote the quantity of interest up to a normalizing constant, we can use any MCMC methods designed for estimating normalization constants to estimate $I$ and $Z$ separately and return the ratio $\frac{I}{Z}$. How this simple procedure relates to bridge sampling I'm still a bit unsure though.

$\endgroup$
3
$\begingroup$

A fairly interesting question! At the Winter Simulation conference last month, in Phoenix, Zdravko Botev gave a talk on this very problem with a paper written by Pierre Lecuyer and Bruno Tuffin. It was applied to a graph model but the idea is there, indeed. (The program and abstracts of WSC 2011 seem to have vanished from the Web, how inconvenient!)

In connection with the earlier question, aiming an MCMC at the optimal $q^\star(x)$ is possible. Since the normalising constant $Z$ is missing, a second MCMC should be directed at approximating $Z$, resulting in a ratio of integrals for which bridge sampling and other variance reduction methods should be useful.

$\endgroup$
  • $\begingroup$ Thank you for the links! I'll take look at these methods. $\endgroup$ – fairidox Jan 24 '12 at 6:21
  • $\begingroup$ I actually came back from Phoenix with the ambition (!) to work on this, so thanks for reminding me. $\endgroup$ – Xi'an Jan 24 '12 at 9:15
  • $\begingroup$ Accepted the answer, I think I understand this much better now, thanks again. I edited my question though, if you have time please let me know if I am correct in my understanding. $\endgroup$ – fairidox Jan 30 '12 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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