6 ms·
This is a pretty old post of mine (2007), and I was a bit surprised to see it on Hacker News this morning! For those of you who find all the Haskell impenetrabl
by ekidd 14y ago
This is a pretty old post of mine (2007), and I was a bit surprised to see it on Hacker News this morning! For those of you who find all the Haskell impenetrable, let me summarize:
1. As raverbashing points out, the key takeaway here is "removing the impossible and normalizing is equivalent to Bayes rule." This can be represented in a programming language using a "die unless X is true" instruction and some magic behind the scenes. It's nothing more than a trivial generalization of McCarthy's "AMB" operator for LISP with some weights attached to each possibility.
2. The nicest thing about this approach is that it makes it very easy to reason about probability correctly. For example, the Monty Hall problem, which is known for being counter-intuitive, can be stated very clearly with all the assumptions visible.
3. The original audience of this post was programming language designers and people who understand Haskell and monads. For everybody else, I'd like to apologize for the notation. "Simple" is relative, and in this post, I take a lot of background knowledge for granted.
4. To implement this idea, you can choose between several approaches: explicit enumeration of all possibilities (which explodes exponentially), particle systems, or weighted particle systems. The latter two would be ideally compiled down to GPU code for big problems. Unfortunately, you can't use either Kalman filters or modern Bayesian network solvers, which somewhat limits the usefulness of this approach. Basically, it will scale to lots of data points, but not to complex Bayesian networks.
5. Dealing with different false-positive and false-negative rates would add a couple lines of code to this example.
If you'd like a more detailed writeup of this idea, see: http://www.randomhacks.net/darcs/probability-monads/probability-monads.pdf http://www.randomhacks.net/darcs/probability-monads/probabil... I'll be back online in a couple of hours and I'll be happy to answer any further questions.
- dllthomas 14y agohttp://en.wikipedia.org/wiki/Monty_Hall http://en.wikipedia.org/wiki/Monty_Hall
- deleted 14y ago[deleted]
- apw 14y agoDo you really mean that "removing impossibility and renormalizing" is equivalent to Bayes Rule? For example, imagine that we know a priori that a coin has only two possible biases, both of which are neither 0 nor 1. When I use Bayes Rule to update my belief in the two biases in response to observed data, I don't see how I am removing any impossibilities. It seems much more like I am downweighting the unlikely bias and upweighting the likely bias.
- ekidd 14y agoExcellent question. Let me unpack a bit. Here's an example from the PDF I linked above: fluStatusGivenPositiveTest = do fluStatus <- percentWithFlu 10 testResult <- if fluStatus == Flu then percentPositive 70 else percentPositive 10 guard (testResult == Pos) return fluStatus In this code, you can read the operator "<-" as "pick a possible value from a probability distribution." Until we look at the test results, there are four possible "worlds" with the following probabilities: 7% (Flu, Pos) 3% (Flu, Neg) 9% (Healthy, Pos) 81% (Healthy, Neg) But once we see the the test result is "Pos", then all those worlds with "Neg" become impossible, giving us: 7% (Flu, Pos) 9% (Healthy, Pos) But our probabilities don't add up to 100% any more. Fortunately, all we need to do is normalize them. That gives us: 43.75% (Flu, Pos) 56.25% (Healthy, Pos) This normalization step is basically the denominator in Bayes rule. As noted above, the number of worlds grows exponentially with the number of probabilistic choices we make. So if you want to use this on a larger problem, you need to use sampling (run the program N times, tabulate the results) or a particle system (which essentially does the same thing in parallel).
- apw 14y agoUntil we look at the coin flip results for a coin known a priori to have only two possible biases a and b, where neither a nor b equal 0 or 1, there are two possible "worlds" with the following probabilities: 0.5 (a) 0.5 (b) But once we see that the first coin flip is tails, which we code as -1, then we update using Bayes rule, giving us: p(-1|a)p(a)/p(-1) (a, -1) p(-1|b)p(b)/p(-1) (b, -1) I just don't see any removing of possible worlds here. Am I doing this wrong?