TE2Rules: Explaining Tree Ensembles using Rules

In recent years, many decision support systems have been constructed as black box models using machine learning such as Tree Ensembles (TE) and Deep Neural Networks. Lack of understanding of the internal logic of decision systems constitutes both a practical and an ethical issue, especially for critical tasks that directly affect the lives of people like health care, credit approval, criminal justice etc. In such use cases, there is a possibility of making wrong decisions, learned from spurious correlations in the training data. The cost of making wrong decisions in these domains is very high. Hence, having some explanations (like what part of the input is the model focusing on, or under what conditions satisfied by the input, does the model behave similarly) is important for building trust on these decision systems. Moreover, recent legal regulations like General Data Protection Regulation (GDPR, 2018) enables all individuals to obtain “meaningful explanations of the logic involved” when automated decision making takes place.

In this work, we focus our attention on explaining tree ensemble (TE) models which are popular in many use cases involving tabular data (Grinsztajn, Oyallon, and Varoquaux 2022; Qin et al. 2021). Our focus is exclusively on binary classification models, as they are prevalent in many critical decision-making systems such as disease diagnosis and spam detection. In the realm of binary classification, providing explanations for one class can be more crucial than the other. Consider healthcare or fraud detection, where explaining why a model identifies a data point as positive (e.g., detecting a tumor or predicting a scammer) is vital. Interestingly, the positive class often represents the minority class in the training/test data.

A popular method to explain any model is to learn an interpretable surrogate model that closely approximates the original model. The accuracy of the surrogate model with respect to the original model is called fidelity. A good explainer needs to have high fidelity on test data. Additionally, for effective explanation of the minority class, the explainer must demonstrate good fidelity specifically on the part of the test data where the model predicts the minority class. Therefore, the explainer needs to maintain high fidelity overall and also high fidelity on the minority class predictions. However, many state of art rule-based explainers excel in overall fidelity but struggle to explain the minority class accurately. This is problematic, especially when the minority class corresponds to the positive class. This limitation hinders their utility in explaining predictions for the important positive class.

In this work, we introduce a novel algorithm TE2Rules (Tree Ensemble to Rules) designed to mine rules only for the (minority) positive class. Each individual rule takes the form ”If feature${}_{i}>t_{i}$ and feature${}_{j}\leq t_{j}$ …and feature${}_{k}\leq t_{k}$, then model prediction = 1,” where the label 1 signifies the positive class. The rules mined by TE2Rules are short with only a few features and each rule has a high precision, i.e, of all the data points that satisfy the rule, a high fraction of them (default of 95%) get positive class prediction by the model. Besides high precision, each rule has a decent coverage on positives. We post process these rules by selecting a small number of rules that cover most of the positives in the data. This small collection of rules can explain the model at a global level with high overall fidelity as well as high fidelity on positive class predictions. TE2Rules can mine these rules in a runtime that is comparable to other state of the art model explainers making the algorithm scale to tree ensembles with hundreds of trees.

TE2Rules achieves it capabilities by leveraging the Apriori Algorithm. The Apriori algorithm is a data mining algorithm that identifies items that are frequently found together in a collection of itemsets. In the context of TE2Rules, positive class predictions are explained by identifying sets of internal tree nodes that are commonly active with positive class predictions, but not with negative class predictions. These sets of tree nodes are then converted into rules using the necessary conditions that an input data point must satisfy to traverse that particular combination of tree nodes within the tree ensemble.

In this work, we show that 1) many existing state of the art rule based explainers for tree ensemble (TE) models have poor fidelity on positives (the minority class) though they may have good overall fidelity. 2) To solve this problem, we propose a novel method, TE2Rules (Tree Ensemble to Rules), that can generate rules corresponding to a single class of interest (say positive class) by merging decision paths from multiple trees in the tree ensemble. Since all the rules are mined for a single class, there is no conflict among the labels predicted by different rules. 3) We show that the resulting rules have high overall fidelity and high fidelity on positives (the class of interest) even if the positives happen to be a minority class in the dataset. TE2Rules can achieve such high performance at comparable number of rules relative to existing baselines, at the cost of slightly higher run time. 4) By stopping the algorithm in the early stages, we can tradeoff fidelity with runtime.

In the past, several methods have been proposed to explain a tree ensemble model using rules or decision trees that can be better understood by a human. Some of these approaches work at a global level by approximating the tree ensemble with a set of rules or decision tree. While some other approaches work at a local (instance-level) by finding a rule or a decision tree that best explains the decisions of the tree ensemble for data points sampled from the neighborhood of that instance.

Rule-based explainers: inTrees(Deng 2019) generate rules from decisions made from individual trees in the tree ensemble and selects high precision rules among them. Another closely related method, ruleFit (Friedman and Popescu 2008) runs a sparse linear regression on rules generated from individual trees to select the most important rules. However, a sparse ensemble of rules is not as interpretable as a list of if-then rules. Both inTrees and ruleFit generate rules from nodes of individual trees and do not consider node combinations from multiple trees. Hence, their search space of rules is limited to rules from individual trees, resulting in low fidelity. deFragTrees (Hara and Hayashi 2018) identifies fragmented regions in the input space defined by the splits made by the tree ensemble and tries to simplify them into a short set of rules that are almost equivalent to the tree ensemble using bayesian inference. deFragTrees works on simplifying rules obtained from all possible node combinations from multiple trees in the ensemble and can achieve higher fidelity than methods like inTrees. However, most rule-based explainers are not targeted to explain any one single class. They often end up mining a lot of rules for the majority class and miss out on the minority class. In such cases, they are not very effective in explaining the minority class prediction.

Tree-based explainers: BATrees (Vidal, Pacheco, and Schiffer 2020), uses the tree ensemble to generate more labeled data points that can be used to fit a decision tree on the data. However, trying to obtain a single tree decision tree to represent a tree ensemble can result in a very deep tree, making it harder to interpret. Node Harvest (Meinshausen 2010) selects a few nodes from the shallow parts of the trees in the ensemble and creates an ensemble of shallow trees. The simplified model is easier to interpret than the original model. But, it is still not as easy to interpret as a decision tree or rule list.

Local instance-level explainers: Some explanation methods are model-agnostic and can be applied to models beyond tree ensembles. Anchors (Ribeiro, Singh, and Guestrin 2018) finds high precision, if-then rules satisfied by the instance, using multi-armed bandit and beam search algorithms. LoRE (Local Rule-based Explanations) (Guidotti et al. 2018) constructs interpretable models (decision trees) based on local samples. For each input data point, rules are generated that are locally accurate. A local search is conducted for every incoming data point to be explained. Hence, these methods can be prohibitively expensive if the objective is to explain a very large set of data points for a single model.

Interpretable models: Instead of explaining existing machine learning models, an alternative approach is to directly learn interpretable models from data. Some methods, like Falling Rule List (Wang and Rudin 2015), Interpretable Decision Sets (Lakkaraju, Bach, and Leskovec 2016), and Bayesian Rule List (Yang, Rudin, and Seltzer 2017; Wang et al. 2017), learn rule lists directly from data using association rule mining algorithms such as Apriori (Agrawal, Srikant et al. 1994) or its variants like FP-Growth (Borgelt 2005).

The Apriori Algorithm is a data mining algorithm designed to identify subsets of items that frequently co-occur in a collection of itemsets. Apriori is particularly valuable in analyzing e-commerce transactions. For instance, in a database of customer transactions where each transaction includes a set of items bought together (like $\{$milk, bread, jam$\}$, $\{$eggs, bread, jam$\}$, etc.), Apriori can identify frequently co-occurring subsets of items (such as $\{$bread, jam$\}$).

Some other approaches like SkopeRules (Gautier, Jafre, and Ndiaye 2020) learns rule lists by first fitting a tree ensemble model on the data and then extracting rules from it. Unlike the methods that explain a trained tree ensemble model, SkopeRules learns a tree ensemble model internally and doesn’t explain an existing trained tree ensemble model.

In this work, our focus is on explainers that take a tree ensemble model and some data as input, producing rules that explain model prediction, especially for the minority (positive) class. The explainer operates globally, producing different possible rules under which the model gives positive predictions. For this purpose, we utilize the Apriori Algorithm to identify frequently co-occurring decisions made within the nodes of the tree ensemble that result in positive class predictions. While the Apriori Algorithm has been employed in recent times to learn interpretable models directly from data, our work represents the first application of association rule mining for explaining a trained tree ensemble model. We choose inTrees and deFragTrees as our baselines since they are also global explainers that generate a rule list from the tree ensemble model and a slice of training data.

Apriori Algorithm: Before describing TE2Rules, it is important to understand the Apriori Algorithm. Apriori is a data mining algorithm designed to identify subsets of items that frequently appear together in a collection of itemsets. It uses 2 user-defined parameters: $m$ and $k$. Apriori looks for subsets containing $1,2,3,$ upto $k$ items, where the items within each subset occur together more than $m$ times in the overall collection of itemsets. For example, Table 4 shows a dataset with a collection of 7 itemsets. The itemset {bread, jam} appears as a subset in 4 different itemsets out of 7 in the dataset. Apriori tries to find such frequently occurring subsets. Apriori algorithm runs in stages. In the $k$-th stage, it tries to find subsets of size $k$ that occur more than $m$ times. Here’s a brief description of how Apriori works.

In stage 1, Apriori examines individual items or $1$-item sets that have a frequency more than $m$ in the collection. Such, itemsets are considered to be frequent enough in stage 1.

In stage $k^{\prime}$ (with $1<k^{\prime}\leq k$), it identifies itemsets of size $k^{\prime}$ that occur more than $m$ times in the dataset. To generate candidate itemsets for the current stage $k^{\prime}$, the Apriori algorithm looks at pairs of itemsets of size $(k^{\prime}-1)$ from the previous stage. Combining such a pair would result in an itemset of size $2(k^{\prime}-1)$. However, Apriori only considers pairs of itemsets that have $(k^{\prime}-2)$ items in common. Combining such a pair results in itemset with $2(k^{\prime}-1)-(k^{\prime}-2)=k^{\prime}$ items.

The algorithm leverages the “Anti-monotone property,” which states that if an itemset is frequent, then all of its subsets must also be frequent. For each candidate itemset generated above, Apriori checks if all its subsets of size $(k^{\prime}-1)$ have been found to be frequent in the previous stage.

For a candidate itemset that has passed the test of “Anti-monotone property,” Apriori counts its number of occurences in the dataset and keeps only those candidate itemsets that occur more than $m$ times in the dataset. These itemsets are considered to be frequent enough in stage $k^{\prime}$.

Example: Let’s apply Apriori to discover subsets of items that appear more than $m$ = 1 times in Table 4 by running Apriori till $k=3$ stages.

Stage 1: In stage 1, Apriori considers individual items or sets of $1$ item, that have a frequency exceeding $m$ in the collection. The counts of these items in the collection are presented in Table 4. Among these items, {jam}, {bread}, {milk}, {butter} are identified as frequent since they occur more than $m$ = 1 times in the collection.

Stage 2: In stage 2, Apriori combines pairs of itemsets found to be frequent in stage 1 to form itemsets of 2 items. This ensures that itemsets containing {eggs} are excluded from exploration in stage 2, since the itemset {eggs} was not frequent enough in stage 1. The counts of these 2-item itemsets formed in this manner are presented in Table 4. Among these items, {jam, bread}, {jam, milk}, {bread, milk}, {jam, butter} occur more than $m$ times in the collection.

Stage 3: In stage 3, Apriori combines pairs of itemsets that were identified as frequent in stage 2. If a pair of itemsets shares one item in common, Apriori merges them to create a new itemset with three items. For instance, it combines {jam, bread} and {jam, milk} to produce {jam, bread, milk}, and similarly for other combinations.

After generating these 3-item itemsets, Apriori verifies that all 2-item subsets derived from each itemset was found to be frequent enough in stage 2. For example, the itemset {jam, bread, butter} is formed from {jam, bread} and {jam, butter}. But, the itemset {jam, bread, butter} also contains the subset {bread, butter}, which was not frequent in stage 2. Thus, Apriori removes this 3-item itemset. Following this approach, only the 1 itemset remains: jam, bread, milk with all its subsets already identified as frequent in stage 2. This itemset also meets the frequency threshold by appearing more than $m$ times in the collection (as illustrated in Table 4).

Thus, the itemsets {jam}, {bread}, {milk}, {butter}, {jam, bread}, {jam, milk}, {bread, milk}, {jam, butter}, {jam, bread, milk} occur frequently (more than $m$ times) in the collection.

TE2Rules Algorithm: TE2Rules takes a trained tree ensemble (TE) model with hundreds of decision trees and a slice of training data as input and gives a list of rules for positive class as output. Consider a tree ensemble containing $n$ trees, each with a maximum depth of $d$. These trees are made of internal nodes, and each node decides whether to move left (if feature${}_{i}\leq t_{i}$) or right (if feature${}_{i}>t_{i}$) based on a single feature. When we input a data point into this tree ensemble model, it traverses all $n$ trees, navigating internal nodes based on feature conditions. This journey involves passing through $d$ internal nodes + $1$ leaf node in each tree. Consequently, the data point traverses a total of $n(d+1)$ tree nodes across the entire ensemble. It is important to note that any other data point meeting these $n(d+1)$ conditions would receive the same model prediction. Figure 5 shows a tree ensemble model with $n=2$ trees of depth $d=2$ and a slice of training data. The model predicts whether a fruit is edible based on 3 features: color, odor, variety. Here’s a simplified overview of how TE2Rules operates on this tree ensemble.

Step 1: Pre-Processing: In this step, TE2Rules transforms each data point from the training data slice into an itemset of $n(d+1)$ tree nodes obtained from its journey through the tree ensemble, treating each node as a separate item. For example, in Figure 5, consider the first data point in the training dataset, described by (color=red, odor=sweet, variety=native). This data point is transformed into the itemset {$t_{0},t_{1},t_{3},u_{0},u_{1},u_{3}$}, encompassing all the nodes it traverses within the tree ensemble. Subsequently, the original training data is depicted as a collection of itemsets, with each data point having a corresponding itemset.

Step 2: Apriori: In this step, TE2Rules finds itemsets that frequently appear alongside positive predictions among all the itemsets found in step 1. To achieve this, TE2Rules retains only the itemsets associated with positive model predictions and applies the Apriori algorithm to find sets of $k^{\prime}$ nodes ($k^{\prime}=1,2,3,\ldots k$) that appear frequently. This step involves running multiple stages of Apriori and in stage $k^{\prime}$, it identifies itemsets with $k^{\prime}$ nodes. The Apriori algorithm is run with user defined parameters for $m$ = min_support and $k$ = num_stages.

Step 3: Itemset-Rule: In this step, TE2Rules converts each itemset found in step 2 into an itemset-rule. An itemset consists of a set of nodes. For a node to be visited by a data point, all decisions along the path from the root to that particular node (i.e. all its ancestors up to the root node) must be satisfied. Each node is represented by the corresponding rule needed to reach it. For example, to reach node $t_{3}$, the data point must satisfy the rule “color=red and odor=sweet”. Similarly, for visiting node $t_{1}$, the data point must satisfy the rule “color=red”. The root node $t_{0}$ is represented by the empty rule, since all data points start their journey from the root node.

Likewise, each itemset can be expressed as a rule formed by combining (via disjunction) the rules for each of its constituent nodes. For example, an itemset with nodes {$t_{1},t_{3},u_{2}$} would be represented by “((color=red) and (color=red and odor=sweet) and (odor=sweet))” = “(color=red and odor=sweet)”. In this way, each itemset found by Apriori is converted into an itemset-rule.

Step 4: High Precision Rules: In this step, TE2Rules transforms every itemset-rule identified in step 3 into the rule: “If itemset-rule Then model prediction = positive” and retains them only if their precision exceeds a user defined threshold of min_precision. The precision of a rule measures its correctness. In this particular context, precision denotes the fraction: count( data points satisfying itemset-rule and model prediction = positive) / count(data points satisfying itemset-rule). By default, TE2Rules uses a min_precision threshold of 0.95. Step 3 identifies itemsets that occur frequently with positives. This step helps in finding itemsets that frequently occur with positives but infrequently with negatives. For example, in Figure 5, the itemset {$t_{2},u_{1}$} representing the rule “color$\neq$red and odor=sweet” occurs only with positives and never with negatives. Hence, TE2Rules would find the rule “If color$\neq$red and odor=sweet, then model prediction = positive” as a possible rule to explain some of the positives.

Step 5: Post-Processing: In this step, TE2Rules selects a small number of rules among all the rules found in step 4 to explain the entire tree ensemble model. This process resembles solving a set cover problem, where each rule covers positives, acting as a set. A greedy algorithm is employed, starting with an empty rule list and successively selecting rules that cover the highest number of positives not already covered by the list. The chosen rule is added to the list, and the process is repeated until all positive instances are covered.

It’s important to note that multiple rules may explain the same data, and the greedy algorithm randomly selects rules in case of ties. Another approach involves having domain experts review all rules generated by TE2Rules, assigning weights based on their alignment with human decision-making. This introduces a weighted set cover problem and addressing it is beyond the scope of this work. In this work, we use the same weight for all rules, and the greedy algorithm is used to address the set cover problem.

TE2Rules uses three user-defined parameters: min_support, num_stages, and min_precision. TE2Rules uses a default value of $0.95$ for min_precision. TE2Rules uses a very conservative value of $0$ as the default value for min_support. This forces TE2Rules to explore all possible rules with support greater than $0$ to explain the positive model predictions. Users can speed up TE2Rules by setting a higher value for min_support, skipping rules with little support in the training data. However, this may result in a slightly reduced fidelity of the rule list mined by TE2Rules. Unless otherwise specified, TE2Rules utilizes these default parameter values in all our experiments. In the results section, we describe the trade-off between fidelity and runtime with varying num_stages.

Example: Here is an example of rule list generated by TE2Rules from a tree ensemble (TE) model. This TE model is an XGBoost model, consisting of 50 trees with a depth of 3 and was trained on the compas dataset. The compas dataset contains outcomes from a commercial algorithm assessing the likelihood of a convicted criminal to reoffend. Positive label indicates a high likelihood of reoffending. The underlying XGBoost model achieved an AUC of 0.765 on training data and 0.724 on test data. TE2Rules was used to explain the predictions of the XGBoost model using 10% of the training data. TE2Rules uses only the model predictions on this slice of training data and does not have access to ground truth labels. TE2Rules was run till stage 3.

TE2Rules identified a list of 10 rules that collectively achieved a fidelity of 0.973 on the training data slice. These rules successfully explained all positive predictions (minority class) with a fidelity of 1.00 on positive model predictions, while achieving a fidelity of 0.956 on the negative model predictions. The rules generalized well to the test data, achieving a fidelity of 0.949 on overall test data, 0.994 on positive predictions, and 0.915 on negative predictions in test data.

The rules found by TE2Rules are shown in Table 1, along with precision and recall of each rules on training/test data. Precision represents the fraction of data points satisfying the rule that are also identified as positive by the model, while recall is the fraction of positive model predictions covered by the rule. Notably, each rule identified by TE2Rules maintains a precision above $0.95$. It is essential to highlight that while these rules are accurate in explaining the model predictions, they may not align with how humans would have arrived at the same decision. These rules only highlight how the model arrived at the decision. These $10$ rules were condensed from $316$ rules found by TE2Rules at the end of Step 4. These selected $10$ rules in Step 5 represent just one of the many possible representations of the model explanations. For alternate representations, human input from domain experts would be necessary to select a different set of rules from the 316 rules based on which ones align closely with human decision-making.

Datasets: We demonstrate the effectiveness of TE2Rules using 3 datasets from domains (like finance, legal sector) where transparency in decision making process is crucial: compas, bank, adult (Larson et al. 2016; Dua and Graff 2017). The compas dataset consists of the results from a commercial algorithm used to assess a convicted criminal’s likelihood of reoffending. The bank dataset consists of results from a marketing campaign by a banking institution on whether a client will subscribe to their term deposit. The adult dataset consists of census data on whether a person has income over 50K$. All these datasets contain demographic attributes of participants like age, gender, race, etc.

Baselines: We compared TE2Rules with two popular baselines: inTrees and deFragTrees.

inTrees goes through each node in the tree ensemble and extracts rules from each node using the decision path to reach the node from its respective root node. For each rule extracted from a node, it assigns the majority label from the support of the rule. Further, it selects a small set of high precision rules and presents it in a falling rule list format.

deFragTrees identifies all possible rules that can be formed out of different node combinations from the tree ensemble. It then simplifies these rules by inducing a probability distribution over the rules and finding the simplest representation of this distribution. In this process, it finds a short falling rule list to represent the tree ensemble.

These algorithms operate at different ends of the spectrum. inTrees mines rules from individual nodes and completely discounts the effects of node combinations from multiple trees. deFragTrees mines rules by simplifying rules from all possible $n$ node combinations from multiple trees. TE2Rules provides a middle ground of exploring rules in stages of $k$ node combinations, with $k=1,2,3,\ldots n$.

We report results of TE2Rules run with stages 1, 2 and 3. deFragTrees requires a parameter to specify the maximum number of rules to mine. We run deFragTrees with 1x, 5x and 10x times the number of rules mined by TE2Rules (with num_stages = 3). Both the baselines (and TE2Rules) take the trained model and a sample of training data (10%) as input to mine rules to explain the model. All explainers are run using the same sampled training dataset, trained model and evaluated using the same test dataset.

Implementation: TE2Rules and deFragTrees are implemented in python while inTrees is implemented in R. We trained our xgboost models in python using scikit-learn and exported them in a format that can be ingested in R. Our implementation of TE2Rules with instructions to reproduce the results can be found here: https://github.com/linkedin/TE2Rules. All experiments were conducted on a 64-bit Ubuntu OS 20.04, with an Intel Xeon 2.4 GHz CPU and 32 GB RAM.

Models: We trained gradient boosted tree ensemble (TE) models with 100, 200, 500 trees with depth 3, 5 for binary classification in python scikit-learn. In all our results, we use red, green, blue colors to denote TE models with 100, 200, 500 trees, respectively. We explain these models using inTrees, deFragTrees and TE2Rules. We report the number of extracted rules and time taken to extract the rules. We evaluate the performance of the rules using fidelity: accuracy of the rules with respect to the model predictions. We report the fidelity of the rules on the test data (overall fidelity) and on the portion of test data on which the model labels it as positive class (positive fidelity). In all these datasets, positive class happens to be the minority class.

We presented a novel approach, TE2Rules to explain a binary tree ensemble (TE) classifier using rules mined specially for a class of interest. We showed that our explainer is faithful (with high fidelity) to the model on both the overall test data and specifically on the minority class. It achieves such high performance in runtimes that are comparable to the state of the art baselines. Further, we show that stopping the algorithm in early stages can tradeoff runtime without loosing much fidelity on positives.