2
$\begingroup$

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 enter image description here 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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks for the explanation @Yuval. My follow up question is how is the algorithm using the prediction to prune the version space? $\endgroup$
    – Naren
    Jan 12, 2022 at 14:58
  • $\begingroup$ The last line prunes away all hypotheses which do not correspond to the true label. $\endgroup$ Jan 12, 2022 at 14:59
  • $\begingroup$ 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\}$$ ? $\endgroup$
    – Naren
    Jan 12, 2022 at 15:02
  • 1
    $\begingroup$ No, that would be a wrong description. What if $p_t \neq y_t$? You will be left with no hypotheses! $\endgroup$ Jan 12, 2022 at 15:02
  • $\begingroup$ 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. $\endgroup$
    – Naren
    Jan 12, 2022 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.