Classifying Text · Natural Language Processing

01 · Motivation

What text classification is

Text classification assigns a piece of text to one or more predefined categories. It is the workhorse of applied NLP — spam filters, sentiment, authorship attribution, content moderation, query-intent, ticket routing, voice-assistant intent.

The pattern is always the same: a document arrives, we need a label, and we have past (document, label) pairs to learn from. That last assumption — labelled training data — is what makes this supervised learning.

key

The four shapes of classification

Binary — two mutually exclusive classes. “Is this spam?” Output is one bit.
Multiclass — one label from $K > 2$ mutually exclusive classes. “Which department?”
Multilabel — any subset of $K$ classes (including none/all). “Tag this article.” Treated as $K$ independent binary problems.
Ordinal — labels have a natural order. “Predict the 1–5 star rating.” Predicting 4 for a true 5 is much less wrong than predicting 1.

Q

Name the shape

(a) language ID of a tweet → multiclass; (b) hashtag suggestion → multilabel; (c) Amazon star rating → ordinal; (d) toxic/non-toxic → binary. Trap: calling multilabel “multiclass with more classes” — multilabel classes are not mutually exclusive.

02 · Refresher

The supervised learning loop

Fix the vocabulary now; it means the same thing in every later chapter. An instance is one example (a document). A feature vector $\mathbf{x} \in \mathbb{R}^d$ is its numerical representation. A label $y$ is the target. A model $f(\mathbf{x};\boldsymbol\theta)$ maps features to a predicted label; its parameters $\boldsymbol\theta$ are learned from data.

Hyperparameters are knobs on the learning algorithm (regularisation strength, learning rate, smoothing constant) — not learned from training data. Tune them on a held-out validation set; touch the test set only once, at the end.

!

Overfitting in one sentence

A model overfits when it memorises noise instead of signal — training error falls while validation error climbs. In text classification this is the default, because you almost always have far more features (vocabulary terms) than documents. That is why every serious text classifier uses regularisation or smoothing.

03 · Representation

Bag-of-Words — the canonical sparse representation

Fix a vocabulary $V = \{v_1, \dots, v_{|V|}\}$ . Represent each document as a vector $\mathbf{x} \in \mathbb{R}^{|V|}$ where $x_i$ is the count (or 0/1, or TF-IDF — Ch. 3) of word $v_i$ .

BoW

x^{(d)}_i = \operatorname{count}(v_i \in d) \qquad \text{or} \qquad x^{(d)}_i = \mathbb{1}[v_i \in d]

BoW captures word identity and frequency; it loses word order. “man bites dog” and “dog bites man” map to the same vector.

Heap’s law says vocabulary grows roughly as the square root of corpus length; Zipf’s law says token frequency is roughly inversely proportional to rank. Together they explain the shape of BoW vectors: any single document uses a tiny slice of the vocabulary, so its vector is mostly zeros. Store them sparse — lists of (index, count) pairs — never dense arrays.

key

Our running example

One six-sentence toy corpus threads through the whole guide — Bag-of-Words here, then TF-IDF, cosine similarity and the inverted index in Chapter 3 — so you watch a single dataset flow through every representation. Three positive (👍) and three negative (👎) one-line reviews:

👍 the film was brilliant and moving
👍 a brilliant and clever film
👍 the acting was great and moving
👎 the film was boring and dull
👎 a dull and predictable film
👎 the acting was boring and weak

The shared words (the, film, and, was, a, acting) carry no class signal; the polar words (brilliant, moving, clever, great vs boring, dull, predictable, weak) do. The AI tutor grounds its worked examples in exactly these sentences.

Hands-on

Build a Bag-of-Words term–document matrix

Each document becomes a vector of word counts (or 0/1). Add a document of all-distinct words and watch the matrix get sparser — the curse of dimensionality lurking under every BoW model.

Documents (one per line)

6 docs × 14 terms · sparsity 60%

doc	a	acting	and	boring	brilliant	clever	dull	film	great	moving	predictable	the	was	weak
D1	0	0	1	0	1	0	0	1	0	1	0	1	1	0
D2	1	0	1	0	1	1	0	1	0	0	0	0	0	0
D3	0	1	1	0	0	0	0	0	1	1	0	1	1	0
D4	0	0	1	1	0	0	1	1	0	0	0	1	1	0
D5	1	0	1	0	0	0	1	1	0	0	1	0	0	0
D6	0	1	1	1	0	0	0	0	0	0	0	1	1	1

TakeawayBoW keeps word identity and frequency but drops order — “man bites dog” and “dog bites man” get the same vector. And because each word is its own dimension, “brilliant” and “great” have zero similarity. Dense embeddings (Ch. 4) exist to fix exactly this.

Q

When BoW is fine, when it isn't, and synonyms

Fine for spam and topic classification of long documents — characteristic words carry the signal regardless of order.
Not fine for sentiment of short compositional sentences (“this film was not bad”) — drop the order and you drop the negation.
Synonyms get zero similarity because each term is its own orthogonal dimension: “brilliant” and “great” share no axis. Dense embeddings (Ch. 4) exist to fix this.
Trap. Calling BoW “useless.” It is a strong, fast baseline that beats fancier methods on long-document tasks.

04 · Probabilistic baseline

Naïve Bayes — Bayes’ rule with a bold assumption

We want the most probable class given the document, $\arg\max_c P(c \mid d)$ . Bayes’ rule swaps the conditioning, and $P(d)$ is constant across classes so it drops out of the argmax:

Bayes

P(c \mid d) = \frac{P(d \mid c)\, P(c)}{P(d)} \;\propto\; P(d \mid c)\, P(c)

The naïve step: assume words are conditionally independent given the class. Obviously false for real text, but it makes the likelihood factorise into one-dimensional probabilities we can count:

Naïve Bayes

\hat{c} = \arg\max_{c \in \mathcal{C}}\, P(c) \prod_{i=1}^{n} P(w_i \mid c)

If a test word never appeared in some class, its raw $P(w_i \mid c) = 0$ annihilates the whole product — the zero-count catastrophe. Fix it with a pseudo-count $\alpha$ (Laplace smoothing, $\alpha = 1$ the default):

Smoothing

P(w_i \mid c) = \frac{\operatorname{count}(w_i, c) + \alpha}{\sum_{w \in V}\operatorname{count}(w, c) + \alpha\, |V|}

Work in log-space — the product becomes a sum, avoiding underflow. The additive form $\log P(c) + \sum_i \log P(w_i\mid c)$ is exactly a linear classifier in BoW space.

Hands-on

Naïve-Bayes step-through

Each test-doc word adds a log P(w | c) term to each class. The class with the largest log-posterior wins. Set α = 0 and an unseen test word sends one log to −∞.

Training data (one class | document per line)

Test docα (Laplace)

class · pos (positive)

log P(pos) = -0.693

+ log P(a | pos) = log(2/31) = -2.741

+ log P(clever | pos) = log(2/31) = -2.741

+ log P(and | pos) = log(4/31) = -2.048

+ log P(brilliant | pos) = log(3/31) = -2.335

+ log P(film | pos) = log(3/31) = -2.335

total ∝ -12.893

class · neg (negative)

log P(neg) = -0.693

+ log P(a | neg) = log(2/31) = -2.741

+ log P(clever | neg) = log(1/31) = -3.434

+ log P(and | neg) = log(4/31) = -2.048

+ log P(brilliant | neg) = log(1/31) = -3.434

+ log P(film | neg) = log(3/31) = -2.335

total ∝ -14.685

predicted class → pos|V| = 14 · 6 training docs

Takeaway“Naïve” = conditional independence of words given the class — false for real text, yet the argmax is often right anyway. Always smooth (α > 0); the predicted probabilities are overconfident, so prefer logistic regression when you need calibration.

Q

Why 'naïve', and why it works anyway

Naïve = conditional independence of features given the class. Neighbouring words (New/York, machine/learning) are correlated, so the assumption is false.
Works because we only need the argmax over classes to be right, not the calibrated probability; correlated features double-count on both sides and the bias often cancels.
Cost. Predicted probabilities are systematically overconfident — prefer logistic regression if you need calibration.
Trap. With $\alpha = 0$ a single unseen word annihilates a class’s score. Always smooth.

05 · Calibrated workhorse

Logistic regression — a discriminative linear classifier

Naïve Bayes models $P(d \mid c)$ and inverts it (generative); logistic regression models $P(c \mid \mathbf{x})$ directly (discriminative). Compute a score $s(\mathbf{x}) = \mathbf{w}^\top\mathbf{x} + b$ ; $s = 0$ is the decision hyperplane. Squash the score into a probability with the sigmoid:

Logistic

P(y = 1 \mid \mathbf{x}) = \sigma\bigl(\mathbf{w}^\top\mathbf{x} + b\bigr) = \frac{1}{1 + e^{-(\mathbf{w}^\top\mathbf{x} + b)}}

Hands-on

From score to probability — the sigmoid

A score in (−∞, +∞) isn’t a probability. The logistic function squashes it into (0, 1), taking 0.5 at the boundary. Larger weights make the transition sharper — almost a step.

Score w·x + b0.00

Weight scale1.0

σ(0.00 × 1.0) = P(y=1) = 0.5000 · prediction: positive

TakeawayLogistic regression is a linear score passed through the sigmoid. Unlike Naïve Bayes it models P(c | x) directly (discriminative) and is usually better calibrated.

Fit the weights by minimising the negative log-likelihood (binary cross-entropy):

\mathcal{L}(\mathbf{w}, b) = -\sum_{j=1}^{N} \Bigl[ y_j \log \sigma(s_j) + (1 - y_j)\log\bigl(1 - \sigma(s_j)\bigr) \Bigr].

Cross-entropy sends loss to $+\infty$ as the predicted probability of the correct class goes to zero, and it is convex in $\mathbf{w}$ — unlike MSE on top of a sigmoid. Because text has far more features than documents, add a penalty $\lambda R(\mathbf{w})$ : L2 (ridge) shrinks all weights gently; L1 (lasso) drives many to exactly zero (sparse, interpretable).

key

Generative vs discriminative — same hyperplane, two routes

Both NB and LR fit a linear boundary in BoW space. NB estimates each $P(w_i\mid c)$ independently from counts; LR jointly optimises all weights so correlated features are traded off rather than double-counted. That joint optimisation is why LR usually wins given enough data — and why NB usually wins when data is scarce (less to overfit on).

Q

LR vs NB, and when to prefer NB

LR is discriminative (models $P(c\mid\mathbf{x})$ , fit by gradient descent on cross-entropy); NB is generative (models $P(\mathbf{x}\mid c)P(c)$ , closed-form one pass). Prefer NB when data is very small or you need a fast, low-variance baseline. Trap: LR does assume the log-odds are linear in $\mathbf{x}$ — it is not assumption-free.

06 · Margin maximiser

Support Vector Machines — geometry, not probability

A third route to a linear boundary, motivated by a different question: not which hyperplane makes the labels most likely? but which hyperplane sits as far from the data as possible? The widest buffer is the margin; the points on its edge are the support vectors — the only training points that affect the boundary. Real text isn’t separable, so allow intrusions at a price — the hinge loss:

Hinge

\ell_{\text{hinge}}(\mathbf{x}_j, y_j) = \max\bigl(0,\; 1 - y_j(\mathbf{w}^\top\mathbf{x}_j + b)\bigr), \qquad y_j \in \{-1, +1\}

A point outside the margin on the correct side pays zero — so SVMs ignore easy cases and focus on the hard ones near the boundary. The full objective adds $\lambda\lVert\mathbf{w}\rVert_2^2$ , equivalent to maximising the margin.

Reference Three classifiers, one comparison

Property	Naïve Bayes	Logistic Regression	Linear SVM
Type	Generative	Discriminative (probabilistic)	Discriminative (geometric)
Optimises	Joint likelihood $P(\mathbf{x}, c)$	Cross-entropy $-\log P(y\mid\mathbf{x})$	Hinge loss + margin
Training	Closed-form, one pass	Iterative (gradient descent)	Iterative (convex QP / SGD)
Output	Label + overconfident prob.	Label + calibrated probability	Label + signed score (not a prob)
Best when	Little data, fast baseline	You need calibrated probabilities	High-dim sparse text, want robustness
Key knob	Smoothing $\alpha$	L1/L2 strength $\lambda$	Margin trade-off $C = 1/\lambda$

Q

Why far-away points are irrelevant to an SVM but not to LR

SVM: hinge loss is exactly zero outside the margin, so distant points contribute no gradient — only support vectors matter. LR: cross-entropy is positive everywhere, so even a correctly classified point at score $+10$ still pulls a little. SVMs are thus less sensitive to outliers far from the boundary.

07 · Evaluation

Confusion matrix, precision, recall, F1

Accuracy lies. On a 99%-ham dataset, “predict ham” scores 99% accuracy and catches zero spam. For a binary task with positive class “spam”:

TP / TN

Correctly predicted positive / negative.

FP — false alarm

Actually ham, predicted spam.

FN — miss

Actually spam, predicted ham.

The metrics

Precision = low FP; Recall = low FN; F₁ = their harmonic mean.

Metrics

\text{Precision} = \frac{TP}{TP + FP} \qquad \text{Recall} = \frac{TP}{TP + FN} \qquad F_1 = \frac{2 \cdot P \cdot R}{P + R}

Hands-on

Confusion matrix · precision / recall / F₁

Move the threshold. A higher threshold predicts “positive” less often — precision rises, recall falls. F₁ is their harmonic mean; the sweep shows where it peaks.

Threshold0.50

	pred 1	pred 0
actual 1	TP · 92	FN · 8
actual 0	FP · 16	TN · 84

Precision

0.852

Recall

0.920

F₁

0.885

F₁ sweep:0.00.670.10.690.20.710.30.760.40.870.50.880.60.860.70.620.80.330.90.111.00.06

TakeawayPrecision and recall trade off through the threshold; F₁ summarises the balance. Which to favour is a product decision — spam filters guard precision, cancer screens guard recall.

For multiclass, macro-F1 averages per-class F1 equally (honest for rare classes); micro-F1 pools all counts first (dominated by frequent classes; equals accuracy in single-label problems). The ROC curve plots TPR vs FPR across all thresholds; AUC is the threshold-independent probability that a random positive scores above a random negative.

Q

Compute the metrics, then choose what to cite

TP = 80, FP = 20, FN = 5, TN = 895. Accuracy = 975/1000 = 0.975; Precision = 80/100 = 0.80; Recall = 80/85 ≈ 0.94; F1 ≈ 0.86. Accuracy hides that 20% of “spam” flags are false alarms — cite precision and recall together; for a spam filter, push precision up by raising the threshold.

08 · Applied

Spelling correction — Naïve Bayes meets the noisy channel

Treat the misspelling $x$ (“acress”) as a corrupted version of an intended word $w$ , and pick the most probable $w$ . Bayes’ rule, denominator dropped:

Noisy channel

\hat{w} = \arg\max_{w \in V}\, \underbrace{P(w)}_{\text{prior}} \cdot \underbrace{P(x \mid w)}_{\text{error model}}

The error model needs “how close” two strings are: Levenshtein edit distance, the minimum number of single-character insertions, deletions, or substitutions, computed by dynamic programming:

Edit distance DP

d(i, j) = \min\begin{cases} d(i-1, j) + 1 & \text{(delete } a_i) \\ d(i, j-1) + 1 & \text{(insert } b_j) \\ d(i-1, j-1) + \mathbb{1}[a_i \neq b_j] & \text{(match / substitute)} \end{cases}

Initialise $d(0,j)=j$ , $d(i,0)=i$ ; fill left-to-right, top-to-bottom; the bottom-right cell is the answer.

Hands-on

Levenshtein edit-distance matrix

Type two strings. Each cell is the minimum of delete (↑+1), insert (←+1), and substitute (↖+0/+1). The highlighted path is one optimal alignment; the corner is the edit distance.

String AString Bdistance = 3

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

TakeawayMinimum edit distance is the candidate-ranking primitive in the noisy-channel spelling corrector: the best correction balances how close a candidate is to the typo against how likely the word is.

Conditioning on context too — $\hat{w} = \arg\max_w P(w)\,P(x\mid w)\,P(\text{prev}\mid w)$ — is exactly a Naïve Bayes classifier: the class is $w$ , the features are the misspelling and the surrounding context, assumed conditionally independent given $w$ .

Q

Edit distance, and why BoW cosine is the wrong tool

$d(\text{intention}, \text{execution}) = 5$ with unit costs. BoW cosine fails for spelling because it indexes by words, not characters: “acress” and “actress” are orthogonal dimensions with zero cosine, even though one is a typo of the other. Spelling needs sequence-aware character distance.

09 · Self-check

Five questions before you move on

A classifier reports TP=40, FP=10, FN=20, TN=130. Which value is the recall?

In Naïve Bayes, "free" appears 0 times in class ham; |V| = 100, class-token total = 500. With α = 1, P("free" | ham) is:

You lower the decision threshold of a logistic classifier from 0.5 to 0.3. What happens to precision and recall?

Which statement best captures L1 vs L2 regularisation in logistic regression?

A linear SVM is trained; you add 1,000 new points all far on the correct side (outside the margin). What happens to the boundary?

10 · Recap

One-screen summary

Chapter 02 — load-bearing ideas

Text classification is a vector → label problem in four shapes (binary, multiclass, multilabel, ordinal). Pick the shape before the model.
Bag-of-Words gives sparse, high-dimensional vectors — loses order, keeps word identity. Zipf and Heap explain the shape.
Naïve Bayes (generative, one pass, smoothed) vs logistic regression (discriminative, calibrated) vs linear SVM (margin, robust) — three routes to similar hyperplanes.
Smoothing (NB) and regularisation (LR, SVM) exist because text always has more features than documents. L1 → sparse; L2 → gentle shrinkage (safer default).
Accuracy lies on imbalanced data. Use precision, recall, F1, macro-vs-micro; the threshold trades precision against recall.
Spelling correction = noisy channel = Naïve Bayes, with Levenshtein edit distance as the error model.

11 · Exam · past papers

Past-paper questions

Answered 0 / 10 · 0 correct

Q10Which task involves assigning a label from a predefined set of categories to a piece of text?
Q1The main reason for performing stemming before building a text classifier is to:
Q5A Naïve Bayes spam classifier has 2,000 spam and 8,000 not-spam emails. What is the prior P(spam)?
Q9With P("win"|spam)=4/10, P("win"|not-spam)=1/10, P(spam)=2/10, what is P(spam | "win")?
Q12"The size of the vocabulary grows roughly in proportion to the square root of the length of the collection" is a statement of:
Q13Zipf's law states that:
Q-LR-NBWhich is TRUE of logistic regression compared with Naïve Bayes?
Q-SVMIn a soft-margin linear SVM, which training points determine the decision boundary?
Q-ACCWhy is accuracy a poor metric on a 99%-ham email dataset?
Q-EDThe Levenshtein distance between "kitten" and "sitting" is:

doc	a	acting	and	boring	brilliant	clever	dull	film	great	moving	predictable	the	was	weak
D1	0	0	1	0	1	0	0	1	0	1	0	1	1	0
D2	1	0	1	0	1	1	0	1	0	0	0	0	0	0
D3	0	1	1	0	0	0	0	0	1	1	0	1	1	0
D4	0	0	1	1	0	0	1	1	0	0	0	1	1	0
D5	1	0	1	0	0	0	1	1	0	0	1	0	0	0
D6	0	1	1	1	0	0	0	0	0	0	0	1	1	1

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

doc	a	acting	and	boring	brilliant	clever	dull	film	great	moving	predictable	the	was	weak
D1	0	0	1	0	1	0	0	1	0	1	0	1	1	0
D2	1	0	1	0	1	1	0	1	0	0	0	0	0	0
D3	0	1	1	0	0	0	0	0	1	1	0	1	1	0
D4	0	0	1	1	0	0	1	1	0	0	0	1	1	0
D5	1	0	1	0	0	0	1	1	0	0	1	0	0	0
D6	0	1	1	1	0	0	0	0	0	0	0	1	1	1

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

doc	a	acting	and	boring	brilliant	clever	dull	film	great	moving	predictable	the	was	weak
D1	0	0	1	0	1	0	0	1	0	1	0	1	1	0
D2	1	0	1	0	1	1	0	1	0	0	0	0	0	0
D3	0	1	1	0	0	0	0	0	1	1	0	1	1	0
D4	0	0	1	1	0	0	1	1	0	0	0	1	1	0
D5	1	0	1	0	0	0	1	1	0	0	1	0	0	0
D6	0	1	1	1	0	0	0	0	0	0	0	1	1	1

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3