I'm trying to solve the following problem but I've gotten sort of stuck.

So for adaboost, $err_t = \frac{\sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) \neq t^{(i)})}{\sum_{i=1}^{N}w_i}$

and $\alpha_t = \frac{1}{2}ln(\frac{1-err_t}{err_t})$

Weights for the next iteration are $w_i' = w_i exp(-\alpha_t t^{(i)} h_t(x^{(i)}))$ and this assumes $t$ and $h_t$ takes on a value of either $-1$ or $+1$.

I have to show that the error with respect to the new weights $w_i'$ is $\frac{1}{2}$. i.e., $err_t' = \frac{\sum_{i=1}^{N}w_i' \Pi (h_t(x^{(i)}) \neq t^{(i)})}{\sum_{i=1}^{N}w_i'} = \frac{1}{2}$

i.e., we use the weak learner of iteration t and evaluate it according to the new weights, which will be used to learn the $t+1$-st weak learner.

I simplified it so that $w_i'=w_i \sqrt{\frac{err_t}{1-err_t}}$ if $w_i$ was correctly classified and $w_i'=w_i \sqrt{\frac{1-err_t}{err_t}}$ if $w_i$ was incorrectly classified. I then tried plugging this into the equation for $err_t'=\frac{1}{2}$ and got $\frac{err_t}{1-err_t} \frac{\sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) = t^{(i)})}{\sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) \neq t^{(i)})} = 1$ but at this point I sort of ran into a dead end and so I'm wondering how one might show the original question.

Thanks for any help!


You're nearly there. The quantity $err_t/(1-err_t)$ is exactly what you need it to be. It might be easier to see if you think about $$\sum_{i=1}^N w_i \Pi(h_t(x^{(i)})=t^{(i)})$$ as $$\sum_{i:\ x^{(i)}\text{ is correctly classified}} w_i$$ (just using the indicator function to reduce the summation range).


For simplicity, lets define some variables as follows:

$W_C := \sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) = t^{(i)})$

$W_I := \sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) \neq t^{(i)})$

Therefore, $err_t = W_I/(W_C+W_I)$

$a := \sqrt{\frac{err_t}{1-err_t}} = \sqrt{\frac{W_I}{W_C}}$

Now, for new weights we have

$W'_C := \sum_{i=1}^{N}w'_i \Pi (h_t(x^{(i)}) = t^{(i)}) = aW_C$

$W'_I := \sum_{i=1}^{N}w'_i \Pi (h_t(x^{(i)}) \neq t^{(i)}) = (1/a)W_I$

Now, as the final step:

$err'_t = \frac{W'_I}{W'_I + W'_C} = \frac{(1/a)W_I}{(1/a)W_I + aW_C} \overset{\times a}{=} \frac{W_I}{W_I + a^2W_C} = \frac{W_I}{W_I + \frac{W_I}{W_C}W_C}=\frac{1}{2}$


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.