# How to prove error of ensemble model by using the Hoeffding's inequality?

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

$$P(h_i(x)≠f(x))=\mathcal{E}.$$

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

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