Computing Rule-Based Explanations by Leveraging Counterfactuals

Fix an instance $x_{i}=(f_{i1},\ldots,f_{in})\in D$. A rule component, $RC$, relevant to $x_{i}$, is a predicate of the form $F_{j}\leq f_{ij}$ or $F_{j}\geq f_{ij}$, for some feature $F_{j}$. For an instance $x\in\textsc{Inst}$, we write $RC(x)$ for the predicate defined by $RC$. In other words, if $x=(f_{1},\ldots,f_{n})$, then $RC(x)$ asserts $f_{j}\leq f_{ij}$ or $f_{j}\geq f_{ij}$ respectively.

A rule relevant to $x_{i}$ is a set of rule components, $R=\{RC_{1},\ldots,\-RC_{c}\}$. We write $R(x)$ for the predicate that is the conjunction of all rule components. The cardinality of the rule is $c$. Notice that, in order to assert equality for some feature, $F_{j}=f_{ij}$, we need two rule components, namely both $\leq$ and $\geq$, therefore $0\leq c\leq 2n$. We denote by $\textsc{Inst}_{R}$ the set of all instances that satisfy $R$:

Consider an instance $x_{i}$ that is classified as “undesired”, $C(x_{i})\leq 0.5$, and let $R$ be some rule. Rudin and Shaposhnik (Rudin and Shaposhnik, 2019) propose three simple properties that, when satisfied, can be used to offer $R$ as explanation for the bad outcome on the instance $x_{i}$:

1. (1)

   Relevance: the input instance $x_{i}$ satisfies $R$, in other words $x_{i}\in\textsc{Inst}_{R}$.

2. (2)

   Global Consistency: all instances $x$ in Inst that satisfy the rule $R$ are “undesired”: $\forall x\in\textsc{Inst}_{R}$, $C(x)\leq 0.5$.

3. (3)

   Interpretability: the rule should be as simple as possible, in other words it should have a small cardinality.

In this paper we consider only rules that are relevant to the instance $x_{i}$, hence the first property is satisfied by definition. Our goal is: given $x_{i}$ with a bad outcome, compute one (or several) globally consistent, interpretable rule $R$.

The trivial rule relevant to the instance $x_{i}$ is the rule $R_{triv}$ that contains all $2n$ rule components relevant to $x_{i}$; $R_{triv}=\{F_{1}\leq f_{i1},F_{1}\geq f_{i1},\ldots,F_{n}\leq f_{in},F_{n}\geq f_{in}\}$. In other words, $R_{triv}(x)$ asserts that the instance $x$ has exactly the same features as the instance $x_{i}$. Since $x_{i}$ is undesired, $R_{triv}$ is globally consistent. However, its cardinality is very large, $2n$, and we say that the trivial rule is not “interpretable”. Instead, we seek a minimal set of rule components that are still globally consistent.

In general, checking global consistency is computationally hard. The number of possible instances, $|\textsc{Inst}|$, is exponentially large in the number of features, and checking all of them is intractable. For that purpose, the authors in (Rudin and Shaposhnik, 2019) relax the global consistency requirement, and check consistency only relative to the database $D=\{x_{1},\ldots,x_{m}\}$. We call this property Data Consistency: $\forall x_{k}\in D\cap\textsc{Inst}_{R}$, $C(x_{k})\leq 0.5$. Anchor (Ribeiro et al., 2018) does consider global consistency, but only aims to enforce it “with high probability”, in other words $\frac{|\{x\in\textsc{Inst}_{R}|C(x)\leq 0.5\}|}{|\textsc{Inst}_{R}|}$ should be close to 1. As we will see in Section 5, explanations returned by both MinSetCover (Rudin and Shaposhnik, 2019) and Anchor (Ribeiro et al., 2018) often fail to satisfy global consistency.

While a rule-based explanation identifies a set of features whose values necessarily lead to an undesired outcome, a counterfactual explanation identifies some features whose values, when updated, could possibly lead to a desired outcome. Formally, we fix an instance $x_{i}$ with a “bad” outcome, and define a counterfactual explanation to be some other instance $x_{cf}\in\textsc{Inst}$ with a “good” outcome, $C(x_{i})>0.5$. We often represent $x_{cf}$ by listing only the set of features where it differs from $x_{i}$.

A counterfactual $x_{cf}$ is required to satisfy two properties. First, $x_{cf}$ must be feasible and plausible w.r.t. $x_{i}$. Feasibility imposes constraints on the new values, e.g. income cannot exceed (say) $1M, while plausibility imposes constraints on how the new values in $x_{cf}$ may differ from the old values in $x_{i}$, e.g. gender cannot change, or age can only increase, etc. We refer to these predicates as PLAF (plausibility/feasibility) predicates, and denote the conjunction of all PLAF predicates by $P(x_{cf})$. Formally, a PLAF predicate is a formula of the form $\Phi_{1}\wedge\cdots\wedge\Phi_{m}\Rightarrow\Phi_{0}$, where $\Phi_{i}$ is a predicate over the features of $x_{i}$ and $x_{cf}$. One example from (Schleich et al., 2021) is $\texttt{gender}_{CF}=\texttt{gender}_{i}$, which asserts that gender cannot change; another example is $\texttt{education}_{CF}>\texttt{education}_{i}\Rightarrow\texttt{age}_{CF}\geq\texttt{age}_{i}+4$, which asserts that, if we ask the customer to get a higher education degree, then we should also increase the age by at least 4 years. Second, we score counterfactuals by how many changes they require over $x_{i}$. Given a distance function $dist(x,x^{\prime})$ on Inst, the counterfactuals that satisfy the PLAF constraints are ranked by their distance from $x_{i}$.

A counterfactual explanation system takes as input an instance $x_{i}$ with a “bad” outcome, a PLAF constraint $P(x)$, and a distance function $dist(x,x^{\prime})$, then returns a rank list of counterfactuals that satisfy $P$ and are closed to $x_{i}$.

Different types of explanations provide the users with very different kinds of information. For an intuition into their differences, consider a user Bob who has applied for life insurance, and was denied.

The SHAP score (Lundberg and Lee, 2017), a popular form of explanation, assigns a fraction to each feature, for example: $\texttt{AGE}=35\%$, BLOOD-PRESSURE = 20%$,\texttt{SMOKING}=10\%$, $\ldots$. This defines a clear ranking of the features, but it has limited value for the end user Bob who was denied. We do not consider the SHAP score in this paper.

An example of a counterfactual explanation is: “change SMOKING from true to false”. This has a clear meaning: if Bob quits smoking, he will get approved for life insurance. However, if Bob’s friend Charlie also smokes, yet was approved, then Bob will feel that he was treated unfairly.

A rule based explanation looks like this: “everybody who has $\texttt{SMOKING}=\texttt{true}$ and $\texttt{BLOOD-PRESSURE}\geq 140$ will be denied”. This does not provide Bob with any actionable advice, but it assures him of the fairness of the decision.

We start with a simple lemma.

Fix an instance $x_{i}=(f_{i1},\ldots,f_{in})$ with a bad outcome. For any other instance $x=(f_{1},\ldots,f_{n})\in\textsc{Inst}$, we will construct a dual rule $R_{x}$ consisting of all rule components relevant to $x_{i}$ that are false on $x$, as follows. If $f_{j}>f_{ij}$ then we say that the rule component $F_{j}\leq f_{ij}$ conflicts with $x$; if $f_{j}<f_{ij}$ then the rule component $F_{j}\geq f_{ij}$ conflicts with $x$. In other words, an $RC$ conflicts with $x$ iff it is relevant to $x_{i}$ and $RC(x)$ is false. The dual of $x$ is the rule $R_{x}$ consisting of all components that conflict with $x$. We combine the rule components in the duals with $\vee$ instead of $\wedge$. For a simple example, if $x_{i}=(F_{1}=10,F_{2}=20,F_{3}=30)$ and $x=(F_{1}=5,F_{2}=90,F_{3}=30)$ then $R_{x}=(F_{1}\geq 10\vee F_{2}\leq 20)$. We prove:

The theorem says that globally consistent rules and counterfactuals are duals to each other. We will exploit the first direction of the duality, and show how to use counterfactuals to compute efficiently globally consistent rules.

We now describe how to use a counterfactual explanation system to compute a relevant, globally consistent, and informative rule $R$ for an instance $x_{i}$. This is the key part of the algorithms we proposed in Section 4.2 and 4.3.

Theorem 3.2 already implies a naive algorithm for this purpose. Use a counterfactual system to compute all counterfactuals $x_{cf,1},\ldots,x_{cf,m}$ for $x_{i}$, construct $S\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{R_{x_{cf,1}},\ldots,R_{x_{cf,m}}\}$ the set of all their duals, and output all minimal set covers $R$ of $S$. Each set covering $R$ of $S$ is a globally consistent rule, because, otherwise there exists an instance $x$ such that $R(x)=1$ and $C(x)>0.5$. This implies that $x$ is a counterfactual for $x_{i}$, but is not among $x_{cf,1},\ldots,x_{cf,m}$ (because it disagrees with each $x_{cf,j}$ on at least one feature), contradicting the assumption that the list of counterfactuals was complete. However, we cannot use this naive algorithm, because counterfactual systems rarely return the complete list of counterfactuals.

Our solution is based on computing the rule $R$ incrementally. Starting with $R=\emptyset$, we increase $R$ with one rule component at a time, until it becomes globally consistent, as follows. Assume $R$ is any rule relevant to $x_{i}$, and suppose that $R$ is not globally consistent. We proceed as follows.

Step 1 Construct the predicate $R(x^{\prime})$ associated with the rule $R$; we will use it as a PLAF predicate in the next step.

Step 2 Using the counterfactual explanation system, find a list of counterfactuals $x_{cf,1},\ldots,x_{cf,k}$ for $x_{i}$ that satisfy the PLAF predicate, i.e. $R(x_{cf,j})=1$ for all $j=1,k$. The number $k$ is usually configurable, e.g. $k=10$. If no such counterfactual is found, then $R$ is globally consistent.

Step 3 For each $j=1,k$, compute the dual $R_{x_{cf,j}}$ of each counterfactual $x_{cf,j}$, i.e. the set of all rule components that conflict with $x_{cf,j}$. We notice that $R_{x_{cf,j}}$ is disjoint from $R$, because $x_{cf,j}$ satisfies the PLAF $R(x)$. Let $S=\{R_{x_{cf,1}},\ldots,R_{x_{cf,k}}\}$ be the set of all the dual rules.

Step 4 For each minimal set that covers $R_{0}$ of $S$, construct the extended rule $R\cup R_{0}$, and repeat the process from Step 1.

We note that our use of PLAF rules differs from their original intent. Rather than constraining the counterfactual, we use them to check if the rule candidate $R$ is globally consistent, and, if not, then to extend it.

GeneticRule  is our “naive” algorithm which generates rules using a genetic algorithm. The pseudo-code is shown in Algorithm 1. The inputs are an instance $x$, the classifier $C$, and a dataset $D$. The output is a set of rules that explain instance $x$ for classifier $C$. In addition, there are five integer hyperparameters: $q>0$ represents the number of rules kept after each iteration, $k\leq q$ is the number of rules that the algorithm returns to the user, $s$ is the number of samples taken from Inst to check for global consistency, $m$ and $c$ specify the number of new candidates that are generated during mutation and respectively crossover. For instance, we use the following settings in most of the experiments: $q=50$, $k=5$, $s=1000$, $m=3$, $c=2$. We refer to Sec. 5 for an explanation why we chose these settings.

GeneticRule first computes the initial population of rule candidates. We define the initial population to be all possible rule candidates with exactly one rule component. The initial candidates are likely not valid and consistent rules. Thus, GeneticRule repeatedly applies mutate and crossover to generate new candidates, computes the fitness score (via selectFittest) for each candidate, and then selects the $q$ fittest candidates for the next generation. This process is repeated until we find $k$ candidates that are consistent on both the dataset $D$ as well as $s$ samples from the more general Inst space. We further check that the top-$k$ candidates are not in the set of new generated candidates CAND, which means that they were stable for at least one generation of the algorithm.

The mutate operator generates $m$ new rule candidates for each candidate $R\in\text{POP}$. First, the operator finds the set $S$ of all rule components that are not part of $R$. Then, it generates each new candidate by sampling (without replacement) a single component from $S$ and adding it to $R$. Adding a single component at a time keeps the cardinality of the rules low and makes it less likely to introduce redundant rule components.

The operator crossover generates $c$ new candidates for each pair of candidates, $R_{i}$ and $R_{j}$. First, we compute the set $S=R_{i}\cup R_{j}$ of all rule components in $R_{i}$ and $R_{j}$. Then, we randomly sample $t$ components from $S$ to form a new candidate. We use $t=max(|R_{i}|,\,|R_{j}|)+1$, in order to keep the cardinality of the new candidate low. We repeat this sampling process $c$ times to generate $c$ new candidates for every pair of candidates in the population.

After generate new candidates via mutation and crossover, the selectFittest operator calculates the fitness score of each candidate in POP, sorts the candidates by in descending order of their fitness scores, and returns the top $q$ candidates. We give more details on the fitness scores in Sec. 4.4.

We note that GeneticRule cannot guarantee that the returned rules are globally consistent. Since we are only able to check global consistency for a sample of Inst, we can only guarantee that the rules are data consistent and are likely to be globally consistent.

We next explain GeneticRuleCF, which extends GeneticRule with a counterfactual explanation model to generate and verify rule candidates. The pseudocode is provided in Algorithm 2.

The main extension to GeneticRule is the CFRules function. It takes as input a set of rule candidates and generates new candidates by computing the counterfactual explanations for each input candidate. As outlined in Sec. 3.2, this process involves multiple steps: it computes the PLAF predicates for a given input candidate, then it computes the counterfactual explanation for this candidate, and finally returns the dual of the counterfactual explanation as a new candidate. We use CFRules to extend both the initial population as well as the candidate pool in the main loop of the genetic algorithm.

We further use the counterfactual model in the consistentCF function, which verifies that the top rule candidates are globally consistent. For a given candidate, the function runs the counterfactual model to generate a counterfactual example. If no such counterfactual example can be found, we conclude that the rule is globally consistent. As a consequence, GeneticRuleCF  provides higher global consistency guarantees than GeneticRule.

Performance optimizations. Since calling the counterfactual explanation model is expensive, we only run CFRules once for every three iteration or when all top-k candidates are marked as data consistent. This setting gave us the best performance improvements with minimal effects on the generated rules in our experiments.

We further cache whether or not we were able to generate counterfactuals for each rule candidate. This ensures that we only need to run the counterfactual model once per candidate, and not multiple times for CFRules and consistentCF.

The algorithm has an optional post process stage (not shown in the pseudo code), to ensure that the returned rules have no redundant components. For each returned rule, we remove one rule component at a time, and check if the rule without this component is still verified by consistentCF. If so, the removed component is redundant and can be removed from the rule. We repeat this process until the returned rules do not have any redundant component.

GreedyRuleCF does not use a genetic algorithm, but instead repeatedly utilizes the underlying counterfactual explanation model to greedily find rule candidates with small cardinality. The pseudocode is provided in Algorithm 3.

GreedyRuleCF generates the initial population by running CFRules on the empty rule candidate, and maintains the population sorted in increasing order with respect to the cardinality of the rule candidates. Then, the algorithm repeatedly takes the candidate with the smallest cardinality, generated new candidates by CFRules on this candidate, removes the considered candidate from and adds the new candidates to the population. The algorithm stops when the candidate with the smallest cardinality is found to be consistent by consistentCF.

In each iteration, GreedyRuleCF removes the inconsistent rule candidate with the smallest cardinality, and adds candidates which have cardinalities strictly larger than the removed one. Therefore, the cardinality of the rules in the population are monotonically increasing. The algorithm is guaranteed to terminate with an consistent rule, since candidates can have at most $2n$ rule components, where $n$ is the number of variables in $D$.

We describe the fitness score that is used to rank the rule candidates in the selectFittest function. For a given rule, the fitness score is based on its degree of consistency and its cardinality (a proxy of interpretability). We define three degrees of consistency:

1. (1)

   The rule failed data consistency ($FDC$): it violates instances in the database $D$;

2. (2)

   The rule failed global consistency($FGC$): it is data consistent (satisfies all instances in the dataset $D$), but fails for some instances in Inst;

3. (3)

   The rule is globally consistent ($GC$): The rule is consistent for both the dataset $D$ as well as the instances from Inst.

The fitness score of a rule $R$ is defined as follows. Suppose the database has $m\stackrel{{\scriptstyle\mathrm{def}}}{{=}}|D|$ instances, each with $n$ features. Let $VD$ denote the number of instances in $D$ that violate $R$. If $VD=0$, then we sample $s$ instances from Inst and denote by $VS$ the number of samples that violate $R$. The fitness score $score(R)$ is:

The expressions (including the coefficients 0.25, 0.75) were chosen to ensure that the score function always ranks candidates in a given level higher than the candidates in the levels below. For instance, the score of a global consistent rule candidate, GC, is always higher than those of levels FDC and FGC. If two candidates are in the same level, the one with smaller cardinality is ranked higher. This ranking ensures that we prioritize candidates that have better consistency guarantees.

In this section, we introduce the datasets, systems, and the setup for all our experiments.

Datasets and Classifiers. We consider four real datasets:

1. (1)

   Credit Dataset (Yeh and hui Lien, 2009): used to predict the default of the customers on credit card payments in Taiwan;

2. (2)

   Adult Dataset (Kohavi, 1996): used to predict whether the income of adults exceeds $\$50$K/year using US census data from 1994;

3. (3)

   FICO Dataset (FICO, 2019): used to predict the credit risk assessments.

4. (4)

   Yelp Dataset (Yelp, 2017): used to predict review ratings that users give to businesses.

Table 1 presents key statistics for each dataset and the corresponding classifiers we used. Credit and Adult are from the UCI repository (Dua and Graf, 2017) and are commonly used in the machine learning explanation fields. We utilize the Decision Tree classifiers for them. FICO is from the public FICO challenge, which is an Explainable Machine Learning Challenge that inspires a lot of research in this field. For the FICO dataset, we use the two-layer neural network classifier, where each layer is defined by logistic regression models. Yelp is the largest dataset we consider, and we use complex MLPClassifier with 10 layers as classifier.

In order to demonstrate whether the systems can recover the rules when these are known (ground truth is known), we create synthetic classifiers for the Credit dataset. The classifier is defined by a rule, with a number of rule components, and in the experiments we check whether the explanation algorithm can recover the rule that defines the classifier. As usual, our algorithms do not know the classifier, but access it as a black box. We expect real rule-based explanations to consists of a relatively small number of rule components (under 10; otherwise they are not interpretable by a typical user), so in this synthetic experiment we created classifiers with 2, 4, 6, and 8 rule components respectively. We repeated our experiments for 1000 randomly generated synthetic classifiers.

In order to ensure that our evaluation is fair, we apply the same preprocessing for all the systems.

Underlying Counterfactual Explanation Model. To identify the best counterfactual explanation model for our algorithm, we benchmarked thirteen different counterfactual explanation models (GeCo (Schleich et al., 2021), Actionable Recourse (Ustun et al., 2019), CCHVAE (Pawelczyk et al., 2020a), CEM (Dhurandhar et al., 2018), CLUE(Antoran et al., 2021), CRUDS (Pawelczyk et al., 2020b), Dice (Mothilal et al., 2020), FACE (Poyiadzi et al., 2020), Growing Spheres (Laugel et al., 2018), FeatureTweak (Tolomei et al., 2017), FOCUS (Lucic et al., 2019), REVISE(Joshi et al., 2019), Wachter (Wachter et al., 2017)) using the Carla benchmark (Pawelczyk et al., 2021). We report the results of this evaluation in our public GitHub repository: https://github.com/GibbsG/GeneticCF.

We find that GeCo is only one among all of these thirteen counterfactual explanation models that can robustly generate counterfactual explanations with flexible PLAF constraints and without redundant feature changes. Therefore, we decided to choose GeCo as the counterfactual explanation model for GeneticRuleCF  and GreedyRuleCF  and to help verify the globally consistency for the rules returned by all of the considered algorithms.

Considered Algorithms. We benchmark our three algorithms, GeneticRule, GeneticRuleCF, and GreedyRuleCF, against two existing systems: Anchor (Ribeiro et al., 2018) and MinSetCover (Rudin and Shaposhnik, 2019).

Anchor (Ribeiro et al., 2018) generates rule-based explanations (i.e. anchors) by the beam-searched version of pure-exploration multi-armed bandit problem. It starts with an empty rule. In each iteration, for each rule, Anchor (1) randomly selects $m$ possible rule components and add each of the possible components to the rule to create $m$ new rules, (2) evaluates all the rules, (3) and then selects top $n$ rule to keep for the next iteration. It stops when reaching a convergence for the rules. When evaluating whether a rule is consistent, Anchor samples $k$ instances in the whole space that are specified by the rule and considers the rule as consistent if all of those $k$ instances are “undesired”.

MinSetCover (Rudin and Shaposhnik, 2019) generates rule-based explanations using the minimum set cover problem. They consider the $m$ instances in the database as elements and the binary predicates ($\leq F_{i}$ or $\geq F_{i}$) as sets. Then, finding a minimum rule with data consistency is reduced to finding the minimum number of binary predicates that covers all those “undesired” instances. Therefore, MinSetCover reduces the rule-based explanations problem to finding a minimum set cover problem and solves it by Linear Programming. Note that this approach can only be applied on the historical database $D$ and does not consider instances outside this database.

Parameter Choice. As discussed in Section 4.1, there are five hyperparameters in our systems: the number $k$ of rules that the algorithm returns to the user, the number $q$ of rules kept in each iteration, the number of new candidates that are generated during mutation ($m$) and crossover ($c$), the number $s$ of samples from Instduring evaluation. While $k$ depends on the user’s requirements, the other parameters determine the tradeoff between the quality of the returned rules and the time it takes to return them. For instance, if we increase the number $q$ of rules kept in each iteration, it is possible that we find rule with higher quality, but we also need to evaluate and verify a larger number of candidates in each iteration of the algorithm. We performed several pilot experiments to find the combination of hyperparameters in order to ensure that the rules are returned in a reseanonble time with acceptable quality. We found $q=50$, $s=1000$, $m=3$, $c=2$ to be best settings for the experiments with the Adult, Credit and FICO datasets. For the Yelp dataset, we use $q=20$, $s=5000$, $m=3$, $c=2$.

For GeneticRuleCF, we enable the optional post reduction stage, but limit it to reduce only the top rule to limit the overhead.

Experimental pipeline. The data is pre-processed as required by the classifiers: all categorical variables in the Credit and Yelp dataset are integer encoded, while those in the Adult are one-hot encoded. We use decision tree classifer for the Credit and Adult dataset, and multi-layer neuron network for Fico and Yelp datasets. This way we explore different types of variable encodings and classifiers. The post-processed datasets retain the same number of instances (tuples) as the original data, as shown in Table 1. Recall that one explanation is for one single user, yet in order to provide explanation to one instance, the system needs to examine at least the entire dataset $D$, or, better, the entire space of instance Inst. If a system returns more than one explanation for the user, then we retained the top explanation. In short, for one user (instance) we run each system to find rule-based explanations, and retain the top-ranked rule. We measure the run time needed to find the explanation, then evaluate its quality. We then repeat this process for 10,000 users (i.e. we compute 10,000 explanations), to get a better sense of the variance of our findings, for all systems. Thus, in our experiments each system returns 10,000 rules, i.e. one explanation for each user.

Evaluation Metrics. We utilize the following two metrics, which are adapted from our principles of rules, to evaluate the quality of the generated rules: (1) Global Consistency: we can not find any instance that is specified by the rule and is classified as “desired” by the classifier; (2) Interpretability: the cardinality of the rule (i.e. the number of rule components). To be specific, we check whether there are redundant components from the return rules and whether the rule returned is minimal. While GeneticRule  and GeneticRuleCF  generate multiple rule-based explanations for each instance, we only consider the top one rule-based explanation in our evaluation.

Setup. We implement GeneticRule, GeneticRuleCF  and GreedyRuleCF  algorithms in Julia 1.5.2. All experiments are run on an Intel Core i7 CPU Quad-Core/2.90GHz/64bit with 16GB RAM running on macOS Big Sur 11.6.

We compare all considered algorithms in terms of the quality of generated rules on the datasets. First, we consider synthetic classifiers and then we evaluate the considered systems on real classifiers.

Synthetic Classifiers. Recall that here the classifier is a rule itself, and the task of the system is to find an explanation that is precisely that rule. We categorize the rule-based explanation into three categories: (1) the rule exactly matches the classifier (consistent and minimal); (2) the rule is consistent but has redundant components, i.e. it is a strict superset of the classifier; or (3) the rule is inconsistent with the classifier, i.e. it misses at least one rule component of the classifier. We report the percentage of rules that fall into the three categories for each considered algorithm.

Figure 1 presents the results of our evaluation on the five algorithms over $1000$ synthetic classifiers with of $2$, $4$, $6$, and $8$ rule components respectively for the Credit dataset.

GeneticRuleCF  and GreedyRuleCF  can always find the consistent and minimal rules ($100\%$) regardless of the cardinality of the rule. GeneticRule  can always find the consistent and minimal rules when the cardinality of the classifiers is small, but it generates some inconsistent rules ($11\%$) for classifiers with 8 rule components. This exemplifies the benefits of including a counterfactual explanation system in the rule generation algorithm.

Both Anchor and MinSetCover do not always find the consistent rules even with redundancy when the cardinality of the classifers is 2 ($61.7\%$ and $44.6\%$). For larger cardinalities, they rarely generate consistent rules: only $7.8\%$ of the rules in Anchor and $1.3\%$ of the rules in MinSetCover are consistent when the cardinality of the rules bebind the classifiers are $6$. Anchor is more likely to find consistent rules than MinSetCover, but the rules generated from Anchor are mostly redundant. MinSetCover limits the cardinality of the generated rules and does not return any rules with redundant components. As a result, however, it often returns rules with fewer components than expected. In conclusion, our algorithm outperforms both Anchor and MinSetCover in terms of consistency and interpretability for the considered synthetic classifiers.

Real Classifiers. For the real classifiers, we categorize each rule $R$ in one of the following five categories:

1. (1)

   Failed data consistency ($FDC$): there is an instance in the dataset $D$ where the rule fails.

2. (2)

   Failed global consistency ($FGC$): all instances in $D$ satisfy the rule, but it fails on some an instance in Inst.

3. (3)

   Globally Consistent ($GC$) but redundant: the rule holds on all instances in Inst, but has some redundant rule components;

4. (4)

   Globally Consistent ($GC$), non-redundant, but not minimal: the rule is globally consistent and non-redundant, but is not of minimum size: there exists a strictly smaller globally consistent rule.

5. (5)

   Globally Consistent ($GC$) and minimal: has the smallest number of rule components.

In contrast to synthetic classifiers, we do not know the correct rules for real classifiers. We can, nevertheless, check whether a rule has redundant components by removing one of its rule components and checking if it is still consistent. If so, the rule component is redundant as the removed feature is not required. When checking the cardinalty of the miniml rules, we check all possible rule sorted by the cardinalty until finding a consistent one. Then, all consistent rules with that cardinality are considered as minimal.

Recall that our test for global consistency consists of running the counterfactual explanations model (in our case GeCo) as a proxy: we run GeCo subject to the constraints provided by the rule and, if GeCo can not find a counterfactual explanation, then we conclude that the rule is globally consistent.

Figure 2 shows our evaluation results for the Credit dataset with a decision tree classifier, the Adult dataset with a decision tree classifier, the Fico dataset with a multi-layer neural network classifier, and the Yelp Dataset with a MLP classifier, respectively.

GeneticRuleCF  and GreedyRuleCF  can always find globally consistent rules without redundancy for the Credit and Adult datasets, while they sometimes return inconsistent rules for Fico (9% and 1%) and Yelp (16% and 23%). This is because GeCo is unstable for these algorithms, and does not always find counterfactual examples. If the underlying counterfactual system is stable, GeneticRuleCF  and GreedyRuleCF  always find globally consistent rules. Further, GreedyRuleCF  is always able to find consistent rules that are minimal. In contrast, GeneticRuleCF  finds rules without redundancy, but the rules are not always minimal (the returned rule often have one or two additional rule components than the minimal rule). This shows that GreedyRuleCF  is the only algorithm that is able to find consistent, non-redundant, and minimal rules.

GeneticRule  is not guaranteed to find the globally consistent rules. For instance, for the Credit dataset 37.6% of the generated rules by GeneticRule  are not globally consistent. Unlike the synthetic classifiers, the real classifiers are more complex. And GeneticRule  only uses a sample from Instto verify for global consistency. Since the real classifiers are complex, it is possible that it finds rules that are consistent on the sample but not on the entire instance space. This further demonstrates the necessity of the counterfactual system to verify rules, as it helps to explore the instance space more broadly.

In GeneticRule  algorithm, we use a heuristic random selection to choose the rule components, which makes rules less likely to include redundant components compared with Anchor (Rules from Anchor usually have 3 or 4 redundant components, while those from GeneticRule have 1 or 2). When using GeCo in the rule-building stage, we assure that the new added rule component is necessary and not redundant. This explains the decreasing pattern in the average cardinality of the rules from Anchor and GeneticRule, to GeneticRuleCF, and GreedyRuleCF. For MinSetCover, it always finds rule-based explanations that are only data consistent, but rarely globally consistent. Thus, most of the rules returned by MinSetCover have small cardinality but are not globally consistent. This further demonstrates that our algorithms can find both consistent and interpretable rules and beat Anchor and MinSetCover on the real dataset and classifiers.

We measure the runtime of all considered algorithms for the synthetic and real classifiers. In particular, we investigate how the runtime is affected by the cardinality of the synthetic classifiers, as well as the sizes of the the different datasets.

Synthetic classifiers. Figure 3 shows the runtime of algorithms in synthetic classifiers with $2$, $4$, $6$, and $8$ rule components.

GeneticRule, GeneticRuleCF, and GreedyRuleCF  usually consume less time than Anchor and MinSetCover, regardless of the cardinality of rules behind the classifier. In particular, for the classifier with 8 rule components GeneticRule  and GreedyRuleCF  are about $5\times$ faster than Anchor and $1.8\times$ faster than MinSetCover; GeneticRuleCF  is about $3.9\times$ faster than Anchor and $1.3\times$ faster than MinSetCover.

We find that the larger the cardinality of the classifier rules, the longer the algorithms take to return a result. This is expected, since it takes more effort to build more complex rules. When the cardinality of classifier rules increases from $2$ to $6$, GeneticRule  is more than 3$\times$ slower, GeneticRuleCF  is 2.8$\times$ slower, and GreedyRuleCF  is only 1.7$\times$ slower. GreedyRuleCF  is less affected by the increase in the cardinality. For instance, it takes almost the same time for classifiers with 4 and 6 rule components. This is because the algorithms can add several required rule components to a rule in every iteration with the counterfactual explanations, while in the traditional approach we can only add one more rule component to a rule in each iteration.

Real Classifiers. Figure 4 compares the runtime with real classifiers for each considered algorithm and dataset.

For the Credit dataset, the runtimes for all algorithms are similar, while GeneticRule  is the fastest and MinSetCover is the slowest. Credit has $14$ variables and thus the decision tree classifier is relatively small. This demonstrates that our GeneticRuleCF  and GreedyRuleCF  algorithms can efficiently generate consistent rule-based explanations without extra cost for a moderately complex datasets and classifiers.

For Adult, GeneticRule, GeneticRuleCF, and GreedyRuleCF  are all significantly faster than Anchor and MinSetCover. For instance, GeneticRule  is more than $6\times$ faster than Anchor and MinSetCover, whereas GreedyRuleCF  is more than $2\times$ faster. This performance difference can be explained by the fact that the dataset contains many variables that were one-hot encoded during preprocessing, which significantly increases the number features. Whereas Anchor and MinSetCover scale poorly in the number of features, our algorithms can treat one-hot encoded features as one feature. As a consequence, our algorithms can significantly outperform the existing systems in the presence of one-hot encoded variables.

For Fico and Yelp, GeneticRuleCF  and in particular GreedyRuleCF  take much more time. This mainly because we use a strong verification mechanism in the two algorithms. The verification mechanism prevents the algorithms from stopping until they find a consistent rule, whereas the other algorithms might stop early and return inconsistent rules (c.f., Figure 2).

Another reason for the slower performance is the performance of the underlying classifier, which is particularly apparent for the Fico dataset. Since our algorithms use a counterfactual explanation system, GeneticRuleCF  and GreedyRuleCF  call the classifier significantly more often than Anchor and MinSetCover. Thus if the underlying classifier is slower, GeneticRuleCF  and GreedyRuleCF  are also much slower. Table 2 presents the runtime for classifiers and GeCo on each dataset. For the Fico dataset, the classifier is more than 25$\times$ slower than that of the Credit dataset and 13 $\times$ slower than that of the Adult dataset. This led to GeCo taking 22.2$\times$ and 14.7$\times$ more time with the classifier of the Fico dataset compared to that of the Credit dataset and the Adult dataset. The increase of runtime in GeCo significantly increases the runtime of GeneticRuleCF  and GreedyRuleCFas they rely on the GeCo to verify the rules. We will discuss more details in the microbenmarks in Sec 5.4.

The Yelp dataset contains millions of instances and we use a significantly more complex classifier. For this reason, it is much harder for the algorithms to generate and verify rules. This is visible for our algorithms but also for MinSetCover, whose runtime is highly depend on the number of instances in the dataset. However, even for the slow classifier as on Fico Dataset, and large dataset as Yelp dataset, our GeneticRuleCFcan always generate rules in time that is at least comparable, and at times significantly faster, than Anchor and MinSetCover. This shows the power of using a genetic algorithm to build the rules with less run time.

In summary, GeneticRuleCF  can always finish in reasonable runtime to generate high quality rules regardless of the classifier speed or the size of the dataset. GreedyRuleCF  typically generates rules with the highest quality, and it is fast when the classifier and dataset have moderate size. For complex classifiers over large datasets, however, GeneticRuleCF  is more efficient than GreedyRuleCF.

In this section, we present the results for the microbenchmarks. We compare the runtime break down for each main operators for GeneticRuleCF, the number of rule components explored for GeneticRuleCF, GreedyRuleCF  and GeneticRule, and the number of rule components explored by the counterfactual explanation systems for GeneticRuleCF  and GreedyRuleCF. We evaluate our algorithms by explaining $100$ instances on Adult Dataset, Credit Dataset, Fico Dataset and $20$ instances on Yelp Dataset with corresponding classifiers.

Breakdown of Runtime. Figure 7 presents the results for the runtime breakdown. We choose to not include GreedyRuleCF  since almost all of its runtime is from the counterfactual system. This is because GreedyRuleCF  only uses the counterfactual system, GeCo, to build and verify rules. Prep (i.e. Preparation) captures the runtime to compute the rule space and to build the initial population. Reduction captures the timed used to removed the redundant components from the returned rules using the counterfactual explanation systems. The runtime for selectFittest (Selection), Crossover, Mutate, and CFRules is accumulated over all iterations.

As discussed in Section 4.2, we only run the counterfactual explanation once in the function CFRules for each rule candidate to optimize the performance. This also gives us the information we need for function consistentCF which used in selectFittest. Therefore, we do not run counterfactual explanations in the selectFittest and the time used by function CFRules captures the time used by the counterfactual system in building the rules. And the total time used by the counterfactual system is the sum of the runtime in CFRules and Reduction.

The results show that the CFRules and Reduction are the most time-consuming operations. This is not surprising since these two operations rely on the counterfactual system, which is costly. And thus, the majority of the runtime is consumed by the counterfactual system. If we can reduce the runtime for the underlying counterfactual system, we would like to see a huge gain in the runtime of our algorithms.

Number of Candidate Rules Explored. Figure 7 shows the number of candidates explored for each of the algorithms. The result shows that our optimizations in GeneticRuleCF  and GreedyRuleCF  effectively limit the total number of rules explored in the Credit and Adult datasets when the classifier is moderately complex and guide GeneticRuleCF  and GreedyRuleCF  to search candidates that are more likely to be consistent. When the classifier is complex as in the Fico and Yelp datasets, our optimizations prevent GeneticRuleCF  and GreedyRuleCF  from stopping early with inconsistent rules and push the algorithms to explore more rules until finding a real consistent one.

The Number of GeCo Runs. Figure 7 presents how many times we use GeCo in each of the algorithms in the four datasets. For moderate dataset and classifiers, like Adult and Credit, the number if rules explored by GeneticRuleCF  and GreedyRuleCF  are similar. However, when the datasets and classifiers become large and complex, like Fico and Yelp, the genetic algorithm in GeneticRuleCF  significantly reduces the number of runs using the counterfactual systems (6 times fewer in the Fico dataset and 35 times fewer in the Yelp dataset). This explains why the GeneticRuleCF  is more efficient than GreedyRuleCF  for large datasets with complex classifiers.