PadhaikoAll subjects

Credibility: Evaluating What’s Been Learned

Data Mining (ENCT 435)

Open in the Padhaiko app

5.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.

Definition

Error Rate and Resubstitution Error

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).

  1. 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.
  2. 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).
  3. -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.
  4. 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:

  1. Quadratic Loss (Brier Score): Let for the true class and otherwise:

Minimized in expectation only when predicted probabilities equal true posterior probabilities.

  1. 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

Binary Confusion Matrix and Performance Metrics
Actual \ PredictedPredicted Positive ()Predicted Negative ()
Actual Positive ()TP (True Positive)FN (False Negative)
Actual Negative ()FP (False Positive)TN (True Negative)

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

AspectLift 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 capturedTrue Positive Rate ( to )
Random BaselineDiagonal line from to Diagonal line ()
Primary Use CaseDirect marketing / campaign targeting under fixed contact budgetComparing classifiers across all decision thresholds and class skews

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:

Numeric Prediction Evaluation Metrics
MetricFormulaKey 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.

Definition

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:

  1. : the number of bits needed to describe the model itself, and
  2. : the number of bits needed to encode the exceptions / errors of on .

The MDL principle selects the hypothesis minimizing total description length:


Worked Examples

Example 1

Cost-Sensitive Classification and Confusion Matrix Metrics (6 marks)

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.

  1. Compute Accuracy, Recall (TPR), Precision, FPR, and -score.
  2. Compute the total misclassification cost of this classifier.
  3. 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 .

Answer:
  1. Accuracy , Recall , Precision , FPR , .
  2. Total cost .
  3. Optimal cost-sensitive threshold: .
Example 2

Evaluating Numeric Prediction Metrics (MAE, RMSE, RAE, RRSE) (6 marks)

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 :

Answer:

, , (), ().

Example 3

Paired t-Test and Probabilistic Scoring (Brier & Log Loss) (6 marks)

  1. Schemes and are evaluated on the same -fold cross-validation split, yielding per-fold error differences . Compute the paired -statistic.
  2. 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:
Answer:
  1. Paired -statistic: (, ).
  2. Quadratic Loss ; Informational Loss .

Exercises

Practice Exercises — Evaluating Learned Models

Question 1

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:

Answer:

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 .

Question 2

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.

Answer:

The confidence interval is . A paired -test removes fold-to-fold difficulty variance by comparing both schemes on identical test folds.

Question 3

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 .

Answer:

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 ).

Question 4

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.

Answer:

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 .

Question 5

A medical screening model outputs disease probability for a patient. If a false negative costs and a false positive costs :

  1. Compute the expected cost of predicting Positive () vs. predicting Negative ().
  2. 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.

Answer:
  1. Expected cost of predicting Positive is vs. for predicting Negative.
  2. Optimal decision: Positive (), consistent with .
← Algorithms: The Basic MethodsImplementations: Real Machine Learning Schemes (part 1: 6.1–6.2) →