Based on the little knowledge that I have on MCMC (Markov chain Monte Carlo) methods, I understand that sampling is a crucial part of the aforementioned technique. The most commonly used sampling methods are Hamiltonian and Metropolis.

Is there a way to utilise machine learning or even deep learning to construct a more efficient MCMC sampler?

  • 5
    Could you specify what kind of "improvement" you have in mind and how do you see machine learning's role it it..? – Tim Jul 18 '16 at 14:15
  • 2
    Not usually, MCMC usually involves estimating values from expressions with no closed form that are simply too complex to find analytic solutions. It's possible that multivariate clustering (or similar approaches) could be used to estimate simpler multivariate densities, but I would see that more as an alternative to using MCMC at all. – AdamO Jul 18 '16 at 14:49
  • 1
    @AdamO, why not convert that into an answer? It seems like it might be as good as we can get here. – gung Jul 18 '16 at 14:54
  • @Tim Well, from what I have read, MCMC draws samples from a distribution in order to calculate inferential quantities. The MH algorithm randomly picks "locations" and then asserts if they are acceptable. What I was wondering is if there are ML alternative techniques. I know it sounds vague, and I apologise for that, but I find MCMC intriguing and I am trying to get a hold on the theory and practical applications by self studying. – Jespar Jul 18 '16 at 15:16
  • Related arxiv.org/pdf/1506.03338v3.pdf – Opt Nov 26 '16 at 19:44
up vote 25 down vote accepted

Yes. Unlike what other answers state, 'typical' machine-learning methods such as nonparametrics and (deep) neural networks can help create better MCMC samplers.

The goal of MCMC is to draw samples from an (unnormalized) target distribution $f(x)$. The obtained samples are used to approximate $f$ and mostly allow to compute expectations of functions under $f$ (i.e., high-dimensional integrals) and, in particular, properties of $f$ (such as moments).

Sampling usually requires a large number of evaluations of $f$, and possibly of its gradient, for methods such as Hamiltonian Monte Carlo (HMC). If $f$ is costly to evaluate, or the gradient is unavailable, it is sometimes possible to build a less expensive surrogate function that can help guide the sampling and is evaluated in place of $f$ (in a way that still preserves the properties of MCMC).

For example, a seminal paper (Rasmussen 2003) proposes to use Gaussian Processes (a nonparametric function approximation) to build an approximation to $\log f$ and perform HMC on the surrogate function, with only the acceptance/rejection step of HMC based on $f$. This reduces the number of evaluation of the original $f$, and allows to perform MCMC on pdfs that would otherwise too expensive to evaluate.

The idea of using surrogates to speed up MCMC has been explored a lot in the past few years, essentially by trying different ways to build the surrogate function and combine it efficiently/adaptively with different MCMC methods (and in a way that preserves the 'correctness' of MCMC sampling). Related to your question, these two very recent papers use advanced machine learning techniques -- random networks (Zhang et al. 2015) or adaptively learnt exponential kernel functions (Strathmann et al. 2015) -- to build the surrogate function.

HMC is not the only form of MCMC that can benefit from surrogates. For example, Nishiara et al. (2014) build an approximation of the target density by fitting a multivariate Student's $t$ distribution to the multi-chain state of an ensemble sampler, and use this to perform a generalized form of elliptical slice sampling.

These are only examples. In general, a number of distinct ML techniques (mostly in the area of function approximation and density estimation) can be used to extract information that might improve the efficiency of MCMC samplers. Their actual usefulness -- e.g. measured in number of "effective independent samples per second" -- is conditional on $f$ being expensive or somewhat hard to compute; also, many of these methods may require tuning of their own or additional knowledge, restricting their applicability.

References:

  1. Rasmussen, Carl Edward. "Gaussian processes to speed up hybrid Monte Carlo for expensive Bayesian integrals." Bayesian Statistics 7. 2003.

  2. Zhang, Cheng, Babak Shahbaba, and Hongkai Zhao. "Hamiltonian Monte Carlo Acceleration using Surrogate Functions with Random Bases." arXiv preprint arXiv:1506.05555 (2015).

  3. Strathmann, Heiko, et al. "Gradient-free Hamiltonian Monte Carlo with efficient kernel exponential families." Advances in Neural Information Processing Systems. 2015.

  4. Nishihara, Robert, Iain Murray, and Ryan P. Adams. "Parallel MCMC with generalized elliptical slice sampling." Journal of Machine Learning Research 15.1 (2014): 2087-2112.

  • 2
    I'm not sure the methods you've listed are really in the category of "machine learning methods", rather just standard MCMC methods (although this is the blurriest of lines). The only one that definitively seems to be a ML/DL method was 3, which has since removed "neural network" from it's title (and seems to admit in the text that using standard ML methods would be much too slow). – Cliff AB Jul 18 '16 at 19:35
  • 2
    @CliffAB thanks. I agree that the line is a bit blurry for some of these methods (e.g., 4 uses a simple Student's $t$ fit -- but their method could use some more complex density estimation technique). As for the rest, well, it depends on whether you consider (nonparametric) function approximation, such as GPs, or density estimation, a ML technique or not. If you don't, fair enough, but I am not sure what is a ML technique then. (The OP asked for ML or DL techniques to improve MCMC.) – lacerbi Jul 18 '16 at 19:51
  • 1
    Thank you very much @lacerbi. I am glad that I can use your references as bedrock for further research. – Jespar Jul 19 '16 at 8:45

A method that could connect the two concepts is that of a multivariate Metropolis Hastings algorithm. In this case, we have a target distribution (the posterior distribution) and a proposal distribution (typically a multivariate normal or t-distribution).

A well known fact is that the further the proposal distribution is from the posterior distribution, the less efficient the sampler is. So one could imagine using some sort of machine learning method to build up a proposal distribution that matches better to the true posterior distribution than a simple multivariate normal/t distribution.

However, it's not clear this would be any improvement to efficiency. By suggesting deep learning, I assume that you may be interested in using some sort of neural network approach. In most cases, this would be significantly more computationally expensive than the entire vanilla MCMC method itself. Similarly, I don't know any reason that NN methods (or even most machine learning methods) do a good job of providing adequate density outside the observed space, crucial for MCMC. So even ignoring the computational costs associated with building the machine learning model, I cannot see a good reason why this would improve the sampling efficiency.

  • Cliff AB I feel that you and @AdamO clarified the MCMC and ML concepts to me more than spending hours on another book. I appreciate your effort guys and I am glad that you mentioned some areas that I can further delve into. – Jespar Jul 18 '16 at 16:28
  • @Sitherion which book are you referring to? – AdamO Jul 18 '16 at 18:10
  • @AdamO Currently I am reading Reinforcement Learning by Richard Sutton and Machine Learning: A Probabilistic Perspective by Kevin Murphy that contains a MCMC chapter; and also publications from various ML and Computational Statistics journals. – Jespar Jul 19 '16 at 9:07

Machine Learning is concerned with prediction, classification, or clustering in a supervised or unsupervised setting. On the other hand, MCMC is simply concerned with evaluating a complex intergral (usually with no closed form) using probabilistic numerical methods. Metropolis sampling is definitely not the most commonly used approach. In fact, this is the only MCMC method not to have any probabilistic component. So ML would not inform anything with MCMC in this case.

Importance based sampling does require a probabilistic component. It is more efficient than Metropolis under some basic assumptions. ML methods can be used to estimate this probabilistic component if it dovetails with some assumptions. Examples might be multivariate clustering to estimate a complex high dimensional Gaussian density. I am not familiar with non-parametric approaches to this problem, but that could be an interesting area of development.

Nonetheless, ML stands out to me as a distinct step in the process of estimating a high dimensional complex probability model which is subsequently used in a numerical method. I don't see how ML really improves MCMC in this case.

  • Thank you @AdamO, at least now I have a far better understanding of this area. – Jespar Jul 18 '16 at 16:16
  • 1
    I think this answer is incomplete and possibly incorrect (depending on the interpretation of the OP's actual question, which is not completely clear). Typical ML methods such as nonparametrics and neural networks can and are used to improve MCMC samplers. In fact, it is an active area of research. See my answer, and references therein to start with. – lacerbi Jul 18 '16 at 17:12
  • 1
    @lacerbi your answer is a good one, and I would say the OP should read these articles for their illumination regardless of what their question may be. I would say the results in your answer build upon my definition of MCMC as being a method for evaluating complex integrals using a probabilistic component. However, they do not incorporate machine learning or deep learning, which should (at the very least) handle cases where $p$ is very, very large. – AdamO Jul 18 '16 at 18:07
  • Thanks @AdamO. Still, to be honest, I don't understand your explanation, or how it makes your answer correct. For example, I don't understand what you mean when you say that Metropolis has "no probabilistic component". Also, you state that ML can't help in sampling, which is simply untrue (even in the narrow definition of sampling as estimation of a high-dimensional integral), as my answer shows. – lacerbi Jul 18 '16 at 18:21
  • 3
    @AdamO: Gaussian processes, kernel methods, random basis networks. In general, any form of function approximation or density estimation would work. If these are not ML methods, I am not sure what is... (please note that the OP asked for ML or DL methods). Also, as I asked above, can you please explain what you meant when you wrote that Metropolis does not have a probabilistic component? Thanks! – lacerbi Jul 18 '16 at 20:01

There were some recent works in computational physics where the authors used the Restricted Boltzmann Machines to model probability distribution and then propose (hopefully) efficient Monte Carlo updates arXiv:1610.02746. The idea here turns out to be quite similar to the references given by @lacerbi in above.

In another attempt 1702.08586, the author explicitly constructed Boltzmann Machines which can perform (and even discover) the celebrated cluster Monte Carlo updates.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.