## Overview {.smaller}

**Tree-based methods** for regression and classification involve:

::: {.incremental}
- **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
:::

::: {.fragment}
**Key Methods:**

- Single Decision Trees
- Bagging (Bootstrap Aggregating)
- Random Forests
- Boosting
:::

---

## Why Tree-Based Methods?

::: {.columns}
::: {.column width="50%"}
**Advantages** ✓

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

::: {.column width="50%"}
**Disadvantages** ✗

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

::: {.fragment}
**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
```

::: {.fragment}
**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):

1. Start with all observations in one region
2. For each predictor Xⱼ and cutpoint s, split into:
   - {X | Xⱼ < s}
   - {X | Xⱼ ≥ s}
3. Choose split that **minimizes RSS** (regression) or maximizes **purity** (classification)
4. Repeat for each resulting region
5. 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ⱼ

::: {.fragment}
**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:

::: {.incremental}
1. **Classification Error Rate:**
   $$E = 1 - \max_k(\hat{p}_{mk})$$

2. **Gini Index** (preferred for growing trees):
   $$G = \sum_{k=1}^{K} \hat{p}_{mk}(1 - \hat{p}_{mk})$$

3. **Cross-Entropy/Deviance:**
   $$D = -\sum_{k=1}^{K} \hat{p}_{mk} \log \hat{p}_{mk}$$
:::

::: {.fragment}
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|$$

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

---

## Complete Tree Algorithm

1. **Grow large tree** T₀ using recursive binary splitting
2. **Apply cost complexity pruning** to get sequence of subtrees for each α
3. **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
4. **Choose α** that minimizes cross-validation error
5. **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.

::: {.fragment}
**Result:** Cross-validation selects tree with **6 terminal nodes**

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

---

## Trees vs Linear Models

::: {.columns}
::: {.column width="50%"}
**Linear Boundary**
```
     |
  ●  |  ○
 ●●  | ○○
●●●●●|○○○○
─────+─────
```
Works well when true boundary is linear
:::

::: {.column width="50%"}
**Non-linear Boundary**
```
  ○○○|●●●
  ○○ | ●●
 ○○──┼──●
  ●  |  ○
```
Trees excel when relationships are complex/non-linear
:::
:::

::: {.fragment}
**Rule of thumb:** Try both approaches! Trees are better for highly non-linear relationships
:::

---

## Bagging: Bootstrap Aggregating {.smaller}

**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:**

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

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

::: {.fragment}
**For classification:** Use **majority vote** across B trees
:::

---

## Out-of-Bag (OOB) Error Estimation

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

::: {.incremental}
- 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)
:::

::: {.fragment}
**Advantage:** No need for separate cross-validation!
:::

---

## Random Forests: Decorrelating Trees

**Problem with Bagging:** Trees can be highly correlated

::: {.fragment}
**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
:::

::: {.fragment}
**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** ✓

::: {.fragment}
Random Forests consistently outperform bagging, especially with many correlated predictors!
:::

---

## Boosting: Learning from Mistakes {.smaller}

**Key Difference:** Trees grown **sequentially**, each fixing previous errors

**Boosting Algorithm:**

1. Initialize $\hat{f}(x) = 0$ and $r_i = y_i$ for all i
2. 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)$
3. Output: $\hat{f}(x) = \sum_{b=1}^{B} \lambda \hat{f}^b(x)$

::: {.fragment}
**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:**

1. Student takes test (initial model)
2. Teacher identifies mistakes (residuals)
3. Student studies **only mistakes** (fit tree to residuals)
4. Student improves a little (add λ × tree)
5. Repeat with new mistakes

::: {.fragment}
**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

::: {.fragment}
**Boosting often wins** in competitions and real applications!
:::

---

## Tuning Parameters Comparison {.smaller}

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

---

## Variable Importance

**How to measure which predictors matter most?**

::: {.incremental}
**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:**

::: {.incremental}
- **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
:::

::: {.fragment}
**Advantages for economists:**

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

---

## When to Use Each Method? {.smaller}

::: {.columns}
::: {.column width="50%"}
**Single Decision Tree**

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

::: {.column width="50%"}
**Ensemble Methods**

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

::: {.fragment}
**Specific Ensemble Choice:**

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

---

## Practical Implementation in R
```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

::: {.incremental}
1. **Single trees:** Simple, interpretable, but low accuracy

2. **Ensemble methods** dramatically improve performance:
   - Bagging: Reduce variance by averaging
   - Random Forest: Decorrelate trees for better averaging
   - Boosting: Sequential learning from mistakes

3. **Trade-off:** Accuracy vs. Interpretability

4. **Random Forest:** Usually best "out-of-box" performance

5. **Boosting:** Often achieves highest accuracy with tuning

6. **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** | ★★★★ | ★ | ★ | ★★★ |

---

## Further Reading

**Key Resources:**

- James, Witten, Hastie, Tibshirani (2013). *An Introduction to Statistical Learning* (Chapter 8)

- Hastie, Tibshirani, Friedman (2009). *The Elements of Statistical Learning* (Chapters 9, 10, 15)

- Breiman (2001). "Random Forests" *Machine Learning*

- Friedman (2001). "Greedy Function Approximation: A Gradient Boosting Machine" *Annals of Statistics*

**R Packages:** `tree`, `rpart`, `randomForest`, `gbm`, `xgboost`

---

## 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:

1. Build $\hat{f}^1(x), \hat{f}^2(x), ..., \hat{f}^B(x)$ on each
2. 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