Tree Limitations and Extensions

Having established that standard decision trees are fundamentally limited to axis-aligned splits, a natural question arises: What if we allowed trees to split on linear combinations of features?

This idea leads to oblique decision trees (also known as linear combination trees or multivariate trees)—a family of tree models that can create diagonal decision boundaries using splits of the form $w^T x \leq \theta$ rather than the simpler $x_j \leq \theta$.

Oblique trees address the representation inefficiency we identified earlier. A diagonal boundary that requires dozens of axis-aligned splits can be captured with a single oblique split. However, this power comes at a cost: optimization becomes significantly harder, and some of the interpretability that makes trees attractive is diminished.

Let's formalize what oblique splits mean mathematically and how they generalize axis-aligned splits.

Axis-Aligned Split (Review):

At node $t$, the standard split test is:

$$\phi_t(x) = \mathbb{1}[x_j \leq \theta_t]$$

This can be rewritten using a unit vector $e_j$ (with 1 at position $j$ and 0 elsewhere):

$$\phi_t(x) = \mathbb{1}[e_j^T x \leq \theta_t]$$

Oblique Split (Generalization):

An oblique split replaces the unit vector $e_j$ with an arbitrary weight vector $w \in \mathbb{R}^d$:

$$\phi_t(x) = \mathbb{1}[w^T x \leq \theta_t]$$

Geometrically, this defines a hyperplane with normal vector $w$ at signed distance $\theta_t / |w|$ from the origin. The hyperplane divides the feature space into two half-spaces.

The Expanded Parameter Space:

At each node, we now optimize over:

• Weight vector: $w \in \mathbb{R}^d$ (or a subset/manifold thereof)
• Threshold: $\theta \in \mathbb{R}$

This gives $d + 1$ continuous parameters per split, compared to 1 discrete + 1 continuous for axis-aligned splits.

The Optimization Problem:

To find the best oblique split, we solve:

$$\max_{w \in \mathbb{R}^d, \theta \in \mathbb{R}} \left[ \mathcal{I}(t) - \frac{n_L}{n_t}\mathcal{I}(t_L(w, \theta)) - \frac{n_R}{n_t}\mathcal{I}(t_R(w, \theta)) \right]$$

where $t_L(w, \theta)$ and $t_R(w, \theta)$ are the left and right child nodes after splitting with hyperplane $w^T x = \theta$.

Critical Challenge:

This optimization problem is non-convex and NP-hard in general. The impurity reduction is a discontinuous function of $(w, \theta)$ because small changes in the hyperplane can cause samples to jump from one side to the other. This is fundamentally different from axis-aligned splits where we can enumerate all $O(n)$ possible thresholds.

The primary motivation for oblique trees is their ability to capture diagonal decision boundaries efficiently. Let's examine the geometric improvements.

Example: XOR Pattern Revisited

Recall the XOR problem from the previous page. With axis-aligned splits:

  Axis-Aligned (requires 3+ splits):
  
       x₂
        │
   ┌────┼────┐
   │ B  │ A  │
   ├────┼────┤
   │ A  │ B  │
   └────┴────┘→ x₁

With oblique splits:

  Oblique (requires 2 splits):
  
        x₂
        │    ╱╲
        │   ╱A ╲
        │  ╱    ╲
        │ B╲    ╱B
        │   ╲  ╱
        │    ╲╱
        ─────────→ x₁
        
  Split 1: x₁ + x₂ ≤ 0  (diagonal /)
  Split 2: x₁ - x₂ ≤ 0  (diagonal \)

The oblique tree is shallower and uses fewer splits while perfectly capturing the true decision boundary.

Representation Efficiency Theorem:

Let $f^*$ be a target function with decision boundary consisting of $k$ hyperplanes. Then:

• An oblique tree needs at most $O(k)$ splits
• An axis-aligned tree may need $O(k \cdot n^{d-1})$ splits in the worst case

where $n$ is the number of training points and $d$ is the feature dimension.

Proof Sketch: Each oblique split directly represents one hyperplane. Axis-aligned trees must approximate each diagonal hyperplane with a staircase of up to $O(n^{d-1})$ axis-aligned hyperplanes (the number of grid cells the hyperplane passes through).

Diagonal Boundaries:

For a simple diagonal boundary $w^T x = \theta$ at angle $\alpha$ to the nearest axis:

Curved Boundaries:

For curved boundaries, oblique trees still offer some advantage because they can better approximate local tangent directions:

• Circle: Tangent lines at various angles, all representable with single oblique splits
• Axis-aligned approximation: Many horizontal/vertical segments

However, both approaches need $O(1/\epsilon)$ splits to achieve $\epsilon$-approximation of a curve; oblique trees just have a smaller constant factor.

Finding optimal oblique splits is computationally challenging. Several algorithms have been developed, each with different tradeoffs between solution quality and computational cost.

Algorithm 1: CART-LC (Linear Combinations)

Breiman's original CART allowed linear combinations as a special mode. The approach:

1. Backward elimination: Start with all features in the linear combination
2. Greedy removal: Iteratively remove the feature that least decreases impurity reduction
3. Threshold optimization: For each candidate weight vector, optimize θ

This is a heuristic that doesn't guarantee finding the optimal split but is computationally tractable.

Algorithm 2: OC1 (Oblique Classifier 1)

Murthy, Kasif, and Salzberg (1994) introduced a randomized search algorithm:

1. Initialize: Random weight vector $w$
2. Coordinate descent: Optimize one weight $w_j$ at a time while holding others fixed
3. Random restarts: Repeat from different initial points to escape local optima
4. Perturbation: Add random noise to escape plateaus

The key insight is that optimizing a single $w_j$ is tractable: we can sort data by the current hyperplane projection and enumerate threshold candidates.

Algorithm 3: Householder CART

An elegant theoretical approach uses Householder reflections:

1. Find the centroid of each class
2. Compute the vector between class centroids (Fisher direction)
3. Use this as the split direction $w$
4. Optimize threshold $\theta$ along this direction

This is essentially Linear Discriminant Analysis (LDA) at each node, giving a principled initialization.

Algorithm 4: SVM-Based Splits

Train a linear SVM on the data at each node:

$$\min_w |w|^2 + C \sum_i \xi_i$$ $$\text{s.t. } y_i(w^T x_i - \theta) \geq 1 - \xi_i$$

The SVM solution provides a maximum-margin hyperplane, which often yields good impurity reduction.

Algorithm 5: Gradient-Based Optimization

Modern approaches use smooth approximations to the impurity function:

$$\tilde{\mathcal{I}}(w, \theta) = \text{Soft impurity using sigmoid boundaries}$$

This allows gradient descent optimization:

$$w \leftarrow w - \eta \nabla_w \tilde{\mathcal{I}}$$

Neural oblique trees (discussed later) extend this idea with end-to-end differentiable training.

Oblique trees have distinct theoretical properties that differentiate them from axis-aligned trees.

VC Dimension:

For a single oblique split (hyperplane in $\mathbb{R}^d$):

$$\text{VCdim}(\text{Halfspace in } \mathbb{R}^d) = d + 1$$

For a depth-$k$ oblique tree with $k$ internal nodes:

$$\text{VCdim}(\text{Oblique tree}) = O(k \cdot d)$$

Compare to axis-aligned trees:

$$\text{VCdim}(\text{Axis-aligned tree, depth } k) = O(k \cdot \log d)$$

The larger VC dimension of oblique trees means:

• Greater expressive power
• More samples needed to achieve the same generalization guarantee
• Higher risk of overfitting on small datasets

Sample Complexity:

For PAC learning with oblique trees, the sample complexity scales as:

$$n = O\left(\frac{k \cdot d}{\epsilon} \log \frac{k \cdot d}{\delta}\right)$$

where $k$ is tree size, $\epsilon$ is target error, and $\delta$ is failure probability.

This linear dependence on $d$ (dimension) means oblique trees require more data in high dimensions, while axis-aligned trees have only logarithmic dependence.

Bias-Variance Tradeoff:

Comparative analysis of oblique vs. axis-aligned trees:

Regularization for Oblique Trees:

To control overfitting, oblique trees often require additional regularization:

1. Weight decay: $|w|_2^2$ penalty on split weights
2. Sparsity penalty: $|w|_1$ encourages axis-aligned-like sparsity
3. Feature selection: Limit number of non-zero weights per split
4. Margin constraints: Encourage large-margin splits like SVMs

The regularization path from oblique to axis-aligned:

$$\min_w \text{Impurity}(w) + \lambda |w|_1$$

As $\lambda \to \infty$, the solution becomes axis-aligned (only one non-zero weight).

Stability Analysis:

Interestingly, oblique trees can be more stable than axis-aligned trees for certain data distributions:

• When true boundaries are diagonal, small data changes don't flip the "winning" feature
• The continuous optimization smooths over discrete feature selection
• Margin-based splits (SVM-style) are robust to individual point perturbations

However, they can also be less stable when:

• The optimization finds different local optima from different initializations
• Weight vectors are poorly constrained (large magnitude fluctuations)
• Data doesn't have strong linear structure

Consistency:

Under mild regularity conditions, oblique trees are consistent:

$$\lim_{n \to \infty} R(\hat{f}_n) = R^*$$

where $R$ is the risk and $R^*$ is the Bayes error. This requires:

• Tree depth growing with sample size (typically $O(\log n)$)
• Appropriate regularization of weight magnitudes
• Node sizes bounded below

Several important oblique tree algorithms have been developed over the years. Let's examine the key approaches in detail.

CART-LC (Breiman et al., 1984)

The original CART algorithm included a linear combinations mode:

Training procedure:

1. At each node, consider both axis-aligned splits and linear combination splits
2. For linear combinations, use backward elimination:
   • Start with all features: $w = (w_1, \ldots, w_d)$
   • Remove one weight at a time, keeping the one that maintains best impurity reduction
   • Continue until no improvement from removing weights
3. Choose the better of axis-aligned or linear combination

Advantages:

• Simple extension of CART
• Can fall back to axis-aligned when appropriate

Disadvantages:

• Backward elimination is slow for large $d$
• May not find optimal weight combination

OC1 (Murthy et al., 1994)

Oblique Classifier 1 introduced randomized optimization for oblique splits:

HHCART: Householder CART (Wickramarachchi et al., 2016)

Uses Householder reflections for principled initialization:

1. Compute class centroids $\mu_1, \mu_2$
2. Normal direction: $v = \mu_1 - \mu_2$
3. Householder matrix: $H = I - 2\frac{vv^T}{|v|^2}$
4. Transform data: $Z = XH$
5. Find axis-aligned split in transformed space
6. Map back to original space (gives oblique split)

This is elegant because it uses the most discriminative direction (Fisher's LDA direction) without explicit optimization.

TAO: Tree Alternating Optimization (Carreira-Perpińan & Tavallali, 2018)

A modern approach that optimizes the entire tree jointly:

1. Initialize with a standard tree (CART)
2. Fix tree structure, optimize all node parameters jointly
3. Fix parameters, consider structural changes
4. Iterate until convergence

The parameter optimization step trains a linear classifier at each node:

$$\min_{{w_t, \theta_t}} \sum_{i=1}^n \mathcal{L}(y_i, \hat{f}(x_i; {w_t, \theta_t}))$$

This can be solved with gradient descent on a smooth approximation.

NODE: Neural Oblivious Decision Ensembles (Popov et al., 2019)

Fully differentiable oblique trees for deep learning:

• Soft routing: $\sigma(w^T x + \theta)$ instead of hard splits
• Gradient-based end-to-end training
• Ensemble averaging for robustness

We'll discuss neural trees in more detail in the connections section.

When should you use oblique trees, and what pitfalls should you avoid?

When Oblique Trees Excel:

1. Diagonal decision boundaries: When domain knowledge suggests linear combinations (e.g., BMI, financial ratios)

2. PCA-preprocessed data: If you've applied PCA or other rotation, boundaries may be diagonal in original space

3. Low to moderate dimensionality: The $O(d)$ parameters per split are manageable when $d < 100$

4. Sufficient training data: Need enough samples to estimate $d+1$ parameters reliably

5. When interpretability as linear rules is acceptable: "If 0.3×income + 0.7×credit_score > threshold" is still interpretable

When to Stick with Axis-Aligned:

1. Categorical features dominate: Oblique splits on categorical data are poorly defined

2. Natural threshold semantics: Age > 18, Temperature > 38°C have clear meaning

3. Very high dimensionality: With $d > 1000$, oblique optimization becomes unreliable

4. Limited data: Not enough samples to fit $d+1$ parameters well

5. Maximum interpretability required: Single-feature splits are easier to explain

One of the primary appeals of decision trees is interpretability. Oblique trees complicate this picture.

Axis-Aligned Interpretability:

A standard tree split is immediately understandable:

if age > 65:
    high_risk
else:
    check_other_factors

Stakeholders, domain experts, and regulators can evaluate the reasonableness of each rule.

Oblique Interpretability Challenges:

An oblique split is less intuitive:

if 0.3*age + 0.4*bmi + 0.2*blood_pressure - 0.1*exercise > 47.3:
    high_risk
else:
    check_other_factors

Questions arise:

• Why these specific weights?
• Is this combination clinically meaningful?
• How do I explain this to a patient?

Strategies for Interpretable Oblique Trees:

1. Weight sparsity: Penalize $|w|_1$ to encourage fewer non-zero weights per split

2. Weight discretization: Round weights to simple fractions (1/2, 1/3, etc.)

3. Semantic combinations: Constrain weights to match known meaningful combinations (BMI, ratios)

4. Post-hoc simplification: After training, replace complex oblique splits with simpler approximations

When Interpretability vs. Performance Clashes:

In many applications, you face a genuine tradeoff:

• High-stakes domains (medical, legal, financial): Interpretability often required by regulation or ethics. Prefer axis-aligned or sparse oblique.

• Competitive performance domains (Kaggle, internal optimization): Pure performance matters. Use whatever works, including dense oblique or ensembles.

• Scientific discovery: Oblique splits may reveal unexpected feature combinations, but need validation.

The Ensemble Escape Hatch:

Remember that ensembles of axis-aligned trees (Random Forests, XGBoost) can approximate oblique boundaries through averaging while each individual tree remains interpretable. This offers a middle ground:

• Individual trees are simple
• Ensemble captures complex boundaries
• Feature importances can be aggregated
• Individual predictions can be traced through representative trees

We've thoroughly examined oblique decision trees as a response to the axis-aligned limitation. Here are the key insights:

Looking Ahead:

Oblique trees represent one way to extend the basic tree framework. The next page explores Multivariate Splits—an even more general formulation that includes nonlinear splits, feature transformations within nodes, and the connection to neural networks. We'll see how the continuum from axis-aligned to oblique to fully multivariate reveals deep connections between decision trees and other machine learning paradigms.