When is Gradient Descent invoked on the objective function while running XGboost?

Question

is it at the end of every tree? or only after all trees are build? I tried to think in both ways but didn't get a clear picture.

Can we focus more the part "the loss function is applied between training models" I am trying to understand how is Gradient Descent is applied to minimize the objective function function.

slide no 36 in http://www.saedsayad.com/docs/xgboost.pdf

Data points reach to a leaf will be assigned a weight. The weight is the prediction

how is the weight assigned ? how is the weight calculated ? why predict the weight again ? Can someone shed some light on this?

Answer 1

Clearing the confusion of gradient descent in XgBoost

Gradient descent is NOT used in Xgboost. If you look at the generalized loss function of XgBoost, it has 2 parameters pertaining to the structure of the next best tree (weak learner) that we want to add to the model: leaf scores and number of leaves. Gradient descent cannot be used to learn them. The other variables in the loss function are gradients at the leaves (think residuals). This is why the algorithm is called gradient boosting. It has nothing to do with gradient descent.

So how do we learn in XgBoost and when is gradient boosting invoked during the algorithm?

Ideally, we need the loss function to find the next best tree (weak learner) that brings the maximum reduction in loss. So if you take the derivative of the loss function to find its minima, you will get the following scoring function to find the best tree-

Iterate overall all possible trees and the tree with the lowest score is our next best tree. BUT it is not practical to scan through all the possible trees.

So, the loss function is modified further to find the next best split and now you can call it the gain. The equation is as follows- Here, gamma is the cost of adding an additional leaf, lambda is the L2 regularization parameter, G and H are derivate and second-derivative of loss, respectively.

Now that we have the equation to calculate gain for each split, find the best split using this equation and ta-daa! That's gradient boosting :)

To understand this in details, read this.

Answer 2

I thought of throwing some historical perspective into this...

The initial algorithm is called AdaBoost. Unlike most of machine learning, this algorithm has its genesis in hard theory. The authors were trying to answer the following theoretical question:

Is it possible somehow to combine weak models and create a very accurate predictor?

Weak models are models that are hardly better than chance. Think about this question. It is quite a philosophical question... And, as it happens, it can be answered by hard mathematics.

They actually demonstrated that yes. Their paper is actually worth reading. They have since published a lot of interesting papers from different perspectives, for instance using game theory.

The AdaBoost algorithm is also very simple and worth checking because it is the basis of xgboost.

AdaBoost works with any model. The only restriction is that the model supports giving weights to each observation. This is because it trains models sequentially by increasing (or decreasing) the weight associated to each observation to make that observation more important (or less important).

The cool thing is that the algorithm is very unlikely to overfit. But notice that this is an empirical claim, not a theoretical one. The algorithm can overfit, but it has been found (empirically) to be very resilient.

This algorithm has been expanded into Gradient Boosting, which has more flexible loss functions. This algorithm is an AdaBoost adaption by the same guy that invented random forests. They are not concerned about theoretical questions like the authors of AdaBoost, they just want to make the algorithm more flexible and efficient. For instance, they also update the weights using all previous weak models, not just the last trained model.

xgboost is just an intelligent implementation of Gradient Boosting. You can see the basic algorithm in wikipedia. Each decision tree is trained sequentially and weights are computed based on the errors from the current ensemble.

I can hear you say:

What? xgboost trains trees in sequence? How is xgboost so fast then?

This website explains it very well. While trees are trained sequentially, each individual decision tree is trained in parallel by using highly creative techniques. Most importantly, nodes in the same depth do not depend in each other, so you can paralelize them.

Long story short: the loss function is applied between training models.

When it comes to making predictions, then the entire ensemble can be used in parallel.