03 Text Classification - Chunk 01 (s.1-30)

Overview

This chunk opens the Text Classification lecture (slides adapted from Zhao Rui & Chen Zhenghua of NTU and Josh Starmer of StatQuest) (s.1). It recaps document representation (Document-Term Matrix, TF, TF-IDF, LSA, NMF, LDA) and announces the move to classification, starting with Naive Bayes (s.2). A “Pre Study” block (s.3-12) then revises the probability needed: Concept - Probability Basics, Concept - Conditional Probability, Concept - Density Estimation, Concept - Argmax and Concept - Maximum Likelihood Estimation (with a Gaussian example). The “Bayes Theorem” block (s.13-24) introduces Concept - Bayes Rule, the evolution of posteriors, Concept - Maximum A Posteriori and MAP vs MLE, classification with Bayes rule and the Concept - Curse of Dimensionality, then the Concept - Conditional Independence assumption that defines Concept - Naive Bayes. The final block (s.25-30) applies Naive Bayes to text: class priors (Concept - Prior Probability), MLE parameter estimation with a “mega-document”, the new-word (zero-probability) problem and Concept - Additive Smoothing.

Detailed notes

1. Title and introduction (s.1-2)

• Title: Text Classification; slides adapted from Zhao Rui & Chen Zhenghua (NTU) and Josh Starmer (StatQuest) (s.1).
• Introduction (s.2):
  • Document representation: methods “we already discussed”: Document-Term Matrix; TF, TF-IDF, etc.; Latent Semantic Analysis (LSA).
  • Other methods: Non-negative Matrix Factorization (NMF); Latent Dirichlet Allocation (LDA); deep-learning-based models (to be discussed later).
  • “Now, we’ll talk about classification”: you already know some classifiers such as KNN from other courses, so the lecture focuses on “more involved algorithms starting with Naive Bayes”.

2. Pre Study (s.3-12)

• s.3 is a section divider “Pre Study”.
• s.4: a tweet by Josh Wills (3 May 2012): “Data Scientist (n.): Person who is better at statistics than any software engineer and better at software engineering than any statistician.” Motivates why the statistics background is needed (no further explanation on slide).

Basics of probability (s.5)

• $P(A)$: probability that $A$ happens. $P(A|B)$: probability that $A$ happens given that $B$ happens (conditional probability).
• Rules (see Formulas): complement, disjunction, conjunction, independence, total probability.

Conditional probability (s.6)

• Example: If the patient has the symptom of toothache, then conclude cavity with probability $P$, where $P=P(\text{cavity}|\text{toothache})$.
• To compute it: $p(\text{cavity}\wedge \text{toothache})/p(\text{cavity})$ (as written on the slide).

Added context

The slide divides by $p(\text{cavity})$; the standard definition of $P(A|B)$ divides by $P(B)$, i.e. by $p(\text{toothache})$ here. This is flagged as a possible slide typo, but it is reproduced as printed.

Density estimation (s.7)

• Density estimation task: construct an estimate of an unobservable underlying probability density function, based on some observed data.
• Data: sample $x$ drawn i.i.d. (independent identically distributed) from set $\mathbf{X}$ according to some distribution $d$: $x_i,\dots ,x_m\in \mathbf{X}$.
• Problem: find a distribution $p$ out of a set $P$ that best estimates the true distribution $d$.

Argmax / Argmin (s.8)

• argmax = the argument of the maximum: the set of points of $x$ at which the given function attains its maximum value (slide text is cut off at the right edge; “points of the [domain] … which” is the evident wording; UNCLEAR (slide 8) for the exact cut-off word).
• $\arg {\max }_{x}f(x)=\{x\mid \forall y:f(y)\le f(x)\}$ and example $\arg {\max }_x(-|x|)=\{0\}$.

Maximum-Likelihood Estimation, MLE (s.9-11)

• Likelihood: probability of observing the sample under distribution $d$, which, given the independence assumption, is $\mathrm{Pr}[x_1,\dots ,x_m]={\prod }_{i=1}^{m}p(x_i)$ (s.9).
• MLE principle: select the distribution maximizing the sample probability: $p_{\ast }=\arg {\max }_{p\in \mathcal{P}}{\prod }_{i=1}^{m}p(x_i)$ (Likelihood) $=\arg {\max }_{p\in \mathcal{P}}{\sum }_{i=1}^m\log p(x_i)$ (Log-Likelihood) (s.9).
• s.10: given training data $D$, MLE finds the best hypothesis $h$ that maximizes the likelihood of the training data: $h_{ML}=\arg {\max }_{h\in H}P(D|h)$. Closing question: “What if you have some ideas about your hypothesis/parameters?” (leads to priors / MAP).
• Example: Gaussian distribution (s.11):
  • Task: find the most likely Gaussian distribution given a sequence of $m$ real-valued observations: 3.23, 1.23, 0.55, 1.23, …
  • Normal density $p(x)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-(x-\mu {)}^2/2{\sigma }^2}$ (bell-curve figure with mean $\mu$ at the centre and $\sigma$ marked as the spread).
  • Log-likelihood: $l(p)=-\frac{1}{2}m\log (2\pi {\sigma }^2)-{\sum }_1^m\frac{(x_i-\mu {)}^2}{2{\sigma }^2}$.
  • Solution (set derivatives to zero): $\partial l/\partial \mu =0\iff \mu =\frac{1}{m}\sum x_i$; $\partial l/\partial {\sigma }^2=0\iff {\sigma }^2=\frac{1}{m}\sum (x_i-\mu {)}^2$.

3. Bayes theorem (s.12-18)

• s.12: section divider “Bayes Theorem”.
• Bayes’ Rule (s.13): by definition of conditional probability, $p(h|D)=\frac{p(h,D)}{p(D)}=\frac{p(D|h)p(h)}{p(D)}$. Terms (colour-coded on the slide):
  • $P(h)$: prior probability of hypothesis $h$ (blue)
  • $P(h|D)$: posterior probability of $h$ given evidence $D$ (dark red)
  • $P(D|h)$: likelihood of $D$ given $h$ (orange)
  • $P(D)$: prior probability of evidence $D$
  • The rule is labelled “Reverse Probability” next to a portrait of Thomas Bayes (the slide does not caption the portrait; identification as Bayes is implied by the slide title).
• Example: H6751 Student Model (s.14). Given: taking H6751 causes you to stay in the library 80% of the time; prior probability of any student taking H6751 is 1/100; prior probability of any student staying in the library is 1/10. Question: if a student stays in the library, what is the probability they took H6751? Evidence $D$ = stay in library; hypothesis $h$ = taking H6751. The slide leaves "$p(h|D)=$" blank for the lecture to fill in.

Added context

Applying Bayes’ rule: $p(h|D)=\frac{0.8\times 0.01}{0.1}=0.08$. This calculation is not shown on the slide.

• Evolution of posterior probabilities (s.15-17): a three-step bar-chart animation, x-axis “hypotheses”, y-axis the probability.
  • s.15: $P(h)$, the prior: a low, flat (uniform) bar across all hypotheses.
  • s.16: $P(h|D1)$: after seeing one piece of data the mass concentrates on a narrower, taller block.
  • s.17: $P(h|D,D2)$: after more data the distribution is a tall narrow peak on one hypothesis.
  • Takeaway: as evidence accumulates, the posterior sharpens around the best hypotheses.
• Maximum A Posteriori (MAP) (s.18): find the most probable hypothesis given the training data: $h_{MAP}=\arg {\max }_{h\in \mathcal{H}}P(h|D)=\arg \max \frac{P(D|h)P(h)}{P(D)}=\arg \max P(D|h)P(h)$ ($P(D)$ is constant over $h$ and drops out). The $P(h)$ term is boxed in red: “Prior encodes the knowledge/preference”.
• MAP vs MLE (s.19): MLE maximizes the likelihood $P(D|h)$; MAP maximizes the posterior $P(h|D)$. Question posed: “When will MLE and MAP give the same results?” (answer is not on the slide).

Added context

They coincide when the prior $P(h)$ is uniform (all hypotheses equally likely), since then $P(h)$ is constant in the argmax. Not stated on the slides.

4. Classification with Bayes rule and Naive Bayes (s.20-23)

• Classification using Bayes rule (s.20): the example is $\mathbf{d}=[d_1,d_2,\dots ,d_n]$ (the features, red arrow). Given multiple attribute values, what is the most probable value (class)?
  • $h_{MAP}=\arg {\max }_{h_i\in \mathbb{H}}p(h_i|d_1,\dots ,d_n)=\arg \max \frac{p(h_i)p(d_1,\dots ,d_n|h_i)}{p(d_1,\dots ,d_n)}=\arg \max p(h_i)p(d_1,\dots ,d_n|h_i)$.
  • Problem: too much data needed to estimate $p(d_1,\dots ,d_n|h_i)$ when $n$ is large: the Curse of Dimensionality.
• Naive Bayes classifier: the idea (s.21): $p(\mathbf{d}|h_i)$ is hard to estimate for high-dimensional $\mathbf{d}$. Use the conditional independence assumption: all attributes are conditionally independent; the assumption is often violated in practice, yet even then it usually works well. Successful applications: classification of text documents, diagnosis.
• Conditional independence (s.22): chain rule $p(d_1,\dots ,d_n|h_i)=p(d_1|h_i)p(d_2|h_i,d_1)p(d_3|h_i,d_1,d_2)\cdots p(d_n|h_i,d_1,\dots ,d_{n-1})$. The Naive Bayes assumption: attributes are independent given the class: $p(d_2|h_i,d_1)=p(d_2|h_i)$, $p(d_3|h_i,d_1,d_2)=p(d_3|h_i)$, …, $p(d_n|h_i,d_1..d_{n-1})=p(d_n|h_i)$, hence $p(d_1,\dots ,d_n|h_i)=p(d_1|h_i)p(d_2|h_i)\cdots p(d_n|h_i)$ (highlighted in red).
• Naive Bayes classifier (s.23): based on Bayes’ rule + the assumption of conditional independence: $h_{NB}=\arg {\max }_{h_i\in \mathbb{H}}p(h_i|d_1..d_n)=\arg \max \frac{p(h_i)p(d_1..d_n|h_i)}{p(d_1..d_n)}=\arg \max p(h_i)p(d_1..d_n|h_i)=\arg \max p(h_i){\prod }_{j=1}^{n}p(d_j|h_i)$.

5. Text classification using Naive Bayes (s.24-30)

• s.24: section divider “Text Classification using Naive Bayes”.
• Text classification task (s.25): given the text of a newsgroup article, guess which newsgroup it is taken from. Naive Bayes works well on this application. Key issue: how do we represent examples? What are the attributes? Figure: three groups (Group A, Group B, Group C) drawn as stacks of cartoon documents in different colours (purple, white, green) = the candidate newsgroups/classes.
• s.26: Class $h_j$: binary classification (+/-) or multiple classes possible, $H$ ($j=1,2,\dots ,k$). Then asks: “How about attributes?” (answered next slides: words).
• Example (s.27): 1000 training documents of which someone has classified 700 as “dislikes” ($h_0$) and 300 as “likes” ($h_1$). Document 1 is “This is a very interesting document”. $h_{NB}={\max }_{h_j\in \{like,dislike\}}p(h_j)\times p(d_1=\text{this}|h_j)\times p(d_2=\text{is}|h_j)\cdots \times p(d_6=\text{document}|h_j)$. Priors: $p(like)=300/1000=0.3$, $p(dislike)=1-p(like)=0.7$. Open question: how to estimate $p(d_i|h_j)$? Each word position is an attribute.
• Parameter estimation (s.28): learning by maximum likelihood estimate: simply count frequencies in the data: $p(d_i=w|h_j)=\frac{count(w,h_j)}{{\sum }_{d\in \mathcal{V}}count(d_i,h_j)}$. Numerator (red arrow): count of the specific word $d_i=w$ in the mega-doc; denominator (orange arrow): count of total words in the mega-doc. Procedure: create a mega-document for class $h_j$ by concatenating all the docs in this class; compute the frequency of word $w$ in the mega-document.
• New word problem (s.29): what if some words do not exist in a certain category $h$? Then $p(d_i=\text{newword}|h)=0$, and the predicted likelihood is zero: $p(\mathbf{d}|h_i)=p(d_1|h_i)\cdots 0\cdots p(d_n|h_i)=0$. “How to solve it?” (answer on the next slide).
• Additive smoothing (s.30): $p(d_i=w|h_j)=\frac{count(w,h_j)+\alpha }{{\sum }_{d\in \mathbb{V}}count(d_i,h_j)+\alpha V}$, where $\alpha$ is the smoothing parameter (red arrow) and $V$ the vocabulary size (orange arrow). It is a weighted estimation of the relative frequency $\frac{count(w,h_j)}{\sum count(d_i,h_j)}$ and the uniform probability $\frac{1}{V}$.

Figures & diagrams

• s.1 Plain title slide with credits.
• s.3, s.12, s.24 Blue divider slides: “Pre Study”, “Bayes Theorem”, “Text Classification using Naive Bayes”.
• s.4 Screenshot of Josh Wills’ tweet defining “Data Scientist” (1,626 retweets, 1,294 likes); humorous motivation for statistics + engineering.
• s.5 Formula slide: probability rules (complement, disjunction, conjunction, independence, total probability).
• s.6 Text-formula slide for the cavity/toothache conditional probability.
• s.7 Definition slide with red key terms (Density Estimation, i.i.d., Problem).
• s.8 Formulas for argmax and $\arg \max (-|x|)=\{0\}$.
• s.9-10 Likelihood, log-likelihood, $h_{ML}$ formulas.
• s.11 Bell curve with $\mu$ at the centre and $\sigma$ marked; Gaussian density, log-likelihood and the closed-form solutions for $\mu$, ${\sigma }^2$.
• s.13 Bayes rule with colour-coded boxes (prior blue, likelihood orange, posterior red) and a portrait labelled “Reverse Probability”.
• s.15-17 Bar charts: prior (flat) -> $P(h|D1)$ (block) -> $P(h|D,D2)$ (narrow peak); posterior sharpens with data.
• s.18 MAP derivation with the prior boxed: “Prior encodes the knowledge/preference”.
• s.20 Features vector $\mathbf{d}$ with arrow “features”; “Curse of Dimensionality” in red.
• s.25 Three groups of cartoon documents (Group A, B, C) = newsgroups as classes.
• s.28 Count formula annotated with arrows (word count in mega-doc / total words in mega-doc).
• s.30 Additive-smoothing formula annotated with arrows ($\alpha$, $V$).

flowchart TD
    B["Bayes rule<br/>p(h|D) = p(D|h)p(h)/p(D)"] --> M["MAP: argmax p(D|h)p(h)"]
    M --> C["Classification: argmax p(h) p(d1..dn|h)"]
    C --> P["Problem: p(d1..dn|h) needs too much data<br/>(curse of dimensionality)"]
    P --> I["Conditional independence assumption"]
    I --> NB["Naive Bayes: argmax p(h) * prod p(dj|h)"]
    NB --> E["Estimate p(w|h) by counting in mega-doc (MLE)"]
    E --> Z["Unseen word -> p = 0 -> whole product 0"]
    Z --> S["Additive smoothing (count+alpha)/(total+alpha*V)"]

flowchart LR
    L["MLE<br/>argmax P(D|h)"] -- "multiply by prior P(h)" --> A["MAP<br/>argmax P(D|h)P(h)"]
    A -- "uniform prior" --> L

Key terms

• Concept - Probability Basics
• Concept - Conditional Probability
• Concept - Density Estimation
• Concept - Argmax
• Concept - Maximum Likelihood Estimation
• Concept - Likelihood
• Concept - Prior Probability
• Concept - Bayes Rule
• Concept - Maximum A Posteriori
• Concept - Curse of Dimensionality
• Concept - Conditional Independence
• Concept - Naive Bayes
• Concept - Additive Smoothing
• Earlier-deck concepts referenced on s.2: Concept - TF-IDF, Concept - Bag of Words, Concept - Latent Semantic Analysis (LSA)

Formulas

• Complement: $P(A^C)=1-P(A)$ (s.5)
• Disjunction: $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ (s.5)
• Conjunction: $P(A\cap B)=P(A|B)P(B)=P(B|A)P(A)$ (s.5)
• Independence: $P(A\cap B)=P(A)P(B)$ (s.5)
• Total probability: $P(B)={\sum }_{i=1}^{k}P(A|B_i)P(B_i)$ (s.5; as printed on the slide)
• Likelihood: $\mathrm{Pr}[x_1..x_m]={\prod }_{i=1}^{m}p(x_i)$; MLE: $p_{\ast }=\arg {\max }_p\prod p(x_i)=\arg {\max }_p\sum \log p(x_i)$ (s.9)
• $h_{ML}=\arg {\max }_{h\in H}P(D|h)$ (s.10, s.19)
• Gaussian MLE: $\mu =\frac{1}{m}\sum x_i$, ${\sigma }^2=\frac{1}{m}\sum (x_i-\mu {)}^2$ (s.11)
• Bayes: $p(h|D)=\frac{p(D|h)p(h)}{p(D)}$ (s.13)
• $h_{MAP}=\arg {\max }_{h}P(D|h)P(h)$ (s.18)
• Naive Bayes: $h_{NB}=\arg {\max }_{h_i}p(h_i){\prod }_{j=1}^{n}p(d_j|h_i)$ (s.23)
• MLE word probability: $p(w|h_j)=\frac{count(w,h_j)}{{\sum }_{d\in V}count(d,h_j)}$ (s.28)
• Additive smoothing: $p(w|h_j)=\frac{count(w,h_j)+\alpha }{{\sum }_{d\in V}count(d,h_j)+\alpha V}$ (s.30)

Likely exam questions

1. State Bayes’ rule and name each term. (s.13) $p(h|D)=p(D|h)p(h)/p(D)$: posterior = likelihood x prior / evidence prior.
2. Discuss the difference between MLE and MAP. (s.19) MLE maximizes $P(D|h)$ (likelihood, no prior); MAP maximizes $P(h|D)\propto P(D|h)P(h)$ (includes the prior knowledge/preference). They coincide for a uniform prior (added context).
3. Explain the Naive Bayes classifier. (s.21-23) Bayes rule + conditional independence of attributes given the class: $\arg {\max }_{h}p(h){\prod }_{j}p(d_j|h)$.
4. What is the conditional independence assumption and is it realistic? (s.21-22) Attributes are independent given the class; often violated in practice, but NB usually still works well.
5. Why is $p(d_1..d_n|h)$ hard to estimate? (s.20) Needs too much data when $n$ is large: curse of dimensionality.
6. How are NB parameters estimated for text? (s.28) MLE by counting: build a mega-document per class and take word count / total words in it.
7. What is the new-word (zero-frequency) problem and how is it solved? (s.29-30) A word unseen in a class gives probability 0, zeroing the whole product; solved by additive smoothing $(count+\alpha )/(total+\alpha V)$.
8. Explain the roles of $\alpha$ and $V$ in additive smoothing. (s.30) $\alpha$ = smoothing parameter; $V$ = vocabulary size; result is a weighted mix of relative frequency and uniform probability $1/V$.
9. Compute priors in the likes/dislikes example. (s.27) $p(like)=300/1000=0.3$, $p(dislike)=0.7$.
10. Derive MLE for a Gaussian. (s.11) Maximize the log-likelihood; derivatives give $\mu$ = sample mean, ${\sigma }^2$ = mean squared deviation.

Common confusions

• Likelihood vs posterior: $P(D|h)$ (likelihood, MLE) is not $P(h|D)$ (posterior, MAP) (s.13, s.19).
• Conditional independence vs independence: NB assumes attributes independent given the class, not unconditionally (s.22).
• Prior $P(h)$ vs evidence $P(D)$: both are “prior probabilities” on s.13 but $P(D)$ is constant across $h$ and drops out of the argmax (s.18).
• Likelihood of document vs class prior: $p(like)=0.3$ is the class prior estimated from document counts; word probabilities $p(d_i|h_j)$ are estimated separately from the mega-document (s.27-28).
• Log-likelihood: taking logs turns the product into a sum without changing the argmax (s.9).
• Smoothing when $\alpha =0$: reduces to the plain MLE estimate of s.28 (derived from the formula).

Slide coverage

Slide	Content	Covered in
1	Title, credits (NTU, StatQuest)	Detailed notes 1
2	Introduction: document representation, move to classification, NB	Detailed notes 1
3	Divider: Pre Study	Detailed notes 2
4	Josh Wills data scientist tweet	Detailed notes 2; Figures
5	Basics of probability	Detailed notes 2; Formulas
6	Conditional probability (cavity/toothache)	Detailed notes 2
7	Density estimation	Detailed notes 2
8	Argmax/Argmin	Detailed notes 2
9	MLE: likelihood, log-likelihood	Detailed notes 2; Formulas
10	MLE: hypothesis $h_{ML}$	Detailed notes 2
11	Gaussian MLE example	Detailed notes 2; Figures
12	Divider: Bayes Theorem	Detailed notes 3
13	Bayes’ rule	Detailed notes 3; Figures
14	H6751 student example	Detailed notes 3
15	Posterior evolution: prior	Detailed notes 3; Figures
16	Posterior evolution: P(h given D1)	Detailed notes 3; Figures
17	Posterior evolution: P(h given D, D2)	Detailed notes 3; Figures
18	Maximum A Posteriori	Detailed notes 3
19	MAP vs MLE	Detailed notes 3
20	Classification using Bayes rule; curse of dimensionality	Detailed notes 4
21	Naive Bayes classifier idea	Detailed notes 4
22	Conditional independence	Detailed notes 4
23	Naive Bayes classifier formula	Detailed notes 4
24	Divider: Text classification using NB	Detailed notes 5
25	Newsgroup classification task	Detailed notes 5; Figures
26	Classes and attributes	Detailed notes 5
27	Likes/dislikes example	Detailed notes 5
28	Parameter estimation (mega-doc)	Detailed notes 5
29	New word problem	Detailed notes 5
30	Additive smoothing	Detailed notes 5

Previous: (none, first chunk) | Next: 03 Text Classification - Chunk 02 (s.31-60) | Up: 03 Text Classification - Index