Recursive Partitions and Piecewise-Constant Predictors

From Covariate Space to Terminal Cells

A regression predictor can be built by dividing the covariate space into regions and assigning one prediction to each region. The division is recursive: begin with the entire space, split one current region into two, and continue splitting selected regions. The regions left unsplit at the end are called terminal cells. A predictor that takes one constant value throughout each terminal cell is called a piecewise-constant predictor.

We use $X$ for a covariate vector taking values in a Borel set $\mathcal X\subseteq\mathbb R^d$, and $x=(x_1,\ldots,x_d)$ for a particular covariate value. A standard tree split chooses a coordinate $j\in\{1,\ldots,d\}$ and a threshold $t\in\mathbb R$. The convention here sends equality to the left child: the two parts are defined by $x_j\le t$ and $x_j>t$.

Definition: A finite recursive binary partition of $\mathcal X$ starts with the root region $\mathcal X$. At each split, a current region $C$ is replaced by its two child regions $C\cap\{x\in\mathcal X:x_j\le t\}$ and $C\cap\{x\in\mathcal X:x_j>t\}$, for a chosen coordinate $j$ and threshold $t$. We require both children to be nonempty. The regions that are not split further are the terminal cells. They form the terminal partition.

The threshold convention makes the two children disjoint and assigns every point in the parent region to exactly one child. The partition is recursive because a later split acts only on one of the regions already produced, not on the whole covariate space. The number of splits is finite, so there are finitely many terminal cells.

What Shape Does a Cell Have?

Each split imposes a coordinate constraint on the points in the child region. Along the path from the root to a particular terminal cell, the constraints accumulate: the cell is the intersection of $\mathcal X$ with all the half-spaces specified by that path. In one dimension, these constraints amount to interval bounds, but the cell must still be intersected with the original covariate space.

Result: Every terminal cell is the intersection of $\mathcal X$ with a region described by the coordinate-threshold constraints on its path from the root. In one dimension, it is therefore the intersection of $\mathcal X$ with an interval (possibly with an endpoint included or excluded). It is an interval in $\mathbb R$ when $\mathcal X$ itself is an interval, but need not be an interval when $\mathcal X$ is an arbitrary subset of $\mathbb R$.

To verify the result, start at the root, whose region is $\mathcal X$, with no accumulated constraints. Each split intersects the current region with one of the two threshold half-spaces. Thus moving to either child adds exactly that child’s constraint. Repeating this step along the finite path gives $\mathcal X$ intersected with all path constraints. In one dimension, each constraint is an upper or lower bound, so their intersection in $\mathbb R$ is an interval, a singleton, or the empty set; because the terminal cell is nonempty, it is an interval or singleton. Intersecting it with $\mathcal X$ gives the stated form. $\square$

Worked Example: Three Cells on an Interval

Let $\mathcal X=[0,10]$. First split at $t=6$, sending $x\le6$ left and $x>6$ right. Then split the left region at $t=2$. The first split produces $[0,6]$ and $(6,10]$. The second split replaces $[0,6]$ by $[0,2]$ and $(2,6]$. Therefore the terminal cells are $[0,2]$, $(2,6]$, and $(6,10]$.

The endpoint convention can be checked directly: $2$ belongs to the first cell, $6$ belongs to the second cell, and every point greater than $6$ belongs to the third. For example, $x=1$ follows the left child twice, $x=4$ follows the left child and then the right child, and $x=9$ follows the right child at the root.

Worked Example: A Discrete Covariate Space

Take $\mathcal X=\{0,2,4\}\subset\mathbb R$ and split at $t=2$. The left cell is $\mathcal X\cap(-\infty,2]=\{0,2\}$; the right cell is $\mathcal X\cap(2,\infty)=\{4\}$. These cells are disjoint and cover $\mathcal X$, but the left cell $\{0,2\}$ is not an interval in $\mathbb R$: for instance, it does not contain $1$, which lies between its two points. The correct geometric description is that the cell is the intersection of the covariate space with an interval or half-space, not necessarily an interval in the ambient real line.

In $d$ dimensions, the same reasoning applies coordinate by coordinate. A cell is the original $\mathcal X$ intersected with the constraints encountered along its path. For a rectangular covariate space and coordinate-threshold splits, these regions are axis-aligned rectangles, with endpoint inclusion determined by the split convention. For an arbitrary $\mathcal X$, they are intersections of that set with such regions.

Why the Terminal Cells Form a Partition

A terminal partition must cover the covariate space without assigning any point to two different terminal cells. This follows directly from the split rule; it does not depend on $\mathcal X$ being a rectangle or even connected.

Theorem: The terminal cells of a finite recursive binary partition are pairwise disjoint and their union is $\mathcal X$.

Proof. Initially, the only current region is the root $\mathcal X$, so the current regions are disjoint and their union is $\mathcal X$. Suppose this property holds before a split. The split replaces one region $C$ by $C_L=C\cap\{x_j\le t\}$ and $C_R=C\cap\{x_j>t\}$. The two children are disjoint because no real number is both at most $t$ and greater than $t$. Their union is $C$, since every point in $C$ satisfies exactly one of those two inequalities. All other current regions are unchanged and disjoint from $C$. Thus the new collection remains disjoint and has the same union, $\mathcal X$. By induction, this holds after every split. At termination, the current regions are precisely the terminal cells, proving the claim. $\square$

Leafwise-Constant Regression Predictors

Once the cells are specified, assign a real number $c_\ell$ to each terminal cell $A_\ell$, where $\ell\in\{1,\ldots,L\}$ indexes the cells. The resulting predictor returns $c_\ell$ whenever its input lies in $A_\ell$. The constants may be chosen in different ways in different applications; the definition of the predictor itself only requires one constant per cell.

Definition: Given terminal cells $A_1,\ldots,A_L$ and constants $c_1,\ldots,c_L\in\mathbb R$, the leafwise-constant regression predictor is the function $g:\mathcal X\to\mathbb R$ defined by $g(x)=c_\ell$ when $x\in A_\ell$. Equivalently, $$ g(x)=\sum_{\ell=1}^{L}c_\ell\,\mathbf 1\{x\in A_\ell\}, $$ where $\mathbf 1\{x\in A_\ell\}$ is $1$ if $x\in A_\ell$ and $0$ otherwise.

The indicator representation works because each covariate value belongs to exactly one terminal cell: one term contributes its constant, and all the other terms contribute zero. This gives a useful equivalent description of the class of predictors associated with a fixed partition.

Result: A function on $\mathcal X$ is constant on every terminal cell if and only if it can be written as a sum of the form $\sum_{\ell=1}^L c_\ell\mathbf 1\{x\in A_\ell\}$ for constants $c_1,\ldots,c_L$.

Proof. First suppose the function has that sum representation. For any $x\in A_k$, disjointness gives $\mathbf 1\{x\in A_k\}=1$ and $\mathbf 1\{x\in A_\ell\}=0$ for every $\ell\ne k$, so the function equals $c_k$ throughout $A_k$. It is therefore constant on each cell. Conversely, suppose the function is constant on each cell. For every $\ell$, let $c_\ell$ be its value on $A_\ell$, which is well-defined because the function is constant there and the cell is nonempty. Since the cells cover $\mathcal X$ and are disjoint, each $x$ belongs to exactly one $A_k$; the sum is then $c_k$, the function’s value at $x$. This proves the representation. $\square$

The cells produced by threshold splits are Borel sets when $\mathcal X$ is Borel: each is formed by intersecting $\mathcal X$ with finitely many coordinate half-spaces, which are Borel. Consequently, the indicator representation also shows that $g$ is a measurable function. This matters because measurable predictors can be evaluated as random variables when applied to a random covariate $X$.

Worked Example: A Two-Dimensional Partition

Let $\mathcal X=[0,4]\times[0,3]$. Split the root at $x_1=2$. Then split the right child at $x_2=1$. The terminal cells are $A_1=\{x\in\mathcal X:x_1\le2\}$, $A_2=\{x\in\mathcal X:x_1>2,\ x_2\le1\}$, and $A_3=\{x\in\mathcal X:x_1>2,\ x_2>1\}$. The first cell is the left half of the rectangle; the other two divide its right half horizontally.

Assign constants $c_1=3$, $c_2=7$, and $c_3=5$. For $x=(1.5,2)$, the first coordinate is at most $2$, so $x\in A_1$ and $g(x)=3$. For $x=(3,0.5)$, $x_1>2$ and $x_2\le1$, so $x\in A_2$ and $g(x)=7$. For $x=(3,2)$, both $x_1>2$ and $x_2>1$, so $x\in A_3$ and $g(x)=5$. Each evaluation follows the successive split decisions from the root.

Worked Example: Assigning Constants to Terminal Cells

Let $\mathcal X=\{0,2,4,6,8,10\}$. Split first at $x=5$, then split the left child at $x=1$. The terminal cells are $A_1=\{0\}$, $A_2=\{2,4\}$, and $A_3=\{6,8,10\}$. Suppose the observed responses attached to these covariate values are respectively $1,3,5,4,6,8$.

For an explicit piecewise-constant predictor, take the arithmetic mean of the listed responses in each cell. In $A_1$, the only response is $1$, so $c_1=1$. In $A_2$, the responses are $3$ and $5$, so $c_2=(3+5)/2=4$. In $A_3$, they are $4,6,8$, so $c_3=(4+6+8)/3=18/3=6$. Thus $g(x)=1$ on $A_1$, $g(x)=4$ on $A_2$, and $g(x)=6$ on $A_3$. In particular, $g(4)=4$ and $g(8)=6$.

This calculation illustrates how cell-specific constants define a predictor; it does not require that every piecewise-constant predictor be constructed from response averages.

Common Mistakes and Why the Construction Matters

A recursive partition separates the bookkeeping of where a prediction applies from the choice of what value to predict there. The same collection of cells can support different constants, and the same constants can yield different predictors when attached to different partitions. The partition is therefore part of the model, not merely a way of displaying its predictions.

Assuming every one-dimensional cell is an interval in $\mathbb R$. A threshold constraint produces an interval-like region before intersecting with $\mathcal X$. If $\mathcal X$ is disconnected or discrete, the resulting cell need not contain every real number between its points.
Forgetting how equality is assigned. With the convention $x_j\le t$ versus $x_j>t$, a point exactly at the threshold goes left. A different convention is possible, but the two children must still be defined to be disjoint and exhaustive.
Evaluating a point using only the final threshold. Each split applies within its parent region. To locate a point, follow the path from the root; a later threshold does not act on points outside the region it splits.
Thinking a cellwise-constant predictor must use a particular formula for its constants. The predictor is defined by its cells and constants. How those constants are selected is a separate modeling or estimation choice.

The essential structure is finite and explicit: threshold decisions determine terminal cells, the cells partition the covariate space, and one constant per cell determines the predictor. This structure makes the prediction at any input value well-defined, including points lying exactly on a split threshold.

Check Your Understanding

Use the threshold convention that equality goes to the child defined by $x_j\le t$.

For $\mathcal X=[-2,8]$, split at $x=3$, then split the left child at $x=-1$. What are the terminal cells?
For $\mathcal X=\{0,2,4\}$, what is the left cell under a split at $t=2$, and why need it not be an interval in $\mathbb R$?
In two dimensions, a root split is $x_1\le1$, and its right child is split at $x_2=0$. Which terminal cell contains $(2,-1)$?
Explain why the terminal cells are pairwise disjoint and cover $\mathcal X$, regardless of the dimension.
Given constants $c_1,\ldots,c_L$, why does the indicator formula return exactly one of those constants at each $x\in\mathcal X$?