AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Greedy axis-aligned CART growth on a finite sample

Definition

The inputs are observations $(x_{i}, y_{i})_{i = 1}^{n}$ with $n \geq 1$ and $x_{i} \in R^{p}$ for an integer $p \geq 1$ , a response mode (regression with $y_{i} \in R$ or classification with labels in a fixed finite ordered class set), a fixed classification impurity criterion when in classification mode, and a finite integer maximum depth $d_{\max} \geq 0$ . The root has sample set ${1, \dots, n}$ and depth $0$ . At a current leaf with nonempty sample set $I$ and depth $d < d_{\max}$ , perform the following procedure.

For each coordinate $j \in {1, \dots, p}$ , sort the distinct observed values in that coordinate as $u_{1} < \dots < u_{r}$ . For each $k = 1, \dots, r - 1$ , form the candidate threshold $t = (u_{k} + u_{k + 1}) / 2$ and its child sets $I_{L} = {i \in I : x_{i j} \leq t}$ and $I_{R} = {i \in I : x_{i j} > t}$ . These are the finite candidates at the node; if no coordinate has at least two distinct values, the candidate set is empty.
For each candidate, compute its child score. In regression the score is $\sum_{i \in I_{L}} (y_{i} - {\overset{ˉ}{y}}_{I_{L}})^{2} + \sum_{i \in I_{R}} (y_{i} - {\overset{ˉ}{y}}_{I_{R}})^{2}$ . In classification it is $∣ I_{L} ∣ Q_{I_{L}} + ∣ I_{R} ∣ Q_{I_{R}}$ for the fixed chosen impurity criterion. Select the candidate with the smallest score; when scores tie, select the least pair $(j, k)$ by comparing coordinate first and cut index second.
Store the selected coordinate and threshold at the current node, create its left and right children, and apply this procedure to the left child and then the right child at depth $d + 1$ . If $d = d_{\max}$ or the candidate set is empty, leave the current node as a leaf.

The output is the finite tree whose leaves use the regression means or classification majority labels from the empirical decision-tree definition. No strictly positive loss reduction is required for a split below the depth cap, and the returned tree is not asserted to be globally optimal among all trees.

Definition references

Empirical tree structure, leaf means, and classification impurities

Least-squares optimality of the regression leaf mean

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2–9.2.3, printed pp. 307–310

MIT OpenCourseWare, 15.097, Lecture 8: Decision trees, slides 14–16

Depends on

Used by

Bagged random-forest construction on a fixed finite sample Algorithm
Exact-line-search gradient tree boosting on a finite sample Algorithm
A one-dimensional regression threshold tree Example
A one-leaf fit can project a nonzero gradient to zero Example
Greedy CART minimizes the listed split loss and terminates Theorem

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §9.2.2–9.2.3 (standard reference, not scraped)
MIT OpenCourseWare, 15.097, Lecture 8: Decision trees, slides 14–16 (standard reference, not scraped)