Slashdot Mirror
Bayesian Filtering For Dummies
Dynamoo writes "Bayesian filtering for spam is awfully clever stuff, touched on by Slashdot several times before. There's a very accessible article at BBC News explaining in fairly simple terms the drawbacks of current keyword-based filtering. It's slightly ironic that the BBC, through the commissioning of Monty Python, also gave 'spam' its name. Those Vikings have a lot to answer for."
The BBC article mentions Paul Graham, and I found his page (and some more information on Bayesian networks for spam filtering) here:
Paul Graham's spam page
He talks a little bit more about the technical aspects there.
the blood has stopped pumping, and he's left to decay
the me that you know is now made up of wires
Someone needs to learn the meaning of "ironic". (Hint: it doesn't mean "weird coincidence".)
Paul
Good question ... through Google Groups I found this page.
the blood has stopped pumping, and he's left to decay
the me that you know is now made up of wires
Why then, does the article show a pic from a Monty Python animation about the black spot who goes to seek his fortune...
You'd think they'd use the actual pic of the skit with the Vikings in the cafe...
/sig
A group of vikings in a monty python sketch drowned out normal conversation by shouting the word "spam" louder and louder. The word was then adopted for all the crap drowning out normal conversation on usenet.
You can try bogofilter, ifile, SpamBayes, or POPFile. The newer versions of SpamAssassin also implement some kind of Bayesian filtering.
Actually, the latent semantic analysis (LSA) that Apple uses is not a form of Bayesian reasoning; it uses a singular value decomposition (SVD) to perform generalized factor analysis. However, there is a probabilistic version of LSA out there.
Well, the type of Bayesian learning used in this spam filtering is called "Naive Bayesian" and the engine is trained using "supervised learning" technique. Naive Bayes has been proven very successful for text categorization. Spam filtering is even more successful because we essentially categorize e-mails to two labels: "spam" or "not spam".
Supervised learning basically works like this. Feed the engine with multiple examples (in this case, e-mails) with labels (in this case, "spam" or "not spam"). The training usually takes thousands of examples to get good enough accuracy. And take note that we need both "spam" and "not spam" examples to enable the learning engine to distinguish them.
How Naive Bayes works? Well, think of the full Bayesian Network. Bayes net is basically a causal-effect graph with annotated Conditional Probability Table (CPT) on each node denoting the probabilities of possible values. Full Bayes Net takes Directed Acyclic Graph (DAG), but Naive Bayes takes a form of tree instead due to some "naive" assumptions. (Okay, I handwaved a whole lot of details here) And in Learning Naive Bayes, we basically try to construct the tree out of the examples.
Let P(spam) be the percentage of training e-mails that is labelled as "spam" and P(not spam) be the percentage of "not spam" e-mails.
First, let the filter reads all e-mails and collect the words out of them. Weed out duplicates and stop words (common words like "I", "you", "the", etc). Let NumVocab be the number of words after weeding.
Second, process e-mail one by one. Do weeding phase like the above. Let "n" be the number of words on that particular e-mail after the weeding. Scan the word one by one. Let "w" be the current word scanned and "nw" be the number of times word "w" occur in that e-mail. Imagine you have a big two dimensional array to store the result (let's call the array "P"). If the e-mail is labeled "spam", then store (nw+1)/(n+NumVocab) to P[w][spam].
Repeat until all training e-mails are read.
And here comes the testing phase...
When you encounter an e-mail and want to classify whether it's spam or not, you'll need to look up the array P you created earlier. First, you do the weeding phase and scan the word one by one. The algo is like this:
Hope this helps.
--
Error 500: Internal sig error
Yes, I've done it and here's how:
/tmp for debugging and training bogofilter. Here's mine:
/usr/bin/bogofilter -p -u > /tmp/bogo.out 2> /tmp/bogo.err
/tmp/bogo.out to retrain bogofilter for the last message processed when necessary.
1. Get and install bogofilter.
2. Make a shell wrapper script that runs bogofilter in passthrough mode, redirect stdout and stderr to files in
#!/bin/bash
status=$?
exit $status
3. Make a new local mail folder in evolution to collect spam.
4. Make a filter in evolution that runs the wrapper script. Tools->Filters, choose Incoming, choose Add. Add a criterion that looks like this:
Pipe message to shell command, (path to your wrapper script), returns, 0. Add an action to move the message to your local spam filter.
5. Be sure evolution is set to apply filters to new mail in the inbox(es) you want bogofilter to act on. Tools->Settings, choose Mail Accounts, choose desired inbox(es), choose edit, choose the Receiving Options tab, check the Apply filters to new messages in INBOX on this server.
Please be sure to RTF bogofilter M. You will need to train (and retrain) bogofilter with spam and non-spam samples over time. The switches to do this have CHANGED from version to version. If you have set things up as above, you can use
Good luck, and happy spam filtering!
Loading...
The sketch is to be found on the album "The Bset of Sellers" - probably released in about 1958, and which also features the nursery rhyme
"Up on the chair behind the door,
hey diddle, diddle,
Hear comes Poppa
so up with the chopper
and split 'im down the middle
And "Balham, gateway to the South" a spoof of the travalogue films that often apepared in the cenema at the time.
Sent from my ASR33 using ASCII
Graham's method is called "naive Bayesian", and it's called "naive" for a reason. It works surprisingly well, but it barely scratches the surface of what people are doing with statistical models of text.
The lack of references on Graham's web site to prior work on text classification makes one wonder whether he just is unfamiliar with a huge body of literature going back decades or whether he just deliberately ignores them. Either way, Graham didn't invent any of the techniques and they are far from state-of-the-art. (Incidentally, you'll probably find Octave or Perl/PDL a more convenient language for implementing this stuff than Lisp.)
Anybody seriously interested in text filtering should at least do a little bit of background reading. "Readings in Information Retrieval" by Jones and Willett covers some of the basic papers.
Mozilla incorporates a twostep filter:
1. Is the sender in the address book? If yes, is not spam, otherwise:
2. Does the message have a probability of 90% that it is spam based on the Bayes filter? If so, flag as spam, otherwise not spam.
You'll soon be running out of bits to store the floating point results. Implement it by adding logarithms of probabilities instead of products of them, thus:
If you have a couple of hundred key-words, this will make a lot of difference concerning the accuracy of the predictions.