Simplification of Forest Classifiers and Regressors by Sharing Branching Conditions

Abstract

We propose a novel method for simplifying a tree ensemble, not only for size reduction but also to enhance interpretability. Our simplification of a tree ensemble needs a set of feature vectors. It is formalized as the problem of sharing as many branching conditions as possible among the component tree internal nodes, under the constraint that the decision paths of all the given feature vectors must remain unchanged. For a branching condition that a value of some feature is, at most, a threshold θ , the range of θ satisfying such a constraint can be represented as an interval. Thus, the problem of minimizing the number of distinct branching conditions by sharing them under the constraint is reduced to the problem of finding the minimum set of thresholds that intersect all the constraint-satisfying range intervals of thresholds for branching conditions on the same feature. We propose an algorithm for the original problem that utilizes a known greedy algorithm to efficiently solve the reduced problem. To promote further sharing of branching conditions, we also study two constraint-relaxed versions of the problem: (1) allowing decision path change of a specified ratio of the given feature vectors at each branching node, (2) allowing constraint breaking of a specified ratio of the branching nodes. We also extended our algorithm for both relaxations. The effectiveness of our method is demonstrated through comprehensive experiments using 21 datasets (13 classification and 8 regression datasets in the UCI Machine Learning Repository) and 4 classifiers/regressors (random forest, extremely randomized trees, AdaBoost, and gradient boosting). Branching condition sharing is effective even after applying other types of simplification methods, such as those that reduce trees, root-to-leaf paths, or nodes. It enables compact hardware implementation of a tree ensemble by sharing comparators.