96 Learning Theory — Halving
96.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 \).
96.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.
Let \(\mathrm{eval}\) be a Boolean evaluation map assigning to each hypothesis and each input a truth value, let \(V\) be a finite version space of hypotheses, and let \(x\) be an input. Every hypothesis in \(V\) predicts either \(\mathsf{false}\) or \(\mathsf{true}\) on \(x\), so the number of hypotheses in \(V\) predicting \(\mathsf{false}\) on \(x\) and the number predicting \(\mathsf{true}\) on \(x\) sum to the total number of hypotheses in \(V\):
Fix an evaluation map \(\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}\), a finite version space \(V \subseteq \mathit{Hyp}\), an input \(x \in X\), and a label \(y \in \mathsf{Bool}\). Then the updated version space is contained in the original one: \(\mathtt{update}(\mathtt{eval}, V, x, y) \subseteq V\).
Let \(\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}\) be an evaluation map, let \(V \subseteq \mathit{Hyp}\) be a version space, fix an input \(x \in X\), and let \(\mathtt{target} \in V\) be a hypothesis. Then \(\mathtt{target}\) remains in the version space obtained by updating \(V\) on \(x\) with the label that \(\mathtt{target}\) itself assigns, that is, \(\mathtt{target} \in \mathtt{update}(\mathtt{eval}, V, x, \mathtt{eval}\, \mathtt{target}\, x)\).
Let \(\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}\) be an evaluation map, let \(V \subseteq \mathit{Hyp}\) be a finite version space, let \(x \in X\) be an input, and let \(y \in \mathsf{Bool}\) be its true label. If the Halving prediction on \(x\) is wrong, that is \(\mathtt{predict}(\mathtt{eval}, V, x) \ne y\), then the updated version space contains at most half of the hypotheses:
For natural numbers \(a\) and \(b\) with \(b \gt 0\) and \(2b \le a\),
where \(\lfloor \log _2 \cdot \rfloor \) denotes the integer (floor) base-\(2\) logarithm.
\(\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.
Let \(\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}\) be an evaluation map, let \(V\) be a finite version space of hypotheses, and fix a target hypothesis \(\mathtt{target} \in V\) whose predictions supply the true label at each step. Then for every input sequence \(xs\), the total number of mistakes made by the Halving Algorithm — which predicts by majority vote over the current version space and, after each input, retains only those hypotheses that agreed with the observed label — satisfies
Let \(\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}\) assign a Boolean label to each input under each hypothesis, let \(H\) be a finite class of hypotheses, and fix a target hypothesis \(\mathtt{target} \in H\) that supplies the correct label \(\mathtt{eval}(\mathtt{target}, x)\) for every input \(x\). Then, on any finite sequence \(xs\) of inputs, the number of mistakes made by the Halving Algorithm run from the initial version space \(H\) is at most \(\lfloor \log _2 \left\lvert H\right\rvert \rfloor \):