Cslib.MachineLearning.PACLearning.VersionSpace
defimported Lean
The *version space* of a concept class C given a labeled sample S: the set of concepts in C whose labels agree with S on every observed point.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal in variable {α : Type*} {β : Type*} in def Cslib.MachineLearning.PACLearning.VersionSpace {m : ℕ} (C : ConceptClass α β) (S : LabeledSample α β m) : ConceptClass α β
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.VersionSpace`
- Lean proof
- By Dhruv Gupta, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Dhruv Gupta. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.MachineLearning.PACLearning.VersionSpace← Cslib.MachineLearning.PACLearning.VersionSpace (Cslib/MachineLearning/PACLearning/VersionSpace.lean:65): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- Cslib.MachineLearning.PACLearning.LabeledSampleA *labeled sample* of size
mover domainαwith label typeβis a finite sequence of(point, label)pairs. - Cslib.MachineLearning.PACLearning.ConceptClassA *concept class* over domain
αwith label typeβis a set of functionsα → β. For binary classification (β = Bool), this is…
- Cslib.MachineLearning.PACLearning.LabeledSampleA *labeled sample* of size
- Used by 20
- Cslib.MachineLearning.PACLearning.versionSpace_empty_sampleVersion space on the empty sample equals the whole concept class.
- Cslib.MachineLearning.PACLearning.mem_versionSpaces_iffMembership in the version-space family unfolds to a witnessing sample.
- Cslib.MachineLearning.PACLearning.VersionSpacesThe family of all version spaces of a concept class, over labeled samples of every size.
- Cslib.MachineLearning.PACLearning.mem_versionSpace_iff_empiricalMiscount_zeroVersion-space membership equals concept-class membership plus zero empirical miscount (combinatorial bridge).
- Cslib.MachineLearning.PACLearning.versionSpaces_subset_powersetEvery version space is a subset of the class: the family lives in the powerset of
C. - Cslib.MachineLearning.PACLearning.ae_mem_versionSpace_of_realizableUnder iid sampling from the realizable joint distribution induced by
c ∈ Cand a probability measurePonα, the target conceptc… - Cslib.MachineLearning.PACLearning.versionSpace_reindex*Version space reindexing.* For any reindexing
f : Fin m → Fin n, the version space onSis contained in the version space on the… - Cslib.MachineLearning.PACLearning.mem_versionSpace_iffMembership in the version space unfolds to concept membership plus per-sample consistency.
- Cslib.MachineLearning.PACLearning.IsConsistentA learner is *consistent* with the concept class
Cif, on every labeled sample it receives, its output hypothesis lies in the version… - Cslib.MachineLearning.PACLearning.versionSpace_antitone*Version space antitonicity.* Given a sample of size
nandm ≤ n, the version space on allnobservations is a subset of the version… - Cslib.MachineLearning.PACLearning.versionSpace_mono_C*Version space is monotone in the concept class.*
- Cslib.MachineLearning.PACLearning.IsConsistent.empiricalError_eq_zeroA consistent learner has zero empirical error on every sample.
- Cslib.MachineLearning.PACLearning.mem_versionSpace_of_realizable*Realizable version-space nonemptiness.* If a target concept
clies inCand the sampleSis labeled byc(i.e. every… - Cslib.MachineLearning.PACLearning.mem_versionSpace_iff_empiricalError_zeroVersion-space membership equals concept-class membership plus zero empirical error (measure-theoretic bridge).
- Cslib.MachineLearning.PACLearning.inter_mem_versionSpacesThe version-space family is closed under intersection (append the witnessing samples).
- Cslib.MachineLearning.PACLearning.versionSpace_append*The version-space meet law.* The version space of an appended sample is the intersection of the version spaces of the two parts:…
- Cslib.MachineLearning.PACLearning.versionSpace_subsetThe version space is a subset of the original concept class.
- Cslib.MachineLearning.PACLearning.Realizable.versionSpace_nonemptyA realizable sample has nonempty version space.
- Cslib.MachineLearning.PACLearning.self_mem_versionSpacesThe whole class is a version space (of the empty sample) which means the family has top
C. - Cslib.MachineLearning.PACLearning.IsConsistent.empiricalMiscount_eq_zeroA consistent learner has zero empirical miscount on every sample.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal in variable {α : Type*} {β : Type*} in /-- The *version space* of a concept class `C` given a labeled sample `S`: the set of concepts in `C` whose labels agree with `S` on every observed point. -/ def Cslib.MachineLearning.PACLearning.VersionSpace {m : ℕ} (C : ConceptClass α β) (S : LabeledSample α β m) : ConceptClass α β := {h ∈ C | ∀ i : Fin m, h (S i).1 = (S i).2}