Standard decision trees possess a fundamental geometric constraint that is often overlooked in introductory treatments: every split must be perpendicular to exactly one feature axis. This seemingly innocuous restriction has profound implications for the shapes of decision boundaries, the efficiency of representation, and the patterns that trees can—or cannot—easily capture.

When you train a CART, ID3, or C4.5 tree, you are implicitly constraining your model to partition the feature space using only horizontal and vertical lines (in 2D) or axis-aligned hyperplanes (in higher dimensions). This creates a world of rectangles, boxes, and rectangular hyperrectangles—never ellipses, diagonal lines, or curved boundaries.

To understand the axis-aligned constraint formally, we need to examine the structure of split tests that decision trees can represent.

The Standard Split Test:

At each internal node $t$ of a standard decision tree, the split test takes the form:

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

where:

• $x_j$ is a single feature (the $j$-th component of feature vector $x$)
• $\theta_t$ is a scalar threshold
• $\mathbb{1}[\cdot]$ is the indicator function

This test examines exactly one dimension and compares it to a constant. Geometrically, this defines a hyperplane perpendicular to axis $j$ at position $\theta_t$.

The Resulting Partition:

After $K$ splits, the tree partitions the feature space $\mathcal{X} \subseteq \mathbb{R}^d$ into regions $R_1, R_2, \ldots, R_M$ where each region is an axis-aligned hyperrectangle:

$$R_m = {x \in \mathbb{R}^d : \ell^{(m)}_j \leq x_j < u^{(m)}_j, ; j = 1, \ldots, d}$$

Here, $\ell^{(m)}_j$ and $u^{(m)}_j$ are the lower and upper bounds for feature $j$ in region $m$.

Why This Constraint?

The axis-aligned restriction emerges from the optimization problem solved at each node. To find the best split, CART maximizes impurity reduction:

$$\max_{j, \theta} \left[ \mathcal{I}(t) - \frac{n_L}{n_t}\mathcal{I}(t_L) - \frac{n_R}{n_t}\mathcal{I}(t_R) \right]$$

The search is over:

• Feature index $j \in {1, \ldots, d}$ (discrete choice)
• Threshold $\theta \in {x_{ij} : i \in I_t}$ (finite set of candidate thresholds)

This is computationally tractable: we sort samples by each feature and evaluate the impurity reduction at each midpoint, giving $O(d \cdot n \log n)$ complexity per node.

If we allowed arbitrary hyperplanes (oblique splits), the search would become:

$$\max_{w \in \mathbb{R}^d, \theta \in \mathbb{R}} \text{Impurity Reduction}(w^T x \leq \theta)$$

This is a continuous, non-convex optimization problem with $d + 1$ parameters per split—dramatically more expensive to solve.

The best way to understand the axis-aligned limitation is through geometric visualization. Let's examine several scenarios in 2D.

Scenario 1: Linearly Separable, Axis-Aligned

Consider two classes separated by a vertical line at $x_1 = 5$:

Class A: x₁ < 5      Class B: x₁ ≥ 5

  │ A A A │ B B B │
  │ A A A │ B B B │
  │ A A A │ B B B │
  ─────────┼───────→ x₁
           5

A decision tree captures this perfectly with a single split: if x₁ < 5 then Class A else Class B.

Scenario 2: Linearly Separable, Diagonal

Now consider two classes separated by the diagonal line $x_1 + x_2 = 10$:

           ╱
    B B B ╱ A A A
   B B B ╱ A A A A
  B B B ╱ A A A A A
 ─────╱────────────→ x₁
     ╱
    optimal: x₁ + x₂ = 10

The true boundary is a single line, but a decision tree must approximate it with a staircase of axis-aligned splits:

       ├─────┬─────┤
       │  B  │     │
  ┌────┼─────┤  A  │
  │ B  │     │     │
  ├────┤  A  ├─────┤
  │    │     │  A  │
  ─────┴─────┴─────→ x₁

Tree staircase approximation

This requires many splits to approximate a single diagonal line, and the approximation is never exact.

Scenario 3: The XOR Problem

The classic XOR pattern lies naturally along diagonals:

        ↑ x₂
        │
   B B  │  A A
   B B  │  A A
 ───────┼───────→ x₁
   A A  │  B B
   A A  │  B B
        │

Classes are separated by: $(x_1 - \bar{x}_1)(x_2 - \bar{x}_2) < 0$

The optimal boundaries are the diagonals, but axis-aligned trees must create a grid:

   ┌─────┬─────┐
   │  B  │  A  │
   ├─────┼─────┤
   │  A  │  B  │
   └─────┴─────┘

This requires at least 3 splits (one vertical, one horizontal in each branch), and the boundaries don't match the true diagonal structure.

Scenario 4: Circular Boundary

Consider a class defined by $x_1^2 + x_2^2 \leq r^2$ (inside a circle):

           ╭───────╮
          ╱         ╲
         │  Class A  │
          ╲         ╱
           ╰───────╯
     Class B everywhere else

An axis-aligned tree approximates this circle with a staircase polygon:

     ┌───────┐
   ┌─┤       ├─┐
   │ │ Class ├─│
   │ │   A   │ │
   ├─┤       ├─┤
     └───────┘

The approximation requires $O(1/\epsilon)$ splits to achieve error $\epsilon$ on the boundary.

To rigorously understand when axis-aligned trees struggle, we need to analyze their representation efficiency compared to other hypothesis classes.

VC Dimension Perspective:

The VC dimension measures the expressive power of a hypothesis class. For axis-aligned rectangles in $\mathbb{R}^d$:

$$\text{VCdim}(\text{Axis-aligned rectangles}) = 2d$$

For arbitrary (oblique) halfspaces in $\mathbb{R}^d$:

$$\text{VCdim}(\text{Halfspaces}) = d + 1$$

This suggests axis-aligned splits have limited VC dimension per split, but trees compensate by using many splits.

Approximation Theory for Oblique Boundaries:

Consider approximating a linear boundary $w^T x = \theta$ where $w$ is not axis-aligned. Let $\alpha$ be the angle between $w$ and the nearest axis.

Theorem (Axis-Aligned Approximation Complexity): To achieve an $\epsilon$-approximation of an oblique hyperplane at angle $\alpha$ to the nearest axis, within a bounded region of diameter $D$, an axis-aligned tree requires:

$$\Omega\left(\frac{D \cdot |\sin \alpha|}{\epsilon}\right)$$

splits.

Implication: When $\alpha = 45°$ (maximum angle), the number of splits is $\Omega(D / \epsilon)$. This is why diagonal boundaries are particularly expensive to represent.

The Representation Gap:

Define the representation gap as the ratio of hypothesis class complexity to decision boundary complexity:

$$\text{Gap}(f, H) = \frac{\min_{h \in H} \text{Complexity}(h) \text{ s.t. } h \approx f}{\text{Intrinsic Complexity}(f)}$$

For axis-aligned trees approximating oblique boundaries:

• Intrinsic complexity of a hyperplane: $O(d)$ parameters
• Tree complexity to approximate: $O(n^d)$ in the worst case for $n$ training points

This exponential gap in dimensionality is a fundamental limitation.

Universal Approximation:

Despite these limitations, decision trees are universal approximators: given enough splits, they can approximate any measurable function to arbitrary precision. This is because the set of axis-aligned rectangles is dense in the space of all measurable sets.

However, being a universal approximator says nothing about efficiency. Neural networks are also universal approximators, but some functions require exponentially many neurons.

The axis-alignment constraint has several practical consequences that practitioners should understand:

Consequence 1: Feature Engineering Sensitivity

Decision tree performance is highly sensitive to how features are represented. Consider these scenarios:

• Original features: $x_1, x_2$
• Rotated features: $z_1 = x_1 + x_2, z_2 = x_1 - x_2$

A diagonal boundary in $(x_1, x_2)$ space becomes axis-aligned in $(z_1, z_2)$ space! The same tree algorithm might need 1 split in the rotated space versus dozens in the original space.

This means: Feature engineering (including PCA, whitening, and domain-specific transformations) can dramatically affect decision tree performance.

Consequence 2: Inability to Model Feature Interactions Succinctly

When the decision boundary depends on combinations of features (interactions), axis-aligned trees face difficulties:

• A split on $x_1 \cdot x_2 > \theta$ cannot be represented directly
• Product features must be added explicitly or approximated with many splits
• Ratio features ($x_1 / x_2$) are similarly problematic

Consequence 3: Inefficiency in High Dimensions

In high-dimensional spaces, the axis-aligned constraint becomes increasingly limiting:

• Most of the decision boundary 'surface area' lies along oblique directions
• Random hyperplanes in high dimensions are almost never axis-aligned
• The staircase approximation error grows with dimensionality

This is one reason why single decision trees often struggle with high-dimensional data, even though they can theoretically represent any boundary.

We can empirically measure how much axis-alignment costs in terms of model complexity and accuracy. This analysis helps understand when the limitation is significant.

Metric 1: Model Complexity Ratio

Define the complexity ratio as:

$$\rho = \frac{\text{Number of leaves in axis-aligned tree}}{\text{Number of leaves in oblique tree for same accuracy}}$$

For synthetic problems with diagonal boundaries, $\rho$ can be 10x or higher.

Metric 2: Accuracy Gap at Fixed Complexity

Compare accuracy of axis-aligned vs. oblique trees with the same number of leaves:

$$\Delta = \text{Accuracy}{\text{oblique}} - \text{Accuracy}{\text{axis-aligned}}$$

Metric 3: Sample Complexity

The number of training samples required to achieve target accuracy $1 - \epsilon$:

$$n_{\text{axis}} \text{ vs } n_{\text{oblique}}$$

Due to the larger hypothesis space needed, axis-aligned trees often require more samples.

Interpreting the Results:

When running such comparisons, you'll typically observe:

1. Axis-aligned cases (0°, 90°): Tree needs 1-2 splits, matches linear classifier
2. Moderate angles (30°, 60°): Tree needs 5-15 splits, slight accuracy gap
3. Diagonal case (45°): Tree needs many splits, largest accuracy gap

This confirms the theoretical prediction that axis-aligned trees struggle most when boundaries are at 45° angles to the axes.

The Variance Component:

Beyond fixed accuracy, axis-aligned approximations of oblique boundaries increase variance:

• The staircase boundary is sensitive to the exact training samples
• Different samples produce different staircase patterns
• This contributes to the instability discussed in the previous page

An interesting perspective on axis-alignment comes from examining how ensemble methods partially mitigate this limitation.

Random Forests and Pseudo-Oblique Boundaries:

While individual trees in a Random Forest are axis-aligned, the ensemble can approximate oblique boundaries through averaging:

$$\hat{f}{\text{RF}}(x) = \frac{1}{B} \sum{b=1}^{B} \hat{f}^{(b)}(x)$$

Each tree creates a different staircase approximation, and averaging produces a smoother, more diagonal effective boundary.

Tree 1:          Tree 2:          Average:
  ┌──┬────┐      ┌────┬──┐       ╱        
  │B │ A  │      │ B  │A │      ╱ smooth 
  ├──┼────┤  +   ├────┼──┤  →  ╱ diagonal
  │B │ A  │      │ B  │A │    ╱  boundary
  └──┴────┘      └────┴──┘   ╱          

This is analogous to how anti-aliasing in computer graphics smooths jagged diagonal lines on a pixel grid.

Gradient Boosting and Additive Staircases:

Gradient boosting builds trees sequentially, with each tree correcting the residual errors of previous trees. For oblique boundaries:

1. First tree creates a coarse staircase approximation
2. Subsequent trees add corrections in the residual regions
3. The sum progressively refines the approximation

$$\hat{f}{\text{GB}}(x) = \sum{m=1}^{M} \gamma_m h_m(x)$$

With enough trees and appropriate learning rate, gradient boosting can closely approximate oblique boundaries, though it remains fundamentally axis-aligned in each tree.

Limit of Ensemble Approximation:

Even with ensembles, there are theoretical limits:

• Each tree contributes axis-aligned boundaries
• Averaging/summing creates piecewise constant approximations
• True smooth curves can only be approximated, never exactly represented
• Sample efficiency still favors methods that match the true boundary geometry

This motivates exploring methods that directly allow oblique splits, which we'll cover in the next page.

Understanding the axis-alignment constraint should influence when you choose decision trees and how you prepare your data.

Decision Framework:

Ask these questions to determine if axis-aligned splits are appropriate:

1. Are there natural threshold-based rules in your domain?

   • Yes: Axis-aligned trees are natural (e.g., medical diagnosis: temperature > 38°C)
   • No: Consider oblique methods or feature engineering

2. Have you examined the true decision boundary shape?

   • Plot 2D projections to understand boundary geometry
   • If boundaries are clearly diagonal, add interaction features

3. Do feature ratios or products have domain meaning?

   • BMI = weight/height², Debt-to-income = debt/income
   • Add these as explicit features before tree fitting

4. Is your data already rotated (e.g., by PCA)?

   • PCA axes are not necessarily axis-aligned with decision boundaries
   • Consider using original features or domain-specific transformations

We've comprehensively analyzed the axis-aligned split constraint—its mathematical basis, geometric implications, and practical consequences. Here are the key insights:

Looking Ahead:

The axis-alignment limitation naturally motivates more flexible tree variants. In the next page, we'll explore Oblique Trees—decision trees that allow splits of the form $w^T x \leq \theta$ where $w$ is an arbitrary weight vector. These trees can represent diagonal boundaries directly but introduce new challenges in optimization and interpretability.