Regression tree

A regression tree is the numerical-response case of decision tree learning. A regression tree recursively partitions predictor space by axis-aligned splits. At each leaf, candidate coordinates and thresholds are compared by the residual sum of squares after replacing that leaf by its two children; the selected split minimizes the total criterion. The fitted value in each terminal region is the sample mean there.

A decision stump is a decision tree with one split. A regression stump predicts a constant, usually the sample mean, in each of its two terminal regions.

For stumps $h(x)=\mathrm{sign}(x_i-b)$ of fixed polarity, sort observations along each coordinate and sweep the threshold across whole groups of equal values. Passing a group adds its positive-label weight and subtracts its negative-label weight from the weighted misclassification risk. Include thresholds below and above all observed values. Every distinct sample prediction pattern is considered, giving exact minimization in $O(nm\log m)$ time complexity for $m$ observations in ${\mathbb{R}}^n$. Coordinate sort orders can be reused across AdaBoost rounds, reducing subsequent weighted scans to $O(nm)$.

For a deterministic partition $R_1,\dots ,R_J$ andconditional independence givesIf the conditional response variance is at most ${\sigma }^2$, the prediction variance at an independent test point is at most ${\sigma }^{2}J/n$.