M2-023M2: Classical Machine LearningDecision TreesEasy
⚡Flashcard Drill➔Mastery:

Detail Pre-Pruning and Post-Pruning Strategies to Prevent Overfitting in Decision Trees

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-024 →
📐 Mathematical Definition
cost complexity: Rα(T)=R(T)+α∣T∣\text{cost complexity}:\ R_\alpha(T)=R(T)+\alpha|T|
⚡ One-Sentence Core Answer
Decision trees prevent overfitting via Pre-Pruning (stopping growth early via depth and sample limits) and Post-Pruning (growing a full tree and pruning subtrees using Cost-Complexity Pruning).

📌 Key Takeaways

  • •
    Pre-Pruning parameters: max_depth (restricts tree levels), min_samples_split (minimum samples to allow split), min_samples_leaf (minimum samples per terminal leaf), min_impurity_decrease.
  • •
    Post-Pruning (Cost-Complexity Pruning): Minimizes Rα(T)=R(T)+α∣T∣R_\alpha(T) = R(T) + \alpha |T|, balancing empirical misclassification R(T)R(T) against tree leaf count ∣T∣|T|.
  • •
    Why Post-Pruning is superior: Pre-pruning suffers from 'myopia' (stops early before reaching split combinations that together provide high gain); post-pruning evaluates full context.

📐 Mathematical Derivations

Minimal Cost-Complexity Pruning (Breiman et al., 1984): For any subtree TtT_t rooted at node tt, the cost of collapsing TtT_t into a single leaf node tt is R(t)+αR(t) + \alpha. The cost of keeping the subtree is R(Tt)+α∣Tt∣R(T_t) + \alpha |T_t|. The subtree is preferred as long as R(Tt)+α∣Tt∣<R(t)+αR(T_t) + \alpha |T_t| < R(t) + \alpha. Setting these equal defines the critical threshold αcrit(t)=R(t)−R(Tt)∣Tt∣−1\alpha_{\text{crit}}(t) = \frac{R(t) - R(T_t)}{|T_t| - 1}. As complexity penalty α\alpha increases from 0 to ∞\infty, it generates a nested sequence of pruned subtrees T0⊃T1⊃T2⋯⊃{troot}T_0 \supset T_1 \supset T_2 \dots \supset \{t_{\text{root}}\}. Cross-validation is used to select optimal α∗\alpha^* (parameter ccp_alpha in scikit-learn).

🏭 Production Trade-offs

In industrial pipelines: (1) Standalone decision trees require aggressive pre-pruning or post-pruning to prevent memorizing training noise. (2) In Random Forests, individual trees are deliberately grown deep and unpruned (maximizing individual tree capacity and diversity) because variance is subsequently eliminated by ensemble averaging. (3) In GBDT, trees are shallow (depth 3 to 6) weak learners.
⚠️ Common Interview Pitfalls
  • ✕
    Setting min_samples_leaf too small in noisy datasets (leads to leaves fitting individual outlier observations).
  • ✕
    Relying solely on max_depth without tuning min_samples_split.
🎯 Interviewer Follow-up Inquiries
  • ?
    How does scikit-learn CostComplexityPruning compute the sequence of effective alphas?
  • ?
    Why are shallow trees (depth 3-6) preferred in Gradient Boosting while deep trees are preferred in Random Forests?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM2-022: Explain Decision Tree Splitting Criteria: Information Gain, Gain Ratio, and Gini Impurity📋 Back to BankNext →M2-024: Explain Why Decision Trees are Invariant to Monotonic Transformations and Their Inductive Bias