Halving.update
defimported Lean
After observing that the correct label for input $x$ is $y$, the version space is updated to $\mathtt{update}(\mathtt{eval}, V, x, y) = \mathtt{voteFor}(\mathtt{eval}, V, x, y)$, i.e.\ only the hypotheses that correctly predict $y$ on $x$ are retained.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in def Halving.update (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) : Finset Hyp
- Defined in
- TCSlib, `Halving.update`
- Lean proof
- By Arhaan Aggarwal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Arhaan Aggarwal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.Halving.update← Halving.update (TCSlib/LearningTheory/MistakeBounds/Halving.lean:80): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 1
- Halving.voteForGiven an evaluation map $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$, a version space $V \subseteq \mathit{Hyp}$, an input…
- Used by 5
- Halving.mistakes_boundMistake bound for the Halving Algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let $V$ be a…
- Halving.mistake_halvesMistake bound for the Halving algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…
- Halving.mistakes$\mathtt{mistakes}(\mathtt{eval}, \mathtt{target}, V, xs)$ is the total number of prediction errors made by the Halving Algorithm when it…
- Halving.target_mem_updateTarget survives its own update. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…
- Halving.update_subsetThe updated version space is a subset. Fix an evaluation map $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$, a finite version…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in /-- The version space after observing the labelled example `(x, y)`: the hypotheses of `V` that agree with the label `y` on `x`; every hypothesis that voted for the other label is discarded. [MRT18, §8.2.1 (Halving algorithm)]; origin [Lit88, §3]. -/ def Halving.update (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) : Finset Hyp := voteFor eval V x y