5 ms·

I'll admit, I looked over https://probmods.org https://probmods.org and I don't really get "probabilistic programming". It just looks like you call random() som

I'll admit, I looked over https://probmods.org https://probmods.org and I don't really get "probabilistic programming". It just looks like you call random() sometimes...? Is there something going on in the language runtime that I'm missing?

sp332 12y ago
You create a probabilistic model. So you tell the compiler: there's a 50% chance this will be true, and the program will compute both sides and say, there's a 50% chance for this result and 50% for this other result.
- tree_of_item 12y ago
  How is this not trivially done with something like (random 0.5)? There must be something significant going on in, say, http://projects.csail.mit.edu/church/wiki/Church http://projects.csail.mit.edu/church/wiki/Church for it promote this "probabilistic programming" term. What I'm trying to say is that at the moment it looks like every programming language ever is trivially capable of expressing these sorts of programs using the random number generators that are wildly common. What is different in this programming paradigm? In particular, this paragraph: > Another way of thinking about this: unlike a traditional program, which only runs in the forward directions, a probabilistic program is run in both the forward and backward direction. It runs forward to compute the consequences of the assumptions it contains about the world (i.e., the model space it represents), but it also runs backward from the data to constrain the possible explanations. Are these programs truly running backwards? Is there some backwards reduction relation in their semantics that I could look at?
  - sp332 12y ago
    I'm not an expert on probabilistic algorithms, but one thing you're missing is that it computes all the possibilities. (random 0.5) just picks one.
  - neurobro 12y ago
    Hand-wavy explanation: (random 0.5) could represent a fair coin toss, e.g. "generate a 0 or 1 with probability 0.5". But the coin isn't necessarily fair, so we can't assume the probability is 0.5. In fact, we'd like to learn what the probability is by observing a lot of coin tosses and counting the heads vs. tails. That's a very simple machine learning model. More complex models involve graphs of random variables where the structure of the graph represents conditional probabilities, and often the variables actually generate other probability distributions instead of scalar values. It doesn't take long before it becomes impossible to calculate the optimal values and parameters of the model. Much of statistical machine learning research involves looking for better ways to approximate solutions to these models, as well as finding graphs that are a good fit for real-world data. Presumably, a programming language designed around this kind of task would make it easier to explore and develop larger, more intricate models.
  - tristanz 12y ago
    Most probabilistic programming languages give you samples from the distribution of execution traces that are consistent with the observed data. No probabilistic programming languages actually run things backward. They all use standard Bayesian computational methods, like MCMC over possible execution traces. The beauty is the user can forget about this and just build generative models with primitives every language contains -- random numbers. The language then offers a way for users to query plausible values for the unobserved elements of the model. Conceptually, the easiest way to understand things is via rejection sampling. You can "run things backward" but running things forward and just keeping the traces that match the observed output. That's Bayesian inference. Unfortunately, the probability of matching the observed output is zero for most problems so you need to use more advanced methods. Most accounts gloss over these methods since it's a huge research area. Running things backwards is also not a perfect analogy because if fails to account for the probability distribution you start with.
gliese1337 12y ago
The power of probabilistic programming is not in running the programs forward to generate output. That pretty much does just come down to calling random() sometimes to alter the flow of the program. Having built-in syntax for that would be nice for modelling stochastic processes, but we can already do that. The big deal is being able to run the program backwards. I.e., you already have some set of output, obtained from some other source, and you want to figure out how that output could have been produced (i.e., how the source works). So, you write a probabilistic program that encodes your various hypotheses about how the source process works, and then run it backwards to figure out what the forward execution path would have had to have been to produce that output, and thus which hypothesis is correct. That's what "inference" refers to. Inference is a basic process in scientific investigation- come up with a bunch of hypotheses, do an experiment that generates data through physical processes independently of whatever you hypothesized, and then go backwards to figure out which of your hypotheses would have had to have been true in order to get the experimental output that you did. Which hypothesis is true corresponds to a particular execution path through a probabilistic program, so having efficient implementations of probabilistic languages means we could do much better at accurate analysis of data, which is Good For Science.
- j2kun 12y ago
  > so having efficient implementations of probabilistic languages means we could do much better at accurate analysis of data What does a compiler-level implementation of probabilistic analysis have to do with accuracy?
  - AlexCoventry 12y ago
    It makes it cheaper to experiment with different models.
    - j2kun 12y ago
      Still not really a statement about accuracy...
      - 12y ago
defen 12y ago
Here's my understanding based on the article alone; would love corrections if I'm wildly missing the mark here. Let's say you want to determine if a coin is fair, but you don't know any statistics. What you can do is write a program (model) that represents the fair coin flip process. It might be as simple as: flips = [random.choice([True, False]) for x in range(0, 10)] Then you flip your coin 10 times and feed the output into your program, and it gives you some indication of the probability that the coin is fair.
- basyt 12y ago
  seemingly the program is also run backwards. so maybe it will try coins with various biases until it determines the model that gives the fair flipping? i am speaking from what i gathered reading the article and the other comments. seems pretty interesting to me.
araes 12y ago
I can attempt to provide a more concrete example of real-world use. At the end of the day, it mostly comes down to preserving the idea that there is a probability associated with the occurrence of a result. One of the easiest versions of this I've seen is the two factor model with: mean value + deviation In one of my lives, I've calculated ballistics. When calculating ballistics, you can probably think of a lot of factors that might go into it. - Release conditions (velocities, angles, ect...) - Environmental / trajectory conditions (winds, gusts, different media, ect...) - Impact conditions and behaviour (spalling, rebounding, fragmentation, yatta....) For more reading, you can look at something like: http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20070028865.pdf http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/2007002... (only uses probabilistic methods for transport) Anyhow, one way to attempt modelling of this is to run a Monte-carlo of the parameter space. Effectively, you run all the permutations of release, all the permutations of those permutations for transport, and then all the permutations^3 of the impact variation. Now, one of the advances that has come about from efforts like that, is that probabilistic models for some of these steps have been created to approximate the results in a time effective manner. For example, in the above, they note that instead of running a Monte-carlo of trajectories and releases, a single trajectory is instead run, and then a probabilistic flight cone is created which calculates parameters based on standard deviation from the mean. A general, and robust version of a language like this would allow you to specify all of your parameters with similar types of effects. IE, you would have mean and then deviation or statistical curve envelopes you would provide around that mean which would be propagated through calculations, and spit out an overall convoluted probability at the end of the pipeline. In ballistics for example, you might have a mean release condition, with statistical variation on release. That would then be fed into a trajectory calculation, which would do so based on a mean, but with a transport cone that does statistical variation on the mean flight. Finally, impact might be calculated around a mean value, but would then carry the statistical variation through the release and flight. At the end, you would then be able to pull a probability number, as well as impact condition at that probability from any point in the potential impact zone. At least that's how I see the use of probabilistic languages.
- mturmon 12y ago
  Everything you say is true, and that only covers the forward problem: given a multi-level model with stochastic dependencies at each stage (like winds, fragmentation, etc., that you list), calculate the overall distribution of the output. At its simplest, the forward problem is like a functional composition: y = F( G( H(x) ) ) where F, G, and H are all noisy, and you want to characterize y. @gliese1337 nearby, in an excellent comment, addresses the more complex inverse problem: when you have outputs (y's above) from such a process, how do you determine the most likely model (F, G, H) that produced it? So for example, if you have a bunch of crater ejecta, what can you tell me about the mass of the incoming objects?
BenoitEssiambre 12y ago
It's true that this Church language seems to be little more than Scheme with a few clever tricks that allows it to walk through code paths and execute programs in clever probabilistic ways. I don't claim to understand it all, however, the clever tricks seem to be very clever and things are put together so well with emphasis on just the right concepts that, to me at least, it makes certain aspects of probabilistic models like the relationship between correlation, causation, induction and deduction much clearer than anything I have seen before. Years ago when I was a grad student, I tried to tackle some NLP problems using similar approaches (ie. unsupervised generative bayesian models organized in hierarchical ways that try to mimic our intuitive concept of causality) but mostly failed at making much headway. I couldn't figure out some of the math and my models usually failed to perform any better than other probabilistic algorithms. No one at my university did anything similar or knew much about bayesian probabilities back then which didn't help. I always believed in the approach however and until I stumbled on this book, never knew there was significant progress being made. I wish it was available to build upon when I was a student. In the "Learning as Conditional Inference" chapter the section "Inferring an Arithmetic Expression" show the first example I have seen of a legitimate and flexible approach that could some day allow a computer to program itself. I mean the algorithm is still far from doing general programming tasks but I could imagine extending the approach so that given a programming language grammar and a unit tests as inputs, a computer could write a well chosen and simplified program that pass the tests (simplified with the automatic Occam's razor inherent in the bayesian approaches) . That to me is mind-blowing. Now not all is perfect in the book, the "Inference about Inference" chapter seems oversimplified to me. The last few chapter seem to get a bit mathematically ad-hoc with an alpha parameter introduced to tie categories and sub-categories together in hierarchical models without much mathematical justification. On the other hand, there is strong evidence for this kind of transfer of information in hierarchies and it's not totally unreasonable to make up a parameter, assign it a bayesian uninformative prior that reflects ignorance of how this parameter should be set and try to induce a value for it from data. It's a perfect example of meta probabilities where probabilities are used to guess parameters that govern other probabilities. It's very bayesian. Anyways before reading this book I was convinced that general AI was not going to happen in my lifetime. Now I'm not so sure.

sp332 12y ago

You create a probabilistic model. So you tell the compiler: there's a 50% chance this will be true, and the program will compute both sides and say, there's a 50% chance for this result and 50% for this other result.

tree_of_item 12y ago
How is this not trivially done with something like (random 0.5)? There must be something significant going on in, say, http://projects.csail.mit.edu/church/wiki/Church http://projects.csail.mit.edu/church/wiki/Church for it promote this "probabilistic programming" term. What I'm trying to say is that at the moment it looks like every programming language ever is trivially capable of expressing these sorts of programs using the random number generators that are wildly common. What is different in this programming paradigm? In particular, this paragraph: > Another way of thinking about this: unlike a traditional program, which only runs in the forward directions, a probabilistic program is run in both the forward and backward direction. It runs forward to compute the consequences of the assumptions it contains about the world (i.e., the model space it represents), but it also runs backward from the data to constrain the possible explanations. Are these programs truly running backwards? Is there some backwards reduction relation in their semantics that I could look at?
- sp332 12y ago
  I'm not an expert on probabilistic algorithms, but one thing you're missing is that it computes all the possibilities. (random 0.5) just picks one.
- neurobro 12y ago
  Hand-wavy explanation: (random 0.5) could represent a fair coin toss, e.g. "generate a 0 or 1 with probability 0.5". But the coin isn't necessarily fair, so we can't assume the probability is 0.5. In fact, we'd like to learn what the probability is by observing a lot of coin tosses and counting the heads vs. tails. That's a very simple machine learning model. More complex models involve graphs of random variables where the structure of the graph represents conditional probabilities, and often the variables actually generate other probability distributions instead of scalar values. It doesn't take long before it becomes impossible to calculate the optimal values and parameters of the model. Much of statistical machine learning research involves looking for better ways to approximate solutions to these models, as well as finding graphs that are a good fit for real-world data. Presumably, a programming language designed around this kind of task would make it easier to explore and develop larger, more intricate models.
- tristanz 12y ago
  Most probabilistic programming languages give you samples from the distribution of execution traces that are consistent with the observed data. No probabilistic programming languages actually run things backward. They all use standard Bayesian computational methods, like MCMC over possible execution traces. The beauty is the user can forget about this and just build generative models with primitives every language contains -- random numbers. The language then offers a way for users to query plausible values for the unobserved elements of the model. Conceptually, the easiest way to understand things is via rejection sampling. You can "run things backward" but running things forward and just keeping the traces that match the observed output. That's Bayesian inference. Unfortunately, the probability of matching the observed output is zero for most problems so you need to use more advanced methods. Most accounts gloss over these methods since it's a huge research area. Running things backwards is also not a perfect analogy because if fails to account for the probability distribution you start with.

gliese1337 12y ago

The power of probabilistic programming is not in running the programs forward to generate output. That pretty much does just come down to calling random() sometimes to alter the flow of the program. Having built-in syntax for that would be nice for modelling stochastic processes, but we can already do that. The big deal is being able to run the program backwards. I.e., you already have some set of output, obtained from some other source, and you want to figure out how that output could have been produced (i.e., how the source works). So, you write a probabilistic program that encodes your various hypotheses about how the source process works, and then run it backwards to figure out what the forward execution path would have had to have been to produce that output, and thus which hypothesis is correct. That's what "inference" refers to. Inference is a basic process in scientific investigation- come up with a bunch of hypotheses, do an experiment that generates data through physical processes independently of whatever you hypothesized, and then go backwards to figure out which of your hypotheses would have had to have been true in order to get the experimental output that you did. Which hypothesis is true corresponds to a particular execution path through a probabilistic program, so having efficient implementations of probabilistic languages means we could do much better at accurate analysis of data, which is Good For Science.

j2kun 12y ago
> so having efficient implementations of probabilistic languages means we could do much better at accurate analysis of data What does a compiler-level implementation of probabilistic analysis have to do with accuracy?
- AlexCoventry 12y ago
  It makes it cheaper to experiment with different models.
  - j2kun 12y ago
    Still not really a statement about accuracy...
    - 12y ago

defen 12y ago

Here's my understanding based on the article alone; would love corrections if I'm wildly missing the mark here. Let's say you want to determine if a coin is fair, but you don't know any statistics. What you can do is write a program (model) that represents the fair coin flip process. It might be as simple as: flips = [random.choice([True, False]) for x in range(0, 10)] Then you flip your coin 10 times and feed the output into your program, and it gives you some indication of the probability that the coin is fair.

basyt 12y ago
seemingly the program is also run backwards. so maybe it will try coins with various biases until it determines the model that gives the fair flipping? i am speaking from what i gathered reading the article and the other comments. seems pretty interesting to me.

araes 12y ago

I can attempt to provide a more concrete example of real-world use. At the end of the day, it mostly comes down to preserving the idea that there is a probability associated with the occurrence of a result. One of the easiest versions of this I've seen is the two factor model with: mean value + deviation In one of my lives, I've calculated ballistics. When calculating ballistics, you can probably think of a lot of factors that might go into it. - Release conditions (velocities, angles, ect...) - Environmental / trajectory conditions (winds, gusts, different media, ect...) - Impact conditions and behaviour (spalling, rebounding, fragmentation, yatta....) For more reading, you can look at something like: http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20070028865.pdf http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/2007002... (only uses probabilistic methods for transport) Anyhow, one way to attempt modelling of this is to run a Monte-carlo of the parameter space. Effectively, you run all the permutations of release, all the permutations of those permutations for transport, and then all the permutations^3 of the impact variation. Now, one of the advances that has come about from efforts like that, is that probabilistic models for some of these steps have been created to approximate the results in a time effective manner. For example, in the above, they note that instead of running a Monte-carlo of trajectories and releases, a single trajectory is instead run, and then a probabilistic flight cone is created which calculates parameters based on standard deviation from the mean. A general, and robust version of a language like this would allow you to specify all of your parameters with similar types of effects. IE, you would have mean and then deviation or statistical curve envelopes you would provide around that mean which would be propagated through calculations, and spit out an overall convoluted probability at the end of the pipeline. In ballistics for example, you might have a mean release condition, with statistical variation on release. That would then be fed into a trajectory calculation, which would do so based on a mean, but with a transport cone that does statistical variation on the mean flight. Finally, impact might be calculated around a mean value, but would then carry the statistical variation through the release and flight. At the end, you would then be able to pull a probability number, as well as impact condition at that probability from any point in the potential impact zone. At least that's how I see the use of probabilistic languages.

mturmon 12y ago
Everything you say is true, and that only covers the forward problem: given a multi-level model with stochastic dependencies at each stage (like winds, fragmentation, etc., that you list), calculate the overall distribution of the output. At its simplest, the forward problem is like a functional composition: y = F( G( H(x) ) ) where F, G, and H are all noisy, and you want to characterize y. @gliese1337 nearby, in an excellent comment, addresses the more complex inverse problem: when you have outputs (y's above) from such a process, how do you determine the most likely model (F, G, H) that produced it? So for example, if you have a bunch of crater ejecta, what can you tell me about the mass of the incoming objects?

BenoitEssiambre 12y ago

It's true that this Church language seems to be little more than Scheme with a few clever tricks that allows it to walk through code paths and execute programs in clever probabilistic ways. I don't claim to understand it all, however, the clever tricks seem to be very clever and things are put together so well with emphasis on just the right concepts that, to me at least, it makes certain aspects of probabilistic models like the relationship between correlation, causation, induction and deduction much clearer than anything I have seen before. Years ago when I was a grad student, I tried to tackle some NLP problems using similar approaches (ie. unsupervised generative bayesian models organized in hierarchical ways that try to mimic our intuitive concept of causality) but mostly failed at making much headway. I couldn't figure out some of the math and my models usually failed to perform any better than other probabilistic algorithms. No one at my university did anything similar or knew much about bayesian probabilities back then which didn't help. I always believed in the approach however and until I stumbled on this book, never knew there was significant progress being made. I wish it was available to build upon when I was a student. In the "Learning as Conditional Inference" chapter the section "Inferring an Arithmetic Expression" show the first example I have seen of a legitimate and flexible approach that could some day allow a computer to program itself. I mean the algorithm is still far from doing general programming tasks but I could imagine extending the approach so that given a programming language grammar and a unit tests as inputs, a computer could write a well chosen and simplified program that pass the tests (simplified with the automatic Occam's razor inherent in the bayesian approaches) . That to me is mind-blowing. Now not all is perfect in the book, the "Inference about Inference" chapter seems oversimplified to me. The last few chapter seem to get a bit mathematically ad-hoc with an alpha parameter introduced to tie categories and sub-categories together in hierarchical models without much mathematical justification. On the other hand, there is strong evidence for this kind of transfer of information in hierarchies and it's not totally unreasonable to make up a parameter, assign it a bayesian uninformative prior that reflects ignorance of how this parameter should be set and try to induce a value for it from data. It's a perfect example of meta probabilities where probabilities are used to guess parameters that govern other probabilities. It's very bayesian. Anyways before reading this book I was convinced that general AI was not going to happen in my lifetime. Now I'm not so sure.