CSE 312 Spam Filter Intro

The Naive Bayes Classifier

Agenda

• What is Machine Learning?
• Featurizing Emails
• Naive Bayes

Machine Learning in the Real World

ML Pipeline

Data

ML Model

​

Intelligence

From Wikipedia: “Machine learning is the study of computer algorithms that improve automatically through experience.”

You are a machine!

Given examples with correct “labels”, make predictions!

You are a machine!

Given examples with correct “labels”, make predictions!

Regression: Idea

$ 340,135 $801,353 ??????

Classification: Idea

“Green” class “Red” class

Classification: Idea

Is this new shape supposed to be “green” or “red”?

“Green” class “Red” class

Spam Filter

• In real life, you may have seen a lot of spam emails like this.

• Building a good spam filter helps protect users from potential scams, unnecessary advertising, or malware links.

Evaluating Performance

Training Set

Test Set

We “train” our spam filter on the training set, and evaluate performance using a test set (data that is unseen by the spam filter initially). This gives an unbiased estimate of performance.

Spam Filter Task

Predict whether this

email is spam or ham:

You buy Crypto!

Training Set

Emails as word collections

For simplicity, we will

• Ignore Duplicate Words
• Ignore Punctuation
• Ignore Casing

​

​

Emails as word collections

For simplicity, we will

• Ignore Duplicate Words
• Ignore Punctuation
• Ignore Casing

​

​

Emails as word collections

For simplicity, we will

• Ignore Duplicate Words
• Ignore Punctuation
• Ignore Casing

​

​

Problem with this model

Consider for example the following two emails:

“!!!Lunch free for You!!!!!”

​

“You free for lunch?”

​

One shortfalling of our model is that it will make the same prediction for these since they have the same set of words!

Spam

Ham

Our approach

Our approach

Naive Bayes Classifier - The bayes part

​

Naive Bayes Classifier - What we Calculate

​

Naive Bayes Classifier - What we Calculate

​

Naive Bayes Classifier - What we Calculate

​

Naive Bayes Classifier - The naive part

​

Naive Bayes Classifier - The naive part

​

It is somewhat unlikely that we have the email “You buy Crypto!” in our training data. (In this case we don’t!)

​

​

​

​

​

Naive Bayes Classifier - The naive part

​

Conditional Independence

• In normal independence: we say two events A and B are independent of each other

​

​

• In conditional independence, we say two events A and B are independent of each other given another event C

​

​

• What does this mean?
• If we know whether an event C occurs or not, our knowledge about A tells us nothing about B (and vice versa)

​

Naive Bayes Classifier - The naive part

​

Naive Bayes Classifier - The naive part

​

Why is this Naive?

Words are not independent of each other!

​

​

Example

Example

Example

Example

Example

= 1

Example

= 1 (Marked as spam since no ham email contained “buy”)

What happens if we got a 0?

P(ham | “You buy Crypto!”) = 0 since P(“buy”| ham) = 0, since no ham email in our training data contained the word ‘buy’.

But does that mean we will never encounter a ham email with word ‘buy’?

​

Laplace smoothing

Pretend in spam emails (training set):

• We saw one extra spam email with word
• We saw one extra spam email without word

​

Laplace smoothing

Pretend in spam emails (training set):

• We saw one extra spam email with word
• We saw one extra spam email without word

​

​

​

​

Laplace smoothing

Pretend in spam emails (training set):

• We saw one extra spam email with word
• We saw one extra spam email without word

​

​

​

Same for ham emails:

​

Laplace smoothing

Pretend in spam emails (training set):

• We saw one extra spam email with word
• We saw one extra spam email without word

​

​

​

Same for ham emails:

​

Example

Example

Example

Example

Example

Underflow Prevention

• Multiplication of many probabilities, each of which will be between 0 and 1, can result in floating-point underflow. The product will be too small and will result in arithmetic underflow.

Underflow Prevention

• Multiplication of many probabilities, each of which will be between 0 and 1, can result in floating-point underflow. The product will be too small and will result in arithmetic underflow.
• Reminder: Log property:

Underflow Prevention

• Multiplication of many probabilities, each of which will be between 0 and 1, can result in floating-point underflow. The product will be too small and will result in arithmetic underflow.
• Reminder: Log property:

​

• Summing logs of probabilities is better than multiplying probabilities

​

Applying underflow prevention

We will output spam iff:

Applying underflow prevention

We will output spam iff:

Denominators are equal and cancel when comparing

Applying underflow prevention

We will output spam iff:

Applying underflow prevention

We will output spam iff:

Taking the log of two sides:

Summary: Naive Bayes Algorithm steps

1.2. Iterate over the training set, for each unique word x, count:

• How many spam emails in the training set contain x
• How many ham emails in the training set contain x

​

​

​

​

1. TRAINING

1.1. Compute the proportion of emails in the training set that is spam or ham:

Summary: Naive Bayes Algorithm steps

Predict email D as spam

Otherwise, predict email D as ham

2. TESTING

Iterate over the test set, for each unlabelled email D:

• Create a set S of n unique words appearing in D:
• For each word in set S, calculate:

​

​

​

• Note: If word doesn’t appear in the training set, we still calculate the above probabilities, with:

• if

Questions?

Comments?

Concerns?