TheoremStatement: Literature-sourcedProof: 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.

Unanimous version-space prediction and disagreement abstention

Statement

Fix a finite pool-based realizable active-learning instance, run the ascending-scan procedure for any finite number of steps, and let $V$ be the resulting current version space. Let $X \sim D_{X}$ be a fresh feature independent of the query history. Define the selective prediction rule $g_{V} (x)$ to be the common label $c \in {0, 1}$ when every $h \in V$ has $h (x) = c$ , and to be the abstention symbol $⊥$ otherwise. Then $DIS (V)$ is measurable, $D_{X} ({x : g_{V} (x) = ⊥}) = D_{X} (DIS (V)),$ and $D_{X} ({x : g_{V} (x) \in {0, 1}, g_{V} (x) \neq h^{*} (x)}) = 0.$ These probabilities are for a fixed query history; the formula gives the abstention probability but no automatic upper bound on it from $∣ V ∣$ .

Statement references

Finite pool-based realizable active-learning instance: defines $D_{X}$ , finite measurable classifiers, and $DIS (V)$ .

Finite-pool version-space query procedure: defines the current version space after each finite pool scan step.

Finite-pool version-space invariant and query bound: proves that every such current version space contains $h^{*}$ .

Steve Hanneke, Theory of Active Learning, version 1.1, §§2.1–2.2 and §5.1

Daniel Joseph Hsu, Algorithms for Active Learning, Chapter 2 §§2.1–2.2.2

Facts & Assumptions

Given: A current version space $V$ from the stated finite-pool procedure and a fresh feature $X \sim D_{X}$ independent of the fixed query history.

[F1]

Finite pool-based realizable active-learning instance: $H$ is finite, its binary classifiers are measurable, and $DIS (V)$ consists of points where two members of $V$ give different labels.

[F2]

Finite-pool version-space query procedure: the query history yields a current version space by finite filtering of $H$ using observed oracle labels.

[F3]

Finite-pool version-space invariant and query bound: under the pointwise exact-oracle assumption, every current version space contains $h^{*}$ .

[A1]

The fresh feature is sampled independently of the fixed query history from the probability measure $D_{X}$ .

[A2]

No choice axiom is assumed; only a finite union over pairs in $V$ is used.

Proof

1.1F1F2A2givenconstruct

For each pair $h, g \in V$ , the disagreement set ${x : h (x) \neq g (x)}$ is the union of $h^{- 1} ({0}) \cap g^{- 1} ({1})$ and $h^{- 1} ({1}) \cap g^{- 1} ({0})$ . These sets are measurable because $h$ and $g$ are measurable. Since $V$ is finite by [F1] and [F2], $DIS (V)$ is a finite union of measurable sets and is measurable; this finite union uses no choice axiom by [A2].

2.1A1F1step 1.1algebra

By the definition of $g_{V}$ , $g_{V} (x) = ⊥$ exactly when the members of $V$ do not all agree at $x$ , which is exactly when $x \in DIS (V)$ . Thus the two events in the first equality are identical, and their $D_{X}$ probabilities agree for the fresh feature in [A1].

3.1F3givenalgebra∎

If $g_{V} (x) \in {0, 1}$ , all classifiers in $V$ give that common label at $x$ . By [F3], $h^{*} \in V$ , so the common label equals $h^{*} (x)$ . Therefore the wrong-prediction event is empty and has probability zero under $D_{X}$ .

Depends on

Used by

Exact labels, slow version-space shrinkage, and abstention limits Remark

Dependency tree · two levels

7 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

Steve Hanneke, Theory of Active Learning, version 1.1, §§2.1–2.2 and §5.1 (standard reference, not scraped)
Daniel Joseph Hsu, Algorithms for Active Learning, Chapter 2 §§2.1–2.2.2 (standard reference, not scraped)