1
$\begingroup$

This is more of a theory question, consider:

$$P(w_1|D)=\int P(w_1|S)P(S|D)d(S)$$

which we approximate via Gibbs sampling $S$ (assume the initial state of the Gibbs sampler is denoted by $M_0$), instead of computing the integral directly. Now,

  • assume for a particular $w$, i.e. $w_1$, we have $N$ samples for $S$. What does it mean if we throw away these samples after evaluating $P(w_1|D)$, and when we get $w_2$, we start the sampler from $M_0$ again. Does it still construct a valid sampler?

  • Why do this? Well, assume the size of the graphical model is so large that keeping samples is not practical (memory wise).

$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by "for a particular $w$"? Earlier in your question you just define a variable $w_1$, but no $w$. Do you mean to say the variable that you want to compute the expectation for is $w$, and $w_1$ is one sample of $w$? Or is $w_1$ itself a variable that is part of the larger set of $w$ that all depend on $S$? $\endgroup$ – Ruben van Bergen Jan 12 '17 at 12:31
  • $\begingroup$ Edited the question. $w_1$ is an assignment for $w$. For example, $w\in\{w_1,w_2,...,w_K\}$. Think about $P(w_1|D)$ as the predictive probability of $w_1$ given data $D$. $\endgroup$ – user3639557 Jan 12 '17 at 12:40
  • $\begingroup$ The sampler is used to draw samples from $P(S|D)$. Then samples are used to approximate the integral with a summation over these samples. $\endgroup$ – user3639557 Jan 12 '17 at 12:46
2
$\begingroup$

After reading the further explanations in the comments (which should definitely be moved to the question itself), I feel that using the same starting point $M_0$ for the MCMC chain is not necessarily damaging to the approximation if

  1. A large enough burn-in (or warm-up) chunk of the simulations is not used for the approximation;
  2. The total number of MCMC simulations is such that convergence (up to some degree of precision) is guaranteed.

My reasoning is the same as with regular Monte Carlo approximations to functions. Using the same simulations for different entries of the function is reducing the variability of the approximation and produces smoother versions of the approximated functions.

As we wrote in our book Introducing Monte Carlo Methods with R (2010, Section 5.4.1),

If $h(x)$ can be written as $\mathbb{E}[H(x,Z)]$ but is not directly computable, a natural Monte Carlo approximation of $h$ is $$ \hat h(x) = {1\over m} \sum_{i=1}^m H(x,z_i),$$ where the $Z_i$'s are generated from the conditional distribution $f(z|x)$. This approximation yields a convergent estimator of $h(x)$ for every value of $x$ (that is, it provides a pointwise convergent estimator), but its use in optimization setups is not recommended because, since the sample of $Z_i$'s changes with every value of $x$, using an iterative optimization algorithm over the $x$'s will result in an unstable sequence of evaluations of $h$ and thus in a rather noisy resolution to $\arg\max h(x)$.

$\endgroup$
2
  • 1
    $\begingroup$ The sampling (in terms of the quality of approximations for $P(w|D)$ ) works very well compared to many strong baselines while having a much lower memory footprint and being a bit slower. But I am not sure if what I am doing is statistically grounded. Your answer definitely helps. $\endgroup$ – user3639557 Jan 12 '17 at 13:45
  • $\begingroup$ I agree that if the chains are independent (and assuming it is okay to do the sampling of these different variables in independent chains), there should be no problem starting from the same initial state. The conditions Xi'an mentioned are of course important, but they are the same as if you started each chain from a different point. $\endgroup$ – Ruben van Bergen Jan 12 '17 at 14:02
1
$\begingroup$

Actually I guess the clarification doesn't really change my answer. If you keep re-starting your chain from the same position, this would violate the detailed balance condition: $$ q(x|y)\pi(y)=q(y|x)\pi(x) $$ Where $q$ is the proposal distribution and $\pi$ the target distribution. The reason being that $q(M_0|y)\pi(y)$ is now certainly not equal to $q(y|M_0)\pi(M_0)$. That is, since you always keep going back to $M_0$ at certain points in your chain regardless of your current state, the probability of this particular transition is completely unrelated to the probability of the transition in the opposite direction (which is essentially what you need for detailed balance).

More intuitively, your chain just wouldn't mix and explore $\pi$ properly because you keep restarting it from the same (arbitrary) starting point.

Memory shouldn't be a problem here since, if you want to compute an expectation on $w$, you only ever need to store one state of $S$ (the most recent sample), which presumably occupies no more memory than storing $M_0$.

Edit: I assumed you ultimately wanted to draw samples of $w$ and thereby approximate $p(w|D)=\int p(w|S)p(S|D)ds$, but with a bit more clarification it now seems that you want to calculate the probability of each possible value of $w$ with separate Gibbs samplings. Is there a special reason why you want to do it this way? The way I described above is more standard (and simple to implement).

$\endgroup$
3
  • $\begingroup$ I know that $M_0$ is already pretty close to the final distribution that a full MCMC chain would converge to. So, mixing at least empirically, shouldn't be an issue. The other issue regarding the memory usage, is a bit hard to explain as I have abstracted away a lot of details. But, regarding the detailed balance property, I am not sure why $q(M_0|y)\pi(y)\neq q(y|M_0)\pi(M_0)$, shouldn't this only be true only for samples in the same MCMC chain? $\endgroup$ – user3639557 Jan 12 '17 at 13:12
  • $\begingroup$ But I also fail to see the connection between detailed balance and the initial condition. $\endgroup$ – Xi'an Jan 12 '17 at 13:17
  • $\begingroup$ @user3639557: Yeah I thought what you were describing was a single chain. As I said how your approaching this problem seems a bit odd to me and I initially didn't get that you were doing it that way. That's also why I asked if there was some special reason for it. Normally how I would approach this problem would be simply: 1. Sample $S|D$ 2. Sample $w|S$ 3. Repeat 1-2 until convergence Your estimate of $p(w|D)$ would then simply be the histogram of accumulated samples of $w$. And in that case you would only ever need to store the last sample of $S$. $\endgroup$ – Ruben van Bergen Jan 12 '17 at 13:26

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.