Nagoya University, Fall 2022

Lecture 6

Naive Bayes I

https://www.henrikbachmann.com/mml2022.html

.

Email spam filter
Let's assume we want to create an email spam filter byusing supervised learning.
Labels: No Spam & Spam

Features: EmailEmails
Training set

Email text

No spam / Spam

1 Do math today

02 Buy1

3 Buy book0

4 Today do math drugs

1

5 Buy drugs book today

1

According to this training set: Is the email “Buy book today” spam?

.

Email spam filter: From emails to vectors
Training set

Email text

No spam / Spam1Do math today

02

Buy

1

3

Buy book04

Today do math drugs

15

Buy drugs book today1Create a dictionary and assign to an email a vector
1book2buy

3

do4drugs

5math

6today“Buy book today”

We will ignore the order and the number of appearances of words

.

Email spam filter
Recall: P(A|B) refers to the conditional probability that event
A occurs, given that event B has occurred.
For a given email (feature) x we want to calculate theprobability that this email is spam, i.e.

.

Email spam filter
Recall: P(A|B) refers to the conditional probability that event A occurs,
given that event B has occurred.
For a given email (feature) x we want to calculate the probability that thisemail is spam, i.e.

bill
W

We will do this by using Bayes rule

nelai
xp
eedinedorm

together with the Naive Bayes assumption that!
erlat
ailet

and the law of total probability

.

Email spam filter
Training set

Email text

No spam / Spam

1 Do math today02 Buy

1

3 Buy book0

4 Today do math drugs

1

5 Buy drugs book today

1

The probabilities according to our training set:.

Email spam filter
Training set

Email text

No spam / Spam

1 Do math today

02 Buy1

3 Buy book0

4 Today do math drugs

1

5 Buy drugs book today

1

The probabilities according to our training set:.

Email spam filter“Buy book today”

.

Email spam filter
x = “Buy book today”

.

Generative vs Discriminative learning algorithm

Logistic regression

x: feature (e.g. hours of studying)
y: label (e.g. passing or failing exam)

Want to find a hypothesis which describes P(y|x)

Learning P(y|x) is an example of a discriminative learning algorithm.

Generative learning algorithm: Learn P(x|y) and P(y).

.

Generative vs Discriminative learning algorithm
Notation: P(A|B) refers to the conditional probability that event A occurs, given thatevent B has occurred.

Generative learning algorithm: Learn P(x | y) and P(y).
Question: But we want P(y | x)… don’t we??
Yes, but we can use:

Bayes rule:.

Bayes rule.

Naive Bayes
An example for a generative learning algorithm: Naive Bayes
Example: Spam filter••Feature: EmailLabel: Spam & No Spam.

Naive Bayes assumption
Naive Bayes assumption:The features are “conditionally independent” given the label.

conditionally independent
A and B are conditionally independent given C if and only
if, given knowledge that C occurs, knowledge of whether
A occurs provides no information on the likelihood of Boccurring, and knowledge of whether B occurs provides
no information on the likelihood of A occurring.

.

Conditionally independent: Example
A: Ability to do math of a person
B: Foot size of a person
A and B are not independent, since if I tell you someone's
foot size, it hints at their age, which in turn hints at theirability to do math.

C: Age of a person
A and B are conditionally independent given C, since if tell you
someone's age (C), then the ability of doing math (A) will notchange whether you know the foot size (B) or not, i.e.

P(A | C) = P(A | B,C).

Naive Bayes assumption
Naive Bayes assumption:
The features are “conditionally independent” given the label.

Chain rule of probabilities:.

Naive Bayes assumption
Naive Bayes assumption:

Chain rule of probabilities:.

Naive Bayes classifier

Our model is parametrized (the stuff we need to remember after training) by.

Naive Bayes classifier: Training
Indicator function.

Naive Bayes classifier: Judging a new email
Training: Determine the values.

Naive Bayes classifier: Problem
Here are some problems:
What is the probability of “buy anti drug book today” to be spam?

.

Naive Bayes classifier: Laplace smoothing
We should never assume an event to have probability 0 or 1.
For this we will use Laplace smoothing and change our parameters as follows:

Possible interpretation: Assume that every word appeared &did not appear in a spam and non-spam email.