Credibility: Evaluating What’s Been Learned
Open in the Padhaiko app5.1 Training and testing: Error rate, resubstitution error, and cross-validation
Building a model on training data is only half the task; we must also estimate credibly how well that model will perform on unseen future instances.
Error Rate and Resubstitution Error
- Error Rate: The fraction of instances misclassified by a model on a dataset: .
- Resubstitution Error (Training Error): The error rate measured by testing a learned model on the same dataset that was used to train it. Because the model was explicitly fitted to those rows (and may memorize noise), resubstitution error is optimistically biased and never a reliable measure of generalization.
Holdout, Validation, and Cross-Validation Protocols
To measure genuine generalization error, training and test data must remain strictly separated (including any normalization, imputation, or feature selection parameters, which must be computed on training data only).
- Holdout Method (and Stratification): Reserve a fraction (typically ) as an independent test set and train on the remaining . Use stratified sampling so each class appears in the same proportion in both training and test sets. Averaging across multiple random holdouts (repeated holdout) reduces split variance.
- Three-Way Split (Train / Validation / Test): Whenever hyperparameters or competing models are tuned, divide data into Training (fit model weights/trees), Validation (compare models and pick hyperparameters), and Test (held completely untouched until the single final evaluation).
- -Fold Cross-Validation: Partition the dataset into approximately equal, stratified folds (commonly ). Run rounds: in round , hold out fold for testing and train on the remaining folds. Average the test errors to estimate generalization error, then train the final deployable model on all of the data.
- Leave-One-Out Cross-Validation (LOOCV): Extreme case ( folds of size ). Nearly unbiased and deterministic, though computationally expensive ( trainings) and unsuitable if stratified balance breaks.
- The Bootstrap: Sample instances with replacement from rows for training; each instance has probability of never being picked, leaving as the out-of-bag test set. The bootstrap combines test and resubstitution error as .
5.2 Comparing data mining schemes and predicting probabilities
Comparing Data Mining Schemes
Observing that Scheme A achieves accuracy and Scheme B achieves on one test split does not prove Scheme A is truly superior—the gap could be random sampling noise.
Confidence Intervals for a Single Error/Success Rate
On independent test instances with successes (), the standard error is , giving a large-sample normal confidence interval:
(For confidence, ; for small , exact binomial or Wilson bounds are preferred.)
Paired -Test Across Cross-Validation Folds
To compare two learning schemes and on the same folds, measure the per-fold difference for , with sample mean and sample standard deviation :
Because every fold-pair uses the exact same test fold, the paired test removes fold-difficulty variance.
Predicting Probabilities (Proper Scoring Rules)
Many applications require calibrated class probability estimates rather than hard class labels (e.g., medical risk scores or ranking). Two classic scoring functions penalize poorly calibrated or overconfident probabilities:
- Quadratic Loss (Brier Score): Let for the true class and otherwise:
Minimized in expectation only when predicted probabilities equal true posterior probabilities.
- Informational Loss (Log Loss / Cross-Entropy): If is the true class with predicted probability :
Heavily penalizes confident mistakes ( drives loss toward ), encouraging well-hedged probabilities.
5.3 Counting the cost: Cost-sensitive classification, lift charts, and ROC curves
Standard accuracy treats all mistakes equally. In real applications, a false negative (missing a cancerous tumor or fraudulent transaction) can cost to more than a false positive (an extra screening test or SMS verification).
Confusion Matrix and Derived Metrics
| Actual \ Predicted | Predicted Positive () | Predicted Negative () |
|---|---|---|
| Actual Positive () | TP (True Positive) | FN (False Negative) |
| Actual Negative () | FP (False Positive) | TN (True Negative) |
- True Positive Rate (TPR / Recall / Sensitivity):
- False Positive Rate (FPR):
- Precision: , -Score:
Cost-Sensitive Classification
Given misclassification costs (cost of predicting when true is ) and (cost of predicting when true is ), total expected cost is:
For a model outputting , predicting incurs expected cost , while predicting incurs expected cost . Therefore, predict whenever:
Costs can also be incorporated by reweighting/resampling training instances in proportion to class costs (or via MetaCost).
Lift Charts and ROC Curves
| Aspect | Lift Chart (Cumulative Gains) | ROC Curve |
|---|---|---|
| Horizontal Axis () | Sample size / fraction of population contacted ( to ) | False Positive Rate ( to ) |
| Vertical Axis () | Number or percentage of true positives captured | True Positive Rate ( to ) |
| Random Baseline | Diagonal line from to | Diagonal line () |
| Primary Use Case | Direct marketing / campaign targeting under fixed contact budget | Comparing classifiers across all decision thresholds and class skews |
- Lift Factor: At sample fraction , (e.g., capturing of responders in the top ranked contacts gives a Lift of ).
- AUC (Area Under the ROC Curve): Summarizes an entire ROC curve in ; equals the probability that a randomly chosen positive instance receives a higher predicted score than a randomly chosen negative instance.
5.4 Evaluating numeric prediction and the Minimum Description Length (MDL) principle
Evaluating Numeric Prediction
When predicting continuous values against actual targets (with sample mean ), standard error metrics measure accuracy from complementary angles:
| Metric | Formula | Key Property |
|---|---|---|
| Mean Squared Error (MSE) | Penalizes large errors heavily; differentiable | |
| Root Mean Squared Error (RMSE) | Same units as target ; sensitive to outliers | |
| Mean Absolute Error (MAE) | Equal weight per unit error; more robust to outliers | |
| Root Relative Squared Error (RRSE) | Scale-free ratio against predicting constant mean | |
| Relative Absolute Error (RAE) | Scale-free absolute ratio against predicting | |
| Correlation Coefficient () | Measures linear alignment ( to ), ignoring scale/offset |
The Minimum Description Length (MDL) Principle
How do we prevent overfitting when comparing a simple model against a complex model on training data alone? The Minimum Description Length (MDL) principle (Rissanen, ) formalizes Occam's Razor as an information-transmission problem.
Minimum Description Length (MDL) Principle
Suppose a sender wants to transmit all target labels of dataset to a receiver who already possesses the input attributes. By choosing a hypothesis (model) , the sender transmits:
- : the number of bits needed to describe the model itself, and
- : the number of bits needed to encode the exceptions / errors of on .
The MDL principle selects the hypothesis minimizing total description length:
- Too simple ( underfits): is tiny, but many errors occur so is huge.
- Too complex ( overfits): , but encoding a massive tree or memorized table makes huge.
- Optimal tradeoff: MDL naturally balances model complexity against training fit without needing a separate validation set, and is widely used in decision-tree pruning, rule pruning, and numeric discretization.
Worked Examples
Cost-Sensitive Classification and Confusion Matrix Metrics
A fraud-detection classifier is evaluated on test transactions, yielding the confusion matrix:
- , , , .
Suppose missing a fraudulent transaction costs currency units, whereas falsely flagging a legitimate transaction costs currency units.
- Compute Accuracy, Recall (TPR), Precision, FPR, and -score.
- Compute the total misclassification cost of this classifier.
- Compute the cost-optimal probability threshold above which a transaction should be flagged as fraud.
Computing standard confusion-matrix metrics ():
Computing total misclassification cost:
Deriving the cost-optimal decision threshold : Flagging a transaction when gives:
Any transaction with predicted fraud probability should be flagged rather than waiting for .
- Accuracy , Recall , Precision , FPR , .
- Total cost .
- Optimal cost-sensitive threshold: .
Evaluating Numeric Prediction Metrics (MAE, RMSE, RAE, RRSE)
On test instances, the actual target values are and a regression model predicts . Compute MAE, RMSE, RAE, and RRSE.
Computing errors and actual mean :
- Errors: , , , .
- Mean of actuals: .
- Deviations from mean : , , , .
Computing MAE and RMSE:
Computing RAE and RRSE relative to predicting :
, , (), ().
Paired t-Test and Probabilistic Scoring (Brier & Log Loss)
- Schemes and are evaluated on the same -fold cross-validation split, yielding per-fold error differences . Compute the paired -statistic.
- On a binary test instance whose true class is Positive (), a classifier predicts probabilities . Compute its Quadratic Loss (Brier Score) and Informational Loss (bits).
Part 1 — Computing the paired -statistic ():
Part 2 — Computing Quadratic Loss and Informational Loss:
- Quadratic Loss (Brier Score):
- Informational Loss:
- Paired -statistic: (, ).
- Quadratic Loss ; Informational Loss .
Exercises
Practice Exercises — Evaluating Learned Models
Why is resubstitution error an unreliable estimate of model credibility? Distinguish between stratified -fold cross-validation and the bootstrap, and compute the bootstrap error estimate when out-of-bag test error is and resubstitution training error is .
Why Resubstitution Error Fails: Resubstitution error evaluates a model on the exact same instances it memorized or fitted during training, producing an overly optimistic bias—for example, an unpruned -NN or full decision tree can get training error while performing poorly on new data.
Stratified -Fold CV vs. Bootstrap:
- Stratified -fold CV partitions the data without replacement into equal folds preserving class proportions, training on and testing on ten times so every instance is tested exactly once.
- Bootstrap draws samples with replacement (leaving out-of-bag for testing); because the bootstrap training sample contains duplicates and only distinct instances, its test error is slightly pessimistic, so it blends test error () and training error ().
Computing the Bootstrap Estimate:
Resubstitution error is optimistically biased because training rows are reused for testing. Stratified -fold CV uses disjoint folds without replacement, whereas the bootstrap samples with replacement and weights out-of-bag vs. training error. Here .
A classifier achieves correct predictions on an independent test set of instances. Compute the confidence interval () for its true success rate, and explain why the paired -test is preferred over an unpaired test when comparing two classifiers on -fold CV.
Computing the Confidence Interval: With and :
Why Paired -Test Is Preferred: Individual folds vary in difficulty. Evaluating both classifiers on the exact same folds and taking fold-by-fold differences cancels out shared fold-difficulty variance, yielding higher statistical power than treating the two sets of fold accuracies as unpaired samples.
The confidence interval is . A paired -test removes fold-to-fold difficulty variance by comparing both schemes on identical test folds.
What is an ROC curve and what does AUC measure? Suppose a small test set has positive and negative instances, and a classifier ranks the top predicted scores as: (+, -, +, +). Compute the (FPR, TPR) coordinates after scanning the first and ranked instances, and sketch how a Lift Chart plots those same predictions differently.
ROC Curve and AUC Definition: An ROC curve plots True Positive Rate () against False Positive Rate () across all classification thresholds from highest score to lowest. AUC (Area Under the ROC Curve) measures ranking quality—the probability that a randomly drawn positive instance is scored higher than a randomly drawn negative instance ( = random, = perfect).
Computing (FPR, TPR) along the top ranked predictions (+, -, +, +) with :
- Start at .
- After rank (
+): . - After rank (
-): . - After rank (
+): . - After rank (
+): .
How a Lift Chart Differs: A Lift Chart plots the cumulative true positives captured () on the -axis against the total sample percentage () on the -axis rather than . At of the sample, capturing of positives gives a lift of .
ROC plots vs. across thresholds; AUC measures pairwise ranking probability. The first four ROC points are , , , and . A Lift Chart instead plots captured positives against overall sample fraction (here of positives in the top , lift ).
State the Minimum Description Length (MDL) principle and explain how it prevents overfitting when selecting between two candidate decision trees without using a validation set.
The MDL Formulation: MDL chooses the hypothesis minimizing , where is the bit-length required to specify the model structure and is the bit-length required to specify the misclassified training instances (deviations from ).
Preventing Overfitting Without a Validation Set: Suppose Tree is small and misclassifies a few noisy points, whereas Tree adds many extra branches solely to memorize those noisy points. Adding branches lowers slightly, but increases substantially to encode the extra split tests and leaves. Because , MDL rejects the overfitted tree using training data alone.
MDL minimizes (model encoding cost plus error encoding cost). It prevents overfitting because extra tree branches that only memorize noise increase more than they reduce .
A medical screening model outputs disease probability for a patient. If a false negative costs and a false positive costs :
- Compute the expected cost of predicting Positive () vs. predicting Negative ().
- State the optimal decision and verify it against the cost-ratio threshold .
Computing Expected Cost of Both Decisions (, ):
- If we predict Positive (): we incur whenever the true class is Negative (probability ):
- If we predict Negative (): we incur whenever the true class is Positive (probability ):
Optimal Decision and Threshold Check: Since , predicting Positive () minimizes expected cost! Equivalently, the cost threshold is:
Because , predicting Positive is optimal.
- Expected cost of predicting Positive is vs. for predicting Negative.
- Optimal decision: Positive (), consistent with .