TheoremStatement: AI-adaptedProof: 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.

Breiman's random-forest strength–correlation error bound

Statement

Fix a finite training dataset and a classifier $h (x, θ)$ taking values in an ordered finite class set $C = {c_{1} < \dots < c_{J}}$ with $J \geq 2$ . Assume $h$ is jointly measurable on the product of the test-feature space and the randomization space. Let $Z = (X, Y)$ be a test pair with $Y \in C$ and test law $P$ . Let $Θ, Θ^{'}$ be independent randomizations with common law $Q$ , and assume the pair $(Θ, Θ^{'})$ is independent of $Z$ . For $j \in {1, \dots, J}$ define $p_{j} (x) = Q {θ : h (x, θ) = c_{j}}$ . For $y = c_{k}$ , let $\hat{j} (x, y)$ be the least index attaining $\max_{j \neq k} p_{j} (x)$ , and define the limiting margin

m (x, y) = p_{k} (x) - p_{\hat{j} (x, y)} (x), s = E_{P} [m (Z)] .

Assume $s > 0$ . For a tree randomization $θ$ , define the raw margin $r_{θ} (x, y) = 1 {h (x, θ) = y} - 1 {h (x, θ) = c_{\hat{j} (x, y)}}$ and $s d (θ) = \sqrt{{Var}_{P} (r_{θ} (Z))}$ . Put $d = E_{Q} [s d (Θ)]$ . If $d = 0$ , then $P {m (Z) < 0} = 0$ . If $d > 0$ , define

ρ = \frac{E_{Q \times Q} [{Cov}_{P} (r_{Θ} (Z), r_{Θ^{'}} (Z))]}{d^{2}} .

Then $ρ \geq 0$ and

P {m (Z) < 0} \leq ρ \frac{1 - s^{2}}{s^{2}} .

The covariance formula for $ρ$ is Breiman's weighted mean raw-margin correlation written without undefined zero-standard-deviation correlation terms.

Statement references

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

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.4, printed pp. 597–602; used for the variance/correlation context, not as a proof of this bound

Facts & Assumptions

Given: The fixed data, classifier jointly measurable on the product of the test-feature and randomization spaces, finite ordered class set, class-valued test response, independent randomizations and test pair, and positive-strength condition in the Statement.

[F1]

Bagged random-forest construction on a fixed finite sample: The tree law is fixed conditional on the training data, and each tree takes one class value at an input.

[F2]

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

[F3]

Moments, variance, and covariance on a probability space: For square-integrable real random variables, variance is the mean squared centered value and covariance is the mean product of centered values.

[F4]

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.

[F5]

Fubini's theorem for L^1 functions on a sigma-finite product: For an integrable function on a product of sigma-finite measure spaces, either order of iterated integration gives the product integral.

[F6]

Cauchy-Schwarz for random variables: If $U, V \in L^{2} (Q)$ , then $E_{Q} ∣ U V ∣ \leq (E_{Q} U^{2})^{1 / 2} (E_{Q} V^{2})^{1 / 2}$ .

[F7]

Chebyshev's inequality for random variables: For square-integrable $W$ and $a > 0$ , $P (∣ W - E W ∣ \geq a) \leq Var (W) / a^{2}$ .

Proof

1.1givenF1F2algebra

For each fixed $z = (x, y)$ , the definition of $\hat{j}$ gives $E_{Q} [r_{Θ} (z)] = p_{k} (x) - p_{\hat{j} (x, y)} (x) = m (z)$ . Also $∣ r_{θ} (z) ∣ \leq 1$ , so all displayed means and covariances are finite.

2.1F3F4F5step 1.1algebra

The bounded jointly measurable class indicators and [F5] make $p_{j}$ and the finite maximizer $\hat{j}$ measurable. By [F4] the pair $(Θ, Θ^{'}, Z)$ has product law, and [F5] permits exchanging the integrals of these bounded functions. Thus $E_{Q \times Q} [{Cov}_{P} (r_{Θ}, r_{Θ^{'}})] = E_{P} [m (Z)^{2}] - s^{2} = {Var}_{P} (m (Z))$ . Indeed, the product of the two conditional raw-margin means is $m (z)^{2}$ , while the product of their $P$ -means integrates to $(E_{P} m)^{2} = s^{2}$ . If both standard deviations are positive, covariance equals correlation times their product; if either is zero, both the covariance and the weighted correlation term are zero. Thus the covariance expression for $ρ$ is exactly Breiman's weighted mean raw-margin correlation.

3.1F2F3F5F6step 1.1step 2.1algebra

Suppose $d > 0$ . From step 2.1, $ρ = {Var}_{P} (m) / d^{2} \geq 0$ . Since $r_{θ}^{2} \leq 1$ , $E_{Q} [s d (Θ)^{2}] = E_{Q \times P} [r_{Θ}^{2}] - E_{Q} [(E_{P} r_{Θ})^{2}] \leq 1 - s^{2}$ . The final inequality uses $E_{Q} [(E_{P} r_{Θ})^{2}] \geq (E_{Q} E_{P} r_{Θ})^{2} = s^{2}$ , by [F6] with one factor equal to $1$ ; [F5] and step 1.1 give $E_{Q} E_{P} r_{Θ} = s$ . The same inequality gives $d^{2} \leq E_{Q} [s d (Θ)^{2}]$ . Therefore ${Var}_{P} (m) = ρ d^{2} \leq ρ (1 - s^{2})$ .

4.1F7step 3.1algebra

Since $s > 0$ , the event ${m (Z) < 0}$ is contained in ${∣ m (Z) - s ∣ \geq s}$ . Applying [F7] and then step 3.1 gives $P {m (Z) < 0} \leq {Var}_{P} (m (Z)) / s^{2} \leq ρ (1 - s^{2}) / s^{2}$ .

5.1F2F3F5step 1.1algebra∎

If $d = 0$ , then $s d \geq 0$ and $E_{Q} s d = 0$ . For each $n \geq 1$ , $Q {s d \geq 1 / n} = 0$ , since otherwise $E_{Q} s d > 0$ ; taking the countable union gives $s d = 0$ $Q$ -almost everywhere. For each such $θ$ , $E_{P} (r_{θ} - E_{P} r_{θ})^{2} = 0$ , so the same nonnegative-integral argument makes $r_{θ} (Z) = E_{P} r_{θ}$ $P$ -almost surely. By [F5], $m (Z) = E_{Q} r_{Θ} (Z)$ is therefore the constant $E_{P} m (Z) = s > 0$ for $P$ -almost every $Z$ . Hence $P {m (Z) < 0} = 0$ , as claimed in this case.

Depends on

Used by

A two-stump strength and correlation calculation Example

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)
Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., corrected 12th printing, Chapter 15 (standard reference, not scraped)