11.1 Introduction to Decision Trees

Introduction

Decision trees are intuitive non-parametric supervised learning method used for classification and regression. They learn hierarchical sequence of rules to make predictions, creating tree structure where each internal node represents test on feature, each branch represents outcome, and each leaf represents class label or value. Their interpretability makes them valuable for understanding model decisions in LLM applications.

1. Tree Structure

Decision tree consists of:

• Root node: Top node, contains all training data
• Internal nodes: Test specific feature, split data
• Branches: Connect nodes, represent test outcomes
• Leaf nodes (terminal): Contain prediction (class or value)

Mathematical Representation

Tree T partitions feature space \(\mathcal{X}\) into disjoint regions \(R_1, R_2, ..., R_M\): $$\mathcal{X} = \bigcup_{m=1}^{M} R_m \quad \text{and} \quad R_i \cap R_j = \emptyset \text{ for } i \neq j$$

Prediction for input \(\mathbf{x} \in R_m\): $$f(\mathbf{x}) = c_m \quad \text{where } c_m \text{ is constant in region } R_m$$

2. Classification Trees

For classification, each leaf contains class label. Prediction is majority class in leaf's training samples.

Example: Email Spam Detection

    Root: Contains word "lottery"?
      ├─ Yes → From known sender?
      │   ├─ Yes → Not Spam
      │   └─ No → Spam
      └─ No → Contains excessive caps?
          ├─ Yes → Spam
          └─ No → Not Spam
    

Probability Estimates

For leaf node m with \(n_m\) samples: $$P(y = k | \mathbf{x} \in R_m) = \frac{1}{n_m} \sum_{x_i \in R_m} \mathbb{1}[y_i = k]$$

3. Regression Trees

For regression, each leaf contains numeric prediction (typically mean of training samples in leaf).

Prediction

For leaf m containing samples with labels \(y_{i_1}, ..., y_{i_{n_m}}\): $$\hat{y} = \bar{y}_m = \frac{1}{n_m}\sum_{j=1}^{n_m} y_{i_j}$$

Example: House Price Prediction

    Root: Square footage > 2000?
      ├─ Yes → Number of bedrooms > 3?
      │   ├─ Yes → Predict: $500,000
      │   └─ No → Predict: $400,000
      └─ No → Age of house > 20 years?
          ├─ Yes → Predict: $250,000
          └─ No → Predict: $300,000
    

4. Splitting Criteria

Key question: Which feature and threshold to use for split?

Goal

Find split that maximally separates classes (classification) or reduces variance (regression).

Greedy Approach

At each node, choose split that gives best immediate improvement. Find feature j and threshold t that solve: $$\min_{j,t} \left[ \text{cost}(R_{\text{left}}(j,t)) + \text{cost}(R_{\text{right}}(j,t)) \right]$$

5. Interpretability

Major advantage of decision trees: easy to interpret and explain.

Rule Extraction

Each path from root to leaf represents IF-THEN rule:

    IF (feature1 > threshold1) AND (feature2 ≤ threshold2) 
    THEN predict class_A
    

Feature Importance

Measure importance of feature j: $$\text{Importance}(j) = \sum_{\text{nodes using } j} \Delta \text{impurity}$$

where Δimpurity is reduction in impurity from split.

6. Advantages

• Interpretability: Easy to visualize and explain
• No feature scaling: Works with features on different scales
• Handles mixed data: Categorical and numerical features
• Non-linear patterns: Captures complex decision boundaries
• Feature interactions: Automatically considers feature combinations
• Missing values: Can handle missing data with surrogate splits
• Fast prediction: O(log n) for balanced tree

7. Disadvantages

• Overfitting: Can create overly complex trees
• Instability: Small data changes → very different tree
• Greedy algorithm: May not find global optimum
• Biased toward features with many values: More split points available
• Axis-aligned splits: Cannot represent diagonal boundaries efficiently
• Poor with linear relationships: Many splits needed for simple linear pattern

8. Decision Boundaries

Decision trees create axis-aligned (rectangular) decision boundaries.

Comparison with Other Methods

Method	Boundary Type	Interpretability	Handles Non-linearity
Logistic Regression	Linear	High	No (without feature engineering)
Decision Tree	Axis-aligned	Very High	Yes
SVM (RBF kernel)	Non-linear	Low	Yes
Neural Network	Non-linear	Very Low	Yes

9. Ensemble Methods Preview

Single decision trees are weak learners, but combining multiple trees creates powerful models:

• Random Forests: Average predictions from many trees trained on bootstrap samples
• Gradient Boosting: Sequentially train trees to correct errors of previous trees
• XGBoost, LightGBM: Optimized gradient boosting implementations

These ensemble methods often achieve state-of-the-art performance on tabular data.

10. Application to LLMs

While transformers dominate language modeling, decision trees relevant for:

• Prompt engineering: Decision trees for routing prompts to appropriate models
• Output classification: Classify LLM responses (safe/unsafe, relevant/irrelevant)
• Feature extraction: Extract interpretable features from embeddings
• Knowledge distillation: Distill complex LLM into interpretable tree rules
• Debugging: Understand when/why LLM makes certain decisions
• Hybrid systems: Decision trees route to specialized LLMs or retrieval systems

Key Takeaways

• Decision trees learn hierarchical rules through recursive splitting
• Classification trees predict class labels, regression trees predict numeric values
• Greedy algorithm finds locally optimal splits at each node
• Highly interpretable - can extract IF-THEN rules
• Create axis-aligned decision boundaries
• Prone to overfitting without regularization (depth limits, pruning)
• Unstable - small data changes can produce very different trees
• Excel in ensemble methods (Random Forests, Gradient Boosting)
• Useful for LLM applications requiring interpretability