Decision tree learning

Decision tree learning fits predictors by recursively partitioning input space. Leaves predict labels for classification or numerical values for regression; a regression tree is the numerical-response case.

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 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$.