My Favorite Algorithm: Metropolis-Hastings • Hacker News Board

Re: My Favorite Algorithm: Metropolis-Hastings

#11

Post by stellographer » Mon, Jun 01, 2015, 10:21 AM UTC

physicsyogi wrote: post #9

stellographer wrote: post #6

Earlier 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…

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…

Check out this guy's work for some really cool examples: http://en.wikipedia.org/wiki/Xin-She_Yang

Re: My Favorite Algorithm: Metropolis-Hastings

#12

Post by murbard2 » Mon, Jun 01, 2015, 1:20 PM UTC

stellographer wrote: post #3

Interesting 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.

No!

The point of Metropolis-Hastings is to sample from a distribution when you do not know the partition function. It is the most important building blocks in a set of algorithms broadly known as Markov Chain Monte Carlo. These algorithms are particularly useful when performing Bayesian statistics.

Genetic algorithms will not give you samples from a distribution, they only perform optimization. Particle swarms also focus on optimization, and on top of that, they do not seem to have either theoretical justification or empirical success.

MH is embarrassingly parallel since you run multiple chains at the same time. Again, the point isn't optimization (that would be simulated annealing) but sampling.

Being 100 years old is also largely irrelevant. People will publish new algorithms to get publications all the time. That do not mean they necessarily outperform the old ones. Gradient descent is the basic algorithm used in training all of these cool new deep learning algorithms, and it's much older than MH.

Yes, there are more recent improvements to MH, the two biggest ones being Hamiltonian Monte Carlo (which uses gradient information) and Parallel Tempering (which is somewhat similar to homotopy optimization), but that's hardly a reason to dismiss the importance of this algorithm.

Re: My Favorite Algorithm: Metropolis-Hastings

#13

Post by tel » Mon, Jun 01, 2015, 1:29 PM UTC

enupten wrote: post #7

stellographer wrote: post #6

Earlier 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"…

Well, you can run multiple simultaneous particle chains and sum their results. There's some wasted work since each will need to burn in, but modern algorithms can make that go quite quickly.

Re: My Favorite Algorithm: Metropolis-Hastings

#14

Post by tel » Mon, Jun 01, 2015, 1:31 PM UTC

stellographer wrote: post #6

enupten wrote: post #4

Earlier 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…

If your goal is optimization then MH is a bad choice. This is fine since MH is simply not an optimization algorithm! It's design to make accurate samples from a posterior distribution which you can measure but not find a functional form for.

It's a vastly more challenging problem than mere optimization.

Re: My Favorite Algorithm: Metropolis-Hastings

#15

Post by gfodor » Mon, Jun 01, 2015, 2:00 PM UTC

I always go back and forth on which of the two things are more amazing: the fact that we can accurately estimate the rendering equation in tractable time, or the fact that the universe manages to do it in real time.

Re: My Favorite Algorithm: Metropolis-Hastings

#16

Post by xioxox » Mon, Jun 01, 2015, 2:02 PM UTC

In practice, there are some nicer algorithms for doing Markov Chain Monte Carlo, such as Goodman & Weare's Affine Invariant sampler, as implemented in http://dan.iel.fm/emcee/current/ . This algorithm has the advantage of not needing a proposal distribution.

Re: My Favorite Algorithm: Metropolis-Hastings

#17

Post by mandelken » Mon, Jun 01, 2015, 2:23 PM UTC

Listen to Press on the naming of the algorithm, seems like Metropolis just put his name on the paper:

https://youtu.be/4gNpgSPal_8?t=938

Re: My Favorite Algorithm: Metropolis-Hastings

#18

Post by enupten » Mon, Jun 01, 2015, 5:38 PM UTC

tel wrote: post #13

enupten wrote: post #7

Earlier quoted context omitted.

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"…

Well, you can run multiple simultaneous particle chains and sum their results. There's some wasted work since each will need to burn in, but modern algorithms can make that go quite quickly.

Sure - but that's not what the OP is referring to. There is no "sync" step in multiple parallel chains, unlike particle swarm & genetic algorithms.

MCMC is also used for finding MAP solutions, an operation which is strictly less difficult than computing the partition function.

Re: My Favorite Algorithm: Metropolis-Hastings

#19

Post by mjfl » Mon, Jun 01, 2015, 8:40 PM UTC

mandelken wrote: post #17

Listen to Press on the naming of the algorithm, seems like Metropolis just put his name on the paper: https://youtu.be/4gNpgSPal_8?t=938

This is true! It should be called the Rosenbluth-Hastings algorithm.

Re: My Favorite Algorithm: Metropolis-Hastings

#20

Post by stellographer » Tue, Jun 02, 2015, 12:42 AM UTC

murbard2 wrote: post #12

stellographer wrote: post #3

Interesting 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.

No! The point of Metropolis-Hastings is to sample from a distribution when you do not know the partition function. It is the most important building blocks in a set of algorithms broadly known as Markov Chain Monte Carlo. These algorithms are particularly useful when performing Bayesian statistics. Genetic algorithms will not give you samples from a distribution, they only perform optimization. Particle swarms also f…

I see you feel strongly about this.

"The point of Metropolis-Hastings is to sample from a distribution when you do not know the partition function." That's one point, yes. The other is optimization. In which case I prefer the others I mentioned.

"they do not seem to have either theoretical justification or empirical success." That's just patently false. They _do_ have empirical success. And besides, a lot of these variants have MH implemented inside of them to some extent o.o

"MH is embarrassingly parallel since you run multiple chains at the same time." I can make six single grilled cheese sandwiches in 2 minutes, but it takes me 8 minutes to make a 6-decker grilled cheese. Is that a parallel process?

"Being 100 years old is also largely irrelevant." In my opinion it is relevant since computation can now be done in completely new ways than 100 years ago.