Under Binary classification situation, error between function $f$ and basic learner(classifier) $h_i(x)$ is


It is assumed that $T$ basic classifiers are combined by a voting method, and if more than half of the basic classifiers get the correct answer, it is assumed that the ensemble classifier gives the correct answer. (Assume $T$ is odd integer for convenience.)

$$H(x) = \operatorname{sign}\left(\sum_{i=1}^T h_i(x)\right)$$

If the error rates of the basic classifier are assumed to be independent of each other, the error rate of the ensemble classifier can be known by the Hoeffding's inequality.

$$ P(H(x) ≠ f(x)) = \sum_{k=0}^{\lfloor T/2\rfloor} {}_T \mathrm{ C }_k (1-\mathcal{E})^k \mathcal{E}^{(T-k)} \le \exp\left(-\frac{1}{2}T(1-2\mathcal{E})^2\right).$$

I can't understand how the result(exponential part) is derived.

I think $\lfloor T/2\rfloor = \frac{(T-1)}{2}$ because $T$ is odd integer by the assumption above.

and given basic concept of the Hoeffding's inequality of binary classification is $$P(H(n) \le k) = \sum_{i=0}^{k} {}_n \mathrm{ C }_i \: p^i (1-p)^{(n-i)} \le \exp\left(-2\mathcal{E}^2n\right), \; (k=(p- \mathcal{E})n \; \textrm{and} \; \mathcal{E}>0).$$


1 Answer 1


Hoeffding's inequality is for a sum of independent variables $S_T = \sum_{i=1}^T X_i$ where $a_i \leq X_i \leq b_i$

$$P(S_T - E[S_T] \geq t) \leq \exp \left(- \frac{2t^2}{\sum_{i=1}^T (b_i - a_i)^2}\right).$$

  • You have a sum of (presumably) independent Bernoulli variables so $a_i = 0$ and $b_i$ = 1 and $\sum_{i=1}^T (b_i - a_i)^2 = T. $
  • $S_T = T-H_T$ is a binomial distributed variable with $E[S_T] = T(\mathcal{E})$
  • Instead of $H_T \leq \lfloor T/2 \rfloor = (T-1)/2$ we can look for the condition $T - S_T \leq (T-1)/2 $ or $S_T \geq (T+1)/2.$
  • If you use $t =(T+1)/2 - E[S_T]$ then the condition from Hoeffding's inequality $$S_T - E[S_T] \geq t$$ becomes $$S_T - E[S_T] \geq (T+1)/2 - E[S_T]$$ or $$S_T \geq (T+1)/2.$$

Filling in these values for $t$, $a_i$, $b_i$ gives

$$P\left(S_T \geq \frac{T-1}{2}\right) \leq \exp \left(-2 \frac{\left( \frac{T+1}{2} - T\mathcal{E}\right)^2}{T}\right) < \exp \left(-2 \frac{\left( \frac{T}{2} - T\mathcal{E}\right)^2}{T}\right) = \exp \left(-2 T\left( \frac{1}{2} - \mathcal{E}\right)^2\right).$$


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.