4 ms·
OK. Naive Bayes is ridiculously simple. [EDIT: Oops, it looks like I myself managed to get it backward on the first write! Whaps self in forehead. Rewritte
by Eliezer 17y ago
OK. Naive Bayes is ridiculously simple.
[EDIT: Oops, it looks like I myself managed to get it backward on the first write! Whaps self in forehead. Rewritten now.]
Let's say your user likes 40 items and hates 60 items. So the prior odds for likes/hates are:
4:6
Then it turns out that, of the 40 items the user liked, 4 of these or 10% are tagged "green", and of the 60 items the user hated, 12 of these or 20% are marked "green". So the likelihood ratio for "green" is:
0.1:0.2 (Given that an item is hated, the user is twice as likely to tag it "green" than if the item is liked.)
Then it turns out that of the 40 items the user liked, 8 or 1/5 are tagged "red", and of the 60 items the user hated, 3 or 1/20 are tagged "red. So the likelihood ratio for "red" is:
4:1 (Given that an item is liked, the user is four times as likely to tag it red.)
Consider a new item tagged "red" and "green". The posterior odds equals the prior odds times the likelihood ratios:
16:12
57% probability of liking it, claims Naive Bayes.
Sometimes it works, sometimes it doesn't.
If multiplying the prior odds by the likelihood ratio doesn't seem justified as a way of getting the answer, see http://yudkowsky.net/rational/bayes http://yudkowsky.net/rational/bayes - there ought to be a shorter version of this, but I haven't gotten around to writing it.
- DanielBMarkham 17y agoYou sir, are the man! That's exactly what I was looking for. For some reason it just wasn't coming. Thanks! I'll worry about the hard stuff if/when Naive Bayes has problems.
- Eliezer 17y agoI must have been seriously tired when I gave you the original answer, but I frantically scrambled back and rewrote it and it should be correct now. It's really scary the way my ability to do elementary math deteriorates after going on a two-hour walk. Please reply so I know you got this and that you didn't run off to use the wrong original answer.
- DanielBMarkham 17y agoGetting to one of my original questions, just to tie up the thread, yes, I will need to track totals of like-tag1, dislike-tag1, like-tag2, dislike-tag3, like-tag4, dislike-tag4 But I will not need to keep track of like-tag1-tag2, like-tag1-tag3, ... like-tag1-tagn. dislike-tag1-tag2, etc. Because I can pre-compute a couple of totals for each tag and then compute the likelihood off the totals. But if I had to track the cartesian product it would become almost impossible to precompute anything. (I want to prevent having to walk a tree or sift a list each time I make a prediction, as it needs to all happen very quickly)
- Eliezer 17y agoRight. You need the total number L and D of items each user has liked or disliked. You need the total number of liked items LT, and the total number of disliked items DT, which have the tag T. Then you just iterate through the tags and multiply the prior odds by (LT/L):(DT/D) for each tag. (To avoid zeroes, you could add 1 to all the numbers above.) This will usually give you a unrealistically extreme probability estimate at the end, but it's sometimes good at classifying positive vs. negative cases. Runtime should be linear in the number of tags. If that doesn't work - don't be too surprised if it fails! - then it's time to either find something off-the-shelf, crack a textbook or hire an expert.
- gchpaco 17y agoI cannot upvote you enough for that.
- gjm11 17y agoThose who don't already know may want to note that this algorithm is exactly the one used by simple Bayesian spam filters, as proposed e.g. by a certain Paul Graham: http://www.paulgraham.com/spam.html http://www.paulgraham.com/spam.html (more on this at http://www.paulgraham.com/antispam.html http://www.paulgraham.com/antispam.html).