A Zero-Math Introduction to Markov Chain Monte Carlo Methods

towardsdatascience.com

38 points·tosh··8 comments

Previous discussion: https://news.ycombinator.com/item?id=15986687

Random-play Monte-Carlo was the first algorithm that lead to good computer Go software, before neural network. It was around 2008 I think. Before that, pattern-base algos were really, really bad (like, barely above human beginner level).

I'm not a mathematician, but the paper itself was a real beauty. I remember vividly the parameter that balanced "exploitation" of apparently-good paths, and "exploration" of unknown/apparently-bad path. I used it in many analogies discussing innovation programs within large companies.

Is this [1] the paper you are referring to? Thanks for the heads up, this work looks interesting.

[1]: https://www.aaai.org/Papers/AIIDE/2008/AIIDE08-036.pdf

Are there any Lot-Of-Math Introduction to Monte Carlo Methods?

I'm not sure, since it doesn't introduce the notion of detailed balance, whether this article really deals meaningfully with the use of Markov chains at all.

It doesn't bring out the fact that the Markov chain transition probabilities have to be tuned to explore the parameter space. The relative efficiency of MCMC versus a naive random sampling approach depends on this leveraging of detailed balance so that the correlations of the Markov chain work in favour of the experiment.

So given that the article introduces this notion of a random walk, so it seems like it's going to discuss the Metropolis algorithm, it's not great that it ducks the main issue which is why a correlated Markov chain random walk is a useful approach.

The key is that it's a "conditioned" random walk, and the method by which it is conditioned is the real trick to MCMC (at least to Metropolis, which is the cool kind.)

Reply on news.ycombinator.com