5 ms·

The State of Probabilistic Programming

109 points by superfx 11y ago

enupten 11y ago
I wonder if kids 30y from now look upon this as the new Prolog.
- vezzy-fnord 11y ago
  I was pretty much thinking about logic programming throughout most of the article. Seems like PPS is a continuation of these ideas, in many ways.
  - enupten 11y ago
    In more ways than one, http://alchemy.cs.washington.edu/ http://alchemy.cs.washington.edu/
  - strmpnk 11y ago
    This paper comes to mind as an interesting link between logic and probabilistic ideas: http://okmij.org/ftp/kakuritu/rethinking.pdf http://okmij.org/ftp/kakuritu/rethinking.pdf
- sieisteinmodel 11y ago
  I think the difference is that Prolog was aimed to solve all kinds of programming problems. PPs on the other hand is very domain specific from the start.
  - digitalzombie 11y ago
    Like Erlang?
nmrm2 11y ago
"Having been rescued from the clutches of object-orientation by early exposure to Mathematica" I kind of laughed at this line, because this seems like a situation where the author came to the correct conclusion for all the wrong reasons. Maybe things have changed, but the Mathematica programming language never struck me as useful for anything over a couple thousand lines. edit: this is completely beside the purpose and message of this article, but it's worth noting that modularity is a pretty significant design criteria that none of these languages have a particularly strong story about.
- clementine 11y ago
  Mathematica itself and Wolfram | Alpha have quite substantial code-bases written in Mathematica (now the Wolfram Language). Also, there was an article recently about probabilistic programming with WL: http://www.mathematica-journal.com/data/uploads/2013/11/Cassel.pdf http://www.mathematica-journal.com/data/uploads/2013/11/Cass... My guess is that WL would be an interesting and powerful starting point for probabilistic programming at some point down the line (if not already).
pjungwir 11y ago
This strikes me as a perfect application for quantum computers---but I'm just an amateur, so I'd love to hear an expert opinion. My understanding is this 1982 talk by Feynman [1] more or less launched the study of quantum computers, and it's all about how they can carry a probabilistic value through their computations rather than a definite one. And one of the lessons from that paper (if I'm reading & remembering right---maybe it's another paper) is that simulating quantum behavior with a non-quantum computer turns a lot of polynomial-time problems into exponential-time problems, so that having a real quantum computer would be very helpful for solving the performance & scalability issues described in the OP. Thoughts? [1] http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf
- ibab 11y ago
  You have to take into account that quantum processes are governed by a kind of "randomness" that is different from the one in stochastic processes. Scott Aaronson explains the basics of quantum mechanics very succinctly in one of his lectures [1]. The exponential->polynomial speedup we might get from a quantum computer doesn't really apply to stochastic processes, because we can already execute them in polynomial time on a classical computer (just use a random number generator). Having a quantum computer would still be truly amazing, though. Even just being able to simulate quantum mechanics efficiently would be revolutionary. [1] - http://www.scottaaronson.com/democritus/lec9.html http://www.scottaaronson.com/democritus/lec9.html
  - pjungwir 11y ago
    I upvoted this comment as soon as I read it, but just to follow up: that link is amazing. I read lecture 9, then 10, 10.5, 11, . . . Eventually I bought the book and am reading it from the beginning. Godel and the Halting Problem has been a pet interest for ~17 years, and I've often wondered about implications similar to Penrose's argument. The recent death of a young promising friend has made me want to research these things more seriously, and Aaronson seems like a wonderful guide. Thank you so much!
typedweb 11y ago
Probabilistic programming in Common Lisp: https://github.com/nikodemus/screamer https://github.com/nikodemus/screamer
- kgwgk 11y ago
  Not really. Screamer gives you "nondeterministic" programming. It can be used for example to solve sudokus: http://nikodemus.github.io/screamer/sudoku.lisp.html http://nikodemus.github.io/screamer/sudoku.lisp.html
mizzao 11y ago
I've tried to use probabilistic programming for building a model of real data, and it seems that there is a long way to go before it's practical and fast. On one hand, there are the Monte Carlo-based methods that will support modeling almost any distributions, but are slow to use for large amounts of data. On the other hand, there are interesting cases like Infer.NET that use a completely different technique (approximate, deterministic inference) but are brittle for many real-world use cases. Then, there is the general issue that one has to be familiar with probabilistic models and the inner workings of the inference algorithms to have any hope of debugging the inevitable errors and convergence issues that arise. That seems to realistically require a machine learning or statistics PhD and the population of those is very small.
- gh02t 11y ago
  The performance of most vanilla Metropolis-Hastings MCMC methods is pretty awful, but there are some good improvements. I use DREAM (a non-Markovian and parallelizable extension of M-H) with realistic problems and its convergence rate is much much much better, to the point that I can use it for what I'm working on while regular M-H methods are just too slow.
- stdbrouw 11y ago
  Well, MCMC is pretty close to brute force so it's never going to be very fast. But the diagnostic tools are really quite good these days – tools like Stan and PyMC make it easy to see diagnostic plots that allow you to check for convergence and such. Additionally, more and more fine-tuning is happening automatically, like setting the right jump sizes and a plausible initial value for the random walk. Note that traditional statistics, like regression, requires similar diagnostic steps: qqplots to check for the normality of your data, the Levene test for heteroskedasticity and so on. They often get ignored, but they're generally not hard to teach or learn. We're really not that far from having this stuff be usable by the broader public. Maybe not "build any model you like and it will just work out of the box" but definitely as a replacement for much frequentist statistics. See "Doing Bayesian Data Analysis" by Kruschke, for example.
  - x0x0 11y ago
capnrefsmmat 11y ago
DrBayes (https://github.com/ntoronto/drbayes https://github.com/ntoronto/drbayes) is another interesting probabilistic programming language. It implements measure-theoretic probability in Racket, so it's not limited to what you can express with probability density functions and standard distributions -- you can condition a random variable on any measurable subset of the probability space, for example, so you could condition Y on 0 < X < 3, which wouldn't be possible to evaluate with density functions. Or you can construct random variables which have no density function. I'm not sure this has great practical use, but it's a very interesting system.
cf 11y ago
What's interesting about most complaints of these systems is people talk about their poor performance or scalability? That is usually more a consequence of using MCMC or other inference algorithm than the language itself. MCMC is a very slow inference algorithm. Its primary advantage was that for well-known models it could be coded up much more simply than a fancier inference technique. When you consider variational methods and newer streaming methods based on things like Assumed Density Filtering you can get really great scalable performance. The point of probabilistic programming is write inference algorithms once for a large class of models and be done. So the advantage of using a fancier method is amplified. This means paradoxically probabilistic programming should eventually be faster than existing methods rather than slower, since you can reuse these fancier inference methods for new models. This is a very active field so this progress is only starting to be appear in the existing systems.
- detaro 11y ago
  > The point of probabilistic programming is write inference algorithms once for a large class of models and be done. So the advantage of using a fancier method is amplified. So that should be something where a few standard libraries or toolsets should emerge that push out the "easy-to-implement" default choice? Are there any contenders yet? (As you might be able to tell, I don't really know anything about the field)
  - cf 11y ago
    I know STAN and Figaro are going to push out inference methods like I mention, but my hope is eventually all of the ones mentioned in the article do this. I like thinking of this in terms of the standard library that needs to be built out. All the systems are making great progress in this regard.
- x0x0 11y ago
  Ease of coding is not the primary advantage of mcmc. The (giant) disadvantage of variational inference is the user needs to derive equations and understand quite a bit of math, where gibbs or other samplers like those in bugs/openbugs/jags/stan can work with the factored distributions and require much less mathematical sophistication from users.
nextos 11y ago
It seems Markov Logic nets can scale to really big problems: * https://code.google.com/p/rockit/ https://code.google.com/p/rockit/ * http://i.stanford.edu/hazy/hazy/tuffy/ http://i.stanford.edu/hazy/hazy/tuffy/ But they seem to be getting less and less coverage in probabilistic programming. Perhaps they are considered too inexpressive?

109 points by superfx 11y ago

enupten 11y ago

I wonder if kids 30y from now look upon this as the new Prolog.

vezzy-fnord 11y ago
I was pretty much thinking about logic programming throughout most of the article. Seems like PPS is a continuation of these ideas, in many ways.
- enupten 11y ago
  In more ways than one, http://alchemy.cs.washington.edu/ http://alchemy.cs.washington.edu/
- strmpnk 11y ago
  This paper comes to mind as an interesting link between logic and probabilistic ideas: http://okmij.org/ftp/kakuritu/rethinking.pdf http://okmij.org/ftp/kakuritu/rethinking.pdf
sieisteinmodel 11y ago
I think the difference is that Prolog was aimed to solve all kinds of programming problems. PPs on the other hand is very domain specific from the start.
- digitalzombie 11y ago
  Like Erlang?

nmrm2 11y ago

"Having been rescued from the clutches of object-orientation by early exposure to Mathematica" I kind of laughed at this line, because this seems like a situation where the author came to the correct conclusion for all the wrong reasons. Maybe things have changed, but the Mathematica programming language never struck me as useful for anything over a couple thousand lines. edit: this is completely beside the purpose and message of this article, but it's worth noting that modularity is a pretty significant design criteria that none of these languages have a particularly strong story about.

clementine 11y ago
Mathematica itself and Wolfram | Alpha have quite substantial code-bases written in Mathematica (now the Wolfram Language). Also, there was an article recently about probabilistic programming with WL: http://www.mathematica-journal.com/data/uploads/2013/11/Cassel.pdf http://www.mathematica-journal.com/data/uploads/2013/11/Cass... My guess is that WL would be an interesting and powerful starting point for probabilistic programming at some point down the line (if not already).

pjungwir 11y ago

This strikes me as a perfect application for quantum computers---but I'm just an amateur, so I'd love to hear an expert opinion. My understanding is this 1982 talk by Feynman [1] more or less launched the study of quantum computers, and it's all about how they can carry a probabilistic value through their computations rather than a definite one. And one of the lessons from that paper (if I'm reading & remembering right---maybe it's another paper) is that simulating quantum behavior with a non-quantum computer turns a lot of polynomial-time problems into exponential-time problems, so that having a real quantum computer would be very helpful for solving the performance & scalability issues described in the OP. Thoughts? [1] http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf

ibab 11y ago
You have to take into account that quantum processes are governed by a kind of "randomness" that is different from the one in stochastic processes. Scott Aaronson explains the basics of quantum mechanics very succinctly in one of his lectures [1]. The exponential->polynomial speedup we might get from a quantum computer doesn't really apply to stochastic processes, because we can already execute them in polynomial time on a classical computer (just use a random number generator). Having a quantum computer would still be truly amazing, though. Even just being able to simulate quantum mechanics efficiently would be revolutionary. [1] - http://www.scottaaronson.com/democritus/lec9.html http://www.scottaaronson.com/democritus/lec9.html
- pjungwir 11y ago
  I upvoted this comment as soon as I read it, but just to follow up: that link is amazing. I read lecture 9, then 10, 10.5, 11, . . . Eventually I bought the book and am reading it from the beginning. Godel and the Halting Problem has been a pet interest for ~17 years, and I've often wondered about implications similar to Penrose's argument. The recent death of a young promising friend has made me want to research these things more seriously, and Aaronson seems like a wonderful guide. Thank you so much!

typedweb 11y ago

Probabilistic programming in Common Lisp: https://github.com/nikodemus/screamer https://github.com/nikodemus/screamer

kgwgk 11y ago
Not really. Screamer gives you "nondeterministic" programming. It can be used for example to solve sudokus: http://nikodemus.github.io/screamer/sudoku.lisp.html http://nikodemus.github.io/screamer/sudoku.lisp.html

mizzao 11y ago

I've tried to use probabilistic programming for building a model of real data, and it seems that there is a long way to go before it's practical and fast. On one hand, there are the Monte Carlo-based methods that will support modeling almost any distributions, but are slow to use for large amounts of data. On the other hand, there are interesting cases like Infer.NET that use a completely different technique (approximate, deterministic inference) but are brittle for many real-world use cases. Then, there is the general issue that one has to be familiar with probabilistic models and the inner workings of the inference algorithms to have any hope of debugging the inevitable errors and convergence issues that arise. That seems to realistically require a machine learning or statistics PhD and the population of those is very small.

gh02t 11y ago
The performance of most vanilla Metropolis-Hastings MCMC methods is pretty awful, but there are some good improvements. I use DREAM (a non-Markovian and parallelizable extension of M-H) with realistic problems and its convergence rate is much much much better, to the point that I can use it for what I'm working on while regular M-H methods are just too slow.
stdbrouw 11y ago
Well, MCMC is pretty close to brute force so it's never going to be very fast. But the diagnostic tools are really quite good these days – tools like Stan and PyMC make it easy to see diagnostic plots that allow you to check for convergence and such. Additionally, more and more fine-tuning is happening automatically, like setting the right jump sizes and a plausible initial value for the random walk. Note that traditional statistics, like regression, requires similar diagnostic steps: qqplots to check for the normality of your data, the Levene test for heteroskedasticity and so on. They often get ignored, but they're generally not hard to teach or learn. We're really not that far from having this stuff be usable by the broader public. Maybe not "build any model you like and it will just work out of the box" but definitely as a replacement for much frequentist statistics. See "Doing Bayesian Data Analysis" by Kruschke, for example.
- x0x0 11y ago

capnrefsmmat 11y ago

DrBayes (https://github.com/ntoronto/drbayes https://github.com/ntoronto/drbayes) is another interesting probabilistic programming language. It implements measure-theoretic probability in Racket, so it's not limited to what you can express with probability density functions and standard distributions -- you can condition a random variable on any measurable subset of the probability space, for example, so you could condition Y on 0 < X < 3, which wouldn't be possible to evaluate with density functions. Or you can construct random variables which have no density function. I'm not sure this has great practical use, but it's a very interesting system.

cf 11y ago

What's interesting about most complaints of these systems is people talk about their poor performance or scalability? That is usually more a consequence of using MCMC or other inference algorithm than the language itself. MCMC is a very slow inference algorithm. Its primary advantage was that for well-known models it could be coded up much more simply than a fancier inference technique. When you consider variational methods and newer streaming methods based on things like Assumed Density Filtering you can get really great scalable performance. The point of probabilistic programming is write inference algorithms once for a large class of models and be done. So the advantage of using a fancier method is amplified. This means paradoxically probabilistic programming should eventually be faster than existing methods rather than slower, since you can reuse these fancier inference methods for new models. This is a very active field so this progress is only starting to be appear in the existing systems.

detaro 11y ago
> The point of probabilistic programming is write inference algorithms once for a large class of models and be done. So the advantage of using a fancier method is amplified. So that should be something where a few standard libraries or toolsets should emerge that push out the "easy-to-implement" default choice? Are there any contenders yet? (As you might be able to tell, I don't really know anything about the field)
- cf 11y ago
  I know STAN and Figaro are going to push out inference methods like I mention, but my hope is eventually all of the ones mentioned in the article do this. I like thinking of this in terms of the standard library that needs to be built out. All the systems are making great progress in this regard.
x0x0 11y ago
Ease of coding is not the primary advantage of mcmc. The (giant) disadvantage of variational inference is the user needs to derive equations and understand quite a bit of math, where gibbs or other samplers like those in bugs/openbugs/jags/stan can work with the factored distributions and require much less mathematical sophistication from users.

nextos 11y ago

It seems Markov Logic nets can scale to really big problems: * https://code.google.com/p/rockit/ https://code.google.com/p/rockit/ * http://i.stanford.edu/hazy/hazy/tuffy/ http://i.stanford.edu/hazy/hazy/tuffy/ But they seem to be getting less and less coverage in probabilistic programming. Perhaps they are considered too inexpressive?