<p>Suppose that the output of <span class="math-container">$h,c$</span> is either <span class="math-container">$+1$</span> or <span class="math-container">$-1$</span>.  Then <span class="math-container">$h(x)c(x)=1$</span> iff <span class="math-container">$h(x)=c(x)$</span>.  Moreover, if we let <span class="math-container">$p=\Pr[h(x)=c(x)]$</span>, then</p>
<p><span class="math-container">$$\begin{align*}
\mathbb{E}[h(x)c(x)] &amp;= 1 \cdot \Pr[h(x)=c(x)] + (-1) \cdot \Pr[h(x)\ne c(x)]\\
 &amp;= p - (1-p) = 2p-1.
\end{align*}$$</span></p>
<p>Now, <span class="math-container">$\Pr[h(x)\ne c(x)] \le \frac12 - \gamma$</span> is equivalent to <span class="math-container">$p \ge \frac12 + \gamma$</span>, which in turn is equivalent to <span class="math-container">$\mathbb{E}[h(x)c(x)] \ge 2 \cdot (\frac12 + \gamma) -1 = 2\gamma$</span>.  So, the two conditions are equivalent, up to a factor of two in <span class="math-container">$\gamma$</span>.</p>

CC BY-SA 4.0
2022-12-05T06:37:20.057Z
2022-12-05T06:37:20.057Z
D.W.
<p>I've been reading about boosting and have come across basically two definitions of a weak learner. Basically for hypothesis <span class="math-container">$h$</span> and target <span class="math-container">$c$</span>, some definitions says that <span class="math-container">$h$</span> is a weak learner if <span class="math-container">$E[h(x)c(x)] \geq \gamma$</span> while others says that it is a weak learner if <span class="math-container">$Pr[h(x) \neq c(x)] \leq \frac{1}{2} - \gamma$</span>. 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!</p>

<machine-learning><pac-learning>
Differing definitions of a weak learner
qc6518
# Differing definitions of a weak learner

(Asked by: username_0 on 2022-12-05)

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!

**Tags:** machine-learning, pac-learning

---

## 1 answers

### Answer by username_1 on 2022-12-05. Score: 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$.


---

