10
$\begingroup$

Gradient tree boosting as proposed by Friedman uses decision trees with J terminal nodes (=leaves) as base learners. There are a number of ways to grow a tree with exactly J nodes for example one can grow the tree in a depth first fashion or in a breadth first fashion, ...

Is there an established way how to grow trees with exactly J terminal nodes for gradient tree boosting?

I examined the tree growing procedure of R's gbm package and it seems that it expands the tree in depth-first fashion and uses a heuristic based on error improvement to choose whether to expand the left or the right child node -- is that correct?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ gbm uses CART to build the trees, a well known algorithm from the 80s. The heuristic is called gini impurity, a pretty standard choice for regression with quadratic loss. $\endgroup$
    – user8183
    Commented Dec 25, 2011 at 3:27
  • 2
    $\begingroup$ Afaik gini impurity is used for classification Problems. Nevertheless, the question refers to the size of the trees. $\endgroup$
    – Peter Prettenhofer
    Commented Dec 29, 2011 at 13:51
  • $\begingroup$ It adds a branch at a time. I would be surprised if each next split is the best of the remaining split candidates in the tree, not just the branch. There are times when the data does not support an exact number - such as when the data is too small for 'J'. $\endgroup$
    – EngrStudent
    Commented Oct 10, 2016 at 21:46
  • $\begingroup$ As @EngrStudent said, you cannot force a precise number of nodes. However, you have some control over an upper bound on the number of nodes. gbm has a parameter n.minobsinnode that controls the minimum number of objects per node. Of course, then the number of nodes is less than or equal to NumberOfPoints/n.minobsinnode $\endgroup$
    – G5W
    Commented Dec 30, 2016 at 12:18
  • $\begingroup$ If I were looking for 'J' leaves, then I would fully build the tree and then, assuming there were more than J leaves, I would prune down to J. This would give me 'J' nodes, and they would be the most informative splits - it would be the healthiest CART model it could be. If there aren't enough splits, I could just randomly split within the domains to get 'J' but they would be spurious and somewhat trivial. I might look at value distribution within the leaf, and use a CDF-driven aproximation, but that would depart from the mean-per-leaf model. $\endgroup$
    – EngrStudent
    Commented Dec 30, 2016 at 17:38

1 Answer 1

Reset to default
2
$\begingroup$

The solution in R's gbm is not a typical one.

Other packages, like scikit-learn or LightGBM use so-called (in scikit-learn) BestFirstTreeBuilder, when the number of leaves is restricted. It supports a priority queue of all the leaves and at each iteration splits the leaf that brings the best impurity decrease. So it is neither depth-first nor breadth-first, but a third algorithm, based on calculations in the leaves.

In some sense, this approach is more optimal than blindly split all the leaves in turn. However, it is still a greedy heuristic, because the choice whether to split the $i$'th node now depends only on the first split of $i$ and not the possible succesive splits that may decrease impurity much more than the current split.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.