4
$\begingroup$

I am reading the chapter 10 of "The Elements of Statistical Learning 2nd ed, (ESLII)", where the Adaboost algorithm is explained by minimizing the exponential loss using stagewise additive modelling approach. That is at the $m$th iteration, we fit a classifier $h\in\{-1,+1\}$ such that the following weighted classification error is minimized:

$h_m=\arg\min_h\sum_{i=1}^N w_i^m I(y_i\neq h(x_i))$, (1)

where $I(\cdot)$ is the indicator function, and $w_i^m=\exp(-y_if_{m-1}(x_i))$

I am wondering if the AdaBoost algorithm can be explained by the framework of gradient boosting, i.e., repeatedly fitting the negative gradient of exponential loss. At the beginning, I thought it was obvious. But when I derive the algorithm it seems that it is not the case.

Given the exponential loss $\ell(f(x),y)=\exp(-yf(x))$, the negative gradient is $r=y\exp(-yf(x))$. Therefore, at the $m$th iteration, we need to perform least square fit: $h_m=\arg\min_h\sum_{i=1}^N(h(x_i)-y_i\exp(-y_if(x_i)))^2|_{f=f_{m-1}}$ (2).

I cannot verify the equivalence between Eq. 1 and Eq. 2. Actually, I doubt the if these two problems are the same.

$\endgroup$
2
$\begingroup$

I think I've found an explanation for this question. We can expand the function:

$\ell(h(x),y)=(h(x)-y\exp(-yf(x)))^2=h^2(x)+(y\exp(-yf(x)))^2-2h(x)y\exp(-yf(x))$.

Since we focus on classification problem here, we have $y\in\{-1,+1\}$ and $h(x)\in\{-1,+1\}$. Therefore, only the last term $-2h(x)y\exp(-yf(x))$ matters. Let $w=\exp(-yf(x))$, then we can see that Eq. 1 and Eq. 2. are equivalent.

$\endgroup$
  • $\begingroup$ I am stuck with the same problem and I think there is some weirdness in your answer: you take l(y~, y) = (y~-y)^2 but you put in the residuals (I.e. the derivatives of the outer loss function at the last step) as y [so far so good as those are values in the whole real numbers] but h(x) as y~ which takes values +-1. So if you find a really good h, who tells you that this square loss equation will be small? If you compare +-1 values to +-1 values and they are the same often then the loss is small. This does not happen in your case as you compare apples with bananas... $\endgroup$ – Fabian Werner Dec 26 '16 at 12:29

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.