DefinitionDefinition: 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.

Empirical axis-aligned binary decision trees

Definition

Fix a finite labeled sample $(x_{i}, y_{i})_{i = 1}^{n}$ with $n \geq 1$ , $x_{i} \in R^{p}$ and $p \geq 1$ . In regression, $y_{i} \in R$ . In classification, the labels lie in a fixed ordered finite set $C = {c_{1} < \dots < c_{K}}$ with $K \geq 1$ . A finite empirical axis-aligned binary decision tree has root sample-index set $I_{r o o t} = {1, \dots, n}$ . Each internal node $v$ stores a coordinate $j \in {1, \dots, p}$ and threshold $t \in R$ ; its left and right child sample sets are $I_{v}^{L} = {i \in I_{v} : x_{i j} \leq t}$ and $I_{v}^{R} = {i \in I_{v} : x_{i j} > t}$ , and both are required to be nonempty. A leaf is a terminal node. The leaf sample sets partition ${1, \dots, n}$ , and each node's feature region is the intersection of its path inequalities. Every input feature vector follows the unique path determined by the stored comparisons.

For a regression leaf with sample set $I$ , put $N_{I} = ∣ I ∣$ , ${\overset{ˉ}{y}}_{I} = N_{I}^{- 1} \sum_{i \in I} y_{i}$ , and $Q_{I} = N_{I}^{- 1} \sum_{i \in I} (y_{i} - {\overset{ˉ}{y}}_{I})^{2}$ ; its prediction is ${\overset{ˉ}{y}}_{I}$ and its total squared-error loss is $N_{I} Q_{I}$ . For a classification leaf, put $p_{I k} = N_{I}^{- 1} ∣ {i \in I : y_{i} = c_{k}} ∣$ and predict the class $c_{k}$ with largest $p_{I k}$ , choosing the least index in a tie. Its optional impurities are misclassification $Q_{I}^{m i s} = 1 - \max_{k} p_{I k}$ , Gini $Q_{I}^{G i n i} = 1 - \sum_{k = 1}^{K} p_{I k}^{2}$ , and entropy $Q_{I}^{e n t} = - \sum_{k = 1}^{K} p_{I k} \log p_{I k}$ , where $\log$ is the natural logarithm and $0 \log 0 = 0$ . A chosen classification criterion determines $Q_{I}$ and the corresponding total leaf impurity is $N_{I} Q_{I}$ .

Definition references

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

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

Used by

Bagged random-forest construction on a fixed finite sample Algorithm
Exact-line-search gradient tree boosting on a finite sample Algorithm
Greedy axis-aligned CART growth on a finite sample Algorithm
Weakest-link pruning of a finite tree Algorithm
Cost-complexity criteria for subtrees Definition
A one-dimensional regression threshold tree Example
A one-leaf fit can project a nonzero gradient to zero Example
An out-of-bag prediction can differ from the full finite forest Example
Two fitted subtrees with different leaf penalties Example
Gradient tree boosting does not increase empirical loss Theorem
Greedy CART minimizes the listed split loss and terminates Theorem
The sample mean uniquely minimizes squared error on a nonempty leaf Theorem
Weakest-link pruning terminates at the root Theorem

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

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