0
$\begingroup$

Question about step 2(c) in the algorithm: what is the range on $\alpha_m$? Since $err_m$ is strictly positive, $\alpha_m$ ranges from $-\infty$ to $\infty$, correct? $\alpha_m = 0$ when $err_m = 0.5$.

I see $\alpha_m$ as the amount of contribution the weak classifier $G_m$ has on the final classifier, so is it possible to have negative contribution? i.e. negative $\alpha_m$?

If $err_m$ is strictly less than $0.5$, then $\alpha_m$ is strictly positive. However, how do we know that we can always find a $G_m$ with error $err_m$ that is strictly less than $0.5$?

$\endgroup$
1
  • $\begingroup$ Yes, $\alpha_m$ can range from $-\infty$ to $\infty$. If the error of the weak classifier is greater than $\frac{1}{2}$, then $\alpha_m$ is negative. If the hypothesis class satisfies the weak learning condition, then it is easy to see that $\alpha_m$ is always positive. If the condition is not satisfied, $\alpha_m$ can be negative. However, there is no easy way to verify the weak learning condition in practice. Irrespective of whether the weak learning condition is satisfied, AdaBoost has some nice properties. It can return the ``best'' possible classifier in the span of weak classifiers $\endgroup$ – v1105 Aug 3 '20 at 4:21
1
$\begingroup$

Your math is correct, and there's nothing unsound about the idea of a negative alpha. In the binary classification problem, if you have a learner with an error $\mathrm{err}_m > 0.5$, then by inverting every decision it makes you get a new learner with an error of $1 - \mathrm{err}_m < 0.5$, which is clearly an improvement. This function does exactly that; if a learner had an error of 0.9, it would invert it, transforming it into a learner with an error of 0.1, and weight its contribution exactly the same as a learner with an error of 0.1.

In practice, this isn't very likely. It's hard for any procedure that tries to minimize error to produce a learner that performs worse than random chance by any significant margin. But, in case it does, the algorithm will still make the best use of the information provided, by assigning a negative alpha.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.