XGBoost Tree 'starting feature break'

Question

I am fairly new to learning the XGBoost algorithm and had a question about how the algorithm knows which feature to break the tree on first.

Here is my understanding (and please correct me if I'm wrong):

Each tree starts as a single leaf and all of the residuals go to that leaf. Then we calculate the similarity score and try to split amongst some feature characteristics. For example, say we only had one feature - height. We could split the residual if its respective x-value was say height > $180cm$ or height < $180cm$. And then proceed to calculate the similarity scores and the gain for the new leaves and continue down our tree.

My question is now say we had two or more features such as height, age, weight, education, etc. How does the algorithm know where to break the initial residuals? Does it compute it over all possible features and finds the best gain? I can imagine for large datasets to go through all features, then break it at some threshold and compare must take a long time.

Or does it start at some random feature and work its way down kind of like a random forest? I know there is a parameter within the algorithm that allows you to set the percentage of features per tree so adding on to my question once we specify this percentage how does it pick the features and more importantly once those features are picked how does it know which one to pick to break the initial leaf of residuals.

Edit: I tried reading the paper where the algorithm was first published but found it a bit too difficult to conceptualize and understand.

Answer 1

Each tree starts as a single leaf and all of the residuals go to that leaf. Then we calculate the similarity score and try to split amongst some feature characteristic. For example say we only had one feature - height. We could split the residual if its respective x-value was say height > 180𝑐𝑚 or height < 180𝑐𝑚. And then proceed to calculate the similarity scores and the gain for the new leaves and continue down our tree

• Here it seems like you are describing just a decision tree. Watch this tutorial to understand it a bit more

My question is now say we had two or more features such as height , age , weight , education etc. How does the algorithm know where to break the initial residuals? Does it compute it over all possible features and finds the best gain? I can imagine for large datasets to go through all features , then break it at some threshold and compare must take a long time.

• Again you are talking about the decision tree and its complexity, but yes, for large datasets is overly computationally expensive. To avoid this several strategies are used, as sampling, feature selection or quantization

Or does it start at some random feature and work its way down kind of like a random forest? I know there is a parameter within the algorithm that allows you to set the percentage of features per tree so adding on to my question once we specify this percentage how does it pick the features and more importantly once those features are picked how does it know which one to pick to break the initial leaf of residuals.

• The random forest does random feature selection per split of the tree. The trees are grown greedy, so it tries all possible splits and chooses the best. If the original paper was too difficult try following this tutorial about random forest