Model Generalization: Error and Overfitting

The performance of a machine learning model is primarily assessed by its error on data. The error rate is the proportion of incorrectly classified samples to the total number of samples. Accuracy is the complement: Accuracy = 1 - Error Rate.

For a dataset with \(m\) samples and \(a\) misclassifications, the error rate \(E = a/m\).

More broadly, error refers to the discrepancy between a model's predictions and the true outputs. Error on the training data is training error; error on new, unseen data is generalization error (or test error). The core goal is to build models that perform well on new data.

Two critical concepts related to generalization are:

• Overfitting: The model learns the training data too well, including its noise and specific details, causing poor performence on new data.
• Underfitting: The model fails to capture the underlying patterns in the training data, resulting in poor performance on both training and new data.

Underfitting is often due to insufficient model capacity and can be addressed by increasing complexity. Overfitting is an inherent challenge in machine learning; it can be mitigated but not entirely eliminated. Common techniques to reduce overfitting include regularization and dropout.

Methods for Model Evaluation

To estimate a model's generalization capability, we typically evaluate it on a separate test set. The test error serves as an approximation of the generalization error. It is crucial that the test set is disjoint from the training set to ensure a fair assessment.

Given a dataset \(D\) of \(m\) samples, we need to split it into training set \(S\) and test set \(T\). Common splitting strategies include:

Hold-Out Method

The dataset \(D\) is randomly partitioned into two mutually exclusive subsets: a training set \(S\) and a test set \(T\), such that \(S \cup T = D\) and \(S \cap T = \emptyset\).

To maintain the data distribution, stratified sampling is often used, preserving the class proportions in both sets. Since a single random split can yield unstable estimates, the hold-out process is usually repeated multiple times (e.g., 100 times), and the average performance across all runs is reported. Typical splits allocate 60% to 80% of data for training.

Cross-Validation

In k-fold cross-validation, dataset \(D\) is divided into \(k\) similarly sized, mutually exclusive folds. Each fold is created using stratified sampling. The model is trained \(k\) times: each time, \(k-1\) folds are used for training, and the remaining fold is used for testing. The final performance metric is the average of the \(k\) test results. Common values for \(k\) are 5, 10, or 20. To increase reliability, the entire k-fold process can be repeated \(p\) times with different random splits (e.g., 10 repetitions of 10-fold CV).

A special case is Leave-One-Out (LOO) validation, where \(k = m\) (the number of samples). This provides an almost unbiased estimate but is computationally expensive for large datasets.

Bootstrap Method

Bootstrap sampling involves creating a new dataset \(D'\) of size \(m\) by randomly selecting samples from \(D\) with replacement. Some original samples will appear multiple times in \(D'\), while others may not appear at all. The probability that a given sample is not included in \(D'\) is approximately 0.368. \(D'\) is used for training, and the out-of-bag samples (\(D \setminus D'\)) form the test set. This method is useful for small datasets but can introduce bias as it alters the original data distribution.

Parameter Tuning and Final Model

During model development, data is typically divided into three sets:

• Training Set: Used to fit the model.
• Validation Set: Used to evaluate model performance during development and for hyperparameter tuning.
• Test Set: Used only once to provide a final, unbiased estimate of the model's generalization performance.

Performence Metrics

Evaluating a model requires quantitative measures of its performance. Common metrics include:

Error Rate and Accuracy

For classification tasks:

• Error Rate: \(E(f, D) = \frac{1}{m} \sum_{i=1}^{m} \mathbb{I}(f(x_i) \neq y_i)\)
• Accuracy: \(\text{acc}(f, D) = 1 - E(f, D)\)

Here, \(\mathbb{I}(\cdot)\) is the indicator function, which returns 1 if the condition is true, otherwise 0.

Precision and Recall

For binary classification, predictions can be categorized into:

• True Positive (TP): Correctly predicted positive.
• False Positive (FP): Incorrectly predicted positive (actual negative).
• True Negative (TN): Correctly predicted negative.
• False Negative (FN): Incorrectly predicted negative (actual positive).

Precision measures the proportion of correctly identified positive predictions among all predicted positives: \(P = \frac{TP}{TP + FP}\).

Recall (or Sensitivity) measures the proportion of actual positives correctly identified: \(R = \frac{TP}{TP + FN}\).

Precision and recall often trade off against each other. The F1 Score provides a harmonic mean of the two: \(F_1 = \frac{2 \cdot P \cdot R}{P + R}\). A more general form, the \(F_\beta\) score, allows weighting recall or precision differently: \(F_\beta = \frac{(1 + \beta^2) \cdot P \cdot R}{\beta^2 \cdot P + R}\), where \(\beta > 0\).

ROC Curve and AUC

For models that output a score or probability, the Receiver Operating Characteristic (ROC) curve plots the True Positive Rate (TPR) against the False Positive Rate (FPR) at various classification thresholds.

• True Positive Rate (TPR) or Recall: \(TPR = \frac{TP}{TP + FN}\)
• False Positive Rate (FPR): \(FPR = \frac{FP}{FP + TN}\)

The Area Under the ROC Curve (AUC) provides a single scalar value summarizing the model's ranking performance across all thresholds. A model with a higher AUC is generally better. The diagonal line (TPR = FPR) represents random guessing.

Cost-Sensitive Evaluation

In many real-world applications, different types of misclassification errors have different consequences. A cost matrix defines the penalty \(cost_{ij}\) for misclassifying a sample from class \(i\) as class \(j\). Typically, \(cost_{ii} = 0\). The goal shifts from minimizing errors to minimizing the total cost. The cost-sensitive error rate is:

\(E(f; D, cost) = \frac{1}{m} \left[ \sum_{x_i \in D^+} \mathbb{I}(f(x_i) \neq y_i) \cdot cost_{01} + \sum_{x_i \in D^-} \mathbb{I}(f(x_i) \neq y_i) \cdot cost_{10} \right]\),

where \(D^+\) and \(D^-\) are the positive and negative subsets of \(D\).

For cost-sensitive analysis, a cost curve can be plotted, with the x-axis representing the probability cost of positive examples and the y-axis representing the normalized expected cost.

Statistical Comparison of Models

Comparing models based solely on point estimates (e.g., a single accuracy score) can be misleading due to variability. Statistical hypothesis tests provide a framework for more reliable comparisons.

Binomial Test: Used to test if a model's true error rate \(\epsilon\) is less than or equal to a hypothesized value \(\epsilon_0\), given a observed test error \(\hat{\epsilon}\).

t-Test: Commonly used when comparing two models via cross-validation. The paired t-test analyzes the differences in performance across the same data folds to determine if the mean difference is statistically significant.

McNemar's Test: Applicable to two models evaluated on the same test set. It uses a contingency table of agreement/disagreement to test the null hypothesis that both models have the same error rate.

Friedman Test with Nemenyi Post-hoc: Used for comparing multiple algorithms across several datasets. It ranks the algorithms on each dataset and tests if the average ranks differ significantly. If the Friedman test rejects the null hypothesis (that all algorithms perform equally), the Nemenyi post-hoc test can identify which specific pairs of algorithms differ significantly.

Bias-Variance Decomposition

The expected generalization error of a learning algorithm can be decomposed into three components: bias, variance, and irreducible noise.

For a test sample \(x\):

• Bias measures the difference between the expected prediction of the model and the true value. High bias indicates underfitting.
• Variance measures the variability of the model's predictions for \(x\) across different training sets. High variance indicates overfitting.
• Noise represents the inherent uncertainty in the data.

The decomposition shows: Expected Generalization Error = Bias² + Variance + Noise². A good model seeks to minimize both bias and variance.

Implementation Examples

Hold-Out Split

from sklearn.model_selection import train_test_split

# X: feature matrix, y: target vector
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=42)

Cross-Validation

from sklearn.model_selection import cross_val_score
from sklearn.linear_model import LogisticRegression

classifier = LogisticRegression(max_iter=200)
cv_scores = cross_val_score(classifier, X, y, cv=5, scoring='accuracy')
print(f"CV Scores: {cv_scores}")
print(f"Mean CV Score: {cv_scores.mean():.3f}")

Mean Squared Error

from sklearn.metrics import mean_squared_error

# y_true: actual values, y_pred: model predictions
mse = mean_squared_error(y_true, y_pred)
print(f"Mean Squared Error: {mse:.4f}")

Precision, Recall, F1

from sklearn.metrics import precision_score, recall_score, f1_score

precision = precision_score(y_true, y_pred)
recall = recall_score(y_true, y_pred)
f1 = f1_score(y_true, y_pred)
print(f"Precision: {precision:.3f}, Recall: {recall:.3f}, F1-Score: {f1:.3f}")

ROC Curve and AUC

from sklearn.metrics import roc_curve, auc
import matplotlib.pyplot as plt

# Assume classifier outputs probabilities for the positive class
y_scores = model.predict_proba(X_test)[:, 1]
fpr, tpr, thresholds = roc_curve(y_test, y_scores)
roc_auc = auc(fpr, tpr)

plt.figure()
plt.plot(fpr, tpr, label=f'ROC curve (AUC = {roc_auc:.2f})')
plt.plot([0, 1], [0, 1], 'k--')  # Diagonal line
plt.xlabel('False Positive Rate')
plt.ylabel('True Positive Rate')
plt.title('Receiver Operating Characteristic')
plt.legend()
plt.show()