Model Evaluation & Selection

Question 1

(a) Bias–variance proof (8 marks)

Let $\bar f(x)=\mathbb{E}_D[\hat f_D(x)]$. Write $\mathbb{E}[(y-\hat f)^2]=\mathbb{E}[(f+\varepsilon-\hat f)^2].$ Expand into three groupings by inserting $\pm \bar f$: $y-\hat f = \varepsilon + (f-\bar f) + (\bar f - \hat f).$ Square and take expectation over $D$ and $\varepsilon$: $\mathbb{E}[(y-\hat f)^2]=\mathbb{E}[\varepsilon^2]+ (f-\bar f)^2 + \mathbb{E}[(\bar f-\hat f)^2] + 2(\text{cross terms}).$

• $\mathbb{E}[\varepsilon^2]=\sigma^2$ (zero-mean noise). (1)
• $(f-\bar f)^2$ is deterministic $=\text{Bias}^2$. (1)
• $\mathbb{E}[(\bar f-\hat f)^2]=\operatorname{Var}_D(\hat f)$. (1)

Cross terms vanish:

• $\mathbb{E}[\varepsilon(f-\bar f)]=\mathbb{E}[\varepsilon]\cdot(f-\bar f)=0$ (noise indep. of training set, zero mean). (1.5)
• $\mathbb{E}[\varepsilon(\bar f-\hat f)]=0$: test noise $\varepsilon$ at $x$ is independent of $\hat f_D$ (trained on $D$, disjoint from test noise), and $\mathbb{E}[\varepsilon]=0$. (1.5)
• $\mathbb{E}[(f-\bar f)(\bar f-\hat f)]=(f-\bar f)\,\mathbb{E}[\bar f-\hat f]=(f-\bar f)\cdot 0=0$ since $\mathbb{E}_D[\hat f]=\bar f$. (1)

Hence result. Assumptions stated: zero-mean noise, noise independent of $D$, $\bar f=\mathbb{E}[\hat f]$. (1)

(b) kNN variance (6 marks)

Prediction $\hat f(x_0)=\frac1k\sum_{i=1}^k y_i$ where locally $y_i=f(x_0)+\varepsilon_i$, $\varepsilon_i$ i.i.d. $(0,\sigma^2)$.

• $\operatorname{Var}(\hat f)=\frac{1}{k^2}\sum \operatorname{Var}(\varepsilon_i)=\frac{k\sigma^2}{k^2}=\sigma^2/k$. (3)
• Bias: as $k$ grows, neighbours span a larger region where $f$ varies, so $\mathbb{E}[\hat f]$ averages over differing $f$ values → bias grows with $k$. (2)
• Thus small $k$ = low bias / high variance = complex model; large $k$ = smooth/regularized. $k$ is the complexity knob. (1)

(c) Diagnosis (8 marks)

• Large gap: val $0.52 \gg$ train $0.18$ → high variance / overfitting. (2)
• Train RMSE $0.18$ is only slightly above irreducible floor $\sigma=0.15$; model fits training data near the noise floor but generalizes poorly → confirms variance-dominated, low bias. (2)
• Curves have flattened ⇒ more data will not close the gap much (learning curve plateaued); adding data alone has limited benefit. (2)
• Two remedies (any two distinct): (i) increase regularization / reduce model complexity; (ii) feature selection / dimensionality reduction; (iii) ensembling/bagging to reduce variance; (iv) early stopping. (2)

Question 2

(a) Derivation + monotonicity proof (8 marks)

• Precision $=\dfrac{TP}{TP+FP}$, Recall/TPR $=\dfrac{TP}{P}$, FPR $=\dfrac{FP}{N}$. (2)
• Substitute $TP=\text{TPR}\cdot P$, $FP=\text{FPR}\cdot N$: $\text{Precision}=\frac{\text{TPR}\,P}{\text{TPR}\,P+\text{FPR}\,N}.$ Divide by $(P+N)$, with $\pi=P/(P+N)$, $1-\pi=N/(P+N)$: $\boxed{\text{Precision}=\frac{\text{TPR}\,\pi}{\text{TPR}\,\pi+\text{FPR}\,(1-\pi)}}.$ (3)
• Monotonicity: write $\text{Prec}=\dfrac{1}{1+\frac{\text{FPR}}{\text{TPR}}\cdot\frac{1-\pi}{\pi}}$. As $\pi\downarrow$, $\frac{1-\pi}{\pi}\uparrow$, denominator $\uparrow$, so precision $\downarrow$ (TPR, FPR fixed, both positive). Hence strictly decreasing in the imbalance. (3)

(b) AUC by pair counting (6 marks)

Labels descending: positions of positives = {1,2,4}, negatives = {3,5,6}. AUC $=\frac{1}{P\cdot N}\sum_{\text{pos }p,\text{neg }n}\mathbf 1[\text{score}(p)>\text{score}(n)]$. Count concordant pairs (positive ranked above negative):

• pos@1: beats negs at 3,5,6 → 3
• pos@2: beats 3,5,6 → 3
• pos@4: beats 5,6 (not 3) → 2

Total concordant $=8$, out of $P\cdot N=9$. (4) $\text{AUC}=8/9\approx 0.889.$ (2)

(c) Top-3 operating point (6 marks)

Top-3 predicted positive = positions {1,2,3}; labels there = {1,1,0}.

• TP=2 (pos at 1,2), FP=1 (neg at 3), FN=1 (pos at 4), TN=2 (negs at 5,6). (2)
• Accuracy $=(2+2)/6=0.667$; Precision $=2/3\approx0.667$; Recall $=2/3\approx0.667$; $F_1=2\cdot\frac{.667\cdot.667}{.667+.667}=0.667$. (2)
• Top-2 threshold: TP=2, FP=0 → Precision $=1.0$, Recall $=2/3$. Compared to top-3 (Prec .667, Recall .667): top-2 has equal recall but higher precision, so top-3 is dominated / NOT Pareto-optimal. (2)

Question 3

(a) Optimistic bias (6 marks)

• Choosing the hyperparameter with the best CV score means maximizing over many noisy estimates. The maximum of noisy estimates is biased high (its expectation exceeds the true best). (3)
• The winning config partly won by fitting the noise/idiosyncrasies of these particular folds → the reported CV score is contaminated by the selection, no longer an unbiased estimate of generalization. It is a multiple-comparisons/"winner's curse" bias. (3)

(b) Nested CV (7 marks)

from sklearn.model_selection import KFold
import numpy as np
 
def nested_cv(X, y, model_factory, G, fit_score):
    outer = KFold(5, shuffle=True, random_state=0)
    outer_scores = []
    for tr, te in outer.split(X):                 # evaluation loop
        # --- inner: model selection only ---
        inner = KFold(3, shuffle=True, random_state=1)
        best_g, best_val = None, -np.inf
        for g in G:
            vals = []
            for itr, iva in inner.split(X[tr]):
                m = model_factory(g).fit(X[tr][itr], y[tr][itr])
                vals.append(fit_score(m, X[tr][iva], y[tr][iva]))
            if np.mean(vals) > best_val:
                best_val, best_g = np.mean(vals), g
        # --- refit on full outer-train, score on untouched outer-test ---
        m = model_factory(best_g).fit(X[tr], y[tr])
        outer_scores.append(fit_score(m, X[te], y[te]))
    return np.mean(outer_scores), np.std(outer_scores)

Marks: inner loop selects only (2), outer test never seen during selection (3), refit + return mean±std (2).

(c) Leakage pitfalls (5 marks)

1. Grouped data leakage: rows from the same patient appear in both train and validation folds → info leaks, optimistic bias. Fix: use GroupKFold/StratifiedGroupKFold keyed on patient ID. (2.5)
2. Feature selection before CV (selection leakage): correlations computed on full data (incl. validation) → optimistically biased. Fix: put feature selection inside the CV pipeline, refit on each training fold only. (2.5)

[
 {"claim":"kNN averaging variance is sigma^2/k",
  "code":"k,s=symbols('k s',positive=True); var=k*s**2/k**2; result = simplify(var - s**2/k)==0"},
 {"claim":"AUC = 8/9 for the given ranking",
  "code":"pos=[1,2,4]; neg=[3,5,6]; c=sum(1 for p in pos for n in neg if p<n); result = Rational(c,len(pos)*len(neg))==Rational(8,9)"},
 {"claim":"Top-3 F1 = 2/3",
  "code":"TP,FP,FN=2,1,1; P=Rational(TP,TP+FP); R=Rational(TP,TP+FN); F1=2*P*R/(P+R); result = F1==Rational(2,3)"},
 {"claim":"Precision decreases as prior pi decreases (fixed TPR,FPR)",
  "code":"pi,tpr,fpr=symbols('pi tpr fpr',positive=True); prec=tpr*pi/(tpr*pi+fpr*(1-pi)); d=diff(prec,pi); result = simplify(d.subs({tpr:Rational(1,2),fpr:Rational(1,4),pi:Rational(1,3)}))>0"}
]