From Split Paths to Cell Geometry

Introduction

A prediction from a decision tree is attached to a leaf, but the leaf is also a region of predictor space. Each split in the route to that leaf imposes one more constraint: an input must lie on one side of a threshold for a particular coordinate. Translating those successive decisions into intervals makes the geometry of a tree cell explicit.

This tutorial develops that translation for a finite axis-aligned tree on a rectangular predictor domain. The aim is to calculate the cell reached by a query and to understand how its coordinate widths and volume follow from the split locations. The resulting geometry is useful for describing a tree’s partition without confusing the numerical thresholds themselves with the lengths of the intervals they define.

For definiteness, take each threshold to be strictly inside the current interval on its split coordinate. The branch convention assigns a point exactly at the threshold to the left. Thus a left decision contributes an upper constraint \(x_j\le t\), while a right decision contributes a strict lower constraint \(x_j>t\). When describing widths and volumes, we can use the closure of the cell: changing whether a boundary is included does not change its interval lengths or its \(p\)-dimensional volume.

From Path Decisions to Coordinate Intervals

Fix a query point \(x=(x_1,\ldots,x_p)\) and follow its path. For coordinate \(j\), collect the thresholds at splits on that coordinate. A right-branch decision at threshold \(t\) places a lower bound at \(t\); a left-branch decision places an upper bound at \(t\). The strongest lower bound is the largest such threshold, and the strongest upper bound is the smallest. If the path never splits on coordinate \(j\), its interval remains the original \([a_j,b_j]\).

Here \(R_j\) and \(L_j\) denote the sets of thresholds for the indicated branch decisions, not sets of coordinates. The union with the original domain bound handles coordinates with no split of that type; for an empty threshold set, the maximum or minimum is therefore just the relevant domain endpoint.

Proof. Start at the root, where the coordinate interval on axis \(j\) is \([a_j,b_j]\). At a split on coordinate \(j\) with threshold \(t\), a left decision intersects the current interval with \((-\infty,t]\); this can only lower its upper endpoint to the smaller of its current upper endpoint and \(t\). A right decision intersects it with \((t,\infty)\); this can only raise its lower endpoint to the larger of its current lower endpoint and \(t\). A split on any other coordinate leaves this interval unchanged. Inducting over the ordered splits gives the stated maximum lower endpoint and minimum upper endpoint for every coordinate. Because each split constrains just one coordinate, all path constraints together are the product of these coordinate intervals, with the stated boundary convention. Taking the closure gives \(\prod_j[\ell_j,u_j]\); its widths are endpoint differences, and the volume of a rectangle is the product of its side lengths. \(\square\)

The path is followed by a query that satisfies all its decisions, so its coordinate intervals are nonempty. Under the interior-threshold condition, each resulting width is positive. The intervals can be open at a lower endpoint because of right-branch decisions; the closure is used in the theorem so that width and volume calculations do not depend on endpoint inclusion.

Widths and Volume Along the Path

The endpoint formula gives the final geometry. A second way to compute it is to update the rectangle after every split. If the current width on the split coordinate is \(w\), a left split at \(t\) replaces it by \(t-\ell\), where \(\ell\) is the current lower endpoint. A right split replaces it by \(u-t\), where \(u\) is the current upper endpoint. All other coordinate widths stay fixed. Each split therefore changes volume by a factor equal to the new width divided by the old width.

Proof. Before a split, the rectangle volume is the product of all its coordinate widths. The split changes exactly one width, from \(w_r^{\mathrm{old}}\) to \(w_r^{\mathrm{new}}\), leaving all others unchanged. Hence the new volume equals the old volume multiplied by \(w_r^{\mathrm{new}}/w_r^{\mathrm{old}}\). Applying this equality in sequence gives \(V_1=V_0(w_1^{\mathrm{new}}/w_1^{\mathrm{old}})\), then \(V_2=V_1(w_2^{\mathrm{new}}/w_2^{\mathrm{old}})\), and so on. Substituting each expression into the next yields the displayed product for the leaf volume. \(\square\)

These are ratios of current interval widths, not ratios of thresholds to one another. A threshold’s effect depends on the interval that has already been formed by earlier splits. Repeated splits on one coordinate can successively trim opposite ends of that interval.

Common Pitfall: Treating Thresholds as Widths

A threshold is a location in the current coordinate interval, not the amount by which the interval shrinks. For example, in the area calculation above, a split at \(x_2=3\) reduced a width of \(4\) to \(3\), while a later split at \(x_2=1\) reduced the then-current width of \(3\) to \(2\). Multiplying the thresholds, or subtracting each threshold from the original domain endpoint without accounting for earlier decisions, would give the wrong geometry.

The correction is to keep the current endpoints visible at every step. A left decision updates the upper endpoint to the smaller of its current value and the threshold; a right decision updates the lower endpoint to the larger of its current value and the threshold. Alternatively, collect all left and right constraints by coordinate and use their minimum upper threshold and maximum lower threshold. Both methods give the same cell.