1
$\begingroup$

I wonder whether algorithms such as GBM, XGBoost, CatBoost, and LightGBM perform more than two splits at a node in the decision trees? Can a node be split into 3 or more branches instead of merely binary splits? Can more than one feature be used in deciding how to split a node? Can a feature be re-used in splitting a descendant node?

$\endgroup$
1
2
$\begingroup$

Gradient boosting can be applied to any base model, so doing it with a Quinlan-family decision tree (which allow for such higher-arity splits for categorical features) should make this possible. However, all implementations of gradient boosted trees that I know of (and certainly XGBoost, CatBoost, LightGBM) all use CART as their tree model, so you won't get anything but binary trees. (These GBMs do modify CART a little, e.g. in using histogram binning to reduce the split searches, but nothing as drastic as n-ary splits for categoricals.)

$\endgroup$
3
  • $\begingroup$ Hey, thanks for the answer. Why are the limitations put into place? Won't it be more accurate and flexible to do away with such limitations? Should I try implementing my own gradient boosting regressor that can perform n-ary splits, use more than one feature at a split, and reuse features? $\endgroup$ – Chong Lip Phang Dec 18 '20 at 15:52
  • $\begingroup$ "More accurate and flexible" on the training set might overfit, so it's not an obvious improvement. multivariate splits and n-ary splits for continuous variables will hurt training time, as well; but if you build such a thing and can show improvement on some benchmark datasets, maybe that can be overcome. Reusing features is already standard. $\endgroup$ – Ben Reiniger Dec 18 '20 at 16:11
  • $\begingroup$ It suddenly occurred to me that there is no point in doing a ternary split as it can always be done in two-level binary splits. As for multivariate splits, I think it is worth looking into. I suppose reusing features in the descendants of a decision tree has been the standard in the implementations of regressors. $\endgroup$ – Chong Lip Phang Dec 18 '20 at 16:17

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.