Extracting Interpretable Models from Tree Ensembles: Computational and Statistical Perspectives

Brian Liu, Rahul Mazumder, Peter Radchenko · 2025

Read Extracting Interpretable Models from Tree Ensembles: Computational and Statistical Perspectives by Brian Liu, Rahul Mazumder, Peter Radchenko (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-20114.txt.

Introduction

Tree ensembles predict well by combining many decision trees, but their size makes them hard to read. Brian Liu, Rahul Mazumder, and Peter Radchenko proposed a method in 2025 to pull a small set of clear decision rules out of such an ensemble. The extracted rules stay accurate and can be checked by hand to see how inputs relate to the outcome.

Their method lets the user control both how many rules are kept and how deep each rule can go. The authors built an exact solver and a faster approximate one, and proved error bounds that match an ideal rule chooser. Tests showed the method beats existing rule extraction tools.

Catalog record

CREATORBrian Liu, Rahul Mazumder, Peter Radchenko
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-20114

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Extracting Interpretable Models from Tree Ensembles: Computational and Statistical Perspectives Brian Liu, Rahul Mazumder, Peter Radchenko Abstract Tree ensembles are non-parametric methods widely recognized for their accuracy and ability to capture complex interactions. While these models excel at prediction, they are difficult to interpret and may fail to uncover useful relationships in the data. We propose an estimator to extract compact sets of decision rules from tree ensembles. The extracted models are accurate and can be manually examined to reveal relationships between the predictors and the response. A key novelty of our estimator is the flexibility to jointly control the number of rules extracted and the interaction depth of each rule, which improves accuracy. We develop a tailored exact algorithm to efficiently solve optimization problems underlying our estimator and an approximate algorithm for computing regularization paths — sequences of solutions that correspond to varying model sizes. We also establish novel non-asymptotic prediction error bounds for our proposed approach, comparing it to an oracle that chooses the best data-dependent linear combination of the rules in the ensemble subject to the same complexity constraint as our estimator. The bounds illustrate that the large-sample predictive performance of our estimator is on par with that of the oracle. Through experiments, we demonstrate that our estimator outperforms existing algorithms for rule extraction. Keywords: Interpretable Machine Learning, Tree Ensembles, Nonparametric Methods 1 Introduction Tree ensemble algorithms, such as random forests ( Breiman 2001a ) and gradient boosting ( Friedman 2002 ) , are among the most well-known methods in statistical modeling and have achieved success across a broad range of disciplines, from remote sensing ( Belgiu and Drăguţ 2016 ) to genomics ( Chen and Ishwaran 2012 ) . Since their introduction, tree ensembles have earned a reputation for excellent predictive performance, in fact, Leo Breiman notably claims in Statistical Modeling: The Two Cultures ( Breiman 2001b ) that “Random Forests are A+ predictors.” By combining a large number of decision trees, either independently trained on bootstrapped samples of the data or sequentially on the residuals of the prior model, tree ensembles attain high predictive accuracy, albeit for an increase in model complexity and often at the expense of interpretability. Compared to a single tree, ensembles are substantially more challenging to interpret and, indeed, for random forests, Breiman ( Breiman 2001b , p. 208) claims that “on interpretability, they rate an F.” Model Explanation • If speduc \leq 14.75 and class \leq 2.5, then predicted income = $30,507.24. • If speduc \leq 14.75 and class > 2.5, then predicted income = $55,272.53. • If speduc > 14.75 and class \leq 2.5, then predicted income = $57,088.07. • If speduc > 14.75 and class > 2.5, then predicted income = $105,252.60. Figure 1 : Decision tree fit to predict household income using survey responses. Feature speduc is the spouse’s education (years); class is the self-identified income class. Consider, for example, the single decision tree shown in the left panel of Figure 1 , constructed to predict household income based on survey responses from the 2022 General Social Survey (GSS) ( Davern et al. 2024 ) —a dataset with 4,000 respondents and 15,000 covariates. This tree is highly interpretable, and its predictions can be fully explained in four sentences corresponding to the four rules listed in the right panel of the figure. Each rule consists of a sequence of conditions obtained by traversing the tree from the root node to a leaf. Tree ensembles can also be described by similar sets of rules, but these are rarely human-interpretable for two reasons. First, the number of rules is prohibitively large; for example, a boosting ensemble of 500 depth 6 trees requires 32,000 rules (sentences) to explain. Second, especially in deeper ensembles, each individual rule may be too complex to interpret. As Breiman ( Breiman 2001b , p. 208) observes for random forests: “their mechanism for producing a prediction is difficult to understand. Trying to delve into the tangled web that generated a plurality vote from 100 trees is a Herculean task.” Yet, ensembles are significantly more accurate than single trees. On the GSS survey example, the decision tree shown in Figure 1 achieves an out-of-sample R^{2} of 0.28 while the 500 depth 6 tree boosting ensemble mentioned above attains an out-of-sample R^{2} of 0.55 . Motivation: “Framing the question as the choice between accuracy and interpretability is an incorrect interpretation of what the goal of statistical analysis is. The point of a model is to get useful information about the relation between the response and predictor variables.” ( Breiman 2001b , p. 210) (a) Boosting ensemble of 500 depth 6 trees: OOS R^{2}=0.55 . (b) Extracted model of 10 rules: OOS R^{2}=0.50 . Figure 2 : Application of our proposed estimator to the GSS example. Our estimator extracts a compact set of rules with varying interaction depths. To bridge the trade-off between model accuracy and interpretability, we propose a novel estimator to extract rule sets from tree ensembles. These rule sets retain predictive accuracy comparable to the full models, while being compact enough for practitioners to manually examine and understand the relationship between the predictors and the response. We consider compactness along two dimensions: the number of rules extracted (i.e., the number of sentences a practitioner must read to explain the model) and the interaction depth of each rule (i.e., the complexity of each sentence). In Figure 2 , we demonstrate an application of our proposed estimator to the GSS example discussed above. Panel (a) visualizes the original boosting ensemble of 500 depth 6 trees (32,000 rules) that achieves an out-of-sample R^{2} of 0.55. In panel (b), we apply our estimator to extract 10 rules from the ensemble, which achieve an out-of-sample R^{2} of 0.50 . Our estimator prunes the interaction depth of many rules and extracts a rule set compact enough to be examined by hand. Our proposed approach builds on prior work by Friedman and Popescu 2008 , who use the LASSO to prune rules from random forests, and by Meinshausen 2010 , who applies the non-negative garrote for rule extraction. Compared to existing methods, a key novelty of our estimator is its ability to jointly control both the number and depths of the extracted rules, a flexibility that leads to substantial improvements in predictive performance. In addition, to the best of our knowledge, we are the first to establish prediction error bounds for pruning rules from tree ensembles. We summarize our main contributions. \bullet We propose a novel estimator that uses an optimization-based framework to extract interpretable models from tree ensembles, offering the flexibility to jointly control both the number of rules extracted and their interaction depths (§ 2 ). \bullet Our estimator is given by a discrete optimization problem that is difficult to solve due to its non-convexity. We develop a novel, specialized exact algorithm that solves this problem to global optimality and scales to sizes significantly beyond the capabilities of commercial solvers such as Gurobi ( Gurobi Optimization, LLC 2024 ) and Mosek ( MOSEK ApS 2024 ) . With this exact algorithm, our estimator has theoretical guarantees (§ 3.1 ). \bullet We develop an approximate algorithm tailored for efficiently extracting sequences of models

Read the complete text