# Best way to merge different trees to single data structure?

I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast because every tree is simply nested if-else statement. What I noticed is that many trees are similar and I was wondering if there is a way to merge all of those trees into one tree or maybe to reduce number of trees by merging some of them? Maybe even convert everything to some different data structure?

This is what dump looks like:

booster[0]:
0:['::'] yes=2,no=1
1:['=>'] yes=4,no=3
3:['es'] yes=8,no=7
7:['ef'] yes=10,no=9
9:leaf=-0.0339584
10:leaf=0.0612883
8:leaf=-0.0484913
4:leaf=0.0358804
2:[';\s'] yes=6,no=5
5:leaf=0.373993
6:leaf=-0.0376609
booster[1]:
0:['</'] yes=2,no=1
1:['h\n'] yes=4,no=3
3:[':v'] yes=8,no=7
7:leaf=-0.0487989
8:leaf=0.0200258
4:['_t'] yes=10,no=9
9:leaf=-0.03375
10:leaf=0.172536
2:['*\s'] yes=6,no=5
5:leaf=0.354577
6:leaf=0.0165644

// etc.. boosters go on and on...


Let me explain how it works by going through booster[0]. First we check if sample we're classyfing contains '::'; if yes we jump to branch 2. There we check if sample contains ';\s' and if yes, we jump to branch 6. Branch 6 is leaf so we just take value -0.0376609 and we add it to probability that sample is class '0'.

We do the same for booster[1] and it gives us probability that sample is of class '1'. It goes on and on for all 50 classes and then the process is repeated for many iterations that gives us 50 * num_iterations of trees. It comes up around 10k of trees.

Anyone has any idea if there is a better way of representing these trees so our classification works even faster?

I don't think post-processing the trees to try to exploit similarity is likely to lead to much success. Instead, I would suggest trying the following approaches, which to my mind seem more likely to be effective.

Tune the hyperparameters. Try adjusting the number of trees (num_iterations). If you can get close to the same accuracy with fewer trees, the classifier will be faster.

Try a different classifier. There are other classifiers that are faster for evaluating new samples, especially in the multi-class regime. For instance, you could try logistic regression and random forests.

Hierarchical multi-class classification. XGBoost is fundamentally a boolean classifier (where there are only two classes). It handles multi-class classification (with more than two classes) using the strategy one-vs-rest (or one-vs-all) strategy: if there are $K$ classes, then we construct $K$ boolean classifiers, where the $i$th either outputs "class $i$" or "not class $i$". This is what leads to the blowup in number of trees: the running time is proportional to $K$.

If your classes have any hierarchical structure, then an alternative is to use a hierarchical structure. You build a binary tree, where each leaf corresponds to a single class and each internal node corresponds to a set of classes (hopefully, ones that are semantically related). You construct a classifier for each internal node of the tree, which predicts whether to go left or right down the tree. You classify each new instance by walking down the tree, as directed by the classifiers that you visit. Thus, with $K$ classes, we end up with a binary tree with $K$ leaves and of depth (typically) about $\lg K$. Thus, you can classify a new instance by evaluating $\lg K$ classifiers. This offers a speedup over one-vs-rest, because the time to classify a new instance is proportional to $\lg K$ rather than $K$.

However, hierarchical classification has some caveats. It can potentially lead to reduced accuracy. The effect on accuracy depends on the structure of the class labels. If there is some hierarchical structure, then it might work well, but if not, it might work poorly. For instance, suppose you have classes "Poodle", "Chihuaha", "Siamese", and "American Shorthair", you might group the first two into the cluster "Dog" and the latter two into the cluster "Cat". Thus, you would first apply a Dog vs Cat classifier; then, depending on the result, you would either apply a Poodle vs Chihuaha classifier or a Siamese vs American Shorthair classifier. So, hierarchical classification might work quite well in this example. However, if your four classes are unrelated, hierarchical classification might cause a loss in accuracy.

Try a cascaded classifier. Rather than building a single classifier, try to build a cascade of classifiers. A cascade is a sequence of multiple fast classifiers, which are applied sequentially. A classifier can either output a confident answer or can output "not sure"; in the former case, we stop and use that as the answer, and in the latter case, we proceed to the next classifier in the cascade. The goal is that many instances will get answered quickly (you only have to apply the first few classifiers), and only the difficult ones will have to be evaluated by classifier in the sequence.