Cslib.MachineLearning.PACLearning.LabeledSample
abbrevimported Lean
A *labeled sample* of size m over domain α with label type β is a finite sequence of (point, label) pairs.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped ENNReal NNReal in abbrev Cslib.MachineLearning.PACLearning.LabeledSample (α β : Type*) (m : ℕ)
- Defined in
- CSLib, `Cslib.MachineLearning.PACLearning.LabeledSample`
- 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.LabeledSample← Cslib.MachineLearning.PACLearning.LabeledSample (Cslib/MachineLearning/PACLearning/Defs.lean:125): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 38
- Cslib.MachineLearning.PACLearning.RealizableA labeled sample
Sis *realizable* by concept classCif some concept inClabels every sample point correctly. - 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.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.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.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.empiricalErrorThe *empirical 0-1 error* of
honS: the empirical distribution's mass on the disagreement set. - 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.empiricalError_eq_divThe empirical 0-1 error equals the empirical miscount divided by the sample size.
- 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.empiricalMeasureThe *empirical distribution* of a labeled sample: the uniform mixture of Dirac measures at each sample point. Equals the zero measure when…
- 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.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.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.empiricalMiscountThe *empirical miscount* of a hypothesis
hon a labeled sampleS: the number of sample points wherehpredicts incorrectly. - 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.output_mem_conceptClassA consistent learner's output is always in the concept class.
- Cslib.MachineLearning.PACLearning.LearnerA *learner* using
msamples is a function that takes a labeled sample and produces a hypothesis (a function from the domain to the label… - 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 *labeled sample* of size `m` over domain `α` with label type `β` is a finite sequence of `(point, label)` pairs. -/ abbrev Cslib.MachineLearning.PACLearning.LabeledSample (α β : Type*) (m : ℕ) := Fin m → (α × β)