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

The unlabeled marginal alone does not identify labels

Statement

Let $X$ be a finite nonempty feature set with its discrete sigma-algebra, and let $μ : X \to [0, 1]$ satisfy $\sum_{x \in X} μ (x) = 1$ . Let $S ⊊ X$ be a nonempty set of observed labeled inputs, and choose $x_{⋆} \in X ∖ S$ with $q = μ (x_{⋆}) > 0$ . Let $h_{0}, h_{1} : X \to {0, 1}$ agree on $X ∖ {x_{⋆}}$ and differ at $x_{⋆}$ . For $j \in {0, 1}$ , let $P_{j}$ be the joint law assigning mass $μ (x)$ to $(x, h_{j} (x))$ . Both laws have the same feature marginal and the same observed labels on $S$ . Let $H = {g : X \to {0, 1}}$ , and let $Q : H \to [0, 1]$ satisfy $\sum_{g \in H} Q (g) = 1$ , so it is a probability vector; take the same $Q$ under both laws, as a predictor rule using their common information must do. For the zero-one population risk $R_{P_{j}} (g) = \sum_{x \in X} μ (x) 1 {g (x) \neq h_{j} (x)},$ the expected risks satisfy $\max_{j \in {0, 1}} \sum_{g \in H} Q (g) R_{P_{j}} (g) \geq \frac{q}{2} .$

Statement references

Supervised prediction problems: a prediction problem supplies a joint law, measurable predictors, and a measurable loss.

Population and empirical risk: population risk is the integral of the loss under the joint law; for these finite discrete laws it is the displayed finite sum.

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 1 §§1.3.2–1.3.3

Facts & Assumptions

Given: A finite discrete feature set, a probability mass function $μ$ , a nonempty observed-input set $S$ , an unseen atom $x_{⋆} \notin S$ with positive mass $q$ , two binary label functions that differ only at $x_{⋆}$ , and a common randomized predictor distribution $Q$ . Prove the worst of the two expected zero-one population risks is at least $q / 2$ .

[A1]

The feature set $X$ is finite and discrete, $μ$ is a probability mass function, $x_{⋆} \notin S$ has mass $q > 0$ , and $h_{0}, h_{1}$ agree away from $x_{⋆}$ and differ there.

[F1]

Supervised prediction problems: a supervised problem has measurable instance and label spaces, a probability law on their product, measurable predictors, and a nonnegative measurable loss. Every map on a finite discrete feature set is measurable.

[F2]

Population and empirical risk: $R_{P} (g)$ is the integral of the loss $ℓ (g (x), y)$ under the joint law $P$ ; on the finite laws here with zero-one loss it equals the sum in the Statement.

Proof

1.1givenA1F1F2

For each $j$ , assigning mass $μ (x)$ to $(x, h_{j} (x))$ defines a probability law because the masses are nonnegative and sum to one. The feature marginal is $μ$ for both laws, and $h_{0} = h_{1}$ on $S$ , so the observed labeled input and unlabeled marginal are identical. Finiteness and the discrete sigma-algebra make every predictor and zero-one loss measurable, so [F2] gives the risk formula in the Statement.

2.1givenA1step 1.1algebra

Fix $g \in H$ . At each $x \neq x_{⋆}$ , the two risk summands agree because $h_{0} (x) = h_{1} (x)$ . At $x_{⋆}$ , the binary labels differ, so exactly one of the two indicators $1 {g (x_{⋆}) \neq h_{0} (x_{⋆})}$ and $1 {g (x_{⋆}) \neq h_{1} (x_{⋆})}$ equals one. Therefore $R_{P_{0}} (g) + R_{P_{1}} (g) \geq q$ .

3.1givenstep 2.1algebra∎

Multiply the inequality in step 2.1 by $Q (g) \geq 0$ and sum over the finite class $H$ . Since $\sum_{g} Q (g) = 1$ , the two expected risks sum to at least $q$ , so at least one is at least $q / 2$ . This proves the claimed maximum.

Depends on

Used by

Dependency tree · two levels

10 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

Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien (editors), Semi-Supervised Learning, MIT Press, 2006 (standard reference, not scraped)