9
$\begingroup$

I know how to implement linear objective function and linear boosts in XGBoost. My concrete question is: when the algorithm it fits the residual (or the negative gradient) is it using one feature at each step (i.e. univariate model) or all features (multivariate model)?

Any reference to documentation about the linear boosts in XGBoost will be appreciated.

EDIT: Linear boosts can be implemented in XGBoost by setting the 'booster' parameter to 'gblinear'. See: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3885826/ for useful information on linear boosting. Note that I am not speaking about the objective function (which can be also linear) but about the boosts themselve.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ I don't know how it's implemented but I see no reason why it should consider only one feature at a time $\endgroup$ – Alexey Grigorev Aug 20 '16 at 16:16
  • $\begingroup$ @AlexeyGrigorev most probably it takes many features at a time, but then, how are these features selected? Any document on the specific process for linear boosting would be very clarifying. $\endgroup$ – Escachator Aug 20 '16 at 21:00
12
+25
$\begingroup$

Short answer to you question:

when the algorithm it fits the residual (or the negative gradient) is it using one feature at each step (i.e. univariate model) or all features (multivariate model)?

The algorithm is using one features or all features depends on your set up. In my long answer listed below, in both decision stump and linear learner examples, they uses all features, but if you want, you can also fit a subset of features. Sampling columns (features) are viewed as reducing the variance of the model or increasing the "robustness" of the model, especially if you have large number of features.

In xgboost, for tree base learner, you can set colsample_bytree to sample features to fit in each iteration. For linear base learner, there are not such options, so, it should be fitting all features. In addition, not too many people use linear learner in xgboost or gradient boosting in general.


Long answer for linear as weak learner for boosting:

In most cases, we may not use linear learner as a base learner. The reason is simple: adding multiple linear models together will still be a linear model.

In boosting our model is a sum of base learners:

$$ f(x)=\sum_{m=1}^M b_m(x) $$

where $M$ is number of iterations in boosting, $b_m$ is the model for $m^{th}$ iteration.

If the base learner is linear, for example, suppose we just run $2$ iterations, and $b_1=\beta_0+ \beta_1x$ and $b_2=\theta_0+ \theta_1x$, then

$$ f(x)=\sum_{m=1}^2 b_m(x)=\beta_0+ \beta_1x+\theta_0+ \theta_1x=(\beta_0+\theta_0)+ (\beta_1+ \theta_1)x $$

which is a simple linear model! In other words, the ensemble model have the "same power" with the base learner!

More importantly, if we use linear model as base learner, we can just do it one step by solving the linear system $ X^T X \beta = X^T y $ instead of go though multiple iterations in boosting.


Therefore, people would like to use other models than linear model as base learner. Tree is a good option, since adding two trees is not equal to one tree. I will demo it with a simple case: decision stump, which is a tree with 1 split only.

I am doing a function fitting, where the data is generated by a simple quadratic function, $f(x,y)=x^2+y^2$. Here is the filled contour ground truth (left) and final decision stump boosting fitting (right).

enter image description here

Now, check the first four iterations.

enter image description here

Note, different from linear learner, the model in 4th iteration cannot be achieved by one iteration (one single decision stump) with other parameters.


So far, I explained, why people are not using linear learner as base learner. However, nothing prevent people to do that. If we use linear model as base learner, and restrict number of iterations, it is equal to solving a linear system, but limit the number of the iterations during the solving process.

The same example, but in 3d plot, the red curve are the data, and the green plane is the final fit. You can easily see, final model is a linear model, and it is z=mean(data$label) which is parallel to x,y plane. (You can think why? this is because our data is "symmetric", so any tilt of the plane will increase the loss). Now, check out what happened in first 4 iterations: the fitted model is slowly going up to the optimal value (mean).

enter image description here


Final conclusion, linear learner is not widely used, but nothing prevent people to use it or implement it in a R library. In addition, you can use it and limit number of iterations to regularize the model.

Related post:

Gradient Boosting for Linear Regression - why does it not work?

Is a decision stump a linear model?

$\endgroup$
  • 1
    $\begingroup$ I would say that combination of n trees is a tree, no matters how big is n! $\endgroup$ – Metariat Mar 9 '17 at 18:51
  • $\begingroup$ @Metariat NO!, combination trees is NOT a tree!. for tree, you will see "T" shape on split. But boosted stump you will see "#" shape. i.e., the split will cross other splits! $\endgroup$ – hxd1011 Mar 9 '17 at 18:53
  • $\begingroup$ Can you give an example of n trees? I will give you an equivalent tree! $\endgroup$ – Metariat Mar 9 '17 at 18:55
  • $\begingroup$ @Metariat sorry i do not have time for now. But i am sure boosting on decision stump cannot easily generated by a decision tree. Will come back to this question when I got time. $\endgroup$ – hxd1011 Mar 9 '17 at 19:21
  • 1
    $\begingroup$ I agree that that combination of n trees is still a tree, but this tree will be significantly bigger. In worst case number of leaves is equal to product of number of leaves in all input trees, so the complexity of such tree is impractical. On the other hand in case of linear functions complexity is exactly the same. $\endgroup$ – Tomek Tarczynski May 11 '17 at 9:22

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.