Comment by tree_of_item | Hacker News Reader

Comment by tree_of_item | Hacker News Reader

Parent Full thread

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 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?

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.

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.

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.

Reply on news.ycombinator.com