# Understanding halving algorithm in online learning

I am working through "Understanding Machine Learning Theory" by Shai Shalev-Schwartz. In the chapter "Online learning" I came across the halving algorithm, the author uses the following algorithmic pseudo-code for the algorithm I am having difficulty understanding authors intention from the highlighted portion. Here $$\mathcal{H}$$ is the hypothesis class, $$V_{t}$$ is the version space at iteration t, $$(x_t,y_t)\in S$$ are samples from the set provided by the oracle. We also assume that $$h^{*}\in\mathcal{H}$$ (realizability).

Attempt: My guess is the prediction is based on majority vote from hypotheses in version space, but I don't see where he is pruning the version space using the majority vote? What am I missing? Any help would be appreciated!

The prediction is the value of $$r$$ which maximizes the quantity $$| \{ h \in V_t : h (\mathbf{x}_t) = r \} |.$$ This is the number of surviving hypotheses (belonging to $$V_t$$) which predict $$r$$ on the current point ($$\mathbf{x}_t$$). Equivalently, we ask all hypotheses in $$V_t$$ for their opinion on $$\mathbf{x}_t$$. If more answer $$0$$, we predict $$0$$. If more answer $$1$$, we predict $$1$$. In case of a tie, we (arbitrarily) predict $$1$$. In other words, we take majority vote on the opinions of the hypotheses in $$V_t$$ on $$\mathbf{x}_t$$.
After seeing the true label, we throw out all hypothesis which were wrong; this is the meaning of the update line, which sets $$V_{t+1}$$ to contain all hypotheses $$h$$ in $$V_t$$ such that $$h(\mathbf{x}_t) = y_t$$, where $$y_t$$ is the true label of $$\mathbf{x}_t$$.
Each time the algorithm is wrong, at least half of the hypotheses in $$V_t$$ were wrong, so $$V_{t+1}$$ is at least twice as small as $$V_t$$. So after $$\log_2 |\mathcal{H}|$$ wrong answers, we are left with a single hypothesis, which must be the true one. This is why this algorithm makes at most $$\log_2 |\mathcal{H}|$$ mistakes.
• In that case wouldn't a more accurate mathematical representation be $$V_{t+1} = \{h\in V_t: h(x_t)=p_t \wedge h(x_t)=y_t\}$$ ? Commented Jan 12, 2022 at 15:02
• No, that would be a wrong description. What if $p_t \neq y_t$? You will be left with no hypotheses! Commented Jan 12, 2022 at 15:02
• I think I understand. I was not thinking about what constitutes a mistake, $p_t \neq y_t$ so for every mistake atleast half the hypothesis are pruned which gives better bound on mistakes after some iterations than choosing a random hypothesis from version space. Commented Jan 12, 2022 at 15:37