Home / MLT / Week 8

Week 8 · Generative models: Naive Bayes

Official syllabus line: Supervised Learning - Classification - Generative Models - Naive Bayes

About 70 minQuiz 2 material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 10 (conditional probability, Bayes' rule), MLT week 4 (Beta prior and the "add one" idea).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine you're teaching a friend to spot spam emails. You describe what spam looks like, like words such as 'free' or 'money'. You also describe normal emails with words like 'meeting' or 'lunch'. When a new email arrives, you simply ask: "Which kind of email would more likely have written this message?"
This way of thinking is called a 'generative model'. We learn a story for how spam emails are *made*, and a story for how normal emails are *made*. Then, we find which story best explains a new email. It's 'naive' because it assumes words appear independently, even if they often come together, like 'free' and 'money'. This simplifies the model.
Let's try an example. Imagine we have some known spam and normal emails. We count how often words appear in each. Now, a new email "free money" arrives. We use these counts to find its score for being spam, and its score for being normal. The spam score is much higher, so we predict this email is spam.
For your exam, remember to classify emails using our method, and count model parameters. Always recall that Naive Bayes assumes features are independent *given the class*. And remember, it's a *generative* model. Keep practising, and you'll easily spot spam, and ace your quiz! You got this!

The one-minute story

Think of it like this

How would you teach someone to spot spam? One way: describe what spam looks like. "Spam emails often say free, win and money. Normal emails talk about meeting, today, lunch." Then, when a new email arrives, ask: "Which kind of email would more likely have written this?"

That is a generative model: for each class you learn a little story of how its members are produced, and you classify by asking which story explains the new example best.

The "naive" part: to keep the stories simple, we pretend the words in an email are chosen independently once we know whether it is spam. That is not really true (free and money often come together), but the shortcut makes the model cheap, quick and, surprisingly, very good at text.

By the end of this week you can:

explain generative vs discriminative models;
apply Bayes' rule and the naive independence assumption to classify;
estimate Naive Bayes parameters from counts with Laplace smoothing;
handle numeric features with Gaussian Naive Bayes;
count the parameters of a Naive Bayes model.

Words you need

Generative model - models how the data $\mathbf x$ is produced for each class: $p(\mathbf x\mid y)$ and $p(y)$ .
Discriminative model - models the answer directly: $p(y\mid\mathbf x)$ (or just a boundary). Logistic regression is next week.
Prior $p(y)$ - how common each class is.
Class-conditional likelihood $p(\mathbf x\mid y)$ - how likely this input is, if the class were $y$ .
Naive Bayes assumption - features are independent given the class.
Laplace smoothing - adding a "1" to every count so nothing gets probability exactly zero.

Idea 1: Generative or discriminative?

Bayes' rule gives the quantity we want, the probability of each class given the data:

P(y\mid\mathbf x)=\frac{P(\mathbf x\mid y)\,P(y)}{P(\mathbf x)}\;\propto\;P(\mathbf x\mid y)\,P(y)

A generative model learns the right-hand side pieces, $P(y)$ and $P(\mathbf x\mid y)$ , and then uses Bayes' rule. It can even generate fake data. (Naive Bayes, Gaussian mixtures.)
A discriminative model learns $P(y\mid\mathbf x)$ directly and never bothers modelling $\mathbf x$ . (Logistic regression, SVM, perceptron.)

The prediction is the class with the largest posterior. The denominator $P(\mathbf x)$ is the same for every class, so we can ignore it when comparing.

Idea 2: The naive assumption

With $d$ features, modelling the full joint $P(x_1,\dots,x_d\mid y)$ needs a huge table (for $d$ yes/no features, $2^d-1$ numbers per class). The naive shortcut:

P(\mathbf x\mid y)=\prod_{j=1}^dP(x_j\mid y)

so we only need one small distribution per feature per class. The classifier becomes

\hat y=\arg\max_y\;P(y)\prod_{j=1}^dP(x_j\mid y)

The idea

Counting parameters (binary features, $C$ classes, $d$ features):

Naive Bayes: $C\,d$ numbers $P(x_j=1\mid y)$ plus $C-1$ class priors $=Cd+(C-1)$ . For two classes: $2d+1$ .
Full joint model: $C(2^d-1)+(C-1)$ . For two classes: $2(2^d-1)+1$ .

For $d=3$ : naive needs $7$ numbers, the full model $15$ . For $d=10$ : $21$ versus $2047$ . The naive assumption turns an exponential into a linear number of parameters.

Idea 3: Learning from counts, and smoothing

Estimating by counting is MLE:

P(y=c)=\frac{\#\text{ examples of class }c}{n},\qquad P(\text{word }w\mid c)=\frac{\#\text{ times }w\text{ appears in class }c}{\#\text{ words in class }c}

Problem. If the word lottery never appeared in any training spam, its estimated probability given spam is $0$ , and because the probabilities are multiplied, one zero wipes out the entire product, no matter how spammy the rest of the email looks.

Laplace smoothing (add-one): pretend you saw every word one extra time:

P(w\mid c)=\frac{\text{count}(w,c)+1}{\text{total words in }c+V},\qquad V=\text{vocabulary size}

For a yes/no feature with two values: $\dfrac{\text{count}+1}{n_c+2}$ . This is exactly the posterior mean with a uniform Beta(1,1) prior (MLT week 4), i.e. "Laplace's rule of succession".

In practice multiply many tiny probabilities and the computer rounds to zero, so we add logs instead: $\log P(y)+\sum_j\log P(x_j\mid y)$ .

Solved example: 1. Spam or not?

Training data (word lists).

Spam (3 emails): "free win", "free money", "win money". Word counts: free 2, win 2, money 2 (total 6).
Ham (3 emails): "meeting today", "free today", "lunch today". Counts: meeting 1, today 3, free 1, lunch 1 (total 6).

Vocabulary: free, win, money, meeting, today, lunch, so $V=6$ . Priors: $\frac12,\frac12$ .

Question. Classify the email "free money" with Laplace smoothing.

Solution.

$P(\text{free}\mid\text{spam})=\frac{2+1}{6+6}=\frac14$ , $P(\text{money}\mid\text{spam})=\frac{2+1}{12}=\frac14$ .
$P(\text{free}\mid\text{ham})=\frac{1+1}{12}=\frac16$ , $P(\text{money}\mid\text{ham})=\frac{0+1}{12}=\frac1{12}$ .
Unnormalised scores: spam $=\frac12\cdot\frac14\cdot\frac14=\frac1{32}=0.03125$ ; ham $=\frac12\cdot\frac16\cdot\frac1{12}=\frac1{144}=0.00694$ .
Normalise: $P(\text{spam}\mid\text{email})=\frac{0.03125}{0.03125+0.00694}=\mathbf{0.818}$ .

Predict spam. Without smoothing, $P(\text{money}\mid\text{ham})$ would be $0$ and ham would score exactly $0$ , which would be too confident.

Idea 4: Numeric features, Gaussian Naive Bayes

When a feature is a number (height, income), model $P(x_j\mid y)$ as a Gaussian with its own mean and variance for each class and feature, both fitted by MLE from the class's examples ( $\mu$ = sample mean, $\sigma^2$ = sample variance). Then multiply the Gaussian densities across features, times the prior, as before.

Solved example: 2. A one-feature Gaussian Naive Bayes

Question. Class $+$ has feature mean 2 and variance 1; class $-$ has mean 5 and variance 1; equal priors. Classify $x=3$ and give the posterior.

Solution. $\mathcal N(3\mid2,1)=\frac{e^{-0.5}}{\sqrt{2\pi}}=0.242$ ; $\mathcal N(3\mid5,1)=\frac{e^{-2}}{\sqrt{2\pi}}=0.054$ . Posterior of $+$ is $\frac{0.242}{0.242+0.054}=\mathbf{0.818}$ . Predict $+$ . With equal priors and equal variances the decision boundary is the midpoint $x=3.5$ .

Idea 5: When does it work, and why "naive" still wins?

Pros: very fast to train (just counting), few parameters, works with little data, handles many features (text with thousands of words).
Cons: correlated features are double counted (if free and offer nearly always appear together, the model counts them as two separate pieces of evidence); the probabilities it outputs are often over-confident, though the ranking of classes is usually still right.
For binary/count features the log-odds are a linear function of the features, so Naive Bayes ends up as a linear classifier, like logistic regression, but fitted by counting instead of optimisation.

Your turn

Your turn: 1. Posterior with given numbers

$P(\text{spam})=0.4$ . $P(\text{win}\mid\text{spam})=0.5$ , $P(\text{win}\mid\text{ham})=0.1$ ; $P(\text{free}\mid\text{spam})=0.6$ , $P(\text{free}\mid\text{ham})=0.2$ . An email contains "win" and "free". Find $P(\text{spam}\mid\text{email})$ .

Need a hint?

Multiply prior times the two likelihoods for each class.

Show the full solution

Spam: $0.4\times0.5\times0.6=0.12$ . Ham: $0.6\times0.1\times0.2=0.012$ . Posterior $=\frac{0.12}{0.132}=\mathbf{0.909}$ .

Your turn: 2. Smoothing

There are 20 words in the spam class, a vocabulary of 100 words, and the word "lottery" never appears in spam. Give its smoothed probability given spam.

Need a hint?

$\frac{\text{count}+1}{\text{total}+V}$ .

Show the full solution

$\frac{0+1}{20+100}=\frac1{120}\approx0.0083$ .

Your turn: 3. Counting parameters

A two-class problem has 10 binary features. Count the parameters for Naive Bayes and for the full joint model.

Need a hint?

Naive: $2d+1$ . Full: $2(2^d-1)+1$ .

Show the full solution

Naive: $2(10)+1=\mathbf{21}$ . Full: $2(1023)+1=\mathbf{2047}$ .

Your turn: 4. True or false

(a) Naive Bayes assumes features are independent given the class. (b) Naive Bayes is a discriminative model. (c) Laplace smoothing prevents zero probabilities. (d) Because of the independence assumption, the predicted probabilities are always correct.

Need a hint?

Re-read the idea boxes.

Show the full solution

(a) True. (b) False: it is generative. (c) True. (d) False: the assumption is usually violated, and probabilities can be over-confident, though the predicted class is often right.

Your turn: 5. Gaussian Naive Bayes

Class A: mean 0, variance 1. Class B: mean 4, variance 1. Equal priors. Classify $x=1$ and give the decision boundary.

Need a hint?

Which mean is $x=1$ closer to? With equal variances and priors the boundary is halfway.

Show the full solution

$\mathcal N(1\mid0,1)=0.242$ and $\mathcal N(1\mid4,1)=\frac{e^{-4.5}}{\sqrt{2\pi}}=0.0044$ . Predict A. Boundary at $x=2$ (the midpoint).

Exam radar

MLT Quiz 2: (of the 21 summarised Quiz 2 papers) Naive Bayes in 18, generative and discriminative models in 9, Laplace smoothing in 6, number of parameters in 3. End Term: Naive Bayes in 19, Prior 13, Posterior 14, Assumption 19.

Typical: classify an email with Laplace smoothing (a fraction calculation like Example 1), count parameters, state the independence assumption exactly ("given the class"), "which of these is a generative model?".

Watch out - real exam trap

The independence is conditional on the class, not unconditional.
Don't forget the prior $P(y)$ .
With Laplace smoothing the denominator gets $+V$ (the vocabulary size) for word counts, or $+2$ for a yes/no feature.
Use the same vocabulary for every class.
Compare unnormalised scores; you only need to normalise if asked for a probability.

Quick quiz

Naive Bayes assumes that the features are...

all equal
independent given the class
independent of the class
Gaussian

The "naive" assumption is conditional independence of features given the class label.

Laplace smoothing is used to...

speed up training
avoid zero probabilities
reduce the number of classes
scale the features

A zero count would make the whole product zero.

Which of these is a generative model?

logistic regression
SVM
Naive Bayes
perceptron

Naive Bayes models p(x|y) and p(y); the others model the boundary or p(y|x) directly.

Select all TRUE statements. (select all that apply)

Naive Bayes needs far fewer parameters than a full joint model.
We can compare classes using unnormalised scores.
Naive Bayes can never be used on text.
The prior p(y) is ignored in Naive Bayes.

Naive Bayes works especially well on text, and the prior is part of the score.

Recap

Remember this

Generative: model $P(y)$ and $P(\mathbf x\mid y)$ , classify with Bayes' rule; discriminative: model $P(y\mid\mathbf x)$ directly.
Naive Bayes: $\hat y=\arg\max P(y)\prod_jP(x_j\mid y)$ . Parameters: $Cd+(C-1)$ for binary features.
Estimate by counting; Laplace smoothing adds 1 (and $V$ to the denominator). Work in logs.
Numeric features: Gaussian per class per feature. Correlated features are double counted.

Formulas to keep

$P(y\mid\mathbf x)\propto P(y)\prod_jP(x_j\mid y)$
Laplace: $\frac{\text{count}+1}{\text{total}+V}$ (words) or $\frac{\text{count}+1}{n_c+2}$ (yes/no)
Parameters (binary): naive $Cd+C-1$ ; full $C(2^d-1)+C-1$
Gaussian NB: $\mathcal N(x_j\mid\mu_{jc},\sigma^2_{jc})$ with class-wise MLE

Connected weeks (learn them together)

MLF week 10 - Probability for machine learning: Naive Bayes is Bayes' rule plus the probability tools from MLF week 10.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 12 real questions on this week All Quiz 2 papers