Machine Learning and Real-World Data

The Golden Rule

Before performing any analysis on a dataset, partition it into three disjoint subsets: training, development (validation), and test. This separation prevents data leakage and preserves the validity of statistical evaluation.

Training Set

The training set is used strictly for fitting model parameters. For a Naive Bayes classifier, this means counting word-class co-occurrences and estimating priors. The model sees these examples during learning; no evaluation happens here.

Typical proportion: 60-80% of the total data.

Development (Validation) Set

The development set tunes hyperparameters, selects features, and debugs the model. You may evaluate on this set repeatedly whilst iterating on the model: adjusting the smoothing parameter $\omega$, choosing which features to include, comparing different model architectures.

Typical proportion: 10-20% of the total data.

Test Set

The test set is used exactly once: to report the final, unbiased performance of the chosen model. It must remain completely unseen throughout development. The model’s parameters must never be influenced by test-set performance.

Typical proportion: 10-20% of the total data.

The Multiple Comparisons Problem

If you check the test set repeatedly during development (even “just to see how things are going”), you are implicitly tuning to it. Each peek constitutes a comparison; across many peeks, the model that happens to score highest on this particular test split will be selected. The test set is no longer “unseen”, and statistical significance tests become invalid.

A common exam scenario: a student develops a model over 20 iterations, checking test-set accuracy after each change. On the final iteration, they obtain 85% and claim significance. This is wrong: the model was selected precisely because it happened to look best on that test split. The p-value associated with that 85% is meaningless, since the test data has been incorporated into the model selection process.

Simple Diagram

A typical data split maps as follows: 70% of the original data becomes the training set. Of the remaining 30%, half (15% of total) forms the development set and half (15% of total) forms the held-out test set. The training set fits the model; the development set guides feature and hyperparameter selection; the test set provides one final, honest evaluation number.

Summary

Past paper questions: y2021p3q9, y2023p3q8

N-Fold Cross-Validation

When data is limited, a single train-dev-test split wastes precious training examples. N-fold cross-validation (CV) maximises data usage: divide the data into $N$ equal folds, train on $N-1$ folds, test on the remaining fold, and rotate until every fold has served as the test set. Report the mean and variance of the metric across folds.

For $N=5$ and 100 documents: partition into 5 folds of 20 documents each. In each round, train on 80 documents, test on 20. After 5 rounds, average the 5 accuracy scores (or F1 scores).

Five-fold or ten-fold CV is standard. Ten-fold gives lower bias but higher variance; five-fold is computationally cheaper.

Stratified Cross-Validation

Standard CV splits data randomly. With imbalanced classes (e.g., 90% OK messages, 10% bullying), a random split could place all bullying messages in one fold, distorting evaluation. Stratified CV ensures each fold preserves the overall class distribution: if the full dataset is 90/10, every fold is also ~90/10.

Stratified CV is essential for any imbalanced classification task.

Leave-One-Out CV (Jack-Knifing)

The extreme case: $N$ equals the number of data points. For 100 documents, train on 99 and test on 1, repeating 100 times. This maximises training data and gives the least biased estimate of performance. The cost is high: 100 training runs, each on nearly the full dataset. Only practical for very small datasets (tens of items).

Dependency-Sensitive Cross-Validation

When data points are not independent (e.g., multiple documents by the same author, or from the same publication venue), random CV overestimates generalisation. The model memorises author style rather than learning the task.

Dependency-sensitive CV folds by domain: all documents from author X go into a single fold, ensuring the model is tested on genuinely unseen authors, genres, or sources. This tests true out-of-domain generalisation.

Worked Example

A dataset contains 100 documents across 2 classes (60 OK, 40 bullying). With 5-fold stratified CV:

• Each fold holds 20 documents: 12 OK and 8 bullying (preserving the 60/40 ratio).
• In round 1: train on folds 2-5 (80 documents, 48 OK + 32 bullying), test on fold 1.
• After 5 rounds: compute mean accuracy = 0.87, variance = 0.002.
• Report: “87% accuracy (SD = 4.5%) across 5-fold stratified CV.”

Without stratification, a fold might contain only 2 bullying messages, producing unreliable per-fold estimates and inflating variance.

Summary

Past paper questions: y2021p3q9 (evaluation strategy)

The 2×2 Confusion Matrix

For binary classification, every prediction falls into one of four cells:

• TP: correctly identified positives (bullies caught)
• FP: false alarms (innocent messages flagged)
• FN: missed positives (bullies that slipped through)
• TN: correctly identified negatives (innocent messages passed)

Accuracy

$\text{Accuracy} = \frac{\text{TP} + \text{TN}}{\text{TP} + \text{FP} + \text{FN} + \text{TN}}$

Accuracy is misleading when classes are imbalanced. A classifier that labels every message “OK” on a dataset with 95% OK messages achieves 95% accuracy, yet detects zero bullying. Always check class distribution before trusting accuracy.

Precision

$\text{Precision} = \frac{\text{TP}}{\text{TP} + \text{FP}}$

Of all messages the system claimed were bullying, what fraction truly were? High precision means when the system flags something, you can trust it.

Prioritise high precision when: medical treatment decisions, legal evidence flagging, any domain where false alarms carry high cost.

Recall

$\text{Recall} = \frac{\text{TP}}{\text{TP} + \text{FN}}$

Of all actual bullying messages, what fraction did the system find? High recall means few bullies are missed.

Prioritise high recall when: disease screening, spam detection, brand-attack detection, any domain where missing a positive is worse than a false alarm.

F1 Score

$\text{F1} = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}$

The harmonic mean of precision and recall. F1 penalises extreme imbalance: if precision = 0.9 and recall = 0.1, F1 = 0.18 (not 0.5). This makes F1 more honest than the arithmetic mean.

Prioritise high F1 when: most NLP classification tasks, balanced trade-off needed.

Worked Example

A bullying-filter classifier is evaluated on 1000 messages, of which 100 are truly bullying:

• Accuracy = (80 + 860) / 1000 = 0.94 (94%)
• Precision = 80 / (80 + 40) = 80/120 = 0.667
• Recall = 80 / (80 + 20) = 80/100 = 0.80
• F1 = 2 × (0.667 × 0.80) / (0.667 + 0.80) = 2 × 0.534 / 1.467 = 0.728

Accuracy looks excellent at 94%, but that is driven by the 860 TNs. Precision and recall reveal that one third of flagged messages are false alarms, and one fifth of bullies are missed.

Note: precision and recall are always defined with respect to a specific class (here, bullying). There is no such thing as “overall precision” without specifying the class of interest.

Summary

Past paper questions: y2021p3q9(b)

Why Averaging Matters

With more than two classes, a single precision/recall/F1 number per class tells only part of the story. We need a way to aggregate per-class metrics into one overall score. The choice between macro and micro averaging determines which classes drive the final number.

Macro-Averaging

Compute the metric (e.g., F1) for each class independently, then take the arithmetic mean across classes. Every class contributes equally, regardless of how many examples it has.

$\text{Macro-F1} = \frac{1}{|C|} \sum_{c \in C} \text{F1}_c$

Best for imbalanced data where minority classes matter. If class A has 1000 examples and class B has 10, macro-F1 gives them equal weight. A poor F1 on the minority class will noticeably drag down the macro average.

Micro-Averaging

Pool all TP, FP, and FN counts across classes into global totals, then compute the metric on those pooled counts.

$\text{Micro-F1} = \frac{2 \times \sum_c \text{TP}_c}{2 \times \sum_c \text{TP}_c + \sum_c \text{FP}_c + \sum_c \text{FN}_c}$

This is equivalent to computing accuracy (when each example has exactly one label). Large classes dominate; a minority class with poor performance barely affects the score.

Worked Example

Consider a 3-class problem with the following per-class counts:

Per-class F1:

• Hardware: Precision = 90/95 = 0.947, Recall = 90/100 = 0.90, F1 = 2×0.947×0.90/(0.947+0.90) = 0.923
• Theory: Precision = 80/90 = 0.889, Recall = 80/100 = 0.80, F1 = 0.842
• Ethics: Precision = 5/10 = 0.50, Recall = 5/20 = 0.25, F1 = 0.333

Macro-F1 = (0.923 + 0.842 + 0.333) / 3 = 0.699

Micro-F1: pool all counts.

Total TP = 90 + 80 + 5 = 175 Total FP = 5 + 10 + 5 = 20 Total FN = 10 + 20 + 15 = 45

Micro-Precision = 175/(175+20) = 0.897 Micro-Recall = 175/(175+45) = 0.795 Micro-F1 = 2×0.897×0.795/(0.897+0.795) = 0.844

The macro-F1 (0.699) reflects the poor Ethics performance. The micro-F1 (0.844) is dominated by the two large classes and hides the Ethics problem. When minority classes matter, report macro-averaged metrics; when overall throughput matters, micro-averaging suffices.

Summary

Past paper questions: y2023p3q8(b) (per-area evaluation)

The Problem

Repeatedly evaluating on the test set during development makes the test set no longer “unseen”. Each evaluation is a comparison; across many comparisons, the model that happens to look best on this particular random split is selected. Statistical significance tests assume a single, pre-planned comparison against fresh data. Using the same test set across iterations violates this assumption.

Why p-Values Break

A p-value of 0.03 means: “if the null hypothesis were true, there is a 3% chance of observing a result this extreme.” This relies on the test data being a single fresh draw. If you have tested 50 model variants on the same test set, you have effectively run 50 comparisons. The probability that at least one variant looks “significant” at $\alpha = 0.05$ purely by chance is:

$P(\text{at least one significant}) = 1 - (1 - 0.05)^{50} \approx 0.923$

There is a 92% chance that pure noise will produce at least one “significant” result. The p-value of the winning variant is meaningless, because that variant won precisely because it overfit the noise in the test set.

Common Exam Scenario

A student splits data into train/test, then develops a classifier over 15 iterations:

1. Train on training set
2. Evaluate on test set
3. Adjust features based on test-set performance
4. Repeat

On iteration 15, accuracy = 88%. The student computes a p-value and claims the classifier is significantly better than a baseline. This is invalid. The model was selected from 15 candidates based on test-set performance. The test set has been incorporated into the model selection process. The 88% is optimistically biased, and the associated p-value is incorrect.

The Correct Approach

Split data into three portions: train, dev, test. Use the dev set for all iterative development (feature selection, hyperparameter tuning, model selection). Only when the final model is locked down, evaluate once on the test set and report that single number as the honest performance estimate. The test set is touched exactly once.

Connection to the Sign Test

The same logic applies to significance testing between systems. If you run a sign test on the test set, then tweak the system and run another sign test on the same test set, you are performing multiple comparisons. The second test’s p-value is invalid unless corrected. The test set must be held out from all development and only used for one pre-planned significance test.

Summary

Past paper questions: y2021p3q9 (evaluation strategy)

Purpose

The sign test determines whether System A is significantly better than System B on a classification task. It tests the null hypothesis that both systems are equally good and any observed differences are due to chance.

Setup

• H0 (null hypothesis): Systems A and B are identical; differences are due to chance.
• H1 (alternative): System A is better than System B (one-tailed) or systems differ (two-tailed).
• Compare item by item: for each document, note whether A wins, B wins, or they tie.

The MLRD Tie Rule (CRITICAL)

Standard statistics textbooks say to discard ties. For classification tasks, this is wrong. Discarding ties reduces $N$, inflating the test statistic and causing a Type 1 error (falsely claiming significance).

The MLRD rule: distribute ties evenly. Let $d$ = number of ties. Add $d/2$ to $k$ (A’s wins) and $d/2$ to $(N - k)$ (B’s wins). Round $k$ up at the end. $N$ remains unchanged.

Test Statistic

Under H0, each item is equally likely to favour A or B (ignoring ties). Test statistic:

$X \sim \text{Binomial}(N, p = 0.5)$

$k = \text{items where A beats B} + \frac{d}{2}$

• One-tailed p-value: $P(X \geq k \mid N, p=0.5)$
• Two-tailed p-value: $2 \times P(X \geq k \mid N, p=0.5)$

If $p \leq 0.05$: reject H0; A is significantly better. If $p > 0.05$: inconclusive; cannot claim A is better.

Full Worked Example

200 documents are classified by both System A and System B:

• A wins on 110 documents
• B wins on 70 documents
• Ties on 20 documents

Step 1 — Apply the tie rule: $k = 110 + 20/2 = 110 + 10 = 120$ $N = 200$ (unchanged) $(N - k) = 200 - 120 = 80$

Step 2 — Two-tailed test: We test whether A differs from B (in either direction). Under H0, $X \sim \text{Binomial}(200, 0.5)$.

$p = 2 \times P(X \geq 120 \mid N=200, p=0.5)$

For a binomial with $N=200$, $p=0.5$, the mean is $Np = 100$ and variance is $Np(1-p) = 50$. We can approximate using the normal distribution:

$z = \frac{k - Np}{\sqrt{Np(1-p)}} = \frac{120 - 100}{\sqrt{50}} = \frac{20}{7.071} \approx 2.828$

From standard normal tables: $P(Z \geq 2.828) \approx 0.0023$.

Two-tailed $p = 2 \times 0.0023 = 0.0046$.

Step 3 — Conclusion: $p = 0.0046 < 0.05$. Reject H0. System A is significantly better than System B.

If we had discarded ties (wrong): $N = 180$, $k = 110$, $z = (110 - 90)/\sqrt{45} = 20/6.708 \approx 2.981$, giving a smaller p-value. This inflates the apparent significance, risking a false claim.

Why Not Discard Ties?

Discarding ties reduces $N$ from 200 to 180. The test statistic $z = (k - N/2)/\sqrt{N/4}$ increases because the denominator $\sqrt{N}$ shrinks while the numerator stays similar. This makes the test more likely to reject H0 even when A and B are truly identical (Type 1 error). The MLRD rule keeps $N$ fixed and distributes ties as half-wins, which is more conservative and honest.

Summary

Past paper questions: y2023p3q8 (evaluation methods)

Purpose

The permutation test (also called the randomisation test) is a more powerful alternative to the sign test for determining whether System A is significantly better than System B. It naturally handles ties without the MLRD special tie rule, because it operates on the actual metric values rather than win/loss/tie counts.

Intuition

Under H0, both systems are equally good: their predictions for any given document are interchangeable. If we randomly swap the predictions of A and B for some documents, the overall performance difference should not systematically change. If the observed difference is larger than what we would see under random swapping, we have evidence that A is genuinely better.

Procedure

1. Compute observed difference: $\Delta_{\text{obs}} = \text{metric}(A) - \text{metric}(B)$, e.g., the difference in F1 scores.

2. Enumerate permutations: There are $2^N$ possible ways to swap predictions between A and B (for each of $N$ documents, either swap or do not swap).

3. For each permutation: apply the swaps, recompute $\Delta_{\text{perm}}$, and record the result.

4. Compute p-value: the proportion of permutations where $\vert \Delta_{\text{perm}} \rvert \geq \vert \Delta_{\text{obs}} \rvert$ (two-tailed) or $\Delta_{\text{perm}} \geq \Delta_{\text{obs}}$ (one-tailed).

5. Decision: if $p \leq 0.05$, reject H0.

Monte Carlo Approximation

For $N = 100$ documents, $2^{100}$ permutations is impossible to enumerate. In practice, we use a Monte Carlo permutation test: randomly sample a large number of permutations (e.g., 10,000) rather than exhaustively enumerating all. The p-value is the proportion of sampled permutations where the difference meets or exceeds the observed one.

Why More Powerful Than the Sign Test

The sign test reduces each document to a ternary outcome (A wins, B wins, tie) and discards the magnitude of the difference. If A beats B by a tiny margin on 60 documents and loses by a huge margin on 40, the sign test treats the 60 as “wins” and the 40 as “losses”, potentially missing the fact that B’s victories are much larger.

The permutation test uses the actual metric values. It captures both the direction and the magnitude of each difference. Ties are naturally absorbed into the metric, since identical predictions produce a difference of zero.

Worked Example

Suppose we have 10 documents. System A achieves F1 = 0.82; System B achieves F1 = 0.74. The observed difference: $\Delta_{\text{obs}} = 0.08$.

Under H0, each document’s pair of predictions (A’s label, B’s label) can be swapped or left as-is. We generate 1,000 random permutations. In each, we randomly swap the predictions for a random subset of documents, recompute F1 for both systems, and compute $\Delta_{\text{perm}}$.

Suppose 23 out of 1,000 permutations produce $\vert \Delta_{\text{perm}} \rvert \geq 0.08$.

$p = 23/1000 = 0.023$

Since $0.023 < 0.05$, reject H0. System A’s improvement is statistically significant.

Summary

Past paper questions: y2023p3q8 (evaluation)

The Four Outcomes

Every significance test yields one of four outcomes, depending on the true state of the world and the test’s conclusion:

Type 1 Error (False Positive, $\alpha$)

Rejecting H0 when it is actually true: claiming System A is better when it is not. The significance level $\alpha = 0.05$ means we accept a 5% chance of committing a Type 1 error every time we run a test.

If we run 20 independent tests at $\alpha = 0.05$, the expected number of Type 1 errors is 1. This is the multiple comparisons problem: across many tests, some will appear significant purely by chance.

Type 2 Error (False Negative, $\beta$)

Failing to reject H0 when it is actually false: missing a real improvement. $\beta$ is the probability of a Type 2 error. Unlike $\alpha$ (which we set explicitly), $\beta$ depends on the true effect size, sample size, and test power. A small sample makes $\beta$ large: real differences go undetected.

Power ($1 - \beta$)

The probability of correctly rejecting a false H0: detecting a real difference when one exists. Higher power is better. Power increases with:

• Larger sample size $N$
• Larger true effect size
• More sensitive test (permutation test is more powerful than sign test)

A test with low power cannot reliably detect real improvements. If you fail to reject H0 with a small dataset, you cannot conclude “A and B are the same”; you can only conclude “the data are insufficient to tell.”

Specificity ($1 - \alpha$)

The probability of correctly not rejecting a true H0: guarding against false discoveries. If $\alpha = 0.05$, specificity = 0.95. Raising the significance threshold (e.g., $\alpha = 0.01$) increases specificity but reduces power.

The Trade-Off

$\alpha$ and $\beta$ are in tension. Lowering $\alpha$ (making it harder to reject H0) reduces Type 1 errors but increases Type 2 errors (since you need stronger evidence to reject). Raising $\alpha$ increases power but also increases false positives.

The standard $\alpha = 0.05$ balances Type 1 and Type 2 errors for most applications. In safety-critical domains (medical treatment), a lower $\alpha$ (more conservative) may be warranted to avoid false positives. In exploratory research, a higher $\alpha$ may be acceptable to avoid missing genuine signals.

Worked Example

A sign test on 200 documents compares two spam filters. H0: filters are equally good. The observed test statistic gives $p = 0.03$. We reject H0 at $\alpha = 0.05$ and conclude Filter A is significantly better.

If H0 were actually true (filters are identical), we have committed a Type 1 error: the significant result was a fluke. There is a 5% chance of this occurring, and it did.

If H0 were actually false (Filter A is genuinely better) and we had instead obtained $p = 0.07$, we would fail to reject H0: a Type 2 error. The test lacked power to detect a real difference.

Summary

Past paper questions: y2023p3q8 (evaluation)

Why Raw Agreement Misleads

If two annotators label items independently, simply counting how often they agree gives a misleading picture. Even if both annotators guess randomly, they will agree by chance some fraction of the time. With few classes (e.g., binary labels), chance agreement can be high: two annotators both guessing “OK” 50% of the time agree by chance 50% of the time.

Cohen’s $\kappa$ corrects for this: it measures agreement above chance, normalised by the maximum possible agreement above chance.

Formula

$\kappa = \frac{P(A) - P(E)}{1 - P(E)}$

• $P(A)$: observed agreement — proportion of items where both annotators gave the same label.
• $P(E)$: expected chance agreement — the probability they would agree if both guessed independently based on their observed label distributions.

$P(E) = \sum_{c \in \text{Classes}} P(\text{Ann}_1 \text{ chooses } c) \times P(\text{Ann}_2 \text{ chooses } c)$

Interpretation

• $\kappa = 1.0$: perfect agreement
• $\kappa > 0.8$: strong agreement
• $\kappa > 0.6$: acceptable agreement
• $\kappa = 0.0$: no better than chance
• $\kappa < 0$: worse than chance (systematic disagreement)

Full Worked Example (2023 Q7)

Two annotators (A and B) classify 8 items into 4 classes (I, II, III, IV). Data:

Step 1 — Observed agreement $P(A)$: Items where A = B: item 1 (III=III), item 3 (II=II), item 6 (I=I), item 7 (IV=IV).

$P(A) = 4/8 = 0.5$

Step 2 — Marginal frequencies for A:

• $P_A(\text{I}) = 2/8 = 0.25$
• $P_A(\text{II}) = 3/8 = 0.375$
• $P_A(\text{III}) = 1/8 = 0.125$
• $P_A(\text{IV}) = 2/8 = 0.25$

Step 3 — Marginal frequencies for B:

• $P_B(\text{I}) = 3/8 = 0.375$
• $P_B(\text{II}) = 1/8 = 0.125$
• $P_B(\text{III}) = 1/8 = 0.125$
• $P_B(\text{IV}) = 3/8 = 0.375$

Step 4 — Expected chance agreement $P(E)$:

$P(E) = (0.25 \times 0.375) + (0.375 \times 0.125) + (0.125 \times 0.125) + (0.25 \times 0.375)$

$P(E) = 0.09375 + 0.046875 + 0.015625 + 0.09375 = 0.25$

Step 5 — Compute $\kappa$:

$\kappa = \frac{0.5 - 0.25}{1 - 0.25} = \frac{0.25}{0.75} = 0.333$

Interpretation: moderate agreement, well above chance ($\kappa = 0.0$) but far from strong ($\kappa > 0.8$). The annotators do better than random guessing but disagree substantially.

Why This Matters for ML

If human annotators achieve only $\kappa = 0.333$ on a task, a classifier trained on their labels cannot realistically exceed that performance. The inter-annotator agreement sets an upper bound on achievable classifier accuracy. Low $\kappa$ indicates the task itself is subjective, and the “ground truth” labels are noisy.

Summary

Past paper questions: y2023p3q7(b), y2021p3q9(c)

When Cohen’s Kappa Is Not Enough

Cohen’s $\kappa$ works for exactly two annotators. When you have three or more annotators (e.g., a crowd of workers each labelling items), you need Fleiss’ $\kappa$, which generalises the chance-corrected agreement measure to an arbitrary number of raters.

Notation

• $N$: number of items
• $k$: number of annotators per item (can vary per item in the generalised version)
• $C$: number of categories (classes)
• $n_{ij}$: number of annotators who assigned category $j$ to item $i$

Formula

Observed agreement per item:

$P_{a,i} = \frac{\sum_{j=1}^{C} n_{ij}(n_{ij} - 1)}{k(k - 1)}$

The numerator counts agreeing pairs for item $i$ (summed over categories). The denominator is the total number of annotator pairs for that item. The factor of 2 in the combination formula cancels between numerator and denominator.

Overall observed agreement:

$P_a = \frac{1}{N} \sum_{i=1}^{N} P_{a,i}$

Expected chance agreement:

For each category $j$, compute the overall proportion of all annotations assigned to that class:

$p_j = \frac{\sum_{i=1}^{N} n_{ij}}{N \times k}$

Then:

$P_e = \sum_{j=1}^{C} p_j^2$

Fleiss’ $\kappa$:

$\kappa = \frac{P_a - P_e}{1 - P_e}$

Interpretation follows the same scale as Cohen’s $\kappa$.

Full Worked Example

Three annotators (A, B, C) label 3 items as POS or NEG:

Here $N=3$, $k=3$, $C=2$.

Step 1 — $n_{ij}$ counts:

Step 2 — $P_{a,i}$ per item:

Item 1: $P_{a,1} = [2(2-1) + 1(1-1)] / [3(3-1)] = [2 + 0] / 6 = 0.333$

Item 2: $P_{a,2} = [1(1-1) + 2(2-1)] / 6 = [0 + 2] / 6 = 0.333$

Item 3: $P_{a,3} = [3(3-1) + 0(0-1)] / 6 = [6 + 0] / 6 = 1.0$

Step 3 — Overall $P_a$:

$P_a = (0.333 + 0.333 + 1.0) / 3 = 1.667 / 3 = 0.556$

Step 4 — Category proportions $p_j$:

Total annotations = $3 \times 3 = 9$. POS annotations = $2 + 1 + 3 = 6$, so $p_{\text{POS}} = 6/9 = 0.667$. NEG annotations = $1 + 2 + 0 = 3$, so $p_{\text{NEG}} = 3/9 = 0.333$.

Step 5 — Expected chance agreement $P_e$:

$P_e = 0.667^2 + 0.333^2 = 0.444 + 0.111 = 0.556$

Step 6 — Fleiss’ $\kappa$:

$\kappa = \frac{0.556 - 0.556}{1 - 0.556} = \frac{0}{0.444} = 0.0$

Interpretation: agreement is no better than chance. Despite $P_a = 0.556$ looking modestly above 50%, the chance correction reveals that the observed agreement is exactly what random guessing with the observed label proportions would produce.

Summary

Past paper questions: y2023p3q7(b), y2021p3q9(c)

The Problem

In real annotation projects, annotators often cover different subsets of items. For example, Annotator D labels items 3-8 whilst Annotator E labels items 1-8. A naive approach is to merge D and E into one “fake” annotator and treat the combined labels as if from a single rater. This creates several problems.

Why Merging D and E Is Wrong

1. Different conditions. D’s decisions on items 3-8 were made at a different time and possibly under different instructions or conditions than E’s decisions on items 1-8. Merging conflates these.

2. Arbitrary bias from discarding. For items both annotated (3-8), you would need to throw away one annotation to avoid duplication. The choice of which to discard introduces arbitrary bias into the dataset.

3. Inconsistent coverage. The “merged” annotator has an inconsistent coverage pattern: some items have one label, some have two. This makes comparisons across items unfair.

4. Asymmetric weighting. If D covered more items than E, the “merged” annotator’s label distribution is skewed toward D’s tendencies. The merged pseudo-annotator is not a real rater; it is a statistical artefact.

The Correct Approach

Adapt Fleiss’ $\kappa$ (or Cohen’s $\kappa$) to handle variable annotator coverage:

1. Calculate $P_a$ only over overlapping items. An item contributes to $P_a$ only if it was labelled by at least two of the full annotator set. For items labelled by only one annotator, no agreement can be computed; they are excluded from the numerator.

2. Calculate $P_e$ from all available annotations. The marginal proportions $p_j$ (how often each class is chosen) are computed across the full dataset, including items with only one label. This gives unbiased estimates of each class’s overall frequency.

3. Use per-item $k$. The denominator $k(k-1)$ for each item uses the number of annotators who actually labelled that specific item, not a global $k$. An item labelled by 2 annotators uses $2 \times 1 = 2$; an item labelled by 5 annotators uses $5 \times 4 = 20$.

Example

Consider a dataset with 5 annotators {A, B, C, D, E} and 8 items. A, B, and C label all 8 items. D labels items 3-8. E labels items 1-8.

For computing $P_a$:

• Items 3-8 are labelled by all 5 annotators: $P_a$ uses these 6 items with $k=5$.
• Items 1-2 are labelled by A, B, C, E: $P_a$ uses these 2 items with $k=4$.

For computing $P_e$:

• All 8 items contribute to the marginal proportions $p_j$.
• Total annotations = $(3 \times 8) + 6 + 8 = 38$ (not $5 \times 8 = 40$).

The global $P_a$ is the mean of per-item $P_{a,i}$ values across all items that have at least 2 annotators.

Why This Matters

Partial annotation is the norm in practical projects. Crowd workers drop out, annotators have different availability, and budgets constrain coverage. Using the correct per-item $k$ and overlapping-only $P_a$ prevents inflated or deflated agreement estimates that would misrepresent annotation quality.

Summary

Past paper questions: y2023p3q7(c)

Why Crowdsourcing Annotations Is Difficult

Crowdsourcing platforms distribute annotation tasks to many workers, each labelling a small batch of items. Whilst this is cheap and fast, it introduces several problems that make standard inter-annotator agreement metrics unreliable or impossible to compute.

Problem 1: Very Small Batches

When each worker annotates only 2-3 items, the variance in per-worker agreement estimates is enormous. A worker who happens to get two easy items looks excellent; a worker who gets two ambiguous items looks terrible. Neither estimate is reliable. With large batches (20+ items per worker), you can form stable per-worker quality estimates; with 2 items, you cannot.

Problem 2: Random Assignment Breaks Pairwise Kappa

Crowd workers are typically assigned random subsets of items. With hundreds of workers each labelling a few items, many annotator pairs never share a single item. Cohen’s $\kappa$ requires pairs to have at least some overlapping items. Pairwise agreement between workers who never labelled the same thing cannot be computed.

Fleiss’ $\kappa$ partially solves this (it pools all annotators), but still assumes most items have multiple labels, which may not hold if workers are spread thinly.

Problem 3: Variable Worker Quality

Crowd workers vary widely in skill and motivation. Some are diligent experts; others spam randomly to maximise payment per unit time. A worker who labels everything “POS” will agree with other workers purely by chance on balanced datasets. Simple agreement metrics cannot distinguish genuine skill from lucky guessing or systematic spamming.

Solutions: include gold-standard items (with known labels) to filter low-quality workers; use worker-specific quality weights in the agreement calculation; reject workers whose accuracy on gold items falls below a threshold.

Problem 4: No Inter-Section Consistency Check

Large annotation projects often divide items into sections, with different worker pools per section. If no workers label items across sections, there is no way to check whether labelling standards are consistent between sections. Section A’s annotators might interpret the guidelines differently from Section B’s. The resulting dataset has systematic bias between sections, but no agreement metric will reveal it because there is no overlap to measure against.

Solution: allocate a shared subset of items across all sections. These overlap items serve as a consistency check, allowing computation of agreement between sections.

Summary

Past paper questions: y2023p3q7(c)(ii-iii)

Tokens vs Types

Given the sentence “The cat sat on the mat.”:

• Token: each occurrence of a word. There are 6 tokens: “The”, “cat”, “sat”, “on”, “the”, “mat”. Count includes repetitions.
• Type: each unique word in the vocabulary. There are 5 types: {“the”, “cat”, “sat”, “on”, “mat”}. “The” and “the” are the same type after lowercasing.

Token count $N$ = total words in corpus. Type count $\lvert V \rvert$ = vocabulary size.

Lexicon-Based Classification

A lexicon is a dictionary mapping words to polarities. A simple sentiment lexicon:

To classify a document: sum the polarities of all lexicon words found. If the sum is positive, classify as positive; negative sum means negative; zero means neutral.

Weaknesses

1. Ignores context. “This film is not good” sums to +1 (from “good”), classified as positive. The negation is missed entirely, because the lexicon contains only unigrams.

2. Cannot handle unseen words. If the document contains “This film is abysmal” and “abysmal” is not in the lexicon, it contributes zero. The document is classified as neutral, missing clear negative sentiment.

3. Fixed vocabulary. Domain shifts break lexicon approaches. A general sentiment lexicon may not capture domain-specific language (e.g., “sick” in gaming communities means “impressive”, not “ill”).

4. No weighting by importance. All lexicon words contribute equally regardless of their discriminating power. “Good” is a weak signal; “masterpiece” is strong. A lexicon with magnitudes (+1, +2, -1, -2) partially addresses this but requires manual calibration.

Lexicon vs Naive Bayes

Lexicon-based classification works when:

• Very little labelled training data is available
• Explicit, inspectable rules are needed
• The domain is well covered by existing lexicons

Naive Bayes works when:

• Sufficient labelled training data exists
• Statistical patterns capture subtle distinctions
• Domain language differs from standard lexicons

The two can be combined: replace words with generic <POSITIVE_WORD> / <NEGATIVE_WORD> tokens before training Naive Bayes. This bridges the lexicon’s generalisation with the classifier’s ability to learn from data.

Summary

Past paper questions: y2021p3q9(e)(ii-iii), y2025p3q7(a)

The Law

Word frequency is inversely proportional to frequency rank. A small number of words are very frequent; a huge number of words are rare.

Basic form:

$f_w \propto \frac{1}{r_w}$

where $f_w$ is the frequency of word $w$ and $r_w$ is its rank (1 = most frequent).

General form:

$f_w \approx \frac{k}{(r_w + \beta)^\alpha}$

• $f_w$: frequency of word $w$ in the corpus
• $r_w$: frequency rank (1 = most frequent)
• $\alpha$: exponent (~1.0 for English, ~1.3 for German)
• $k$, $\beta$: language-specific constants

Log-Log Estimation

Taking logs of the basic form:

$\log(f_w) = \log(k) - \alpha \cdot \log(r_w)$

Plotting $\log(\text{frequency})$ against $\log(\text{rank})$ gives a straight line:

• Slope = $-\alpha$ (estimate $\alpha$ from the slope)
• Y-intercept = $\log(k)$ (estimate $k = e^{\text{intercept}}$)

Estimate $\alpha$ and $k$ by fitting a least-squares regression to the log-log plot.

The Long Tail

In a typical English corpus:

• The top 10 words (the, of, and, to, a, …) account for ~25% of all tokens.
• The top 100 words account for ~50%.
• Thousands of words appear only once (hapax legomena).
• The tail is very long: a huge number of word types each appear very few times.

Consequence for Classification

The long tail means that even a large training corpus misses many word types. Any new document is likely to contain words never seen during training. For a Naive Bayes classifier without smoothing:

$P(w \mid c) = \frac{\text{count}(w, c)}{\sum_{w'} \text{count}(w', c)} = 0 \quad \text{for any unseen } w$

A single unseen word makes the entire product $P(c) \times \prod P(w_i \mid c)$ equal to zero. The classifier breaks.

This is why Laplace smoothing is not optional — Zipf’s Law guarantees that unseen words are ubiquitous, not rare exceptions.

Worked Example

Consider “the” (rank 1, frequency ~70,000 per million words) and “antidisestablishmentarianism” (estimated rank ~50,000, frequency < 1 per million). The ratio is roughly 70,000:1, consistent with $\alpha \approx 1$.

If a test document uses a rare word not in the training data (and there are tens of thousands of such words in the long tail), the unsmoothed NB classifier assigns probability zero to every class. Smoothing fixes this by shifting a small amount of probability mass from frequent words to the long tail.

Summary

Past paper questions: y2024p3q7 (feature engineering sub-question)

The Law

As a corpus grows, its vocabulary keeps growing, but with diminishing returns. No matter how much text you collect, you will always encounter new word types.

$\lvert V \rvert = k \times N^\beta$

• $\lvert V \rvert$: vocabulary size (number of unique types)
• $N$: total number of tokens in the corpus
• $\beta$: exponent, typically 0.4-0.6
• $k$: language-dependent constant, typically 30-100

Log-Log Estimation

Taking logs:

$\log\lvert V \rvert = \log(k) + \beta \cdot \log(N)$

Plot $\log(\text{vocabulary size})$ against $\log(\text{total tokens})$. The result is a straight line:

• Slope = $\beta$
• Y-intercept = $\log(k)$

Why Growth Diminishes

When only 100 tokens have been seen, each new token is likely to be a new type. After 10,000 tokens, most new tokens are repeats of known words. After 1 million tokens, genuinely new types are rare. Yet mathematically, $\lvert V \rvert$ never plateaus: it grows as $N^\beta$, which is unbounded (albeit slowly).

With $\beta = 0.5$: doubling $N$ increases $\lvert V \rvert$ by a factor of $2^{0.5} \approx 1.41$. Quadrupling $N$ doubles $\lvert V \rvert$.

Heaps’ Law and Zipf’s Law: The Connection

Zipf’s Law explains the shape of the frequency distribution (many rare words). Heaps’ Law explains the growth of vocabulary with corpus size (unbounded new types). Together they tell a single story: the tail of rare words is not only long but also inexhaustible. Collecting more data reduces but never eliminates the problem of unseen words.

Consequence for Classification

Smoothing is a mathematical necessity, not a pragmatic convenience. Heaps’ Law guarantees that:

1. Any finite training corpus will have an incomplete vocabulary.
2. New text will contain types never seen in training, regardless of training corpus size.
3. Without smoothing, $P(w \mid c) = 0$ for unseen words, collapsing all class probabilities to zero.

This is the theoretical justification for Laplace (add-one) smoothing: it assigns non-zero probability to the infinite set of possible but unseen word types by reserving a portion of the probability mass.

Summary

Past paper questions: y2024p3q7 (feature engineering)

Core Idea

Given a document $d$ and a set of classes $C$, find the class with the highest posterior probability:

$c^* = \underset{c \in C}{\text{argmax}} \ P(c \mid d)$

By Bayes’ Theorem:

$P(c \mid d) = \frac{P(c) \times P(d \mid c)}{P(d)}$

Since $P(d)$ is constant across all classes for a given document, we drop it:

$c^* = \underset{c \in C}{\text{argmax}} \ P(c) \times P(d \mid c)$

The Naive Assumption

The “naive” part: all features (words) are independent given the class. This lets us decompose the document probability into a product:

$P(d \mid c) = \prod_{i=1}^{n} P(w_i \mid c)$

where $w_1, w_2, \dots, w_n$ are the words in the document. The full classification rule:

$c^* = \underset{c \in C}{\text{argmax}} \ P(c) \times \prod_{i=1}^{n} P(w_i \mid c)$

Parameter Estimation (Unsmoothed MLE)

Prior:

$P(c) = \frac{N_c}{N_{\text{total}}}$

where $N_c$ is the number of training documents of class $c$.

Likelihood (Maximum Likelihood Estimate, no smoothing):

$P(w \mid c) = \frac{\text{count}(w, c)}{\sum_{w' \in V} \text{count}(w', c)}$

where $\text{count}(w, c)$ is the number of times word $w$ appears in documents of class $c$, and $V$ is the vocabulary.

The Zero-Probability Problem

If any word $w$ in the test document never appeared with class $c$ in training, then $\text{count}(w, c) = 0$, so $P(w \mid c) = 0$. The product $\prod P(w_i \mid c)$ becomes zero. If this happens for all classes, the classifier cannot decide.

Even one unseen word kills the entire product. This is not a rare edge case: Zipf’s Law and Heaps’ Law guarantee that test documents will contain unseen words.

Worked Example (Small 3-Word Problem)

Training data (2 classes, SPAM and HAM):

SPAM documents: “buy now”, “free buy” HAM documents: “meeting now”, “free lunch”

Vocabulary $V = \{\text{buy}, \text{now}, \text{free}, \text{meeting}, \text{lunch}\}$, $\lvert V \rvert = 5$.

Token counts per class:

• SPAM: buy=2, now=1, free=1 (3 tokens total)
• HAM: meeting=1, now=1, free=1, lunch=1 (4 tokens total)

Priors: $P(\text{SPAM}) = 2/4 = 0.5$, $P(\text{HAM}) = 2/4 = 0.5$.

Likelihoods (unsmoothed):

• $P(\text{buy} \mid \text{SPAM}) = 2/3 \approx 0.667$
• $P(\text{buy} \mid \text{HAM}) = 0/4 = 0$ (never seen with HAM)

Classify test document “buy lunch”:

$P(\text{SPAM} \mid \text{"buy lunch"}) \propto 0.5 \times (2/3) \times P(\text{lunch} \mid \text{SPAM})$

$P(\text{lunch} \mid \text{SPAM}) = 0/3 = 0$ (never seen with SPAM).

$P(\text{HAM} \mid \text{"buy lunch"}) \propto 0.5 \times P(\text{buy} \mid \text{HAM}) \times (1/4)$

$P(\text{buy} \mid \text{HAM}) = 0/4 = 0$ (never seen with HAM).

Both products collapse to zero. The classifier cannot choose. This is exactly what Laplace smoothing prevents.

Interpretability

Naive Bayes is interpretable: every parameter $P(w \mid c)$ is directly inspectable. If a feature value appears only with one class in training, you can identify the bias mathematically (e.g., $P(\text{Gender=F} \mid \text{Success}) = 0$ means the classifier can never predict Success for Female applicants). This property is invaluable for fairness auditing and is not available in black-box models.

Summary

Past paper questions: y2021p3q9(a), y2023p3q8(a), y2024p3q9(a)

The Problem

Without smoothing, any word never seen with class $c$ in training gets $P(w \mid c) = 0$. One unseen word makes the entire Naive Bayes product collapse to zero. Zipf’s Law and Heaps’ Law guarantee that unseen words are ubiquitous.

Laplace (Add-One) Smoothing

Add 1 to every word count and add $\lvert V \rvert$ to the denominator:

$P(w \mid c) = \frac{\text{count}(w, c) + 1}{\sum_{w' \in V} \text{count}(w', c) + \lvert V \rvert}$

• $\lvert V \rvert$: total number of unique word types across all training data (all classes combined)
• Effect: shifts a small amount of probability mass from seen words to unseen ones
• Every word type, even those never seen in training, now has $P(w \mid c) > 0$

General Smoothing Parameter $\omega$

$P(w \mid c) = \frac{\text{count}(w, c) + \omega}{\sum_{w' \in V} \text{count}(w', c) + \omega \times \lvert V \rvert}$

Laplace smoothing is the special case $\omega = 1$. The parameter $\omega$ can be tuned on the development set: try $\omega = 0.1, 0.5, 1.0, 2.0$ and pick the value that maximises dev-set accuracy or F1.

Worked Example

Revisiting the small 2-class problem from the Naive Bayes note.

Training data:

• SPAM documents: “buy now”, “free buy”
• HAM documents: “meeting now”, “free lunch”

Vocabulary $V = \{\text{buy}, \text{now}, \text{free}, \text{meeting}, \text{lunch}\}$, $\lvert V \rvert = 5$.

Smoothed likelihoods:

SPAM class (total tokens = 3):

$P(\text{buy} \mid \text{SPAM}) = \frac{2 + 1}{3 + 5} = \frac{3}{8} = 0.375$

$P(\text{now} \mid \text{SPAM}) = \frac{1 + 1}{3 + 5} = \frac{2}{8} = 0.25$

$P(\text{free} \mid \text{SPAM}) = \frac{1 + 1}{3 + 5} = \frac{2}{8} = 0.25$

$P(\text{meeting} \mid \text{SPAM}) = \frac{0 + 1}{3 + 5} = \frac{1}{8} = 0.125$

$P(\text{lunch} \mid \text{SPAM}) = \frac{0 + 1}{3 + 5} = \frac{1}{8} = 0.125$

HAM class (total tokens = 4):

$P(\text{meeting} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{now} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{free} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{lunch} \mid \text{HAM}) = \frac{1 + 1}{4 + 5} = \frac{2}{9} \approx 0.222$

$P(\text{buy} \mid \text{HAM}) = \frac{0 + 1}{4 + 5} = \frac{1}{9} \approx 0.111$

Classify “buy lunch”:

Priors: $P(\text{SPAM}) = 0.5$, $P(\text{HAM}) = 0.5$.

$P(\text{SPAM} \mid d) \propto 0.5 \times 0.375 \times 0.125 = 0.5 \times 0.046875 = 0.02344$

$P(\text{HAM} \mid d) \propto 0.5 \times 0.111 \times 0.222 = 0.5 \times 0.02464 = 0.01232$

The classifier predicts SPAM. Without smoothing, both products were zero; the classifier could not choose. With Laplace smoothing, every word has non-zero probability, and the classifier works correctly.

Exam Rule

Apply smoothing whenever the question does not explicitly say “without smoothing”. Always state $\lvert V \rvert$ explicitly as the denominator correction.

Summary

Past paper questions: y2021p3q9(a), y2023p3q8(a), y2024p3q9(a)

The Underflow Problem

The Naive Bayes classification rule multiplies many small probabilities:

$P(c) \times \prod_{i=1}^{n} P(w_i \mid c)$

With Laplace smoothing, a typical $P(w \mid c)$ might be ~0.001. For a document with 100 words, the product is roughly $(10^{-3})^{100} = 10^{-300}$. Standard 64-bit floating-point numbers can represent values down to approximately $10^{-308}$ before hitting zero. A 100-word document is close to this boundary; longer documents or smaller probabilities push the product to exactly zero on the computer.

Floating-point underflow turns a mathematically valid (but tiny) number into zero. When this happens, the classifier loses all discriminative information: every class product becomes zero, and the argmax is meaningless.

Solution: Work in Log Space

Since $\log$ is strictly monotonically increasing, the argmax is identical:

$c^* = \underset{c \in C}{\text{argmax}} \ \log\left(P(c) \times \prod_{i=1}^{n} P(w_i \mid c)\right)$

$c^* = \underset{c \in C}{\text{argmax}} \ \left[ \log P(c) + \sum_{i=1}^{n} \log P(w_i \mid c) \right]$

The product becomes a sum of log-probabilities. Each $\log P(w \mid c)$ is a moderate negative number (e.g., $\log(0.001) = -6.91$). For 100 words, the sum is roughly $-691$, which is easily representable.

Why This Works

Logarithms map multiplication to addition:

$\log(a \times b) = \log(a) + \log(b)$

For three probabilities:

$\log(P(c) \times P(w_1 \mid c) \times P(w_2 \mid c)) = \log P(c) + \log P(w_1 \mid c) + \log P(w_2 \mid c)$

Each term is a negative number. The sum grows (becomes more negative) linearly with document length, rather than exponentially shrinking toward zero.

Worked Example

Classify a 10-word document with two classes. Smoothed probabilities:

Priors: $P(\text{A}) = 0.6$, $P(\text{B}) = 0.4$.

In probability space (dangerous):

$P(\text{A} \mid d) \propto 0.6 \times (0.001 \times 0.003 \times 0.0005 \times \dots)$

The product is approximately $10^{-34}$, still representable for 10 words, but for 100 words it would underflow.

In log space (safe):

$\log P(\text{A}) = \log(0.6) = -0.511$

$\sum \log P(w_i \mid \text{A}) = \log(0.001) + \log(0.003) + \log(0.0005) + \dots = -6.908 + (-5.809) + (-7.601) + \dots$

Sum for A: $-0.511 + (-65.2) = -65.7$. Sum for B: $\log(0.4) + (-58.4) = -0.916 + (-58.4) = -59.3$.

Since $-59.3 > -65.7$, the classifier predicts Class B. The log-space computation is numerically stable for documents of any length.

Implementation Note

Always convert to log space immediately after computing smoothed probabilities. Pre-compute $\log P(w \mid c)$ for every word-class pair during training. At classification time, sum the pre-computed log values for the words in the document and add $\log P(c)$. The class with the largest (least negative) sum wins.

Summary

Past paper questions: y2021p3q9(a)

Why Feature Engineering Matters

Raw text produces a sparse, high-dimensional feature space. Naive Bayes’ independence assumption becomes less tenable, and zero-probability events proliferate. Feature engineering reduces sparsity and improves generalisation to unseen data.

Lowercasing

Convert all text to lowercase: “Running” and “running” become the same type.

Why it helps: Reduces vocabulary size without losing discriminative information. Capitalisation rarely carries class-relevant signal in standard text classification. A halved vocabulary means fewer unseen-word events and more reliable probability estimates per type.

Stemming and Lemmatisation

Map morphological variants to a common root:

• “argued”, “arguing”, “argues”, “argument” → “argu” (stemming)
• “better”, “good” → “good” (lemmatisation, handles irregular forms)

Why it helps: Groups related forms together, increasing the count for each root and reducing vocabulary size. The probability estimate for “argu” is based on the combined evidence from all its surface forms, making it more reliable.

Stop-Word Removal

Remove high-frequency function words: “the”, “and”, “is”, “of”, “to”, “a”.

Why it helps: These words appear in every document regardless of class. They carry no discriminative power and add noise. Removing them reduces document length and vocabulary size without affecting the classifier’s ability to separate classes.

Hapax Legomena Removal

Remove words that occur exactly once in the training data (hapax legomena, singular: hapax legomenon).

Why it helps: A word seen only once provides an unreliable probability estimate. It may be a typo, a rare proper noun, or statistical noise. Removing hapaxes reduces vocabulary size and prevents the classifier from overfitting to idiosyncratic training tokens that will never appear again. The trade-off: some rare but genuinely informative words are lost, but the noise reduction usually outweighs this.

Binning Continuous Features

For numerical features (age, income, scores), group values into discrete brackets:

• Age 18, 19, 20 → [17-20]
• Score 72, 88, 91 → [70-80], [80-90], [90-100]

Why it helps: Naive Bayes requires discrete features. A continuous feature like age has potentially infinite values, each with zero or negligible counts. Binning reduces the feature to a small set of categories, each with meaningful probability estimates. The bracket width can be tuned on the development set.

Lexicon Integration

Replace specific words with generic sentiment tokens:

• “awful”, “terrible”, “dreadful” → <NEGATIVE_WORD>
• “excellent”, “wonderful”, “brilliant” → <POSITIVE_WORD>

Why it helps: Unseen synonyms of known sentiment words are mapped to the same token, so the classifier recognises their polarity even without having seen the specific word in training. This handles language change and domain shift: a new slang term for “bad” is still replaced by <NEGATIVE_WORD> if it appears in the lexicon.

Combined Approach

These techniques are not mutually exclusive. A typical pipeline: lowercase → remove stop words → stem → remove hapaxes → replace lexicon words with polarity tokens. The development set guides which combination produces the best held-out performance.

Summary

Past paper questions: y2021p3q9(c)(ii), y2021p3q9(e)(iii), y2024p3q7(d)

Why Naive Bayes Is Interpretable

Naive Bayes is interpretable: you can inspect every parameter — every $P(w \mid c)$, every $P(c)$ — directly from the probability table. You can trace any classification decision back to which specific features contributed which specific probabilities.

The useful property: identify bias immediately by scanning the parameter table for zeros. If $P(\text{feature} \mid \text{class}) = 0$, that class can never be predicted when that feature is present. You can prove this mathematically with two test instances.

The problematic property: zero probabilities propagate. Multiplying small probabilities together means one zero anywhere in the product makes the entire posterior zero — the classifier becomes completely insensitive to all other evidence. A single unseen word or feature value kills the classifier for that instance.

This interpretability is impossible with black-box models (neural networks, random forests, SVMs). You cannot inspect individual parameters, trace decisions to specific training examples, or construct guaranteed counter-examples.

The 4-Step Method for Proving Bias

To mathematically demonstrate that a classifier is biased against a protected group:

1. Identify a protected attribute (Gender, Ethnicity, Nationality, Age).
2. Find a value of that attribute that only appears in one class in the training data (i.e., $P(\text{value} \mid \text{other\_class}) = 0$).
3. Construct two identical test instances differing ONLY in the protected attribute. All other features should appear in both classes (neutral features).
4. Show that the classifier gives different predictions for the two instances, or show $P(\text{class} \mid \text{protected\_value}) = 0$, meaning that class can NEVER be predicted for any instance with that protected value — regardless of all other features.

Full Worked Example: Football Academy (2024 Q9)

Training data: 6 recruits with features Goals (Many/Few/None), Position (Attack/Defender/Goalkeeper), Gender (M/F), and label Success (Y/N).

Step 1 — Priors

$P(Y) = \frac{3}{6} = 0.5 \qquad P(N) = \frac{3}{6} = 0.5$

Step 2 — Likelihoods (MLE, no smoothing)

Goals:

$P(\text{Many} \mid Y) = \frac{1}{3} \quad P(\text{Few} \mid Y) = \frac{1}{3} \quad P(\text{None} \mid Y) = \frac{1}{3}$

$P(\text{Many} \mid N) = 0 \quad P(\text{Few} \mid N) = \frac{2}{3} \quad P(\text{None} \mid N) = \frac{1}{3}$

Position:

$P(\text{Attack} \mid Y) = \frac{2}{3} \quad P(\text{Defender} \mid Y) = \frac{1}{3} \quad P(\text{Goalkeeper} \mid Y) = 0$

$P(\text{Attack} \mid N) = 0 \quad P(\text{Defender} \mid N) = \frac{2}{3} \quad P(\text{Goalkeeper} \mid N) = \frac{1}{3}$

Gender:

$P(\text{M} \mid Y) = 1 \quad P(\text{F} \mid Y) = 0$ $P(\text{M} \mid N) = \frac{2}{3} \quad P(\text{F} \mid N) = \frac{1}{3}$

Bias Group 1: Goalkeepers (Protected: Position)

Protected value: Position = Goalkeeper. Only appears with class N in training.

Test instance: Goals=None, Position=Goalkeeper, Gender=M.

$P(Y \mid \text{instance}) \propto P(Y) \cdot P(\text{None} \mid Y) \cdot P(\text{Goalkeeper} \mid Y) \cdot P(\text{M} \mid Y)$ $= 0.5 \cdot \frac{1}{3} \cdot 0 \cdot 1 = 0$

A Goalkeeper can NEVER be predicted as Successful — regardless of their Goals scored or Gender. The zero from $P(\text{Goalkeeper} \mid Y)$ propagates through the product and wipes out all other information.

Bias Group 2: Female Players (Protected: Gender)

Protected value: Gender = F. Only appears with class N in training.

Test instance: Goals=Many, Position=Attack, Gender=F.

$P(Y \mid \text{instance}) \propto 0.5 \cdot \frac{1}{3} \cdot \frac{2}{3} \cdot 0 = 0$

A Female player can NEVER be predicted as Successful — regardless of their Goals or Position. Every $P(Y \mid \dots)$ is zero the moment Gender=F appears.

Why This Happened

The training data encoded historical discrimination: no Female players and no Goalkeepers appeared in the Successful group. Naive Bayes faithfully reproduced the patterns in the data. This mirrors the London Medical School Admissions case: a program built to replicate human admissions decisions reproduced the gender and ethnic discrimination present in the historical training data. “Fitting the data” does not produce fair decisions if the data itself reflects historical injustice.

Summary

Past paper questions: y2024p3q9

Two Approaches to Text Classification

Naive Bayes is a supervised statistical classifier: it learns $P(w \mid c)$ from labelled training data by counting word-class co-occurrences. The decision rule is:

$c^* = \arg\max_{c} \; P(c) \prod_{i=1}^{n} P(w_i \mid c)$

Lexicon-based classification uses a hand-built dictionary where each word has a pre-assigned polarity or category (e.g., “terrible” → negative, “great” → positive). The decision is typically a sum or majority vote over lexicon matches. No training data is needed.

When Naive Bayes Wins

Naive Bayes is the better choice when:

• Sufficient labelled training data exists. The classifier needs enough examples per class to estimate reliable word probabilities. With thousands of labelled messages, NB can detect subtle statistical patterns.
• Statistical patterns capture subtle discrimination. Combinations of seemingly neutral words (e.g., “you should know your place”) can together signal bullying even though no individual word is in a bullying lexicon. NB captures these co-occurrence patterns.
• Domain language differs from standard lexicons. A general sentiment lexicon performs poorly on specialised domains like gaming slang, medical reports, or legal documents. NB learns the domain-specific vocabulary directly from the labelled data.

When Lexicon-Based Wins

A lexicon is better when:

• Very little labelled data is available. Building a domain lexicon requires modest expert effort but no labelled examples.
• The domain is well-covered by existing lexicons. Sentiment analysis with standard dictionaries (LIWC, VADER, SentiWordNet) needs no training data.
• You need explicit, inspectable rules. A human can read the lexicon and understand exactly which words trigger which decisions. This is essential in regulated settings where decisions must be explainable and auditable.

The Best-of-Both Strategy

Use lexicon tokens as Naive Bayes features: replace specific words with generic category tokens before training.

This hybrid approach provides four advantages:

• Handles unseen synonyms: if “grotesque” is in the lexicon but never appeared in training, it maps to <NEGATIVE> and NB can use it immediately.
• Handles language change: new bullying slang (e.g., “ratio’d”, “mid”) can be added to the lexicon without retraining the full NB model.
• Reduces vocabulary size dramatically: all positive words collapse into one feature, all negative words into another. The vocabulary $|V|$ shrinks, reducing the zero-probability problem and improving smoothing.
• Combines strengths: NB captures word co-occurrence and overall message tone; the lexicon captures expert knowledge about specific words and handles the long tail.

Cyberbullying Detection Example (2021 Q9)

In cyberbullying detection, language change is the critical threat. Younger users constantly invent new words and repurpose existing ones. A fixed NB classifier degrades rapidly.

Building a Cyberbullying Lexicon

Method 1 (new words): track unknown words during classification. If a word suddenly spikes in frequency, sample messages containing it, have them manually labelled, and add the word to the lexicon if bullying-related. The labelled messages become new training data.

Method 2 (new senses): find “maximally surprising” messages where the classifier was confident but wrong. Check whether known words in these messages have acquired a new threatening sense. Add these to the lexicon and use the surprising messages for retraining.

Robustness to Language Change

Run the lexicon-based detector on new messages to cheaply identify likely bullying instances. Use these as new training material for periodic NB retraining. The lexicon acts as a lightweight, continuously-updated scout. Active learning approaches can also help: find the messages where the classifier is most uncertain, have humans label those, and retrain NB.

Evaluation with Lexicons

When a company policy demands “delete as many bullying messages as possible while keeping non-filtered messages high,” this translates to: optimise recall (find all bullying) while maintaining reasonable precision (don’t falsely flag OK messages). Precision and recall — not accuracy — are the right metrics because bullying messages are rare, and accuracy would be dominated by correctly identifying the abundant OK messages. A development corpus helps find the probability threshold that balances precision and recall for the new policy.

Comparison Summary

Past paper questions: y2021p3q9, y2025p3q7

Motivation

Naive Bayes treats every observation independently: word order does not matter. But many real-world problems involve sequences where items depend on their neighbours: speech, weather patterns, financial time series, biological sequences (DNA, proteins). Hidden Markov Models explicitly model these temporal dependencies through a two-level structure: hidden states that evolve over time and visible observations emitted by those states.

Formal Definition: $\mu = (S, V, A, B, \pi)$

An HMM models a system where we observe outputs (emissions) but cannot directly observe the underlying process (hidden states). The model is fully specified by five components:

Each row of $A$ sums to 1. Each row of $B$ sums to 1. $\sum_j \pi_j = 1$.

Concrete Example: Weather HMM

This is the 2024 Q8 HMM. Hidden states: $S = \{\text{Freezing}(F), \text{NotFreezing}(NF)\}$ (air temperature, unobservable without a thermometer). Observations: $V = \{\text{Snow}(S), \text{Rain}(R), \text{Dry}(D)\}$ (visible weather).

Transition matrix $A$ — models how temperature changes month to month:

Emission matrix $B$ — models the weather given the temperature:

Note: Snow requires freezing temperatures ($P(S \mid NF) \approx 0$). Rain implies above-freezing ($P(R \mid F) \approx 0$). Dry is possible in either state.

Initial distribution $\pi$: $\pi = [P(q_1 = F),\; P(q_1 = NF)]$.

What Makes HMMs Different from Naive Bayes

Naive Bayes: $P(c \mid d) \propto P(c) \prod_i P(w_i \mid c)$ — each word contributes independently. Word order does not matter. “The dog bit the man” and “The man bit the dog” are identical to NB.

HMMs model the dependence between consecutive items through the transition matrix $A$. The hidden state at time $t$ depends on the hidden state at $t-1$. The observation at time $t$ depends on the state at $t$. This sequential structure makes HMMs suitable for any data where context matters: part-of-speech tagging, speech recognition, activity recognition, financial regime detection.

Dual-Tape Training Data

Training requires fully labelled sequences: both the hidden state and the observation at every timestep must be known. This is called dual-tape data. Example: