ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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 two-stump strength and correlation calculation

Example

Let $X \in {0, 1}$ , $Y = X$ , with $P (X = 0, Y = 0) = 3 / 4$ and $P (X = 1, Y = 1) = 1 / 4$ . Conditional on fixed training data, let each randomized tree independently be the constant class- $0$ stump with probability $3 / 4$ and the constant class- $1$ stump with probability $1 / 4$ . For a randomization $θ$ , write $p_{c} (x) = Q {h (x, θ) = c}$ ; for $y \in {0, 1}$ define $m (x, y) = p_{y} (x) - p_{1 - y} (x)$ , $s = E [m (X, Y)]$ , and $P E^{*} = P {m (X, Y) < 0}$ . For each tree set $r_{θ} (x, y) = 1 {h (x, θ) = y} - 1 {h (x, θ) = 1 - y}$ and $s d (θ) = \sqrt{{Var}_{X, Y} (r_{θ} (X, Y))}$ . For independent randomizations $Θ, Θ^{'}$ let $d = E_{Q} s d (Θ)$ and $ρ = E_{Q \times Q} [{Cov}_{X, Y} (r_{Θ}, r_{Θ^{'}})] / d^{2}$ . Then the limiting margins at the two test pairs are $m (0, 0) = 1 / 2$ and $m (1, 1) = - 1 / 2$ , so $s = 1 / 4$ and $P E^{*} = 1 / 4$ . Each tree's raw-margin standard deviation is $\sqrt{3 / 4}$ , the covariance numerator defining $ρ$ is $3 / 16$ , and $ρ = 1 / 4$ . The strength-correlation bound has right-hand side $15 / 4$ in this example.

Example references

Strength, raw margins, and the correlation bound

Breiman, “Random Forests,” Definitions 2.1–2.2 and Theorem 2.3, printed pp. 8–9

Facts & Assumptions

Given: The test law and independent two-stump randomization law in the Example.

[F1]

Bagged random-forest construction on a fixed finite sample: A regression or classification forest aggregates trees with a fixed class order, and a classification tree casts one class vote.

[F2]

Breiman's random-forest strength–correlation error bound: The strength is $s = E_{P} m$ , tree standard deviations are $s d (θ) = \sqrt{{Var}_{P} (r_{θ})}$ , and for $d > 0$ the correlation parameter is the expected independent-pair covariance divided by $d^{2}$ .

[F3]

Expectation of a nonnegative or integrable random variable: Expectation on a probability space is integration against its probability measure.

[F4]

Moments, variance, and covariance on a probability space: Variance and covariance are expectations of the corresponding centered products.

[F5]

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.

Verification

1.1F1F2F3algebra

By the tree-vote convention [F1], at $Z = (0, 0)$ the correct class receives probability $3 / 4$ and the wrong class $1 / 4$ , giving margin $1 / 2$ . At $Z = (1, 1)$ , the correct class receives probability $1 / 4$ and the wrong class $3 / 4$ , giving margin $- 1 / 2$ . Therefore $s = (3 / 4) (1 / 2) + (1 / 4) (- 1 / 2) = 1 / 4$ and $P E^{*} = 1 / 4$ .

1.2F2F3F4algebra

For tree type $A$ , the raw margin is $+ 1$ at $(0, 0)$ and $- 1$ at $(1, 1)$ ; its mean is $1 / 2$ and its second moment is $1$ , so its variance is $3 / 4$ . Type $B$ reverses the two signs, giving mean $- 1 / 2$ and the same variance $3 / 4$ . Thus $s d (A) = s d (B) = \sqrt{3 / 4}$ and $d^{2} = 3 / 4$ .

2.1F2F4F5step 1.2algebra

The independent pair has probabilities $P (A, A) = 9 / 16$ , $P (B, B) = 1 / 16$ , and total mixed probability $6 / 16$ . The covariance over $Z$ is $3 / 4$ for equal types and $- 3 / 4$ for mixed types, so its expectation is $[(9 + 1 - 6) / 16] (3 / 4) = 3 / 16$ . By [F2] and [F5], $ρ = (3 / 16) / (3 / 4) = 1 / 4$ .

3.1F2step 1.1step 2.1algebra∎

Substitution gives $ρ (1 - s^{2}) / s^{2} = (1 / 4) (15 / 16) / (1 / 16) = 15 / 4$ , and the example's error $1 / 4$ satisfies the bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

19 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)