Both of them produce the same decision for the classification of the cases. The difference is in the absolute value of the chances, or in the AdaBoost terms, the margin (with the classic AdaBoost also applying the logarithm on top).

I still think that using the value without the square root has the more correct "physical meaning". But either can be used with the same result.

Following the classic AdaBoost, the version of the confidence with the square root follows from the expression

Z = sum for all good cases i (Wi / S) + sum for all bad cases j (Wj * S)

Z = sum for all good cases i (Wi * (C-1) / C) + sum for all bad cases j (Wj * C / (C-1))

Just like the last post, W is the weight of a particular training case, same as D(i) in the classic AdaBoost terms, just since I've been using weights rather than a distribution, the letter W comes easier to my mind.

The "physical meaning" here is that the weights of the training cases for the next round of boosting are adjusted opposite to how the chances of these training cases get affected by this round during the final computation. If a training case gets predicted correctly by a partial hypothesis, its weight will get multiplied by C and the weight of the other cases will be multiplied by (1-C), so the changes will get multiplied by C/(1-C), and for the next round of boosting the good cases get divided by that to compensate. For the cases that get predicted incorrectly, the opposite happens.

This translates to

C / (1-C) = S = sqrt((1-e) / e) = sqrt(1-e) / sqrt(e)

The last expression does NOT mean

C = sqrt(1-e)

Instead, it means

C = sqrt(1-e) / (sqrt(1-e) + sqrt(e))

Alternatively, the approach without the square root starts with the premise

Z = sum for all good cases i (Wi / C) + sum for all bad cases j (Wj / (1-C))

The "physical meaning" is as described before, the weights of the training cases for the next round of boosting are adjusted opposite to how the weights of these training cases get affected by this round during the final computation. It seems to me that compensating the weights for the changes in weights is the more correct "physical meaning" than compensating the weights for the changes in chances.

This translates to

C / (1-C) = S

^{2}= sqrt( (1-e) / e )

^{2}= (1-e) / e

and

C = (1-e)

By the way, chasing this version through the derivatives as shown in the previous post was interesting. I've appreciated why the authors of AdaBoost involved the exponents into the formulas: doing the derivatives and integrals with the exponents is much easier than without them. Then I've realized that with the derivatives where S = exp(Alpha) I'm computing dZ/dAlpha, not dZ/dC. And that is the correct approach. So without the exponents I should be computing the dZ/dS, and that gets easy again.

So, the

*real*version of AdaBoost described in the third part is this:

Given: (x

_{1}, y

_{1}), ..., (x

_{m}, y

_{m}) where x

_{i}belongs to X, y

_{i}belongs to {-1, +1}.

Initialize: D

_{1}(i) = 1 for i = 1, ..., m.

For t = 1, ..., T:

- Train the basic algorithm using the weights D
_{t}. - Get weak hypothesis h
_{t}: X -> {-1, +1}. - Aim: select h
_{t}to minimalize the boundary on the training error Z_{t}where:

Wgood_{t}= 0; Wbad_{t}= 0;

for i = 1, ..., m {

if h_{t}(x_{i}) = y_{i}{

Wgood_{t}+= D_{t}(i)

} else {

Wbad_{t}+= D_{t}(i)

}

}

C_{t}= Wgood_{t}/ (Wgood_{t}+ Wbad_{t})

Z_{t}= Wgood_{t}/C_{t}+ Wbad_{t}/(1-C_{t})

which can also be represented symmetrically through S_{t}:

Z_{t}= Wgood_{t}/S_{t}+ Wbad_{t}*S_{t}

S_{t}= sqrt(C_{t}/ (1-C_{t})) = sqrt(Wgood_{t}/ Wbad_{t})

and substituting S_{t}:

Z_{t}= Wgood_{t}/ sqrt(Wgood_{t}/ Wbad_{t}) + Wbad_{t}* sqrt(Wgood_{t}/ Wbad_{t})

= 2 * sqrt(Wgood_{t}* Wbad_{t})

Which gets minimalized when either of Wgood_{t}or Wbad_{t}gets minimalized, but to be definitive we prefer to minimalize Wbad_{t}.

- Update,

for i = 1, ..., m {

if h_{t}(x_{i}) != y_{i}; {

D_{t+1}(i) = D_{t}(i) / (1-C_{t})

} else {

D_{t+1}(i) = D_{t}(i) / C_{t}

}

}

H(x) {

chance = 1;

for t=1,...,T {

if (h

_{t}(x) > 0) {

chance *= C

_{t}/(1-C

_{t});

} else

chance *= (1-C

_{t})/C

_{t};

}

}

return sign(chance - 1)

}

Having this sorted out, I can move on to more creative versions of the algorithm where on a step of boosting the different training cases may get stamped with the different confidence values C.

## No comments:

## Post a Comment