How does xgboost select which feature to split on?

Question

Pretty straightforward question. Does it check every feature and pick the one that maximizes some split-quality metric (like a decision tree), or does it just select a feature at random (like a random forest)?

Answer 1

I believe that the xgboost paper is a little underprecise on this point but I will share my interpretation of what they describe. This understanding is not based on reading the code so take it with a grain of salt and hope for a braver soul to put a finer point on this anwer (which I found because I also had it after reading the paper).

The lead-in to the discussion of the approximate algorithm for choosing a split point says

. . . a split finding algorithm enumerates over all the possible splits on all the features"

and then goes on to say that this exhaustive search is unfeasible for large datasets and also does not interact well with distributed training so that an approximate algorithm is needed. This algorithm is described in some detail in the appendix and it is (I believe) specifically an algorithm for finding candidate split points for a given feature.

Their description of how this approximate algorithm is used says

To summarize, the algorithm first proposes candidate splitting points according to percentiles of feature distribution (a specific criteria will be given in Sec. 3.3). The algorithm then maps the continuous features into buckets split by these candidate points, aggregates the statistics and finds the best solution among proposals based on the aggregated statistics.

I believe that this means that candidate splits are proposed for every single feature in the dataset and that all of these candidate splits are inspected to find the optimal one. This means that the method of finding splits really is an approximate form of the algorithm that inspects every single feature and every single split to find the best one but that the approximation only happens at the level of the splits proposed for each feature. Every single feature is still inspected.

Answer 2

The complete algorithm is outlined in the xgboost paper, which also provides this summary:

We summarize an approximate framework, which resembles the ideas proposed in past literatures, in Alg. 2. To summarize, the algorithm first proposes candidate splitting points according to percentiles of feature distribution (a specific criteria will be given in Sec. 3.3). The algorithm then maps the continuous features into buckets split by these candidate points, aggregates the statistics and finds the best solution among proposals based on the aggregated statistics.

Since it's finding the best solution (feature and split) from some set of proposed solutions, we can infer that it is (approximately) optimizing some metric, and that the selection of features and splits is not at random. More complete information is provided in the paper.

It's also worth noting that random forest doesn't simply select features at random -- for each split, random forest selects a subset of features, and then chooses the best split from among the random subset.

Answer 3

The splitting algorithm for XgBoost is pre-sorted and histogram (which is what Joel described in his answer). If you search with these keywords, you will understand them better. Also, my understanding is that to figure out the best split, Xgboost scores the split candidates by using the equation obtained from the derivative of objective function.