12 - Overfitting and Cross Validation

Recap: Decision Trees

  • Definition: A popular machine learning algorithm for both classification and regression tasks.
  • Splitting Criterion: Measures how well a feature splits the data. Common criteria include:
    • Entropy: A measure of the impurity or disorder in a dataset.
    • Gini Impurity: Another measure of impurity that evaluates how often a randomly chosen element would be incorrectly labeled.
    • Information Gain: The reduction in uncertainty about the class label after the dataset is split on a feature.
  • Recursive Binary Splitting: The method used to split data at each node of the tree.
  • Overfitting: A common issue with decision trees is overfitting, especially when there are many features.
  • Solution: Various pruning techniques are required to prevent overfitting.

Overfitting in Decision Trees

  • Definition: When a decision tree model is overly complex, capturing noise in the training data rather than the underlying pattern.
  • Symptoms: The tree has too many branches due to excessive complexity, leading to poor generalization.
  • Solutions:
    1. Stop Growing: Halt tree growth when data splits are not statistically significant.
    2. Simplify Attributes: Remove irrelevant attributes manually when possible.

Pruning

  • Definition: A technique to reduce model complexity and prevent overfitting by replacing a subtree with a leaf node.
  • Pruning Rule: Replace a subtree with a leaf node if the expected error rate in the subtree is greater than in the leaf.
  • Objective: Simplify the decision tree by removing branches that do not improve accuracy.

Types of Pruning

Pre-pruning (Early Stopping)
  • Stops growth of the tree before it becomes too complex using criteria such as:
    • Max Depth: Limits the maximum depth of the tree.
    • Min Samples to Split: Sets a minimum number of samples required to split a node.
    • Min Samples at Leaf: Sets a minimum number of samples required at a leaf node.
    • Max Leaf Nodes: Limits the number of leaf nodes.
    • Min Improvement: Requires a minimum improvement in the splitting criterion.
Post-pruning (Backward Pruning)
  • Process:
    1. Grow a full decision tree.
    2. Remove non-essential branches that do not improve predictive ability.
  • Benefit: Simplifies the tree while preserving accuracy.

The Post-Pruning Process with scikit-learn

  1. Train a full decision tree without pruning.
  2. Obtain effective alphas and total impurities at each step.
  3. Generate pruned trees using different ccp_alpha values.
  4. Evaluate each tree on a validation set to identify the optimal ccp_alpha.
  5. Select and evaluate the best pruned tree on a test set.
  • Effective alpha (α): A parameter that balances the complexity of the tree with its fit to the training data.

Validation during the Pruning Process

  • Train, Prune, Validate:
    • Train: Grow the tree
    • Prune: Apply pre- or post-pruning criteria
    • Validate: Assess performance on a validation set
  • Goal of Pruning:
    • Balance model complexity and simplicity to avoid overfitting and underfitting.

Model Overfitting

  • Definition: Overfitting occurs when a model learns both patterns and noise in the training data, resulting in poor performance on new data.
  • Indicator: High variance suggests the model captures noise and fails to generalize.
  • Bias and Stereotypes:
    • Models can learn biases present in training data, leading to unfair outcomes.

Assessing Model Performance

  • Goals of Evaluation: Reduce errors, improve generalization, and increase accuracy.
  • Key Metrics:
    • Accuracy: Proportion of correct predictions.
    • Precision: Proportion of true positives among predictions.
    • Recall: Proportion of true positives among actual positives.
    • F1 Score: Harmonic mean of precision and recall.
    • Mean Squared Error (MSE): Average squared difference between predicted and actual values.

Train/Validate/Test Split

  • Common Practice: Split data into training (60%), validation (20%), and test sets (20%).
  • Purpose: Train models, evaluate performance, tune hyperparameters, and prevent overfitting.
  • Validation Set: Helps with model tuning and acts as unseen data during development.

Limitations of Simple Train/Validate/Test Split

  • Issues:
    • Depends heavily on the random split chosen.
    • May lead to biases and variance trade-offs.

Cross-Validation (CV)

  • Definition: A resampling procedure used to evaluate machine learning models on a limited data sample.
  • Primary Goals: Hyperparameter optimization and model selection.
  • Benefits of CV: Improved generalization, overfitting, underfitting prevention.

K-Fold Cross-Validation

  • Process: The dataset is divided into k folds, and the model is trained k times, each time using k-1 folds for training and 1 for validation/testing.
  • Advantage: A reliable estimate of model performance and helps detect overfitting.

Leave-One-Out Cross-Validation (LOOCV)

  • Description: Each instance serves as a validation set once, with the remaining instances forming the training set.
  • Use Case: Ideal for small datasets to maximize data utilization.

Stratified K-Fold Cross-Validation

  • Purpose: Ensures each fold represents the overall dataset's target variable distribution, particularly useful for imbalanced datasets.

Hyperparameters and Hyperparameter Tuning

  • Definition: Parameters of the learning algorithm that affect behavior and performance. Examples include maximum depth, learning rate, regularization strength.
  • Tuning Methods: Grid search, random search, Bayesian optimization, and gradient-based optimization.

Model Selection Process

  1. Identify candidate models.
  2. Train models.
  3. Validate models.
  4. Compare performance.
  5. Select the best model.
  6. Evaluate selected model to ensure generalization to new data.