Recent advances in machine learning and in particular deep learning have led to models becoming increasingly complex and less interpretable. This has led to a surge in the field of explainable AI (XAI) which aims to understand and interpret predictions made by such models. One significant direction is that of generating counterfactuals that can help in providing rich causal explanations. In this work, we present a novel counterfactual generation algorithm, with an underlying monotonic constraint respecting classifier. The generated counterfactuals are realistic and the end-user can make changes to only a few features, allowing them to make amendments easily. We demonstrate the results of our algorithm and show how this technique can generate counterfactuals closer to the query with improved coverage, while incorporating domain knowledge in the form of monotonic constraints.
In recent years, there have been quite a few interesting research papers reporting the applicability
of Case Based Reasoning (CBR) in facilitating better explanations [
In this paper, we assume a twin-system context [
The rest of the paper is organized as follows. In Section 2, we introduce notation and present background information on counterfactual explanations. Section 3 investigates the current approaches to generate counterfactual explanations and the problems they are plagued by. Section 4 presents the formal approach and performance measures, and Section 5 elaborates the data sets and experiment results. Finally, we draw conclusions and discuss future steps in Section 6.
In this section, we introduce notation and provide background on counterfactual explanations. Notation: We use a case base containing cases, each of which is a vector of features ∈ ℝ and label ∈ {−1, +1} . We refer to the set of features in the case base as ℱ. Further, is used to index attribute in case . It is important to note that we assume the positive class to be the desired outcome (e.g., loan application approved). Additionally, we also assume access to a classifier that allows the imposition of feature-wise monotonic constraints prior to the training process.
Counterfactual Explanations: Given a query ∈ ℝ , belonging to the negative class, counterfactual explanations return a case ∈ ℝ that is close to , by some pre-defined distance measure, but is predicted to be positive by the classifier .
Nearest Like Neighbour: Given a query , a case is called the nearest-like neighbour (NLN) if it is the case closest to the in the case base, belonging to the same class as , i.e., the negative class.
Monotonic Constraints: Domain knowledge often dictates the way in which a feature should influence the predictions of a classifier, in order for them to be plausible. These constraints guided by domain knowledge can be of two types: 1. Increasing Constraint or MIB: Imposing the increasing constraint on a feature ∈ ℱ implies that increasing the value of would lead to a greater probability of belonging to the positive class, i.e., the feature is of type More is Better (MIB). Thus, ( 1, 2, … , , … , −1 , ) ≤ ( 1, 2, … , + , … , −1 , ) where ( ) gives the probability of case belonging to the positive class and ≥ 0 . Thus, to get closest to the boundary of the two classes, we would need to find the lowest possible value of for which the predicted class is positive. 2. Decreasing Constraint or LIB: Imposing the decreasing constraint on a feature ∈ ℱ implies that increasing the value of would lead to a lower probability of belonging to the positive class, i.e., the feature is of type Less is Better (LIB). Thus,
( 1, 2, … , , … , −1 , ) ≥ ( 1, 2, … , + , … , −1 , ) where ≥ 0 and ( ) is as defined above. To get closest to the boundary of the two classes, we would need to find the greatest possible value of for which the predicted class is positive.
Distance Function: To find the distance between and ′ with respect to a single, real-valued or order-enumerated attribute , we define feature distance as the absolute diference between the two attribute values and ′ normalized by the diference between the maximum and minimum values of the attribute in the case base.
( , ′ ) =
| − ′ | max − min where,
( , ′ ) refers to the feature distance between and ′ for attribute , max =
max ( ∀ ∈ ) and min = min ( ∀ ∈ ). Nominal attributes are handled in the usual
way [
( , ′) = ∑
| − ′ | ∈ℱ max − min where,
( , ′) is the combined feature distance between , ′ ∈ ℝ and ℱ is the set of features
in the case base such that |ℱ | = . The closer the feature distance is to 0, the better the
counterfactual. Using the combined feature distance, we can define the similarity between two
instances , ′ ∈ ℝ as,
( , ′) = 1 −
( , ′)
where is the number of features in the case base. The similarity measure is also upper-bounded
by 1 and lower-bounded by 0. The closer the similarity is to 1, the better the counterfactual.
While accounting for varied ranges across features, the combined feature distance (and similarity)
produces sparse solutions and accurately depicts the absolute change that would have to be
made to the features of to reach ′ [
Actionable Features: In order to maintain feasibility in the proposed counterfactual explanations, often changes can be made only to a subset of features among the entire set ℱ. The largest possible subset of MIB/LIB features ⊆ ℱ , such that changes to any feature in do not afect feasibility of the solution, is called the set of actionable features. For instance, features such as gender or nationality of a user cannot be modified in order to get a loan approved and hence, these cannot be included in the set of actionable features.
Diference and Match Features: The set of diference features ℒ [
Likewise, the set of match features ℒ consists of the features whose feature distances are lower than the threshold . The number of match features (|ℒ|) is given by . ℒ = { ∶ ( , ′) ≥ }, ℒ = ℱ − ℒ ⟹ = +
Given a query and its corresponding counterfactual explanation , the features that have to be changed to go from to are given by ℒ.
Counterfactual generation algorithms involve exploration of the space around the query
to discover points that are close to but have a diferent class label. For this, a variety of
approaches have been proposed. These may be classified based on the search strategy, access
to training data and access to the machine learning model [
Perturbation-based approaches attempt to meaningfully disturb the input until a point of the
opposite class is obtained [
In this work, we focus on enhancing the method proposed by Keane et al. [
Additionally, we experiment with imposing monotonic-constraints on features such that the MIB/LIB nature of the attribute is respected by the algorithm. Failure to take into account such constraints frequently leads to implausible or counter-intuitive answers. The proposed approach (henceforth referred to as MBC − Monotonic constrained Bound Corner counterfactuals) generates a variety of counterfactuals by finding corners in the decision surface created by a machine learning model across a subset of actionable attributes. The present work aims to maintain sparsity, by strictly restricting the number of dimensions along which changes can be made, while simultaneously improving upon diversity, by providing multiple diferent options to the end user, and plausibility, by introducing domain-informed monotonic constraints at the classifier-level.
Working of the GCF Algorithm: In the GCF algorithm [
The MBC algorithm uses corners in the decision surface of a monotonicity-respecting classifier to identify the changes to be made to the query in order to flip its class. In this section, we formalize the approach used in this work.
The goal of counterfactual explanations is to return a case ∈ ℝ close to the query ∈ ℝ such
that the changes to be made to the features of to flip its class label are minimal. In order to do
so, we take each of the possible pairs of cases in the case base (i.e., each of the (2) pairs) and
evaluate the feature distance ( , ′ )∀ ∈ ∧ ∀, ′ ∈ . If the feature distances of a pair,
for all except a maximum of three features, (depending on the number of allowed diference
features ) are below a threshold known as tolerance level, the pair is added to a separate case
base known as the Explanation Case Base [
However, even after allowing some tolerance while computing match features, the number of explanation cases often turns out to be low due to cases in the case base being spread out in space. In case the number of case pairs in is less than 1% of the total number of possible pairs, we eliminate features in order of increasing feature importance, such that the most important features remain. The feature importance values are obtained from the underlying classifier . This procedure is repeated until we obtain at least 1% of the (2) possible pairs. The value of 1% has been chosen arbitrarily and can be changed according to the requirement of the user. The features in the set of eliminated features ℰ are no longer considered during the computation of feature distance or similarity. Since the number of features under consideration reduces, the number of features required to be matched, until the criteria for an explanation case is satisfied, also reduces, i.e., ℒ + ℒ = ℱ − ℰ. This allows the number of explanation cases detected to increase. When a query is input, the explanation cases from containing the nearest-like neighbour are retrieved. Let the pairs be of the form ( , ) such that belongs to the negative class, and is the nearest like neighbour to , while belongs to the positive class. The diference features of and are chosen to be the diference features of the query and the counterfactual . This is done because the presence of the explanation case pair ( , ) close to tells us that by keeping the match features (approximately) constant and varying only the diference features, we are able to flip the prediction of the classifier, implying that the chosen diference features are able to influence the decision of the classifier, in turn, indicating the existence of a counterfactual. Similar to the algorithm, the values of the match features are directly copied into the counterfactual vector from the query . However, instead of copying the values of the diference-features from to , like in the algorithm, the algorithm replaces the values with those of the corners in -dimensional decision surface of the classifier . This decision surface could be visualized as one obtained when the diference feature dimensions are systematically varied and the output of the classifier is plotted at each point in this -dimensional space.
Ignoring the match-feature dimensions, which are held constant throughout this
exploration, the dimensional decision surface of the classifier is monotonic in nature due to the
explicit MIB/LIB constraints the classifier is met with. Although the present work is applicable
to diferent types of classifiers, it is of special significance in case of tree-based classifiers (such
as XGBoost [
To locate skyline corners at the boundary of the decision surface in ℝ , a 2 × 2 grid in case of = 2 and a 2 × 2 × 2 grid in case of = 3 is systematically slid across the dimensions of the search space. A skyline corner is said to be obtained when a single positive-class instance is captured in one of the corners of the grid. The end-points of each dimension of the search space are given by the maximum and minimum values of the corresponding attribute in the case base. In addition to these corner counterfactuals having ∈ {2, 3}, we also return counterfactuals in every diference-feature dimension having
= 1. For this, in each of the dimensions, the point in the boundary, lying on the axis, where the class flips is located using binary search and output as a counterfactual. The top-5 counterfactuals, located using the aforementioned procedure, closest to the query in terms of the normalized Manhattan distance (i.e., feature distance) are returned as the output counterfactuals. This allows the user to choose convenient dimensions to make changes or to trade-of between changes in multiple dimensions as per their choice. This solves the diversity problem. As an example of the working of the method, in Fig. 1,
1 is an example of a counterfactual located using binary search along the Applicant Income dimension. Along the Co-applicant Income dimension, both end points of the search space have a negative class label, hence, the search is abandoned, and no counterfactual is returned along that dimension. Further, 2, 3 and 4 are the returned corner counterfactuals.
To demonstrate the performance of the MBC algorithm, it is compared to the GCF algorithm
using a variety of measures listed in Section 4.3. To test each algorithm, we consider 2 cases −
= 2 and = 3 . In case of = 2 counterfactuals with ∈ {1, 2} are returned while in case of
2 , 3 , −2 and −3
of monotonic constraints on .
= 3 counterfactuals with ∈ {1, 3} are returned. Some counterfactuals with = 2 may also
be returned in case of = 3 , depending on the number of diference features in the explanation
case closest to the query. We do not go beyond 3 diference features due to the human memory
constraints [
Further, to demonstrate the importance of monotonic constraints experimentally, both the algorithms, each having two variants, are evaluated with and without these constraints on the underlying classifier . It is important to note that the variant without the monotonic constraints uses the same classifier as the one with constraints. The only diference is that, in one case, the MIB/LIB constraints are not fed to the classifier prior to the training procedure, and thus, it can learn any arbitrary decision surface. This, however, leads to counter-intuitive results, as we will see in Section 4.3.
Thus, all experiments are carried out on 4 variants of each of the two algorithms, namely, , where X = , and the subscript refers to the use
Most modern day classifiers, unless explicitly pre-programmed to do so, are unable to learn monotonicity patterns in the attributes of the data. For example, if we consider the case of a loan approval system, attributes such as applicant income are commonly known to be MIB, while attributes such as loan amount are LIB, i.e., decreasing the loan amount increases the chances of loan approval. In such a case the decision boundary of the classifier, unless fed with monotonic constraints, often turns out to be counter-intuitive. For example, in Fig. 2 we observe the decision boundary for a query for which applicant income and co-applicant income are being varied. In both Fig. 2 (a) and (b) we observe that, for the same loan amount, as applicant income increases from 1 to 2 , the loan which was rejected at 2 is approved at 2 since 2 > 1 . However, in the non-monotonic case (Fig. 2(a)) we can see that, all other features being the same, for the same co-applicant income, a loan with applicant income 3 is rejected but 2 is approved even though 3 > 2 and all other features are held constant. This does not match our expectation. Since the quality of counterfactuals produced greatly depends on the classifier, it is very important that the classifier learns the general rules for loan application acceptance rather than overfit itself to a small case base.
In this section, we highlight the performance measures used to compare the variants of the algorithms listed in Section 4.2. It must be noted that the algorithm returns multiple counterfactuals (up to 5) while the algorithm returns only 1. To make the comparison fair, all evaluation measures for the variants of are calculated using the output counterfactual closest to the query . The evaluation measures include similarity to query ( ) which measures the similarity of the output counterfactual to the query and similarity to data ( ) measures the similarity of the output counterfactual to the nearest case. It is representative of how close to real data the returned counterfactual is. Additionally, we also measure coverage, which measures the proportion of queries for which the algorithm in question is able to provide counterfactuals. A higher value of coverage is desired since it indicates that the algorithm is able to provide counterfactuals to a larger number of queries. It is given by, = ∑∈ 1, if ℎ { 0 otherwise
The Loan approval data set, consisting of 614 instances and 12 attributes, computes loan eligibility based on customer details such as gender, marital status, education, loan amount, credit history, applicant income, co-applicant income, etc. Among these, features such as gender, marital status and education are excluded from the set of actionable features (even though education could be an MIB feature) since the customer cannot alter these in order to get their loan approved. Increasing constraints (MIB) are placed on features such applicant income and co-applicant income, while features such as loan amount are subjected to decreasing constraints (LIB). A counterfactual, in this case, would tell the loan applicant what measures to take to get her loan approved. From Table 1, it can be seen that all variants of outperform the corresponding variants of with respect to and . The top-performing variant - − 2 , with respect to ), outperforms the top-performing variant − 2 by 5.7%. As expected, variants have a higher similarity to data ( ) due to their usage of actual feature values from the case base. However, the top-performing variant is only marginally. behind the top variant in terms of . The coverage of most -variants is seen to be very low, while the variants fair better. The top variant has double the coverage as that of the top variant. Additionally, we observe that each of the variants with monotonic constraints, for both and outperform those without with respect to each of the three measures, demonstrating the importance of these constraints in the context of the given data set. Lastly, we observe that between the cases of = 2 and = 3 ,
coverage and increase as increases, while across all variants of both the algorithms.
The Wine data set consists of the chemical analysis of wines. It has 178 instances and 12 attributes such as content of Malic acid, ash, Flavonoids, colour intensity, hue, etc. There are three class labels corresponding to the alcohol content. Since the and algorithms deal with binary classification settings, the data set is converted to a binary classification case base using the one-vs-all technique. A counterfactual, in this case, would tell the wine distillery what changes to make to improve the alcohol content in the wine. Attributes such as Flavonoid content, colour intensity and Malic acid content are assumed to have a decreasing constraint (LIB) while hue is assumed to have an increasing constraint (MIB). Similar to the Loan data set case in Section 5.1, we observe, from Table 2, that outperforms in terms of and coverage while marginally outperforms in terms of . In this data set, however, monotonic constraints do not add as much value as the previous one. For example, in 3 , similarity to data and query are seen to increase with the introduction of monotonic constraints, while coverage decreases. In the case of 2 however, the addition of monotonic constraints is seen to decrease similarity to data and query, while coverage remains constant. This can be attributed to the lack of domain knowledge in the field, due to which some constraints may have been formulated incorrectly.
The Employee Attrition data set consists of 1470 employee records with 34 attributes such as gender, percentage of salary hike, job satisfaction, distance from home, monthly income, overtime hours etc. These attributes are used to predict employee attrition - whether the employee will leave the company or not. A counterfactual, in this case, would tell the company what measures to take to prevent an employee from leaving. Features such as gender and distance from home are excluded from the list of actionable attributes, since it is not possible for
the company to change the gender of an employee. An increasing constraint (MIB) is placed on features such as percentage of salary hike, job satisfaction, monthly income (for e.g. increasing the salary of an employee would reduce the chances of him/her leaving) while, features such as overtime hours are met with a decreasing constraint (LIB)(i.e., the lesser number of overtime hours an employee is subject to the more likely he/she is to stay in the company). In Table 3, we observe trends similar to the previous two case studies. The variants outperform their corresponding variants in terms of and coverage, while marginally outperforms in terms of . Monotonic constraints are seen to improve similarity to data in all cases except −3 , while they improve similarity to query for all the variants. Coverage is seen to be substantially higher among the variants as compared to the variants. The variants without constraints are seen to have a higher coverage than those with the constraints.
In this work, we address the issues of prolixity, sparsity and plausibility raised by Keane et al.
[
Prolixity: Keane et al. [
Diversity: In contrast to the algorithm which returns only 1 counterfactual per query, the algorithm returns multiple counterfactuals per query, which make trade-ofs among the diferent dimensions to reach the desired outcome. This presents the user with a diverse choice of counterfactuals to choose from.
Sparsity: Even though many algorithms claim to make changes to only a few features, many
of these counterfactuals may still involve relatively high numbers of feature-diferences (e.g.
> 4) [
Plausibility: Finally, we address the problem of plausibility, which states that the counterfactuals generated may not be valid cases in the domain, or they may suggest feature-changes that are dificult-to-impossible. However, this concern stands invalidated in cases where the attributes are known to be MIB or LIB. For an LIB or MIB attribute, every point between the extremes is valid by definition, since the attributes are of monotonic nature. Further, to eradicate the possibility of impossible values being returned, since we cap the values of each feature by the corresponding minimum and maximum of the cases in the case base.
Majority of the present day counterfactual generation algorithms face the challenges of prolixity, sparsity, plausibility and diversity among others. In this work, we explore skyline corners in the decision boundary of a tree-based classifier, as counterfactuals. We also incorporate domain knowledge by compelling the underlying classifier to respect monotonic constraints such that the generated counterfactuals more plausible. Better counterfactuals are achieved with this technique, in terms of similarity to query and coverage, while closely maintaining their similarity to the existing cases. Although this is a unique way to find diverse counterfactuals, monotonicity tends to be a subjective characteristic of each data set, and concrete domain knowledge is required to represent such constraints. There is scope to find more eficient processes to obtain counterfactuals in the monotonic feature space that could be explored in the future.