Learning Actionable Counterfactual Explanations in Large State Spaces

## Abstract

Abstract Counterfactual explanations (CFEs) are sets of actions that an agent with a negative classification could take to achieve a (desired) positive classification, for consequential decisions such as loan applications, hiring, admissions, etc. In this work, we consider settings where optimal CFEs correspond to solutions of weighted set cover problems. In particular, there is a collection of actions that agents can perform that each have their own cost and each provide the agent with different sets of capabilities. The agent wants to perform the cheapest subset of actions that together provide all the needed capabilities to achieve a positive classification. Since this is an NP-hard optimization problem, we are interested in the question: can we, from training data (instances of agents and their optimal CFEs) learn a CFE generator that will quickly provide optimal sets of actions for new agents? In this work, we provide a deep-network learning procedure that we show experimentally is able to achieve strong performance at this task. We consider several problem formulations, including formulations in which the underlying “capabilities” and effects of actions are not explicitly provided, and so there is an informational challenge in addition to the computational challenge. Our problem can also be viewed as one of learning an optimal policy in a family of large but deterministic Markov Decision Processes (MDPs).

## 1 Introduction

Machine learning models are increasingly being used to guide consequential decision-making, e.g., for hiring and school admissions.
Since these decisions can significantly impact people’s lives, society demands the right to explanation, as stated in Articles 13–15 of the European Parliament and Council of the EU [] General Data Protection Regulation.
One of the most needed explanations is of how people (agents) can modify their input features (i.e., their state) to get a (desired) positive classification from these models.
Counterfactual explanations (CFEs) provide insights into which input features to change and to what extent to achieve a desirable model outcome [, , ].
CFEs are transformed into actionable feedback to make it easy for agents to act on the insights, that is to say, negatively classified agents receive recommendations as to how to optimally act to get desirable model outcomes [, , , ].

We consider settings where an optimal CFE corresponds to the solution of weighted set cover problem. Specifically, given a set of actions with known costs and known effects on state features, the problem is to find the lowest-cost subset of actions that achieve all capabilities (state features greater than or equal to a given threshold) needed to be positively classified.
This formulation is, in principle, similar to search-based optimization CFE generation frameworks [], user-specific integer linear program recourse approaches [, , ], and logic and answer-set programs based counterfactual generation [, , ].
For example, a bank loan officer with access to a binary classifier that determines loan eligibility and a set of actions, their underlying effect on the agent features, and their costs can use the solution of the weighted set cover problem to suggest the least expensive subset of actions that can help an ineligible borrower become eligible for a loan.

However, this formulation, like similar contemporary approaches to CFE generation heavily relies on information access assumptions, for example, at the very least, query access to the classifier and knowledge of the actions, their costs, and underlying effects on agent features. These assumptions rarely hold in practice which limits the usage of the CFE generators. We are, therefore interested in generating CFEs for settings where different information challenges might exist (see Table 1).

Consider, for example, unlike the previous setup, the loan officer assistant only knows the name of actions but not their costs and underlying effects on agent state features or even query access to the loan eligibility classifier. In this setting, the assistant recommends a *named-action* CFE, an optimal set of named-actions to the agent, e.g., increase bank credit (named-action), without information on the cost of the named-actions, or how the actions might affect the agent’s state, but only relying on how agents that had a similar profile (current agent state) became loan eligible after increasing their bank credit.

**Table 1: We propose three kinds of data-driven CFE generators: named-action, full-action and named CFE generators, each with a specific set of informational challenges it works with.**
|  | CFE<br>name | Action(s)<br>name | Action(s)<br>cost | Action(s)<br>effects | Classifier<br>query-access |
| --- | --- | --- | --- | --- | --- |
| Weighted set cover problem | × | ✓ | ✓ | ✓ | ✓ |
| Named-action | × | ✓ | × | × | × |
| Full-action | × | ✓ | × | ✓ | × |
| Named | ✓ | × | × | × | × |

In another setting, the loan officer, even with knowledge of the actions and their underlying effects on the agent’s state, might not know the cost of those actions. Relying on the history of which CFEs worked well for agents with a similar state, they then recommend a *full-action* CFE, an optimal set of full-actions, to help a new agent in a similar state become loan-worthy, e.g., increase credit score by $20\%$ (full-action). This setting would preclude the use of contemporary CFE generators that require knowledge of the action costs and at least query access to the classifier.

Alternatively, there are instances where there is very limited information access, where the decision-makers have no query access to the classifier and the actions, their costs, and underlying effects on the features is unknown.
In this case, the decision-maker might have access to *named* CFEs, where the name of a CFE holds significant implicit information, and there is an expectation the agent taking the CFE possesses some domain expertise. For example, a mortgage broker without query access to the bank loan eligibility classifier, actions, their costs, and underlying effects on the agent features might recommend that an agent wanting to take out a mortgage first takes a personal loan x years prior (named CFE), without specifying what sub-actions the agent needs to take.

Other than the aforementioned informational challenges to CFE generation, generating an optimal CFE as a solution of weighted set cover problem is an NP-hard optimization problem []. Additionally, like other similar CFE generation methods, this CFE generator requires solving an optimization problem for each new agent which is not scalable and is significantly expensive. Given all these informational and computational challenges, we are interested in the question: can we, from training data (instances of agents and their optimal CFEs), learn a CFE generator that will quickly provide optimal sets of actions for most new agents?

In this work, we provide a neural network learning procedures
(see Figure 1)
that we experimentally show to achieve strong performance on this task. We consider several problem formulations, including those in which the classifier and grouped access to actions are not explicitly known, and the underlying effects of the actions are not explicitly provided.

Figure: Figure 1: Data-driven CFE generators trained on agent-CFE data generate information specific CFEs ($\mathcal{I}$) for new agents given their state ($\mathbf{x}$) without re-optimizing the CFE generator.

### 1.1 Related Work

Closest to our work is that of Naumann and Ntoutsi [] and Verma et al. []. While our formulation is synonymous with learning an optimal policy in a family of large but deterministic Markov decision processes (MDPs), Verma et al. [] learns an optimal policy in stochastic, but relatively small MDP settings.
While Naumann and Ntoutsi [] optimizes their CFE generation method for each agent to find an optimal ordered sequence of actions to recommend, in our generalized CFE generation approach, we assume that the train-set CFE is optimal, and we don’t re-optimize the model to generate a CFE for each new agent.

Our approach to generating CFEs is similar to that of CFE generation tools that use reinforcement learning [, ]. However, due to computational complexity, these tools only provide approximate solutions, while our generators produce exact solutions.

Our main contribution is CFE generators that are computationally efficient and work under varied information settings, thus providing a solution to the informational and computational challenges of CFE generation in settings where actions correspond to solving a weighted set cover problem. Unlike other methods that need, at the very least, query access to the classifier as well as knowledge of the cost of each action and its effect on state features [, , , ], our formulation effectively generates CFEs in the absence of explicit access to this information.

Lastly, our work is also related to data-driven algorithm design [, , ] in which models trained on training data instances perform well on the training data and generalize to the testing data.
Specifically, given testing data: instances of agents and their optimal CFEs (of varying information), we train neural-network models that we empirically show achieve strong performance at generating optimal CFEs for new instances.

## 2 Motivation

Consider a binary classifier $\mathbf{t}=\{t_{1},t_{2},\cdots,t_{n}\}$ over $n$ features that classifies an agent as positive if its state $\mathbf{x}$ satisfies the condition: $x_{j}\geq t_{j},\ \forall j\in[n]$, and negative otherwise. We consider scenarios in which agents that are classified as negative can take a set of actions to acquire capabilities required to receive a positive classification.

An action $\mathbf{a}\in\mathcal{A}$ provides the agent with different sets of capabilities to transform features of the agent’s state. An action transforms the feature $j$ of the agent state, $\mathbf{x}$, if after performing the action, the new agent state $\mathbf{x+a}=\mathbf{x}^{\prime}$, is such that $x^{\prime}_{j}>x_{j}$ and $x^{\prime}_{j}\geq t_{j}.$

An action provides a negatively classified agent with all necessary capabilities, if after performing the action, the state of the agent changes from the initial state $\mathbf{x}$ to a counterfactual state $\mathbf{x}^{\star}$, such that $x^{\star}_{j}\geq t_{j},\forall j\in[n]$, where $\mathbf{x}^{\star}$ results in a positive classification.
A counterfactual state is the final state with which the agent has all the needed capabilities.
If the agent requires more than one action to achieve these capabilities, actions are performed sequentially to transform the agent’s initial state to the counterfactual state.

### 2.1 Weighted Set Cover Problem

Let there be a collection of actions $\mathcal{A}$ that an agent can perform, where associated with each action $a_{i}\in\mathcal{A}$ is its cost $c_{i}\in\mathbf{c}$ and a specific set of effects that that action has on the agent’s state.
A negatively classified agent, $\mathbf{x}$, wants to perform the cheapest subset of actions ${I}\subseteq\mathcal{A}$ that together provide all the needed capabilities to achieve a positive classification, i.e., $\mathbf{x}+{I}=\mathbf{x}^{\star}$, s.t. $x^{\star}_{j}\geq t_{j},\forall j\in[n]$.

#### Example

Given an agent $\mathbf{x}=[0,0,0,0,1]$, a binary classifier $\mathbf{t}=[1,1,1,1,1]$, and actions $\mathcal{A}=\{[0,0,1,0,1]$, $[1,0,0,0,1]$, $[0,0,1,1,0]$, $[0,0,0,0,1]$, $[0,1,0,0,0]$, $[1,1,1,1,1]$, $[0,0,0,0,0]$, $[1,0,0,0,0]$, $[0,1,1,0,0]\}$ with their associated costs $\mathbf{c}=[6,5,9,2,1,15,0,3,5]$, the goal is to find the lowest-cost subset of actions that together provide the agent all the needed capabilities.

Formulating this as a weighted set cover problem, we find the best (lowest-cost) subset of actions for the agent to take as ${I}$ $=\{[0,0,1,1,0]$, $[0,1,0,0,0]$, $[1,0,0,0,0]\}$, at a total cost of $13.0$. Sequentially performing the actions in ${I}$ changes the agent state from the initial state $\mathbf{x}=[0,0,0,0,1]$ to the counterfactual state $\mathbf{x}^{\star}=[1,1,1,1,1]$.

#### Integer Linear Program (ILP)

We mathematically formulate the weighted set cover problem as an integer linear program [].

Given a set of actions $\mathcal{A}\in\{0,1\}^{A\times n}$ and their costs $\mathbf{c}\subseteq\mathbb{R}^{A}$, and a negatively classified agent with initial state $\mathbf{x}\in\{0,1\}^{n}$, the problem is to find the lowest-cost subset of actions $I\subseteq\mathcal{A}$ that the agent can take to reach the counterfactual state.

Let the binary matrix $\mathcal{D}\in\{0,1\}^{A\times n}$ denote the relationship between the features to transform and actions the agent can take, where $d_{ij}\in\mathcal{D}=1$ if action $i$ transforms feature $j$, and 0 0 otherwise.
Therefore, we define $\{i\in\mathcal{A}:d_{ij}=1\},j\in[n]$ as the number of actions that can transform feature ${j}$, and $\{j\in[n]:d_{ij}=1\},i\in\mathcal{A}$ as the number of features action $i$ can transform. If we choose action $i$, then $a_{i}=1$ and 0 0 otherwise.
Formally, we define the integer linear program as follows:

$$ minimize $\displaystyle\sum_{i\in\mathcal{A}}{c_{i}a_{i}}$ subject to $\displaystyle\sum_{i\in\mathcal{A}}{d_{ij}a_{i}}\geq t_{j},\ \forall j\in[n],$ $\displaystyle a_{i}\in\{0,1\},\ d_{ij}\in\{0,1\}$ $$

Therefore, for each agent with a negative classification, the lowest-cost (optimal) CFE required to achieve the capabilities needed for a positive classification is given by $I=\{i:a_{i}=1\}$. The cost of the optimal CFE is given by the total cost of the actions in the CFE, $\sum_{i\in I}{c_{i}}.$

#### Challenges of using the weighted set cover problem CFE generator

In principle, as described above, the weighted set cover problem can be solved by exhaustive search over all the combinations of the actions.
In our empirical experiments, an agent can use one action or a set of two/three actions to get all the necessary capabilities needed to achieve a positive classification. It’s inexpensive to try all the ($A/3$) ways of finding the most optimal combination (set) of actions.
However, in the worst-case scenario, a search through all the combinations of actions, $2^{A}-1$ is needed to find the optimal set of actions the agent needs to acquire all the needed capabilities.
Therefore, exhaustive search would have an exponential time complexity $O(n2^{A})$.
Although removing already covered/satisfied features of an agent could reduce the complexity by a factor, the CFE generator would still be computationally expensive.

In addition to being computationally expensive, this nature of CFE generation requires solving an optimization problem for each new agent, and needs access to the classifier. Also, given real-world settings, like health care, especially counterfactual explanations in medical settings, where health professionals recommend interventional actions based on the current state of the patient and similarity to other patients who were in a similar state, CFE generation as a solution to the weighted set cover problem doesn’t adequately leverage advantages of historical counterfactual explanations.

## 3 CFE Generation as a Learning Problem

Due to computational and informational challenges of CFE generation in settings where actions
correspond to solving a weighted set cover problem, we propose various CFE generators based on the limited and specific information accessible to the decision-maker, and without having CFE generation as an optimization problem for every single agent. Below are three kinds of proposed data-driven CFE generators.

### 3.1 Named-action CFE Generators

The named-action (NA) CFE generator addresses the informational challenge where only the names of the actions in the CFE are known. Explicit information regarding the cost of actions or their explicit effects on features is unknown, and decision-makers have no query access to the classifier.
The named-action CFE generator is considerably cheaper than the weighted set cover problem CFE generator, and the number of CFEs is upper bounded by the number of training examples.

The named-action CFE generator is trained on instances of agents and their optimal CFEs for which the names of the actions in the CFE are known, but not their effects on features.
Each action in the collection of actions $\mathcal{A}_{\textrm{name}}$ is represented by its name.
Each negatively classified train-set agent $\mathbf{x}_{i}\in\mathcal{X}_{T}$ has an optimal named-action CFE that is a subset of the actions, ${I}_{i}\subseteq\mathcal{A}_{\textrm{name}}$. The CFE ${I}_{i}$ is represented by a binary vector, where ${I}_{i}^{(a)}=1$ if the $a^{\textrm{th}}$ action is in the optimal CFE vector ${I}_{i}$ and 0 0 otherwise.
For each agent $\mathbf{x}_{i}$, the named-action CFE generator computes a vector score for each action using a linear combination of the input features and CFE generator weights $\mathbf{z}_{i}=\mathbf{x}_{i}W$.
The probability that a generated action, $\hat{I}^{(a)}_{i}$ is among the actions in the optimal CFE for the agent $\mathbf{x}_{i}$ is given by the sigmoid function:

$$ $\hat{I}^{(a)}_{i}=\sigma(\mathbf{z}^{(a)}_{i})$ $$

To ensure that the named-action CFE generator performs well on the train-set, $\mathcal{X}_{T}\in\{0,1\}^{m\times n}$ and generalizes to the test-set, we optimize the binary cross entropy loss function given by:

$$ $\mathcal{L}_{\textrm{NA}}=-\frac{1}{m}\sum_{i=1}^{m}\left[I_{i}\log(\hat{I}_{i })+(1-I_{i})\log(1-\hat{I}_{i})\right]$ $$

The binary vectored named-action CFEs were sparse because agents had either $1$, $2$, or $3$ named-actions in their CFEs, and there were at most $100$ possible named-actions. As a result, the named-action CFE generator was susceptible to overfitting. Additionally, some named-actions were more common than others especially the second and third named-actions in three-action CFEs were less common than those in one-action CFEs.

To address named-action imbalance and overfitting, we weight and regularize the loss function, $\mathcal{L}_{\textrm{NA}},$ as follows:

$$ $\mathcal{L}_{\textrm{NA}}^{w}=p_{w}\mathcal{L}_{\textrm{NA}}+\alpha\frac{1}{m} \sum_{i=1}^{m}\left|\hat{I}_{i}-I_{i}\right|$ $$

The weighting factor $p_{w}$ weights the loss function $\mathcal{L}_{\textrm{NA}}$ to help with named-action imbalance by scaling the contribution of each sample to the loss function.
The sparsity term $\alpha\frac{1}{m}\sum_{i=1}^{m}\left|\hat{I}_{i}-I_{i}\right|$ regularizes the model, thus preventing overfitting, where $\frac{1}{m}\sum_{i=1}^{m}\left|\hat{I}_{i}-I_{i}\right|$ encourages the model to produce named-action CFEs closer to $I_{i}$’s distribution.

Figure: Figure 2: An encoder-decoder full-action CFE generator.

### 3.2 Full-action CFE Generators

The full-action (FA) CFE generator addresses the informational challenge where all the exhaustive space of actions is unknown and the decision-maker has no query access to the classifier.
Only actions in the CFE, their effects on features are known.

Given instances of agents $\mathbf{x}_{i}\in\mathcal{X}_{T}$ and their optimal CFEs $I_{i}\in\{0,1\}^{s\times n}$ for which the underlying and effects of the $s$ full-actions on the agent features are explicitly provided, the goal is to learn a full-action CFE generator that will quickly provide optimal CFEs for new agents.
We model the generator using two kinds of neural networks: a sequential encoder-decoder network (see Figure 2) and a multi-label classifier. In the case of the multi-label classifier, we convert the CFEs into padded binary vectors and apply the same loss function as described in the named-action CFE generators in Section 3.1.

### 3.3 Named CFE Generators

The named CFE generator addresses the informational challenge where only the CFE names and costs are known. Explicit information about the actions in each CFE, including actions’ costs and explicit effects on features is unknown, and decision-makers have no query access to the classifier.

In this setting, the decision-maker generates CFEs with only the names and costs of the CFEs at hand. Each negatively classified train-set agent $\mathbf{x}_{i}\in\mathcal{X}_{T}$ has an optimal CFE $I_{i}\in\mathcal{I}_{T}$, where $I_{i}$ is the optimal CFE name.
To generate the optimal CFE for a test-set agent, we use a named CFE generator trained on the train-set to learn the patterns between agents and their optimal named CFEs.
Following are the two proposed named CFE generators.

#### Hamming distance

As a baseline, we consider the hamming distance named CFE generator. In this case, given a negatively classified test-set agent $\mathbf{x}_{v}$, we compute the Hamming distance (see Figure 3) between it and each of the train-set agents $\mathbf{x}_{i},\forall i\in[m]$. Based on the computed distances, we choose the $k$ nearest train-set agents and their associated optimal CFEs. We then use the most common CFE as the CFE for the test-set agent $\mathbf{x}_{v}$.

Figure: Figure 3: Hamming distance between the train-set agent $\mathbf{x}_{i}$ and test-set agent $\mathbf{x}_{v}$.

#### Multi-class classification

We consider a more sophisticated model, a neural network-based named CFE generator, i.e., a multi-class classification (MC) named CFE generator.
First, we one-hot encode the CFE names to $\mathcal{I}_{T}\subseteq\{0,1\}^{K}$, where $K$ is number of unique named CFEs. For each agent $\mathbf{x}_{i}\in\mathcal{X}_{T}$, the CFE generator computes a vector score for each CFE using a linear combination of the input features and CFE generator weights $\mathbf{z}_{i}=\mathbf{x}_{i}W$. The probability that a generated CFE $\hat{I}^{(k)}_{i}$ is the lowest-cost CFE for the agent $\mathbf{x}_{i}$ is given by the softmax function:

$$ $\hat{I}^{(k)}_{i}=\frac{e^{\mathbf{z}^{(k)}_{i}}}{\sum_{j=1}^{K}e^{\mathbf{z}^ {(j)}_{i}}}$ $$

To ensure that the CFE generator performs well on the train-set, $\mathcal{X}_{T}\in\{0,1\}^{m\times n}$ and generalizes to the test-set, we optimize the cross entropy loss:

$$ $\mathcal{L}_{\textrm{MC}}=-\frac{1}{m}\sum_{i=1}^{m}\sum_{k=1}^{K}I^{(k)}_{i} \log(\hat{I}^{(k)}_{i})$ $$

## 4 Experimental Setup

In this section, we describe the setup used to empirically demonstrate the strong performance with which our method generates optimal CFEs for new instances of negatively classified agents.

### 4.1 Data generation

We generate the agents by activating each feature with probability $p_{f}$.
We then create a collection of actions $\mathcal{A}\in\{0,1\}^{A\times n}$ by setting each action $\mathbf{a}\in\mathcal{A}$ to $1$ with probability $p_{a}$.
Each action coordinate has its own pre-generated cost, and the cost of active action coordinates (those with capabilities) determines the cost of the action.
Using solutions of the weighted set cover problem based on the generated actions and the agent datasets, we create datasets of instances of agents and their associated optimal CFEs.
We generate three kinds of agent-CFE datasets that exhibit variations in their dimension, binary classifier sparsity, and actions access:

- •
Varied data dimensions We created three datasets, varying the number of features ($n=20$, $50$, $100$) and keeping $p_{f}=0.68$ the same for all datasets. In all three cases, the binary classifier was a unit vector of length $n$. We created the actions dataset with $p_{a}=0.5$. Each action coordinate cost was randomly assigned in the range $n$. The cost of each action equaled the sum of the cost of action coordinates.
- •
Varied binary classifiers sparsity We generated five, $n=20$ datasets with varied binary classifier sparsity. The first dataset (Last5) has all zeros except for the last five features. The second dataset (First5) has all zeros except for the first five features. The third dataset (First10) has all zeros except for the first ten features. The fourth dataset (Last10) has all zeros except for the last ten features. Finally, the fifth dataset (Mid5) has a binary classifier for which the five middle features are one and the rest are zero.
- •
Varied access to actions We also consider a setting where grouped agents have restricted access to a set of actions. We consider two main settings: 1) actions generated with the same probability $p_{a}=0.5$ and agents are randomly assigned a subset of actions; and 2) agents assigned to groups and each group has its own actions generated by different probabilities $p_{a}=[0.4,0.5,0.6,0.7,0.8].$ In what follows, we refer to the first setting as manual groups and the second as probabilistic groups. See Figure 4(a) and Figure 4 for the statistics of the datasets.

Figure: (a) Manual groups
Refer to caption: x1.png

Each agent had exactly one optimal CFE, i.e., there were no equally cheap alternate CFEs. We excluded four-action CFE agents because they were very limited in number (e.g., only $4$ agents of the $20$-feature dataset), and even after the data split, they were in train-set. In the case of varied binary classifiers sparsity datasets, due to reduced thresholds required for validity, some agents did not need CFEs and were therefore excluded.

For each dataset of agents and their associated optimal CFEs, we created three datasets: all where all data is included, >10 where a frequency of more than $10$ agents per CFE is ensured, and >40 where a frequency of more than $40$ agents per CFE is ensured.
We then encode the CFEs into named-action, full-action and named CFEs, fit for training and testing each specific proposed CFE generator.
We create $80\%/20\%$ train-set/test-set splits for each of the datasets. In the case of the >40 dataset, each CFE has a frequency of at least $20$ in the train-set. We generate a different data split for every experiment and all methods use the same data split.

### 4.2 Data observations

Although most actions have effects on multiple features of the agent state, most agents require more than one action to achieve all the capabilities needed for a positive classification, which increases with the data dimension, $n$.
Additionally, the uniqueness of CFEs increases with the data dimension.
The average frequency of the CFEs for the all train-set for the $20$, $50$, and $100$ feature datasets is $46.64\%$, $21.75\%$, and $8.09\%$, respectively.
Additionally, $18.115\%$, $20.797\%$, and $31.072\%$ of the CFEs of the train-sets of the $20$, $50$, and $100$ feature datasets, respectively have a frequency of one.

In Manual groups datasets, agents are more balanced with respect to the number of actions needed (see Figure 4(a)) because the agents have access to the same distribution of agents, i.e., although agents in each group have access to only a selected group of actions, all actions for all groups were generated with the same probability, $p_{a}=0.5$.
However, for the Probabilistic groups datasets, as seen from Figure 4(b), the lower the probability of action capabilities $p_{a}$, the more actions agents need to acquire all the capabilities needed for a positive classification. In other words, some agents in some groups only have access to more expensive and limited capability actions compared to agents in other groups. Agents in group 0 0 of Probabilistic groups have a harder time (limited capability and more expensive actions), getting positively classified than those in group $4$.

### 4.3 CFE generator architectures

The Hamming distance named CFE generator had varied the nearest neighbors: $5,10,$ and $15$, for the $20$-, $50$-, and $100$-dimensional datasets, respectively.

We mainly based the architectures for the multi-class classification (MC) named CFE generator on neural network models.
Typically, each model has two hidden layers, each consisting of $2000$ neurons, $\ell_{2}$ regularization, dropout, and batch normalization. The model architecture was optimal for the $20$-, $50$-, and $100$-dimensional datasets.
We used the Adam optimizer [] for all datasets and implemented early stopping with the restoration of the best weights after a patience level of $360$. On average, we set the batch size to $2000,$ and the number of epochs set to $3000$.

The named-action (NA) CFE generator, like the MC CFE generator, relied on neural network models. The model has three hidden layers, each with 2000 neurons, $\ell_{2}$ regularization, dropout, and batch normalization.
We used the Adam optimizer [] and implemented early stopping with best weights restored after a patience level of $300.$ We, on average, set the batch size to $6000$ and the number of epochs to $5000$. We choose the values of $\alpha$ from the set $\{0.05,0.1,0.07\}$ and $p_{w}$ from $\{0.05,0.1,0.07\}$.

We utilized two kinds of neural network models for the full-action CFE generator: sequential encoder-decoder and NA CFE generator-like networks. To fit the NA model setting for the latter model, we added padding to the CFE vectors. The architecture and hyperparameters for both networks varied greatly depending on the context. In general, the models were shallow and implemented on CPU machines.

### 4.4 Evaluation of generated CFEs

For all the CFE generators, we evaluate the generated CFEs with the zero-one loss that compares the generated CFE $\hat{I}_{i}$ to the true CFE $I_{i}$.

$$ $\mathcal{L}_{\textrm{eval}}(I_{i},\hat{I}_{i})=\begin{cases}0&\text{if }I_{i}= \hat{I}_{i}\\ 1&\text{if }I_{i}\neq\hat{I}_{i}\end{cases}$ $$

## 5 Experimental Results

In this section, we empirically demonstrate the strong performance with which our method generates optimal CFEs for new instances of negatively classified agents.

Figure: Figure 5: Accuracy of various CFE generators on varied datasets. Accuracy of the named (a), named-action (b), and full-action (c) CFE generators on $20$-dimensional, all dataset. The named CFE generator is the most accurate, and in all cases, single CFEs were the most accurately generated.

Figure: Figure 6: Accuracy of named action CFEs generators on the $20$-dimensional, >40 dataset.

### 5.1 Accuracy and Confidence of CFE Generators

CFE generators generally performed well on new agents. On the $20$-dimensional dataset, the named-action CFE generator generated CFEs for new agents at an accuracy of
$96.9$% on all, $98.4\%$ on >10, and $99.3\%$ on >40 datasets (see Table 2). Similarly, as shown in Figure 5, the named and full-action CFE generators, do equally well.

The CFE generators are confident when they are correct. As seen from Figure 7(a), the confidence scores are close to $1$ when the named-action CFE generator correctly generates CFEs for the test-set agents.
Additionally, the accuracy of CFE generators has very small margin of error, therefore results are precise and reproducible (see Table 2).

**Table 2: Accuracy of CFE generators: named (MC), named-action (NA) and full-action (FA), on $20$ feature: all, >10, and >40 datasets.**
|  | CFE Generators on $20$-dimensional Datasets |  |  |  |
| --- | --- | --- | --- | --- |
|  | all | >10 | >40 |  |
| MC | ${0.969}\pm 0.00284$ | ${0.984}\pm 0.00208$ | ${0.993}\pm 0.00141$ |  |
| NA | $0.854\pm 0.00581$ | $0.886\pm 0.00531$ | $0.940\pm 0.00411$ |  |
| FA | $0.839\pm 0.00605$ | $0.892\pm 0.00518$ | $0.937\pm 0.00420$ |  |

Figure: (a) CFE generator confidence scores
Refer to caption: x3.png

### 5.2 Effect of Data Dimension and CFEs Frequency

Due to the uniqueness of CFEs, after data partitioning, some CFEs appeared in one data split and not the other.
For example, for the $20,50$, and $100$ features: all datasets, some CFEs appeared in the test-set but not the train-set.
There were $52,154$ and $708$ unique CFEs in the test-set that were not seen before in the train-set for $20,50$, and $100$ features: all datasets, respectively.

The CFE generators become less accurate as the frequency of CFEs in the train set decreases.
In Table 2, the accuracy of all CFE generators for the $20$ feature dataset was highest when CFEs had a frequency of at least $20$ in the train-set (>40) and lowest for all data (all), in which case, some CFEs appeared in the test-set but not the train-set. For example, the accuracy of the named CFE generator decreased from an accuracy of $99.3\%$ on $20$-dimensional >40 dataset to $96.9\%$ on $20$-dimensional all dataset.

Since the frequency of CFEs in train-set decreases with increases in data dimension, the generalization of CFE generators decreases with dimension. As seen in Table 3 (top), the named CFE generator had the lowest accuracy on the $100$-dimensional dataset and the highest on the $20$-dimensional dataset. For example, while the named CFE generator had an accuracy of $74.4\%$ on the $50$-dimensional all dataset, it had an accuracy of $96.9\%$ on the $20$-dimensional all dataset.

Additionally, the minimum frequency of CFEs required for a generalizable CFE generator increases with information in the CFE and the number of features in the agent state.
While the frequency of $20$ is sufficient for all $20$ features CFE generators (see Table 2), a frequency of at least $20$ CFEs in the train-set is sufficient for named CFE generators for the $50$ and $100$ feature datasets, and a higher CFE frequency is needed for named-action CFE generators (see Figure 7(b)).

**Table 3: On the top, accuracy of the named-action (NA), full-action (FA), and named (MC) CFE generators for $20$ ($20$-dim), $50$ ($50$-dim) and $100$ ($100$-dim) feature: all, >10, and >40 datasets. The bottom table shows that data augmentation improves accuracy of CFE generators, as seen for named CFE generators on $20,50$, and $100$ features: all datasets.**
|  | CFE Generators on $20$-, $50$-, and $100$-dimensional Datasets |  |  |  |
| --- | --- | --- | --- | --- |
|  |  | all | >10 | >40 |
| MC | $\hphantom{1}20$-dim | ${0.969}\pm 0.00284$ | $0.984\pm 0.00208$ | ${0.993}\pm 0.00141$ |
| NA | $\hphantom{1}50$-dim | ${0.744}\pm 0.00608$ | $0.838\pm 0.00534$ | ${0.915}\pm 0.00458$ |
| FA | $100$-dim | ${0.354}\pm 0.00664$ | $0.630\pm 0.00778$ | ${0.856}\pm 0.00772$ |

Figure: Algorithm 1 Data Augmentation

#### Data augmentation

To increase the frequency of CFEs, we employ two kinds of data augmentation using Algorithm 1.
The principle we follow for Algorithm 1 is to make the agent worse enough, such that the current CFE is still the best CFE for the worse-off agent. Worse-off agents are those such that the features where the CFE is doing more than required are made worse, i.e., for $j$ such that ${x}^{\star}_{ij}>t_{j},{aug}_{j}<x_{ij}$. A CFE is doing more than required to feature $j$ of $\mathbf{x}_{i}$, if by applying it to ${x}_{ij}$, ${x}^{\star}_{ij}>t_{j}$.
A derived worse-off augment $\mathbf{aug}$ is valid if $\mathbf{x}_{i}$’s CFE is the best CFE for it, $\textrm{aug}^{\star}_{j}\geq t_{j},\forall j\in[n]$.

With Algorithm 1, we augmented the train-set to ensure that more CFEs are included and representation of CFEs is balanced (AG1). As seen from Table 3 (bottom), applying AG1 improves the accuracy of the CFE generators. For the $100$ feature dataset with the named CFE generator, accuracy increases from $35.37\%$ before data augmentation to $50.54\%$ after AG1.

After applying AG1, we apply another level of data augmentation, AG2, aimed at increasing the number of frequency of CFEs in the train-set whose current frequency is less than $20$.
We reduce the number of CFEs with less than $20$ agents from $813$ to $638$, $2676$ to $2005$, and $9043$ to $7144$ for the $20$- $50$- and $100$-dimensional datasets, respectively.
AG2 improves the accuracy of the CFE generators as shown in Table 3 (bottom). For example, for the $100$-dimensional dataset with named CFE generator, accuracy increases from $35.37\%$ to $78.99\%$.

### 5.3 Differential Validity & Grouped Actions Access

In addition to the action-specific and classifier access informational challenges, we also examine cases where grouped information about agents is unknown.
We examine two additional information challenges: agents verified by different thresholds (differential validity) and agents having restricted access to a group of actions (manual groups and probabilistic groups ). Refer to Section 4.1 for information on how we created these groups for the experimental setup.

Without explicit knowledge of the differential validity, when given test-set agents, the CFE generators successfully generate the right CFEs. The full-action CFE generator achieves an accuracy of $99.683\%$ on First10, $99.496\%$ on Last10, $100\%$ on First5, $100\%$ on Mid5, and $100\%$ on Last5, varied validity groups.
Similar to differential validity, we study the case in which the agents in a group only have access to a selected set of actions. Without explicit knowledge of groups and the actions available to the agents in each group, the CFE generators correctly generate the CFEs for test-set agents in both manual groups and probabilistic groups (see Table 4).

**Table 4: Group-wise accuracy of the CFE generator on manual groups & probabilistic groups.**
| Manual Groups |  | Probabilistic Groups |  |  |
| --- | --- | --- | --- | --- |
| Group | Accuracy |  | Group | Accuracy |
| group 0 0 | $0.881\pm 0.01200$ |  | group 0 0 ($0.4$) | $0.880\pm 0.04400$ |
| group $1$ | $0.871\pm 0.01260$ |  | group $1$ ($0.5$) | $0.771\pm 0.02081$ |
| group $2$ | $0.875\pm 0.01249$ |  | group $2$ ($0.6$) | $0.802\pm 0.01571$ |
| group $3$ | $0.847\pm 0.01359$ |  | group $3$ ($0.7$) | $0.873\pm 0.01241$ |
| group $4$ | $0.886\pm 0.01212$ |  | group $4$ ($0.8$) | $0.931\pm 0.00947$ |

Since agents in the Manual groups had more balanced access to actions (Figure 4(a)), CFE generators had almost similar accuracy
(${\sim}87\%$) in the generation of CFEs across all agents in different groups (as shown in Table 4 (left)). On the other hand, agents in the Probabilistic groups had access to varied actions (see Table 4 (right))), which led to varied accuracy in generating their CFEs. For instance, as expected, the CFEs for Probabilistic groups $4$ agents with one-action CFEs were more accurately generated with an accuracy of $93.06\%$ as compared to group 0 0 and $1$ agents, generated at an accuracy of $88.04\%$ and $77.09\%$, respectively.

### 5.4 Single-action CFEs vs. Multiple-action CFEs

In general, all CFE generators, regardless of information entailed in the CFEs, generate single-action CFEs more accurately than multiple-action CFEs. As can be seen in Figure 5a, one-action CFEs were generated at higher accuracy of $99.4\%$, compared to $96.2\%$ for two-action CFEs and $87.1\%$ for three-action CFEs. Similarly, as seen in Figure 5c, full-action CFE generators generated one-action CFEs at an accuracy of $94.4\%$, compared to $79.6\%$ for two-action CFEs and $60.0\%$ for three-action CFEs.
This might be partly because each CFE regardless of length has the first action, therefore there is more data on the first action than any other action, so in cases of single action, they are more accurately generated.

### 5.5 Comparison of CFE Generators

Figure 5a to 5c and Table 2 show that named CFE generators are more accurate and need less CFE frequency in the train-set, than named-action and full-action CFE generators.
As can be seen in Table 2, the named CFE generators consistently generated CFEs at a higher accuracy than the named-action and full-action CFE generators. For the $20$ feature, all dataset, MC had an accuracy of $96.9\%$, compared to $85.4\%$ with NA and $83.9\%$ with FA.
Additionally, as shown in Figure 5a and 5b, the multi-class classification named CFE generator performs better than the baseline Hamming distance CFE generator.

Figure: (a) Infeasible mistakes
Refer to caption: x4.png

### 5.6 Feasibility of CFE Generators’ Mistakes

A generated CFE is a mistake when it doesn’t match the true CFE.
A CFE mistake is said to be feasible if transforms the agent’s initial state to a counterfactual state but is not the lowest-cost CFE. CFE mistakes are labeled as infeasible if they do not transform the agent to a counterfactual state.
Feasible CFE mistakes are by definition, more expensive than the true CFEs, while infeasible CFE mistakes are cheaper than the true CFEs (see Figure 8).

Of the $1.58\%,16.23\%$ and $37.00\%$ mistakes the named CFE generator makes on the $20$-, $50$-, and $100$-dimensional >10 datasets, $100\%,99.23\%,$ and $87.29\%$, respectively, were feasible. Similarly, the majority of the mistakes of the full-action CFE generators were feasible, e.g., for the $20$-dimensional >10 dataset, of the $10.8\%$ of the mistakes, $63.10\%$ were feasible.

Additionally, the percentage of feasible mistakes decreases with the frequency of CFEs in the train-set, e.g., the percentage of feasible mistakes decreases from $87.29\%$ on the $100$-dimensional, >10 dataset to $57.83\%$ on $100$-dimensional, >all dataset.

## 6 Conclusion

In this work, we provide a solution to the informational and computational challenges of CFE generation in settings where selecting a set of actions corresponds to solving a weighted set cover problem.
We propose three CFE generators: named-action, full-action, and named CFE generators. The CFE generators are computationally cheaper than the single agent optimization-based ILP CFE generator, and each addresses a unique informational challenge specific to the CFE, its action, and its costs.
We empirically show that the CFE generators generate CFEs for new agents at high accuracy, which increases with the frequency of CFEs in the training set.
Lastly, we explore two other potential informational challenges: agents with varied access to actions and different agents classified by different classification thresholds.
Without explicit information on which agents were classified by which threshold or which agents had access to which actions, given the mappings of agents to CFEs, the CFE generator accurately generates CFEs for new agents.

#### Limitations

We focus on learning to generate CFEs in settings where actions provide agents with various “capabilities” and a CFE is a solution to a weighted set cover problem. This limits CFEs to being characterized as a set of actions to perform. More generally, one could consider settings where the order of actions matters, such as where a CFE corresponds to an optimal policy for an agent in a deterministic Markov decision process (MDP). Even more generally, one could consider actions whose effects are stochastic, and a CFE then corresponds to an optimal policy for the agent in a general MDP.

In our work, we investigate two grouped agent settings. These settings involve agents having different access to different actions and agents classified by different thresholds. Promising future works could extend these settings to more complex scenarios and explore potential issues such as survivorship bias and its effect on generating CFEs. Additionally, future research could investigate the ethical implications of generating CFEs using data-driven algorithms.

Lastly, it is important to note that our approach to generating CFEs is subject to certain assumptions. We assume that variables are discrete, that generalized CFE generators have access to labeled historical agent-CFE data and that agents have only one optimal CFE. These are all potential directions for future work.

#### Ethical statement

Our proposed approaches to CFE generation are closely related to data-driven algorithm design.
As a result, ethical concerns related to data-driven algorithms, for example, potentially propagating and exacerbating biases in historical agent-CFE data, might apply to our proposed CFE generators.
Additionally, our CFE generators are not $100\%$ accurate, and the CFE generator mistakes could lead to the wastage of the agent’s effort and other undesirable downstream effects like wrong allocation of resources.
The experimentation code is at this [link](https://anonymous.4open.science/r/GeneralCFEGenerators-0800/README.md).

## Acknowledgements

We thank Alexandra DeLucia for the helpful feedback on the manuscript.
This work was supported in part by the National Science Foundation under grants CCF-2212968 and ECCS-2216899, and by the Simons Foundation under the Simons Collaboration on the Theory of Algorithmic Fairness.

## Appendix A Supplemental Data

We created agent-CFE datasets using solutions of the weighted set cover problem, implemented with CVXPY Python package [, ]. Below, we provide information on missing dataset statistics on varied binary classifier sparsity and action access.

**Table 5: Statistics of the datasets used in the experiments.**
| dataset | dataset size | one-action CFEs | two-action CFEs | three-action CFEs |
| --- | --- | --- | --- | --- |
| $20$-dimensional dataset | $71125$ | $23687$ | $44858$ | $\hphantom{0}2576$ |
| $50$-dimensional dataset | $98966$ | $\hphantom{0}1262$ | $96770$ | $\hphantom{00}934$ |
| $100$-dimensional dataset | $99728$ | $\hphantom{0000}0$ | $45515$ | $54213$ |
| Manual groups | $73484$ | $13480$ | $56653$ | $\hphantom{0}3351$ |
| Probabilistic groups | $70226$ | $44661$ | $20258$ | $\hphantom{0}5307$ |
| First10 | $74524$ | $61794$ | $12046$ | $\hphantom{000}39$ |
| First5 | $74594$ | $60656$ | $\hphantom{0}6005$ | $\hphantom{0000}0$ |
| Last10 | $74401$ | $53822$ | $19952$ | $\hphantom{0000}1$ |
| Last5 | $74565$ | $66068$ | $\hphantom{00}644$ | $\hphantom{0000}0$ |
| Mid5 | $74594$ | $63530$ | $\hphantom{0}3010$ | $\hphantom{0000}0$ |

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: I have a few questions that I’m still trying to fully understand. I would greatly appreciate any clarification you could provide on the following points:

- Why are these approaches considered "high-level"? Adjusting multiple feature combinations is not a new idea, so I’m curious about what uniquely qualifies these methods as high-level.
- How does the method handle datasets with both discrete and continuous actions?
- How are the pre-defined parameters, such as c and b, chosen? Since these parameters are not derived directly from the data, what guidelines or expertise inform their selection? Additionally, would the model’s performance benefit from dynamically adjusting these parameters based on the dataset, and is there a sensitivity analysis to evaluate how variations in bb might impact the results?
soundness: 2
strengths: - The paper provides a comprehensive analysis across diverse feature types, different dataset dimensions, and varying CFE frequencies. It also discuss fairness.
- The proposed methods are model-agnostic. So it can be adapted to different models.
summary: This paper proposes three high-level data-driven CFE generators: hl-continuous uses ILP to find the least costly set of continuous actions to change an individual's status; hl-discrete selects from discrete actions by solving a set cover problem; hl-id assigns a label to provide general recommendations without specific actions for cases where information aren’t accessible. The datasets include real-world health, some semi-synthetic and fully synthetic datasets.
weaknesses: - This paper is limited to binary classification.
- Equation (2) presumes a linear classifier, which may not represent the complexity of real-world models. This simplification could restrict the performance and generalizability of the proposed methods.
- The reliance on pre-defined parameters, such as classifier coefficients and thresholds, may reduce the flexibility and accuracy of the approach across diverse datasets.  These parameters are not directly derived from the data, potentially leading to counterfactual explanations that do not align well with actual case. The paper also does not include a sensitivity analysis of the pre-defined parameters.
- The study does not compare the proposed methods against other CFEs (only low-level CFE).

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 2
questions: They mention that previous methods have high computational complexity, impacting scalability. Could you clarify how your proposed algorithm addresses this issue?
soundness: 2
strengths: Strength:
1 The topic is quite interesting. 
2 The algorithm is concise and several case studies are provided.
3 The paper is well presented.
summary: In this paper, the author proposes an algorithm for generating high-level counterfactual explanations (CFs). Rather than modifying individual features, the approach involves modifying groups of features simultaneously. The task is formulated as an integer linear program to obtain an optimal solution. Three different versions of the algorithm are presented for generating CFs.
weaknesses: 1 The motivation is unclear. From my understanding, they aim to define a high-level action to identify counterfactual explanations. However, they do not clearly explain why this high-level action is suitable for users to act upon. Additionally, they should clarify how these actions are identified.
2 The paper lacks a theoretical guarantee to demonstrate the efficiency of the proposed algorithm.
3 The proposed algorithms overlook the practicality of the generated counterfactual explanations (CFs).
4In Formula 2, the linear integer program (LIP) could be very time-consuming when the action space is large. They did not explain how to constrain the action space.

---

confidence: 5
contribution: 1
initial_rating: 1
presentation: 1
questions: All my questions are written in the weakness section. Overall, the authors really need to convince that their technique is usuable at all (because currently it seems it is not -- one needs to have access to thousands of CFEs to use this technique) and write the section on how to actually use the technique (section 3.2 and 4.1 need to be explained much more better with a motivation for each part)
soundness: 1
strengths: The paper proposes to tackle an interesting problem of providing higher level actions, that might make it easier to communicate actionable changes to a user
summary: The paper proposes to provide higher-level actions as CFEs to individuals who have received undesirable predictions from a classifier, instead of low-level CFEs that most previous techniques provide. The authors claim that higher-level CFEs are sparser, make more improvement to an individual, are diverse, more fair and personalized.
weaknesses: The paper suffers from several weaknesses. I have enumerated them below, and marked the ones that are major. If the authors like, they can only focus on the major weaknesses:

1. [Major] The paper's motivation states that their proposed technique will be useful in cases when an individual does not have access to the priviledged information such as the ability to query the classifier. Now the entire proposed technique hinges on the ability to generate CFEs for all individuals and then train another model on that top of that? So how is an individual who does have access to a classifier use this technique when the pre-requisite of the technique is to generate CFEs not for 1 just thousands of individuals and then use the technique to do something for that individual? The proposed technique does not need less privilege than having access to the classifier, in facts it requires a 1000X more priviledge, the ability to generate CFEs for thousands of individuals. So the question is how is your technique applicable for an individual who does have access to a classifier as claimed in your motivation? 
Could the authors explain how their method would be deployed in a real-world setting where individual users lack access to the classifier? Who would be responsible for generating the initial dataset of CFEs, and how would this be done with the restrictions the paper aims to address?"

2. in line 152 you mention there are 4 notable limitations of low-level CFEs. There are no references to show that these limitations are indeed "notable". 

3. In line 154 you say: solving this problem is computationally expensive as it is NP-hard optimization for each new agent. What is an agent? Please define it. Also in practice this optimization is quite cheap, fast, and scalable. See the dozens of the papers cited in Verma et al 2020. 

4. In line 157, you say that "each action modifies an individual feature" -- that is not true for most causality based CFE generation techniques, like Consequence-aware sequential counterfactual generation, Geco: Quality counterfactual explanations in real time, Amortized generation of sequential algorithmic recourses for black-box models. 

5. [Major] Given example of a situation where a CFE providing organization would not have access to the underlying classifier. Usually CFEs are provided for financial situations like loans and credit cards, and the banks are supposed to provide CFEs. In this case, the banks have access to their own models. Your current example of a dietician and celiac **does not** do a good job, celiac classification is a very simple rule based thing and the advice (CFE as you say) is known to all the physicians. No body uses a complex model that makes a decision that nobody understands (due to it being a black-box model) and therefore you need a CFE. Could the authors provide a more relevant example, perhaps from domains like algorithmic hiring or credit scoring, where the decision-making process is less transparent and the need for actionable explanations is more apparent?

6. [Major] Is Hl-discrete not the same as HL_continuous with just binary weights on the features? Is that is the case, then why do you make it as a separate case, its just a special case of HL_continuous, does not need that much attention and focus in the paper.

7. The HL-ID suggestions are generic and not useful, it is like a banker suggesting to a person whose loan request is canceled to increase their credit score or their bank balance -- everybody knows that. The point of a CFE is to provide a specific and small changes that are easily achievable, not generic advice. 

8. [Major] Line 258 Please define what you mean by the symbol individual -> CFE dataset. From what I understand this is a dataset of individuals and their corresponding CFEs (which you never mention how you computed)

9. [Really Major] What is the job of the neural networks you train in section 4.2? From what I understand you first gather this dataset of individuals and CFEs, then somehow you get the actions for HL-continuous (mentioned on line 322-323) and then you use these actions to generate CFEs for new individuals? If this is the case, then what do you need the neural networks for, you can just use ILP to do this as stated in Section 3.1. The experimental section is really badly written and I did not understand the motivation of what you are doing at all. Please rewrite the section stating why you did something before telling what you did and even before that show the full pipeline of what you plan to do (ideally in a figure). Could the authors provide a clear, step-by-step explanation of their method's pipeline, including:

**a)** How the initial dataset of individuals and CFEs is generated
**b)** The specific role of neural networks in the process
**c)** How this approach differs from or improves upon using ILP directly
**d)** A diagram illustrating the full pipeline from data generation to CFE prediction for new individuals

10. [Major] Where do you magically get the actions to use in HL-continuous (or discrete) you mention in line 322?

11. Please explain the job of neural networks in HL-ID CFE generator? In this case you don't even have access to the classifier, so what loss are you optimizing over? You don't even know if the actions you propose will do anything to change the prediction of the classifier (because of the setting)

12. The assumptions and statements in the experimental results section 5.1 are either unsupported or obvious:
      1. Line 362: sparsity might be undesirable and challenging because individuals aim to implement as many changes as possible: No this is not true at all, in case of CFEs individuals want to just change the classifier prediction and want to implement as **less** changes as possible to get it. Your examples of health are invalid because nobody uses a complex neural network classifier to classify if someone is unhealthy and healthy, and your goal is not to change the prediction of the classifier, but to become healthy. And therefore in a health example you want to implement a lot of changes, not in the case of a usual CFE like a financial situation. 

       2. Line 372: Despite hl-continuous CFEs having fewer actions on average, they result in more feature changes: This is **really obvious** in your case. You are just clubbing multiple changes to several features and calling that one action. I could define one action that changes all features and that final datapoint is classifier as positive by the classifier. So then I can say my proposed techniques just requires 1 action and this action changes all the features and achieves 100% success rate. I don't think that is useful. 

      3. Line 404: Additionally, on average, hl-continuous CFEs, with fewer actions (∼ 2) result in states that are more distant: This is also **obvious**. If your actions make large changes in features, it is obvious that the new datapoint will be more distant. 

       4. Line 409: hl-continuous CFEs tend to be more desirable for decision-makers and individuals alike: how can you claim this? Did you do a user study or even any automated metric to show this? I don't think this is true. 

13. Line 390: What does "having a higher CFEs frequency" mean? What is CFEs frequency?

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Consider introducing the notion of high-level actions at the beginning of the introduction, defining them as combinations of low-level actions.
2. Why are hl-continuous counterfactuals considered superior to low-level counterfactuals? While having a predefined set of high-level actions with known outcomes can simplify the CFE generation process and facilitate testing, the feasibility of combining actions may not always be straightforward, and the constraints could be more complex. Have you tested your approach on more complex datasets with additional constraints to demonstrate its effectiveness?
3. For the ILP in Definition 2 (line 196), the condition $\epsilon_j\leq a_j$ appears to be redundant. If $a_j=0$ then $e_j$ has no effect, and if $a_j=1$ this condition always holds since both $\epsilon_j$ and $a_j$ are in $\{0,1\}$. Additionally, there seems to be a typo on the same line, where $\epsilon_i$ should be $\epsilon_j$.
4. Could you clarify the need for hl-discrete actions? It seems unnatural to limit changes to only "positive changes." Moreover, since the focus is on binary features, isn't this approach overly restrictive in your experiments, where $t = 1$ means targeting a specific state?
5. For the ILP in Definition 4, the constraint on line 220 should be written as $\sum_{j\in J}d_{ji}a_j +x_{i} \geq t_i$.
6. Could you clarify how the generators produce "generalizable CFEs" (line 52)
7. Regarding Figure 2 (a) Comparing actions may not be meaningful, as a high-level action can modify multiple features simultaneously, whereas a low-level action changes only one feature (also stated on line 356). (b) In the bibliography, the number of features changed is important for explainability. You should emphasize that, in the case of high-level actions, having more feature changes does not necessarily reduce explainability. (c) a more distant state does not necessarily indicate a higher improvement. Since most ML models used for generating CFEs are non-linear, the concept of CFEs is inherently linked to minimizing cost. Thus, the goal of a CFE generator should not be maximizing improvement, which contradicts the problem being addressed. (d) Higher frequency is expected because the actions are predefined, resulting in more "global" CFEs. (General comment:) It would be beneficial to include variance or standard deviation in the figures for a more comprehensive analysis.
8. In line 367, you mention "diverse improvements." Could you clarify what you mean by this?
soundness: 2
strengths: 1. Once the generator is trained, the counterfactual explanation (CFE) prediction is very efficient. With proper training and a high-quality dataset, the generator can achieve high accuracy in its results.
2. If a predefined set of actions is available, generating counterfactuals for subgroups can be more straightforward.
3. The proposed approach enables fairness auditing in a more structured and systematic manner.
summary: The authors identify limitations in traditional low-level counterfactual explanation (CFE) generators and propose an alternative approach involving three data-driven counterfactual generators. These generators are trained with high-level CFEs, which consist of combinations of high-level actions, where each action can alter multiple features. The high-level counterfactuals are defined as follows: (1) hl-continuous CFE, representing the lowest-cost subset of hl-continuous actions that can achieve recourse (either by addition or subtraction of the feature changes that correspond to each action); (2) hl-discrete CFE, which is formulated as a minimum weight set cover problem using hl-discrete actions (limited to the positive feature changes that correspond to each action); and (3) hl-id, for which the exact cost and the resulting feature changes are unknown. For (1) and (2) once the counterfactuals are defined, an integer linear programming (ILP) solution is applied to each instance, creating a training dataset consisting of (X, CFE) pairs. The generators are trained with these datasets.
weaknesses: 1. Training the generator requires solving integer linear programming (ILP) problems, which are specifically suited for linear classifiers. For other types of classifiers, creating the dataset necessitates brute-force methods, which may not be efficient.
2. The hl-discrete CFEs are limited to positive changes, which may not apply to non-linear models. Even for linear models, this approach requires additional preprocessing and a deeper understanding of the model's internal.
3. The hl-continuous and hl-discrete generators still rely on query access to the model and the cost of actions to create the training set, meaning that these requirements are not fully eliminated.
4. For the hl-id generator, the challenge remains in how to construct the training dataset, as the process is not clearly defined.

Meta-review: This paper addresses counterfactual explanation (CFE) generation with a focus on (i) scalability in the underlying state space - the set of feasible states in which an individual input can exist and (ii) actionability of the CFE - can an input x actually get to the suggested x’ to cross a decision boundary, or is that path from x to x’ blocked by causal constraints etc represented as an SCM, and (iii) comprehensible CFEs.  Reviewers appreciated the motivation of the problem and its placement in the literature, as well as the coverage of the approaches given (continuous actions, discrete actions, and the hl-id setting).  Unfortunately, after a rebuttal process, all reviewers had unanswered questions, with no clear champion for the work.

Decision: Reject