04_Bayes_Decision_Theory_and_Naive_Bayes

Module 3 — Bayes Decision Theory and Naive Bayes

Sources: Lec 7 — Bayes Decision Rule for Data Classification; Lec 8 — Naive Bayes Classifier. · Prev: Module 2 · Next: Module 4 — kNN · Index: 00_INDEX_and_Coverage

Notation

Classes $w_1,\dots ,w_c$; priors $p(w_i)$, ${\sum }_{i}p(w_i)=1$; class-conditional density $p(\vec{X}|w_i)=f_i(\vec{X})$; posterior $p(w_i|\vec{X})$. $\Phi$ = standard normal CDF, $\varphi$ = its density.

Python helpers — run once, checks below reuse them

import numpy as np
from scipy.stats import norm
from scipy.optimize import minimize_scalar
Phi = norm.cdf                       # standard normal CDF

flowchart LR
    P["prior p(w)"] --> B((Bayes))
    L["likelihood p(X|w)"] --> B
    B --> Q["posterior p(w|X)"]
    Q --> D["decide argmax"]

---

C14. The Bayes Decision Rule

Intuition

Before seeing data you hold a prior belief about each class. After seeing $\vec{X}$ you update to a posterior. The best you can do is pick the class with the highest posterior. Using only the prior (“always say the biggest class”) ignores the evidence.

Formal definition

Bayes’ theorem: $p(w_i|\vec{X})=\frac{p(\vec{X}|w_i)p(w_i)}{p(\vec{X})}=\frac{p(\vec{X}|w_i)p(w_i)}{{\sum }_{j=1}^{c}p(\vec{X}|w_j)p(w_j)}.$ Bayes decision rule: assign $\vec{X}$ to $w_i$ if $p(w_i|\vec{X})\ge p(w_j|\vec{X})\forall j\ne i$, equivalently $p(\vec{X}|w_i)p(w_i)\ge p(\vec{X}|w_j)p(w_j)\forall j\ne i.$ Ties are resolved arbitrarily.

Derivation (why the denominator can be dropped)

$p(\vec{X})={\sum }_{j}p(\vec{X}|w_j)p(w_j)$ is the same for every class, so comparing $p(w_i|\vec{X})\ge p(w_j|\vec{X})$ reduces to comparing numerators. The joint form: $p(w_i,\vec{X})=p(w_i|\vec{X})p(\vec{X})=p(\vec{X}|w_i)p(w_i)$.

Special case: two Gaussian classes with common variance (1-D)

Decide $w_1$ iff $\ln p_1-\frac{(x-{\mu }_1{)}^2}{2{\sigma }^2}\ge \ln p_2-\frac{(x-{\mu }_2{)}^2}{2{\sigma }^2}$. Using $(x-{\mu }_2{)}^2-(x-{\mu }_1{)}^2=({\mu }_1-{\mu }_2)(2x-{\mu }_1-{\mu }_2)$ and assuming ${\mu }_1<{\mu }_2$: $x\le \frac{{\mu }_1+{\mu }_2}{2}+\frac{{\sigma }^2\ln (p_1/p_2)}{{\mu }_2-{\mu }_1}.$

Key insights

• The prior-only rule is a degenerate case ($p(\vec{X}|w_i)$ ignored).
• A larger prior moves the threshold toward the other class’s mean (enlarging its own region).
• In practice, $p(\vec{X}|w_i)$ and $p(w_i)$ must be estimated; optimality (C15) holds only if they are right.

Worked examples

Example 1 — Very Easy · Spam with no evidence

• Problem: A data set has 300 spam and 700 ham mails. A new mail is classified using only the prior. Which class?
• Asked: Prior-only decision.
• Concept: Prior rule.
• Approach: Priors $=0.3,0.7$.
• Solution: $p(\text{ham})=0.7>0.3=p(\text{spam})$ → ham for every mail.
• Final answer: Ham (always).

Key lesson

The prior alone never flags spam — we need the likelihood.

Example 2 — Easy · Evidence overturns the prior

• Problem: $p(w_1)=0.6,p(w_2)=0.4$; at the observed $\vec{X}$: $p(\vec{X}|w_1)=0.2,p(\vec{X}|w_2)=0.5$. Find the posteriors and the decision.
• Asked: Posteriors and class.
• Concept: Bayes’ theorem.
• Approach: Joints, then normalise.
• Solution: Joints: $0.6\times 0.2=0.12$; $0.4\times 0.5=0.20$. $p(\vec{X})=0.32$. Posteriors: $0.12/0.32=0.375$; $0.20/0.32=0.625$.
• Final answer: $p(w_1|\vec{X})=0.375$, $p(w_2|\vec{X})=0.625$ → $w_2$.

Key lesson

A strong likelihood can overturn a larger prior.

Example 3 — Moderate · Three classes

• Problem: Three classes with priors $0.5,0.3,0.2$ and likelihoods at $\vec{X}$ of $0.1,0.4,0.8$. Classify and give posteriors.
• Asked: Decision and posteriors.
• Concept: Multi-class Bayes rule.
• Approach: Joints → normalise.
• Solution: Joints $0.05,0.12,0.16$; sum $0.33$. Posteriors $0.1515,0.3636,0.4848$.
• Final answer: $w_3$ (posterior $0.485$), though it has the smallest prior.

Python check

prior = np.array([.5, .3, .2]); lik = np.array([.1, .4, .8])
joint = prior * lik; print(joint / joint.sum())      # [0.1515 0.3636 0.4848]

Key lesson

Rank by the joint $p(w)p(\vec{X}|w)$, not by prior or likelihood alone.

Example 4 — Hard · Same point, different priors

• Problem: $f_1=N(0,1)$, $f_2=N(2,1)$. (a) Equal priors: threshold? (b) $p_1=0.8,p_2=0.2$: threshold? (c) Classify $x=1.2$ in each case, verifying with densities.
• Asked: Two thresholds and decisions.
• Concept: The prior shifts the boundary.
• Approach: Use the threshold formula; verify numerically.
• Solution: (a) $\frac{0+2}{2}+\frac{1\cdot \ln 1}{2}=1$. (b) $1+\frac{\ln (0.8/0.2)}{2}=1+\frac{1.3863}{2}=1.6931$. (c) $f_1(1.2)=\varphi (1.2)=0.1942$; $f_2(1.2)=\varphi (-0.8)=0.2897$. Equal priors: $0.1942<0.2897$ → $w_2$ (consistent with $1.2>1$). Priors $(0.8,0.2)$: $0.8(0.1942)=0.1554$ vs $0.2(0.2897)=0.0579$ → $w_1$ (consistent with $1.2<1.693$).
• Final answer: Thresholds $1$ and $1.693$; $x=1.2$ goes to $w_2$, then $w_1$.

 density
   ▲      f1·p1 (tall, prior 0.8)        f2·p2 (short, prior 0.2)
   │        ╱‾╲                              ╱‾╲
   │      ╱     ╲                          ╱     ╲
   └────╱────────┼───────┼─────────────╱─────────────→ x
        0        1     1.69            2
              equal-prior   prior-shifted boundary

Python check

print(1 + np.log(4) / 2)                                       # 1.6931
print(norm.pdf(1.2), norm.pdf(0.8))                            # 0.1942  0.2897
print(0.8 * norm.pdf(1.2), 0.2 * norm.pdf(0.8))                # 0.1553  0.0579 -> w1

Key lesson

The same data point flips class when priors change.

Example 5 — Very Hard · Same mean, different spread

• Problem: Equal priors, $f_1=N(0,1)$, $f_2=N(0,4)$ (variance 4). Find the decision regions and the Bayes error.
• Asked: Regions and error $R$.
• Concept: Unequal variances → two thresholds; $R=\int \min$.
• Approach: Compare densities; integrate.
• Solution: Decide $w_1$ iff $f_1\ge f_2$: $\frac{1}{\sqrt{2\pi }}{e}^{-x^2/2}\ge \frac{1}{2\sqrt{2\pi }}{e}^{-x^2/8}$ $⟺e^{-3x^2/8}\ge \frac{1}{2}$ $⟺x^2\le \frac{8}{3}\ln 2=1.8484$ $⟺|x|\le 1.3596$. So $w_1$ in the middle, $w_2$ in both tails. Error: $R=\frac{1}{2}[P(|X|\le 1.3596|w_2)+P(|X|>1.3596|w_1)]$. Under $w_2$, $X/2\sim N(0,1)$: $P(|X|\le 1.3596)=2\Phi (0.6798)-1=0.5034$. Under $w_1$: $2(1-\Phi (1.3596))=0.1740$. $R=\frac{1}{2}(0.5034+0.1740)=0.3387$.
• Final answer: $w_1$ iff $|x|\le 1.36$; $R=0.339$.

Python check

x0 = np.sqrt(8 / 3 * np.log(2))
R = 0.5 * ((2 * Phi(x0 / 2) - 1) + 2 * (1 - Phi(x0)))
print(x0, R)                                    # 1.3596  0.3387

Key lesson

With unequal variances the Bayes boundary is not a single point; the wide class owns both tails.

Common mistakes

• Comparing likelihoods only, forgetting priors.
• Normalising incorrectly (posteriors must sum to 1).

Exam traps

• Priors are estimated from the class proportions of the data.
• The rule is "$\ge$"; ties are broken arbitrarily.

Connections: C15–C18 (error, bounds, discriminants), Naive Bayes (C19), logistic regression (C27), kNN (C23).

Mastery checklist

• Derive the posterior; drop $p(\vec{X})$.
• Find the 1-D Gaussian threshold with priors.
• Interpret a prior shift.

---

C15. Probability of Error and Optimality of the Bayes Rule

Intuition

A classifier’s mistakes are the regions where it picks the less likely class. The Bayes rule always picks the more likely one, so it makes the minimum possible total error.

Formal definition

For $h:{\mathbb{R}}^m\to \{w_1,w_2\}$ with decision regions $T_i(h)=\{\vec{X}:h(\vec{X})=w_i\}$: $R(h)={\int }_{T_2(h)}p(w_1)f_1(\vec{X})d\vec{X}+{\int }_{T_1(h)}p(w_2)f_2(\vec{X})d\vec{X}.$ For the Bayes rule: $R(h_{Bayes})=\int \min (p(w_1)f_1(\vec{X}),p(w_2)f_2(\vec{X}))d\vec{X}.$

Derivation (optimality)

Every point $\vec{X}$ contributes either $p(w_1)f_1$ (if placed in $T_2$) or $p(w_2)f_2$ (if placed in $T_1$). The smallest possible contribution is the minimum of the two, achieved by placing $\vec{X}$ in $T_1$ when $p(w_1)f_1\ge p(w_2)f_2$ — exactly Bayes. Therefore $R(h)\ge R(h_{Bayes})$ for every $h$. ∎

Closed form for equal-variance Gaussians

$f_i=N({\mu }_i,{\sigma }^2)$, ${\mu }_1<{\mu }_2$, equal priors; Bayes threshold $\frac{{\mu }_1+{\mu }_2}{2}$: $R=\frac{1}{2}P(X>\frac{{\mu }_1+{\mu }_2}{2}|w_1)+\frac{1}{2}P(X\le \frac{{\mu }_1+{\mu }_2}{2}|w_2)=\frac{1}{2}[1-\Phi (\frac{{\mu }_2-{\mu }_1}{2\sigma }\left)\right]+\frac{1}{2}\Phi \left(\frac{{\mu }_1-{\mu }_2}{2\sigma }\right).$ Using $1-\Phi (z)=\Phi (-z)$, both brackets equal $\Phi \left(\frac{{\mu }_1-{\mu }_2}{2\sigma }\right)$, so $\boxed{R=\Phi \left(\frac{{\mu }_1-{\mu }_2}{2\sigma }\right)=\Phi (-\frac{d}{2}),d=\frac{|{\mu }_2-{\mu }_1|}{\sigma }.}$

Key insights

• The Bayes error is a floor; no learner (kNN, SVM, NN, …) can beat it with the true distribution.
• If the densities are estimated, optimality is no longer guaranteed.
• Error shrinks as the means move apart relative to $\sigma$.

Worked examples

Example 1 — Very Easy · A discrete feature

• Problem: A discrete feature takes values $a,b,c$. Joint probabilities $p(w_1,x)=(0.20,0.15,0.05)$ and $p(w_2,x)=(0.05,0.10,0.45)$ for $x=a,b,c$. Give the Bayes decision per value and the Bayes error.
• Asked: Decisions and $R$.
• Concept: $R=\sum \min$.
• Approach: The larger joint wins; the smaller is the error mass.
• Solution: $a$: $0.20>0.05$ → $w_1$, error $0.05$. $b$: $0.15>0.10$ → $w_1$, error $0.10$. $c$: $0.05<0.45$ → $w_2$, error $0.05$. $R=0.05+0.10+0.05=0.20$.
• Final answer: $a,b\to w_1$; $c\to w_2$; $R=0.20$.

Key lesson

Error = total mass of the losing joint at each point.

Example 2 — Easy · Closed-form Gaussian error

• Problem: $f_1=N(0,4)$ ($\sigma =2$), $f_2=N(4,4)$, equal priors. Bayes error?
• Asked: $R$.
• Concept: $R=\Phi (-d/2)$.
• Approach: $d=|0-4|/2=2$.
• Solution: $R=\Phi (-1)=0.1587$.
• Final answer: $0.159$.

Key lesson

Only the ratio separation / $\sigma$ matters.

Example 3 — Moderate · A wrong threshold costs error

• Problem: Same setup as Example 2 but use the (non-optimal) threshold $t=1$ instead of $2$. Compute its error and compare.
• Asked: $R(t=1)$.
• Concept: Optimality of Bayes.
• Approach: $R(t)=\frac{1}{2}[P(X>t|w_1)+P(X<t|w_2)]$.
• Solution: $P(X>1|w_1)=1-\Phi (0.5)=0.3085$. $P(X<1|w_2)=\Phi (-1.5)=0.0668$. $R=\frac{1}{2}(0.3085+0.0668)=0.1877$.
• Final answer: $0.188>0.159$.

Python check

print(Phi(-1), 0.5 * ((1 - Phi(.5)) + Phi(-1.5)))         # 0.1587  0.1877

Key lesson

Moving the threshold off the Bayes point strictly increases error.

Example 4 — Hard · How far apart must the classes be?

• Problem: For equal priors and equal variance, what separation $d=|{\mu }_2-{\mu }_1|/\sigma$ is needed for Bayes error $5\%$? For $1\%$?
• Asked: Two $d$‘s.
• Concept: Invert $\Phi (-d/2)=R$.
• Approach: ${\Phi }^{-1}$.
• Solution: $\Phi (-d/2)=0.05\Rightarrow d/2=1.645\Rightarrow d=3.29$. $\Phi (-d/2)=0.01\Rightarrow d/2=2.326\Rightarrow d=4.65$.
• Final answer: $d=3.29$ and $d=4.65$.

Python check

print(-2 * norm.ppf(.05), -2 * norm.ppf(.01))             # 3.2897  4.6527

Key lesson

Pushing the error from 5 % to 1 % needs $\approx 41\%$ more separation ($4.65/3.29=1.41$).

Example 5 — Very Hard · Bayes vs ignoring the prior vs always-majority

• Problem: $f_1=N(0,1)$, $f_2=N(2,1)$, priors $0.8,0.2$. Compute (a) the Bayes error; (b) the error of the threshold $1$ (which ignores priors); (c) the error of “always $w_1$”.
• Asked: Three errors.
• Concept: Bayes optimality with priors.
• Approach: Threshold $1.6931$ from C14 Ex. 4.
• Solution: (a) $R=0.8[1-\Phi (1.693)]+0.2\Phi (1.693-2)=0.8(0.0452)+0.2(0.3794)=0.0362+0.0759=0.1121$. (b) $0.8[1-\Phi (1)]+0.2\Phi (-1)=0.1587$. (c) $=p_2=0.20$.
• Final answer: $0.112<0.159<0.200$.

Python check

t = 1 + np.log(4) / 2
print(0.8 * (1 - Phi(t)) + 0.2 * Phi(t - 2),                # 0.1121
      0.8 * (1 - Phi(1)) + 0.2 * Phi(-1))                   # 0.1587

Key lesson

Bayes beats both the “ignore-prior” threshold and the trivial majority classifier.

Common mistakes

• Writing $R$ as an integral of posteriors instead of $p(w_i)f_i$ (the lecture’s “minimum posterior” means the minimum joint).
• Using $\Phi$ with the wrong sign.

Exam traps

• Optimality needs the true densities; estimated densities may not be optimal.
• $R=\Phi \left(\frac{{\mu }_1-{\mu }_2}{2\sigma }\right)$ requires equal priors and equal variances.

Connections: C14, C16 (bounds), 1-NN vs Bayes (C23).

Mastery checklist

• Prove the Bayes rule minimises $R$.
• Derive $R=\Phi (-d/2)$.
• Compute $R$ with unequal priors.

---

C16. Chernoff and Bhattacharyya Error Bounds

Intuition

The Bayes error integral $\int \min (\cdot ,\cdot )$ is usually impossible to evaluate. Replace $\min (u,v)$ by the smooth upper bound $u^{\alpha }{v}^{1-\alpha }$ (a geometric-type mean), which does integrate in closed form for Gaussians.

Formal results

For $u,v\ge 0$ and $0\le \alpha \le 1$: $\min (u,v)\le u^{\alpha }{v}^{1-\alpha }$. Hence $R(h)\le p(w_1{)}^{\alpha }p(w_2{)}^{1-\alpha }\int f_1^{\alpha }{f}_2^{1-\alpha }d\vec{X}.$ For Gaussians $f_i=N({\vec{\mu }}_i,{\Sigma }_i)$: $\int f_1^{\alpha }{f}_2^{1-\alpha }d\vec{X}=e^{-I(\alpha )}$, $I(\alpha )=\frac{\alpha (1-\alpha )}{2}({\vec{\mu }}_2-{\vec{\mu }}_1{)}^T[\alpha {\Sigma }_1+(1-\alpha ){\Sigma }_2{]}^{-1}({\vec{\mu }}_2-{\vec{\mu }}_1)+\frac{1}{2}\ln \frac{|\alpha {\Sigma }_1+(1-\alpha ){\Sigma }_2|}{|{\Sigma }_1{|}^{\alpha }|{\Sigma }_2{|}^{1-\alpha }}.$ $R\le p(w_1{)}^{\alpha }p(w_2{)}^{1-\alpha }{e}^{-I(\alpha )}.$

• Chernoff bound: minimise the right side over $\alpha \in [0,1]$ (tightest).
• Bhattacharyya bound: the easy choice $\alpha =\frac{1}{2}$.

Derivation of $\min (u,v)\le u^{\alpha }{v}^{1-\alpha }$

Suppose $u<v$ (so $\min =u$). Then $u^{\alpha }{v}^{1-\alpha }=u(v/u{)}^{1-\alpha }\ge u$ because $v/u>1$ and $1-\alpha \ge 0$. The case $v\le u$ is symmetric (use $v(u/v{)}^{\alpha }\ge v$). ∎

Special case: equal covariance

${\Sigma }_1={\Sigma }_2=\Sigma$ ⇒ log-term $=0$ and $I(\alpha )=\frac{\alpha (1-\alpha )}{2}{\Delta }^T{\Sigma }^{-1}\Delta$, maximal (so the bound is tightest) at $\alpha =\frac{1}{2}$ when priors are equal.

Key insights

• Every $\alpha$ gives a valid bound; $\alpha$ is a tuning knob.
• For equal priors and equal covariances, Chernoff = Bhattacharyya.

Worked examples

Example 1 — Very Easy · The inequality

• Problem: Check $\min (u,v)\le u^{1/2}{v}^{1/2}$ for $u=4,v=9$.
• Asked: Verify.
• Concept: The inequality.
• Approach: Numbers.
• Solution: $\min =4$; $\sqrt{4\cdot 9}=6\ge 4$ ✓.
• Final answer: $4\le 6$.

Key lesson

The geometric mean exceeds the minimum.

Example 2 — Easy · Dependence on α

• Problem: Same $u,v$ with $\alpha =0.3$ and $\alpha =1$.
• Asked: Bound values.
• Concept: Dependence on $\alpha$.
• Approach: $u^{\alpha }{v}^{1-\alpha }$.
• Solution: $\alpha =0.3$: $4^{0.3}{9}^{0.7}=e^{0.4159+1.5381}=e^{1.954}=7.06\ge 4$. $\alpha =1$: $4^1\cdot 9^0=4=\min$ (tight).
• Final answer: $7.06$ and $4$.

Key lesson

The bound is exact at the extreme $\alpha$ that matches which of $u,v$ is smaller — but a single $\alpha$ is used for the whole integral.

Example 3 — Moderate · Bhattacharyya vs the truth

• Problem: $f_1=N(0,4)$, $f_2=N(4,4)$, equal priors. Bhattacharyya bound vs true error.
• Asked: Bound.
• Concept: $I(\frac{1}{2})$ with equal variances.
• Approach: 1-D: $\Delta =4$, ${\sigma }^2=4$.
• Solution: $I(\frac{1}{2})=\frac{0.5\cdot 0.5}{2}\cdot \frac{16}{4}=0.5$. Bound: $\sqrt{0.5\cdot 0.5}{e}^{-0.5}=0.5(0.6065)=0.3033$. True $R=\Phi (-1)=0.1587$.
• Final answer: $R\le 0.303$ (true $0.159$).

Key lesson

Bounds are valid but loose.

Example 4 — Hard · Chernoff with unequal priors

• Problem: $f_1=N(0,1)$, $f_2=N(2,1)$, priors $0.8,0.2$. Minimise the bound over $\alpha$ (Chernoff) and compare with $\alpha =\frac{1}{2}$ and with the true $0.1121$.
• Asked: ${\alpha }^{\ast }$ and bounds.
• Concept: Chernoff.
• Approach: $\ln g(\alpha )=\alpha \ln 0.8+(1-\alpha )\ln 0.2-\frac{\alpha (1-\alpha ){\Delta }^2}{2}$ with ${\Delta }^2/2=2$.
• Solution: $\ln g=-0.2231\alpha -1.6094(1-\alpha )-2\alpha (1-\alpha )$. Derivative: $4\alpha -0.6137=0\Rightarrow {\alpha }^{\ast }=0.1534$. $g({\alpha }^{\ast })=0.1908$. At $\alpha =0.5$: $\ln g=-1.4163\Rightarrow 0.2426$.
• Final answer: Chernoff $\approx 0.191$ (${\alpha }^{\ast }=0.153$); Bhattacharyya $0.243$; true $0.112$.

Python check

g = lambda a: a*np.log(.8) + (1-a)*np.log(.2) - a*(1-a)*4/2
r = minimize_scalar(g, bounds=(0, 1), method="bounded")
print(r.x, np.exp(r.fun), np.exp(g(.5)))                  # 0.1534  0.1908  0.2426

Key lesson

Unequal priors push the optimal $\alpha$ away from $\frac{1}{2}$.

Example 5 — Very Hard · Separation from covariance alone

• Problem: $f_1=N(0,1)$, $f_2=N(0,4)$, equal priors (C14 Ex. 5; true $R=0.3387$). Compute the Bhattacharyya bound.
• Asked: The bound.
• Concept: $I(\alpha )$ with unequal covariances.
• Approach: Means equal ⇒ first term $0$; use the determinant term.
• Solution: $\alpha =\frac{1}{2}$: $\alpha {\Sigma }_1+(1-\alpha ){\Sigma }_2=2.5$. $|{\Sigma }_1{|}^{1/2}|{\Sigma }_2{|}^{1/2}=2$. Ratio $=1.25$. $I=\frac{1}{2}\ln 1.25=0.1116$. Bound $=0.5e^{-0.1116}=0.4472$.
• Final answer: $R\le 0.447$ (true $0.339$).

Python check

print(0.5 * np.exp(-0.5 * np.log(1.25)))                  # 0.4472

Key lesson

Differences in covariance alone contribute separation via the determinant term.

Common mistakes

• Forgetting priors in the bound.
• Treating the bound as the error.

Exam traps

• Chernoff = optimise $\alpha$; Bhattacharyya = fix $\alpha =0.5$.
• The first term vanishes when the means coincide.

Connections: C15; mutual-information / Hellinger-type measures.

Mastery checklist

• Prove $\min (u,v)\le u^{\alpha }{v}^{1-\alpha }$.
• Evaluate $I(\alpha )$ in 1-D.
• Optimise $\alpha$.

---

C17. Minimum Distance Classifier

Intuition

If all classes are equally likely and spread identically round their means (a round “ball” of unit variance), the most likely class is simply the class whose mean is nearest.

Formal derivation (lecture)

$f_i=N({\vec{\mu }}_i,I)$, equal priors $1/c$. Decide $w_i$ iff $p(w_i)f_i\ge p(w_j)f_j$: $\frac{1}{c}\frac{1}{(\sqrt{2\pi }{)}^m}{e}^{-\frac{1}{2}(\vec{X}-{\vec{\mu }}_i{)}^T(\vec{X}-{\vec{\mu }}_i)}\ge \frac{1}{c}\frac{1}{(\sqrt{2\pi }{)}^m}{e}^{-\frac{1}{2}(\vec{X}-{\vec{\mu }}_j{)}^T(\vec{X}-{\vec{\mu }}_j)}$ (cancel constants, $|I|=1$) ⇒ $(\vec{X}-{\vec{\mu }}_i{)}^T(\vec{X}-{\vec{\mu }}_i)\le (\vec{X}-{\vec{\mu }}_j{)}^T(\vec{X}-{\vec{\mu }}_j)\forall j\ne i,$ i.e. $\Vert \vec{X}-{\vec{\mu }}_i\Vert \le \Vert \vec{X}-{\vec{\mu }}_j\Vert$.

Generalisation (derived)

For ${\Sigma }_i={\sigma }^{2}I$ and unequal priors the rule is: maximise $g_i(\vec{X})=\ln p(w_i)-\frac{\Vert \vec{X}-{\vec{\mu }}_i{\Vert }^2}{2{\sigma }^2}$. For general common $\Sigma$ it is the Mahalanobis-distance rule $(\vec{X}-{\vec{\mu }}_i{)}^T{\Sigma }^{-1}(\vec{X}-{\vec{\mu }}_i)$.

Boundary between two means

$\Vert \vec{X}-{\vec{\mu }}_1{\Vert }^2=\Vert \vec{X}-{\vec{\mu }}_2{\Vert }^2⟺2{\vec{X}}^T({\vec{\mu }}_2-{\vec{\mu }}_1)=\Vert {\vec{\mu }}_2{\Vert }^2-\Vert {\vec{\mu }}_1{\Vert }^2$ — the perpendicular-bisector hyperplane.

Worked examples

Example 1 — Very Easy · Nearest of two means

• Problem: ${\vec{\mu }}_1=(0,0)$, ${\vec{\mu }}_2=(4,2)$; classify $\vec{X}=(1,1)$.
• Asked: Class.
• Concept: Nearest mean.
• Approach: Squared distances.
• Solution: $d_1^2=1+1=2$; $d_2^2=9+1=10$.
• Final answer: $w_1$.

Key lesson

Compare squared distances; no square root needed.

Example 2 — Easy · Three classes

• Problem: Means $(0,0),(5,0),(0,5)$; classify $(3,1)$.
• Asked: Class.
• Concept: $c$-class nearest mean.
• Approach: Three distances.
• Solution: $d_1^2=10$; $d_2^2=4+1=5$; $d_3^2=9+16=25$.
• Final answer: $w_2$.

Key lesson

Extends directly to $c$ classes.

Example 3 — Moderate · The boundary line

• Problem: Equation of the boundary for ${\vec{\mu }}_1=(0,0)$, ${\vec{\mu }}_2=(4,2)$, and which side is $w_2$?
• Asked: Boundary.
• Concept: Perpendicular bisector.
• Approach: Equate squared distances.
• Solution: $x_1^2+x_2^2=(x_1-4{)}^2+(x_2-2{)}^2\Rightarrow 0=-8x_1-4x_2+20\Rightarrow 2x_1+x_2=5$. Test ${\vec{\mu }}_2$: $2(4)+2=10>5$ ⇒ $w_2$ side is $2x_1+x_2>5$.
• Final answer: $2x_1+x_2=5$.

Key lesson

The boundary passes through the midpoint $(2,1)$ ($2\cdot 2+1=5$ ✓) and is perpendicular to ${\vec{\mu }}_2-{\vec{\mu }}_1=(4,2)$.

Example 4 — Hard · With a prior

• Problem: 1-D, ${\sigma }^2=1$, ${\mu }_1=0,{\mu }_2=4$, priors $0.8,0.2$. Boundary and the class of $x=2.2$.
• Asked: Threshold.
• Concept: $g_i=\ln p_i-\frac{(x-{\mu }_i{)}^2}{2{\sigma }^2}$.
• Approach: Set $g_1=g_2$.
• Solution: $x_{th}=2+\frac{\ln 4}{4}=2.3466$. At $x=2.2$: $g_1=\ln 0.8-2.42=-2.6431$; $g_2=\ln 0.2-1.62=-3.2294$. $g_1>g_2$.
• Final answer: Threshold $2.347$; $x=2.2\to w_1$ (although $2.2>2$, the midpoint).

Key lesson

Plain minimum distance is only the equal-prior special case.

Example 5 — Very Hard · When Euclid is wrong

• Problem: Common covariance $\Sigma =\mathrm{diag}(9,1)$, equal priors, ${\vec{\mu }}_1=(0,0)$, ${\vec{\mu }}_2=(3,3)$, $\vec{X}=(0,2)$. Classify by the Euclidean minimum-distance rule and by the Bayes (Mahalanobis) rule.
• Asked: Two decisions.
• Concept: Minimum distance requires $\Sigma =I$.
• Approach: Compute both distances.
• Solution: Euclid: $\Vert \vec{X}-{\vec{\mu }}_1{\Vert }^2=4$; $\Vert \vec{X}-{\vec{\mu }}_2{\Vert }^2=9+1=10$ ⇒ $w_1$. Mahalanobis with ${\Sigma }^{-1}=\mathrm{diag}(\frac{1}{9},1)$: $d_1^2=0+4=4$; $\vec{X}-{\vec{\mu }}_2=(-3,-1)$: $d_2^2=\frac{9}{9}+1=2$. $2<4$ ⇒ $w_2$.
• Final answer: Euclidean → $w_1$; Bayes → $w_2$.

Python check

Si = np.diag([1/9, 1]); X = np.array([0, 2]); m1 = np.array([0, 0]); m2 = np.array([3, 3])
mah = lambda d: d @ Si @ d
print(mah(X - m1), mah(X - m2))                           # 4.0  2.0  -> class 2

Key lesson

Features with large variance (here $x_1$) must be discounted; ignoring $\Sigma$ gives the wrong answer.

Common mistakes

• Using it with unequal priors or non-identity covariance.
• Mixing up the minimum-distance rule with kNN (it uses means, kNN uses stored points).

Exam traps

• Needs three assumptions: Gaussian, ${\Sigma }_i=I$, equal priors.

Connections: C14, C18, k-means (C36; the assignment step = minimum distance to centroids).

Mastery checklist

• Derive the rule from Bayes.
• Write the boundary as a hyperplane.
• State when Euclidean distance is wrong.

---

C18. Linear Discriminant Function (Gaussian, Equal Covariance)

Intuition

With two Gaussian classes sharing the same covariance, the quadratic pieces of the log-posteriors cancel, leaving a straight-line (hyperplane) boundary.

Derivation (lecture, with all steps)

$f_i=N({\vec{\mu }}_i,\Sigma )$, $i=1,2$. Decide $w_1$ iff $p_1{f}_1\ge p_2{f}_2$. Taking logs (the constant $\frac{1}{(\sqrt{2\pi }{)}^m|\Sigma {|}^{1/2}}$ cancels): $\ln p_1-\frac{1}{2}(\vec{X}-{\vec{\mu }}_1{)}^T{\Sigma }^{-1}(\vec{X}-{\vec{\mu }}_1)\ge \ln p_2-\frac{1}{2}(\vec{X}-{\vec{\mu }}_2{)}^T{\Sigma }^{-1}(\vec{X}-{\vec{\mu }}_2).$ Expand: $-\frac{1}{2}[{\vec{X}}^T{\Sigma }^{-1}\vec{X}-2{\vec{X}}^T{\Sigma }^{-1}{\vec{\mu }}_i+{\vec{\mu }}_i^T{\Sigma }^{-1}{\vec{\mu }}_i]$ (using ${\vec{X}}^T{\Sigma }^{-1}{\vec{\mu }}_i={\vec{\mu }}_i^T{\Sigma }^{-1}\vec{X}$, both scalars, $\Sigma$ symmetric). The term $-\frac{1}{2}{\vec{X}}^T{\Sigma }^{-1}\vec{X}$ appears on both sides and cancels. Rearranging, $\ln \frac{p_1}{p_2}\ge {\vec{X}}^T{\Sigma }^{-1}({\vec{\mu }}_2-{\vec{\mu }}_1)+\frac{{\vec{\mu }}_1^T{\Sigma }^{-1}{\vec{\mu }}_1-{\vec{\mu }}_2^T{\Sigma }^{-1}{\vec{\mu }}_2}{2}.$ Equivalently, define $g(\vec{X})={\vec{w}}^T\vec{X}+w_0,\vec{w}={\Sigma }^{-1}({\vec{\mu }}_1-{\vec{\mu }}_2),w_0=-\frac{1}{2}({\vec{\mu }}_1^T{\Sigma }^{-1}{\vec{\mu }}_1-{\vec{\mu }}_2^T{\Sigma }^{-1}{\vec{\mu }}_2)+\ln \frac{p_1}{p_2};$ decide $w_1$ iff $g\ge 0$.

Python helper for the checks in this section

def ldf(mu1, mu2, Sigma, p1=.5, p2=.5):
    Si = np.linalg.inv(Sigma); mu1, mu2 = map(np.asarray, (mu1, mu2))
    w = Si @ (mu1 - mu2)
    w0 = -0.5 * (mu1 @ Si @ mu1 - mu2 @ Si @ mu2) + np.log(p1 / p2)
    return w, w0                       # decide class 1 iff w @ x + w0 >= 0

Key insights

• The general Bayes boundary $p_1{f}_1=p_2{f}_2$ is quadratic; it becomes linear iff ${\Sigma }_1={\Sigma }_2$.
• The normal $\vec{w}={\Sigma }^{-1}({\vec{\mu }}_1-{\vec{\mu }}_2)$ is generally not parallel to ${\vec{\mu }}_1-{\vec{\mu }}_2$.
• Priors only shift the intercept.

Worked examples

Example 1 — Very Easy · Identity covariance

• Problem: $\Sigma =I$, ${\vec{\mu }}_1=(0,0),{\vec{\mu }}_2=(2,2)$, equal priors. Find $g$.
• Asked: $g(\vec{X})$.
• Concept: LDF formula.
• Approach: $\vec{w}={\vec{\mu }}_1-{\vec{\mu }}_2$.
• Solution: $\vec{w}=(-2,-2)$; ${\vec{\mu }}_1^T{\vec{\mu }}_1=0$, ${\vec{\mu }}_2^T{\vec{\mu }}_2=8$; $w_0=-\frac{1}{2}(0-8)=4$. $g=-2x_1-2x_2+4$; boundary $x_1+x_2=2$.
• Final answer: $g=-2x_1-2x_2+4$; $w_1$ iff $x_1+x_2\le 2$.

Key lesson

With $\Sigma =I$ this is the perpendicular bisector (C17).

Example 2 — Easy · Diagonal covariance

• Problem: $\Sigma =\mathrm{diag}(2,1)$, ${\vec{\mu }}_1=(1,1)$, ${\vec{\mu }}_2=(3,0)$, equal priors. Find $g$ and classify $(1,2)$ and $(3,1)$.
• Asked: $g$ and two decisions.
• Concept: General LDF.
• Approach: ${\Sigma }^{-1}=\mathrm{diag}(0.5,1)$.
• Solution: $\vec{w}={\Sigma }^{-1}(-2,1)=(-1,1)$. $a_1={\vec{\mu }}_1^T{\Sigma }^{-1}{\vec{\mu }}_1=1.5$; $a_2=9(0.5)=4.5$. $w_0=-\frac{1}{2}(1.5-4.5)=1.5$. $g=-x_1+x_2+1.5$. $g(1,2)=2.5>0\Rightarrow w_1$. $g(3,1)=-0.5<0\Rightarrow w_2$.
• Final answer: $g=-x_1+x_2+1.5$; $(1,2)\to w_1$, $(3,1)\to w_2$.

Python check

w, w0 = ldf([1, 1], [3, 0], np.diag([2, 1]))
print(w, w0, w @ [1, 2] + w0, w @ [3, 1] + w0)            # [-1. 1.]  1.5  2.5  -0.5

Key lesson

Plug into $g$; the sign decides.

Example 3 — Moderate · A prior moves the line

• Problem: Same as Example 2 but priors $0.9,0.1$. How does the boundary move? Reclassify $(3,1)$.
• Asked: New intercept, decision.
• Concept: The prior shifts $w_0$.
• Approach: Add $\ln (p_1/p_2)$.
• Solution: $\ln 9=2.1972$. $g=-x_1+x_2+3.6972$. $g(3,1)=1.6972>0\Rightarrow w_1$.
• Final answer: $(3,1)$ flips to $w_1$.

Python check

w, w0 = ldf([1, 1], [3, 0], np.diag([2, 1]), .9, .1)
print(w0, w @ [3, 1] + w0)                                # 3.6972  1.6972

Key lesson

The boundary translates parallel to itself.

Example 4 — Hard · Unequal variances give a parabola

• Problem: $f_1=N(0,1)$, $f_2=N(2,4)$ (variance 4), equal priors. Show the boundary is quadratic and find the decision region of $w_1$.
• Asked: Boundary roots.
• Concept: Unequal covariance ⇒ quadratic.
• Approach: Log-likelihood difference.
• Solution: $g=\ln f_1-\ln f_2=\frac{1}{2}\ln 4-\frac{x^2}{2}+\frac{(x-2{)}^2}{8}=1.1931-0.5x-0.375x^2$. Roots: $0.375x^2+0.5x-1.1931=0\Rightarrow x=\frac{-0.5\pm 1.4282}{0.75}$, i.e. $x=1.2376$ or $x=-2.5709$. $g>0$ between the roots (e.g. $g(0)=1.19$).
• Final answer: $w_1$ iff $-2.571\le x\le 1.238$; $w_2$ elsewhere.

Python check

print(np.roots([0.375, 0.5, -(np.log(2) + 0.5)]))         # roots of 0.375x² + 0.5x − 1.1931  →  1.2376  -2.5709

Key lesson

The $x^2$ coefficient is $-\frac{1}{2}({\sigma }_1^{-2}-{\sigma }_2^{-2})\ne 0$.

Example 5 — Very Hard · Correlated features tilt the line

• Problem: $\Sigma =\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$, ${\vec{\mu }}_1=(0,0)$, ${\vec{\mu }}_2=(2,0)$, equal priors. (a) Find the boundary line. (b) Is it the perpendicular bisector of the means? (c) Classify $(1.1,1)$ with both the LDF and Euclidean nearest mean.
• Asked: Line, comparison, two decisions.
• Concept: $\vec{w}={\Sigma }^{-1}\Delta \vec{\mu }$ differs from $\Delta \vec{\mu }$.
• Approach: Invert $\Sigma$.
• Solution: ${\Sigma }^{-1}=\frac{1}{3}\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)$. ${\vec{\mu }}_1-{\vec{\mu }}_2=(-2,0)$ ⇒ $\vec{w}=(-\frac{4}{3},\frac{2}{3})$. The midpoint $(1,0)$ lies on the boundary: $g(\vec{X})=-\frac{4}{3}(x_1-1)+\frac{2}{3}{x}_2$. Boundary: $x_2=2(x_1-1)$. (b) The perpendicular bisector is the vertical line $x_1=1$; slope $2\ne \infty$ ⇒ not the bisector. (c) $g(1.1,1)=0.5333>0\Rightarrow w_1$. Euclid: $d_1^2=2.21$, $d_2^2=1.81\Rightarrow w_2$.
• Final answer: Boundary $x_2=2(x_1-1)$; LDF → $w_1$, Euclid → $w_2$.

Python check

w, w0 = ldf([0, 0], [2, 0], np.array([[2, 1], [1, 2]]))
print(w, w0, w @ [1.1, 1] + w0)                           # [-1.333  0.667]  1.333  0.5333

Key lesson

Correlated features tilt the boundary; ignoring $\Sigma$ misclassifies points near it.

Common mistakes

• Dropping the $\ln (p_1/p_2)$ term.
• Sign errors in $\vec{w}$.

Exam traps

• “Quadratic in $\vec{X}$” for the general log-likelihood but “linear” after cancellation with equal $\Sigma$.
• A linear boundary needs Gaussians, two classes, same covariance.

Connections: C14, C17, logistic regression (C27: also linear), SVM (C30).

Mastery checklist

• Derive $g$ step by step.
• Explain why the quadratic term cancels.
• Compute the tilt due to ${\Sigma }^{-1}$.

---

C19. Naive Bayes Classifier (Conditional Independence, MAP, Log-Space)

Intuition

Estimating $p(x_1,\dots ,x_m|w)$ directly needs exponentially many numbers. Naive Bayes assumes features are independent given the class, so the joint becomes a product of simple one-feature distributions — cheap to estimate, surprisingly effective.

flowchart TD
    W((class w)) --> X1[x₁]
    W --> X2[x₂]
    W --> X3[x₃]
    W --> Xm[x_m]

Given the class, the features do not talk to each other — only the class points to them.

Formal derivation (lecture)

$p(w_k|\vec{X})\propto p(w_k,\vec{X})=p(x_1|x_2,\dots ,x_m,w_k)p(x_2|x_3,\dots ,x_m,w_k)\cdots p(x_m|w_k)p(w_k)$ (chain rule). Naive assumption: $p(x_i|x_{i+1},\dots ,x_m,w_k)=p(x_i|w_k)$. Therefore $p(w_k|\vec{X})\propto p(w_k){\prod }_{i=1}^{m}p(x_i|w_k),w_{map}=\arg {\max }_{k}p(w_k){\prod }_{i=1}^{m}p(x_i|w_k).$ Log version (avoids floating-point underflow): $w_{map}=\arg {\max }_k[\ln p(w_k)+{\sum }_{i=1}^m\ln p(x_i|w_k)].$ Priors: $p(w_k)=\frac{\#\text{samples in }{w}_k}{\text{total}}$.

Key insights

• Parameters: with $m$ binary features and $c$ classes: $cm+(c-1)$ vs $c(2^m-1)+(c-1)$ for the full joint.
• Naive Bayes is a generative classifier (C29).
• The ranking of classes can be right even if the probabilities are miscalibrated.

Worked examples

Example 1 — Very Easy · Estimates from counts

• Problem: From the weather data (Module 1) find $p(Y),p(N)$, $p(\text{Sunny}|Y)$, $p(\text{Sunny}|N)$.
• Asked: Four numbers.
• Concept: Estimates from counts.
• Approach: Count.
• Solution: $p(Y)=\frac{9}{14}$, $p(N)=\frac{5}{14}$. Sunny rows: 1,2,8 (N), 9,11 (Y) ⇒ $p(S|Y)=\frac{2}{9}$, $p(S|N)=\frac{3}{5}$.
• Final answer: $0.643,0.357,0.222,0.6$.

Key lesson

All parameters are simple relative frequencies.

Example 2 — Easy · Classify a day

• Problem: Classify $\vec{X}=(\text{Sunny},\text{Cool},\text{High},\text{True})$ with Naive Bayes.
• Asked: Class and posterior.
• Concept: MAP with independence.
• Approach: Needed counts: Yes: Sunny $2/9$, Cool $3/9$, High $3/9$, True $3/9$; No: Sunny $3/5$, Cool $1/5$, High $4/5$, True $3/5$.
• Solution: $Y:\frac{9}{14}\cdot \frac{2}{9}\cdot \frac{3}{9}\cdot \frac{3}{9}\cdot \frac{3}{9}=0.005291$. $N:\frac{5}{14}\cdot \frac{3}{5}\cdot \frac{1}{5}\cdot \frac{4}{5}\cdot \frac{3}{5}=0.020571$. Normalise: $P(N|\vec{X})=\frac{0.020571}{0.025862}=0.795$.
• Final answer: No (posterior $\approx 0.80$).

Python check

yes = 9/14 * 2/9 * 3/9 * 3/9 * 3/9; no = 5/14 * 3/5 * 1/5 * 4/5 * 3/5
print(yes, no, no / (yes + no))                           # 0.005291  0.020571  0.7954

Key lesson

The unnormalised scores suffice for the decision; normalise only if you need a probability.

Example 3 — Moderate · 200 tiny probabilities

• Problem: A model has $m=200$ features; every $p(x_i|w_1)=0.01$ and every $p(x_i|w_2)=0.02$; equal priors. Why does the product fail, and how do logs fix it?
• Asked: Failure and fix.
• Concept: Underflow.
• Approach: Magnitudes.
• Solution: $0.01^{200}=10^{-400}$ and $0.02^{200}\approx 10^{-340}$. Double precision underflows below $\approx 10^{-308}$ (denormals to $\approx 5\times 10^{-324}$), so both products become $0$ ⇒ tie ⇒ arbitrary. Logs: $\ln 0.5+200\ln 0.01=-921.73$; $\ln 0.5+200\ln 0.02=-783.10$.
• Final answer: Class 2 (score $-783.1>-921.7$); only the log computation sees it.

Python check

print(0.5 * 0.01**200, 0.5 * 0.02**200)                   # 0.0  0.0   (underflow)
print(np.log(.5) + 200*np.log(.01), np.log(.5) + 200*np.log(.02))   # -921.73  -783.10

Key lesson

Sum logs; never multiply many small probabilities.

Example 4 — Hard · A duplicated feature double-counts

• Problem: Equal priors. A feature $f$ has $p(f|w_1)=0.6$, $p(f|w_2)=0.2$. The same feature accidentally appears twice (perfectly correlated). Compare the true posterior of $w_1$ with Naive Bayes’s.
• Asked: Two posteriors.
• Concept: Violated independence double-counts evidence.
• Approach: Likelihood ratio.
• Solution: True: $P(w_1|f)=\frac{0.6}{0.8}=0.75$. NB with two copies: $\frac{0.36}{0.36+0.04}=0.90$.
• Final answer: $0.75$ vs NB’s $0.90$.

Key lesson

NB is over-confident when features are correlated, but the argmax is unchanged (still $w_1$).

Example 5 — Very Hard · Counting parameters

• Problem: (a) Count free parameters for $c=2$ classes with $m=10$ binary features, full joint vs Naive Bayes. (b) Prove NB’s MAP rule equals the Bayes rule when the independence assumption holds.
• Asked: Counts and proof.
• Concept: Complexity; relation to Bayes.
• Approach: Count; substitute.
• Solution: (a) Full: each class has a joint over $2^{10}=1024$ cells with $1023$ free parameters ⇒ $2046$, plus $1$ prior ⇒ $2047$. NB: $2\times 10=20$, plus 1 prior ⇒ $21$. (b) The Bayes rule maximises $p(w_k)p(\vec{X}|w_k)$. If features are conditionally independent, $p(\vec{X}|w_k)={\prod }_{i}p(x_i|w_k)$ exactly; substituting gives the NB rule — identical. When independence is false, NB maximises a different (misspecified) quantity.
• Final answer: $2047$ vs $21$ parameters; NB = Bayes under conditional independence.

Key lesson

The “naive” assumption trades bias for a huge reduction in parameters and variance.

Common mistakes

• Assuming unconditional independence (it is conditional on the class).
• Multiplying many probabilities instead of summing logs.

Exam traps

• Zero counts kill the product → smoothing (C21).
• $p(\vec{X})$ is dropped; outputs are unnormalised.

Connections: Bayes (C14), Gaussian / multinomial / Bernoulli variants (C20–C22), logistic regression (C27 / C29).

Mastery checklist

• Derive the product rule from the chain rule.
• Classify with logs.
• Explain over-confidence.

---

C20. Gaussian Naive Bayes (Continuous Features)

Intuition

For numeric features, model each feature within each class as a bell curve, with its own mean and variance estimated from the training data.

Formal definition

$p(x_i|w_k)=\frac{1}{\sqrt{2\pi {\sigma }_{ik}^2}}\exp \{-\frac{(x_i-{\mu }_{ik}{)}^2}{2{\sigma }_{ik}^2}\},$ with ${\mu }_{ik},{\sigma }_{ik}^2$ the sample mean and variance of feature $i$ among class-$k$ samples. Log form: $\ln p(x_i|w_k)=-\frac{1}{2}\ln (2\pi {\sigma }_{ik}^2)-\frac{(x_i-{\mu }_{ik}{)}^2}{2{\sigma }_{ik}^2}.$ (The maximum-likelihood variance divides by $n_k$; an unbiased estimate divides by $n_k-1$.)

Key insights

• If all ${\sigma }_{ik}^2$ are equal across classes, the $\ln \sigma$ terms cancel; the rule becomes a (weighted) nearest-mean rule.
• Unequal variances ⇒ quadratic boundary (the wide class wins in the tails).
• A zero variance (constant feature in a class) breaks the formula — add a small floor.

Worked examples

Example 1 — Very Easy · Peak height

• Problem: Density of $N(\mu ,{\sigma }^2=4)$ at $x=\mu$.
• Asked: $p$.
• Concept: Gaussian pdf.
• Approach: The exponent is $0$.
• Solution: $\frac{1}{\sqrt{2\pi \cdot 4}}=\frac{1}{5.013}=0.1995$.
• Final answer: $0.1995$.

Key lesson

Peak height $=1/(\sigma \sqrt{2\pi })$.

Example 2 — Easy · Estimating parameters

• Problem: Class A values of a feature: $1,2,3$. Estimate $\mu ,{\sigma }^2$ (MLE).
• Asked: Parameters.
• Concept: Estimation.
• Approach: Mean, mean squared deviation.
• Solution: $\mu =2$; ${\sigma }^2=\frac{1+0+1}{3}=0.6667$ (unbiased: $1.0$).
• Final answer: $\mu =2$, ${\sigma }^2=0.667$ (MLE).

Key lesson

State which variance estimator you use.

Example 3 — Moderate · One feature, equal variance

• Problem: Class A: $\mu =2,{\sigma }^2=\frac{2}{3}$; class B: $\mu =7,{\sigma }^2=\frac{2}{3}$; equal priors. Classify $x=4$.
• Asked: Class.
• Concept: 1-feature Gaussian NB.
• Approach: Log-scores.
• Solution: Same $\sigma$ ⇒ compare $\frac{(x-\mu {)}^2}{2{\sigma }^2}$: A: $\frac{4}{1.3333}=3.0$; B: $\frac{9}{1.3333}=6.75$. Smaller ⇒ A.
• Final answer: A.

Key lesson

With equal variances it is nearest-mean.

Example 4 — Hard · Two features add in log space

• Problem: A: $x_1\sim N(2,\frac{2}{3})$, $x_2\sim N(3,\frac{2}{3})$. B: $x_1\sim N(7,\frac{2}{3})$, $x_2\sim N(2,\frac{2}{3})$. Equal priors; classify $(4,2.5)$.
• Asked: Class and log-ratio.
• Concept: Sum of per-feature logs.
• Approach: Constants cancel (equal variances).
• Solution: A: $-\frac{4}{1.3333}-\frac{0.25}{1.3333}=-3.1875$. B: $-\frac{9}{1.3333}-\frac{0.25}{1.3333}=-6.9375$. Difference $3.75$ in favour of A.
• Final answer: A.

Key lesson

Features contribute additively in log space.

Example 5 — Very Hard · Standard deviations, not raw distance

• Problem: Equal priors. A: $x\sim N(0,1)$; B: $x\sim N(3,9)$. Classify $x=-3$. Compare with the nearest-mean answer and explain.
• Asked: Class and explanation.
• Concept: Unequal-variance effect.
• Approach: Full log-likelihoods.
• Solution: $\ln p(x|A)=-0.9189-4.5=-5.4189$. $\ln p(x|B)=-\frac{1}{2}\ln (2\pi \cdot 9)-\frac{36}{18}=-0.9189-1.0986-2.0=-4.0175$. B is larger. Nearest mean: $|-3-0|=3$ vs $|-3-3|=6$ ⇒ A.
• Final answer: Gaussian NB: B; nearest-mean: A.

Python check

print(norm.logpdf(-3, 0, 1), norm.logpdf(-3, 3, 3))       # -5.4189  -4.0175

Key lesson

Distance measured in standard deviations ($3{\sigma }_A$ vs $2{\sigma }_B$) matters, not raw distance.

Common mistakes

• Forgetting the $\ln \sigma$ term when variances differ.
• Zero variance → division by zero.

Exam traps

• Gaussian NB for continuous features; multinomial / Bernoulli for discrete (counts / binary).

Connections: C14, C19, C21–C22.

Mastery checklist

• Estimate ${\mu }_{ik},{\sigma }_{ik}^2$.
• Classify with log-scores.
• Explain the unequal-variance effect.

---

C21. Multinomial Naive Bayes and Laplace (Add-One) Smoothing

Intuition

For text, a feature is a word and its value is how often it occurs. A class is summarised as a “bag” of its words; $p(\text{word}|\text{class})$ is the word’s share of that class’s word-tokens. A word never seen in a class would zero out the whole product — so we pretend we saw every word once.

Formal definition

Let $F_{ik}$ = total frequency of term $i$ in all class-$k$ documents; $m$ = vocabulary size. $p(x_i|w_k)=\frac{F_{ik}}{{\sum }_{j=1}^m{F}_{jk}}\text{(raw)};p(x_i|w_k)=\frac{F_{ik}+1}{{\sum }_{j=1}^m{F}_{jk}+m}\text{(Laplace)}.$ Test document: each occurrence of a term contributes one factor.

Derivation (Laplace form)

Add $1$ to every one of the $m$ counts: numerator $F_{ik}+1$; denominator ${\sum }_j(F_{jk}+1)={\sum }_j{F}_{jk}+m$. The smoothed probabilities sum to $1$: ${\sum }_i\frac{F_{ik}+1}{{\sum }_j{F}_{jk}+m}=\frac{{\sum }_i{F}_{ik}+m}{{\sum }_j{F}_{jk}+m}=1$. ∎

Key insights

• Smoothing shrinks estimates toward the uniform value $1/m$; strongest for small classes.
• Repeated words in a test document are counted repeatedly (multinomial) — unlike Bernoulli (C22).

Worked example corpus (used in all five)

Class $c$ (3 docs): “Chinese Beijing Chinese”, “Chinese Chinese Shanghai”, “Chinese Macao”. Class $j$ (1 doc): “Tokyo Japan Chinese”. Vocabulary $=\{$Chinese, Beijing, Shanghai, Macao, Tokyo, Japan$\}$, $m=6$. Test: “Chinese Chinese Chinese Tokyo Japan”.

Counts. Class $c$: Chinese 5, Beijing 1, Shanghai 1, Macao 1, Tokyo 0, Japan 0 → total 8. Class $j$: Chinese 1, Tokyo 1, Japan 1, others 0 → total 3. Priors $p(c)=\frac{3}{4},p(j)=\frac{1}{4}$.

Python helper for this section and C22

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB, BernoulliNB
docs = ["Chinese Beijing Chinese", "Chinese Chinese Shanghai", "Chinese Macao", "Tokyo Japan Chinese"]
labels = ["c", "c", "c", "j"]
cv = CountVectorizer(lowercase=False); X = cv.fit_transform(docs)
test = cv.transform(["Chinese Chinese Chinese Tokyo Japan"])

Example 1 — Very Easy · The zero-frequency problem

• Problem: Raw $p(\text{Tokyo}|c)$; what happens to a test document containing Tokyo?
• Asked: Value and consequence.
• Concept: Zero-frequency problem.
• Approach: $F/\sum F$.
• Solution: $\frac{0}{8}=0$. Any product containing it is $0$.
• Final answer: $0$; class $c$ would be impossible for that document.

Key lesson

One unseen word vetoes the class.

Example 2 — Easy · Smoothed estimates

• Problem: Smoothed $p(\text{Chinese}|c)$, $p(\text{Tokyo}|c)$, $p(\text{Chinese}|j)$, $p(\text{Tokyo}|j)$.
• Asked: Four numbers.
• Concept: Laplace.
• Approach: $\frac{F+1}{\text{total}+6}$.
• Solution: $c$: total $8$, denominator $14$: Chinese $\frac{6}{14}$, Tokyo $\frac{1}{14}$. $j$: total $3$, denominator $9$: Chinese $\frac{2}{9}$, Tokyo $\frac{2}{9}$.
• Final answer: $0.4286,0.0714,0.2222,0.2222$.

Key lesson

The smaller class gets more smoothing mass per word.

Example 3 — Moderate · Classify the test document

• Problem: Classify the test document.
• Asked: Class.
• Concept: Multinomial NB.
• Approach: Terms: Chinese ×3, Tokyo, Japan.
• Solution: $c$: $\frac{3}{4}{\left(\frac{6}{14}\right)}^3{\left(\frac{1}{14}\right)}^2=3.01\times 10^{-4}$. $j$: $\frac{1}{4}{\left(\frac{2}{9}\right)}^5=1.35\times 10^{-4}$. Normalised $P(c|d)=0.690$.
• Final answer: Class $c$.

Python check

m = MultinomialNB(alpha=1).fit(X, labels)
print(cv.get_feature_names_out(), m.classes_, m.predict_proba(test))   # P(c|d)=0.6898

Key lesson

“Chinese” appears three times and is very probable in $c$, outweighing Tokyo / Japan.

Example 4 — Hard · Logs, and what happens without smoothing

• Problem: Redo Example 3 in log space and verify; then compute what the decision would be if smoothing were not used.
• Asked: Log scores; unsmoothed decision.
• Concept: Logs and the zero problem.
• Approach: $\ln$.
• Solution: $c$: $\ln 0.75+3\ln \frac{6}{14}+2\ln \frac{1}{14}=-8.1077$. $j$: $\ln 0.25+5\ln \frac{2}{9}=-8.9067$. $c>j$ ✓ ($e^{-8.1077}=3.01\times 10^{-4}$ ✓). Unsmoothed: $p(\text{Tokyo}|c)=0$ ⇒ score${}_c=0$; $j$ (with $p(\text{Chinese}|j)=p(\text{Tokyo}|j)=p(\text{Japan}|j)=\frac{1}{3}$): $\frac{1}{4}{\left(\frac{1}{3}\right)}^5=\frac{1}{972}=0.00103>0$ ⇒ $j$.
• Final answer: Smoothed → $c$; unsmoothed → $j$ (a spurious veto).

Key lesson

Smoothing can change the decision; unsmoothed zeros are not evidence.

Example 5 — Very Hard · Properties of Laplace smoothing

• Problem: (a) Prove the smoothed class-$k$ probabilities sum to $1$ for $m$ terms. (b) A new class $k^{\prime }$ has zero training tokens. What are its probabilities? (c) How would the Example 3 posterior change if a seventh vocabulary word “Osaka” (never seen) is added so $m=7$?
• Asked: Proof and two computations.
• Concept: Laplace’s properties.
• Approach: Direct.
• Solution: (a) shown in the Derivation. (b) $\frac{0+1}{0+m}=\frac{1}{m}$ for every term — uniform. (c) $c$ denominator $8+7=15$: Chinese $\frac{6}{15}$, Tokyo $\frac{1}{15}$, Japan $\frac{1}{15}$; $j$ denominator $3+7=10$: each $\frac{2}{10}$. Scores: $c$: $0.75(\frac{6}{15}{)}^3(\frac{1}{15}{)}^2=2.133\times 10^{-4}$; $j$: $0.25(0.2{)}^5=8.0\times 10^{-5}$. $P(c|d)=\frac{2.133}{2.133+0.8}=0.727$.
• Final answer: Uniform $\frac{1}{m}$ for an empty class; with $m=7$, class $c$ still wins, posterior $0.727$ (up from $0.690$).

Key lesson

Vocabulary size $m$ appears in the denominator — it controls how much probability mass goes to unseen words.

Common mistakes

• Adding $1$ only to zero counts.
• Using the number of documents instead of the vocabulary size $m$ in the denominator.
• Forgetting that repeated words count repeatedly.

Exam traps

• Denominator: ${\sum }_j{F}_{jk}+m$ (Lecture eq. 8.9).
• The ratio of probabilities, not their absolute values, determines the class.

Connections: C19, C22 (Bernoulli), text classification.

Mastery checklist

• Apply Laplace smoothing.
• Do the full Chinese / Tokyo example.
• Explain why zeros are dangerous.

---

C22. Bernoulli Naive Bayes

Intuition

Record only whether a word occurs in a document (yes / no), ignoring how often. Each word is a coin flip per document, with a class-specific head probability.

Formal definition

$p(x_i|w_k)$ = fraction of class-$k$ documents containing term $i$. With smoothing (standard form): $p(t_i|w_k)=\frac{N_{ik}+1}{N_k+2}$, where $N_{ik}$ = number of class-$k$ docs containing $t_i$, $N_k$ = class-$k$ document count. A test document $d$ is scored by $p(w_k){\prod }_{i\in \text{present}}p(t_i|w_k){\prod }_{i\in \text{absent}}(1-p(t_i|w_k))$ (the full Bernoulli model also penalises absent words). The lecture notes that Bernoulli uses only binary occurrence information and “makes mistakes on long documents”, so it is used for short texts.

Key insights

• Multinomial counts repeats; Bernoulli does not.
• Absent terms contribute evidence in the Bernoulli model.
• The smoothing form $(N+1)/(N_k+2)$ is the two-outcome Laplace analogue.

Worked example corpus (same as C21)

Class $c$ docs: $\{$Chinese, Beijing$\}$, $\{$Chinese, Shanghai$\}$, $\{$Chinese, Macao$\}$; class $j$ doc: $\{$Chinese, Tokyo, Japan$\}$. Test doc (presence): $\{$Chinese, Tokyo, Japan$\}$.

Example 1 — Very Easy · Document frequencies

• Problem: Raw $p(\text{Chinese}|c)$ and $p(\text{Beijing}|c)$.
• Asked: Two fractions.
• Concept: Document-frequency estimate.
• Approach: Docs containing the term / class docs.
• Solution: Chinese in 3 of 3 ⇒ $1$. Beijing in 1 of 3 ⇒ $\frac{1}{3}$.
• Final answer: $1,0.333$.

Key lesson

Probabilities are per-document, not per-token.

Example 2 — Easy · Smoothed table

• Problem: Smoothed $p(t|c)$ and $p(t|j)$ for all six terms.
• Asked: Table.
• Concept: $(N+1)/(N_k+2)$.
• Approach: $N_c=3$ ⇒ denominator $5$; $N_j=1$ ⇒ denominator $3$.
• Solution:

term	$p(t\mid c)$	$p(t\mid j)$
Chinese	4/5	2/3
Beijing, Shanghai, Macao	2/5 each	1/3 each
Tokyo, Japan	1/5 each	2/3 each

• Final answer: As tabulated.

Key lesson

Every term probability lies strictly in $(0,1)$ — absent-term factors never vanish.

Example 3 — Moderate · Presence-only score

• Problem: Score the test document, using only the present terms.
• Asked: Class (partial model).
• Concept: Presence-only product.
• Approach: ${\prod }_{\text{present}}$.
• Solution: $c$: $0.75\cdot \frac{4}{5}\cdot \frac{1}{5}\cdot \frac{1}{5}=0.024$. $j$: $0.25\cdot {\left(\frac{2}{3}\right)}^3=0.0741$.
• Final answer: $j$ under the presence-only version.

Key lesson

Already differs from multinomial ($c$).

Example 4 — Hard · The full Bernoulli model

• Problem: Score the test document with the full Bernoulli model (include absent terms Beijing, Shanghai, Macao).
• Asked: Class and posterior.
• Concept: Full Bernoulli.
• Approach: Multiply $(1-p)$ for the three absent terms.
• Solution: $c$: $0.024\times {\left(\frac{3}{5}\right)}^3=0.005184$. $j$: $0.25{\left(\frac{2}{3}\right)}^3{\left(\frac{2}{3}\right)}^3=0.02195$. $P(j|d)=\frac{0.02195}{0.02195+0.005184}=0.809$.
• Final answer: Class $j$ ($\approx 0.81$).

Python check

b = BernoulliNB(alpha=1, binarize=0).fit(X, labels)       # sklearn's BernoulliNB is the full model
print(b.classes_, b.predict_proba(test))                  # P(j|d) = 0.8089

Key lesson

Absent words push toward $j$ because class $c$ “expects” Beijing / Shanghai / Macao, yet they are missing.

Example 5 — Very Hard · Why the two models disagree

• Problem: The multinomial model (C21 Ex. 3) said $c$; the Bernoulli model says $j$. Explain the discrepancy and say which is appropriate for (a) tweets, (b) 5000-word articles.
• Asked: Reasoned comparison.
• Concept: Counts vs presence.
• Approach: Identify what each model uses.
• Solution: The word “Chinese” appears 3 times in the test text. Multinomial multiplies $p(\text{Chinese}|c)=\frac{6}{14}$ three times, and since $c$ makes “Chinese” very likely it earns a large reward. Bernoulli sees “Chinese present” once; its decisive evidence is Tokyo / Japan present (favouring $j$) and the absence of Beijing / Shanghai / Macao. (a) Tweets are short: presence / absence is informative and Bernoulli works well. (b) In long documents most words occur at least once, so presence saturates; the lecture warns Bernoulli errs on long documents ⇒ multinomial.
• Final answer: Different modelling assumptions ⇒ different predictions; Bernoulli for short texts, multinomial for long.

Key lesson

Choose the model whose generative story matches your data.

Common mistakes

• Ignoring absent terms in the full Bernoulli model.
• Using token counts in Bernoulli.

Exam traps

• “Bernoulli errs on long documents” (lecture).
• Smoothing uses $+2$ in the denominator for Bernoulli (binary event), $+m$ for multinomial.

Connections: C21, C19, C29.

Mastery checklist

• Estimate document-frequency probabilities.
• Include absent terms.
• Contrast with the multinomial model.