Prediction without Preclusion: Recourse Verification with Reachable Sets

Thank you for your review and questions! We have addressed your questions below

The paper compares the proposed method to two conventional baselines in terms of improving recourse feasibility.

Thanks for asking this question! This question provides an excellent opportunity to clarify the concept of "feasibility".

These methods are designed to find actions that are “feasible” in that they cross over the decision boundary of complex models like XGB and DNNs. It’s important to note that their primary focus is not on guaranteeing feasibility concerning "actionability constraints."

The recourse problem is:

$

    \min \quad & cost({\mathbf{a} | \mathbf{x}})\\
    s.t. \quad & f(\mathbf{x} + \mathbf{a}) = +1 \\
    & \mathbf{a} \in A({\mathbf{x}})

$

The methods you describe are designed to return actions that obey the $f(x+a) = 1$ constraint. However, they cannot handle the actionability constraints $\mathbf{a} \in A(\mathbf{x})$. So their “actions” will violate the $\mathbf{a} \in A(\mathbf{x})$ condition. For example, Face [2] fails to handle interval, encoding, and implication constraints (see Table 1). In practice, this means that they will behave in the same way as DiCE which fails to handle similar constraints. This leads to loopholes (method returns an action that violates the actionability constraints) and blindspots (a point that has a feasible action, but the search algorithm cannot find it) as seen in Table 3

I am unsure about the paper's significant contribution. The primary focus appears to be on describing a search algorithm to confirm the existence of a feasible action for a user.

This is a very difficult problem to address (please see this for more details). Stepping back, however, the technical contribution is that it’s hard to build a method that can find actions that will work with general classes of models and that satisfy actionability constraints.

The reason why we need methods like the ones above is that it is inherently difficult to find points that cross over the decision boundary when we work with complex models like DNNs, XGB, and RF. The methods resolve this issue to ensure feasibility with respect to the $f(\mathbf{x}+\mathbf{a})$. In doing so, they sacrifice the ability to certify infeasibility with respect to the $\mathbf{a} \in A(\mathbf{x})$ constraints.

This is where reachable sets are powerful. Our framework provides a way to handle this for any model. We can build a reachable set once and then apply it to many models $f$. This allows us to certify feasibility for complex models like XGBoost, DNNs, and RFs.

My major concern regarding this paper is its inapplicability to continuous features, as claimed by the authors.

This seems to be a misunderstanding of something that we wrote.

Our approach is applicable to continuous features! Every method that we have in the paper will work on classifiers that use continuous features. Our software is designed to handle them.

The only issue that we have with continuous features is that we may not be able to certify infeasibility in all possible cases. In this regime, we still obtain meaningful results with regard to verification – by certifying feasibility and by flagging certain kinds of infeasibility.

We can show that recourse is feasible by using IsReachable to show that we can reach other points in the sample. Or by certifying that a point produced using another method obeys actionability constraints. We can flag infeasibility by detecting only fixed points by calling the FindAction Routine (Eq 5). In the remaining, our methods will still work and output results that are correct as we will claim “I don’t know” rather than “feasible” and “infeasible”.

We can show that recourse is feasible by using Theorem 3 with any labeled dataset to set an upper bound for the number of points needed in a reachable set.

The optimization problem (2) aims to optimize a constant value of 1. What does this objective imply? Does this optimization problem solely seek to find all feasible actions (feasible recourses)

Yes, this is a correct interpretation.

Is there a relationship between two reachable sets? For instance, if x1 is within the reachable set of x and x2 is within the reachable set of x1, is it guaranteed that x2 is also within the reachable set of x

This is not guaranteed to be true. Suppose $\mathbf{x_1} \in R(\mathbf{x_0})$ and $\mathbf{x_2} \in R(\mathbf{x_1})$. $R(\mathbf{x_0})$ and $R(\mathbf{x_1})$ may or may not be overlapping. In the case when they are not overlapping then $\mathbf{x_2}$ does not lie in $R(\mathbf{x_0})$. In the case when they are overlapping $\mathbf{x_2}$ may lie in $R(\mathbf{x_0})$ if $\mathbf{x_2}$ is in the overlapping region. The only time when $\mathbf{x_2} \in R(\mathbf{x_0})$ is guaranteed to be in $R(\mathbf{x_0})$ is when $R(\mathbf{x_1}) \subseteq R(\mathbf{x_0})$.

If I understand correctly, in cases with only discrete features, your problem can be formulated as a graph-based path-finding problem. Each vertex represents a user's feature set, and edges connect vertices with their reachable sets.

A graph-based path-finding algorithm would not work for two reasons:

1. In cases with only discrete features, the problem can only be cast as a graph-based path-finding problem if we have observed all possible samples. Otherwise, we may be interested in looking for paths to vertices that do not exist.

2. In the case that we had observed all possible features, then reachable points would not necessarily be connected. For example, suppose that the reachable set for the point $\mathbf{x\_0} \in X$ contains the points $\mathbf{x\_1} \in R(\\mathbf{x\_0})$ and $\mathbf{x\_2} \in R(\\mathbf{x\_0})$. In this case, we may have that $\mathbf{x\_2} \not\in R(\mathbf{x\_1})$ and $\mathbf{x\_1} \not\in R(\mathbf{x\_2})$. Please see our previous response for how reachable sets may not be overlapping or contained in one another. Therefore, there may be no path connecting points within the reachable set.

In real-world scenarios, certain actions may be feasible for one group of people but not for others, reflecting the user-dependence feature of reachable sets more broadly. How does your method adapt to such practical cases

Thank you for this question! This would be a setting where - for example, 100 people have the same features $\mathbf{x}\_0$ but different actionability constraints from $A(\mathbf{x}\_0)$. If the people had different features, then they would each have a different reachable set.

In general, the machinery that we develop can be used with any action set at $A(\mathbf{x}_0)$. This means that if we could elicit actionability constraints from each person – using e.g., an interface like [1] - then we could use it to generate a personalized reachable set for each person and use that to verify the feasibility of recourse. In short, we can support this use case. However, we envision that the most common use case is that practitioners will have to run our methods without observing differences among individuals.

In our main use case, we purposefully disregard these individual-level differences and seek to find models that restrict access for all individuals. In this setting, we use an action set that consists of “inherent constraints”. For example, in section 5 we collaborated with a domain expert to identify constraints that would apply to all individuals. $A({\mathbf{x}})$ only includes basic constraints that should adhere to everyone. Thus, when we flag recourse as infeasible using $A(\mathbf{x})$, then it will imply that recourse is also infeasible under $A\_i({\mathbf{x}})$ since $A({\mathbf{x}}) \subset A\_i({\mathbf{x}}).$ We use this strategy in our experiments specifically for this reason – i.e., to show that recourse can be infeasible simply under actionability constraints that are “not subject to debate.”

[1] Wang, Zijie J, Jennifer Wortman Vaughan, Rich Caruana, and Duen Horng Chau. Gam coach: Towards interactive and user-centered algorithmic recourse. In Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, pages 1–20, 2023

In cases with only discrete features, the problem can only be cast as a graph-based path-finding problem if we have observed all possible samples. Otherwise, we may be interested in looking for paths to vertices that do not exist.

It's not necessary to construct the entire graph of all samples; the graph-based implication is just a more intuitive concept. Starting from the initial vertex $x_0$, you iterate through the child nodes that are both valid and within the Reachable set $R(x_0)$. For instance, let's consider the child nodes $x_1$ and $x_2$. If either $x_1$ or $x_2$ represents a recourse, the procedure concludes. If not, the procedure continues with the valid child nodes of $x_1$ and then proceeds to $x_2$. Note that in some cases, you do not need to consider all child nodes, just ones that are confirmed valid.

In the case that we had observed all possible features, then reachable points would not necessarily be connected. For example, suppose that the reachable set for the p ...

The graph I am referring to is specifically a directed graph. I'm having difficulty understanding your message.

Thank you for your time and feedback. We appreciate your suggestions for minor comments and will address them! We would like to help clarify the misunderstandings.

It is unclear how the separable features are identified. What role does the prediction model play in the identification of these feature?

There seems to be some kind of misunderstanding that we would like to correct. The prediction model plays no role in determining if features are separable or non-separable. Separable features are defined as features that can be altered independently under a given action set $A(x)$. For example, the features $reapplicant$ and $n\\_accounts$ can be altered independently of one another. However, features like $max\\_degree\\_BS$, $max\\_degree\\_MS$, $max\\_degree\\_PHD$ that arise from a one-hot encoding cannot be altered independently. Likewise, features that are tied together in $X$ like if $is\\_employed = true$ then $work\\_hrs\\_per\\_week > 0$.
In our case, the action set captures all the relationships described above. Given an action set $A(\mathbf{x})$, we can easily identify the features that can be altered independently if the actions from one feature $A(x_1)$ do not affect or are not dependent on the actions in $A(x_2)$. Likewise we can find the actions that are non-separable if the actions in $A(x_1)$ rely on other features. We can express the action set as a “product space” of smaller action sets over the features. We can use this to generate reachable sets for each action set in a way that is far more efficient without sacrificing correctness.

the verification step may return infeasibility certificate in partitions A_1(x) and A_2(x), but actionable recourses may still exist in the Cartesian product A_1(x) X A_2(x) of the two sets.

This seems to be a misunderstanding that stems from the previous comment on separability. This cannot happen because our partition is designed to specifically avoid this effect. In particular, we would only consider a partition where we can express the actions as $A(x) = A\_1(x_1) \times A\_2(x_2) \times A_m(x_m)$

Could this approach be extended to certify the existence or non-existence of an abundance of recourse options instead of just one. A single recourse option might not be feasible for everybody.

We thank you for bringing this to our attention!

Our methods can easily be extended to certify the existence or non-existence of multiple options. We can count the number of recourse options in a reachable set as a measure of “abundance.” Given a complete reachable set, we can certify existence or non-existence. Given an interior approximation, we can only certify existence. Stepping back, we think that the measures are also interesting as a richer measure of feasibility when recourse is feasible - e.g., if there is only 1 point in a reachable set that would lead to recourse, then recourse is brittle and existing methods for recourse provision are unlikely to find it (i.e., high likelihood of blind spot). We will mention this in our manuscript!

Could we incorporate costs for the actions and certify the existence of a low-cost recourse?

Yes this can be done. Here are the steps: Compute the reachable set such that $\\{ \mathbf{x} + \mathbf{a} \mid \mathbf{a} \in A({\mathbf{x})} \text{ and } \mathbf{a} \in \text{cost}(\mathbf{a};\mathbf{x}) \\}$ We can now filter the reachable set $R(\mathbf{x})$ to only include reachable points such that $\text{cost}(\mathbf{x},\mathbf{x_0}) ≤ B$ where $B$ represents a budget. Filtering out points after the reachable set has been computed allows us to generate the reachable set once and reuse it to handle different budgets. We do not explore this for two reasons. The first is because costs and budgets are difficult to elicit in a way that most people would agree on. The second, relatedly, is because we would like to flag infeasibility in a way that is not subject to debate. So if a model is precluded access, this is arising because of the oversight of basic actionability constraints rather than because we have elicited the wrong costs or set the wrong budget.

the purpose of using decomposition is to reduce the number of points to verify

We want to clarify that the purpose of decomposition is not “reduce the number of points to verify.” Rather it is a computationally efficient way to compute the reachable set $R(\mathbf{x})$. The action set remains the same regardless of decomposition. Figure 3 represents just how efficient decomposition is compared to brute force. In less than 3 seconds decomposition is able to fully compute large reachable sets of 600 points compared to brute force which can only generate 40 points in the same time frame.

Minor comments

Thank you for catching these. We have uploaded an updated manuscript with these fixes!

It is unclear how often does the undesired preclusion occur in practice. In particular, continuous features are quite common and may trivially avoid preclusion if the capacity of the predictive model is not constrained…. If the diversity of the approved users is so limited that no recourse can be found for user A

We think there may be a big misunderstanding, and we’d like to get to the bottom of it. To make things easier, let’s consider an extreme version of your setting. Say we have a classifier $f$ that approves one user with features $\mathbf{x}_\textrm{app}$ and rejects all other users with features $\mathbf{x}_i \neq \mathbf{x}\_{app}$ . Formally, we have:

$

f(x) = 1 \text{ for all } \mathbf{x} = \mathbf{x}_\textrm{app} \\ f(x) = -1 \text{ for all } \mathbf{x} \neq \mathbf{x}_\textrm{app}

$

Given a person with features $\mathbf{x}\_i$, let us define the change they need to reach features $\mathbf{x}\_\textrm{app}$ as $\mathbf{a}\_i = \mathbf{x}\_\textrm{app} - \mathbf{x}\_i$. Your review seems to suggest that we would claim that person $i$ does not have recourse when $\mathbf{a}\_i \notin A(\mathbf{x}\_i).$ To be clear, this is not the case. When $\mathbf{a}\_i \notin A(\mathbf{x}\_i)$, this only means that person $i$ cannot reach $\mathbf{x}_\textrm{app}$. However, we would not claim “preclusion” because there may be many other points that person $i$ could reach that lead to approval.

This is because we search over all possible changes that a user can perform - not simply the changes to reach users that are approved.

Our methods are designed to handle this search because we search for all possible actions that a person could perform over the feature space (i.e., rather than only the features of users in, e.g., a training dataset). Thus, the “diversity of users” in a dataset will not influence a claim of preclusion. When the feature set is discrete, we can search over all points in the discrete exhaustively, and thus claim that a person $i$ has recourse or does not have recourse. When the feature set is continuous, we can only claim that a person has recourse. If we cannot find a point for which a person has recourse, then we claim that we do not know.

Following question 1, I am wondering if it is reasonable to adopt the idea of cost constraint in recourse provision to reduce the reachable set? For example, we certify if a model is not "fixed" given an upper bound of cost.

Yes this can be done. Here are the steps: Compute the reachable set such that $\\{ \mathbf{x} + \mathbf{a} \mid \mathbf{a} \in A({\mathbf{x})} \text{ and } \mathbf{a} \in \text{cost}(\mathbf{a};\mathbf{x}) \\}$ We can now filter the reachable set $R(\mathbf{x})$ to only include reachable points such that $\text{cost}(\mathbf{x},\mathbf{x_0}) ≤ B$ where $B$ represents a budget. Filtering out points after the reachable set has been computed allows us to generate the reachable set once and reuse it to handle different budgets.

We do not explore this for two reasons. The first is because costs and budgets are difficult to elicit in a way that most people would agree on. The second, relatedly, is because we would like to flag infeasibility in a way that is not subject to debate. So if a model is precluded access, this is arising because of the oversight of basic actionability constraints rather than because we have elicited the wrong costs or set the wrong budget.

How do we check the quality of a recourse verification algorithm? Specifically, if we employ two recourse verification methods and get inconsistent results, how do we decide which one is better?

We should not get “inconsistent” results. Say that we have two different methods for recourse verification $Recourse_A({\mathbf{x}},{f},{R})$ and $Recourse_B({\mathbf{x}},{f},{R})$

Here, each method $Recourse_A$ and $Recourse_B$ takes as input a model $f$, a point $x$ and a reachable set $R(x)$. Given these methods, it would output a claim of “has recourse”, “no recourse”, or “I don’t know.”

In this case, the results should be consistent in that we should never have one method claim “recourse” and another method “no recourse.”

We can have a situation where $Recourse_A$ or $Recourse_B$ claims “I don’t know” while another claims “recourse” or “no recourse”:

Based on this, methods for recourse verification can only differ in terms of their abstention rate. Ideally, we would like for methods to avoid abstaining. In applications like credit scoring, we would like to have a low “abstention rate” on the points that do not have recourse. This is because we would like to flag models that can detect preclusion.

I thank the authors for the thorough response. The response addresses my concerns, particularly regarding Question 1. After evaluating this work again, we decide to keep my score and vote for accept. As previously commented, this work has some limitations (e.g. issues on continuous features) as acknowledged by the authors, while the idea of verification seems promising and potentially impactful. I also think the authors have established a solid foundation for this new topic, which can benefit researchers engaged in this area.

Thank you for your review and feedback! We found a few big misunderstandings in your review that we would like to address!

When introducing reachable sets, more details are expected to be discussed, i.e., continuous or discrete, ℓp-norm bound ball. The verification seems to be sound but incomplete, and it is expected to be compared to more off-the-shelf reachability-based verification methods in [1].

There seems to be a big misunderstanding that we would like to clarify! We are very familiar with the reachability-based methods to verify deep neural networks presented by Liu et al. [1]. One issue is that these algorithms are designed for deep neural networks, so they would not naturally work for complex model classes like RFs and XGB. The main issue is that these algorithms will fail for “recourse verification” because they cannot verify the stability of predictions under actionable perturbations.

In particular, the algorithms are designed to certify that the prediction of a DNN at $\mathbf{x}_0$ will not change under perturbations in a smooth and convex set – e.g., the set of all perturbations within a $\ell_p$-Ball. In a recourse verification task, however, we are exclusively interested in certifying that a model’s predictions at $\mathbf{x}_0$ would not change under the set of actionable perturbations: $\\{ \mathbf{x} = \mathbf{x}_0 + \mathbf{a} \mid \mathbf{a} \in A(\mathbf{x}_0) \\}$

This set of actionable perturbations is neither smooth nor convex. This is because the action set $A(\mathbf{x}_0)$ is neither smooth nor convex in the vast majority of applications we care about (i.e., classification tasks with semantic feature spaces). For example, $A(\mathbf{x})$ would require discrete perturbations for binary and integer-valued features like $n\\_accounts$. This is also the case for non-separable constraints that we need to enforce actionability over categorical variables like job_type or capture logical relationships like if $is\\_employed = `TRUE` \quad \implies\quad hrs\\_worked\\_per\\_week > 0$.

We are happy to include a comparison in a potential revision. However, we do not think that this would be informative since it would show that the methods fail at a task that they need to be designed to handle. In particular, we would expect to obtain a number of loopholes and blindspots using these approaches as we would have to work with a convex relaxation of the perturbation set.

There are no other baselines of recourse verification for the comparison of tightness and time efficiency.

This might also be a misunderstanding related to the issue above. This is the first paper to present an actual procedure for recourse verification, so there are no other baselines to compare to. There are also no other off-shelf methods that are designed for recourse verification in this setting – in part because we are exclusively interested in certifying stability over “actionable” perturbations where the perturbation set is almost always non-smooth and non-convex.

With this in mind, we did want to provide a detailed account of tightness and time efficiency. We discuss these issues in Section 3. To reiterate, the MIP is solved to optimality within ≪ 1s for the instances we consider in Section 4. In general, the core property that we exploit is that action sets can be decomposed to compute reachable sets. In Figure 3, for example, we can generate the largest reachable set that we would need in $\leq3$ seconds. Computation and time efficiency are important considerations since they may often present a barrier to adoption. Our results above suggest that these issues should not be a bottleneck in most practical applications. In the event that they are the algorithms have the benefit that they use limited memory and can be easily run in parallel over multiple CPUs. Another key benefit is that we only need to call these procedures once – as the reachable set that we recover can be used for all possible models

My biggest concern lies in the lack of contribution in the verification methods, which directly follow the basic idea of formal verification

Thank you for mentioning this! Some of this may stem from a lack of familiarity with work on algorithmic recourse. If so, please read our main response above. In short, formal verification is urgently required in this task – since models can assign fixed predictions that permanently preclude access from credit, employment, or assistance. The task is also challenging from a technical standpoint – as we must certify the stability predictions of a model over the set of actionable perturbations, which are neither convex nor smooth. This lack of structure makes it a very difficult problem to address, especially in a way that is model-agnostic. In contrast, existing robustness verification methods (e.g. [1]) primarily focus on structured and nice perturbation sets. We discuss these issues in Section 3, but we are happy to make it more prominent if you need.