8 ms·

Markov Chain Monte Carlo for Bayesian Inference – The Metropolis Algorithm

87 points by shogunmike 10y ago

warrenmar 10y ago
Not to hijack this post, but I'm saddened every time I see anything monte carlo related referred to as the metropolis algorithm. When you're the boss, what you say goes. http://andrewgelman.com/2014/06/30/invented-metropolis-algorithm/ http://andrewgelman.com/2014/06/30/invented-metropolis-algor...
- shogunmike 10y ago
  There is also a bit of historical discussion on Wikipedia about this: https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm#History https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_al...
constantlm 10y ago
This is so incredibly far over my head.
- adenadel 10y ago
  This could potentially help http://jeremykun.com/2015/04/06/markov-chain-monte-carlo-without-all-the-bullshit/ http://jeremykun.com/2015/04/06/markov-chain-monte-carlo-wit... If you're unfamiliar with Bayes Theorem and Bayesian inference the earlier articles from the OP might help.
  - shogunmike 10y ago
    Also, John Kruschke's "Doing Bayesian Data Analysis", aka the "Puppy Book", is a gentle introduction to Bayesian inference. It is very readable, especially with regards MCMC.
- douche 10y ago
  Yup, going to have to save this for later... I vaguely remember a Metropolis Light Transport from my college graphics course, which I assume uses similar sampling methodology
  - agumonkey 10y ago
    I came here to .. too late.
- doug1001 10y ago
  it's not. set aside for a moment the prose description, find an MH module in your language of choice and study the code then play around w/ it in the REPL. A couple of things will probably surprise you when you look at an MCMC implementation (either MH or Gibbs): (i) very compact (eg, MH ~ 40 loc in python; 120 in scala; Gibbs ~10 lines in python, ~40 in scala); and (ii) the primary data structures are ones you probably use every day (eg, 2D array, which is used to represent the transition probabilities among the nodes comprising the graph that models the random walk). (A python/numpy implementation of MH: http://isaacslavitt.com/2013/12/30/metropolis-hastings-and-slice-sampling/ http://isaacslavitt.com/2013/12/30/metropolis-hastings-and-s...)
Houshalter 10y ago
I'm sad that every explanation of MCMC uses complicated symbolic explanations. I was trying to explain it once and came up with a fairly intuitive way to visualize it. Probably that is the way it was first discovered, though who knows. In words, you can visualize it as doing a random walk around the area of a probability graph. Then it just turns into an explanation of why random walks accurately sample from an area, and the various tricks used in MCMC methods to make random walks more efficient. Relatedly, bayes theorem makes much more sense when you visualize it, e.g. this post: https://oscarbonilla.com/2009/05/visualizing-bayes-theorem/ https://oscarbonilla.com/2009/05/visualizing-bayes-theorem/

87 points by shogunmike 10y ago

Not to hijack this post, but I'm saddened every time I see anything monte carlo related referred to as the metropolis algorithm. When you're the boss, what you say goes. http://andrewgelman.com/2014/06/30/invented-metropolis-algorithm/ http://andrewgelman.com/2014/06/30/invented-metropolis-algor...

shogunmike 10y ago
There is also a bit of historical discussion on Wikipedia about this: https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm#History https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_al...

constantlm 10y ago

This is so incredibly far over my head.

adenadel 10y ago
This could potentially help http://jeremykun.com/2015/04/06/markov-chain-monte-carlo-without-all-the-bullshit/ http://jeremykun.com/2015/04/06/markov-chain-monte-carlo-wit... If you're unfamiliar with Bayes Theorem and Bayesian inference the earlier articles from the OP might help.
- shogunmike 10y ago
  Also, John Kruschke's "Doing Bayesian Data Analysis", aka the "Puppy Book", is a gentle introduction to Bayesian inference. It is very readable, especially with regards MCMC.
douche 10y ago
Yup, going to have to save this for later... I vaguely remember a Metropolis Light Transport from my college graphics course, which I assume uses similar sampling methodology
- agumonkey 10y ago
  I came here to .. too late.
doug1001 10y ago
it's not. set aside for a moment the prose description, find an MH module in your language of choice and study the code then play around w/ it in the REPL. A couple of things will probably surprise you when you look at an MCMC implementation (either MH or Gibbs): (i) very compact (eg, MH ~ 40 loc in python; 120 in scala; Gibbs ~10 lines in python, ~40 in scala); and (ii) the primary data structures are ones you probably use every day (eg, 2D array, which is used to represent the transition probabilities among the nodes comprising the graph that models the random walk). (A python/numpy implementation of MH: http://isaacslavitt.com/2013/12/30/metropolis-hastings-and-slice-sampling/ http://isaacslavitt.com/2013/12/30/metropolis-hastings-and-s...)

Houshalter 10y ago

I'm sad that every explanation of MCMC uses complicated symbolic explanations. I was trying to explain it once and came up with a fairly intuitive way to visualize it. Probably that is the way it was first discovered, though who knows. In words, you can visualize it as doing a random walk around the area of a probability graph. Then it just turns into an explanation of why random walks accurately sample from an area, and the various tricks used in MCMC methods to make random walks more efficient. Relatedly, bayes theorem makes much more sense when you visualize it, e.g. this post: https://oscarbonilla.com/2009/05/visualizing-bayes-theorem/ https://oscarbonilla.com/2009/05/visualizing-bayes-theorem/