4 ms·

I really wanted to like this article, because I came accross the term MCMC quite a bit, but never knew what it was exactly. I'm slightly disappointed, though.

by svara 9y ago

I really wanted to like this article, because I came accross the term MCMC quite a bit, but never knew what it was exactly. I'm slightly disappointed, though. Almost all of it is dedicated to introducing prerequisite terminology (prior, posterior, likelihood, markov chains) which probably a lot of readers will already be familiar with, and then the actual explanation of MCMC is just this: > To begin, MCMC methods pick a random parameter value to consider. The simulation will continue to generate random values (this is the Monte Carlo part), but subject to some rule for determining what makes a good parameter value. The trick is that, for a pair of parameter values, it is possible to compute which is a better parameter value, by computing how likely each value is to explain the data, given our prior beliefs. If a randomly generated parameter value is better than the last one, it is added to the chain of parameter values with a certain probability determined by how much better it is (this is the Markov chain part). "subject to some rule", "it is possible to"... I feel like this is really glossing over the actual explanation of how this works. Actually, I still have no idea why there is a Markov chain. What is the structure of the chain? Where does it come from and why can't we just sample the parameter without using a chain? Anyway, I appreciated most of the article and it started out really promising. It would be great if the author could try to expand on that still-baffling part ;)

contravariant 9y ago
It's a Markov chain because you use the previous sample to sample the next. A chain of random variables where each variable depends on the previous one (and only the previous one) is by definition a Markov chain. The theory of Markov chains also provides a useful theorem, which is that (under suitable conditions) the distribution of each sample converges to a particular 'limit' distribution. In fact it converges to the so called 'stationary' distribution. It's called stationary because if you start the Markov Chain at a sample from the stationary distribution then all following samples of the chain will have the exact same distribution. For the finite case, if you put the probabilities of transitioning from state i to state j in a matrix M then the stationary distribution is a vector p such that Mp = p (or pM = p depending on what convention is used). The MCMC methods consist of trying to design a Markov chain which has a useful stationary distribution. This allows you to sample the stationary distribution by sampling the Markov chain.
dablya 9y ago
If you're going to go for the "zero-math introduction", it seems only reasonable to expect some "glossing over [of] the actual explanation".
j2kun 9y ago
I humbly submit my article as an alternative. I clearly explain why there is no alternative, and give a concrete description of the markov chain. Though after the initial description of what problem MCMC is solving, I do dip into the math. https://jeremykun.com/2015/04/06/markov-chain-monte-carlo-without-all-the-bullshit/ https://jeremykun.com/2015/04/06/markov-chain-monte-carlo-wi...
- mathcomp7 9y ago
  Your article is interesting. But I see a problem in your exposition, in MCMC we don't know the probabilities of individual events. For example let p_n proportional to 1/n^3. We know that 1/n^3 converges but we don't know the sum. The key factor here is that we can compute the transition probabilities without computing the sum of the series. In the continuous variable setting we can compute the transition probabilities without computing difficult integrals. I hope you can incorporate this key factor to improve the quality of your article.
  - j2kun 9y ago
    I'm sorry but I can't make any sense of what you've written.
    - mathcomp7 9y ago
      Let X be the random variable that takes values in natural numbers n>1 with p(X=k)=A/k^3 with constant A such that sum p(X=k)=1, you can't apply MCMC with ypur explanation since you don't have an oracle for p(x=k). To apply MCMC you only need an oracle for the quotient of probabilies, here the transition probabilities are k^3/j^3 and you don't need to compute the unknown constant A.
      - j2kun 9y ago
        I don't think this distinction is key. You're talking about a detail of the Metropolis-Hastings algorithm, while I'm defining a problem that Metropolis-Hastings is one of many algorithms to solve. Sure, Metropolis-Hastings might not need an oracle, but providing an oracle doesn't make the sampling problem any easier, and the way I wrote it makes it clearer why the sampling problem is hard. "Avoiding a difficult integral" is an engineering detail.
kgwgk 9y ago
You can not sample the distribution directly when “it is impossible to solve for analytically”. There are a few methods to overcome this issue, in particular “MCMC methods allow us to estimate the shape of a posterior distribution in case we can’t compute it directly”. You only need to be able to compute the relative values of the function you want to integrate (in this case a probability density) at the current point and the proposed destination. Where is this function coming from is not relevant to understand MCMC methods, they can be applied in many problems unrelated to Bayesian statistics. Here is another (non-zero-math) introduction to the topic: https://arxiv.org/pdf/cond-mat/9612186.pdf https://arxiv.org/pdf/cond-mat/9612186.pdf https://www.coursera.org/learn/statistical-mechanics/lecture/rWoI7/lecture-1-introduction-to-monte-carlo-algorithms https://www.coursera.org/learn/statistical-mechanics/lecture...
gwern 9y ago
I think probably the single most intuitive way of implementing a Bayesian model for a programmer is ABC: https://en.wikipedia.org/wiki/Approximate_Bayesian_computation https://en.wikipedia.org/wiki/Approximate_Bayesian_computati... because it is generative and inherently algorithmic. I wonder if there is a good tutorial way of starting with ABC and developing into MCMC and other more efficient methods? It's easy to transition from simple Monte Carlo methods to ABC rejection sampling, but I'm not sure how to link up ABC and MCMC (in part because I don't grok MCMC myself well enough to explain it).
billf1953 9y ago
This is like describing a painting to a blind person. Describing "a dust-covered sunflower" as a "yellow flower" doesn't much help the blind person and certainly doesn't help the sighted.
cosmic_ape 9y ago
>>Actually, I still have no idea why there is a Markov chain. What is the structure of the chain? Where does it come from and why can't we just sample the parameter without using a chain? If the parameter can be sampled from the posterior directly, then no chain is usually needed, just sample it. However, most often you can not directly sample from the posterior. Note that this is not necessarily because "posterior is hard to analytically compute". Most times you know the analytical expression for the posterior distribution (up to the normalization constant) but this does not mean you can generate samples from it easily. So, instead, you construct a Markov chain, from which you can sample easily, and which has the property that in the limit its distribution coincides with your posterior. Then you sample the chain for a long time an hope for the best. Any chain for which you can show that its stationary distribution is the posterior works in principle. But some chains are better than others. There are also some generic ways to construct such chains, most famous are the Gibbs and the Metropolis-Hastings samplers. Finally, do not sample blogs by "wikipedia researchers". Sample books like "Bayesian Data Analysis" by Gelman et al. They will not lie to you.

by svara 9y ago

contravariant 9y ago

It's a Markov chain because you use the previous sample to sample the next. A chain of random variables where each variable depends on the previous one (and only the previous one) is by definition a Markov chain. The theory of Markov chains also provides a useful theorem, which is that (under suitable conditions) the distribution of each sample converges to a particular 'limit' distribution. In fact it converges to the so called 'stationary' distribution. It's called stationary because if you start the Markov Chain at a sample from the stationary distribution then all following samples of the chain will have the exact same distribution. For the finite case, if you put the probabilities of transitioning from state i to state j in a matrix M then the stationary distribution is a vector p such that Mp = p (or pM = p depending on what convention is used). The MCMC methods consist of trying to design a Markov chain which has a useful stationary distribution. This allows you to sample the stationary distribution by sampling the Markov chain.

dablya 9y ago

If you're going to go for the "zero-math introduction", it seems only reasonable to expect some "glossing over [of] the actual explanation".

j2kun 9y ago

I humbly submit my article as an alternative. I clearly explain why there is no alternative, and give a concrete description of the markov chain. Though after the initial description of what problem MCMC is solving, I do dip into the math. https://jeremykun.com/2015/04/06/markov-chain-monte-carlo-without-all-the-bullshit/ https://jeremykun.com/2015/04/06/markov-chain-monte-carlo-wi...

mathcomp7 9y ago
Your article is interesting. But I see a problem in your exposition, in MCMC we don't know the probabilities of individual events. For example let p_n proportional to 1/n^3. We know that 1/n^3 converges but we don't know the sum. The key factor here is that we can compute the transition probabilities without computing the sum of the series. In the continuous variable setting we can compute the transition probabilities without computing difficult integrals. I hope you can incorporate this key factor to improve the quality of your article.
- j2kun 9y ago
  I'm sorry but I can't make any sense of what you've written.
  - mathcomp7 9y ago
    Let X be the random variable that takes values in natural numbers n>1 with p(X=k)=A/k^3 with constant A such that sum p(X=k)=1, you can't apply MCMC with ypur explanation since you don't have an oracle for p(x=k). To apply MCMC you only need an oracle for the quotient of probabilies, here the transition probabilities are k^3/j^3 and you don't need to compute the unknown constant A.
    - j2kun 9y ago
      I don't think this distinction is key. You're talking about a detail of the Metropolis-Hastings algorithm, while I'm defining a problem that Metropolis-Hastings is one of many algorithms to solve. Sure, Metropolis-Hastings might not need an oracle, but providing an oracle doesn't make the sampling problem any easier, and the way I wrote it makes it clearer why the sampling problem is hard. "Avoiding a difficult integral" is an engineering detail.

kgwgk 9y ago

You can not sample the distribution directly when “it is impossible to solve for analytically”. There are a few methods to overcome this issue, in particular “MCMC methods allow us to estimate the shape of a posterior distribution in case we can’t compute it directly”. You only need to be able to compute the relative values of the function you want to integrate (in this case a probability density) at the current point and the proposed destination. Where is this function coming from is not relevant to understand MCMC methods, they can be applied in many problems unrelated to Bayesian statistics. Here is another (non-zero-math) introduction to the topic: https://arxiv.org/pdf/cond-mat/9612186.pdf https://arxiv.org/pdf/cond-mat/9612186.pdf https://www.coursera.org/learn/statistical-mechanics/lecture/rWoI7/lecture-1-introduction-to-monte-carlo-algorithms https://www.coursera.org/learn/statistical-mechanics/lecture...

gwern 9y ago

I think probably the single most intuitive way of implementing a Bayesian model for a programmer is ABC: https://en.wikipedia.org/wiki/Approximate_Bayesian_computation https://en.wikipedia.org/wiki/Approximate_Bayesian_computati... because it is generative and inherently algorithmic. I wonder if there is a good tutorial way of starting with ABC and developing into MCMC and other more efficient methods? It's easy to transition from simple Monte Carlo methods to ABC rejection sampling, but I'm not sure how to link up ABC and MCMC (in part because I don't grok MCMC myself well enough to explain it).

billf1953 9y ago

This is like describing a painting to a blind person. Describing "a dust-covered sunflower" as a "yellow flower" doesn't much help the blind person and certainly doesn't help the sighted.

cosmic_ape 9y ago

>>Actually, I still have no idea why there is a Markov chain. What is the structure of the chain? Where does it come from and why can't we just sample the parameter without using a chain? If the parameter can be sampled from the posterior directly, then no chain is usually needed, just sample it. However, most often you can not directly sample from the posterior. Note that this is not necessarily because "posterior is hard to analytically compute". Most times you know the analytical expression for the posterior distribution (up to the normalization constant) but this does not mean you can generate samples from it easily. So, instead, you construct a Markov chain, from which you can sample easily, and which has the property that in the limit its distribution coincides with your posterior. Then you sample the chain for a long time an hope for the best. Any chain for which you can show that its stationary distribution is the posterior works in principle. But some chains are better than others. There are also some generic ways to construct such chains, most famous are the Gibbs and the Metropolis-Hastings samplers. Finally, do not sample blogs by "wikipedia researchers". Sample books like "Bayesian Data Analysis" by Gelman et al. They will not lie to you.