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.

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.

---

C14. The Bayes Decision Rule

Intuition

Before seeing data you have 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 the comparison $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

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

Worked examples

Example 1 — Very Easy

• Problem: A spam 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

• 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

• 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.
• Key lesson: Rank by joint, not by prior or likelihood alone.

Example 4 — Hard

• 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: 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$.
• Key lesson: The same data point flips class when priors change.

Example 5 — Very Hard

• 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^{-x^2/2+x^2/8}\ge \frac{1}{2}$ $⟺-\frac{3x^2}{8}\ge -\ln 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$.
• 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

• 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: 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

• 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

• 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 (\frac{1-0}{2})=1-\Phi (0.5)=0.3085$. $P(X<1|w_2)=\Phi (\frac{1-4}{2})=\Phi (-1.5)=0.0668$. $R=\frac{1}{2}(0.3085+0.0668)=0.1877$.
• Final answer: $0.188>0.159$.
• Key lesson: Moving the threshold off the Bayes point strictly increases error.

Example 4 — Hard

• 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$.
• Key lesson: Pushing the error from 5 % to 1 % needs $\approx 41\%$ more separation.

Example 5 — Very Hard

• 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=p_{1}P(X>1.693|w_1)+p_{2}P(X\le 1.693|w_2)=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.8(0.1587)+0.2(0.1587)=0.1587$. (c) $=p_2=0.20$.
• Final answer: $0.112<0.159<0.200$.
• 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 wording “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 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

• 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: Geometric mean exceeds the minimum.

Example 2 — Easy

• 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.3(1.3863)+0.7(2.1972)}=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 can be 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

• 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})$ 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.125\times 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

• 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=\alpha (-0.2231)+(1-\alpha )(-1.6094)-2\alpha (1-\alpha )$. Derivative: $-0.2231+1.6094-2+4\alpha =4\alpha -0.6137=0\Rightarrow {\alpha }^{\ast }=0.1534$. $\ln g({\alpha }^{\ast })=-0.0342-1.3625-0.2597=-1.6564$ ⇒ $g=0.1908$. At $\alpha =0.5$: $\ln g=0.5(-1.8325)-2(0.25)=-1.4163$ ⇒ $0.2426$.
• Final answer: Chernoff $\approx 0.191$ (${\alpha }^{\ast }=0.153$); Bhattacharyya $0.243$; true $0.112$.
• Key lesson: Unequal priors push the optimal $\alpha$ away from $\frac{1}{2}$.

Example 5 — Very Hard

• 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=0.5(1)+0.5(4)=2.5$. $|{\Sigma }_1{|}^{1/2}|{\Sigma }_2{|}^{1/2}=\sqrt{1}\sqrt{4}=2$. Ratio $=1.25$. $I=\frac{1}{2}\ln 1.25=0.1116$. Bound $=\sqrt{0.5\cdot 0.5}{e}^{-0.1116}=0.5(0.8944)=0.4472$.
• Final answer: $R\le 0.447$ (true $0.339$).
• 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$.
• First term vanishes when 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

• 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

• 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=9+1=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

• 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=x_1^2-8x_1+16+x_2^2-4x_2+4\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: 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

• 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}=\frac{{\mu }_1+{\mu }_2}{2}+\frac{{\sigma }^2\ln (p_1/p_2)}{{\mu }_2-{\mu }_1}=2+\frac{\ln 4}{4}=2.3466$. At $x=2.2$: $g_1=\ln 0.8-\frac{4.84}{2}=-0.2231-2.42=-2.6431$; $g_2=\ln 0.2-\frac{(1.8{)}^2}{2}=-1.6094-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

• 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=0+4=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=\frac{0}{9}+\frac{4}{1}=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$.
• 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, 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$.

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

• 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

• 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=0.5+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)=-3+1+1.5=-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$.
• Key lesson: Plug into $g$; sign decides.

Example 3 — Moderate

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

Example 4 — Hard

• 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 1-\frac{x^2}{2}+\frac{1}{2}\ln 4+\frac{(x-2{)}^2}{8}=0.6931-\frac{x^2}{2}+\frac{x^2-4x+4}{8}=1.1931-0.5x-0.375x^2$. Roots: $0.375x^2+0.5x-1.1931=0\Rightarrow x=\frac{-0.5\pm \sqrt{0.25+1.7897}}{0.75}=\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.
• Key lesson: The $x^2$ coefficient is $-\frac{1}{2}({\sigma }_1^{-2}-{\sigma }_2^{-2})\ne 0$.

Example 5 — Very Hard

• 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{1}{3}(-4,2)=(-\frac{4}{3},\frac{2}{3})$. Midpoint $(1,0)$ lies on the boundary (equal priors, $g=0$ there): $g(\vec{X})=-\frac{4}{3}(x_1-1)+\frac{2}{3}{x}_2$. Boundary: $x_2=2(x_1-1)$. (b) Perpendicular bisector is the vertical line $x_1=1$; slope $2\ne \infty$ ⇒ not the bisector. (c) $g(1.1,1)=-\frac{4}{3}(0.1)+\frac{2}{3}=0.5333>0\Rightarrow w_1$. Euclid: $d_1^2=1.21+1=2.21$, $d_2^2=0.81+1=1.81\Rightarrow w_2$.
• Final answer: Boundary $x_2=2(x_1-1)$; LDF → $w_1$, Euclid → $w_2$.
• 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$.
• 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.

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 (avoid 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

• Problem: From the weather data 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

• 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: Cool $3/9$, High $3/9$, True $3/9$; No: 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.6429\times 0.00823=0.005291$. $N:\frac{5}{14}\cdot \frac{3}{5}\cdot \frac{1}{5}\cdot \frac{4}{5}\cdot \frac{3}{5}=0.3571\times 0.0576=0.020571$. Normalise: $P(N|\vec{X})=\frac{0.020571}{0.025862}=0.795$.
• Final answer: No (posterior $\approx 0.80$).
• Key lesson: The unnormalised scores suffice for the decision; normalise only for a probability.

Example 3 — Moderate

• 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}=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=-0.693-921.03=-921.72$; $\ln (0.5)+200\ln 0.02=-0.693-782.45=-783.14$.
• Final answer: Class 2 (score $-783.1>-921.7$); only the log computation sees it.
• Key lesson: Sum logs, never multiply many small probabilities.

Example 4 — Hard

• 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.6+0.2}=0.75$. NB with two copies: $\frac{0.6^2}{0.6^2+0.2^2}=\frac{0.36}{0.40}=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

• 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 ⇒ $2\times 1023=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/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}.$ (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 (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

• Problem: Density of $N(\mu ,{\sigma }^2=4)$ at $x=\mu$.
• Asked: $p$.
• Concept: Gaussian pdf.
• Approach: Exponent $=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

• 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

• 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

• Problem: Two features. 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-2{)}^2}{1.3333}-\frac{(2.5-3{)}^2}{1.3333}=-3.0-0.1875=-3.1875$. B: $-\frac{(4-7{)}^2}{1.3333}-\frac{(2.5-2{)}^2}{1.3333}=-6.75-0.1875=-6.9375$. Difference $3.75$ in favour of A.
• Final answer: A.
• Key lesson: Features contribute additively in log space.

Example 5 — Very Hard

• 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)=-\frac{1}{2}\ln (2\pi )-\frac{9}{2}=-0.9189-4.5=-5.4189$. $\ln p(x|B)=-\frac{1}{2}\ln (2\pi \cdot 9)-\frac{(-3-3{)}^2}{18}=-0.9189-1.0986-2.0=-4.0175$. B larger. Nearest mean: $|-3-0|=3$ vs $|-3-3|=6$ ⇒ A.
• Final answer: Gaussian NB: B; nearest-mean: A.
• Key lesson: Distance 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 examples (training data used in all)

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}$.

Example 1 — Very Easy

• 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

• 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

• 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\frac{1}{14}\cdot \frac{1}{14}=0.75(0.07872)(0.005102)=3.01\times 10^{-4}$. $j$: $\frac{1}{4}{\left(\frac{2}{9}\right)}^3\cdot \frac{2}{9}\cdot \frac{2}{9}=0.25(\frac{2}{9}{)}^5=0.25(5.42\times 10^{-4})=1.35\times 10^{-4}$. Normalised $P(c|d)=0.690$.
• Final answer: Class $c$.
• Key lesson: The word “Chinese” appears three times and is very probable in $c$, outweighing Tokyo/Japan.

Example 4 — Hard

• 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}=-0.2877+3(-0.8473)+2(-2.6391)=-0.2877-2.5419-5.2781=-8.1077$. $j$: $\ln 0.25+5\ln \frac{2}{9}=-1.3863+5(-1.5041)=-1.3863-7.5204=-8.9067$. $c>j$ ✓ ($e^{-8.1077}=3.01\times 10^{-4}$ ✓). Unsmoothed: $p(\text{Tokyo}|c)=0$ ⇒ score${}_c=0$; $j$: $\frac{1}{4}(\frac{1}{3}{)}^5=\frac{1}{4}\cdot \frac{1}{243}\cdot \dots$ with $p(\text{Chinese}|j)=\frac{1}{3}$: $\frac{1}{4}\cdot (\frac{1}{3}{)}^3\cdot \frac{1}{3}\cdot \frac{1}{3}=\frac{1}{4}\cdot \frac{1}{243}=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

• 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 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=0.75(0.064)(0.004444)=2.133\times 10^{-4}$; $j$: $0.25(0.2{)}^5=0.25(3.2\times 10^{-4})=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 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 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.
• Smoothing form $(N+1)/(N_k+2)$ is the two-outcome Laplace analogue.

Worked examples (same corpus 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

• 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

• 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: $c$: Chinese $\frac{4}{5}$; Beijing, Shanghai, Macao $\frac{2}{5}$ each; Tokyo, Japan $\frac{1}{5}$ each. $j$: Chinese, Tokyo, Japan $\frac{2}{3}$ each; Beijing, Shanghai, Macao $\frac{1}{3}$ each.
• Final answer: As tabulated.
• Key lesson: Probabilities for each term lie strictly in $(0,1)$ — absent-term factors never vanish.

Example 3 — Moderate

• 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.75(0.032)=0.024$. $j$: $0.25\cdot {\left(\frac{2}{3}\right)}^3=0.25(0.2963)=0.0741$.
• Final answer: $j$ under the presence-only version.
• Key lesson: Already differs from multinomial ($c$).

Example 4 — Hard

• 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.75\cdot \frac{4}{5}\cdot \frac{1}{5}\cdot \frac{1}{5}\cdot {\left(1-\frac{2}{5}\right)}^3=0.024\times 0.216=0.005184$. $j$: $0.25\cdot {\left(\frac{2}{3}\right)}^3{\left(1-\frac{1}{3}\right)}^3=0.25\times 0.2963\times 0.2963=0.02195$. $P(j|d)=\frac{0.02195}{0.02195+0.005184}=0.809$.
• Final answer: Class $j$ ($\approx 0.81$).
• Key lesson: Absent words push toward $j$ because class $c$ “expects” Beijing/Shanghai/Macao yet they are missing.

Example 5 — Very Hard

• 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, and 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, 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.