9 ms·

Markov Chain Monte Carlo: Burn-In Is Unnecessary

62 points by spekcular 6y ago

activatedgeek 6y ago
For the interested, here is a classic article that goes into more depth: _Practical Markov Chain Monte Carlo_ [1]. [1]: https://projecteuclid.org/euclid.ss/1177011137 https://projecteuclid.org/euclid.ss/1177011137
text70 6y ago
Interesting theory. So does this mean that quasi-supervised learning can be quicker than unsupervised ML when using Monte-Carlo methods?
credit_guy 6y ago
This is plain silly. If you don't have burn in, you bias your estimate. Sure, in the long run the bias becomes smaller and smaller, but, as the saying goes, in the long run we are all dead. MCMC is generally slow, any way to speed it up a bit is good. Throwing away the burn-in part of the chain is just such a way to speed it up.
- justindomke 6y ago
  A helpful way to think about burn-in is that you probably don't care about bias as such but rather error which is a combination of bias and variance. Burn-in reduces bias at the cost of variance (since you have fewer points in your final estimates). My intuition is you want to be somewhere in the middle of the tradeoff. You want to tolerate some bias -- use burn-in to get partway but only partway to the stationary distribution. Here's a paper that advances this way of thinking: http://web.stanford.edu/~ngoodman/papers/LiederGriffithsGoodman2013NIPS.pdf http://web.stanford.edu/~ngoodman/papers/LiederGriffithsGood...
- DiogenesKynikos 6y ago
  The author's proposal to start at a high-probability-density (HPD) point reduces the bias that you get from not doing burn-in, but it still creates a bias. In order to get a reasonable answer from MCMC, you need to run for many correlation times. Burn-in should only last a few correlation times, so you don't lose that large a fraction of your chain by throwing it away. And the part of the chain you're using is biased, so you're probably not gaining anything by keeping it.
- asdf_snar 6y ago
  I think Geyer's point is that if you generate samples X_0, ..., X_b where b>0 is a burn-in time, and start collecting estimates at time t>b, then that's not somehow better than starting at X_b and not burning in (the two are equal in distribution).
  - contravariant 6y ago
    The problem there is that (assuming a source of true noise) X_b is a random variable, in fact if b is sufficiently high its distribution approximates your target distribution pretty well. So if you're arguing "instead of burn-in you can also use an approximate sample of your target distribution" then that's technically correct. However generating an approximate sample is the exact problem that a MCMC process is trying to solve.
    - asdf_snar 6y ago
      Of course, you are right. I recall Geyer at some point writing some people thought there was a difference between having a burn-in period that happened to have X_b = x_b, and simply starting with X_0 = x_b. I can't find that on this page though.
      - contravariant 6y ago
        I see, you're right that those two are entirely equivalent (it's what makes the Markov chain 'Markov'). And using an approximate sample instead of burn-in isn't entirely without merit, though I think I've only seen that being used with things like Brownian motion where the trajectory is the thing of interest, rather than the samples themselves.
      - jmmcd 6y ago
        Yes, he writes "If you start at x and I start at x then your MCMC run is no better than mine." and surrounding text is making this point.
  - derbOac 6y ago
    At that point, though, isn't it just semantics? If you have a chain, and throw out the beginning fraction, is that any more burnin than starting with X_b, which you probably had to find using some period of... burnin? This is really all about time series heterogeneity which is a topic unto itself. Eventually the chain reaches some stationary distribution but in the meantime there will be some shift in the distribution potentially. Seems like you could model the chain to do some test of where the distribution shifts, if at all. I imagine this is in the literature. Giving it a brief look I can't find anything but I haven't looked hard enough.
ellisv 6y ago
I disagree with Geyer on this. Burn-in may not be necessary but often is for the type of inference that most people are familiar with. But these days, who cares? I can fit a highly parameter used model on my 6 year old MacBook Pro with Stan just fine. If I want some extra juice I can rent an EC2 or Droplet.
rich_sasha 6y ago
I'm not too sure about this. Isn't the usual derivation of MCMC methods based on equilibrium distribution of the chain? So you either need to run the chain for a (unknowably) long time to achieve equilibrium (hence burn-in) or start from an equilibrium distribution - but if you knew that, you wouldn't be running MCMC. And sure, we can never tell the chain has achieved equilibrium, but that's better than calling any odd point 'equilibrium'. He does mention this stream of thought but dismisses it out of hand, without an explanation.
aimless_infamy 6y ago
I particularly like the suggestion of not doing burn-in and instead starting your chain where the last one ended. Is that not simply doing a burn-in of many thousands? Fully agree with everyone else. The argument "asymptotically the burn in doesn't matter so don't do it" misses a few key points -- like about how I'm not going to get to the limit, and I certainly won't _know_ I get to the limit.
- mcmcrulz 6y ago
  NO! The point of multiple chains is to test for convergence. If you start four chains at four random points in probability space and they all converge to same distribution, you can be confident in the result, but many times that fails to occur. This is what the rhat diagnostic shows. If you calculate rhat with one big chain it will mislead you. This is terrible advice.
mattb314 6y ago
I think I generally agree with the majority of the comments here that burn in can serve a useful purpose (especially if you can't find a high probability density point to start from), but I also wonder: if burn-in vs no burn-in makes a large difference in your outcome, aren't you likely just not running your chain long enough? Sure, if you choose a bad starting point, your initial samples might not be representative of the overall distribution, but if a handful of non-representative points can massively impact your result, then I'm not sure how stable your result was to begin with (how do you know there isn't some other set of low-probability high-impact points that your sampler just missed through luck?). People tend to have a cognitive bais towards distributions looking pretty (eg not having random chains off to the side as in the article), but I'm not sure it makes a real difference. That said, I do think burn in is a pretty reasonable way to find a good starting point if you don't have existing knowledge about the distribution. From a practical standpoint, has anyone actually seen a massive difference between runs with/without burn in? kinda curious how often it really matters
- bachmeier 6y ago
  > Sure, if you choose a bad starting point, your initial samples might not be representative of the overall distribution, but if a handful of non-representative points can massively impact your result, then I'm not sure how stable your result was to begin with (how do you know there isn't some other set of low-probability high-impact points that your sampler just missed through luck?). You're right, and most comments I've seen over the years on the post conveniently miss that he addresses that: > This unbiasedness argument is rubbish. If you start at x and I start at x then your MCMC run is no better than mine. If you used burn-in and I didn't, then you are entitled to woof about approximate unbiasedness and I am not. But that woof does not make your estimator any better. My interpretation has always been this, and I think it's correct: You need a good starting point. There's no reason to think burn-in gives you a good starting point. Instead, use something that's actually intended to give a good starting point, like the mode.
  - radford-neal 6y ago
    For difficult problems, find the mode may (a) be as hard to find, or harder, as doing an MCMC sampling run, (b) be completely unrepresentative of the overall distribution.
radford-neal 6y ago
This rant is rather misguided. For easy problems, it doesn't much matter what you do, as long as you don't limit your computation time to some unnecessarily-small amount. So let's assume you're trying to sample from some complicated distribution that you don't know much about, and for which you don't know how well your Markov Chain mixes. It is then highly likely that whatever point you start at, regardless of good intentions, is not representative of the distribution (saying it's a possible point is obtuse). You don't want to include that point in your estimates. Hence you want to discard burn-in. By the way, a kernel of truth in the rant (though not actually mentioned) is that if you are using just one chain, you should not discard more than about 20% as burn in. If you are tempted to discard 50%, then you don't really know that the chain has come close to convergence. You may say, "this function of state is near 20 for the first half, then drops to around 10 for the second half, so I'll discard the first half as burn-in". But you're fooling yourself. For all you know, if you ran the chain longer, it might go back to a state where the value is 20, moving back and forth between these two modes, and by discarding the first half, you're throwing out half the distribution, getting drastically wrong results. (The longer the chain stays at around 10, the less chance of this being true, which is why discarding 20% as burn-in could make sense.) An exception would be if you had good prior reason to think the first 50% couldn't be representative of the distribution, but in that case too you'd be better off running for longer (if at all possible) to make sure the second half isn't also unrepresentative. However, if you're trying to be as sure as you can that you're getting the right result, you should be running more than one chain, even though they'll have to be shorter (given a fixed budget). Geyer rants against this too, on the basis that using all your computational budget for one run gives the greatest chance of convergence, but this makes no practical sense. At a minimum, along with your long run, you'd want to to do a few extra short runs to see if they end up going to radically different values that are never visited in the long run - in which case you'll have to rethink the whole thing. A good general guide would be to run something like 5 to 10 chains, for equal time, and checking whether they seem to have converged to the same distribution. (If not, you need a better Markov chain, or a faster computer.) Of course, doing a huge number of short runs is also bad. Moderation is good.
- fanboi98765 6y ago
  Wow! Thank you professor Neal! Inspiring that the father of modern MCMC techniques takes the time to correct bad takes on hacker news!

62 points by spekcular 6y ago

For the interested, here is a classic article that goes into more depth: _Practical Markov Chain Monte Carlo_ [1]. [1]: https://projecteuclid.org/euclid.ss/1177011137 https://projecteuclid.org/euclid.ss/1177011137

text70 6y ago

Interesting theory. So does this mean that quasi-supervised learning can be quicker than unsupervised ML when using Monte-Carlo methods?

credit_guy 6y ago

This is plain silly. If you don't have burn in, you bias your estimate. Sure, in the long run the bias becomes smaller and smaller, but, as the saying goes, in the long run we are all dead. MCMC is generally slow, any way to speed it up a bit is good. Throwing away the burn-in part of the chain is just such a way to speed it up.

justindomke 6y ago
A helpful way to think about burn-in is that you probably don't care about bias as such but rather error which is a combination of bias and variance. Burn-in reduces bias at the cost of variance (since you have fewer points in your final estimates). My intuition is you want to be somewhere in the middle of the tradeoff. You want to tolerate some bias -- use burn-in to get partway but only partway to the stationary distribution. Here's a paper that advances this way of thinking: http://web.stanford.edu/~ngoodman/papers/LiederGriffithsGoodman2013NIPS.pdf http://web.stanford.edu/~ngoodman/papers/LiederGriffithsGood...
DiogenesKynikos 6y ago
The author's proposal to start at a high-probability-density (HPD) point reduces the bias that you get from not doing burn-in, but it still creates a bias. In order to get a reasonable answer from MCMC, you need to run for many correlation times. Burn-in should only last a few correlation times, so you don't lose that large a fraction of your chain by throwing it away. And the part of the chain you're using is biased, so you're probably not gaining anything by keeping it.
asdf_snar 6y ago
I think Geyer's point is that if you generate samples X_0, ..., X_b where b>0 is a burn-in time, and start collecting estimates at time t>b, then that's not somehow better than starting at X_b and not burning in (the two are equal in distribution).
- contravariant 6y ago
  The problem there is that (assuming a source of true noise) X_b is a random variable, in fact if b is sufficiently high its distribution approximates your target distribution pretty well. So if you're arguing "instead of burn-in you can also use an approximate sample of your target distribution" then that's technically correct. However generating an approximate sample is the exact problem that a MCMC process is trying to solve.
  - asdf_snar 6y ago
    Of course, you are right. I recall Geyer at some point writing some people thought there was a difference between having a burn-in period that happened to have X_b = x_b, and simply starting with X_0 = x_b. I can't find that on this page though.
    - contravariant 6y ago
      I see, you're right that those two are entirely equivalent (it's what makes the Markov chain 'Markov'). And using an approximate sample instead of burn-in isn't entirely without merit, though I think I've only seen that being used with things like Brownian motion where the trajectory is the thing of interest, rather than the samples themselves.
    - jmmcd 6y ago
      Yes, he writes "If you start at x and I start at x then your MCMC run is no better than mine." and surrounding text is making this point.
- derbOac 6y ago
  At that point, though, isn't it just semantics? If you have a chain, and throw out the beginning fraction, is that any more burnin than starting with X_b, which you probably had to find using some period of... burnin? This is really all about time series heterogeneity which is a topic unto itself. Eventually the chain reaches some stationary distribution but in the meantime there will be some shift in the distribution potentially. Seems like you could model the chain to do some test of where the distribution shifts, if at all. I imagine this is in the literature. Giving it a brief look I can't find anything but I haven't looked hard enough.

ellisv 6y ago

I disagree with Geyer on this. Burn-in may not be necessary but often is for the type of inference that most people are familiar with. But these days, who cares? I can fit a highly parameter used model on my 6 year old MacBook Pro with Stan just fine. If I want some extra juice I can rent an EC2 or Droplet.

rich_sasha 6y ago

I'm not too sure about this. Isn't the usual derivation of MCMC methods based on equilibrium distribution of the chain? So you either need to run the chain for a (unknowably) long time to achieve equilibrium (hence burn-in) or start from an equilibrium distribution - but if you knew that, you wouldn't be running MCMC. And sure, we can never tell the chain has achieved equilibrium, but that's better than calling any odd point 'equilibrium'. He does mention this stream of thought but dismisses it out of hand, without an explanation.

aimless_infamy 6y ago

I particularly like the suggestion of not doing burn-in and instead starting your chain where the last one ended. Is that not simply doing a burn-in of many thousands? Fully agree with everyone else. The argument "asymptotically the burn in doesn't matter so don't do it" misses a few key points -- like about how I'm not going to get to the limit, and I certainly won't _know_ I get to the limit.

mcmcrulz 6y ago
NO! The point of multiple chains is to test for convergence. If you start four chains at four random points in probability space and they all converge to same distribution, you can be confident in the result, but many times that fails to occur. This is what the rhat diagnostic shows. If you calculate rhat with one big chain it will mislead you. This is terrible advice.

mattb314 6y ago

I think I generally agree with the majority of the comments here that burn in can serve a useful purpose (especially if you can't find a high probability density point to start from), but I also wonder: if burn-in vs no burn-in makes a large difference in your outcome, aren't you likely just not running your chain long enough? Sure, if you choose a bad starting point, your initial samples might not be representative of the overall distribution, but if a handful of non-representative points can massively impact your result, then I'm not sure how stable your result was to begin with (how do you know there isn't some other set of low-probability high-impact points that your sampler just missed through luck?). People tend to have a cognitive bais towards distributions looking pretty (eg not having random chains off to the side as in the article), but I'm not sure it makes a real difference. That said, I do think burn in is a pretty reasonable way to find a good starting point if you don't have existing knowledge about the distribution. From a practical standpoint, has anyone actually seen a massive difference between runs with/without burn in? kinda curious how often it really matters

bachmeier 6y ago
> Sure, if you choose a bad starting point, your initial samples might not be representative of the overall distribution, but if a handful of non-representative points can massively impact your result, then I'm not sure how stable your result was to begin with (how do you know there isn't some other set of low-probability high-impact points that your sampler just missed through luck?). You're right, and most comments I've seen over the years on the post conveniently miss that he addresses that: > This unbiasedness argument is rubbish. If you start at x and I start at x then your MCMC run is no better than mine. If you used burn-in and I didn't, then you are entitled to woof about approximate unbiasedness and I am not. But that woof does not make your estimator any better. My interpretation has always been this, and I think it's correct: You need a good starting point. There's no reason to think burn-in gives you a good starting point. Instead, use something that's actually intended to give a good starting point, like the mode.
- radford-neal 6y ago
  For difficult problems, find the mode may (a) be as hard to find, or harder, as doing an MCMC sampling run, (b) be completely unrepresentative of the overall distribution.

radford-neal 6y ago

This rant is rather misguided. For easy problems, it doesn't much matter what you do, as long as you don't limit your computation time to some unnecessarily-small amount. So let's assume you're trying to sample from some complicated distribution that you don't know much about, and for which you don't know how well your Markov Chain mixes. It is then highly likely that whatever point you start at, regardless of good intentions, is not representative of the distribution (saying it's a possible point is obtuse). You don't want to include that point in your estimates. Hence you want to discard burn-in. By the way, a kernel of truth in the rant (though not actually mentioned) is that if you are using just one chain, you should not discard more than about 20% as burn in. If you are tempted to discard 50%, then you don't really know that the chain has come close to convergence. You may say, "this function of state is near 20 for the first half, then drops to around 10 for the second half, so I'll discard the first half as burn-in". But you're fooling yourself. For all you know, if you ran the chain longer, it might go back to a state where the value is 20, moving back and forth between these two modes, and by discarding the first half, you're throwing out half the distribution, getting drastically wrong results. (The longer the chain stays at around 10, the less chance of this being true, which is why discarding 20% as burn-in could make sense.) An exception would be if you had good prior reason to think the first 50% couldn't be representative of the distribution, but in that case too you'd be better off running for longer (if at all possible) to make sure the second half isn't also unrepresentative. However, if you're trying to be as sure as you can that you're getting the right result, you should be running more than one chain, even though they'll have to be shorter (given a fixed budget). Geyer rants against this too, on the basis that using all your computational budget for one run gives the greatest chance of convergence, but this makes no practical sense. At a minimum, along with your long run, you'd want to to do a few extra short runs to see if they end up going to radically different values that are never visited in the long run - in which case you'll have to rethink the whole thing. A good general guide would be to run something like 5 to 10 chains, for equal time, and checking whether they seem to have converged to the same distribution. (If not, you need a better Markov chain, or a faster computer.) Of course, doing a huge number of short runs is also bad. Moderation is good.

fanboi98765 6y ago
Wow! Thank you professor Neal! Inspiring that the father of modern MCMC techniques takes the time to correct bad takes on hacker news!