I've been reading about boosting and have come across basically two definitions of a weak learner. Basically for hypothesis $h$ and target $c$, some definitions says that $h$ is a weak learner if $E[h(x)c(x)] \geq \gamma$ while others says that it is a weak learner if $Pr[h(x) \neq c(x)] \leq \frac{1}{2} - \gamma$. I don't really understand how these two definitions are related, are we made to make assumptions about the weights that the hypothesis function puts on the points in order to calculate expectation from probability? Thanks!
1 Answer
$\begingroup$
$\endgroup$
Suppose that the output of $h,c$ is either $+1$ or $-1$. Then $h(x)c(x)=1$ iff $h(x)=c(x)$. Moreover, if we let $p=\Pr[h(x)=c(x)]$, then
$$\begin{align*} \mathbb{E}[h(x)c(x)] &= 1 \cdot \Pr[h(x)=c(x)] + (-1) \cdot \Pr[h(x)\ne c(x)]\\ &= p - (1-p) = 2p-1. \end{align*}$$
Now, $\Pr[h(x)\ne c(x)] \le \frac12 - \gamma$ is equivalent to $p \ge \frac12 + \gamma$, which in turn is equivalent to $\mathbb{E}[h(x)c(x)] \ge 2 \cdot (\frac12 + \gamma) -1 = 2\gamma$. So, the two conditions are equivalent, up to a factor of two in $\gamma$.
