17 ms·

Markov Chain Monte Carlo (MCMC) Sampling, Part 1: The Basics (2019)

146 points by vonadz 6y ago

melling 6y ago
Ben Lambert has a great series on Bayesian Statistics: https://www.youtube.com/playlist?list=PLwJRxp3blEvZ8AKMXOy0fc0cqT61GsKCG https://www.youtube.com/playlist?list=PLwJRxp3blEvZ8AKMXOy0f... He works his way up to MCMC
- ranc1d 6y ago
  Agreed, that YouTube playlist along with his book of the same name really helped me get a good understanding of Bayesian Statistics/MCMC https://uk.sagepub.com/en-gb/eur/book/student%E2%80%99s-guide-bayesian-statistics https://uk.sagepub.com/en-gb/eur/book/student%E2%80%99s-guid...
swsieber 6y ago
So this is only tangentially related in that it's ML related. I'm working on a system where a user uploads a single document that corresponds to several documents we already have I'm the system (and we know which documents those are) and we are supposed to map pages from the single document to pages in the other know documents. I'm having a hard time finding literature on problems like this. I think the closest thing it's like is the stable matching problem, but I'm not sure. My current algorithm doesn't allow for missing or reordered pages. Does anyone have magic words I could google to find pertinent research/algorithms? I think if worst comes to worse I'll have to try to model the incoming page stream as something like a bayseian ... graph? It's been so long since I've done something like that (5 years), and that was in school.
- KidComputer 6y ago
  I'd generate document embeddings for each page then put the embedding vectors in a similarity search database like Facebook Research's Faiss.
- setr 6y ago
  It sounds like you're just trying to do similarity search? In which case, I imagine the key terms you want to be looking for are Information Retrieval and Recommendation Algorithms The most basic thing I'd imagine (assuming text docs) is something like index each document by TF-IDF, and then the new document by TF-IDF, and then rank results by similarity You're basically doing a google search on documents, but with a really big query (another document)
- sixhobbits 6y ago
  If the pages are ordered it sounds like a text alignment problem. Lots of literature on that especially in machine translation
- sgt101 6y ago
  If I were you I would measure reconstruction errors from transformer predictions using input from the source document and then difference vs the target documents. The challenge would be to get a good measure of the difference, perhaps us some cosine difference again from the transformer? If you have specialist vocab you can train the transformers - so maybe you are doing legal matching?
michaericalribo 6y ago
The Gibbs sampler is right at the top of my personal list of the greatest technical achievements in statistics. Not only is the asymptotic guarantee of producing a sample from the target distribution a neat and elegant result, but it also opened up a really rich world of probabilistic modeling. From a practical / ML perspective, variational methods are more efficient for getting decent estimates of complex models. And there are a lot of devilish details to MCMC sampling, and the real world _never_ goes to infinity. Still, the sheer theoretical fact that an imperfect, simulation-based method can produce valid statistical estimates is just awesome.
- wheresmycraisin 6y ago
  I appreciate the theoretical aspects of it as well -- however, I could never get over the notion that bayesians need to use frequentist statistics to judge whether the chain has sufficiently converged... isn't that defeating the entire point?
  - soVeryTired 6y ago
    Interesting point, but I think the academic culture has taken a pragmatic shift: there aren't many 'pure' bayesians or frequentists left anymore, and the boundary between the two viewpoints has softened. Stats has more of a 'shut up and calculate' mentality about it these days.
    - sgt101 6y ago
      >Stats has more of a 'shut up and calculate' mentality about it these days. I'm happy that the "pure this pure that" fundamentalism has faded into retirement... but shut up and calculate has problems - especially around causality. The "blessings of multiple causes" paper for example.
    - wheresmycraisin 6y ago
      Then why bother pretending to calculate a posterior distribution when you can do a MLE estimator with regularization or something?
xvilka 6y ago
There are many articles about MCMC in Python. I am surprised Tweag didn't write the same but for Haskell.
Fishysoup 6y ago
Something I've had trouble finding resources for is how to apply probabilistic/Bayesian techniques and thinking to chaotic dynamical systems. People keep telling me "Look up MCMC" but I don't see the relevance to dynamical systems (further than the notion that you can maybe sample from them with MCMC somehow?)
- c1ccccc1 6y ago
  If all you want to do is sample from possible outcomes of the system, then you should just be able to run a simulation of it on your computer. If you want to condition on an event? Say you want to predict the weather on Tuesday, conditioned on the event that it rained on Sunday? Run a lot of simulations, and only keep the ones where it rained on Sunday. Similarly: If you want to compute an expectation value? Run a lot of simulations and take the average. If the event is unlikely? Say you want to condition on the fact that it rained on Sunday, and the high temperature was precisely 15 degrees C? Then you have a difficult problem on your hands. (Sometimes the expectation value of the quantity you care about will depend a lot on a few rare events with outcomes many standard deviations away from the mean. Then you also have a difficult problem on your hands.) Sometimes MCMC will work on this kind of problem, and sometimes it won't. Even if it doesn't, maybe other techniques will work. To apply MCMC to a dynamical system, one method is write down all of the history of the system as a single object, say a single vector. You write down what your system is doing at t=1, at t=2, etc, and all that information goes into the vector. The rules governing the system determine a probability distribution over the vector space that the vector lives in. (Or more generally, the object in the object space. The vector axioms aren't important here, it's just a nice familiar example.) Generally speaking, if you know how to describe your dynamical system, you know how to compute an non-normalized probability for any given vector. Usually you won't be able to compute a normalized probability for that vector. That's fine, since MCMC works with non-normalized probabilities. The next step is simply to run MCMC. If you want to condition on some fact, cut out all the parts of the space where that fact doesn't hold, and then run MCMC. If you want to compute an expectation value, there are other tweaks to MCMC that are possible (i.e. importance sampling).
  - Fishysoup 6y ago
cake93 6y ago
This week, the PyMCon 2020 is happening: All around PyMC3, one of the leading libraries for MCMC/Bayesian statistics/probabilistic programming, this online conference is split into an asynchronous and a synchronous part. The talks of the asynchronous part are publicly accessible on the forum: https://discourse.pymc.io/c/pymcon/2020talks/15 https://discourse.pymc.io/c/pymcon/2020talks/15 Tickets for the synchronous part with Keynote sessions and live Q&A are still available: https://pymc-devs.github.io/pymcon/ https://pymc-devs.github.io/pymcon/

146 points by vonadz 6y ago

Ben Lambert has a great series on Bayesian Statistics: https://www.youtube.com/playlist?list=PLwJRxp3blEvZ8AKMXOy0fc0cqT61GsKCG https://www.youtube.com/playlist?list=PLwJRxp3blEvZ8AKMXOy0f... He works his way up to MCMC

ranc1d 6y ago
Agreed, that YouTube playlist along with his book of the same name really helped me get a good understanding of Bayesian Statistics/MCMC https://uk.sagepub.com/en-gb/eur/book/student%E2%80%99s-guide-bayesian-statistics https://uk.sagepub.com/en-gb/eur/book/student%E2%80%99s-guid...

swsieber 6y ago

So this is only tangentially related in that it's ML related. I'm working on a system where a user uploads a single document that corresponds to several documents we already have I'm the system (and we know which documents those are) and we are supposed to map pages from the single document to pages in the other know documents. I'm having a hard time finding literature on problems like this. I think the closest thing it's like is the stable matching problem, but I'm not sure. My current algorithm doesn't allow for missing or reordered pages. Does anyone have magic words I could google to find pertinent research/algorithms? I think if worst comes to worse I'll have to try to model the incoming page stream as something like a bayseian ... graph? It's been so long since I've done something like that (5 years), and that was in school.

KidComputer 6y ago
I'd generate document embeddings for each page then put the embedding vectors in a similarity search database like Facebook Research's Faiss.
setr 6y ago
It sounds like you're just trying to do similarity search? In which case, I imagine the key terms you want to be looking for are Information Retrieval and Recommendation Algorithms The most basic thing I'd imagine (assuming text docs) is something like index each document by TF-IDF, and then the new document by TF-IDF, and then rank results by similarity You're basically doing a google search on documents, but with a really big query (another document)
sixhobbits 6y ago
If the pages are ordered it sounds like a text alignment problem. Lots of literature on that especially in machine translation
sgt101 6y ago
If I were you I would measure reconstruction errors from transformer predictions using input from the source document and then difference vs the target documents. The challenge would be to get a good measure of the difference, perhaps us some cosine difference again from the transformer? If you have specialist vocab you can train the transformers - so maybe you are doing legal matching?

michaericalribo 6y ago

The Gibbs sampler is right at the top of my personal list of the greatest technical achievements in statistics. Not only is the asymptotic guarantee of producing a sample from the target distribution a neat and elegant result, but it also opened up a really rich world of probabilistic modeling. From a practical / ML perspective, variational methods are more efficient for getting decent estimates of complex models. And there are a lot of devilish details to MCMC sampling, and the real world _never_ goes to infinity. Still, the sheer theoretical fact that an imperfect, simulation-based method can produce valid statistical estimates is just awesome.

wheresmycraisin 6y ago
I appreciate the theoretical aspects of it as well -- however, I could never get over the notion that bayesians need to use frequentist statistics to judge whether the chain has sufficiently converged... isn't that defeating the entire point?
- soVeryTired 6y ago
  Interesting point, but I think the academic culture has taken a pragmatic shift: there aren't many 'pure' bayesians or frequentists left anymore, and the boundary between the two viewpoints has softened. Stats has more of a 'shut up and calculate' mentality about it these days.
  - sgt101 6y ago
    >Stats has more of a 'shut up and calculate' mentality about it these days. I'm happy that the "pure this pure that" fundamentalism has faded into retirement... but shut up and calculate has problems - especially around causality. The "blessings of multiple causes" paper for example.
  - wheresmycraisin 6y ago
    Then why bother pretending to calculate a posterior distribution when you can do a MLE estimator with regularization or something?

xvilka 6y ago

There are many articles about MCMC in Python. I am surprised Tweag didn't write the same but for Haskell.

Fishysoup 6y ago

Something I've had trouble finding resources for is how to apply probabilistic/Bayesian techniques and thinking to chaotic dynamical systems. People keep telling me "Look up MCMC" but I don't see the relevance to dynamical systems (further than the notion that you can maybe sample from them with MCMC somehow?)

c1ccccc1 6y ago
If all you want to do is sample from possible outcomes of the system, then you should just be able to run a simulation of it on your computer. If you want to condition on an event? Say you want to predict the weather on Tuesday, conditioned on the event that it rained on Sunday? Run a lot of simulations, and only keep the ones where it rained on Sunday. Similarly: If you want to compute an expectation value? Run a lot of simulations and take the average. If the event is unlikely? Say you want to condition on the fact that it rained on Sunday, and the high temperature was precisely 15 degrees C? Then you have a difficult problem on your hands. (Sometimes the expectation value of the quantity you care about will depend a lot on a few rare events with outcomes many standard deviations away from the mean. Then you also have a difficult problem on your hands.) Sometimes MCMC will work on this kind of problem, and sometimes it won't. Even if it doesn't, maybe other techniques will work. To apply MCMC to a dynamical system, one method is write down all of the history of the system as a single object, say a single vector. You write down what your system is doing at t=1, at t=2, etc, and all that information goes into the vector. The rules governing the system determine a probability distribution over the vector space that the vector lives in. (Or more generally, the object in the object space. The vector axioms aren't important here, it's just a nice familiar example.) Generally speaking, if you know how to describe your dynamical system, you know how to compute an non-normalized probability for any given vector. Usually you won't be able to compute a normalized probability for that vector. That's fine, since MCMC works with non-normalized probabilities. The next step is simply to run MCMC. If you want to condition on some fact, cut out all the parts of the space where that fact doesn't hold, and then run MCMC. If you want to compute an expectation value, there are other tweaks to MCMC that are possible (i.e. importance sampling).
- Fishysoup 6y ago

cake93 6y ago

This week, the PyMCon 2020 is happening: All around PyMC3, one of the leading libraries for MCMC/Bayesian statistics/probabilistic programming, this online conference is split into an asynchronous and a synchronous part. The talks of the asynchronous part are publicly accessible on the forum: https://discourse.pymc.io/c/pymcon/2020talks/15 https://discourse.pymc.io/c/pymcon/2020talks/15 Tickets for the synchronous part with Keynote sessions and live Q&A are still available: https://pymc-devs.github.io/pymcon/ https://pymc-devs.github.io/pymcon/