Cslib.MachineLearning.PACLearning.ConceptClass
abbrevimported Lean
A *concept class* over domain α with label type β is a set of functions α → β. For binary classification (β = Bool), this is equivalent to a collection of subsets of α via the characteristic function.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal NNReal in abbrev Cslib.MachineLearning.PACLearning.ConceptClass (α β : Type*)
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.ConceptClass`
- Lean proof
- By Samuel Schlesinger, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Samuel Schlesinger. 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.ConceptClass← Cslib.MachineLearning.PACLearning.ConceptClass (Cslib/MachineLearning/PACLearning/Defs.lean:121): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 64
- Cslib.MachineLearning.PACLearning.RealizableA labeled sample
Sis *realizable* by concept classCif some concept inClabels every sample point correctly. - Cslib.MachineLearning.PACLearning.IsPACLearnable.antitone_CPAC learnability is antitone in the concept class: a subclass of a learnable class is learnable.
- 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.IsPACLearnerFor
IsPACLearnerFor m ε δ C 𝒟asserts that there exists a learner usingmsamples that is(ε, δ)-correct for the concept classCover… - Cslib.MachineLearning.PACLearning.IsRPACLearnerFor.antitone_familyThe randomized PAC learner predicate is antitone in the distribution family. The universe of the randomness space
Ωis pinned so the… - Cslib.MachineLearning.PACLearning.IsRPACLearnable.rsampleComplexity_mono_family
rsampleComplexity_mono_familyfor a randomized-learnable class. - Cslib.MachineLearning.PACLearning.IsRPACLearnableA concept class
Cis *randomized PAC learnable* over the distribution family𝒟if for every accuracyε ∈ (0, 1)and confidence… - Cslib.MachineLearning.PACLearning.VersionSpacesThe family of all version spaces of a concept class, over labeled samples of every size.
- Cslib.MachineLearning.PACLearning.sampleComplexity_antitone_δDeterministic sample complexity is antitone in the confidence parameter
δ: weaker confidence requires no more samples. - Cslib.MachineLearning.PACLearning.optimalErrorThe *optimal error* of a concept class
Cunder a joint distributionD, defined as the infimum oferror D cover all concepts… - Cslib.MachineLearning.PACLearning.mem_versionSpace_iff_empiricalMiscount_zeroVersion-space membership equals concept-class membership plus zero empirical miscount (combinatorial bridge).
- Cslib.MachineLearning.PACLearning.IsPACLearnerFor.antitone_familyThe deterministic PAC learner predicate is antitone in the distribution family: a learner for a larger family
𝒟'is also a learner for… - 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.VersionSpaceThe *version space* of a concept class
Cgiven a labeled sampleS: the set of concepts inCwhose labels agree withSon every… - Cslib.MachineLearning.PACLearning.sampleComplexity_mono_familyDeterministic sample complexity is monotone in the distribution family under
⊆: a smaller family (fewer distributions to cover) requires… - Cslib.MachineLearning.PACLearning.sampleComplexityThe *sample complexity* of a concept class
Cunder a learner modelL, at accuracyε ∈ (0, 1)and confidenceδ ∈ (0, 1)over… - 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.versionSpaces_ncard_leA finite concept class has at most
2 ^ C.ncardversion spaces: the lattice embeds in the powerset. - Cslib.MachineLearning.PACLearning.rsampleComplexity_mono_familyRandomized sample complexity is monotone in the distribution family under
⊆. - 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.SetShattersA binary concept class
C*shatters* a setWif for every subsetW' ⊆ W, there exists a conceptc ∈ Cwhose positive set… - 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.rsampleComplexity_antitone_δRandomized sample complexity is antitone in the confidence parameter
δ. - Cslib.MachineLearning.PACLearning.IsRPACLearnerFor.mono_δA randomized PAC learner with confidence
δ₁is also a randomized PAC learner with any weaker confidenceδ₂ ≥ δ₁. Unlikemono_εor… - Cslib.MachineLearning.PACLearning.versionSpaces_finiteA finite concept class has finitely many version spaces.
- Cslib.MachineLearning.PACLearning.versionSpace_mono_C*Version space is monotone in the concept class.*
- Cslib.MachineLearning.PACLearning.IsPACLearnerFor.mono_δA PAC learner with confidence
δ₁is also a PAC learner with any weaker confidenceδ₂ ≥ δ₁: the failure-probability bound only gets… - Cslib.MachineLearning.PACLearning.IsConsistent.empiricalError_eq_zeroA consistent learner has zero empirical error on every sample.
- Cslib.MachineLearning.PACLearning.sampleComplexity_mono_CDeterministic sample complexity is monotone in the concept class under
⊆: a smaller class (weaker agnostic benchmark) requires no more… - Cslib.MachineLearning.PACLearning.LearnerModelA *learner model* is a predicate on (sample size, accuracy, confidence, concept class, distribution family) that classifies which sample…
- Cslib.MachineLearning.PACLearning.hasFiniteVCDim_iffA class has finite VC dimension iff there is a uniform bound on the cardinality of every shattered finite set.
- 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.HasFiniteVCDimA binary concept class
Chas *finite VC dimension* if there is a uniform upper bound on the cardinalities of finite sets it shatters.… - Cslib.MachineLearning.PACLearning.mem_versionSpace_iff_empiricalError_zeroVersion-space membership equals concept-class membership plus zero empirical error (measure-theoretic bridge).
- Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_mono_family
sampleComplexity_mono_familyfor a learnable class (learnability at the *larger* family𝒟'is the hypothesis). - Cslib.MachineLearning.PACLearning.SetShatters.subsetShattering is anti-monotone in the shattered set: if
CshattersWandV ⊆ W, thenCshattersV. - Cslib.MachineLearning.PACLearning.IsRPACLearnerFor
IsRPACLearnerFor m ε δ C 𝒟asserts that there exists a *randomized* learner usingmsamples that is(ε, δ)-correct for the concept… - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.mono_εA PAC learner with accuracy
ε₁is also a PAC learner with any weaker accuracyε₂ ≥ ε₁: the bad event{error > opt + ε}only shrinks. - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.toIsRPACLearnerForEvery deterministic PAC learner is in particular a randomized PAC learner (with the trivial one-point randomness space
PUnit). - Cslib.MachineLearning.PACLearning.inter_mem_versionSpacesThe version-space family is closed under intersection (append the witnessing samples).
- Cslib.MachineLearning.PACLearning.IsRPACLearnable.antitone_familyRandomized PAC learnability is antitone in the distribution family.
- Cslib.MachineLearning.PACLearning.IsRPACLearnable.rsampleComplexity_antitone_δ
rsampleComplexity_antitone_δfor a randomized-learnable class. - Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_mono_C
sampleComplexity_mono_Cfor a learnable class (learnability at the *larger* classC'is the hypothesis). - Cslib.MachineLearning.PACLearning.rsampleComplexityThe *randomized sample complexity* of
C, i.e.sampleComplexityinstantiated at the randomized learner modelIsRPACLearnerFor. The… - 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.sampleComplexity_antitone_εDeterministic sample complexity is antitone in the accuracy parameter
ε: weaker accuracy requires no more samples. - Cslib.MachineLearning.PACLearning.IsPACLearnable.antitone_familyPAC learnability is antitone in the distribution family: a subfamily of a learnable family is learnable.
- Cslib.MachineLearning.PACLearning.vcDimThe *Vapnik-Chervonenkis dimension* of a binary concept class
Cis the supremum of the cardinalities of finite sets shattered byC.… - 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.output_mem_conceptClassA consistent learner's output is always in the concept class.
- Cslib.MachineLearning.PACLearning.SetShatters.supersetShattering is monotone in the concept class: if
CshattersWandC ⊆ C', thenC'shattersW. - Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_antitone_δ
sampleComplexity_antitone_δfor a learnable class: the nonemptiness hypothesis comes for free fromIsPACLearnable. - Cslib.MachineLearning.PACLearning.IsPACLearnable.toIsRPACLearnableDeterministic PAC learnability implies randomized PAC learnability.
- Cslib.MachineLearning.PACLearning.IsPACLearnable.sampleComplexity_antitone_ε
sampleComplexity_antitone_εfor a learnable class. - Cslib.MachineLearning.PACLearning.IsPACLearnableA concept class
Cis *PAC learnable* over the distribution family𝒟if for every accuracyε ∈ (0, 1)and confidenceδ ∈ (0, 1),… - Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forallGeneral pointwise monotonicity of
sampleComplexity: if every witness sample size for(L₁, ε₁, δ₁, C₁, 𝒟₁)is also a witness for… - Cslib.MachineLearning.PACLearning.IsPACLearnerFor.antitone_CThe deterministic PAC learner predicate is antitone in the concept class: a learner for a larger class
C'is also a learner for any… - Cslib.MachineLearning.PACLearning.IsConsistent.output_agreesA consistent learner's output agrees with the sample on every observed point.
- Cslib.MachineLearning.PACLearning.IsConsistent.empiricalMiscount_eq_zeroA consistent learner has zero empirical miscount on every sample.
- Cslib.MachineLearning.PACLearning.RealizableA labeled sample
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal NNReal in /-- A *concept class* over domain `α` with label type `β` is a set of functions `α → β`. For binary classification (`β = Bool`), this is equivalent to a collection of subsets of `α` via the characteristic function. -/ abbrev Cslib.MachineLearning.PACLearning.ConceptClass (α β : Type*) := Set (α → β)