2
$\begingroup$

I have an array of sklearn.tree._classes.DecisionTreeClassifier classifiers that are used in a boosting algorithm, so the final classifier is a weighted sum of these individual trees. The problem is that for out-of-sample prediction, it takes a long time to apply the final classifier.

Is there an effective way to combine 2 DecisionTreeClassifiers into an equivalent single DecisionTreeClassifier so that oos prediction does not require iteration?

I could inductively fit a single tree classifier to the ensemble classifier and hope for a good fit - any exact methods without a fitting step?

$\endgroup$

1 Answer 1

2
$\begingroup$

Algorithms such as random forest or boosting are not very computationally demanding at prediction time. If they are for you maybe you should change the hyperparameters, for example, use trees of smaller depth, print them, use fewer trees/iterations. If this still doesn't help because you have some tight constraints, consider using a simpler algorithm like logistic regression, single decision tree, or naive Bayes classifier.

Alternatively, you can use model distillation, i.e. train a simpler model on the predictions of your model. It was shown that it can lead to retaining some of the performance of the original model.

Regarding the comment, the answer to Is the sum of two decision trees equivalent to a single decision tree? makes a theoretical argument that the weighted sum of many decision trees can be collapsed into a single tree. Let's assume you collapse 100 trees into a single tree, in such a case you would have a 100-fold deeper tree than the individual trees in the initial model, this won't make the algorithm more time-performant! In a 100x deeper tree, you would make 100x more decisions on each split. If you used boosting, you would make the same number of decisions and then take a weighted sum of the results. In the end, you would only make it faster by omitting the weighted sum step that would have a negligible effect on the computation time. Moreover, since you would be basically concatenating the trees together, the final decision tree would be huge and you would need (exponentially!) more memory to store the tree (in the random forest or boosting, you could call the individual trees sequentially or in parallel).

$\endgroup$
3
  • $\begingroup$ This seems to be lossless - stats.stackexchange.com/questions/336276/… so I'm looking for an implementation. $\endgroup$ Commented Aug 23, 2021 at 16:05
  • $\begingroup$ @CharlesPehlivanian see my edit. $\endgroup$
    – Tim
    Commented Aug 24, 2021 at 8:44
  • $\begingroup$ I wound up using your last suggestion, the sum of weighted decision trees is easily parallelizable. I was hoping for some redundancy gains when combining trees, but even then run times will be longer than a distributed approach. It is working well thans. $\endgroup$ Commented Aug 26, 2021 at 1:57

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.