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."
I suggest Slashdot immediatly implement this "Bayesian Filter for Dummies" to remove most of the trolls, etc.
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
I have used a bayesian filter for some time now and while it is the BEST filter type I have ever used nothing is 100% reliable. While this is the best technology for the average user it is most cirtainly not perfect. Instead I use a combination of moderate bayesian filtering and good old fasion "block sender" filtering.
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
Interesting yes, ironic, no.
What's your name, Alanis Morissette ?
This whole spam thing reminds me of a story I read while in 7th grade. In it, the postage for sending junk mail was decreased to practically nothing. Then, junk mail buried America. Hundreds of years later, archeologists came back and investigated the remains. Their conclusions about our society are kind of humorous. However, the idea of junk mail burying us when the postage goes way down has kind of been proved with spam. Maybe a small tax for spam wouldn't be a bad idea.
Thank you for your support.
Is this truly the only Earth I can live on?
Viagra often spelled V-l-a-g-r-a online
I-f I t-r-o-l-l l-i-k-e t-h-i-s, w-i-l-l i-t p-a-s-s S-l-a-s-h-d-o-t.'s t-r-o-l-l f-i-l-t-e-r ?
"A door is what a dog is perpetually on the wrong side of" - Ogden Nash
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.
"The sheer number of spam mail sent means that even tiny response rates, reportedly 0.0001%, means junk mailers turn a profit. "
And this is why I say that educating users is just about as important as implementing spam filtering technology. If people know that they are perpetuating a serious problem by replying to spam, then that's bad news for spammers.
About another fact mentioned in the article: It said Paul Graham's filter extracts "the top 15 features that define them as spam." 15? I thought that most Bayesian filters use many more spam-defining features. Because I'd say that there are quite a few more. Just think of the many features that spam tends to have. But he says his filter works well. Interesting.
In my home mailbox, I don't receive spam. And I only got two 419 nigerian invesment frauds on my professional address in a whole year, despite the fact that my corporate email address is widly publicized and easy to find on google. And amazingly, I never receive spam in my "special bogus registration" hotmail account (useful for programs like RealPlayer, or nytimes.com).
:
So existing mail filters work for me, more or less. The few unwanted mails that pass through are easily taken care of by my trusted delete button. This leads me to ask
- Do other people really receive that much spam, or am I an isolated case ?
- Do people who receive spam purchase things online, or register software and other services with their real names and email ?
"A door is what a dog is perpetually on the wrong side of" - Ogden Nash
...supposedly uses some form of Baysian reasoning. I've been using it for a year now. I trained it for a couple of weeks, turned it on "automatic filtering" mode, and now I can count the number of times its misclassified a message on my two hands. I used to get more spam than legit mail, now I can't help but wonder why spam is a problem for people. Until I remember that most people don't use a mac. Every once in a while, I flip it back into training mode so that I can see the lovely see of brown-colored spam messages that flood my inbox. I flip it back to automatic mode, Mail automatically moves them to my junk folder, and I can forget about them.
I find in our case it stops 98-99% of spam dead in its tracks. There have been a few false positives, and you do need check from time to time just in case an genuine emails are misclassified, but it's surprising just how quickly the filter sorts the wheat from the chaff.
Don't expect miracles but they can save you a lot of time... what I find cool is that it learns so quickly, almost like a complicated neural net should, but it's such a simple idea. I wonder if there are any other uses for this kind of thing?
Sorry, but my karma just ran over your dogma.
I simply got to the point that I could count the number of real emails on my hands. So I reversed my previous filter. Instead of filtering spam to my spam folder, I made it default *ALL* mail to the spam folder except from certain known addresses (such as work, friends and my own domain). So far, it has only made one wrong decision, and that was because I hadn't written the email address of a friend correctly.
:)
This is waaaaay better than any other filtermethod I've tried and requires no learning period at all
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
This allows your single spam/non-spam feedback to the system to do double duty, so that once the program knows that you consider an email source to be "trusted", it will allow even spammy-looking stuff (read: mailing list digests, plane schedules, bank statements, etc) through to your non-spam folder.
Of course, if spammers start constructing google-style databases of who your friends are and impersonating their accounts, then this won't work anymore... but if they start that, all hell is going to break loose anyway.
I don't care if it's 90,000 hectares. That lake was not my doing.
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
It's natural to think that is the case, but in reality it isn't. Accidentally putting one email in the wrong corpus ("good" or "spam") will not be enough to kill you. If you consistently fail to put them in the right corpus then over time, yes, things would snowball. But that'll only happen over time. A mistake now and then isn't enough to mess things up.
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.
Great. Wanna filter my email for me? ;)
The sheer number of spam mail sent means that even tiny response rates, reportedly 0.0001%, means junk mailers turn a profit.
Are we missing a critical factor of the end user who actually responds to SPAM?
If spammers survive on 0.0001% response rate, how many people are actually clicking/buying? Are these people who provide the customers for spammers going to stop or use any sort of filters?
I don't use email. Yes, I have a few addresses but I havent checked them in months. Email is kinda dead way of communication anyway, beaten by things such as mobile phones and instant messaging.
On my mailbox outside my apartment I have a "No Junk Mail please" sticker... This actually works. I tried to put the same sticker on my pc, but the junk mail just keeps on comming... I don't understand....
Ask me no questions, and I'll tell you no lies...
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.