99 Learning Theory — Halving
99.1 Overview
This module formalises the Halving Algorithm for binary classification in the realizable online-learning setting. Given a finite version space \(V\) of hypotheses and a sequence of labelled examples generated by an unknown target hypothesis, the algorithm predicts by majority vote and eliminates every consistent-minority on each mistake. The central result is that the number of mistakes is at most \(\lfloor \log _2 |V|\rfloor \).
99.2 Declarations
Given an evaluation map \(\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}\), a version space \(V \subseteq \mathit{Hyp}\), an input \(x \in X\), and a label \(y \in \mathsf{Bool}\), \(\mathtt{voteFor}(\mathtt{eval}, V, x, y)\) is the subset of \(V\) consisting of all hypotheses that predict label \(y\) on input \(x\).
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}\)).
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.
For any version space \(V\) and input \(x\), the false-voters and true-voters partition \(V\):
The updated version space is always a subset of the previous one: \(\mathtt{update}(\mathtt{eval}, V, x, y) \subseteq V\).
In the realizable setting, if \(\mathtt{target} \in V\) then after updating on the correctly labelled example \((x,\, \mathtt{eval}\; \mathtt{target}\; x)\) the target hypothesis remains in the new version space: \(\mathtt{target} \in \mathtt{update}(\mathtt{eval}, V, x, \mathtt{eval}\; \mathtt{target}\; x)\).
If the algorithm makes a mistake on input \(x\) with true label \(y\) (i.e. \(\mathtt{predict}(\mathtt{eval}, V, x) \ne y\)), then after the update at most half the hypotheses survive:
For natural numbers \(a\) and \(b\) with \(b \gt 0\) and \(2b \le a\),
\(\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.
In the realizable setting (\(\mathtt{target} \in V\)), the total number of mistakes made by the Halving Algorithm on any input sequence \(xs\) is at most \(\lfloor \log _2 |V|\rfloor \):
Specialising to the initial hypothesis class \(H\) (with \(\mathtt{target} \in H\)), the Halving Algorithm makes at most \(\lfloor \log _2 |H|\rfloor \) mistakes on any input sequence: