Halving.mistakes
defimported Lean
$\mathtt{mistakes}(\mathtt{eval}, \mathtt{target}, V, xs)$ is the total number of prediction errors made by the Halving Algorithm when it processes the input list $xs$, using the version space $V$, with the true label at each step supplied by $\mathtt{target}$. It is defined recursively: the empty list yields zero mistakes, and for a list $x :: xs$ the count is $1$ if the algorithm mispredicts on $x$ (else $0$), plus the mistakes on the remainder using the updated version space.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in def Halving.mistakes (eval : Hyp → X → Bool) (target : Hyp) (V : Finset Hyp) : List X → ℕ
- Defined in
- TCSlib, `Halving.mistakes`
- 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.mistakes← Halving.mistakes (TCSlib/LearningTheory/MistakeBounds/Halving.lean:178): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- Halving.updateAfter observing that the correct label for input $x$ is $y$, the version space is updated to…
- Halving.predictThe Halving Algorithm predicts on input $x$ by taking a majority vote of the current version space $V$: it returns $\mathsf{true}$…
- Used by 2
- 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.halving_boundHalving mistake bound. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ assign a Boolean label to each input under each…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in /-- The number of mistakes the Halving Algorithm makes when run from the version space `V` over the finite list of inputs `xs`, with every label generated by the hypothesis `target` (the label of `x` is `eval target x`). At each input the algorithm predicts with the current version space, incurs one mistake if that prediction differs from the target's label, and then updates the version space with the observed label before moving to the next input. [MRT18, §8.2.1 (Halving algorithm)]; origin [Lit88, §3]. -/ def Halving.mistakes (eval : Hyp → X → Bool) (target : Hyp) (V : Finset Hyp) : List X → ℕ | [] => 0 | x :: xs => let y := eval target x let V' := update eval V x y (if predict eval V x = y then 0 else 1) + mistakes eval target V' xs