7
$\begingroup$

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)?

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It would have been nice if the question was answered from a different perspective, without quoting directly from a (rather technical) paper -- especially since the answer assumes that the OP didn't read or trying reading it. $\endgroup$ – cosmosis Sep 29 '17 at 17:27
  • 2
    $\begingroup$ I don't have another answer -- I'm looking for one. $\endgroup$ – cosmosis Sep 29 '17 at 17:54
  • 1
    $\begingroup$ I had the same question as OP after having read this section of the paper carefully a number of times. I think it is aggressive to assume the OP has not read the paper and I do not think the provided quote is really clear on what the answer to the question is. $\endgroup$ – Joel Dodge Nov 21 '17 at 19:39
  • 1
    $\begingroup$ OP specifically asks about whether FEATURES are chosen at random and the method for selecting which features to consider is neither addressed in the provided quote nor really explicitly addressed in the paper. $\endgroup$ – Joel Dodge Nov 21 '17 at 21:10
  • 1
    $\begingroup$ @JoelDodge It's clear that you have a dramatically different reading of the question and my answer. $\endgroup$ – Sycorax says Reinstate Monica Nov 21 '17 at 21:15
0
$\begingroup$

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.

| cite | improve this answer | |
$\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.