9 ms·

Bayes' rule in Haskell (2007)

176 points by tikhonj 14y ago

tripzilch 14y ago
This actually explains a lot on Google's abysmal customer service, especially where they appear way too triggerhappy on the account-suspensions and pagerank penalizing for appearing too spammy.
- adlpz 14y ago
  Google lacks customer service. They are not interested in you, but in volume. And you handle volume through statistics. If you happen to fall on an edge case, they won't really care. Because you fall in the error.
- epo 14y ago
  People who try to exploit Google on the margin risk falling the wrong side of that margin. If that happens then Google are not interested in your feeble "but if you look at this way" justifications. This is not abysmal customer service, it is simply not giving abusive idiots the benefit of the doubt. If they don't like it then they can get free service elsewhere.
raverbashing 14y ago
Well, the quoted statement mentions bayesian filtering which is an application of bayesian rule, but it's not as simple as an if. The other quote 'removing the impossible and normalizing is equivalent to Bayes rule' is a good thing to remember. Just to mention that drug tests have different rates of false positives and negatives, it's not usually '1% failure'
wfunction 14y ago
Is it just me who doesn't understand what the body of the article had to do with Google or Microsoft?
- cturner 14y ago
  It made some sense to me. The author used the G/M thing to introduce an idea: that it's powerful to think at scale. And then seeks a way to make a thinking-at-scale structure (bayes' rule) as accessible to the programmer as an if statement, by putting it in the language. That was the only bit of the article that did make sense to me :) I get lost trying to read ML-style languages.
- sordina 14y ago
  What people are referring to with respect to Google is that if higher-level statistical operations are as easy as an if statement, then this may explain why google takes (presumably amorally) such a statistical approach their customers (because it is easy to).
  - wfunction 14y ago
    But what did any of that have to do with Microsoft, or even Google's practices? The entire article was a tutorial on Bayes's rule, with a completely irrelevant introductory paragraph thrown in at the top. Nothing about Google or Microsoft's practices was actually mentioned anywhere.
    - sordina 14y ago
      Yes, the article was about simplifying statistical operations. The comments were inferring that some observed practices may have followed as a consequence. I'd prefer to discus the meat of the article, but it's not unusual to see comments go off on a tangent like this.
      - wfunction 14y ago
        What annoys me is when people write irrelevant provocative introductions just to attract attention to their otherwise not so interesting writings.
        dllthomas 14y ago
millstone 14y ago
Here's more of the quote: Look at how Google does spell checking: it's not based on dictionaries; it's based on word usage statistics of the entire Internet, which is why Google knows how to correct my name, misspelled, and Microsoft Word doesn't. It's also why Google knows "Jews should be wiped out" and "Muslims should be exterminated" and "blacks are ruining America" and "whites are neanderthals", all suggestions based on the first two words of each phrase. Yes, I'm provoking Google - but surely people also encounter these by accident. If Microsoft shipped a version of Office that suggested any of the above as "corrections," they would be lambasted for it, and rightly so. Why does Google get a pass? Is it because our standard of decency is so much lower on the Internet? Or is it because we know that Google is merely reflecting popular sentiment on the Internet, and so the true villain is ourselves? (In fairness, Bing happily suggests equally monstrous ideas.)
- ivanca 14y ago
  Both, Office haves enterprise as target market and people know this and they set their expectatives in this context; the same thing happens in the Internet where the context is "everyone in the world" and is assumed that most things are popularity-driven (likes, re-tweets, etc).
- anonymous 14y ago
  Because unethical sentences aren't a criminal offence? I mean, if you gave me the first two words from those sentences and asked "what's the most probable next words", I would give you pretty much the same answer. Let me try some more and I'll put my answer next to google's "lawyers are" -> "greedy sharks" (actual suggestion: scum) "gays should" -> "be killed" (actual suggestion: be killed) "marijuana should" -> "be legal" (actual suggestion: be legalized) "drug users should" -> "get help" (actual suggestion: be shot) "macs are" -> "better than windows" (actual suggestion: better than pcs) As you can see, google's opinion on what is the largest cluster of opinions on the subject aligns with what I expect in 4 out of 5 cases. Also note how you're getting both the suggestion that marijuana should be legal and that people who smoke it should be shot. These suggestions aren't google's opinion on the matter, it's what google expects you to think. Thankfully, they're wrong most of the time. In the end, it's not impossible to write an ethical filter the same way google has a spam filter, the only reason they haven't done it is because there's no pressure to do so. If you don't want to see such suggestions on google, you have two options: 1) Make people not talk about killing gays or how all lawyers are scum 2) Pressure google to add a filter Also, white people really are partly neanderthal https://en.wikipedia.org/w/index.php?title=Neanderthal&oldid=553113335#Interbreeding_hypotheses https://en.wikipedia.org/w/index.php?title=Neanderthal&o...
doctorpangloss 14y ago
I entered expecting a cool implementation of Bayes through a simple if statement. Instead, I saw Bayes' rule in Haskell, a form that's more idiosyncratic than probability expressions. Simple is in the eye of the beholder. Perhaps making monads isn't actually making Bayes' rule simpler.
- wfunction 14y ago
  +1 it was actually a rather horrifying presentation of Bayes's theorem. I would just explain it in 2 lines: P(Cause and Effect) = P(Cause) × P(Effect given Cause) = P(Effect) × P(Cause given Effect) so P(Cause) = P(Effect) × P(Cause given Effect) ÷ P(Effect given Cause)
  - jhdevos 14y ago
    Naming it Cause and Effect is misleading; it makes it seem like bayes rule only applies when there is a causal relation somewhere. It also make the symmetry of the first line seem off. I would write the first line as P(A and B are both true) = P (A is true) x P (B is also true, given that we know A is already true) = P (B is true) x P (A is also true, given that we know B is already true)
    - wfunction 14y ago
      I was actually going to write A and B at first, but then realized that wouldn't show the relationship of the formula to the disease example very obviously. I thought it'd be better to make it easier to understand (and more practical) by showing how it helps you infer causes from effects.
  - ajanuary 14y ago
    Two lines of equations aren't a simple to use programming tool. It's debatable whether TFA achieved that goal, but you certainly didn't.
    - pekk 14y ago
carlob 14y ago
Shameless plug: Mathematica knows about Bayes' rule and makes reasoning about it quite simple. If you look here [0] you'll find Bayes' rule in the section: "Properties and relations". What makes it extremely powerful is that it's fully symbolic so you can do things like: Probability[x^2 > a \[Conditioned] x < b, x \[Distributed] NormalDistribution[m, s]] and have it evalate to a bunch of Erf… [0] http://reference.wolfram.com/mathematica/ref/Probability.html http://reference.wolfram.com/mathematica/ref/Probability.htm...
forrestthewoods 14y ago
I still don't understand bayesian statistics and every article I've read to try and learn has had syntax I didn't understand. I just don't know lisp/haskell/etc syntax. My college math stopped at calc 3 and it's been many years since I took that. Is there a good "bayesian probability for dummies" type resource out there? Any suggestions?
- astrec 14y ago
  Try: An Intuitive Explanation of Eliezer Yudkowsky’s Intuitive Explanation of Bayes’ Theorem http://commonsenseatheism.com/?p=13156 http://commonsenseatheism.com/?p=13156
  - huherto 14y ago
    Thanks for the link. I loved this quote. Seeing the world through the lens of Bayes’ Theorem is like seeing The Matrix. Nothing is the same after you have seen Bayes.
- pfortuny 14y ago
  You probably don't understand it because nobody has taken the effort to explain it to you simply. Everything I have seen on the Internet (especially programming related sources) take a lot for granted and just spread a little code here and there. Also, a good idea is not "trying to turn your mind inside out", which is what seems to be needed from a lot of explanations I have read. It is easy, it is simple, it is normal. I am sorry I do not have a reference handy (because of the above) but those are good suggestions (otherwise I would not be writing them) that have helped me overcome similar "difficulties". Edit: Cannot help saying it. The 'a priori' and 'a posteriori' and all those terms are just fancy words (which mean what they signal) which scare a lot of people away from something, I repeat, natural.
- RobAley 14y ago
  If you understand procedural languages better, the following article discusses a basic naive bayesian classifier and implements it in PHP : http://phpir.com/bayesian-opinion-mining http://phpir.com/bayesian-opinion-mining
willvarfar 14y ago
I would imagine that in real life you track the reliability of a drugs test as % false positive and % false negative, rather than a single % reliable?
wfunction 14y ago
> "What if Bayes' rule was as simple as an if statement?" As the article clearly showed, this is wishful thinking. And there's one simple reason why: - Bayesian inference is generally computationally intractable. - "If" statements are quite tractable. Any language in which you could perform Bayesian inference as easily as you perform "if" statements in would result in horrifyingly slow code and become useless.
- flipgimble 14y ago
  You are thinking about languages that are targeting a single machine at a time. That's the way Microsoft thinks with their history in client-side software. The implication of the quote is that Google attempts to implement the seemingly intractable algorithms by running them on huge clusters, and returning the results to a large audience that makes the computation worth it. If your language targets a data center then having a language support Bayesian inference might be useful.
- duaneb 14y ago
  I think the original quotation simply used it as a rhetorical device to indicate difference in approach at a more abstract level than literally replacing conditionals with Bayes filters.
- gizmo686 14y ago
  As I pointed out elsewhere in this thread, Quantom computer languages literally do this. Also, if you want to perform Bayseian inference, then it is equally as difficult computationally whether or not it can be expressed as simple 'if' statements. However, in terms of code simplicity, expressing it as simple if statements is easier.
  - wfunction 14y ago
    > Quantom computer languages literally do this Quantum computers also make the sun rise every morning. I can claim anything about what they do, because they don't exist.
    - 14y ago
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 ago
  http://en.wikipedia.org/wiki/Monty_Hall http://en.wikipedia.org/wiki/Monty_Hall
  - deleted 14y ago
    [deleted]
- apw 14y ago
  Do 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.
auggierose 14y ago
This is funny, because Microsoft Research actually works on that. http://link.springer.com/chapter/10.1007%2F978-3-642-19718-5_5 http://link.springer.com/chapter/10.1007%2F978-3-642-19718-5...
visarga 14y ago
> Google uses Bayesian filtering the way Microsoft uses the if statement. I am sure it depends on the employee, not the company. MS has done amazing things in machine learning. I love Vowpal Wabbit which is maintained by an ex Yahoo, currently MS employee. I am amazed at the complexity of the Kinect software to translate images into body configurations. Just today I have seen another amazing tecnology from MS: IllumiRoom. Check out the vid : http://www.youtube.com/watch?v=nGGMv9RnJIA http://www.youtube.com/watch?v=nGGMv9RnJIA Check out MAVIS too, a system for transcribing videos and making them searchable. It's a little dated, but very cool nonetheless. So, while I still think Google is superior, MS is making some amazing stuff too, from time to time.
- zaphar 14y ago
  The quote wasn't about their technology. It was about their decision making. Google is famous for data driven decision making.
- abecedarius 14y ago
  The quote was from most of a decade ago; probably truer then. (Though Clippy was Bayesian. I read somewhere a claim that its awfulness came from management messing with it.)
Eliezer 14y ago
I've totally seen a LISP dialect with probabilistic execution and Bayesian updating built in - it was one of the lecturers at SPARC 2012 - but damned if I can remember the name of the speaker or the LISP dialect. Roughly, using this dialect, you could build a program that would randomly branch at various points, then keep only the cases of the program that matched some property, and ask what the probabilities were for some other property over those cases. I think the keyword was rejection-query but the first page of Google doesn't turn up the desired result for that.
- rawatson 14y ago
  Church? I'm not very familiar with the language but I believe it sounds similar to what you're describing. http://projects.csail.mit.edu/church/wiki/Church http://projects.csail.mit.edu/church/wiki/Church
- gmodena 14y ago
  Possibly church? http://projects.csail.mit.edu/church/wiki/Church http://projects.csail.mit.edu/church/wiki/Church
- JadeNB 14y ago
  It's not a Lisp, but there aren't many probabilistic programming languages, so you may be interested in IBAL (http://www.gelberpfeffer.net/Papers/ibal-ch.pdf http://www.gelberpfeffer.net/Papers/ibal-ch.pdf).
gizmo686 14y ago
As much as I like Haskell, if your goal is to make Bayes' rule as simple as an if statement, I doubt you can do better than quantum computer emulators. Say the probability of being a User is 1%. You can initialize your variable, X, to a superpossition, with 99% chance of being clean, and a 1% chance of being a user. Now, the function, f(x) for the test is such that: f(user) = (99% positive) + (1% negative) f(clean) = (1% positive) + (99% negative) Take y=f(x). Now, look at the quantum state of your machine (this is why we are on an emulator). Each of the 4 potential states have a certain probability associated with them. The (theoretical) slowdown of using a quantom emulator is the fact that as the size of your memory increases, you have exponentially more states to deal with. But, because we would need to deal with the same number of states any way, this is not actually relevant. I should also mention that using a real quantom computer does not provide a (trivial) speed up to this prosess. This is because, while the quantom state contains all 4 possibilities with some probability, when we go to measure it, we will only see 1 of the 4 states. Not only will this not give us a probability, but we would need to re-run the computation to measure it again.

176 points by tikhonj 14y ago

This actually explains a lot on Google's abysmal customer service, especially where they appear way too triggerhappy on the account-suspensions and pagerank penalizing for appearing too spammy.

adlpz 14y ago
Google lacks customer service. They are not interested in you, but in volume. And you handle volume through statistics. If you happen to fall on an edge case, they won't really care. Because you fall in the error.
epo 14y ago
People who try to exploit Google on the margin risk falling the wrong side of that margin. If that happens then Google are not interested in your feeble "but if you look at this way" justifications. This is not abysmal customer service, it is simply not giving abusive idiots the benefit of the doubt. If they don't like it then they can get free service elsewhere.

raverbashing 14y ago

Well, the quoted statement mentions bayesian filtering which is an application of bayesian rule, but it's not as simple as an if. The other quote 'removing the impossible and normalizing is equivalent to Bayes rule' is a good thing to remember. Just to mention that drug tests have different rates of false positives and negatives, it's not usually '1% failure'

wfunction 14y ago

Is it just me who doesn't understand what the body of the article had to do with Google or Microsoft?

cturner 14y ago
It made some sense to me. The author used the G/M thing to introduce an idea: that it's powerful to think at scale. And then seeks a way to make a thinking-at-scale structure (bayes' rule) as accessible to the programmer as an if statement, by putting it in the language. That was the only bit of the article that did make sense to me :) I get lost trying to read ML-style languages.
sordina 14y ago
What people are referring to with respect to Google is that if higher-level statistical operations are as easy as an if statement, then this may explain why google takes (presumably amorally) such a statistical approach their customers (because it is easy to).
- wfunction 14y ago
  But what did any of that have to do with Microsoft, or even Google's practices? The entire article was a tutorial on Bayes's rule, with a completely irrelevant introductory paragraph thrown in at the top. Nothing about Google or Microsoft's practices was actually mentioned anywhere.
  - sordina 14y ago
    Yes, the article was about simplifying statistical operations. The comments were inferring that some observed practices may have followed as a consequence. I'd prefer to discus the meat of the article, but it's not unusual to see comments go off on a tangent like this.
    - wfunction 14y ago
      What annoys me is when people write irrelevant provocative introductions just to attract attention to their otherwise not so interesting writings.
      - dllthomas 14y ago

millstone 14y ago

Here's more of the quote: Look at how Google does spell checking: it's not based on dictionaries; it's based on word usage statistics of the entire Internet, which is why Google knows how to correct my name, misspelled, and Microsoft Word doesn't. It's also why Google knows "Jews should be wiped out" and "Muslims should be exterminated" and "blacks are ruining America" and "whites are neanderthals", all suggestions based on the first two words of each phrase. Yes, I'm provoking Google - but surely people also encounter these by accident. If Microsoft shipped a version of Office that suggested any of the above as "corrections," they would be lambasted for it, and rightly so. Why does Google get a pass? Is it because our standard of decency is so much lower on the Internet? Or is it because we know that Google is merely reflecting popular sentiment on the Internet, and so the true villain is ourselves? (In fairness, Bing happily suggests equally monstrous ideas.)

ivanca 14y ago
Both, Office haves enterprise as target market and people know this and they set their expectatives in this context; the same thing happens in the Internet where the context is "everyone in the world" and is assumed that most things are popularity-driven (likes, re-tweets, etc).
anonymous 14y ago
Because unethical sentences aren't a criminal offence? I mean, if you gave me the first two words from those sentences and asked "what's the most probable next words", I would give you pretty much the same answer. Let me try some more and I'll put my answer next to google's "lawyers are" -> "greedy sharks" (actual suggestion: scum) "gays should" -> "be killed" (actual suggestion: be killed) "marijuana should" -> "be legal" (actual suggestion: be legalized) "drug users should" -> "get help" (actual suggestion: be shot) "macs are" -> "better than windows" (actual suggestion: better than pcs) As you can see, google's opinion on what is the largest cluster of opinions on the subject aligns with what I expect in 4 out of 5 cases. Also note how you're getting both the suggestion that marijuana should be legal and that people who smoke it should be shot. These suggestions aren't google's opinion on the matter, it's what google expects you to think. Thankfully, they're wrong most of the time. In the end, it's not impossible to write an ethical filter the same way google has a spam filter, the only reason they haven't done it is because there's no pressure to do so. If you don't want to see such suggestions on google, you have two options: 1) Make people not talk about killing gays or how all lawyers are scum 2) Pressure google to add a filter Also, white people really are partly neanderthal https://en.wikipedia.org/w/index.php?title=Neanderthal&oldid=553113335#Interbreeding_hypotheses https://en.wikipedia.org/w/index.php?title=Neanderthal&o...

doctorpangloss 14y ago

I entered expecting a cool implementation of Bayes through a simple if statement. Instead, I saw Bayes' rule in Haskell, a form that's more idiosyncratic than probability expressions. Simple is in the eye of the beholder. Perhaps making monads isn't actually making Bayes' rule simpler.

wfunction 14y ago
+1 it was actually a rather horrifying presentation of Bayes's theorem. I would just explain it in 2 lines: P(Cause and Effect) = P(Cause) × P(Effect given Cause) = P(Effect) × P(Cause given Effect) so P(Cause) = P(Effect) × P(Cause given Effect) ÷ P(Effect given Cause)
- jhdevos 14y ago
  Naming it Cause and Effect is misleading; it makes it seem like bayes rule only applies when there is a causal relation somewhere. It also make the symmetry of the first line seem off. I would write the first line as P(A and B are both true) = P (A is true) x P (B is also true, given that we know A is already true) = P (B is true) x P (A is also true, given that we know B is already true)
  - wfunction 14y ago
    I was actually going to write A and B at first, but then realized that wouldn't show the relationship of the formula to the disease example very obviously. I thought it'd be better to make it easier to understand (and more practical) by showing how it helps you infer causes from effects.
- ajanuary 14y ago
  Two lines of equations aren't a simple to use programming tool. It's debatable whether TFA achieved that goal, but you certainly didn't.
  - pekk 14y ago

carlob 14y ago

Shameless plug: Mathematica knows about Bayes' rule and makes reasoning about it quite simple. If you look here [0] you'll find Bayes' rule in the section: "Properties and relations". What makes it extremely powerful is that it's fully symbolic so you can do things like: Probability[x^2 > a \[Conditioned] x < b, x \[Distributed] NormalDistribution[m, s]] and have it evalate to a bunch of Erf… [0] http://reference.wolfram.com/mathematica/ref/Probability.html http://reference.wolfram.com/mathematica/ref/Probability.htm...

forrestthewoods 14y ago

I still don't understand bayesian statistics and every article I've read to try and learn has had syntax I didn't understand. I just don't know lisp/haskell/etc syntax. My college math stopped at calc 3 and it's been many years since I took that. Is there a good "bayesian probability for dummies" type resource out there? Any suggestions?

astrec 14y ago
Try: An Intuitive Explanation of Eliezer Yudkowsky’s Intuitive Explanation of Bayes’ Theorem http://commonsenseatheism.com/?p=13156 http://commonsenseatheism.com/?p=13156
- huherto 14y ago
  Thanks for the link. I loved this quote. Seeing the world through the lens of Bayes’ Theorem is like seeing The Matrix. Nothing is the same after you have seen Bayes.
pfortuny 14y ago
You probably don't understand it because nobody has taken the effort to explain it to you simply. Everything I have seen on the Internet (especially programming related sources) take a lot for granted and just spread a little code here and there. Also, a good idea is not "trying to turn your mind inside out", which is what seems to be needed from a lot of explanations I have read. It is easy, it is simple, it is normal. I am sorry I do not have a reference handy (because of the above) but those are good suggestions (otherwise I would not be writing them) that have helped me overcome similar "difficulties". Edit: Cannot help saying it. The 'a priori' and 'a posteriori' and all those terms are just fancy words (which mean what they signal) which scare a lot of people away from something, I repeat, natural.
RobAley 14y ago
If you understand procedural languages better, the following article discusses a basic naive bayesian classifier and implements it in PHP : http://phpir.com/bayesian-opinion-mining http://phpir.com/bayesian-opinion-mining

willvarfar 14y ago

I would imagine that in real life you track the reliability of a drugs test as % false positive and % false negative, rather than a single % reliable?

wfunction 14y ago

> "What if Bayes' rule was as simple as an if statement?" As the article clearly showed, this is wishful thinking. And there's one simple reason why: - Bayesian inference is generally computationally intractable. - "If" statements are quite tractable. Any language in which you could perform Bayesian inference as easily as you perform "if" statements in would result in horrifyingly slow code and become useless.

flipgimble 14y ago
You are thinking about languages that are targeting a single machine at a time. That's the way Microsoft thinks with their history in client-side software. The implication of the quote is that Google attempts to implement the seemingly intractable algorithms by running them on huge clusters, and returning the results to a large audience that makes the computation worth it. If your language targets a data center then having a language support Bayesian inference might be useful.
duaneb 14y ago
I think the original quotation simply used it as a rhetorical device to indicate difference in approach at a more abstract level than literally replacing conditionals with Bayes filters.
gizmo686 14y ago
As I pointed out elsewhere in this thread, Quantom computer languages literally do this. Also, if you want to perform Bayseian inference, then it is equally as difficult computationally whether or not it can be expressed as simple 'if' statements. However, in terms of code simplicity, expressing it as simple if statements is easier.
- wfunction 14y ago
  > Quantom computer languages literally do this Quantum computers also make the sun rise every morning. I can claim anything about what they do, because they don't exist.
  - 14y ago

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 ago
http://en.wikipedia.org/wiki/Monty_Hall http://en.wikipedia.org/wiki/Monty_Hall
- deleted 14y ago
  [deleted]
apw 14y ago
Do 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.

auggierose 14y ago

This is funny, because Microsoft Research actually works on that. http://link.springer.com/chapter/10.1007%2F978-3-642-19718-5_5 http://link.springer.com/chapter/10.1007%2F978-3-642-19718-5...

visarga 14y ago

> Google uses Bayesian filtering the way Microsoft uses the if statement. I am sure it depends on the employee, not the company. MS has done amazing things in machine learning. I love Vowpal Wabbit which is maintained by an ex Yahoo, currently MS employee. I am amazed at the complexity of the Kinect software to translate images into body configurations. Just today I have seen another amazing tecnology from MS: IllumiRoom. Check out the vid : http://www.youtube.com/watch?v=nGGMv9RnJIA http://www.youtube.com/watch?v=nGGMv9RnJIA Check out MAVIS too, a system for transcribing videos and making them searchable. It's a little dated, but very cool nonetheless. So, while I still think Google is superior, MS is making some amazing stuff too, from time to time.

zaphar 14y ago
The quote wasn't about their technology. It was about their decision making. Google is famous for data driven decision making.
abecedarius 14y ago
The quote was from most of a decade ago; probably truer then. (Though Clippy was Bayesian. I read somewhere a claim that its awfulness came from management messing with it.)

Eliezer 14y ago

I've totally seen a LISP dialect with probabilistic execution and Bayesian updating built in - it was one of the lecturers at SPARC 2012 - but damned if I can remember the name of the speaker or the LISP dialect. Roughly, using this dialect, you could build a program that would randomly branch at various points, then keep only the cases of the program that matched some property, and ask what the probabilities were for some other property over those cases. I think the keyword was rejection-query but the first page of Google doesn't turn up the desired result for that.

rawatson 14y ago
Church? I'm not very familiar with the language but I believe it sounds similar to what you're describing. http://projects.csail.mit.edu/church/wiki/Church http://projects.csail.mit.edu/church/wiki/Church
gmodena 14y ago
Possibly church? http://projects.csail.mit.edu/church/wiki/Church http://projects.csail.mit.edu/church/wiki/Church
JadeNB 14y ago
It's not a Lisp, but there aren't many probabilistic programming languages, so you may be interested in IBAL (http://www.gelberpfeffer.net/Papers/ibal-ch.pdf http://www.gelberpfeffer.net/Papers/ibal-ch.pdf).

gizmo686 14y ago

As much as I like Haskell, if your goal is to make Bayes' rule as simple as an if statement, I doubt you can do better than quantum computer emulators. Say the probability of being a User is 1%. You can initialize your variable, X, to a superpossition, with 99% chance of being clean, and a 1% chance of being a user. Now, the function, f(x) for the test is such that: f(user) = (99% positive) + (1% negative) f(clean) = (1% positive) + (99% negative) Take y=f(x). Now, look at the quantum state of your machine (this is why we are on an emulator). Each of the 4 potential states have a certain probability associated with them. The (theoretical) slowdown of using a quantom emulator is the fact that as the size of your memory increases, you have exponentially more states to deal with. But, because we would need to deal with the same number of states any way, this is not actually relevant. I should also mention that using a real quantom computer does not provide a (trivial) speed up to this prosess. This is because, while the quantom state contains all 4 possibilities with some probability, when we go to measure it, we will only see 1 of the 4 states. Not only will this not give us a probability, but we would need to re-run the computation to measure it again.