Examinable Syllabus for MLRD

Course Information

• Course name: Machine Learning and Real-World Data (MLRD)
• Paper: Part IA Paper 3, Question 8 (2023-2025) / Question 9 (2020-2021)
• Term: Easter Term, 2025/26 syllabus
• Marks: 20 marks per question
• Format: Answer 2 out of 3 questions on Paper 3

Examinable Core Topics

These topics have appeared in past papers (2020-2025) and are assessed in the written Tripos examination.

Topic 1: Methodology and Evaluation

• Train / development / test split and the multiple comparisons problem
• N-fold cross-validation: stratified, leave-one-out, dependency-sensitive
• Confusion matrix: TP, FP, TN, FN
• Accuracy, precision, recall, F1 (including harmonic mean formula)
• Macro-averaging vs micro-averaging for multi-class problems
• Sign test: null hypothesis, binomial test statistic, the MLRD tie rule (distribute ties as 0.5 to each side; never discard ties), one-tailed vs two-tailed
• Permutation / randomisation test
• Type 1 and Type 2 errors, power, specificity

Appears in: 2021 Q9 (prec/recall, dev-corpus tuning), 2023 Q8 (evaluation methods with area-chair feedback).

Topic 2: Inter-Annotator Agreement

• Cohen’s $\kappa$ for two annotators: $\kappa = \frac{P(A) - P(E)}{1 - P(E)}$, where $P(E) = \sum_c P(\text{Annotator}_1 = c) \cdot P(\text{Annotator}_2 = c)$
• Fleiss’ $\kappa$ for more than two annotators (formula: $P_a$ per-item agreement via pairwise counts, $P_e = \sum_c p_c^2$)
• Partial annotation: compute $P_a$ only over overlapping items, $P_e$ from all available annotations
• Crowdsourcing problems: small batches, random assignment, worker quality variation

Appears in: 2023 Q7 (Cohen’s $\kappa$ calculation, partial annotation problems). Fleiss’ $\kappa$ appears in the syllabus but has not yet been examined.

Topic 3: Statistical Classification (Naive Bayes)

• Types vs tokens vs lexicon-based classification
• Naive Bayes classification rule: $c^* = \arg\max_c P(c) \prod_i P(w_i \mid c)$ and the log-space form $c^* = \arg\max_c \left[\log P(c) + \sum_i \log P(w_i \mid c)\right]$
• Prior estimation: $P(c) = N_c / N_{\text{total}}$
• Laplace (add-one) smoothing: $P(w \mid c) = \frac{\text{count}(w,c) + 1}{\sum_{w'} \text{count}(w',c) + \lvert V \rvert}$
• General smoothing parameter $\omega$: denominator becomes $\sum \text{count}(w',c) + \omega \cdot \lvert V \rvert$
• Log-probability underflow mitigation
• Zipf’s Law: $f_w \approx \frac{k}{(r_w + \beta)^\alpha}$, log-log estimation of $\alpha$ and $k$
• Heaps’ Law: $\lvert V \rvert = k N^\beta$, vocabulary grows without bound
• Feature engineering: stemming, lowercasing, stop-word removal, hapax removal, lexicon integration
• NB bias detection: the 4-step mathematical method for proving bias by constructing test instances differing only in a protected attribute
• Naive Bayes vs lexicon-based classification: when each is preferred

Appears in: 2021 Q9 (NB parameter estimation, bias demonstration, lexicon for language-change robustness), 2023 Q8 (NB with conference-paper routing, feature engineering for area changes), 2024 Q7/Q9 (NB with smoothing and classification).

Topic 4: Hidden Markov Models

• Formal definition: $\mu = (S, V, A, B, \pi)$
• Three assumptions (examined every year): first-order Markov, output independence, stationarity; for each, state the assumption and give a concrete failure case
• Parameter estimation with Laplace smoothing
  • Transitions: $a_{ij} = \frac{\text{count}(s_i \to s_j) + 1}{\text{count}(s_i) + \lvert S \rvert}$
  • Emissions: $b_i(v_k) = \frac{\text{count}(s_i \text{ emits } v_k) + 1}{\text{count}(s_i) + \lvert V \rvert}$
  • Critical distinction: transition denominator uses $\lvert S \rvert$, emission denominator uses $\lvert V \rvert$
• Viterbi decoding: $\delta_j(t) = \max_i \left[\delta_i(t-1) \cdot a_{ij} \cdot b_j(o_t)\right]$ with backpointers
• Common shortcomings (stationarity violated, first-order insufficient, small training set, discrete states too coarse, output independence violated, supervised training needs dual-tape data)
• Time-aware compound states (e.g. $F_{\text{Winter}}$, $NF_{\text{Summer}}$)

Appears in: 2022 Q8/Q9 (COVID HMM, Viterbi), 2023 Q9 (inflation HMM), 2024 Q8 (snowfall HMM, Viterbi for 3 months, time-aware compound states), 2025 Q9.

Topic 5: Networks and Graph Theory

• Network taxonomy: social (undirected, high clustering, triadic closure), information (directed, bow-tie, power-law), technological (geography-constrained, hub-vulnerable), biological (modular, robust to random failure)
• Small-world phenomenon: $L \sim \log N$ AND $C \gg C_{\text{random}}$ (both conditions required)
• Triadic closure and weak ties / local bridges
• Power-law degree distribution: $P(k) \propto k^{-\alpha}$; preferential attachment origin; robustness to random failure, fragility to targeted hub attack
• Degree $k_i$ and local clustering coefficient: $C_i = \frac{2e_i}{k_i(k_i - 1)}$
• Betweenness centrality: $C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$; halve scores for undirected graphs
• Brandes algorithm: $O(\lvert V \rvert \cdot \lvert E \rvert)$
• Diameter and the giant component
• Newman-Girvan algorithm: divisive community detection (recalculate edge betweenness after every single edge removal)
• Strongly connected directed graphs: leaf nodes prevent strong connectivity
• Effect of edge edits on betweenness centrality

Appears in: 2020 Q9 (betweenness, bridges, small-world), 2025 Q8 (degree, clustering coefficient, betweenness for named nodes, Newman-Girvan, diameter, strongly connected, edge-edit effects).

Topic 6: Unsupervised Clustering

• Hard vs soft clustering
• K-Means algorithm: initialise, assign (Euclidean distance), update (centroid mean), iterate to convergence
• K-Means convergence proof: WCSS never increases across iterations
• K-Means++ initialisation: probability proportional to $d(x)^2$ (distance to nearest existing centroid)
• WCSS (Within-Cluster Sum of Squares): $\sum_n \lVert x_n - \mu_{z_n} \rVert^2$; elbow method for choosing K
• Silhouette score: $S(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$
• Extrinsic metrics: purity (flawed, singleton problem), ARI (chance-corrected, $-1$ to $1$), NMI (preferred, $0$ to $1$)

Appears in: 2024 Q7(e) (school class grouping via K-Means, evaluation via silhouette).

Non-Examinable Lecture Content

The following topics appear in lectures and the revision guide but are not assessed in the written Tripos examination:

• London Medical School Admissions case study (1970s, algorithmic replication of human bias)
• Pneumonia-Asthma interpretability case study (Caruana et al., neural network vs transparent model)
• AI hype problems: anthropomorphisation, cherry picking, significance misuse, no-significance-test claims
• Asimov’s Laws of Robotics: Zeroth through Third Laws, loopholes, philosophical nature
• AGI and existential risk: CSER, Leverhulme CFI, current non-AGI risks (stock trading, autonomous vehicles)

These topics provide important context for understanding algorithmic bias, interpretability, and responsible AI deployment, but no past paper (2020-2025) has examined them directly. They may be referenced indirectly in bias-detection sub-questions, where the focus is on the mathematical method (constructing identical instances differing only in a protected attribute) rather than the case-study details.

Past Paper Availability

Papers available from 2020-2025. Earlier years (2020-2021): MLRD appears as Question 9. Later years (2023-2025): MLRD appears as Question 8.

Summary

Topic	Key concept	Assessed?	Past appearances
Methodology & evaluation	Sign test (MLRD tie rule), F1, CV	Yes	2021, 2023
IAA (Kappa)	Cohen’s $\kappa$, Fleiss’ $\kappa$, partial annotation	Yes	2023 Q7
Naive Bayes	Smoothing, log-space, bias detection	Yes	2021, 2023, 2024
Zipf’s Law / Heaps’ Law	Log-log estimation, vocabulary growth	Yes (supporting NB)	—
HMM	Viterbi, assumptions, smoothing ($\lvert S \rvert$ / $\lvert V \rvert$), compound states	Yes	2022, 2023, 2024, 2025
Networks	Betweenness, $C_i$, Newman-Girvan, small-world	Yes	2020, 2025
Clustering	K-Means, K-Means++, silhouette, NMI	Yes	2024 Q7(e)
Ethics case studies	London Medical School, pneumonia-asthma	No	—
AI hype / reporting	Anthropomorphisation, cherry picking	No	—
Asimov’s Laws / AGI risk	Zeroth-Third Laws, existential risk	No	—