1
$\begingroup$

I am trying to understand the mathematics behind SAMME AdaBoost:

At some stage, the paper adds a constraint for f to be estimable:

enter image description here

I do not understand why this is required. Can someone explain a bit better why this restriction is needed?

As well, would be possible to use a different constraint than the one added in the paper that would make f estimable?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Think for a while, if $f$ is not estimable, it can have any constant added to it with no difference on the result of the process.

This means that if no other constraints are imposed, $f$ is not well/uniquely defined and in fact represents a whole class of functionals. This obviously needs to be fixed and some natural constraint needs to be added (to uniquely fix $f$).

On the other hand, the additional constraint can also be seen as a free parameter of the process which nevertheless needs to be fixed somehow in a concrete instance of the process in order to take place.

In an analogy with physics, the algorithm is "gauge-invariant", but for any concrete physical problem to be solved some "gauge" needs to be chosen and fixed.

They choose to impose the symmetric constraint which reduces to the usual AdaBoost in the 2-class case.

One can impose another constraint on $f$ (than the symmetric one), choosing to satisfy other criteria if so desirable (as long as it can uniquely fix $f$).

For example, the general non-symmetric constraint is also valid: $$f_1 + \dots + f_K = c$$

for arbitrary constant $c$. This also fixes $f$ uniquely and it can introduce bias favoring certain classes over others (eg for an imbalanced problem). Additionaly, unless $c=0$, does not reduce to the (symmetric) AdaBoost in 2-classes case (which may or may not be desirable).

Improve this answer
$\endgroup$
2
  • $\begingroup$ This was a very clear answer. Thank you so much. I am just wondering, if I understood well, the outputs for the multiclass case are recoded in such a way that f_k will be 1 if k=c and -1/(K-1) otherwise. Therefore, the sum of them should be always equal to zero. Should this recoding change in case that a non-symmetric constrain is use? $\endgroup$
    – Aggamarcel
    Commented Aug 1, 2020 at 10:00
  • $\begingroup$ @Aggamarcel, in general yes this will change if another constraint is imposed $\endgroup$
    – Nikos M.
    Commented Aug 1, 2020 at 13:39

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.