What is the difference between growing a tree based learning algorithm vertically as compared to horizontally?

Question

I came across the tree based algorithm Light GBM and I have read that it grows the trees vertically meaning that the Light GBM grows tree leaf-wise (while some other algorithms grow level-wise). I was just wondering and thinking: What is the advantage of growing a tree vertically? Are there any?

A difference (not necessarily an advantage) which I can see is the way you need to define early-stopping criteria while growing the tree. Any thoughts on this?

Answer 1

As described in this section of LightGBM's documentation

LightGBM uses leaf-wise (or what XGBoost calls lossguide) tree growth because it can achieve lower loss (i.e. better fit to the training data) than depth-wise tree growth, holding the number of leaves constant.

In leaf-wise tree growth, the split with the largest gain is chosen, regardless of its level of depth.

A difference ... I can see is the way you need to define early-stopping criteria while growing the tree

It's true that in this type of tree growth, you now have to consider two closely-related ways to prevent overfitting:

• maximum depth (max_depth in LightGBM)
• total allowed number of leaves (num_leaves in LightGBM)

I'm assuming this is what you meant by "early-stopping criteria", but wanted to also note that the phrase "early stopping" has a special meaning in GBMs that isn't related to how individual trees are grown. Early stopping, as XGBoost, LightGBM, and other GBM libraries refer to it, means "if performance on held-out data fails to improve for n iterations, stop training".