I see a random forest as a parallel ensemble of CART models, and a gradient boosted machine as a series ensemble of CART models. A forest is defined by the interaction of many trees, so there should be a pruning that accounts for multiple trees and is more than "one tree at a time vs. the data". Is there pruning that works on "trees" and not just "tree"?

Typical decision tree pruning involves removing branches from a single tree by looking at the data and error. No inspection of "multiple trees" is made.

My thought:
So I was thinking about boiling down a forest to remove redundant branches in context of other trees in the forest.

I envision it as something like this

  • fit random forest to data (ntrees > decent floor)
  • pop out each tree and predict using it
  • use clustering on the predictions (GMM + AICc) to find optimal cluster count and parameters. A distance metric would also be needed.
  • for each cluster, look to cull predicted points such that minimum samples to support mean and variance per component are retained.
  • remove branches from trees that were not retained, replacing output with "NaN" or something not included in aggregation.

I would expect that applying this approach to a random-forest fit of the iris data, one could get perhaps a single branch of a single tree to indicate "setosa" while several more would be required to account for "setosa" and "virginica".

I would expect this tree-trimmed forest to have faster compute time on some canonical datasets.

My questions:

  • Has anything like this been done and documented before to random forests? I tried looking for documentation and found only "Ensemble Selection from Libraries of Models" by Caruana from ICML '04. It seemed more about forward construction, not backwards trimming.

  • What sorts of speed-ups/complexity reductions can be found for the canonical data to which RF is typically applied.

  • Has this been used online or batch-online in a predictor-corrector to add->cull->repeat for growing random forests? I would imagine that only adding trees that have some level of innovation would be efficient.
  • Has this been used online in gradient boosted machines (aka boosted series forests)? The xgboost library is one of the winning-est on kaggle but after 10,000 serial trees it is still slow. Someone has to have thought of looking at sequential trees and culling before adding another tree.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.