Stage 11 of 18Week 3 · Classificationabout 45 min

LDA and naive Bayes

Instead of modelling "class given inputs" directly, describe what the inputs look like inside each class, then flip it round with Bayes' theorem. LDA assumes bell curves with a shared spread; naive Bayes assumes the inputs are independent within each class.

LDA and naive Bayes are new this year, so no past paper has asked about them yet. Expect them in the same five formats: explain with an example, write the formula (Bayes’ theorem, the discriminant), discuss flexibility (why naive Bayes has low variance), and a small calculation (a posterior, a boundary).

Book: what to read for this stage

ISLP 4.4 intro, 4.4.1 LDA for \(p = 1\) (note the pooled variance, eq. 4.20), and 4.4.4 naive Bayes: read. 4.4.2 LDA for \(p > 1\): skim the multivariate maths (the confusion-matrix and ROC half is stage 12). 4.4.3 QDA: skip. 4.5.1: skim for “which method when”.

Slide issues

Eq. (31) estimates \(\sigma^2\) from the spread around the overall mean. LDA needs the spread within each class, around each class’s own mean (ISLP 4.20, used below). The slide version is far too big when the class means are apart. Eq. (33) is not equal to \(\log p_k(x)\); it drops terms that are the same for every class, which is fine for picking the winner. Slide 27’s “\(X = k\)” should be “\(X = x\)”.

1. Bayes’ theorem, by counting

1000 customers, 30 of whom default. 80% of defaulters have a high balance; 10% of the others do. A new customer has a high balance: how likely are they to default?

Defaulters with a high balance: \(30 \times 0.8 = 24\). Others with a high balance: \(970 \times 0.1 = 97\).
Of the 121 high-balance customers, 24 default: \(24/121 = 0.198\).

That is Bayes’ theorem. With the prior \(\pi_k = P(Y = k)\) and the class-conditional \(f_k(x) = P(X = x \mid Y = k)\):

\[p_k(x) = P(Y = k \mid X = x) = \frac{\pi_kf_k(x)}{\sum_l\pi_lf_l(x)}.\]

\(p_k(x)\) is the posterior. Lesson: even though a high balance is 8 times more typical of defaulters, the posterior is only 20%, because defaulters are rare. Priors matter. For a continuous \(X\), \(f_k\) is a density (a curve whose area gives probabilities); Bayes’ theorem works the same way.

2. LDA with one input

LDA assumes that within each class \(X\) is Gaussian with its own mean \(\mu_k\) and a shared variance \(\sigma^2\):

\[f_k(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\Big(-\frac{(x - \mu_k)^2}{2\sigma^2}\Big).\]

Fitting is counting and averaging:

\[\hat\pi_k = \frac{n_k}{n},\qquad \hat\mu_k = \text{mean of class } k,\qquad \hat\sigma^2 = \frac{1}{n - m}\sum_k\sum_{i: y_i = k}(x_i - \hat\mu_k)^2.\]

Predicting. Compare the numerators \(\pi_kf_k(x)\) (the denominator is shared). Take logs, expand \((x - \mu_k)^2\), and drop the terms with no \(k\) in them. What’s left is the discriminant:

\[\boxed{\delta_k(x) = \frac{x\mu_k}{\sigma^2} - \frac{\mu_k^2}{2\sigma^2} + \log\pi_k}, \qquad \hat Y = \arg\max_k\delta_k(x).\]

It is a straight line in \(x\), hence linear discriminant analysis. Setting \(\delta_0 = \delta_1\) gives the two-class boundary

\[x^* = \frac{\mu_0 + \mu_1}{2} + \frac{\sigma^2}{\mu_1 - \mu_0}\log\frac{\pi_0}{\pi_1}:\]

the midpoint of the means when the priors are equal, pushed towards the rarer class otherwise.

Worked example. Class 0: \(x = (1, 2, 3)\). Class 1: \(x = (5, 6, 7, 8)\). So \(n = 7\), \(m = 2\).

\(\hat\pi_0 = 3/7\), \(\hat\pi_1 = 4/7\); \(\hat\mu_0 = 2\), \(\hat\mu_1 = 6.5\).
Within-class squared deviations: class 0: \(1 + 0 + 1 = 2\); class 1: \(2.25 + 0.25 + 0.25 + 2.25 = 5\). \(\hat\sigma^2 = 7/5 = 1.4\). (Slide eq. 31 would give 6.95.)
At \(x = 4\): \(\delta_0 = \frac{8}{1.4} - \frac{4}{2.8} + \log\frac37 = 3.438\); \(\delta_1 = \frac{26}{1.4} - \frac{42.25}{2.8} + \log\frac47 = 2.923\). Predict class 0.
Boundary: \(x^* = 4.25 + \frac{1.4}{4.5}\log\frac{3/7}{4/7} = 4.25 - 0.09 = 4.16\), just left of the midpoint, since class 1 is more common.

With \(p\) inputs, LDA assumes each class is a multivariate Gaussian with its own mean vector and a shared covariance matrix. What shape are its decision boundaries?

straight lines (planes)
circles
any shape
boxes

The discriminant \(\delta_k(x) = x^T\Sigma^{-1}\mu_k - \frac12\mu_k^T\Sigma^{-1}\mu_k + \log\pi_k\) is still linear in \(x\). (QDA, with a covariance per class, gives curved boundaries.)

3. Naive Bayes

With many inputs, describing the joint density \(f_k(x_1, \dots, x_p)\) is hard. Naive Bayes assumes the inputs are independent within each class:

\[f_k(x) = f_{k1}(x_1)\times f_{k2}(x_2)\times\cdots\times f_{kp}(x_p).\]

Each \(f_{kj}\) can be its own kind: a Gaussian per class for a number, or simple counting for a category (\(P(X_j = c \mid Y = k) = n_{ck}/n_k\)). Then apply Bayes’ theorem.

It’s rarely exactly true, but it often works well, especially when \(p\) is large relative to \(n\): estimating \(p\) one-dimensional things is much easier than one \(p\)-dimensional thing, and the reduced variance usually outweighs the added bias.

Worked example: spam filter. \(P(\text{spam}) = 0.4\). “free” appears in 50% of spam and 5% of ham; “meeting” in 10% of spam and 40% of ham. An email has both words.

Spam: \(0.4 \times 0.5 \times 0.1 = 0.020\). Ham: \(0.6 \times 0.05 \times 0.4 = 0.012\). \(P(\text{spam} \mid \text{email}) = 0.020/0.032 = 0.625\).

\(P(\text{spam}) = 0.3\). “win” appears in 60% of spam and 5% of ham; “prize” in 40% of spam and 10% of ham. Assuming independence within each class, what is \(P(\text{spam})\) for an email containing both?

Spam: \(0.3 \times 0.6 \times 0.4 = 0.072\). Ham: \(0.7 \times 0.05 \times 0.1 = 0.0035\). Posterior \(0.072/0.0755 = 0.954\).

Stage test

(4 marks, exam formats 1 and 3.) Explain the assumption naive Bayes makes, give an example where it is used, and explain why it can work well even when the assumption is false.

Assumes the inputs are independent of each other within each class, so \(f_k(x) = \prod_j f_{kj}(x_j)\).
Classifies by Bayes’ theorem: posterior \(\propto \pi_k\prod_jf_{kj}(x_j)\), pick the largest.
A concrete example (e.g. spam filtering from word occurrences).
Works because estimating \(p\) one-dimensional distributions needs far less data: low variance, which can outweigh the bias (especially when \(p\) is large relative to \(n\)).

Naive Bayes assumes that, within each class \(k\), the inputs are independent, so the class-conditional density factorises: \(f_k(x) = f_{k1}(x_1)\cdots f_{kp}(x_p)\). Each one-dimensional \(f_{kj}\) is easy to estimate (a Gaussian for a number, counts for a category). It then classifies with Bayes’ theorem, \(P(Y = k \mid x) \propto \pi_k\prod_jf_{kj}(x_j)\), choosing the largest. Example: spam filtering, where the inputs are whether each word appears in the email. The independence assumption is usually false (words co-occur), but it means only \(p\) simple distributions per class are estimated instead of one \(p\)-dimensional one, so the model has low variance; the bias it introduces is often smaller than the variance it removes, especially when there are many inputs and relatively few observations.

2% of customers default. A late payment is seen in 90% of defaulters and 15% of non-defaulters. Someone has a late payment. What is the probability they default?

\(\frac{0.02 \times 0.9}{0.02 \times 0.9 + 0.98 \times 0.15} = \frac{0.018}{0.165} = 0.109\).

LDA with one input, equal priors, \(\hat\mu_0 = 2\), \(\hat\mu_1 = 8\), \(\hat\sigma^2 = 3.33\). Where is the decision boundary?

With equal priors \(\log(\pi_0/\pi_1) = 0\), so the boundary is the midpoint \((2 + 8)/2 = 5\).

How does Gaussian naive Bayes differ from LDA?

LDA lets the inputs be correlated but makes every class share one covariance matrix; Gaussian naive Bayes assumes no correlation within a class but lets each class have its own variances.
They are the same model.
Naive Bayes can’t use priors.
LDA can only handle two classes.

Different simplifying assumptions, both generative, both using Bayes’ theorem.