3
$\begingroup$

In order to implement the MH algorithm you need a proposal density or jumping distribution $q(⋅|⋅)$, from which it is easy to sample. If you want to sample from a distribution $f(⋅)$, the MH algorithm can be implemented as follows:

  1. Pick a initial random state $x_0$.
  2. Generate a candidate $x^*$ from $q(⋅|x_0)$.
  3. Calculate the ratio $\alpha=\frac{f(x^*)}{f(x_0)} \frac{q(x_0|x^*)}{q(x^*|x_0)}$.
  4. Accept $x^*$ as a realisation of f with probability min(1,α).
  5. Take $x^*$ as the new initial state and continue sampling until you get the desired sample size.

$q$ is often symmetrical so $\frac{q(x^*|x_0)}{q(x_0|x^*)}=1$

I have two questions :

  1. Does $q$ describe the Birth-or-Death move that is often associated with Metropolis Hastings algorithm? When would you want to take $q$ non symmetrical? A colleague of mine wants to implement MH for sampling from a complex distribution (Y is a sample from X with a distribution $f$), and said he would impose different probabilities of picking $u$ in $X-Y$ to make the chain converge quicker (with Y the sample at a time and $\{Y-{v}\}\cup{\{u\}}$ the sample retained the next time if the ratio is big enough at step 3). Is it standard?

  2. The context in which I personally use MH algorithm is for Bayesian model averaging. In this context, I have some models $M_i$ with an a priori probability $\pi$, some data D and an a posteriori probability I want to sample from. So the ratio of the 3th step of the algorithm becomes $\frac{f(D|M_i)\pi(M_i)}{f(D|M_j) \pi(M_j)}$ (Bayes formula). Do you agree that $q$ in this case is still about the modification of $M_i$ between two iterations and the Bayesian context doesn't change anything about it? Shouldn't my colleague adopt a Bayesian approach and choose a a priori distribution on the observations to favour those he wants to select more often rather than changing the jumping distribution?

Sorry for the naive questions, I want to be sure I understood the algorithm.

EDIT : some of you say there is no link between MH and Birth-death moves, but here is what is explained in the vignette of the BMS package I use :

"In addition to enumerating all models, BMS implements two MCMC samplers that differ in the way they propose candidate models:

  • Birth-death sampler (bd): This is the standard model sampler used in most BMA routines. One of the K potential covariates is randomly chosen; if the chosen covariate forms already part of the current model Mi, then the candidate model Mj will have the same set of covariates as Mi but for the chosen variable ('dropping' a variable). If the chosen covariate is not contained in Mi, then the candidate model will contain all the variables from Mi plus the chosen covariate ('adding' a variable).

  • Reversible-jump sampler (rev.jump): Adapted to BMA by Madigan and York (1995) this sampler either draws a candidate by the birth-death method with 50% probability. In the other case (chosen with 50% probability) a 'swap' is proposed, i.e. the candidate model Mj randomly drops one covariate with respect to Mi and randomly adds one chosen at random from the potential covariates that were not included in model Mi.

  • Enumeration (enum): Up to fourteen covariates, complete enumeration of all models is the default option: This means that instead of an approximation by means of the aforementioned MCMC sampling schemes all possible models are evaluated. As enumeration becomes quite time-consuming or infeasible for many variables, the default option is mcmc="bd" in case of K > 14, though enumeration can still be invoked with the command mcmc="enumerate"."

I just want to know if there is a link between the sampling option and $q$.

$\endgroup$
  • 1
    $\begingroup$ I'll come back to this question later, but you should really look at the original paper. It explains everything from scratch pretty well. $\endgroup$ – Neil G Feb 24 '16 at 11:35
  • $\begingroup$ @Xi'an, yes I get that, but what is the link with q ? $\endgroup$ – Stéphanie C Feb 24 '16 at 16:44
  • $\begingroup$ In both Birth-and-death and for the more general reversible jump sampler, you have to pick a proposal $q$ that is most often non-symmetric because there usually are more ways to kill one term than to add one term. $\endgroup$ – Xi'an Feb 24 '16 at 17:01
  • $\begingroup$ Ok but q is exactly what defines the sampler, right ? $\endgroup$ – Stéphanie C Feb 24 '16 at 17:25
  • 1
    $\begingroup$ As pointed out by Neil G. in his answer, those are different issues: if you want to penalise non-sparse models, your prior $\pi$ should reflect this. The choice of $q$ is important in exploring the space of models faster and focussing on those with high posterior probability. A major change in $\pi$ should induce a major change in $q$ to keep the efficiency high. $\endgroup$ – Xi'an Feb 24 '16 at 18:35
2
$\begingroup$

As signalled by bdeonovic, there seems to be some confusion in your understanding of Metropolis-Hastings algorithms. What you describe is the standard version of the algorithm where both target $f$ and proposal $q(\cdot|x)$ are densities against the same dominating measure (e.g., the Lebesgue measure). In this framework, the proposal $q(\cdot|x)$ can be absolutely anything and be chosen in terms of the target $f$ [and of the observations in a Bayesian setting] and of its mixing performances. For instance, when $q(\cdot|x)$ is a random walk, the scale of the random walk can be selected for the acceptance rate to stay around 0.234. But non-symmetric versions are also available like the Metropolis-adjusted Langevin (MALA) algorithm which is asymmetric and aims at bringing the chain towards the mode(s) of the target $f$.

You seem to be interested in model choice, where the measure issues are much more complicated because the target is defined on a space of varying dimension, with the measure being a direct sum of measures. thus requiring the move to be equally measurable against this sum. Green (1995) managed to formalise this requirement into a valid framework and produced the reversible jump Metropolis-Hastings algorithm, which works by pairs of models and spaces and proposals. While the implementation can be brought down to a reasonable level of difficulty, the presentation of the algorithm does not fit in a forum answer. I thus suggest you read the reference by Green (1995) or a book like my book with George Casella (2004, Chap. 11).

As for your question #2, if you can compare directly the models via the marginal likelihoods $p(D|M_i)$, there is no need for reversible jump as you are working on a finite or countably discrete space of model indices. Any proposal exploring this space produces a valid Markov chain on the model indices but in cases you can compute directly those probabilities $p(D|M_i)\pi(M_i)$ there is even no need for MCMC since all you have to do is select the highest value or average across models. If you cannot list (and compare) all models, you need a proposal $q$ that considers enough model indices at once to guarantee irreducibility of the resulting Markov chain: since $q$ can be asymmetric, it should appear in the ratio.

$\endgroup$
  • $\begingroup$ I don't understand your last paragraph, in my context MCMC is used to avoid testing all the models since the dimension of the space may be very high, right ? $\endgroup$ – Stéphanie C Feb 24 '16 at 15:26
  • $\begingroup$ I edited my question to clarify $\endgroup$ – Stéphanie C Feb 24 '16 at 15:29
  • $\begingroup$ Do you mean the number of models can be very high? $\endgroup$ – Xi'an Feb 24 '16 at 15:29
  • $\begingroup$ yes, for k regressors, you can have 2^k models $\endgroup$ – Stéphanie C Feb 24 '16 at 16:44
1
$\begingroup$
  1. $q$ is the proposal distribution. I've only ever seen symmetric $q$, but it's okay to make it asymmetrical since you're dividing the ratio out in $\alpha$. It's normal to choose $q$ so that the chain converges more quickly. If $q$ is too wide, then you have a lot of rejected points, and if it's too narrow, it takes a long time to explore the high probability areas.

  2. $q$ has nothing to do with your $\pi$ or $f$ or $M$. The $f$ in step 3 is your Bayesian posterior (likelihood times prior). Changing $q$ should not affect your sampled distribution (if it does, that's a bad $q$, and you would have to pick a weird $q$ for that to happen.)

$\endgroup$
  • $\begingroup$ Ok, so far I am reassured by your answer : so does q describe the Birth-or-Death move that is often associated with metropolis hastings algorithm? $\endgroup$ – Stéphanie C Feb 24 '16 at 12:56
  • 2
    $\begingroup$ I don't think the standard Metropolis-Hastings algorithm has anything similar to the concept of birth-death moves. This sounds like Reverse-Jump Markov Chain Monte Carlo (RJMCMC) $\endgroup$ – bdeonovic Feb 24 '16 at 13:02
  • $\begingroup$ I edited my question to clarify $\endgroup$ – Stéphanie C Feb 24 '16 at 15:29
1
$\begingroup$

I would add to other answers that $q$ can be chosen as asymmetric when the support of the prior for a given parameter is restricted. For example, if $p(\theta<0)=0$ then it could be interesting to choose a proposal avoiding negative $\theta$ e.g. using $q(.|x)$ as a gaussian density with location parameter $x$ truncated on $R^+$. In such a case $q(x_1|x_2) \ne q(x_2|x_1)$. This can easily noticed by considering that in a truncated normal density, the value of the location parameter appears in the normalisation constant of the density (and is thus different in $q(.|x_2)$ and $q(.|x_1)$).

$\endgroup$

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.