4
$\begingroup$

Referring to the algorithm on page 11 in this paper on boosting algorithms, I really don't understand step 2, (ii) and (iii).

What does this mean:

(ii) Fit the regression function $g_j^h (x)$ by weighted least-squares of the working response $z_{ij}$ to $x_i$ with weights $w_{ij}$ on the training data.

(iii) Set $g_j(x) \leftarrow g_j(x) + g_j^h (x)$

For convenience, I'm pasting the algorithm here:

gentleboost.c

I do understand the theory and general concept of least squares regression. I understand we have data whose graph doesn't have a clear line or curve formula, and so we try to come up with a function that'll help us predict a response given an input. Using "least-squares" means coming up with a formula whose parameters are such that the square of the errors of the prediction is minimized.

But once this regression function is "fitted" to data, how is it "added" to other functions like itself?

I'm having a hard time understanding the application of the above quoted statement. Not just in this algorithm, but in others, wherever they mention "fitting" a regression function and then using that function with others. At best I understand using regression functions to actually predict values as output. But how do we use them to predict/generate more functions?

Could someone please explain this simply, maybe using arrays of data or something?

$\endgroup$
3
$\begingroup$

You have to notice that you not use in this algorithm the "least-squares", but "weighted least squares". See Wikipedia page dedicated to this matter.

The main distinction is that instead of the usual: $$LSE(y, \hat{y}) = E[(y - \hat{y})^2] = E[(y-\hat{f}(x, \beta))^2]$$ you have an additional factor $$WLSE(y, \hat{y}) = E[(y - w\hat{y})^2] = E[(y-w \hat{f}(x,\beta))^2]$$ where $w$ comes from weights. In the standard weighted least squares, weights have some properties, to be able to get a BLUE estimator. In your case the weights are the current weights computed at step $(i)$.

Now you have also to note that at step $(b)$ the predictor for the current step $g_j(x)$ is altered by adding previously fitted predictors. Note that the formula from the $(b)$ step can be decomposed as a linear combination of other functions. Which means it has the form:

$$g(x) = \beta_0 + \beta_1f_1(x) + \beta_2f_2(x) .. + \beta_pf_p(x)$$

where $\beta_i$ are constant factors, and $f_i$are functions of input variables.

Thus, in the end, the final computed $g_j(x)$ will be a linear combination of the fitted function at step $j$ and all other previously fitted predictors.

This qualifies the final $g_j(x)$ to be an additive model since an generalized additive model is a linear combination of other predictors.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. Just to be absolutely sure I'm on the right track, just want to make a few clarifications: (1) y = true response, (2) y^= predicted response from our regression function f(x,β), (3) E[...] = expectation/mean (4) and let's say that the first iteration, our regression function is g1(x) = 3x + 4, and in the second iteration, it's g2(x) = 5x -1, then at the end of the second iteration, we'll have g(x) = 8x + 3. Have I got it all right? $\endgroup$ – user961627 Apr 14 '14 at 14:14
  • 1
    $\begingroup$ 1. If m=2, than for your case you have $g_2=\frac{m-1}{m}[g_2-\frac{1}{m}\sum_{i=1}^{m}g_i]=\frac{1}{2}[5x-1 - \frac{1}{2}(5x-1+3x+4)] = \frac{1}{2}[5x-1-\frac{1}{2}(8x+3)]=\frac{1}{4}[2x-7]$1. 2. I made a mistake, instead of $\hat{f}(x,\beta)$ I typed without hat. I will correct that. Agree with all the other things. $\endgroup$ – rapaio Apr 14 '14 at 14:31
  • 1
    $\begingroup$ At step $(a)$ are fit $m$ prediction vectors, one for each target class. At step $(b)$ the prediction vectors are smoothed, so that each prediction vector will take into account what the others prediction vectors "have to say about that". This is why is called "gentle", the changes are not aggressive. Now, you need one $\beta$ for each class. The formula for $\beta$ "incorporates" also knowledge about which is the target value. In fact if you notice, both formulas are the same, since if $j=c_j$ the $g_j(x_i)-g_{c_j}(x_i)=0$. $\endgroup$ – rapaio Apr 14 '14 at 15:54
  • 1
    $\begingroup$ the answer is yes (to your last question) $\endgroup$ – rapaio Apr 23 '14 at 14:44
  • 1
    $\begingroup$ No, the regression will be performed on the whole data set, with current weights and regress on current residual $z$, then you compute the fit values, which are the prediction of the model on the data $\endgroup$ – rapaio Apr 28 '14 at 23: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.