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.

A zero-margin bootstrap forest need not approach strict-margin risk

Example

Use classification labels $0 < 1$ and the fixed training sample $D = ((x_{1}, 0), (x_{2}, 1))$ with $x_{1} = (0, 1)$ and $x_{2} = (1, 0)$ . Grow trees with depth cap $1$ and one uniformly selected feature at the root, along with the size- $2$ bootstrap samples in the bagged random-forest algorithm. Let $Θ_{b}$ be IID tree randomizations with common law $Q$ , write $p_{c} (x) = Q {h (x, Θ_{b}) = c}$ , and define $m (x, y) = p_{y} (x) - \max_{c \neq y} p_{c} (x)$ . Let the test pair have the point-mass law at $(x^{*}, Y) = ((1 / 4, 1 / 4), 1)$ , and for $B$ trees let $G_{B} (x)$ be their majority vote with class $0$ breaking a tie and $P E_{B} = 1 {G_{B} (x^{*}) \neq 1}$ . Then each randomized tree predicts class $1$ at $x^{*}$ with probability $1 / 2$ , so $m (x^{*}, 1) = 0$ and $P {m (X, Y) < 0} = 0$ . For every odd $B$ , $P E_{B}$ has expectation $1 / 2$ over the tree randomizations; consequently it cannot converge almost surely to the strict-margin value $0$ .

For a mixed bootstrap sample, the two possible root splits and their leaf labels are shown below. In each tree the left child is selected when the displayed feature is at most $1 / 2$ , and the right child otherwise. The test point lies in the left child of both trees, whose labels differ. The diagram records these two CART cases; the verification derives the risk from the finite randomization counts and does not rely on the diagram.

diagram failed to render:
\begin{tikzpicture}[level distance=10mm,sibling distance=18mm]
  \node[draw] at (0,0) {$x_1\le\tfrac12$}
    child {node[draw] {$0$}}
    child {node[draw] {$1$}};
  \node[draw] at (6,0) {$x_2\le\tfrac12$}
    child {node[draw] {$1$}}
    child {node[draw] {$0$}};
\end{tikzpicture}

Example references

Bootstrap and randomized-feature construction

Risk limit with the zero-margin hypothesis

Breiman, “Random Forests,” Theorem 1.2, printed p. 7, and Appendix I, printed pp. 29–30

Facts & Assumptions

Given: The sample and test law in the Example, independent bootstrap samples of size $2$ , and independent uniform one-feature choices at each tree root.

[F1]

Bagged random-forest construction on a fixed finite sample: A bootstrap sample contains $N_{b i}$ copies of training observation $i$ , and a node uses its independently drawn feature subset when forming split candidates.

[F2]

Independent random elements have product joint law: The joint law of a finite independent family of random elements is the product of their marginal laws.

[F3]

Dominated convergence: Almost-everywhere convergence under a common integrable majorant implies convergence of the integrals.

[F4]

Almost-sure limiting risk of an infinite random-forest classifier: The stated conditional-risk limit assumes that the zero-margin test-pair set has probability zero.

Verification

1.1givenF1algebra

There are four equally likely ordered bootstrap draws. The count vectors $(2, 0)$ and $(0, 2)$ each have probability $1 / 4$ , and the mixed count vector $(1, 1)$ has probability $1 / 2$ .

2.1givenF1step 1.1algebra

With counts $(2, 0)$ the only leaf predicts $0$ , and with counts $(0, 2)$ it predicts $1$ . With mixed counts, either feature separates the two training points at $1 / 2$ . The selected feature is uniform: feature $1$ sends $x^{*}$ to the class- $0$ leaf, while feature $2$ sends it to the class- $1$ leaf. Hence $Q {h (x^{*}, Θ) = 1} = 1 / 4 + (1 / 2) (1 / 2) = 1 / 2$ .

3.1givenF2F4step 2.1algebra

At the point-mass test pair, $p_{0} (x^{*}) = p_{1} (x^{*}) = 1 / 2$ , so $m (x^{*}, 1) = 0$ and $P {m < 0} = 0$ ; the zero-margin hypothesis in [F4] fails. For every odd $B$ , the class- $1$ vote count has a symmetric binomial law with no tie; exactly half of its outcomes are below $B / 2$ . The conditional risk is the error indicator at this single test pair, so $E_{Q} [P E_{B}] = 1 / 2$ .

4.1F3step 3.1algebra∎

If $P E_{2 k + 1} \to 0$ almost surely, then the bounded random variables $P E_{2 k + 1} \in [0, 1]$ would have expectations tending to zero by [F3]. This is incompatible with step 3.1, so the full risk sequence cannot converge almost surely to the strict-margin value $0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

25 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

Leo Breiman, "Random Forests," Machine Learning 45 (2001), 5–32; full text hosted by the University of Chicago Macro Finance Research Program (standard reference, not scraped)