Spam Classifier Using Naive Bayes

Spam and Normal Emails

In the previous lesson, we learned about the Naive Bayes classifier. In this lesson, we use it to build a spam classifier.

Let's first look at a few emails:

• "Congratulations, you have won a free gift card." The email says you have been selected for a $500 gift card, and that you should hurry because the offer expires in 24 hours. This is definitely spam.
• "Urgent: your account will be suspended." The email says your bank account needs immediate verification, or it may be terminated. This also looks like spam.
• "Meeting agenda for 15th October." The email shares the agenda for tomorrow's meeting with the team. This is a normal email.
• "Your order has been shipped." The email gives an order number and a link to track the package. This is also a normal email.

Just by looking at these emails, we can tell which ones are spam. But how can a machine learning model do this?

The presence or absence of certain words can influence whether an email is normal or spam. For the emails above, words like free, won, gift, and urgent make spam more likely, while words like meeting, order, shipped, and agenda make a normal email more likely.

Different datasets will have different words, since a corporate inbox and an e-commerce inbox don't look alike. But the idea holds for any dataset: different words influence whether an email is normal or spam.

Bag of Words

Naive Bayes treats an email or document as a bag of words, which is just a collection of words. It also assumes that the presence of each word in the document is independent of the others. This is why it is called naive.

This assumption isn't entirely true, because words in a document can be related. Consider this sentence:

Click the link to claim your prize.

Here, click and link are related, because the link is what you click. Claim and prize are related too, and so are your and prize.

Naive Bayes doesn't consider any of these relationships. It ignores syntax, dependency structure, and word order. Yet it still performs surprisingly well for spam classification.

Representing Emails as Vectors

Suppose we have a labeled dataset:

Each $x_i$ is an email, and $y_i$ is its output class. We use $y_i = 1$ for spam and $y_i = -1$ for not spam.

Suppose our vocabulary has $d$ words. We can then represent each email as a $d$-dimensional vector:

Here, $n_{ik}$ is the number of times the $k$-th word of the vocabulary occurs in the $i$-th email. For example, $n_{21}$ is how many times the first word occurs in the second email.

Classifying a New Email

For a new email $x$, we need the probability of the output class given the input. Using Bayes' theorem from the previous lesson:

We can calculate $P(y)$ and $P(x \mid y)$ from the training data. For example, $P(\text{spam})$ is the share of training emails that are spam.

The denominator $P(x)$ doesn't change between the classes, so:

We have two classes, spam and not spam. We calculate this value for both, and the higher one is our output class.

A Worked Example

Let's use a small dataset of five emails.

Spam emails:

• claim cash now
• win cash reward
• money reward now

Not spam emails:

• account reward money updated
• cash received now

Three of the five emails are spam, so:

To keep things simple, our vocabulary has only four words, cash, reward, now, and money. We ignore all other words. Each email then becomes a four-dimensional vector of word counts.

For example, "claim cash now" contains cash once, reward zero times, now once, and money zero times.

So there are 7 vocabulary words in total in the spam class, and 4 in the not spam class.

Classifying the Test Email

Now let's classify the test email "cash reward now".

Naive Bayes treats the words as independent, so we can split $P(x \mid \text{spam})$ into one probability per word:

The probability of a word given a class is its count in that class divided by the total words in that class. Cash occurs 2 times out of 7 in spam, and the same goes for reward and now:

For the not spam class, each of the three words occurs 1 time out of 4:

The spam value is higher, so we classify "cash reward now" as spam.

Laplace Smoothing

Without Laplace smoothing, a single word can destroy the entire probability. Let's see why.

The Zero Probability Problem

We'll make one change to the dataset. We remove money from the first not spam email, so it becomes "account reward updated".

The spam counts stay the same. The not spam counts are now:

Now let's classify a new test email, "money reward now".

For the spam class, everything works as before:

For the not spam class, money never occurs, so $P(\text{money} \mid \text{not spam}) = 0$:

The result is zero because of just one word. Because the probabilities are multiplied together, that single zero wipes out all the evidence from the other words, and the class can never win.

The Fix

Laplace smoothing prevents a probability from becoming zero when a word doesn't appear in the training data for a class.

It changes how we calculate the probability of a word. Instead of the word count divided by the total words in the class, we use:

Adding 1 to the count makes sure that no probability is ever zero.

Applying Laplace Smoothing

Our vocabulary size is 4. For the spam class, the total is 7, so the denominator is $7 + 4 = 11$:

For the not spam class, the total is 3, so the denominator is $3 + 4 = 7$:

The not spam value is no longer zero, and both classes now have a meaningful score. The spam value is higher, so "money reward now" is classified as spam.

Other Applications

Naive Bayes can be used for many document classification tasks beyond spam detection, including:

• Sentiment analysis
• Text classification
• Language detection
• News categorization
• Customer support ticket classification

Summary

The key ideas are:

• Naive Bayes treats an email as a bag of words and assumes the words are independent.
• It ignores syntax and word order, yet it performs surprisingly well.
• Each email is represented as a vector of word counts.
• To classify an email, we compare $P(y) \prod P(\text{word} \mid y)$ across the classes.
• Without Laplace smoothing, one word with a count of zero makes the whole class score zero.
• Laplace smoothing adds 1 to each count and the vocabulary size to the denominator.