My Favorite Algorithm: Metropolis-Hastings
flynnmichael.com
My Favorite Algorithm: Metropolis-Hastings
1–10 of 24 posts
Re: My Favorite Algorithm: Metropolis-Hastings
#2I like the build-up explanation in this chapter (Monte Carlo Methods) from MacKay's book: http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/356.384....
Re: My Favorite Algorithm: Metropolis-Hastings
#3Interesting choice...
Seems like genetic algorithms, particle swarms etc. would be more attractive choices since they solve the same problem and are inherently parallelizable while Metropolis Hastings is almost 100 years old and designed for a 4 function calculator.
Although I guess some people have meta-parallelized it... but still seems like a patch job compared to modern likelihood navigation algos.
Re: My Favorite Algorithm: Metropolis-Hastings
#4Interesting choice... Seems like genetic algorithms, particle swarms etc. would be more attractive choices since they solve the same problem and are inherently parallelizable while Metropolis Hastings is almost 100 years old and designed for a 4 function calculator. Although I guess some people have meta-parallelized it... but still seems like a patch job compared to modern likelihood navigation algos.
One of the parallelized versions is Gibbs sampling that is used for sampling from Bayesian networks. In this case you don't even need a proposal distribution; neither would you need the test from MH.
I think Graphlab (https://dato.com/) comes implemented with something of this kind.
The trouble with Particle swarms/Genetic algorithms is that they aren't guaranteed to sample from the underlying p.d. It is not yet apparent whether you can find the mode of a distribution faster by choosing a Markov chain whose stationary distribution is different from the underlying one.
Re: My Favorite Algorithm: Metropolis-Hastings
#5Interesting choice... Seems like genetic algorithms, particle swarms etc. would be more attractive choices since they solve the same problem and are inherently parallelizable while Metropolis Hastings is almost 100 years old and designed for a 4 function calculator. Although I guess some people have meta-parallelized it... but still seems like a patch job compared to modern likelihood navigation algos.
One of the parallelized versions is Gibbs sampling that is used for sampling from Bayesian networks. In this case you don't even need a proposal distribution; neither would you need the test from MH. I think Graphlab ( https://dato.com/ ) comes implemented with something of this kind. The trouble with Particle swarms/Genetic algorithms is that they aren't guaranteed to sample from the underlying p.d. It is not yet ap…
[deleted]
Re: My Favorite Algorithm: Metropolis-Hastings
#6Interesting choice... Seems like genetic algorithms, particle swarms etc. would be more attractive choices since they solve the same problem and are inherently parallelizable while Metropolis Hastings is almost 100 years old and designed for a 4 function calculator. Although I guess some people have meta-parallelized it... but still seems like a patch job compared to modern likelihood navigation algos.
One of the parallelized versions is Gibbs sampling that is used for sampling from Bayesian networks. In this case you don't even need a proposal distribution; neither would you need the test from MH. I think Graphlab ( https://dato.com/ ) comes implemented with something of this kind. The trouble with Particle swarms/Genetic algorithms is that they aren't guaranteed to sample from the underlying p.d. It is not yet ap…
Are you sure that Gibbs sampling isn't just the multivariate version of MH?
What I'm saying is that convergence speed for MH is limited by the fact that guesses cannot communicate with each other... which doesn't matter when you have a pencil and a 4 function calculator like when it was designed.
A genetic algorithm or a particle swarm algorithm is capable of much swifter convergence because the guesses _can_ communicate and influence the direction of the drunken walk.
Re: My Favorite Algorithm: Metropolis-Hastings
#7Earlier quoted context omitted.
One of the parallelized versions is Gibbs sampling that is used for sampling from Bayesian networks. In this case you don't even need a proposal distribution; neither would you need the test from MH. I think Graphlab ( https://dato.com/ ) comes implemented with something of this kind. The trouble with Particle swarms/Genetic algorithms is that they aren't guaranteed to sample from the underlying p.d. It is not yet ap…
Are you sure that Gibbs sampling isn't just the multivariate version of MH? What I'm saying is that convergence speed for MH is limited by the fact that guesses cannot communicate with each other... which doesn't matter when you have a pencil and a 4 function calculator like when it was designed. A genetic algorithm or a particle swarm algorithm is capable of much swifter convergence because the guesses _can_ communi…
It is a multivariate (co-ordinate wise) version of MH. You can paralleize it because the Bayes net allows a decomposition of the p.d.
I feel like while your comment on Global-optimization algorithms may indeed be true, I don't quite yet believe that the hacks they involve are quite that general yet.
MH wasn't designed for Global optimization, and there is only one "particle". I guess this what you meant by "parallel" ?
Re: My Favorite Algorithm: Metropolis-Hastings
#8Earlier quoted context omitted.
Are you sure that Gibbs sampling isn't just the multivariate version of MH? What I'm saying is that convergence speed for MH is limited by the fact that guesses cannot communicate with each other... which doesn't matter when you have a pencil and a 4 function calculator like when it was designed. A genetic algorithm or a particle swarm algorithm is capable of much swifter convergence because the guesses _can_ communi…
It is a multivariate (co-ordinate wise) version of MH. You can paralleize it because the Bayes net allows a decomposition of the p.d. I feel like while your comment on Global-optimization algorithms may indeed be true, I don't quite yet believe that the hacks they involve are quite that general yet. MH wasn't designed for Global optimization, and there is only one "particle". I guess this what you meant by "parallel"…
Yeah, that's what I meant, the one particle bit.
Frequently you'll see things along the lines of "we ran 10,000 MCMC iterations to find the solution" and my first thought is "that must be a lot of wasted cycles."
I think I see what you mean now about the parallelization by decomposing the variables (splitting the problem into i separate problems which can be chained independently?)-- I didn't know that was a possibility. I'll have to look at that.
Re: My Favorite Algorithm: Metropolis-Hastings
#9Earlier quoted context omitted.
One of the parallelized versions is Gibbs sampling that is used for sampling from Bayesian networks. In this case you don't even need a proposal distribution; neither would you need the test from MH. I think Graphlab ( https://dato.com/ ) comes implemented with something of this kind. The trouble with Particle swarms/Genetic algorithms is that they aren't guaranteed to sample from the underlying p.d. It is not yet ap…
Are you sure that Gibbs sampling isn't just the multivariate version of MH? What I'm saying is that convergence speed for MH is limited by the fact that guesses cannot communicate with each other... which doesn't matter when you have a pencil and a 4 function calculator like when it was designed. A genetic algorithm or a particle swarm algorithm is capable of much swifter convergence because the guesses _can_ communi…
When I was in grad school, we used MH to compute 400-dimensional integrals. We computed ground state and excited state properties of a particular system, using a wavefunction as the probability distribution. This was easily parallelized.
e.g http://phya.snu.ac.kr/~gsjeon/Primary/Abstract/abs26.html
While I can't say that one guess communicated with others, I can say that whenever I moved one particle, the others knew about it immediately because the wavefunction described a strongly correlated system. Communication between guesses sounds really interesting though. I've been out of the game for a while, so I'll have to look that up.
Re: My Favorite Algorithm: Metropolis-Hastings
#10Earlier quoted context omitted.
One of the parallelized versions is Gibbs sampling that is used for sampling from Bayesian networks. In this case you don't even need a proposal distribution; neither would you need the test from MH. I think Graphlab ( https://dato.com/ ) comes implemented with something of this kind. The trouble with Particle swarms/Genetic algorithms is that they aren't guaranteed to sample from the underlying p.d. It is not yet ap…
Are you sure that Gibbs sampling isn't just the multivariate version of MH? What I'm saying is that convergence speed for MH is limited by the fact that guesses cannot communicate with each other... which doesn't matter when you have a pencil and a 4 function calculator like when it was designed. A genetic algorithm or a particle swarm algorithm is capable of much swifter convergence because the guesses _can_ communi…
[deleted]