Stage 18 of 18Finalabout 60 min

Mock exam: weeks 1 to 4

Four questions in the shape of Nicolo Colombo's half of the 2024 and 2025 papers: explain, write the formula, discuss flexibility, then a small hand calculation. Pass 70% to finish the path. Calculation parts get fresh numbers every attempt.

How to sit this mock

Time it. The real paper is 2 hours for 100 marks, about 1.2 minutes per mark. This mock is about 60 marks, so give yourself 70 minutes, no notes, calculator allowed.
Write on paper first for the written parts, as you would in the exam, then type or summarise your answer and mark it honestly against the scheme.
Show the working for calculations on paper; here only the final numbers are checked, but in the exam the steps carry most of the marks.
After marking, go back to the stage for every part you dropped marks on. Retake the mock a few days later: the numbers will be different.

The real paper will also have two questions on second-half topics (past years: bagging and out-of-bag error, boosting, clustering, multiple testing, PageRank, tf-idf). Those will be added when they’ve been taught.

Mock exam

Q1 Linear regression. (a) [4 marks] Why would you use a linear regression model? Include a real-world example, and write the model for a single input with parameters \(\lambda \in \mathbb R^2\).

Output is real-valued; reason to use: simple, interpretable, cheap, little data, good when roughly linear.
A specific example naming input and output.
\(f(X) = \lambda_0 + \lambda_1X\) with intercept and slope explained.
\(\lambda\) fitted by minimising the RSS.

Linear regression predicts a real-valued output that is expected to vary roughly linearly with the inputs; it is simple, cheap, needs little data and is interpretable, since the slope gives the average change in the output per unit change of the input. Example: predicting a flat’s rent in pounds from its floor area. \(f(X) = \lambda_0 + \lambda_1X\) with \(\lambda = (\lambda_0, \lambda_1) \in \mathbb R^2\) (intercept, slope), fitted by minimising \(\sum_n(Y_n - f(X_n))^2\).

Q1 (b) [3 marks] Write the residual sum of squares of \(f\) on \(D = \{(X_n, Y_n)\}_{n=1}^N\) and explain each symbol.

\(\mathrm{RSS}(\lambda) = \sum_{n=1}^N\big(Y_n - f(X_n)\big)^2\).
\(Y_n\) observed output, \(f(X_n) = \lambda_0 + \lambda_1X_n\) the prediction; the difference is the residual.
Squares make all residuals positive and punish large ones; least squares minimises it.

\(\mathrm{RSS}(\lambda) = \sum_{n=1}^{N}\big(Y_n - (\lambda_0 + \lambda_1X_n)\big)^2\): for each of the \(N\) training pairs, the residual is the observed output \(Y_n\) minus the model’s prediction \(f(X_n)\); squaring makes every miss positive and penalises large misses more. Least squares chooses \(\lambda\) to minimise it.

Q1 (c) [5 marks] A polynomial model \(f(X) = \lambda\cdot\phi(X)\) has \(\lambda \in \mathbb R^d\). Discuss the relationship between the degrees of freedom, \(d\) and the model’s flexibility.

Degrees of freedom = number of free parameters = \(d\).
Larger \(d\): more flexible, lower bias, lower training RSS.
Larger \(d\): higher variance; as \(d \to N\) the model interpolates the data and overfits (\(d > N\): no unique solution).
Model stays linear in \(\lambda\) (least squares still applies).
Choose \(d\) by validation error / regularise.

The degrees of freedom are the number of free parameters, \(d\). Increasing \(d\) adds basis functions, so the model can follow more complex curves: flexibility rises, bias and training RSS fall. But the \(d\) parameters are estimated from the same \(N\) points, so variance rises; as \(d\) approaches \(N\) the model can interpolate the training data and fits the noise (overfitting, rising test error), and for \(d > N\) the solution is not unique. The model remains linear in \(\lambda\), so least squares still applies. \(d\) should be chosen on a validation set or controlled by regularisation.

Q2 Decision trees. (a) [3 marks] Write the entropy of a data set \(D\) with labels in \(\{\text{yes}, \text{no}\}\), defining \(p_{yes}\).

\(p_{yes} = \frac1N\sum_n\mathbb 1(Y_n = \text{yes})\), \(p_{no} = 1 - p_{yes}\).
\(H(D) = -p_{yes}\log p_{yes} - p_{no}\log p_{no}\).
0 for a pure set, largest at \(p_{yes} = 0.5\).

With \(p_{yes} = \frac1N\sum_{n=1}^N\mathbb 1(Y_n = \text{yes})\) and \(p_{no} = 1 - p_{yes}\): \(H(D) = -p_{yes}\log p_{yes} - p_{no}\log p_{no}\) (with \(0\log 0 = 0\)). It is 0 when all labels agree and maximal (\(\log 2\)) when \(p_{yes} = 0.5\).

Q2 (b) [5 marks] Discuss the flexibility of decision trees in terms of the number of terminal nodes. Give a technique to mitigate overfitting.

More terminal nodes = smaller regions = more flexible, lower training error.
Lower bias, higher variance; too many leaves fit noise (overfitting).
Cost-complexity pruning: minimise RSS (or impurity) \(+ \alpha|T|\) over subtrees of a large tree.
Larger \(\alpha\), fewer leaves; \(\alpha\) chosen on validation data / cross-validation.
(Or another valid technique, e.g. maximum depth / minimum leaf size, explained.)

Each terminal node is a region with its own constant prediction, so more terminal nodes mean smaller regions and a more flexible model: lower bias and lower training error (zero with one point per leaf), but higher variance, since each prediction rests on fewer points, so a large tree fits the noise and overfits. To mitigate this, grow a large tree and prune it with cost-complexity pruning, choosing the subtree that minimises the training error plus \(\alpha|T|\); larger \(\alpha\) gives smaller trees, and \(\alpha\) is chosen by validation error (or cross-validation).

Q3 Neural networks. (a) [4 marks] What is a neural network? Describe the role of input, hidden and output neurons.

Input neurons hold the input features.
Hidden neurons compute a non-linear activation of a weighted sum of their inputs plus a bias.
Output neuron(s) combine hidden activations (linearly for regression; softmax/sigmoid for classes).
Weights learned from data by gradient descent / backpropagation.

A neural network maps inputs to outputs through layers of simple units. Input neurons hold the features \(X_1, \dots, X_p\); each hidden neuron computes \(g(w_0 + \sum_jw_jX_j)\) with a non-linear activation such as ReLU or the sigmoid, creating learned features; the output neuron combines the hidden activations, \(\beta_0 + \sum_k\beta_kA_k\) (followed by a sigmoid or softmax for classification). The weights and biases are learned by gradient descent with backpropagation.

Q3 (c) [3 marks] Why is a neural network more flexible than a linear model? Write an objective function you could use to train it on real-valued outputs.

Non-linear activations make \(f\) non-linear in \(X\) (curves, interactions); learned features; more hidden units = more flexible.
Without the non-linearity it collapses to a linear model.
\(\frac1N\sum_n(Y_n - f(X_n))^2\) (MSE), minimised by gradient descent.

Its hidden neurons apply non-linear activations to weighted sums of the inputs, so \(f\) can bend and represent interactions; it learns its own features, and with enough hidden neurons can approximate almost any smooth function (with identity activations it would collapse to a linear model). Objective: \(L(\lambda) = \frac1N\sum_{n=1}^N(Y_n - f(X_n; \lambda))^2\), minimised by gradient descent with backpropagation.

Q4 Classification. (a) [4 marks] Explain the role of \(K\) in KNN classification and how it controls bias and variance.

Prediction = majority vote among the \(K\) nearest training points.
Small \(K\): flexible, low bias, high variance (1-NN has zero training error, overfits).
Large \(K\): smooth, high bias, low variance (underfits).
Choose \(K\) on validation data (test error U-shaped).

KNN predicts the majority class among the \(K\) training points nearest to the new point. Small \(K\) gives a jagged, very flexible boundary with low bias and high variance (\(K = 1\) has zero training error and overfits); large \(K\) averages over many points, giving a smooth boundary with high bias and low variance (\(K = n\) predicts the majority class everywhere). Test error is U-shaped in \(K\), so \(K\) is chosen on a validation set.

Q4 (b) [4 marks] For the sigmoid \(\sigma(t) = 1/(1 + e^{-t})\), give its domain and range and show that \(\sigma'(t) = \sigma(t)(1 - \sigma(t))\).

Domain \(\mathbb R\), range \((0, 1)\), never reaching 0 or 1.
Chain rule: \(\sigma' = e^{-t}/(1 + e^{-t})^2\).
Split into \(\frac{1}{1 + e^{-t}}\cdot\frac{e^{-t}}{1 + e^{-t}}\).
Second factor \(= 1 - \sigma(t)\).

Domain: all real \(t\); range: \((0, 1)\). \(\sigma'(t) = -(1 + e^{-t})^{-2}(-e^{-t}) = \frac{e^{-t}}{(1 + e^{-t})^2} = \frac{1}{1 + e^{-t}}\cdot\frac{e^{-t}}{1 + e^{-t}} = \sigma(t)(1 - \sigma(t))\), since \(1 - \sigma(t) = \frac{e^{-t}}{1 + e^{-t}}\).