My understanding of this stuff is pretty basic so my semantics may be off, but bare with me.

XGBoost and other gradient descent packages make the best possible split of the data right off the bat. Then with that subset of data, make the best possible split again. But what if the best possible tree is full of splits that require other splits to work?

For example, imagine there was this best possible perfect tree. But the first split on its own would be awful, and the second split on its own would be awful as well, BUT when you apply the second split to one of the subsets from the first split, it works really well?

Gradient descent would never explore this possibility, where each split on its own doesn't work but when you combine them its really effective.

The only way to find this "perfect" tree of splits would be some sort of genetic algorithm to make the trees that just tries weird stuff and sees if it is good?


2 Answers 2


"All models are wrong, some are useful" - George Box

CART based trees are greedy. They may miss the best split. CART based trees do not look ahead or backfit. The hope is that after many splits, many trees, the final answer will be close enough to optimal. There is no guarantee with any algorithm though, i.e. the no free lunch theorem.

There are other types of trees besides CART. Bayesian trees, optimal trees, model based trees, and more, that may not be as greedy and MAY or MAY NOT make a "better" model for your use case. You can always try different algorithms.


Your question:
how poor is the CART ensemble (random forest or GBM) at finding an exact perfect line of split?

Each tree can be considered a piecewise constant fit of the surface. The inputs for the trees are trained on a random subset of both the columns and the rows, so no two trees are fed the same information. This leads to the trees having a bootstrap-style distribution of split locations.

For the RF, the trees are aggregated for continuous domain outputs using an error weighted mean sum.
For the Boosted Machine (series ensemble) the target is a weighted error of the previous ensemble. This means that over time it gets closer and closer to exact.

What it means:
If you were trying to use a random-forest to approximate a cube, all else being equal, you are likely to get a 12th power spheroid. If you were trying using a GBM it might be a 120th power spheroid. In the limit of many samples, many compute, big model, it could be said to approach to within a bound of error, which a mathematician would love. It can get very very close.

The problem is that there is "no perfect system". All universal approximators are approximators.

As always, we are mechanics at the garage and there is no perfect tool. We need to have a wide variety of tools that we understand sufficiently well to apply to the problem.


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.