Evaluating the Accuracy of a Classifier or Predictor

1. Why Not Simply Use Training Accuracy?

The resubstitution (training-set) accuracy is optimistically biased: a model can memorise (overfit) the training data and still generalise poorly — the classic example is a 1-NN classifier, which has 0% training error but a large test error. Hence, evaluation must use data not seen during training.

Holdout method: split the data into two independent sets — a training set (typically 2/3) and a test set (1/3). Accuracy is measured on the test set.

 Full dataset (n tuples)
 +--------------------------+-----------------+
 |      TRAINING (2/3)      |   TEST (1/3)    |
 +--------------------------+-----------------+
          build model          measure accuracy

Problem — the estimate depends on the split. The same accuracy figure can vary with different partitions of the data, so confidence intervals or resampling methods are needed.

2. Random Sampling (Repeated Holdout)

Repeat the holdout $k$ times with random, stratified partitions (stratified = class proportions preserved in each set) and average:

\text{acc} = \frac{1}{k}\sum_{i=1}^{k}\text{acc}_i,\qquad \sigma = \sqrt{\frac{1}{k-1}\sum_{i=1}^{k}(\text{acc}_i-\overline{\text{acc}})^{2}}

Some tuples are never used for testing, while others are tested repeatedly; still, this is the simplest unbiased-in-expectation estimator.

3. Cross-Validation ( $k$ -fold CV)

Algorithm

Randomly partition the data into $k$ mutually exclusive subsets ("folds") $D_1, \dots, D_k$ , each of roughly equal size (stratified).
For each fold $i$ : train on all folds except $D_i$ , test on $D_i$ to get $\text{acc}_i$ .
Overall accuracy = average of the $k$ accuracies; every tuple is used for testing exactly once and for training $k-1$ times.

\text{acc}_{CV}=\frac{1}{k}\sum_{i=1}^{k}\text{acc}_i,\qquad \text{error}_{CV}=\frac{1}{k}\sum_{i=1}^{k}\Big(1-\frac{\text{correct}_i}{|D_i|}\Big)

Choice of $k$

$k$	Training size per fold	Notes
2	50%	Weak, high bias
5	80%	Good compromise
10	90%	Standard practice — lowest bias/variance trade-off, reasonable computation
$n$ (Leave-One-Out, LOO)	$n-1$ (almost all)	Nearly unbiased; $n$ model builds; high variance; computationally expensive; stratified always

Advantages of CV over a single holdout: all data are used both for training and testing; every tuple is tested exactly once; the estimate is less random and its variance can be reported. Limitation: computation × $k$ ; folds are not independent, so the training sets overlap (breaks strict independence assumptions); for time-series data folds must respect chronological order (forward-chaining / rolling-origin CV).

Stratified $k$ -fold cross-validation preserves class distribution in each fold — important for imbalanced classes.

4. Bootstrap

The 0.632 bootstrap draws $n$ tuples with replacement from a dataset of $n$ tuples; on average only $63.2\%$ of the tuples appear in the bootstrap sample, so the rest ( $\approx 36.8\%$ or $1-e^{-1}$ ) form the test set ("out-of-bag" data).

\lim_{n\to\infty}\Big(1-\frac{1}{n}\Big)^{n}=e^{-1}\approx 0.368

Each tuple has probability $1-(1-1/n)^{n}\approx 0.632$ of appearing. Accuracy estimate over $b$ bootstrap samples, correcting for the optimistic training accuracy:

\text{acc}_{boot}=\frac{1}{b}\sum_{i=1}^{b}\Big(0.632\times \text{acc}_{\text{test},i}+0.368\times \text{acc}_{\text{train},i}\Big)

Bootstrap is useful for small datasets and also gives standard errors/confidence intervals for almost any statistic; smoothed variants use a weight $1-(1-1/n)^{n}$ per tuple.

5. Estimating a Predictor's Accuracy (Numeric)

For numeric predictors, cross-validation and bootstrap are applied with the error measures instead of the accuracy fraction:

\text{MAE}_{CV}=\frac{1}{k}\sum_{i=1}^{k}\text{MAE}_i,\qquad \text{RMSE}_{CV}=\frac{1}{k}\sum_{i=1}^{k}\text{RMSE}_i

\text{Relative error}_{CV}=\frac{1}{k}\sum_{i=1}^{k}\Bigg(\frac{\sum_{x \in D_i}|y-\hat y|}{\sum_{x\in D_i}|y-\bar y|}\Bigg)

The last form is the relative error, which removes the influence of the scale of the target values (used e.g. in the Weka/C4.5 evaluation).

6. Model Comparison — Statistical Significance

$k$ -fold CV gives $k$ accuracy estimates per model (not independent!). To compare models A and B on the same folds:

\text{paired } t\text{-statistic: } t=\frac{\overline{d}}{\sqrt{\dfrac{\sum_{i=1}^{k}(d_i-\bar d)^2}{k(k-1)}}},\qquad d_i=\text{acc}_{A,i}-\text{acc}_{B,i}

with $k-1$ degrees of freedom — reject "models are equal" if $|t|$ exceeds the critical value (this is the cross-validated paired t-test of Dietterich, who also proposes 5×2 CV $t$ -test, McNemar's test and a test on differences of proportions for more reliable comparisons).

7. Practical Issues in Evaluation

Issue	Recommendation
Class imbalance	Stratified folds, choose measures like F1/AUC/recall, resample (SMOTE) inside the fold
Data leakage	All preprocessing (normalisation, feature selection, discretisation, oversampling) must be fitted inside each fold, not on the whole dataset
Hyper-parameter tuning	Use a separate validation set or nested CV so the test set stays untouched
Temporal data	Time-ordered (rolling-origin) splits, no random shuffling
Grouped data	Group-aware CV so the same patient/customer is not in both train and test
Reporting	State the number of folds, the split strategy, mean ± standard deviation, and the metric used

8. Exam Points

Explain holdout, random subsampling, cross-validation ( $k$ -fold and LOO) with diagrams and advantages — 10 marks (very frequent).
Explain the 0.632 bootstrap and why approximately 63.2% of tuples appear — 5-7 marks.
How do you estimate the accuracy of a predictor for numeric prediction (relative error, CV)? — 5 marks.
Discuss the paired $t$ -test for comparing two classifiers — 5 marks.
Why is the training-set accuracy not a valid estimate? — 3 marks.

Evaluating the Accuracy of a Classifier or Predictor