ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge 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.

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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

3 results within one dependency step 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.