Halving.predict
defimported Lean
The Halving Algorithm predicts on input $x$ by taking a majority vote of the current version space $V$: it returns $\mathsf{true}$ whenever the number of hypotheses in $V$ that predict $\mathsf{true}$ is at least as large as the number that predict $\mathsf{false}$ (ties are broken in favour of $\mathsf{true}$).
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in def Halving.predict (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) : Bool
- Defined in
- TCSlib, `Halving.predict`
- 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.predict← Halving.predict (TCSlib/LearningTheory/MistakeBounds/Halving.lean:71): 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 3
- 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…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in /-- The Halving prediction on the input `x`: the label that receives the majority of the votes of the version space `V`, with ties broken towards `true`. [MRT18, §8.2.1 (Halving algorithm)]; origin [Lit88, §3]. -/ def Halving.predict (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) : Bool := if (voteFor eval V x true).card ≥ (voteFor eval V x false).card then true else false