CS229 Machine Learning — Lecture 6 Notes Andrew Ng

CS229 Machine Learning

Lecture 6: Naı̈ve Bayes (cont.),
Neural Networks & SVMs (Intro)
Andrew Ng · Stanford University
Topics: Multinomial Event Model · Laplace Smoothing · Neural Networks · Functional &
Geometric Margins · Max-Margin Classifier

Lecture Roadmap

Naı̈ve Bayes Neural SVM

(Variations) Networks Introduction

Multinomial event model Non-linear classifiers Margins

Laplace smoothing Backpropagation Max-margin classifier

1 Naı̈ve Bayes: Variations and Extensions

Connection to Lecture 5
In Lecture 5, we introduced Naı̈ve Bayes as a generative learning algorithm for spam
classification. We modelled p(x|y) as a product of independent Bernoulli features and used
Bayes’ Rule to get p(y|x). This lecture extends that model in two important directions.

1.1 Quick Recap

The core Naı̈ve Bayes model predicts:

ŷ = arg max p(y|x) = arg max p(x|y) p(y)

y y

with the conditional independence assumption:

n
Y
p(x|y) = p(xi |y)
i=1

In Lecture 5, each xi ∈ {0, 1} indicated whether word i appeared in the email (the Multi-
variate Bernoulli Event Model). Here we examine two generalizations.

1.2 Variation 1: Multi-Valued Discrete Features (Discretization)

Generalisation to K-valued features

When a feature xi can take on K values (instead of just 0/1), we model p(xi |y) as a
multinomial instead of a Bernoulli. The rest of the Naı̈ve Bayes structure is unchanged.

1
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

1.2.1 Practical Example: Discretising Continuous Features

Suppose we want to predict whether a house will be sold in 6 months using its living area (a
continuous value). We cannot directly plug a continuous feature into Naı̈ve Bayes. The fix:
discretise.

Discretised buckets (in practice ≈ 10 buckets)

xi =1 xi =2 xi =3 xi =4 xi =5
Living area (sq ft)
500 1000 1500 2000

Intuition
By placing a continuous feature into a discrete bucket, we can still apply Naı̈ve Bayes. In
practice, ≈ 10 equal-width or equal-frequency buckets work well. This technique bridges
the gap between continuous and discrete feature spaces.

1.3 Variation 2: The Multinomial Event Model

1.3.1 Motivation: What Does the Bernoulli Model Miss?
The Multivariate Bernoulli model records whether a word appears, but not how many times. An
email containing “Viagra” 50 times feels more suspicious than one mentioning it once!

1.3.2 New Feature Representation

Multinomial Event Model — Feature Encoding

For a training email x(i) with ni words, represent it as:
(i) (i)
x(i) = x1 , x2 , . . . , x(i)


ni

(i)
where each xj ∈ {1, . . . , |V |} is the dictionary index of the j-th word in the email, and
|V | is the vocabulary size (e.g. 50,000).

Multivariate Bernoulli Multinomial Event Model

buy 1 pos 1: “buy” index

Viagra 1 pos 2: “cheap” index
deal 0 extend pos 3: “Viagra” index
hello 0 pos 4: “buy” index
friend 0 pos 5: “now” index
click 1
Fixed length = |V |, binary Variable length = ni , word indices

1.3.3 Generative Story

How the Model “Imagines” Generating an Email

1. Choose the class: Is this email spam (y = 1) or not (y = 0)?
2. Pick each word independently: For each of the ni positions, sample a word from a
distribution that depends on whether it is spam. Spam emails draw from a distribution
heavy on words like “buy”, “Viagra”, “discount”. Ham emails draw from a more natural
language distribution.

2
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

The joint distribution is:

ni  
(i)
Y
(i) (i) (i)
p(x , y ) = p(y ) p xj y (i)
j=1

1.3.4 Parameters and Maximum Likelihood Estimates

The parameters are:

ϕk|y=1 = p(xj = k | y = 1), ϕk|y=0 = p(xj = k | y = 0), ϕy = p(y = 1)

The MLE for the spam word probabilities (with Laplace smoothing):

MLE with Laplace Smoothing

m h ni
iX h i
(i)
X
(i)
1 y =1 1 xj = k + 1
i=1 j=1
ϕk|y=1 = m h i
X
1 y (i) = 1 ni + |V |
i=1

Numerator: Count how many times word k appears in all spam emails, plus 1 (smoothing).
Denominator: Total word count in all spam emails, plus |V | (one for each possible word).

Why Laplace Smoothing? (Connection to Lecture 5)

Laplace smoothing was introduced in Lecture 5 to handle the zero-probability problem:
if a word never appeared in the training spam emails, the model would assign p(word|y =
1) = 0, making the entire joint probability zero no matter what else is in the email. Adding
1 to each count ensures no word gets probability 0.
Intuition: Pretend you saw every word at least once before starting to count.

1.4 Bernoulli vs. Multinomial: Which Is Better?

Aspect Multivariate Bernoulli Multinomial

Feature vector length Fixed (|V |) Variable (ni )
Each feature encodes Presence/absence Actual word identity
Counts word frequency No Yes
Performance on text Decent Generally better
Feature type Binary Integer index

Important Caveat
Both models are bag-of-words models — they ignore word order entirely. Shuffling all
words in an email produces the exact same prediction. This is sometimes called a “unigram
model” in NLP. Bigram/trigram models account for ordering but offer only marginal
improvements for text classification.

2 Neural Networks

3
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

2.1 Motivation: The Linearity Problem

Connection to Logistic Regression (Lecture 3)

Logistic regression (Lecture 3) finds a linear decision boundary θ⊤ x = 0. It predicts y = 1
iff θ⊤ x ≥ 0. But real-world data is often not linearly separable. We need a richer class of
models — neural networks are one answer.

Linearly separable Not linearly separable

× × ◦ ×
nonlinear
×× needs NN
× ◦ ◦ ◦
◦
◦boundary
◦ ◦ × ◦ ×

2.2 Architecture: Building Blocks

A single sigmoid unit takes inputs and computes:

⊤
 1
a=g θ x , g(z) =
1 + e−z
Stack several of these to get a neural network.

Input Layer Hidden Layer

θ1
x1 a1 ⊤
g(θ1 x)

Output Layer
θ4
x2 a2 ⊤
g(θ2 x) hθ (x) g(a⊤ θ4 )

x3 a3 ⊤
g(θ3 x)

x0 =1

2.2.1 Computations at Each Layer

 
a1 = g(θ1⊤ x), a2 = g(θ2⊤ x), a3 = g(θ3⊤ x), hθ (x) = g θ4⊤ a

where a = (1, a1 , a2 , a3 )⊤ .

2.3 Training: Backpropagation

Define the cost function (mean squared error):
m
1 X (i)
2
J(θ) = y − hθ (x(i) )
2
i=1

4
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

Backpropagation
Backpropagation is simply gradient descent applied to the neural network cost function.
The name comes from how gradients are computed: errors are propagated backwards from
the output layer to each hidden layer using the chain rule.

θ ← θ − α ∇θ J(θ)

2.4 Key Challenge: Non-Convexity

The Non-Convexity Problem

Unlike logistic regression (whose log-likelihood is concave, guaranteeing a global optimum),
the neural network cost function is non-convex. There can be many local minima, and
gradient descent may get stuck.

J J

local local
global min

θ θ
Logistic Reg. (convex)
Neural Network (non-convex)

Historical Note: LeNet and NETtalk

LeNet (Yann LeCun, NYU): A convolutional neural network for handwritten digit
recognition. Its hidden layers learn edge detectors automatically from data — an early
demonstration that NNs discover hierarchical representations.
NETtalk (Terry Sejnowski): Learned to pronounce English text from raw letter-to-sound
pairs. Generated excitement about AI by sounding like “a child learning to speak”. An
early milestone in neural network history (1987).

3 Support Vector Machines — Introduction

Connection to Neural Networks and Logistic Regression

Neural networks give non-linear classifiers but suffer from non-convexity. SVMs achieve
non-linear classification with a convex optimisation problem (to be seen in upcoming
lectures via the “kernel trick”). They start from the same idea as logistic regression —
find a hyperplane — but optimise a richer objective.

3.1 Notation Change

SVM development is cleaner with a modified notation:

Element Logistic Regression SVM

Labels y ∈ {0, 1} y ∈ {−1, +1}
Decision function g(z) = 1+e1−z g(z) = sign(z)
Parameters θ ∈ Rn+1 , x0 = 1 w ∈ Rn , b ∈ R
Hypothesis g(θ⊤ x) g(w⊤ x + b)

5
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

The decision boundary is the hyperplane {x : w⊤ x + b = 0}.

3.2 Two Intuitions for Good Classifiers

3.2.1 Intuition 1: Confident Predictions

A classifier is “confident” when |w⊤ x + b| is large. If y (i) = +1 we want w⊤ x(i) + b ≫ 0; if

y (i) = −1 we want w⊤ x(i) + b ≪ 0.

Decision boundary

very confident − very confident +

w⊤ x + b
predict y = −1 uncertain region predict y = +1

3.2.2 Intuition 2: Maximising the Margin

Bad separator Better separator Best: max margin

× × ×margin
×
× ×
× ×
×
× × ×

◦ ◦ ◦
◦ ◦◦ ◦ ◦◦ ◦ ◦◦

Key Insight
Among all decision boundaries that correctly classify the training data, the maximum
margin boundary is the most “robust” — it is furthest from all training examples. This
leads to better generalisation.

3.3 Functional Margin

Functional Margin — Definition

The functional margin of hyperplane (w, b) with respect to training example (x(i) , y (i) )
is:
γ̂ (i) = y (i) w⊤ x(i) + b

The functional margin with respect to the entire training set is:

γ̂ = min γ̂ (i)
i=1,...,m

Intuition: Why This Formula Works

ˆ If y (i) = +1: we want w⊤ x(i) + b > 0, so a large positive product is good.
ˆ If y (i) = −1: we want w⊤ x(i) + b < 0, so y (i) · (. . .) is again positive and large.
ˆ If γ̂ (i) > 0: the example is correctly classified.

6
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

The Scale Problem with Functional Margin

If we replace (w, b) by (2w, 2b), the functional margin doubles without any change to the
actual decision boundary. We cannot naively maximise γ̂ — it is trivially made arbitrarily
large by rescaling.
γ̂ (i) (2w, 2b) = 2 γ̂ (i) (w, b)
Fix: Introduce a normalisation condition, e.g. ∥w∥ = 1, leading to the geometric margin.

3.4 Geometric Margin

Geometric Margin — Definition

The geometric margin of (w, b) w.r.t. example (x(i) , y (i) ) is the Euclidean distance from
x(i) to the decision boundary:

γ̂ (i)
 
(i) (i) w ⊤ (i) b
γ =y x + =
∥w∥ ∥w∥ ∥w∥

For the training set: γ = min γ (i) .

i=1,...,m

3.4.1 Geometric Derivation

x2

x(i)
γ (i)
w/ ∥w∥

⊤
w x+b=0
margin boundaries

x1

Geometric Margin Key Properties

ˆ Scale-invariant: Replacing (w, b) with (cw, cb) does not change γ.
ˆ Equals functional margin when ∥w∥ = 1.
ˆ Measures the actual physical distance between a point and the boundary.

3.5 The Maximum Margin Classifier

Optimisation Problem (Maximum Margin Classifier)

Choose γ, w, b to solve:
 
max γ subject to y (i) w⊤ x(i) + b ≥ γ ∀ i, ∥w∥ = 1
γ, w, b

7
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

Equivalently (using scale freedom to set γ̂ = 1, to be shown in next lecture):

1  
min ∥w∥2 subject to y (i) w⊤ x(i) + b ≥ 1 ∀ i
w, b 2

This is a convex quadratic programme — solvable efficiently and globally!

Why 1
2 ∥w∥2 ?

Maximising γ = 1/ ∥w∥ is equivalent to minimising ∥w∥, and hence ∥w∥2 (the 12 is just
for algebraic convenience). This is the foundation of the full SVM — to be developed in
upcoming lectures.

4 Connecting Everything: The Big Picture

Linear Logistic Generalized
Regression Regression
add sigmoid Linear Models
Lecture 1–2 Lecture 3 Lecture 4
generative view
both logistic
give
Bayesposterior
GDA ⇒ Logistic
(Lecture 5 key result)
Gaussian
Discriminant max margin Naı̈ve Bayes
stack units
Analysis Lecture 5–6
Lecture 5
MLE + Laplace smoothing

Support Vector Neural

Machines Networks
Lecture 6+ Lecture 6

Convex opt. → global min! Non-convex, local minima

All Connections in One View

1. Logistic Regression → Naı̈ve Bayes: Both are classifiers; logistic is discriminative
(models p(y|x) directly) while Naı̈ve Bayes is generative (models p(x|y), uses Bayes
Rule). If the Naı̈ve Bayes model is correct, both converge to the same posterior — the
logistic function. (Key Lecture 5 result.)

2. GDA → Logistic Regression: If x|y is Gaussian, the posterior p(y|x) is exactly

logistic. GDA makes stronger assumptions but can need less data to train.

3. Logistic Regression → Neural Networks: A neural network stacks logistic (sigmoid)

units to build non-linear classifiers. A single sigmoidal unit is logistic regression.

4. Logistic Regression → SVMs: Both find a linear boundary, but SVMs optimise the
geometric margin rather than the log-likelihood. The result is a convex optimisation
problem, unlike neural networks.

5. Laplace Smoothing → MLE: Laplace smoothing is a Bayesian prior (uniform Dirich-

let) on the MLE estimate. It prevents zero probabilities and improves generalisation in
Naı̈ve Bayes.

8
CS229 Machine Learning — Lecture 6 Notes Andrew Ng

6. Functional Margin → Geometric Margin → SVM: Functional margin measures

confidence but is scale-dependent. Normalising by ∥w∥ gives the geometric margin (true
distance), which is the quantity SVMs maximise.

Quick Reference: Key Formulas

Concept Formula Notes

Naı̈ve Bayes (Multi- ϕk|y=1 = Laplace-smoothed

nomial MLE) P  (i)=1  P h (i) i
i1 y j 1 xj = k + 1
P  (i) 
i1 y = 1 ni + |V |
J(θ) = 21 i (y (i) − hθ (x(i) ))2
P
NN cost function Minimised by backprop

Functional margin γ̂ (i) = y (i) (w⊤ x(i) + b) Scale-dependent

Geometric margin γ (i) = γ̂ (i) /∥w∥ Scale-invariant

Max-margin objec- minw,b 12 ∥w∥2 s.t. y (i) (w⊤ x(i) + b) ≥ 1 Convex QP

tive

Next Lecture: Full SVM derivation — the kernel trick, soft-margin SVMs, and how to handle
non-linearly separable data efficiently.