1
$\begingroup$

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"?

Background:
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.
$\endgroup$

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.