Introduction

In recent years, there have been quite a few interesting research papers reporting the applicability of Case Based Reasoning (CBR) in facilitating better explanations [1,2]. An important direction in this regard is that of generating counterfactuals, which can help discover relationships between the inputs fed to a machine learner and the prediction decision made by it. This is especially useful for end users trying to understand how their current circumstances can be improved to receive the desired outcome in the future. For instance, let us say, a user applies for loan and a classifier rejects the loan (negative class). The simplest explanation that a CBR system may generate is a "factual" one, in which the system just reports a case or a set of few cases that were similar to the query, which had a similar outcome. A richer explanation takes the form of a counterfactual that can reveal more actionable information: If you asked for a slightly lower amount or your co-applicant income had been marginally higher, you would have been granted the loan. Generating interesting counterfactuals that are actually useful for the end user is a challenging problem, and this work attempts to identify and address certain limitations of past research, and present fresh insights in this direction.

In this paper, we assume a twin-system context [1] where predictions from a machine learning (ML) or deep learning (DL) model have to be explained by a Case based Reasoner. In order to generate counterfactuals, we exploit the fact that certain attributes in the cases are naturally of the type More is Better (MIB) or Less is Better (LIB). This terminology was first introduced by McSherry et al. [3]. When buying a camera, a customer would typically prefer a model that has high optical zoom and low price. Here, optical zoom is an MIB attribute and price is an LIB attribute. In the context of generating counterfactuals in the loan domain, the chances of a loan getting accepted are higher if the applicant income is high and the loan amount is low. Thus, applicant income and loan amount are MIB and LIB attributes, respectively. We argue in this paper that it is important for the predictive ML system to respect the monotonic nature of attributes, in order to ensure that meaningful explanations are generated.

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.

Background

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 difference between the two attribute values 𝑥 𝑘 and 𝑥 ′ 𝑘 normalized by the difference 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 [4]. The search space for counterfactual explanations in ℝ 𝑑 is restricted in each of the 𝑑 dimensions by the minimum and maximum values of the corresponding attribute in the case base. Since the goal of counterfactual explanations is to be as close as possible to the query, looking beyond this region would prove to be wasteful. Due to this restriction on the dimensions, the value of feature distance for every attribute is upper-bounded by 1 and lower-bounded by 0, i.e., 0 ≤ 𝑓 𝑑 (𝑥 𝑘 , 𝑥 ′ 𝑘 ) ≤ 1 ∀𝑘 ∈ ℱ. On extending this measure to all features, we obtain a combined feature distance which is equivalent to the Manhattan distance measure normalized using min-max scaling.

𝑓 𝑑 (𝑥, 𝑥′ ) = ∑ 𝑘∈ℱ |𝑥 𝑘 − 𝑥 ′ 𝑘 | 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 𝑥 ′ [5]. 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 affect 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. Difference and Match Features: The set of difference features ℒ [1] between two cases 𝑥, 𝑥 ′ ∈ ℝ 𝑑 comprises the features whose feature distances are greater than or equal to some arbitrary threshold 𝑡. The threshold can be set according to the needs of the application. This is explained further in Section 4.1. The number of difference features (|ℒ |) is given by 𝑑 𝑓 and the maximum number of allowed difference features is given by 𝑣 such that, 𝑑 𝑓 ≤ 𝑣.

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 ℒ.

Related Work

Counterfactual generation algorithms involve exploration of the space around the query 𝑞 to discover points that are close to 𝑞 but have a different 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 [6]. The most commonly adopted approaches make use of convex optimization methodologies or custom heuristic rules. Convex optimization procedures need a differentiable scoring function because they incorporate the computation of gradients [7]. However, these algorithms often need to solve the optimization problem once for every generated counterfactual for each query, making it very expensive to generate a set of diverse counterfactuals for every query. There are only a few approaches that are able to generate a sizeable number of diverse counterfactuals, by some measure of diversity, for each input query [8,9,10].

Perturbation-based approaches attempt to meaningfully disturb the input until a point of the opposite class is obtained [9,11]. One challenge in such approaches is to contain the number of counterfactuals that may be generated thereby -small increments in a numeric feature, for example, can result in numerous counterfactuals, only a handful of which may truly be worth considering. This problem of over-generation of potentially superfluous counterfactuals is referred to as the problem of prolixity, and may be addressed, for instance, by restricting attention to a case that is closest to the query case but has the opposite class label (the nearest unlike neighbour). A second problem is that of sparsity, which relates to the requirement that the generated counterfactual must make changes to the fewest possible features. A counterfactual that makes changes to four or more features in the query may not be usable and is unlikely to have substantial actionable information content. The third problem is that of ensuring plausibility of the generated counterfactuals; in other words, the counterfactuals should not suggest changes to feature values that are unrealistic, or those that violate underlying domain constraints. Suggesting that doubling one's salary or changing one's gender would fetch her a loan, for instance, is an example of an implausible counterfactual [1]. A final challenge is that of ensuring diversity -in other words, we need to generate multiple counterfactuals that are sufficiently diverse with respect to each other. This enhances the flexibility of the system in terms of its ability to cater to a diverse set of users.

In this work, we focus on enhancing the method proposed by Keane et al. [1], henceforth referred to as GCF (Good CounterFactual), which generates counterfactuals using a classical CBR approach by reusing and revising the explanation cases close to the query.

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 different 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 [1], the cases 𝑥 and 𝑥 ′ closest to the query 𝑞 and belonging to opposite classes are identified, where 𝑥 and 𝑞 belong to the negative class while 𝑥 ′ belongs to the positive class. The values of difference features of 𝑥 and 𝑥 ′ are copied to 𝑝 from 𝑥 ′ , i.e., ℒ 𝑥,𝑥 ′ = ℒ 𝑝,𝑥 ′ . The values of the remaining features, i.e., the match features, are copied from 𝑞 onto counterfactual 𝑝, i.e., 𝑝 𝑘 = 𝑞 𝑘 ∀𝑘 ∈ ℒ. Upon predicting the class of 𝑝 using the underlying ML model, if we obtain the desired positive class, counterfactual 𝑝, which is a combination of 𝑞 and 𝑥 ′ , is output as the final result. If not, an additional adaptation step is performed where the values of the difference features in 𝑝 obtained from 𝑞 are perturbed until the desired class is obtained.

Proposed Methodology

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.

Approach

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 difference features 𝑣) are below a threshold known as tolerance level, the pair is added to a separate case base known as the Explanation Case Base 𝑋 𝐶 [1] and is referred to as an explanation case. If the tolerance level is set to a low value, the number of explanation cases obtained is low, since it is difficult to find cases that have the same or very close values for all except a maximum of three features in the case base. If the tolerance level is set to a high value, however, the result becomes unreliable since it is based on the argument that all else equal, only the difference features contribute to the flip in class. However, if the match features vary widely, they may contribute significantly to the decision made by the classifier. In this work, the tolerance is chosen to be 2%. This value can be changed depending upon the requirement.

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 difference features of 𝑋 𝐶 𝐴 and 𝑋 𝐶 𝐵 are chosen to be the difference 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 difference features, we are able to flip the prediction of the classifier, implying that the chosen difference 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 difference-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 𝑑 𝑓 difference 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 different types of classifiers, it is of special significance in case of tree-based classifiers (such as XGBoost [12], used in this work), due to the axis-aligned nature of the decision surface [13] produced which leads to the formations of corners (either 2D or 3D, depending on the value of 𝑣) on the decision boundary. Among these corners, the skyline corners [14] are identified as potential counterfactual candidates. Corners are chosen over other points in the decision boundary as they are optimal in terms of the MIB/LIB constraints. For example, consider the point 𝐴 in Fig. 1. It is on the decision boundary, however, it is not at a corner. It can naturally be seen that on moving along the Applicant Income direction until 𝐶𝐹 2 is reached, increasingly better counterfactuals are obtained, since, Applicant Income, which is an MIB dimension, along with distance to query reduce progressively. The same argument would apply to internal corners, such as 𝐵 due to which only skyline corners are seen as counterfactual candidates.

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 difference-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-off 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.

Variants of the MBC and GCF Algorithms

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 𝑣 = 3 counterfactuals with 𝑑 𝑓 ∈ {1, 3} are returned. Some counterfactuals with 𝑑 𝑓 = 2 may also be returned in case of 𝑣 = 3, depending on the number of difference features in the explanation case closest to the query. We do not go beyond 3 difference features due to the human memory constraints [1]. The algorithm, however, could easily be extended to higher dimensions. Each of the two algorithms are subject to these two cases and are labelled as 𝑀𝐵𝐶 2𝑑 , 𝑀𝐵𝐶 3𝑑 , 𝐺𝐶𝐹 2𝑑 and 𝐺𝐶𝐹 3𝑑 respectively.

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 difference 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, 𝑋 2𝑑 , 𝑋 3𝑑 , 𝑋 𝑚𝑜𝑛𝑜−2𝑑 and 𝑋 𝑚𝑜𝑛𝑜−3𝑑 , where X = 𝑀𝐵𝐶, 𝐺𝐶𝐹 and the subscript 𝑚𝑜𝑛𝑜 refers to the use of monotonic constraints on 𝑐.

Importance of Monotonicity-respecting Classifier

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.

Performance Measures

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 𝑇 𝑜𝑡𝑎𝑙 𝑁 𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑄𝑢𝑒𝑟𝑖𝑒𝑠

Results

Loan Approval Data Set

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 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 𝑆𝑖𝑚 𝑞𝑢𝑒𝑟𝑦 is seen to decrease with increase in 𝑣 across all variants of both the algorithms.

ICCBR

Wine Data Set

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.

Employee Attrition Data Set

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.

Discussion

In this work, we address the issues of prolixity, sparsity and plausibility raised by Keane et al. [1] as follows: Prolixity: Keane et al. [1] suggests the use of methods that find the minimal changes to the features of the test case that flip the prediction (i.e., the nearest unlike neighbour) to tackle the problem of prolixity. However, in this study it is shown that to produce minimal changes that flip the prediction, we do not need to rely on the nearest unlike neighbour. The present algorithm produces points that are closer to the decision boundary, thus requiring lesser change.

Diversity: In contrast to the 𝐺𝐶𝐹 algorithm which returns only 1 counterfactual per query, the 𝑀𝐶𝐵 algorithm returns multiple counterfactuals per query, which make trade-offs among the different 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-differences (e.g. > 4) [1]. Since the present algorithm chooses and changes only between 1 and 3 features at a time, it is possible to successfully deliver sparse counterfactuals.

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 difficult-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 ICCBR'22 Workshop Proceedings the corresponding minimum and maximum of the cases in the case base.

Conclusion

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 efficient processes to obtain counterfactuals in the monotonic feature space that could be explored in the future.