Tree-Based Methods in Economics

Classification and Regression Trees (CART)

Overview

Tree-based methods for regression and classification involve:

Stratifying or segmenting the predictor space into simple regions
Making predictions based on the mean/mode of training observations in each region
The splitting rules can be summarized in a tree structure

Key Methods:

Single Decision Trees
Bagging (Bootstrap Aggregating)
Random Forests
Boosting

Why Tree-Based Methods?

Advantages ✓

Easy to explain and interpret
Can be displayed graphically
Handle qualitative predictors naturally
Mirror human decision-making
No need for dummy variables

Disadvantages ✗

Lower prediction accuracy than other methods (for single trees)
High variance
Can overfit easily

Solution: Ensemble methods (Bagging, Random Forests, Boosting) dramatically improve performance!

Decision Tree Example: Baseball Salaries

Predicting log salary based on Years of experience and Hits:

                Years < 4.5
                /          \
           Yes /            \ No
              /              \
          5.11          Hits < 117.5
                        /          \
                   Yes /            \ No
                      /              \
                   6.00             6.74

Three regions created:

R₁: Years < 4.5 → Salary = 5.11
R₂: Years ≥ 4.5, Hits < 117.5 → Salary = 6.00
R₃: Years ≥ 4.5, Hits ≥ 117.5 → Salary = 6.74

How Trees Work: Building Process

Recursive Binary Splitting (greedy, top-down approach):

Start with all observations in one region
For each predictor Xⱼ and cutpoint s, split into:
- {X | Xⱼ < s}
- {X | Xⱼ ≥ s}
Choose split that minimizes RSS (regression) or maximizes purity (classification)
Repeat for each resulting region
Stop when regions are small enough

Regression Trees: Minimize RSS

Objective: Find boxes R₁, …, Rⱼ that minimize:

\[\sum_{j=1}^{J} \sum_{i \in R_j} (y_i - \hat{y}_{R_j})^2\]

where \(\hat{y}_{R_j}\) is the mean response in region Rⱼ

Prediction for new observation:

Assign it to one of the regions and predict the mean of training observations in that region

Classification Trees: Splitting Criteria

Cannot use RSS for classification. Instead use:

Classification Error Rate: \[E = 1 - \max_k(\hat{p}_{mk})\]
Gini Index (preferred for growing trees): \[G = \sum_{k=1}^{K} \hat{p}_{mk}(1 - \hat{p}_{mk})\]
Cross-Entropy/Deviance: \[D = -\sum_{k=1}^{K} \hat{p}_{mk} \log \hat{p}_{mk}\]

where \(\hat{p}_{mk}\) = proportion of training observations in region m from class k

Tree Pruning: Avoiding Overfitting

Problem: Large trees overfit → poor test performance

Solution: Cost Complexity Pruning

Minimize: \[\sum_{m=1}^{|T|} \sum_{i \in R_m} (y_i - \hat{y}_{R_m})^2 + \alpha|T|\]

|T| = number of terminal nodes
α = tuning parameter (controls trade-off)
Select α using cross-validation
Larger α → smaller tree (more pruning)

Complete Tree Algorithm

Grow large tree T₀ using recursive binary splitting
Apply cost complexity pruning to get sequence of subtrees for each α
Use K-fold cross-validation:
- For each fold, repeat steps 1-2
- Calculate MSE/error on left-out fold for each α
- Average results across folds
Choose α that minimizes cross-validation error
Return subtree from step 2 corresponding to chosen α

Economic Application Example

Heart Disease Classification (303 patients, 13 predictors)

Key predictors identified:

Thal (Thallium stress test result)
Ca (Number of vessels colored by fluoroscopy)
ChestPain type
MaxHR (Maximum heart rate)
Age, Sex, Cholesterol, etc.

Result: Cross-validation selects tree with 6 terminal nodes

Test error ≈ 25% (vs. 45% for single large tree)

Trees vs Linear Models

Linear Boundary

     |
  ●  |  ○
 ●●  | ○○
●●●●●|○○○○
─────+─────

Works well when true boundary is linear

Non-linear Boundary

  ○○○|●●●
  ○○ | ●●
 ○○──┼──●
  ●  |  ○

Trees excel when relationships are complex/non-linear

Rule of thumb: Try both approaches! Trees are better for highly non-linear relationships

Bagging: Bootstrap Aggregating

Key Insight: Averaging reduces variance!

If we have n independent observations Z₁, …, Zₙ with variance σ²:

\[\text{Var}(\bar{Z}) = \frac{\sigma^2}{n}\]

Bagging Algorithm:

Take B bootstrap samples from training data
Build tree on each bootstrap sample → \(\hat{f}^{*b}(x)\)
Average predictions:

\[\hat{f}_{\text{bag}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}^{*b}(x)\]

For classification: Use majority vote across B trees

Out-of-Bag (OOB) Error Estimation

Clever trick: Each bagged tree uses ≈ 2/3 of observations

Remaining ≈ 1/3 are out-of-bag (OOB) for that tree
For each observation i: predict using trees where i was OOB
Get ≈ B/3 predictions per observation
Average these → OOB prediction
OOB error ≈ cross-validation error (when B is large)

Advantage: No need for separate cross-validation!

Random Forests: Decorrelating Trees

Problem with Bagging: Trees can be highly correlated

Random Forest Solution:

At each split, randomly select m predictors as split candidates (from p total)

Typically \(m \approx \sqrt{p}\) for classification
Typically \(m \approx p/3\) for regression
Special case: m = p → bagging

Why does this help?

Forces diversity among trees → reduces correlation → lower variance when averaging!

Random Forest Performance

Heart Disease Example:

Single tree: 25% error
Bagging (m = p): 22% error
Random Forest (m = √p): 19% error ✓

Gene Expression Example (15 classes, 500 predictors):

Single tree: 45.7% error
Bagging: 25% error
Random Forest: 22% error ✓

Random Forests consistently outperform bagging, especially with many correlated predictors!

Boosting: Learning from Mistakes

Key Difference: Trees grown sequentially, each fixing previous errors

Boosting Algorithm:

Initialize \(\hat{f}(x) = 0\) and \(r_i = y_i\) for all i
For b = 1, 2, …, B:
- Fit tree \(\hat{f}^b\) with d splits to data (X, r)
- Update: \(\hat{f}(x) \leftarrow \hat{f}(x) + \lambda \hat{f}^b(x)\)
- Update residuals: \(r_i \leftarrow r_i - \lambda \hat{f}^b(x_i)\)
Output: \(\hat{f}(x) = \sum_{b=1}^{B} \lambda \hat{f}^b(x)\)

Key parameters:

B = number of trees (use CV)
λ = shrinkage/learning rate (typically 0.01 or 0.001)
d = tree depth (interaction depth, often d = 1)

Boosting Intuition

Teacher-Student Analogy:

Student takes test (initial model)
Teacher identifies mistakes (residuals)
Student studies only mistakes (fit tree to residuals)
Student improves a little (add λ × tree)
Repeat with new mistakes

Result: Slow, steady learning → very accurate final model

Unlike bagging/RF: can overfit if B too large (but slowly)

Boosting Performance

Gene Expression Data (15 classes, 500 predictors):

Random Forest: 22% error
Boosting (depth=1): 8% error ✓
Boosting (depth=2): 10% error

California Housing Data:

Boosting with depth=6 achieves lowest test error among all methods

Boosting often wins in competitions and real applications!

Tuning Parameters Comparison

Method	Key Parameters	Typical Values
Single Tree	α (pruning)	Use CV
Bagging	B (# trees)	Large (≈ 500), doesn’t overfit
Random Forest	B (# trees) m (# predictors per split)	B ≈ 500 m = √p (classification) m = p/3 (regression)
Boosting	B (# trees) λ (learning rate) d (tree depth)	Use CV for B λ = 0.01 or 0.001 d = 1 to 6

Variable Importance

How to measure which predictors matter most?

For Bagging/Random Forest (Regression):

Record total RSS decrease from splits on predictor Xⱼ
Average across all B trees
Large value → important predictor

For Bagging/Random Forest (Classification):

Record total Gini index decrease from splits on predictor Xⱼ
Average across all B trees

For Boosting:

Similar, but weighted by number of times predictor is selected

Economic Applications

Common Uses in Economics:

Credit scoring: Default prediction using financial variables
Labor economics: Wage prediction, employment classification
Marketing: Customer segmentation, purchase prediction
Finance: Stock return prediction, risk assessment
Health economics: Disease diagnosis, treatment outcomes
Development economics: Poverty classification, policy targeting

Advantages for economists:

Handle non-linearities naturally
Automatic interaction detection
Robust to outliers
Variable importance measures

When to Use Each Method?

Single Decision Tree

Need interpretability ✓
Want to explain model to stakeholders ✓
Exploratory analysis ✓
Small datasets
Don’t care about maximum accuracy

Ensemble Methods

Maximum prediction accuracy needed ✓
Large datasets available ✓
Can sacrifice interpretability
Complex relationships expected ✓
Competition or production setting ✓

Specific Ensemble Choice:

Random Forest: Default choice, hard to beat
Boosting: Often wins, but requires more tuning
Bagging: Baseline comparison

Practical Implementation in R

# Single Tree
library(tree)
tree_model <- tree(y ~ ., data = train)
cv_tree <- cv.tree(tree_model)
pruned <- prune.tree(tree_model, best = 6)

# Random Forest
library(randomForest)
rf_model <- randomForest(y ~ ., data = train, 
                        mtry = sqrt(p), ntree = 500)

# Boosting
library(gbm)
boost_model <- gbm(y ~ ., data = train,
                  distribution = "gaussian",
                  n.trees = 5000, interaction.depth = 4,
                  shrinkage = 0.01)

Key Takeaways

Single trees: Simple, interpretable, but low accuracy
Ensemble methods dramatically improve performance:
- Bagging: Reduce variance by averaging
- Random Forest: Decorrelate trees for better averaging
- Boosting: Sequential learning from mistakes
Trade-off: Accuracy vs. Interpretability
Random Forest: Usually best “out-of-box” performance
Boosting: Often achieves highest accuracy with tuning
Economic applications: Powerful for prediction when relationships are complex

Summary Comparison

Aspect	Single Tree	Bagging	Random Forest	Boosting
Interpretability	★★★★★	★	★	★
Accuracy	★★	★★★★	★★★★★	★★★★★
Speed	★★★★★	★★★	★★★	★★
Tuning Required	★★	★	★★	★★★★
Overfitting Risk	★★★★	★	★	★★★

Questions?

Contact Information:

[Your email/office hours]

Additional Resources:

Course materials: [link]
R code examples: [link]
Practice datasets: [link]

Backup Slides: Technical Details

Additional mathematical details and proofs for interested students

Appendix: RSS Calculation

For regression trees, at each split we choose predictor j and cutpoint s to minimize:

\[\sum_{i: x_i \in R_1(j,s)} (y_i - \hat{y}_{R_1})^2 + \sum_{i: x_i \in R_2(j,s)} (y_i - \hat{y}_{R_2})^2\]

where:

\(R_1(j,s) = \{X | X_j < s\}\)
\(R_2(j,s) = \{X | X_j \geq s\}\)
\(\hat{y}_{R_1}\) and \(\hat{y}_{R_2}\) are means in each region

This is done for all possible j and s (greedy search)

Appendix: Why Bagging Works

Mathematical Intuition:

If we had multiple training sets, we could:

Build \(\hat{f}^1(x), \hat{f}^2(x), ..., \hat{f}^B(x)\) on each
Average: \(\hat{f}_{\text{avg}}(x) = \frac{1}{B}\sum_{b=1}^B \hat{f}^b(x)\)

This would have lower variance than any single \(\hat{f}^b(x)\)

Bootstrap approximation:

Since we have only one training set, create B bootstrap samples to simulate having B different training sets!

Appendix: Correlation in Bagging

Problem: If there’s a very strong predictor, most/all bagged trees will use it at the first split

→ All trees look similar → highly correlated → averaging doesn’t reduce variance much

Example: If correlation between trees = ρ, then variance of average:

\[\text{Var}(\bar{X}) = \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2\]

As B → ∞, first term remains → correlation limits improvement

Random Forest solution: Force decorrelation by limiting predictor choice at each split