Data Science Asked by Saad Hussain on October 1, 2021
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).
Answered by Ben Reiniger on October 1, 2021
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}$
Answered by Esmailian on October 1, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP