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 1


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$.


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.