Tripos Question Patterns for MLRD

Exam Structure

MLRD appears on Part IA Paper 3, worth 20 marks. You answer 2 out of 3 questions on the paper. MLRD is typically Question 8 (2023-2025) or Question 9 (2020-2021). Each MLRD question follows a consistent pattern of sub-questions.

Standard Question Structure

Every MLRD question is structured as a progression:

Part	Marks	Type	What to Do
(a)	2-4	Setup / Formula	Write down the definition, state the formula, define the model
(b)	4-8	Apply / Calculate	Compute parameters, run Viterbi for 3 timesteps, calculate $\kappa$, compute betweenness
(c)	4-6	Evaluate / Critique	Identify bias, discuss shortcomings, handle domain changes
(d)	4-6	Extend / Design	Design a time-aware HMM, modify a classifier for new requirements

Topic Pairings in Actual Past Papers

Naive Bayes and Evaluation

2021 Q9, 2023 Q8

Typical structure: (a) write the Naive Bayes classification formula and parameter estimation with Laplace smoothing [3-4 marks]; (b) compute all feature probabilities from given training data [6 marks]; (c) apply the classifier to a test instance [2 marks]; (d) detect and demonstrate bias by constructing two test instances differing only in a protected attribute [4 marks]; (e) propose improvements for domain change or language change robustness [4-6 marks].

The 2021 paper included a lexicon for cyberbullying detection; the 2023 paper centred on conference-paper routing with topics as classes.

Hidden Markov Models

2022 Q8/Q9, 2024 Q8

Typical structure: (a) define HMM components $(S, V, A, B, \pi)$ and estimate parameters from labelled data [4 marks]; (b) state and evaluate the three assumptions in the given context — give a concrete failure case for each [4 marks]; (c) run Viterbi decoding for a sequence of 3-4 observations, showing all $\delta$ values, backpointers, and the final optimal path [6-8 marks]; (d) propose a time-aware compound-state HMM to handle seasonality [4-6 marks].

The 2022 paper used a COVID infection-level HMM; 2024 used a snowfall-prediction HMM with monthly weather data.

Networks and Graph Theory

2020 Q9, 2025 Q8

Typical structure: (a) compute degree, local clustering coefficient, and betweenness centrality for specific named nodes [5-6 marks]; (b) conceptual questions on clustering measures, cliques, bridges/local bridges [3-4 marks]; (c) compute the diameter [2 marks]; (d) analyse the effect of edge edits on betweenness centrality [4 marks]; (e) discuss strongly connected directed graphs [3 marks]; (f) describe the Newman-Girvan community-detection algorithm [2 marks].

The 2020 paper used a 4x4 grid; the 2025 paper used an 8-node graph with a leaf node E.

Strategy for Calculation Questions

Show All Working

Mark schemes reward correct method even if the final number is wrong. A wrong final answer with correct methodology can still earn 6/8 marks. Always:

• Write the formula before plugging in numbers.
• Show intermediate steps.
• Circle or box the final answer.

For Viterbi Questions

Draw a table with rows = hidden states and columns = timesteps. Show:

1. The observation at each timestep.
2. For each state, the full product $\delta_i(t-1) \times a_{ij} \times b_j(o_t)$.
3. Circle the maximum value in each column.
4. Draw backpointer arrows from each max back to its source state.
5. Explicitly state the optimal path and its probability at termination.

For Betweenness Questions

For undirected graphs, halve all scores at the end. Even a qualitative answer that correctly identifies which nodes gain or lose traffic from an edge edit will earn marks. Show which (source, target) pairs have shortest paths passing through each node.

For $\kappa$ (Kappa) Questions

1. Tabulate the agreement: rows = items, columns = annotators’ assigned classes.
2. Count observed agreements for $P(A)$.
3. Compute marginal frequencies ($P(\text{Ann}_1 = c)$, $P(\text{Ann}_2 = c)$) for $P(E)$.
4. Plug into $\kappa = (P(A) - P(E)) / (1 - P(E))$.
5. Interpret the result (strong > 0.8, acceptable > 0.6, no better than chance ≈ 0).

For Sign Test Questions

1. Count wins for A, wins for B, and ties.
2. Apply the MLRD tie rule: $k = \text{wins}_A + \text{ties}/2$, round up.
3. Do NOT discard ties — this inflates the test statistic and causes Type 1 error.
4. $N$ = total items unchanged.
5. Test statistic: $X \sim \text{Binomial}(N, p = 0.5)$.
6. $p$-value (two-tailed) = $2 \times P(X \ge k \mid N, 0.5)$.

Strategy for Critique Questions

State at least 3 distinct points. The mark scheme typically allocates 1-2 marks per point. For HMM shortcomings, the canonical list is:

1. Stationarity violated (transitions change with season or policy).
2. First-order Markov insufficient (real trends persist over longer windows).
3. Small training set (unreliable parameter estimates).
4. Output independence violated (consecutive observations are correlated).
5. Discrete hidden states too coarse (continuous reality forced into few categories).

Topic Frequency in Available Past Papers (2020-2025)

Topic	2020	2021	2023	2024	2025
Naive Bayes	—	Q9	Q8	Q7/Q9	Q7
HMM	—	—	Q9	Q8	Q9
Networks	Q9	—	—	—	Q8
IAA (Kappa)	—	—	Q7	—	—
Clustering	—	—	—	Q7(e)	—

(NB: 2022 paper data is unavailable. 2024 Q7 and Q9 are NB-focused with parts touching ethics/clustering.)

Recommended Preparation Order

1. Naive Bayes + HMMs first: these appear most years in predictable formats.
2. Networks: your backup if HMMs are elsewhere on the paper.
3. IAA (Kappa): a straightforward calculation that can appear as part of a wider question.
4. Evaluation and significance testing: short sub-questions, the sign test specifically.
5. Clustering: appears as sub-parts within NB or evaluation questions.

Summary

Exam Aspect	Detail
Paper	Part IA Paper 3
Marks per question	20
Sub-question pattern	Setup → Calculate → Critique → Extend
Calculation strategy	Show all working; correct method earns most marks
Viterbi strategy	Table with rows = states, columns = timesteps; circle maxes; draw backpointers
Betweenness strategy	Halve scores for undirected graphs at the end
Sign test strategy	MLRD tie rule: split ties 0.5/0.5, never discard
Kappa strategy	Compute $P(A)$, compute marginals for $P(E)$, plug into formula
Most predictable topics	NB and HMM
Non-assessed lecture content	Ethics case studies, AI hype, Asimov’s Laws, AGI risk