3
$\begingroup$

According to the explanation in Complete Guide to Parameter Tuning in XGBoost, XGBoost doesn't use max_depth argument as Random Forest or GBM does. It expands the tree up to this depth and start pruning all the way up by judging if each node has a positive gain or not. But how does it split the nodes? Is it again greedy? And, if it is greedy, is it possible to have a first split yielding negative gain, and then positive gain?

$\endgroup$
  • 1
    $\begingroup$ How is this off-topic? It clearly ask on how a widely used boosting algorithm populates its tree learners. (+1 for the question) $\endgroup$ – usεr11852 Apr 7 '19 at 17:37
  • 1
    $\begingroup$ @usεr11852 thanks for the comment. Also, I'd be happy to revise my question if any of the voters who voted as "off-topic" comments on why they think so, because I just tried to ask how a hyper parameter of XGBoost works, which I believe very well suits this forum. $\endgroup$ – cross-entropy Apr 7 '19 at 19:26
  • $\begingroup$ @usεr11852 - it's about the implementation of an algorithm in a specific piece of code, so is really more of a programming question. Other GBM implementations, e.g., LightGBM, do some of their things differently. Also - note that the documentation link is over three years old! XGBoost, which I am very familiar with, has changed quite a bit over the last three years. Try xgboost.readthedocs.io/en/latest instead for your future work! (I did not vote to close, but I did think for some time about it.) $\endgroup$ – jbowman Apr 12 '19 at 21:47
  • $\begingroup$ @jbowman: Apologies but I cannot see the point you are trying to make. If anything exactly because other variants of gradient boosting "do their things differently", it makes sense for us to present/highlight these differences. $\endgroup$ – usεr11852 Apr 12 '19 at 23:46
  • $\begingroup$ @usεr11852 - It makes sense for somebody to highlight those differences, but whether CrossValidated, as opposed to StackOverflow or DataScience (both of which are under the "Technology" branch of StackExchange rather than the "Science" branch of StackExchange as we are) is that somebody is open for debate. Questions about how a specific hyperparameter works in a specific computer program... when I look at that statement, which mimics the one the OP made in comments above, it looks to me like this belongs on a different site. Still, I'll give it the benefit of the doubt. $\endgroup$ – jbowman Apr 13 '19 at 1:05
3
$\begingroup$

XGBoost has multiple ways of tree construction. Excluding GPU-centric implementations, in the current XGBoost version (0.82) there are three tree_method options: exact, approx and hist.

The exact method is most likely what the authors of the linked tutorial refer at; it uses a greedy algorithm where the data are first sorted and all possible splits for continuous features are examined. Thus, yes, the split is done in a greedy manner too. As you correctly note, XGBoost does expand the tree up to max_depth and start prunes exactly because another negative split might benefit future splits. This is imporant as the minimum loss reduction required parameter is embedded in the overall loss function (see T. Chen's XGBoost presentation in page 34).

While fully informative, this exact approach can be computationally demanding and rather hard to parallelise so two additional algorithms have been suggested approx and hist. The approximate greedy algorithm uses weighted quantile of feature distribution to identify the best split. Notice that there is a argument sketch_eps that directly relates to the number of bins used - the weighting actually comes from the second order gradient statistics on the loss function; see the original XGBoost paper in page 4. The hist algorithm implements an approximate binning approach too but it is more sophisticated than the "simple" weighted quantile defined above. The github thread of the related code submission gives more information on the matter. In short, only a subset of possible split values is considered and certain binning calculations can be reused. Caveat: when the construction parameter is set to hist, the grow_policy parameter comes into play where it allows us to include new nodes in a depthwise or a lossguide manner. The lossguide manner can result to rather deep trees because we might end up repeatedly splitting the one leaf that gives the biggest gain instead of splitting until max_depth.

As you see in all tree_method options, the growth is "greedy"; what changes is the way that splits are enumerated. Finally, please note that when it comes to pruning that there is the gamma parameter; it defines a minimum loss reduction required to make a further partition on a leaf node of the tree. That can lead to even to positive split to be pruned.

To recap, yes, the nodes are split in a greedy manner up to the predefined maximum depth irrespective of their potentially negative gain at some stage.

$\endgroup$

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.