Combine decision trees from GBM to reduce output

Question

I am curious if any research has been conducted to efficiently combine trees resulting from a gradient boosting process. I routinely run a process that generates 20 or 30 thousand trees in R. I then convert these trees to SAS which results in hundreds of thousands of lines of code. Many of the trees are very similar, however. This begs the question of whether subsets of related trees can be combined to reduce the amount of code that needs to be generated.

My first approach was to find trees that differed only by their final predictions and de-dupe them. These trees had identical interactions and splits at every node. This works well when the number of interactions is small (<3) however, there is virtually no performance gain when the interactions increase beyond this size as the trees are increasingly likely to be unique.

My next thought is that many of the first or second splits are going to be identical so why not consolidate that logic and nest the remaining nodes within? Before heading down that path, though, I thought I would reach out for guidance or insight here.

Is there a way to combine decision trees output from a GBM process to reduce the number necessary to calculate the final score?

Answer 1

Compressing the decision trees is, as far as I know, an open problem and it seems to be part of the large family of NP problems. However, there are known some greedy approaches which seem to work, at least the second I will present.

The intuition of the first approach is based on splitting the trees into some boolean clauses rules. Then, these rules can be simplified such as to occupy less space, and there were developed also some procedures to remove also the irrelevant rules. The drawback of this approach is the fact that it works usually only with C45-like trees (those decision trees which exhausts one variable, if it was used as a splitting criteria). It is much harder to work with rules generated by binary decision trees or more complex trees because the clauses used in splitting are not trivial anymore.

The second approach it was developed by Yoav Freund and Llew Mason. It is called alternating decision trees (ADTree) and is usually used with boosting. The idea is to build incrementally (as in boosting) some alternate splitting nodes on an existent tree, in order to save some space. You can check more on Wikipedia page. I think one can easily develop further the idea (I planned to do this also in the mid-term future) in order to use alternating splits on decision tree nodes to save some space. I personally see no reason why it would eventually not work, my only concern is related with how much one can save.

Answer 2

I came across this solution after searching for "Compression Ensemble Trees" and was reminded of an approach I read about a couple of years ago. Once the decision forest has been created (in my case 18,828 trees), I applied L1 regularization using the glmnet packaged in R.

This has the effect of re-weighting the trees output by GBM and shrinking the non-predictive or highly correlated tree weights to 0.

The end result was a GBM model of only 847 trees with nearly the same validation performance as the full model. I was able to reduce the model size by a factor of 20 with a minimal hit to performance.