1
$\begingroup$

I've read and think I got a good grasp of the math behind AdaBoost, but I wasn't able to understand why AdaBoost requires a weak base-classifier?

Specifically, I'm dealing with AdaBoost using decision-tree as base-classifier. So, what if my DT wasn't "weak"? So instead of using a stump (DT with depth of 1), what should happen with AdaBoost if I used deeper tree for example?

I found this, but I'm not it fully answers my question

$\endgroup$
1
  • $\begingroup$ Where are you seeing that a weak base-classifier is required? $\endgroup$ Jun 9, 2020 at 1:51

1 Answer 1

2
$\begingroup$

Practically, I'm unsure why one would need to rely on AdaBoost if we already had a strong classifier. Tl;dr: I don't believe that having a weak learner is requirement for AdaBoost to work.

I can try to walk through some of the analysis. We'll deal with empirical error, and then generalization error.

Empirical Error (train)

We define a weak learner as any classifier with error rate $\frac{1}{2} - \gamma$ for $\gamma \in (0, \frac{1}{2})$. In the case you're worried about, $\gamma$ is close to $\frac{1}{2}$.

Let $J(\theta^{(i)})$ be the error of AdaBoost after $i$ rounds; we can prove the following rate-of-convergence result:

$$J(\theta^{(i+1)}) \leq \sqrt{1 - 4\gamma^2} J(\theta^{(i)})$$.

This is proven by Duchi here. So if we denote $\gamma$ for the weak learner after round $i$ as $\gamma_i$, we can write $$J(\theta^{(T)}) \leq \prod_{t=1}^T \sqrt{1 - 4\gamma_t^2} \leq exp\left(-2 \sum_{t=1}^T \gamma_t^2\right) \leq exp\left(-2\gamma^2T\right)$$ for $\gamma = \underset{t}{\min}\gamma_t$. So, basically, the empirical error vanishes exponentially. Note that this occurs regardless of $\gamma$; it simply trades off with $T$, so we don't necessarily need a particular type of weak learner, just any classifier with better-than-random error rate.

Generalization Error (test)

Dealing with generalization error is a little bit past my mathematical abilities. But, using basic statistical learning theory, it's a result from Vapnik (1971) that $$\varepsilon(h) \leq \hat{\varepsilon}(h) + O\left(\frac{1}{\sqrt{m}}\sqrt{d\log\frac{m}{d} + \log\frac{1}{\delta}}\right)$$ for classifiers under the empirical risk minimization (ERM) learning framework with high probability ($1-\delta$). Note $d = VC(\mathcal{H})$, the VC-dimension of the hypothesis class of $H$. We can treat AdaBoost this way since it is a classifier that tries to minimize some empirical risk (i.e. training loss) on a training dataset (this is hand-wavey, but the definition of ERM isn't the point here). I believe the notes here build on these principles and show a similar bound on the generalization error of Adaboost, that is;

$$\varepsilon(h) \leq \hat{\varepsilon}(h) + O\left(\frac{1}{\sqrt{m}}\sqrt{\frac{\log m\log|\mathcal{H}|}{\theta^2} + \log\frac{1}{\delta}}\right)$$

where they treat Adaboost as a max-margin classifier with margin $\theta$; unfortunately, I don't think I'll be much help in elucidating this particular formula. Note, however, that there is no dependence on $\gamma$ here except in the first $\hat{\varepsilon}(h)$ term, which vanishes regardless of $\gamma$ as $T \to \infty$. So a particular type of weak learner is again unnecessary -- we just need a better-than-random learner.

$\endgroup$
2
  • 2
    $\begingroup$ I agree. The interesting thing about AdaBoost is that it works even with weak learners, which is not a trivial fact (though I think it's less interesting a fact than I did when I first saw it) $\endgroup$ Jun 9, 2020 at 3:10
  • $\begingroup$ Thanks a lot - this really cleared this up for me. Everywhere I read about AdaBoost it started out with weak-classifiers, but I wasn't sure this is an actual requirement for the algorithm. As you showed, it isn't really. I'll chew some more on the math - thanks! $\endgroup$
    – Ruslan
    Jun 9, 2020 at 6:31

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.