TZBayesClassifier

A few months ago, Paul Graham lit a fire under the anti-spam community with his, A Plan for Spam web page.

Paul uses so-called "naive Bayes" to filter spam astoundingly well. Others have created such filters to cope with last year's exponential growth in spam traffic. Field experience is supporting strong claims of effectiveness for these types of filters.

For the past several months, I have been using Spam Assassin to filter email for a system that delivers email summaries to phones. Spam Assassin works reasonably well for a wide variety of email. I have used it on my own email and have a pretty good feel for its characteristics. But it suffers from some deficiencies for my system use:

1. It is a large set of Perl modules.

2. It is slow and complex.

1. The system may need to run on a machine without Perl.

2. Whatever spam filter runs successfully in a prototype system must be easily implemented in C.

"Naive Bayes" filters can be really fast. And they can be very, very simple. Too, they can be used to personalize email filtering. This latter capability is also important.

To gather first-hand knowledge about these Bayes filters, I wrote some Perl modules, the main program for which is named TZBayesClassifier.pm.

What follows is a summary of, and some discussion about, what I have found.

Program Description

Test Data Description

Results

Unknowns

Source Code

Program Description

TZBayesClassifier.pm learns and classifies emails from Netscape/Unix mailbox files.

    Unix:

      From whoFrom@whereFrom.com  Mon Feb  3 01:02:28 2003

    Netscape:

      From - Sat Sep 28 09:55:41 2002

  

TZBayesClassifier.pm uses EmailToke.pm to tokenize each email.

TZBayesClassifier.pm then puts the tokens through some more processing:

If the email is being learned, TZBayesClassifier.pm bumps the count for the email's category for each instance of tokens contained in the email.

Or, if the email is to be classified, TZBayesClassifier.pm does the "Bayes" logic with the email's tokens.

Naturally, there are quite a number of settings and variants that can be made to this general logic. I tried quite a few. Some are mentioned below. The rest have notes about them in the source code.

Test Data Description

I used the following test data:

• Several years of personal email. The emails were selected from mailboxes that were very, very unlikely to contain spam. (No "Trash", for instance.)
  We're talking 27,000+ emails.

  The emails were actually sent to 2 or 3 of my "guises": work #1, work #2, personal. That sort of thing.

  A lot of these emails are software order notifications and mail-list content. Such email is quite similar from email to email.

• Validated spam from the last few months.
  We're talking about a 120+ meg of 13,000+ emails.

  This spam was mostly sent to my tranzoa.com accounts. But some were to family members and some were to a couple of "work" accounts of much different ilk. (One, for instance, is a buttoned down, corporate kind of account. Another is a chat-room, Instant Message kind of account.)

  By "validated", I mean that I had specifically designated each and every one of these emails as spam. Not surprisingly, these experiments with TZBayesClassifier have proven the imperfection of my own eyes and mind.

  These "spams" include quite a lot of virus-containing emails. If you interact with a wide variety of people from all over the world (as I do in one of my work guises), you will often receive several virus emails (e.g. Klez) in a day.

  All of my spam has had Spam Assassin headers and decoration removed.

• 600+ emails downloaded from Spam Archive. These emails are a motley crew. They often contain headers and decoration from spam filters such as Spam Assassin. And the actual spam is often encapsulated in a forwarded email.

Results

First runs...

Then, with various settings, I told TZBayesClassifier to learn one half of the spam and one half of the "ham". After it learned from these two halves, it classified the other halves.

It did not take long to find settings that yielded extremely good false positive (innocent victim) numbers. That is, I found settings that, for instance, considered zero to two of the 13,000+ "hams" to be spam. Given that quite a few of the "hams" are actually on the edge of spamminess, that's almost too good.

It took longer to find settings that brought spam filtering above 95%. Eventually, spam filtering got slightly above 95% at a .9 probability cutoff, and around 98% at a .5 probability cutoff. Both cutoffs did fine on the false positive front (e.g. zero emails at .9, and two emails and .5).

Now, these results are not a big surprise. 20,000 emails is quite a learning experience for anyone, even a simple computer program. So it's not surprising that the learning was effective.

I did learn a few things, myself, though:

• The single most distinct token tells the whole story.
  Paul Graham uses the top 15 most distinct tokens. I tried several values from 1 to 60. 1 did quite well. 20+ not so well. I settled on 10.

  Generally speaking, lower values tend to yield results that are the same no matter what the probability-of-spam cutoff. That is, either emails are considered strongly spam or not. Not many emails are considered ambiguous.

  Higher values for this number of distinct tokens resulted in more emails being considered ambiguous.

  This makes sense, intuitively. So it made for a nice bit of validation of the program logic.

• Which tokens actually were effective followed a variant of the usual curve that you will see in distributions of words, etc. etc. in text.
  This classic curve is easily (if inaccurately) described: the top word/token is as popular as all the rest of the words/tokens. The next one is as popular as the remaining words/tokens. And so on.

  To be more specific, a few tokens were used to classify emails a lot. Most were not used at all.

  For example, for some experiments, there were 2 to 4 hundred thousand unique tokens. But only 15,000 of them were ever used to classify emails. And most of those were rarely used. The most distinct token for each email is printed out by the program. There isn't a lot of variety in this top token. For instance, if you see "WIDTH=0" anywhere in an email, you can toss the email. It's spam. And TZBayesClassifier does so. Again and again. Because "WIDTH=0" is quite common in my spam, anyway. As they say in sales, it's a "top producer."

• The characters that are used to split the email into tokens do not matter much.
  I tried an alternate set of characters to include in tokens. The alternate set included a lot more punctuation/symbol characters. It had no real effect.

• After a hundred-ish emails, emails that provide more than 40% new tokens are pretty new.
  When the memory knows 500 spams but no hams, 40% to 60% of a typical ham email's unique tokens were new to the memory. By the time the memory knew that many spams, though, the typical spam contributed 15% to 30% of its unique tokens as new-to-memory.

• To avoid divide-by-zeros and such, I substituted a probability of 0.0001 for zero.
  I had first tried 0.01. But, 0.0001 worked better.

  I tried a couple of other tricks to mitigate the importance of, say, a token with a spam count of 10 and a ham count of 0 being considered more distinct than, say, a token with a spam count of 700, and a ham count of 1.

  The results for each of these tricks were disappointing.

Tangent...

But, some of the original spark for writing TZBayesClassifier was to find out if a "naive Bayes" filter could be used to pick a good token set for use by an email "signature" algorithm. So, this CRC trail remains to be followed.

Foreign emails...

So, I downloaded a sample of spam from Spam Archive.

And, I ran it through the email that had been taught my own spam and "ham".

Disaster!

In early runs, anywhere from 20% to 40% of the Spam Archive spam was classified as spam. The rest of those emails fooled the filter.

It did not take long to find out a reason for many of the false negatives: the Spam Archive spam contains many emails with spam filter headers and decoration. Since my own spam has all of that removed, and since some of my own "hams" contain such headers and decoration, ... Well, the results were what one would expect.

Did I strip such headers and decoration from the Spam Archive spam? Did I strip such emails from my own "ham"?

No and no.

Maybe someday. But, my computers were getting tired by then, and refused to do it.

Just kidding. It was I who didn't want to do it.

Heck, computers are here to do our work, not the other way around.

And, anyway, I didn't want to "get cute" with the data.

Smaller data sets...

I extracted two random selections of 500 emails from my spam and ham. I split the Spam Archive spam into two randomly chosen parts of ~500 emails a part.

I use these data sets in this way:

• Learn 500 hams and ~500 spams (the spams can be either mine or from Spam Archive.

• Classify:
  • Two sets of spam (500 of my own and ~500 from Spam Archive).
  • One 500 email set of ham.

Well, what happened? !!!!

N-grams...

• ..a
• .ab
• abc
• bcd
• cde
• dea
• eab
• ab.
• b..

This logic dumbly trigrams the email text, HTML, replicated headers, and 2-attachment-lines.

Of course, the unique token count explodes with n-gramming.

Turns out, n-gramming does pretty well all alone. I found that using the top 40 n-gram distinct tokens was best. Things degrade very slowly when more tokens than 40 are considered. And below 20, things get pretty bad.

For some of the "foreign" spam tests (either learning from my own spam or from the Spam Archive spam, and then classifying the other), normal tokens in combination with 3-grams worked best, 3-grams alone were a close 2nd best, and using just normal tokens was notably worse. Gut feeling: 3-grams helped with the spam-header problem. 3-grams that came from spam headers played a significant role in classification, for instance, but their effect seemed to be diluted.

Anyway, since n-gramming and Perl don't go together very well, these 3-gram tests were just a quick way to get a sense of how a poor-man's CRM114 might work. It's worth looking in to more, I think.

Learn as you go...

So what happens if the program is required to be a good filter right from the start?

I used the following logic (in TestIncTZBLearn.pl):

1. Train the logic on 1 spam and 1 ham.

2. The feed the logic alternating spams and hams.

3. For each email, track whether the logic correctly classifies the email's category, spam or ham.

4. Tell the logic whether the email is spam or ham.

5. If the logic misclassified the email before training, repeat from step 3 - that is, classifiy the email again (and retrain). Keep doing this until the email is correctly classified.

The result: An email or two are misclassified in the first 10 emails. After a 100 emails, as many as 5 emails have been misclassified - more or less evenly divided between spams or hams. After 200 emails there generally is another email that has been misclassified. And so on.

In other words, the logic is so good that the measurements are at the noise level.

Does it make a difference how many distinct tokens are used?

The essential thing is that the logic works well enough that "improvements" hinge on individual emails and cases - not on any global "smarts."

Current numbers...

Now comes the good part: those 5 false positives among the hams? 4 of them are ambiguous spams. I could have easily lived without any of those four. The one definite false positive is a very, very strange email from someone in France. Yes, yes. I know what you are saying: "That explains it!" But it was a real, solid, important email. So perfection is not currently the state of the art.

Those 177 Spam Archive "hams"? Well, a quick sort shows that the top distinct token for 87 of them is "x-spam-status:". 54 of the 90 "hams" had "x-spam-status:" as their top token. You get the picture. By a quick look at a few of the emails, it appears that almost all of the mistakes with the Spam Archive spams are because of spam headers and decoration!

New tokens...

Turns out that after the first 50 emails or so (of a random spam or ham selection), around 20% or 25% of the unique tokens in an email are new. After a few hundred emails, that percentage of new tokens can drop below 20% relatively often. After 2000 emails, the new token percentage is in the teens, and the percentage of emails that have fewer than 5% new tokens has gone up to the 5% to 10% range. After 4000 emails, that percentage of such emails that don't have 5% new tokens is up in the 12% to 18% range. That is, as far as new-token tracking is concerned, 12% to 18% of the emails do not add value. Many of these emails are probably "dupes," in fact. After 6000 emails, those been-there-done-that emails comprise somewhere from 25% to 35% of all emails. And the average percentage of new tokens for emails has dropped to 6% to 12%.

Interestingly, I found that my own spams became more "familiar" in this new-token sense than the hams. At the 8000 email mark, hams were still providing new tokens at the kinds of rates that spams were doing in the 4000's.

That surprised me because the hams contained so many emails that came from automated notification systems. Apparently, these emails just had enough unique information (transaction ID's, names, email addresses, etc.) that they continued to provide new, though useless, tokens.

Unknowns

Can a Bayes filter be used to fill a good email hash function token list?

Everybody's favorite question: What about combining tokens? Or using other combinations of tokens than simple sequential appearance in the email?

Does the little trick work that TZBayesClassifier uses to recognize viruses?

Which tokens should be thrown away if tokens must be aged so that useless tokens can be flushed from memory to save space.

Source Code

Perl source code for TZBayesClassifier:

http://www.tranzoa.com/Download/tzbayes.zip