Pipeline-generated

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.

✓ 2 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 2 also cleared it.

CART trees and pruning — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Two fitted subtrees with different leaf penalties

Example

Take one predictor and the sample $(x_{i}, y_{i}) = (0, 0), (1, 0), (2, 1)$ in regression. Let $T_{1}$ split at $x_{1} \leq 1.5$ , and let $T_{2}$ add a split at $x_{1} \leq 0.5$ inside $T_{1}$ 's left branch. Thus $T_{1}$ has leaves with feature values ${0, 1}$ and ${2}$ , with predictions $0$ and $1$ ; $T_{2}$ has leaves ${0}$ , ${1}$ , and ${2}$ , with predictions $0$ , $0$ , and $1$ . Both trees have training residual sum of squares $0$ , but they have $2$ and $3$ leaves respectively. With penalty $α = 1$ per leaf, their costs (training residual sum of squares plus $α$ times the number of leaves) are $2$ and $3$ . For a nonterminal node $t$ , define $g (t)$ as its loss after collapse minus its current descendant-leaf loss, divided by the number of descendant leaves removed. In $T_{2}$ , the left branch has $g = 0$ , while the root has $g = 1 / 3$ , so the first weakest-link collapse is the left branch.

Each internal label in the diagrams is its split predicate. The left edge means the predicate holds and the right edge means it fails. Each leaf gives the feature values reaching it and its constant prediction.

diagram failed to render:
\begin{tikzpicture}[
  box/.style={draw,rounded corners,align=center,font=\scriptsize,inner sep=3pt}
]
\node[box] (t1r) at (-4,0) {T1 root: x1 <= 1.5};
\node[box] (t1l) at (-5.2,-1.5) {x values: 0,1\\prediction: 0};
\node[box] (t1rr) at (-2.8,-1.5) {x value: 2\\prediction: 1};
\draw (t1r.south) -- (t1l.north);
\draw (t1r.south) -- (t1rr.north);

\node[box] (t2r) at (2,0) {T2 root: x1 <= 1.5};
\node[box] (t2l) at (0.7,-1.35) {left node: x1 <= 0.5};
\node[box] (t2rr) at (3.5,-1.35) {x value: 2\\prediction: 1};
\node[box] (t2ll) at (-0.3,-2.7) {x value: 0\\prediction: 0};
\node[box] (t2lr) at (1.7,-2.7) {x value: 1\\prediction: 0};
\draw (t2r.south) -- (t2l.north);
\draw (t2r.south) -- (t2rr.north);
\draw (t2l.south) -- (t2ll.north);
\draw (t2l.south) -- (t2lr.north);
\end{tikzpicture}

Facts & Assumptions

Given: The three regression observations and the two subtrees described in the example.

[F1]

Empirical axis-aligned binary decision trees: A nonempty regression leaf predicts its sample mean, and its residual sum of squares is $N_{I} Q_{I} = \sum_{i \in I} (y_{i} - {\overset{ˉ}{y}}_{I})^{2}$ .

[F2]

Cost-complexity criteria for subtrees: The cost-complexity criterion is $C_{α} (T) = R (T) + α ∣ T ∣$ .

[F3]

Cost-complexity criteria for subtrees: For a current nonterminal node, $g (t) = [R (t) - R (T_{t})] / (∣ T_{t} ∣ - 1)$ .

[F4]

Weakest-link pruning of a finite tree: The current nonterminal node with least $g (t)$ is collapsed, with the stated fixed tie rule.

Verification

1.1givenF1algebra

In $T_{1}$ , the leaf on ${0, 1}$ has mean $0$ and the leaf on ${2}$ has mean $1$ , so both residual sums are $0$ . Splitting the first leaf in $T_{2}$ gives singleton leaves with responses $0$ and $0$ , so $T_{2}$ also has residual sum $0$ and has one additional leaf.

2.1F2step 1.1algebra

By [F2], $C_{1} (T_{1}) = 0 + 1 \cdot 2 = 2$ and $C_{1} (T_{2}) = 0 + 1 \cdot 3 = 3$ . Thus the subtrees have equal fit and different leaf penalties.

3.1F1F3F4step 1.1algebra∎

Collapsing the left branch of $T_{2}$ has loss $0$ , equal to its descendant-leaf loss, and removes one leaf, so $g (t_{L}) = 0$ . Collapsing the root predicts the full-sample mean $1 / 3$ and has loss $(0 - 1 / 3)^{2} + (0 - 1 / 3)^{2} + (1 - 1 / 3)^{2} = 2 / 3$ ; the current three leaves have loss $0$ , so $g (r o o t) = (2 / 3 - 0) / (3 - 1) = 1 / 3$ . By [F4], the first collapse is therefore the left branch.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A one-dimensional regression threshold tree

Example

Take a single predictor and the regression sample $(x_{i}, y_{i}) = (0, 0), (1, 0), (2, 1), (3, 1)$ , with maximum depth $1$ . Its candidate thresholds are the midpoints $0.5$ , $1.5$ , and $2.5$ . The child-weighted squared-error score is $2 / 3$ at $0.5$ , $0$ at $1.5$ , and $2 / 3$ at $2.5$ . Thus greedy growth chooses the unique split $x_{1} \leq 1.5$ , producing leaves on feature values ${0, 1}$ and ${2, 3}$ with predictions $0$ and $1$ .

The internal label in the diagram is the split predicate. The left edge means the predicate holds and the right edge means it fails. Each leaf gives the feature values reaching it and its constant prediction.

diagram failed to render:
\begin{tikzpicture}[
  box/.style={draw,rounded corners,align=center,font=\small,inner sep=3pt}
]
\node[box] (root) at (0,0) {split: x1 <= 1.5};
\node[box] (left) at (-2,-1.5) {x values: 0,1\\prediction: 0};
\node[box] (right) at (2,-1.5) {x values: 2,3\\prediction: 1};
\draw (root.south) -- (left.north);
\draw (root.south) -- (right.north);
\end{tikzpicture}

Facts & Assumptions

Given: The four regression observations and the greedy growth procedure with maximum depth $1$ .

[F1]

Empirical axis-aligned binary decision trees: A nonempty regression leaf predicts its sample mean and has residual sum of squares $\sum_{i \in I} (y_{i} - {\overset{ˉ}{y}}_{I})^{2}$ .

[F2]

Greedy axis-aligned CART growth on a finite sample: Candidate thresholds lie between adjacent distinct coordinate values, and the procedure chooses the candidate minimizing the child score.

[F3]

Greedy CART minimizes the listed split loss and terminates: Every nonempty coordinate-threshold partition occurs among the midpoint candidates, and the chosen split minimizes the child loss on that finite list.

Verification

1.1givenF1F2algebra

The four distinct coordinate values are $0 < 1 < 2 < 3$ , so the midpoint candidates are exactly $0.5$ , $1.5$ , and $2.5$ . At $0.5$ , the right child has responses $0, 1, 1$ , mean $2 / 3$ , and residual sum $2 / 3$ . At $1.5$ , both children have constant responses, so the score is $0$ . At $2.5$ , the left child has responses $0, 0, 1$ , mean $1 / 3$ , and residual sum $2 / 3$ .

2.1F1F3step 1.1algebra

The middle threshold is therefore the unique minimum-scoring candidate. By [F3], it is the best listed split and the procedure chooses it. Its two leaves have means $0$ and $1$ , as displayed.

3.1F2step 2.1algebra∎

The root split has depth $1 = d_{\max}$ , so the procedure stops there and returns the stated two-leaf tree. The diagram merely records the split and leaf predictions; the previously computed scores and the depth cap establish the output independently of the diagram.