03_Evaluation_and_Model_Selection

Module 2 — Evaluating Classifiers and Tuning Parameters

Sources: Lec 5 — Evaluation Criteria for Data Classification; Lec 6 — Parameter Tuning (Cross-Validation).

---

C11. The Confusion Matrix, Accuracy, Precision, Recall, F-measure

Intuition

A classifier can be wrong in two different ways: crying wolf (false alarm) and missing the wolf (miss). The confusion matrix counts all four outcomes. Accuracy lumps everything together; precision asks “when I say positive, am I right?”; recall asks “of all real positives, how many did I find?”; F-measure combines the two.

Formal definition

	Predicted +	Predicted −
Actual +	TP	FN
Actual −	FP	TN

$\text{Accuracy}=\frac{TP+TN}{TP+FP+FN+TN},\text{Precision}=\frac{TP}{TP+FP},\text{Recall}=\frac{TP}{TP+FN},$ $F=\frac{2\cdot \text{Precision}\cdot \text{Recall}}{\text{Precision}+\text{Recall}}.$

Mathematical properties

• $F$ is the harmonic mean of precision $P$ and recall $R$: $\frac{1}{F}=\frac{1}{2}\left(\frac{1}{P}+\frac{1}{R}\right)$.
• $F\in [0,1]$; $F=1$ iff $P=R=1$; $F=0$ if $P=0$ or $R=0$.
• Equivalent count form: $F=\frac{2TP}{2TP+FP+FN}$.
• $\min (P,R)\le F\le \sqrt{PR}\le \frac{P+R}{2}$.

Derivation of the count form

$P=\frac{TP}{TP+FP}$, $R=\frac{TP}{TP+FN}$. Then $F=\frac{2PR}{P+R}=\frac{2\frac{T{P}^2}{(TP+FP)(TP+FN)}}{\frac{TP(TP+FN)+TP(TP+FP)}{(TP+FP)(TP+FN)}}=\frac{2T{P}^2}{TP(2TP+FN+FP)}=\frac{2TP}{2TP+FP+FN}.∎$

Key insights

• TN does not appear in precision, recall, or $F$ — they ignore the (often huge) negative class.
• Closer $P$ and $R$ ⇒ higher $F$ for a given sum.
• Convention: if $TP+FP=0$ precision is taken as $0$ (undefined $0/0$).

Worked examples

Example 1 — Very Easy

• Problem: $TP=40,FP=10,FN=20,TN=30$. Compute accuracy.
• Asked: Accuracy.
• Concept: Accuracy formula.
• Approach: Correct / total.
• Solution: Correct $=40+30=70$; total $=40+10+20+30=100$.
• Final answer: $0.70$.
• Key lesson: Accuracy uses the diagonal.

Example 2 — Easy

• Problem: Same matrix. Compute precision and recall.
• Asked: $P,R$.
• Concept: Definitions.
• Approach: Row/column totals of the positive class.
• Solution: $P=\frac{40}{40+10}=0.80$. $R=\frac{40}{40+20}=0.667$.
• Final answer: $P=0.80$, $R=0.667$.
• Key lesson: Precision divides by the predicted-positive column; recall by the actual-positive row.

Example 3 — Moderate

• Problem: Same matrix. Compute $F$ two ways and verify $\min (P,R)\le F\le \frac{P+R}{2}$.
• Asked: $F$.
• Concept: Harmonic mean.
• Approach: Formula and count form.
• Solution: $F=\frac{2(0.8)(0.6667)}{0.8+0.6667}=\frac{1.0667}{1.4667}=0.7273$. Count form: $\frac{80}{80+10+20}=\frac{80}{110}=0.7273$ ✓. Bounds: $0.667\le 0.727\le 0.733$ ✓.
• Final answer: $F=0.727$.
• Key lesson: Harmonic mean sits below the arithmetic mean, pulled toward the smaller value.

Example 4 — Hard

• Problem: 1000 samples, 20 positive. Classifier A predicts everything negative. Classifier B has $TP=15,FN=5,FP=30,TN=950$. Compare accuracy, $P$, $R$, $F$.
• Asked: Which is better.
• Concept: Accuracy paradox.
• Approach: Fill matrices.
• Solution: A: $TP=0,FN=20,FP=0,TN=980$. Accuracy $=980/1000=0.98$. $R=0$; $P=\frac{0}{0}$→$0$ by convention; $F=0$. B: accuracy $=\frac{15+950}{1000}=0.965$; $P=\frac{15}{45}=0.333$; $R=\frac{15}{20}=0.75$; $F=\frac{2(15)}{30+30+5}=\frac{30}{65}=0.4615$.
• Final answer: A has higher accuracy (0.98 vs 0.965) but is useless (F=0); B is far better (F=0.46).
• Key lesson: On imbalanced data, accuracy hides total failure on the rare class.

Example 5 — Very Hard

• Problem: Ten test items ranked by classifier score (highest first) have true labels P,P,N,P,N,N,P,N,N,N (4 positives). Predicting “positive” for the top $k$ items, compute $F$ for each $k$ and choose the best $k$.
• Asked: $\arg {\max }_{k}F(k)$.
• Concept: $F=\frac{2TP}{2TP+FP+FN}$; threshold selection.
• Approach: Track $TP,FP$ cumulatively; $FN=4-TP$.
• Solution: $k=1$: $TP=1,FP=0,FN=3$ → $\frac{2}{2+0+3}=0.400$. $k=2$: $TP=2,FP=0,FN=2$ → $\frac{4}{4+2}=0.667$. $k=3$: $TP=2,FP=1,FN=2$ → $\frac{4}{7}=0.571$. $k=4$: $TP=3,FP=1,FN=1$ → $\frac{6}{8}=0.750$. $k=5$: $TP=3,FP=2,FN=1$ → $\frac{6}{9}=0.667$. $k=6$: $TP=3,FP=3,FN=1$ → $\frac{6}{10}=0.600$. $k=7$: $TP=4,FP=3,FN=0$ → $\frac{8}{11}=0.727$. $k=8$: $\frac{8}{12}=0.667$. $k=9$: $\frac{8}{13}=0.615$. $k=10$: $\frac{8}{14}=0.571$.
• Final answer: Best $k=4$, $F=0.75$ (not $k=7$ where recall is 1).
• Key lesson: $F$ is not monotone in the threshold; best $F$ balances precision and recall.

Common mistakes

• Mixing the roles of FP and FN in precision/recall.
• Quoting accuracy alone on imbalanced data.

Exam traps

• “Precision = TP/(TP+FN)” is wrong — that is recall.
• $F$ undefined/0 when $TP=0$.

Connections

Sensitivity/specificity and averaging (C12), clustering F-measure (C41), cross-validation scoring (C13).

Mastery checklist

• Draw the confusion matrix and fill it.
• Compute $A,P,R,F$ and the count form.
• Explain the accuracy paradox.

---

C12. Macro/Micro Averaging, Sensitivity & Specificity, Class Imbalance

Intuition

With $m$ classes there is one $(T{P}_i,F{P}_i,F{N}_i)$ per class (treat class $i$ as “positive”, the rest “negative”). Two ways to summarise: average the per-class scores (macro: every class counts equally, rare classes matter) or pool the counts then compute (micro: every data point counts equally, big classes dominate).

Formal definitions

$P_{macro}=\frac{1}{m}{\sum }_{i=1}^m\frac{T{P}_i}{T{P}_i+F{P}_i},R_{macro}=\frac{1}{m}{\sum }_{i=1}^m\frac{T{P}_i}{T{P}_i+F{N}_i},$ $P_{micro}=\frac{{\sum }_{i}T{P}_i}{{\sum }_{i}T{P}_i+{\sum }_{i}F{P}_i},R_{micro}=\frac{{\sum }_{i}T{P}_i}{{\sum }_{i}T{P}_i+{\sum }_{i}F{N}_i}.$ $\text{Sensitivity}=\frac{TP}{TP+FN}(\text{recall, TPR}),\text{Specificity}=\frac{TN}{TN+FP}(\text{TNR}).$

Mathematical result (derived)

In single-label multiclass classification, every misclassified item is a false positive for exactly one class and a false negative for exactly one class, so ${\sum }_{i}F{P}_i={\sum }_{i}F{N}_i$. Hence $P_{micro}=R_{micro}=\frac{{\sum }_{i}T{P}_i}{N}=\text{accuracy}$.

Derivation

Let $M_{ab}$ = count with actual $a$, predicted $b$. $F{P}_b={\sum }_{a\ne b}{M}_{ab}$, $F{N}_a={\sum }_{b\ne a}{M}_{ab}$. ${\sum }_{b}F{P}_b={\sum }_b{\sum }_{a\ne b}{M}_{ab}={\sum }_{a\ne b}{M}_{ab}$, and ${\sum }_{a}F{N}_a$ is the same off-diagonal sum. ∎

Key insights

• Macro: “per-class average”, insensitive to class frequency. Micro: “per-data-point average”.
• Sensitivity and specificity are the standard medical pair: how many sick found, how many healthy cleared.

Worked examples

Example 1 — Very Easy

• Problem: Binary matrix $TP=15,FN=5,FP=30,TN=950$. Sensitivity and specificity?
• Asked: Both.
• Concept: Definitions.
• Approach: Direct.
• Solution: Sens $=\frac{15}{20}=0.75$. Spec $=\frac{950}{950+30}=0.9694$.
• Final answer: $0.75$ and $0.969$.
• Key lesson: High specificity can coexist with mediocre sensitivity.

Example 2 — Easy

• Problem: Three-class confusion matrix (rows actual A,B,C; columns predicted A,B,C): $\left(\begin{array}{ccc}50& 5& 5\\ 5& 22& 3\\ 4& 2& 4\end{array}\right)$. Compute $T{P}_i,F{P}_i,F{N}_i$ and per-class precision/recall.
• Asked: Per-class counts and scores.
• Concept: One-vs-rest counts.
• Approach: Diagonal; column sums minus diagonal; row sums minus diagonal.
• Solution: Row totals: $60,30,10$. Column totals: $59,29,12$. $TP=(50,22,4)$. $FP=\text{col}-TP=(9,7,8)$. $FN=\text{row}-TP=(10,8,6)$. Precision: $\frac{50}{59}=0.8475,\frac{22}{29}=0.7586,\frac{4}{12}=0.3333$. Recall: $\frac{50}{60}=0.8333,\frac{22}{30}=0.7333,\frac{4}{10}=0.4$.
• Final answer: As computed.
• Key lesson: Class C (rare, 10 items) is much worse than A.

Example 3 — Moderate

• Problem: For the matrix of Example 2 compute macro and micro precision and recall.
• Asked: Four numbers.
• Concept: Averaging.
• Approach: Macro: mean of per-class; micro: pooled.
• Solution: Macro $P=\frac{0.8475+0.7586+0.3333}{3}=0.6465$. Macro $R=\frac{0.8333+0.7333+0.4}{3}=0.6556$. Micro: $\sum TP=76$, $\sum FP=24$, $\sum FN=24$ → $P_{micro}=\frac{76}{100}=0.76$, $R_{micro}=0.76$.
• Final answer: Macro $(0.647,0.656)$; micro $(0.76,0.76)$.
• Key lesson: Macro is lower because the weak rare class gets a full third of the weight.

Example 4 — Hard

• Problem: 980 “common” and 20 “rare” items; a classifier labels everything common. Compute accuracy, micro $R$, macro $R$, sensitivity and specificity of the rare class.
• Asked: Five numbers.
• Concept: Which metric exposes imbalance.
• Approach: Per-class recalls.
• Solution: Common: $TP=980,FN=0$ → $R=1$. Rare: $TP=0,FN=20$ → $R=0$. Accuracy $=\frac{980}{1000}=0.98$. Micro $R=\frac{980+0}{980+0+20}=0.98$. Macro $R=\frac{1+0}{2}=0.5$. Sensitivity (rare) $=0$; specificity (rare) $=\frac{980}{980+0}=1$.
• Final answer: Accuracy $0.98$, micro $0.98$, macro $0.5$, sensitivity $0$, specificity $1$.
• Key lesson: Macro averaging (and sensitivity) reveal failure on the rare class; accuracy and micro do not.

Example 5 — Very Hard

• Problem: Starting from the matrix of Example 2, an improved model re-labels 3 class-C items that were predicted A as predicted C: the C row becomes $[1,2,7]$ (rows A,B unchanged). Recompute micro and macro recall and precision, and compare the improvement.
• Asked: New metrics and change.
• Concept: Sensitivity of macro vs micro to a rare class.
• Approach: Recount.
• Solution: New matrix $\left(\begin{array}{ccc}50& 5& 5\\ 5& 22& 3\\ 1& 2& 7\end{array}\right)$. Column totals: $56,29,15$. $TP=(50,22,7)$, $FP=(6,7,8)$, $FN=(10,8,3)$. Precision: $\frac{50}{56}=0.8929,0.7586,\frac{7}{15}=0.4667$ → macro $P=0.7060$. Recall: $0.8333,0.7333,0.7$ → macro $R=0.7556$. Micro: $\sum TP=79$ → $P_{micro}=R_{micro}=0.79$. Changes: micro $+0.03$; macro $P$ $+0.060$; macro $R$ $+0.100$.
• Final answer: Micro $0.79$ (+3 pts); macro $P=0.706$ (+6 pts), macro $R=0.756$ (+10 pts).
• Key lesson: Improving one small class barely moves micro scores but visibly moves macro scores.

Common mistakes

• Averaging per-class accuracies and calling it macro precision.
• Expecting micro $P\ne$ micro $R$ in single-label problems.

Exam traps

• Sensitivity ≡ recall ≡ TPR; specificity is not precision.
• Micro = per-data-point average; macro = per-class average.

Connections

C11, class imbalance, cross-validation (C13), clustering evaluation (C41).

Mastery checklist

• Extract $T{P}_i,F{P}_i,F{N}_i$ from a multiclass matrix.
• Compute macro vs micro.
• Prove micro $P$ = micro $R$ = accuracy.

---

C13. Cross-Validation: Leave-One-Out and $k$-Fold

Intuition

Evaluating on training data flatters the model; setting aside one test set wastes data and gives a lucky-or-unlucky estimate. Cross-validation (CV) rotates the roles: every point gets to be a test point exactly once, while the model is never trained on the point it is tested on. CV is also how hyper-parameters (like $k$ in kNN, $C$ in SVM, tree depth) are chosen.

Formal definition

Data $Z=\{{\vec{X}}_1,\dots ,{\vec{X}}_n\}$, labels $y_i\in \{1,\dots ,c\}$.

• Leave-One-Out (LOO): for $i=\mathrm{1..}n$: train on $Z\setminus \{{\vec{X}}_i\}$, predict $y_i^{\prime }$ for ${\vec{X}}_i$. Score using $\{y_i\}$ vs $\{y_i^{\prime }\}$ (e.g. $F$-measure).
• $k$-fold CV: partition $Z$ into $Z_1,\dots ,Z_k$ with (i) $Z_i\ne \varnothing$, (ii) $Z_i\cap Z_j=\varnothing$, (iii) $\bigcup Z_i=Z$, (iv) sizes (nearly) equal. For $i=\mathrm{1..}k$: train on $P_i=Z\setminus Z_i$, predict $Z_i$. Score on the pooled predictions.

Mathematical formulation

• Number of trainings: LOO $=n$; $k$-fold $=k$. $k=n$ ⇒ $k$-fold = LOO.
• Each training set has $n-n/k=n(1-1/k)$ samples.
• LOO is deterministic (exhaustive); $k$-fold with random folds varies between runs. Repeating (e.g. 50 times) and averaging makes the estimate independent of the particular partition.

Key insights

• Bias–variance of the estimate: LOO training sets are nearly the full data (low bias) but cost $n$ trainings; $k$-fold is cheaper.
• The folds must be disjoint and cover everything.

Worked examples

Example 1 — Very Easy

• Problem: $n=10$ points, 3-fold CV. Possible fold sizes? How many models are trained?
• Asked: Sizes and count.
• Concept: Near-equal folds.
• Approach: $10=4+3+3$.
• Solution: Sizes $4,3,3$ (any order). One model per fold → 3 models.
• Final answer: $4,3,3$; 3 models.
• Key lesson: Folds differ by at most one element.

Example 2 — Easy

• Problem: $n=100$. For 5-fold CV and for LOO give training-set size and number of trainings.
• Asked: Four numbers.
• Concept: Counts.
• Approach: Formulas.
• Solution: 5-fold: test $=20$, train $=80$, 5 trainings. LOO: train $=99$, 100 trainings.
• Final answer: $(80,5)$ and $(99,100)$.
• Key lesson: LOO is $n/k$ times more expensive.

Example 3 — Moderate

• Problem: 1-D points $x=1,2,3,10,11$ with labels A,A,A,B,B. Run LOO with 1-NN and report accuracy. (Ties: both neighbours A.)
• Asked: LOO accuracy of 1-NN.
• Concept: LOO procedure.
• Approach: Remove each point, classify by nearest remaining.
• Solution: $x=1$: nearest is 2 (A) ✓. $x=2$: neighbours 1 and 3 equidistant (1), both A ✓. $x=3$: nearest 2 (A) ✓. $x=10$: nearest 11 (B) ✓. $x=11$: nearest 10 (B) ✓. 5/5.
• Final answer: $100\%$.
• Key lesson: Well-separated clusters give perfect LOO for 1-NN.

Example 4 — Hard

• Problem: Same data. Use LOO to choose between $k=1$ and $k=3$ nearest neighbours (majority vote).
• Asked: Best $k$.
• Concept: Parameter tuning by CV.
• Approach: Compute LOO accuracy for $k=3$.
• Solution: $x=1$: others 2(d1),3(d2),10(d9) → A,A,B → A ✓. $x=2$: 1,3 (d1,d1), 10 (d8) → A,A,B → A ✓. $x=3$: 2(d1),1(d2),10(d7) → A,A,B → A ✓. $x=10$: 11(d1),3(d7),2(d8) → B,A,A → A ✗. $x=11$: 10(d1),3(d8),2(d9) → B,A,A → A ✗. Accuracy $3/5=0.6$. $k=1$ gave $1.0$.
• Final answer: $k=1$ (LOO accuracy 1.0 vs 0.6).
• Key lesson: A $k$ larger than the size of the smaller class ($2$ B’s) forces errors; tune $k$ by CV.

Example 5 — Very Hard

• Problem: A 2-fold CV gives fold 1: $TP=2,FP=0,FN=2$; fold 2: $TP=8,FP=4,FN=0$. Compute $F$ (a) per fold then averaged; (b) on the pooled predictions as the lecture prescribes (“using the actual labels of $Z$”). Explain the difference.
• Asked: Two scores.
• Concept: Pooling vs averaging.
• Approach: $F=\frac{2TP}{2TP+FP+FN}$.
• Solution: (a) $F_1=\frac{4}{4+0+2}=0.6667$; $F_2=\frac{16}{16+4+0}=0.8$; mean $=0.7333$. (b) Pooled: $TP=10,FP=4,FN=2$ → $F=\frac{20}{20+4+2}=0.7692$.
• Final answer: Average-of-folds $0.733$; pooled $0.769$.
• Key lesson: $F$ is nonlinear in counts; fold-averaging weights small/odd folds equally, pooling weights data points equally. Be explicit about which you use.

Common mistakes

• Tuning on the test fold (data leakage) and reporting that score.
• Overlapping folds.
• Using stratification-free random folds with tiny classes.

Exam traps

• LOO is exhaustive and deterministic; $k$-fold with random partition is not.
• $k=n$ ⇒ LOO.

Connections

Pruning (C8), $k$ in kNN (C23), $C$ in SVM (C32), $\theta ,\beta$ parameters.

Mastery checklist

• Write both algorithms.
• State folds’ four properties.
• Use CV to pick a hyper-parameter.