Actionable Recourse in Linear Classification

Introduction

In the context of machine learning, we define recourse as the ability of a person to obtain a desired outcome from a fixed model. Consider a classifier used for loan approval. If the model provides recourse to someone who is denied a loan, then this person can alter its input variables in a way that guarantees approval. Otherwise, this person will be denied the loan so long as the model is deployed, and will lack the ability to influence a decision that affects their livelihood.

Recourse is not formally studied in machine learning. In this paper, we argue that it should be. A model should provide recourse to its decision subjects in applications such as lending (Siddiqi, 2012), hiring (Ajunwa et al., 2016; Bogen and Rieke, 2018), insurance (Scism, 2019), or the allocation of public services (Chouldechova et al., 2018; Shroff, 2017). Seeing how the lack of autonomy is perceived as a source of injustice in algorithmic decision-making (Binns et al., 2018; O’Neil, 2016; Crawford and Schultz, 2014), recourse should be considered whenever humans are subject to the predictions of a machine learning model.

The lack of recourse is often mentioned in calls for increased transparency and explainability in algorithmic decision-making (see e.g., Citron and Pasquale, 2014; Wachter et al., 2017; Doshi-Velez et al., 2017). Yet, transparency and explainability do not provide meaningful protection with regards to recourse. In fact, even simple transparent models such as linear classifiers may not provide recourse to all of their decision subjects due to widespread practices in machine learning. These include:

Choice of Features: A model could use features that are immutable (e.g., age $\geq 50$), conditionally immutable (e.g., has_phd, which can only change from ${\footnotesize\texttt{FALSE}}{}\to{\footnotesize\texttt{TRUE}}{}$), or should not be considered actionable (e.g., married).

Out-of-Sample Deployment: The ability of a model to provide recourse may depend on a feature that is missing, immutable, or adversely distributed in the deployment population.

Choice of Operating Point: A probabilistic classifier may provide recourse at a given threshold (e.g., $\hat{y}_{i}=1$ if predicted risk of default $\geq 50\%$) but fail to provide recourse at a more stringent threshold (e.g., $\hat{y}_{i}=1$ if predicted risk of default $\geq 80\%$).

Drastic Changes: A model could provide recourse to all individuals but require some individuals to make drastic changes (e.g., increase income from \50\textrm{K}\to\$1\textrm{M}$).

Considering these failure modes, an ideal attempt to protect recourse should evaluate both the feasibility and difficulty of recourse for individuals in a model’s deployment population (i.e., its target population).

In this paper, we present tools to evaluate recourse for linear classification models, such as logistic regression models, linear SVMs, and linearizable rule-based models (e.g., rule sets, decision lists). Our tools are designed to ensure recourse without interfering in model development. To this end, they aim to answer questions such as:

Will a model provide recourse to all its decision subjects?

How does the difficulty of recourse vary in a population of interest?

What can a person change to obtain a desired prediction from a particular model?

We answer these questions by solving a hard discrete optimization problem. This problem searches over changes that a specific person can make to “flip” the prediction of a fixed linear classifier. It includes discrete constraints so that it will only consider actionable changes — i.e., changes that do not alter immutable features and that do not alter mutable features in an infeasible way (e.g., n_credit_cards from $5\to 0.5$, or has_phd from ${\footnotesize\texttt{TRUE}}{}\to{\footnotesize\texttt{FALSE}}{}$). We develop an efficient routine to solve this optimization problem, by expressing it as an integer program (IP) and handing it to an IP solver (e.g., CPLEX or CBC). We use our routine to create the following tools:

A procedure to evaluate the feasibility and difficulty of recourse for a linear classifier over its target population. Given a classifier and a sample of feature vectors from a target population, our procedure estimates the feasibility and difficulty of recourse in the population by solving the optimization problem for each point that receives an undesirable prediction. This procedure provides a way to check recourse in model development, procurement, or impact assessment (see e.g, Reisman et al., 2018; United States Senate, 2019).

A method to generate a list of actionable changes for a person to obtain a desired outcome from a linear classifier. We refer to this list as a flipset and present an example in Figure 1. In the United States, the Equal Opportunity Credit Act (United States Congress, 2003) requires that any person who is denied credit is sent an adverse action notice explaining “the principal reason for the denial.” It is well-known that adverse action notices may not provide actionable information (see e.g., Taylor, 1980, for a critique). By including a flipset in an adverse action notice, a person would know a set of exact changes to be approved in the future.

Recourse is broadly related to a number of different topics in machine learning. These include: inverse classification, which aims to determine how the inputs to a model can be manipulated to obtain a desired outcome (Aggarwal et al., 2010; Chang et al., 2012); strategic classification, which considers how to build classifiers that are robust to malicious manipulation (Hardt et al., 2016; Dong et al., 2018; Milli et al., 2019a; Hu et al., 2019; Cowgill and Tucker, 2019); adversarial perturbations, which studies the robustness of predictions with respect to small changes in inputs (Fawzi et al., 2018); and anchors, which are subsets of features that fix the prediction of a model (Ribeiro et al., 2018; Hara et al., 2018).

The study of recourse involves determining the existence and difficulty of actions to obtain a desired prediction from a fixed machine learning model. Such actions do not reflect the principle reasons for the prediction (c.f., explainability), and are not designed to reveal the operational process of the model (c.f., transparency). Nevertheless, simple transparent models (e.g., Ustun and Rudin, 2016, 2017; Sokolovska et al., 2018; Malioutov and Varshney, 2013; Angelino et al., 2017) have a benefit in that they allow users to check the feasibility of recourse without extensive training or electronic assistance.

Methods to explain the predictions of a machine learning model (see e.g., Poulin et al., 2006; Lim and Dey, 2009; Biran and McKeown, 2014; Ribeiro et al., 2016) do not produce useful information with regards to recourse. This is because: (i) their explanations do not reveal actionable changes that produce a desired prediction; and (ii) if a method fails to find an actionable change, an actionable change may still exist. For example, consider the method of Wachter et al. (2017) to produce counterfactual explanations from a black-box classifier. This method does not produce useful information about recourse because: (a) it does not constrain changes to be actionable; (b) it assumes that a feasible changes must be observed in the training data (i.e., a feasible action is defined as $\bm{a}\in\{\bm{x}-\bm{x}^{\prime}\},$ where $\bm{x},\bm{x}^{\prime}$ are points in the training data). In practice, this method could output an explanation stating that a person can flip their prediction by changing an immutable attribute, due to (a). In this case, one cannot claim that the model fails to provide recourse, because there may exist a way to flip the prediction that is not observed in the training data, due to (b). Note that (ii) is a key requirement to verify the feasibility of recourse.

In contrast, our tools overcome limitations of methods to generate counterfactual explanations for linear classification problems (e.g., Martens and Provost, 2014; Wachter et al., 2017). In particular, they can be used to: (i) produce counterfactual explanations that obey discrete constraints; (ii) prove that specific kinds of counterfactual explanations do not exist (e.g., actionable explanations); (iii) enumerate all counterfactual explanations for a given prediction; and (iv) choose between competing counterfactual explanations using a custom cost function (c.f., a Euclidean distance metric).

Software and Workshop Paper

This paper extends work that was first presented at FAT/ML 2018 (Spangher and Ustun, 2018). We provide an open-source implementation of our tools at http://github.com/ustunb/actionable-recourse.

Problem Statement

In this section, we define the optimization problem that we solve to evaluate recourse, and present guarantees on the feasibility and cost of recourse. We include proofs for all results in Appendix A.

Given a person who is assigned an undesirable outcome $f(\bm{x})=-1$, we aim to find an action $\bm{a}$ such that $f(\bm{x}+\bm{a})=+1$ by solving an optimization problem of the form,

Solving (LABEL:Eq::RecourseProblem) allows us to make one of the following claims related to recourse:

If (LABEL:Eq::RecourseProblem) is feasible, then its optimal solution $\bm{a}{}^{*}$ is the minimal-cost action to flip the prediction of $\bm{x}$.

If (LABEL:Eq::RecourseProblem) is infeasible, then no action can attain a desired outcome from $\bm{x}$. Thus, we have certified that the model $f$ does not provide actionable recourse for a person with features $\bm{x}$.

Given a linear classifier of the form $f(\bm{x})=\textnormal{sign}(\langle{\bm{w}},{\bm{x}}\rangle)$, we denote the coefficients of actionable and immutable features as $\bm{w}_{A}$ and $\bm{w}_{N}$, respectively. We denote the indices of all features as $J=\{1,\ldots,d\}$, of immutable features as $J_{N}(\bm{x})=\{j\in J~{}|~{}A_{j}(\bm{x})=0\}$, and of actionable features as $J_{A}(\bm{x})=\{j\in J~{}|~{}|A_{j}(\bm{x})|>1\}$. We write $J_{A}$ and $J_{N}$ when the dependence of these sets on $\bm{x}$ is clear from context. We assume that features are bounded so that $\left\|\bm{x}\right\|\leq B$ for all $\bm{x}\in\mathcal{X}$ where $B$ is a sufficiently large constant. We define the following subspaces of the $\mathcal{X}$ based on the values of $y$ and $f(\bm{x})$:

2. Feasibility Guarantees

We start with a simple sufficient condition for a linear classifier to provide a universal recourse guarantee (i.e., to provide recourse to all individuals in any target population).

A linear classifier provides recourse to all individuals if it only uses actionable features and does not predict a single class.

Remark 1 is useful in settings where models must provide recourse. For instance, the result could be used to design screening questions for an algorithmic impact assessment (e.g., “can a person affected by this model alter all of its features, regardless of their current values?”).

The converse of Remark 1 is also true – a classifier denies recourse to all individuals if it uses immutable features exclusively or it predicts a single class consistently. In what follows, we consider models that deny recourse in non-trivial ways. The following remarks apply to linear classifiers with non-zero coefficients $\bm{w}\neq\bm{0}$ that predict both classes in the target population.

If all features are unbounded, then a linear classifier with at least one actionable feature provides recourse to all individuals.

If all features are bounded, then a linear classifier with at least one immutable feature may deny recourse to some individuals.

Remarks 2 and 3 show how the feasibility of recourse depends on the bound of actionable features. To make meaningful claims about the feasibility of recourse, these bounds must be set judiciously. In general, we only need to specify bounds for some kinds of features since many features are bounded by definition (e.g., features that are binary, ordinal, or categorical). As such, the validity of a feasibility claim only depends on the bounds for actionable features, such as income or n_credit_cards. In practice, we would set loose bounds for such features to avoid claiming infeasibility due to overly restrictive bounds. This allows a classifier to provide recourse superficially by demanding drastic changes. However, such cases will be easy to spot in an audit as they will incur large costs (assuming that we use an informative cost function such the one in Section 3.2).

Recourse is not guaranteed when a classifier uses features that are immutable or conditionally immutable (e.g., age or has_phd). As shown in Example 2.1, a classifier with only one immutable feature could achieve perfect predictive accuracy without providing a universal recourse guarantee. In practice, it may be desirable to include such features in a model because they improve predictive performance or provide robustness to manipulation.

Consider training a linear classifier using $n$ examples $(\bm{x}_{i},y_{i})_{i=1}^{n}$ where $\bm{x}_{i}\in\{0,1\}^{d}$ and $y_{i}\in\{-1,+1\}$ where each label is drawn from the distribution

In this case, the Bayes optimal classifier is $f(\bm{x})=\textnormal{sgn}(\sum_{j=1}^{d}x_{j}-\alpha).$ If $\alpha>d-1$, then $f$ will deny recourse to any person with $x_{j}=0$ for an immutable feature $j\in J_{N}.$

3. Cost Guarantees

In Theorem 2.3, we present a bound on the expected cost of recourse.

The expected cost of recourse of a classifier $f:\mathcal{X}\to\{-1,+1\},$ is defined as:

where $\bm{a}^{*}$ is an optimal solution to the optimization problem in (LABEL:Eq::RecourseProblem).

Our guarantee is expressed in terms of cost function with the form $\textnormal{cost}({\bm{a}};{\bm{x}})=c_{\bm{x}}{}\cdot\left\|\bm{a}\right\|,$ where $c_{\bm{x}}\in(0,+\infty)$ is a positive scaling constant for actions from $\bm{x}\in\mathcal{X}$, and $\mathcal{X}$ is a closed convex set.

The expected cost of recourse of a linear classifier over a target population obeys:

$p^{+}=\textnormal{Pr}_{H^{-}}\left(y=+1\right)$ is the false omission rate of $f$;

$p^{-}=\textnormal{Pr}_{H^{-}}\left(y=-1\right)$ is the negative predictive value of $f$;

\gamma^{\max{}}_{A}{}=\max_{\bm{x}\in H^{-}{}}\bigl{|}c_{\bm{x}}\cdot\frac{\bm{w}_{A}^{\top}\bm{x}_{A}}{||\bm{w}_{A}||_{2}^{2}}\bigr{|} is the maximum unit cost of actionable changes for negative predictions;

$R_{A}(f)=p^{+}\cdot\textnormal{Pr}_{H^{-}{}\cap D^{+}}\left(\bm{w}_{A}^{\top}\bm{x}_{A}\leq 0\right)+p^{-}\cdot\textnormal{Pr}_{H^{-}{}\cap D^{-}}\left(\bm{w}_{A}^{\top}\bm{x}_{A}\geq 0\right)$ is the internal risk of actionable features.

Theorem 2.3 implies that one can reduce a worst-case bound on the expected cost of recourse by decreasing the maximum unit cost of actionable changes $\gamma^{\max{}}_{A}$ or the internal risk of actionable features $R_{A}(f)$. Here, $R_{A}(f)$ reflects the calibration between the true outcome and the actionable component of the scores $\bm{w}_{A}^{\top}\bm{x}_{A}$ among individuals where $f(\bm{x})=-1$. When $R_{A}(f)=0$, the actionable component of the scores is perfectly aligned with true outcomes, yielding a tighter bound on the expected cost of recourse.

Integer Programming Tools

In this section, we describe how we solve the optimization problem in (LABEL:Eq::RecourseProblem) using integer programming, and discuss how we use this routine to audit recourse and build flipsets.

We consider a discretized version of the optimization problem in (LABEL:Eq::RecourseProblem), which can be expressed as an integer program (IP) and optimized with a solver (see Mittleman, 2018, for a list). This approach has several benefits: (i) it can directly search over actions for binary, ordinal, and categorical features; (ii) it can optimize non-linear and non-convex cost functions; (iii) it allows users to customize the set of feasible actions; (iv) it can quickly find a globally optimal solution or certify that a classifier does not provide recourse. We express the optimization problem in (LABEL:Eq::RecourseProblem) as an IP of the form:

Here, constraint (2) determines the cost of a feasible action using a set of precomputed cost parameters $c_{jk}=\textnormal{cost}({x_{j}+a_{jk}};{x_{j}})$. Constraint (2) ensures that any feasible action will flip the prediction of a linear classifier with coefficients $\bm{w}$. Constraints (2) and (2) restrict $a_{j}$ to a grid of $m_{j}+1$ feasible values $a_{j}\in\{0,a_{j1},\ldots,a_{jm_{j}}\}$ via the indicator variables $u_{j}=1[a_{j}=0]$ and $v_{jk}=1[a_{j}=a_{jk}]$. Note that the variables and constraints only depend on actions for actionable features $j\in J_{A}$, since $a_{j}=0$ when a feature is immutable.

Modern integer programming solvers can quickly recourse a globally optimal solution to IP (2). In our experiments, for example, CPLEX 12.8 returns a certifiably optimal solution to (2) or proof of infeasibility within $<0.1$ seconds. In practice, we further reduce solution time through the following changes: (i) we drop the $v_{jk}$ indicators for actions $a_{jk}$ that do not agree in sign with $w_{j}$; (ii) we declare $\{v_{j1},\ldots,v_{jm_{j}}\}$ as a special ordered set of type I, which allows the solver to use a more efficient branch-and-bound algorithm (Tomlin, 1988).

Users can easily customize the set of feasible actions by adding logical constraints to the IP. These constraints can be used when, for example, a classifier uses dummy variables to encode a categorical attribute (i.e., a one-hot encoding). Many constraints can be expressed with the $u_{j}$ indicators. For example, we can restrict actions to alter at most one feature within a subset of features $S\subseteq J$ by adding a constraint of the form $\sum_{j\in S}^{d}(1-u_{j})\leq 1$.

Discretization Guarantees

Our IP formulation discretizes the actions for real-valued features so that users can specify a richer class of cost functions. Discretization does not affect the feasibility or the cost of recourse when actions are discretized over a suitably refined grid. We discuss how to build such grids in Appendix B.We can also avoid discretization through an IP formulation that captures the actions of real-valued features using continuous variables. We present this IP formulation in Appendix B.3, but do not discuss it further as it would restrict us to work with linear cost functions.

2. Cost Functions

Our IP formulation can optimize a large class of cost functions, including cost functions that may be non-linear or non-convex over the action space. This is because it encodes all values of the cost function in the $c_{jk}$ parameters in constraint (2). Formally, our approach requires cost functions that are specified by a vector of values in each actionable dimension. However, it does not necessarily require cost functions that are “separable” because we can represent some kinds of non-separable functions using minor changes in the IP formulation (see e.g., the cost function in Equation (3)).

We present off-the-shelf cost functions for our tools in Equations (3) and (4). Both functions measure costs in terms of the percentiles of $x_{j}$ and $x_{j}+a_{j}$ in the target population: $Q_{j}(x_{j}+a_{j})$ and $Q_{j}(x_{j})$ where $Q_{j}(\cdot)$ is the CDF of $x_{j}$ in the target population. Cost functions based on percentile shifts have the following benefits in comparison to a standard Euclidean distance metric: (i) they do not change with the scale of features; (ii) they reflect the distribution of features in the target population. Our functions assign the same cost for a unit percentile change for each feature by default, which assumes that changing each feature is equally difficult. This assumption can be relaxed by, for example, having a domain expert specify the difficulty of changing features relative to a baseline feature.

3. Auditing Recourse

We evaluate the cost and feasibility of recourse of a linear classifier by solving IP (2) for samples drawn from a population of interest. Formally, the auditing procedure requires: (i) the coefficient vector $\bm{w}$ of a linear classifier; (ii) feature vectors sampled from the target population $\{\bm{x}_{i}\}_{i=1}^{n}$ where $f(\bm{x}_{i})=-1$. It solves the IP for each $\bm{x}_{i}$ to produce:

an estimate of the feasibility of recourse (i.e., the proportion of points for which the IP is feasible);

an estimate of the distribution of the cost of recourse (i.e., the distribution of $\textnormal{cost}({\bm{a}^{*}_{i}};{\bm{x}_{i}})$ where ${\bm{a}_{i}}^{*}$ is the minimal-cost action from $\bm{x}_{i}$).

This cost function is well-suited for auditing because it produces an informative measure of the difficulty of recourse. If the optimal cost is 0.25, for example, then any feasible action must change a feature by at least 25 percentiles. In other words, there does not exist an action that flips the prediction by changing a feature by less than 25 percentiles. To run an audit with the cost function in Equation (3), we use a variant of IP (2) where we replace constraint (2) with $|J_{A}|$ constraints of the form: $\textrm{cost}\geq\sum_{k=1}^{m_{j}}c_{jk}v_{jk}.$

The maximum percentile shift is also useful for assessing how the feasibility of recourse changes with the bounds of feasible actions. Say that we wanted to assess how many more people have recourse when we assume that each feature can be altered by at most a 50 percentile shift or at most a 90 percentile shift. Using a generic cost function, we would have to compare feasibility estimates from two audits: one where the action set restricts the changes in each feature to a 50 percentile shift, and another where it restricts the changes to a 90 percentile shift. Using the cost function in Equation (3), we only need to run a single audit using a loosely bounded action set (i.e., an action set where each feature can change by 99 percentiles), and compare the number of individuals where the optimal cost exceeds 0.5 and 0.9.

4. Building Flipsets

We construct flipsets such as the one in Figure 1 using enumeration procedure that solves IP (2) repeatedly.

In Algorithm 1, we present an enumeration procedure to produce a collection of minimal-cost actions that alter distinct subsets of features. The procedure solves IP (2) to recover a minimal-cost action $\bm{a}^{*}$. Next, it adds a constraint to the IP to eliminate actions that alter the same combination of features as $\bm{a}^{*}$. It repeats these two steps until it has recovered $T$ minimal-cost actions or determined that the IP is infeasible (which means that it has enumerated a minimal-cost action for each combination of features that can flip the prediction from $\bm{x}$).

Each action $\bm{a}^{*}\in\mathcal{A}$ returned by Algorithm 1 can be used to create an item in a flipset by listing the current feature values $x_{j}$ along with the desired feature values $x_{j}+{a^{*}_{j}}$ for $j\in S=\{j:a^{*}_{j}\neq 0\}$.

We propose the total log-percentile shift:

This function aims to produce flipsets where items reflect “easy” changes in the target population. In particular, it ensures that cost of $a_{j}$ increases exponentially as $Q_{j}(x_{j})\to 1$. This aims to capture the notion that changes become harder when starting off from a higher percentile value (e.g., changing income from percentiles $90\to 95$ is harder than $50\to 55$).

Demonstrations

In this section, we present experiments where we use our tools to study recourse in credit scoring problems. We have two goals: (i) to show how recourse may affected by common practices in the development and deployment of machine learning models; and (ii) to demonstrate how our tools can protect recourse in such events by informing stakeholders such as practitioners, policy-makers and decision-subjects.

In the following experiments, we train classifiers using scikit-learn, and use standard 10-fold cross-validation (10-CV) to tune free parameters and estimate out-of-sample performance. We solve all IPs using the CPLEX 12.8 (ILOG, 2018) on a 2.6 GHz CPU with 16 GB RAM. We include further information on the features, action sets, and classifiers for each dataset in Appendix C. We provide scripts to reproduce our analyses at http://github.com/ustunb/actionable-recourse.

We consider a processed version of credit dataset (Yeh and Lien, 2009). Here, $y_{i}=-1$ if person $i$ will default on an upcoming credit card payment. The dataset contains $n=30\,000$ individuals and $d=16$ features derived from their spending and payment patterns, education, credit history, age, and marital status. We assume that individuals can only change their spending and payment patterns and education.

Results

We present the results of our audit in Figure 2, and present a flipset for a person who is denied credit by the most accurate classifier in Figure 3.

Our tools can identify mechanisms that affect recourse by running audits with different action sets. For example, one can evaluate how the mutability of feature $j$ affects recourse by running audits for: (i) an action set where feature $j$ is immutable ($A_{j}(\bm{x})={0}$ for all $\bm{x}\in\mathcal{X}$); and (ii) an action set where feature $j$ is actionable ($A_{j}(\bm{x})=\mathcal{X}_{j}$ for all $\bm{x}\in\mathcal{X}$). Here, such an analysis reveals that the lack of recourse stems from an immutable feature related to credit history (i.e., an indicator set to 1 if a person has ever defaulted on a loan). Given this information, a practitioner could replace this feature with a mutable variant (i.e., an indicator set to 1 if a person has recently defaulted on a loan), and thus deploy a model that provides recourse. Such changes are sometimes mandated by industry-specific regulations (see e.g., policies on “forgetfulness” in Blanchette and Johnson, 2002; Edwards and Veale, 2017). Our tools can support these efforts by showing how regulations would affect recourse in deployment.

2. Out-of-Sample Deployment

We now discuss an experiment where a classifier is deployed in a setting with dataset shift. Our setup is inspired by a real-world feedback loop with credit scoring in the United States: young adults often lack the credit history to qualify for loans, so they are undersampled in datasets that are used to train a credit score. It is well-known that this kind of systematic undersampling can affect the accuracy of credit scores for young adults (see e.g., Wilhelm, 2018; Kallus and Zhou, 2018). Here, we show that it can also affect the cost and feasibility of recourse.

We consider a processed version of the givemecredit dataset (Kaggle, 2011). Here, $y_{i}=-1$ if person $i$ will experience financial distress in the next two years. The data contains $n=150\,000$ individuals and $d=10$ features related to their age, dependents, and financial history. We assume that all features are actionable except for Age and NumberOfDependents.

Baseline Classifier. This is a baseline model that we train for the sake of comparison. It is trained using all $n=112\,500$ examples, which represents the target population.

Biased Classifier. This is the model that we would deploy. It is trained using $n=98\,120$ examples (i.e., the $112\,500$ examples used to train the baseline classifier minus the $14\,380$ examples with ${\textit{Age}}<35$).

We compute the cost of recourse using percentile distributions computed from a hold-out set of $n=37\,500$ examples. We adjust the threshold of each classifier so that only $10\%$ of examples receive the desired outcome.

Results

We present the results of our audit in Figure 4 and show flipsets for a prototypical young adult in Figure 5. As shown, the median cost of recourse among young adults under the biased model is 0.66, which means that the median person can only flip their predictions by a 66 percentile shift in any feature. In comparison, the median cost of recourse among young adults under the baseline model is 0.14. These differences in the cost of recourse are less pronounced for other age brackets.

Our results illustrate how out-of-sample deployment can significantly affect the cost of recourse. In practice, such effects can be measured with an audit using data from a target population. Such a procedure may be useful in model procurement, as classifiers are often deployed on populations that differ from the population that produced the training data.

There are several ways in which out-of-sample deployment can affect recourse. For example, a probabilistic classifier may exhibit a higher cost of recourse if the threshold is fixed, or if the target population has a different set of feasible actions. We controlled for these issues by adjusting thresholds to approve the same proportion of applicants, and by fixing the action set and cost function to audit both classifiers. As a result, the observed effects of out-of-sample deployment only depend on distributional differences in age.

3. Disparities in Recourse

Our last experiment aims to illustrate how our tools could be used to evaluate disparities in recourse across protected groups. We evaluate the disparity in recourse of a classifier between males and females while controlling for basic confounding. Here, a disparity in recourse occurs if, given comparable individuals who are denied a loan in the target population, individuals in one group are able to obtain a desired outcome by making easier changes than individuals in another group.

Results

As shown in Figure 6, the cost of recourse can differ between males and females even when models ignore gender. These disparities can also be examined by comparing flipsets as in Figure 7, which shows minimal-cost actions for comparable individuals from each protected group.

Concluding Remarks

We are currently extending our tools to evaluate recourse for non-linear classifiers. One could apply our tools to this setting by replacing the linear classifier with a local linear model that approximates the decision boundary around $\bm{x}$ in actionable space (e.g., similar to the approach used by LIME, Ribeiro et al., 2016). This approach may find actionable changes. However, it would not provide the proof of infeasibility that is required to claim that a model does not provide recourse.

Pricing Incentives

Our tools could be used to price incentives induced by a model by running audits with different action sets (see e.g., Kleinberg and Raghavan, 2018). Consider a credit score that includes features that are causally related to creditworthiness (e.g., income) and “ancillary” features that are prone to manipulation (e.g., social media presence). In this case, one could price incentives in a target population by comparing the cost of recourse for actions that alter (i) only causal features, and (ii) causal features and at least one ancillary feature.

Measuring Flexibility

Our tools can enumerate the complete set of minimal-cost actions for a person by using the procedure in Algorithm 1 to list actions until the IP become infeasible. This would produce a collection of actions, where each action reflects a way to obtain the outcome by altering a different subset of features. The size of this collection would reflect the flexibility of recourse, and may be used to evaluate other aspects of recourse. For example, if a classifier provides a person with 16 ways to flip their prediction, 15 of which are legally contestable, then the model itself may be contestable.

2. Limitations

The flipsets in this paper are “abridged” in that they do not reveal all features of the model. In practice, a person who is shown a flipset in this format may fail to flip their prediction after making the recommended changes if they unknowingly alter actionable features that are not shown. This issue can be avoided by including additional information along the flipset – for example, a list of undisclosed actionable features that must not change, or a list of features that must change in a certain way. Alternatively, one could also build an abridged flipset with “robust” actions (i.e., actions that flip the prediction and provide an additional “buffer” to protect against the possibility that a person alters other undisclosed features in an adversarial manner).

Model Theft

Model owners may not be willing to provide consumers with flipsets due to the potential for model theft (see e.g., efforts to reverse-engineer the Schufa credit score in Germany by crowdsourcing (Deutschland, 2018)). One way to address such concerns would be to produce a lower bound on the number of actions needed to reconstruct a proprietary model (Tramèr et al., 2016; Milli et al., 2019b). Such bounds may be useful for quantifying the risk of model theft, and to inform the design of safeguards to reduce this risk.

3. Discussion

Individual rights with regards to algorithmic decision-making are often motivated by the need for human agency over machine-made decisions. Recourse reflects a precise notion of human agency – i.e., the ability of a person to alter the predictions of a model. We argue that models should provide recourse in applications subject to equal opportunity laws (e.g., lending or hiring) and in applications where individuals should have agency over decisions (e.g., the allocation of social services).

Recourse provides a useful concept to articulate notions of procedural fairness in applications without a universal “right to recourse.” In recidivism prediction, for example, models should provide defendants who are predicted to recidivate with the ability to flip their prediction by altering specific sets of features. For example, a model that includes age and criminal history should allow defendants who are predicted to recidivate to flip their predictions by “clearing their criminal history.” Otherwise, some defendants would be predicted to recidivate solely on the basis of age.

In settings where recourse is desirable, our tools can check that a model provides recourse through two approaches: (1) by running periodic recourse audits; and (2) by generating a flipset for every person who is assigned an undesirable prediction. The second approach has a benefit in that it can detect recourse violations while a model is deployed. That is, we would know that a model did not provide recourse to all its decision subjects on the first instance that we would produce an empty flipset.

Should We Inform Consumers of Recourse?

In settings where there is an imperative for recourse, providing consumers with flipsets may lead to harm. Consider a case where a consumer is denied a loan by a model so that $\hat{y}=-1$, and we know that they are likely to default so that $y=-1$. In this case, providing them with an action that allows them to flip their prediction from $\hat{y}=-1$ to $\hat{y}=+1$ could inflict harm if the action did not also improve their ability to repay the loan from $y=-1$ to $y=+1.$ Conversely, say that we presented the consumer with an action that allowed them to receive a loan and also improved their ability to pay it back. In this case, disclosing the action would benefit both parties: the consumer would receive a loan that they could repay, and the model owner would have improved the creditworthiness of their consumer.

This example shows how flipsets could benefit all parties if we can find actions that simultaneously alter their predicted outcome $\hat{y}$ and true outcome $y$. Such actions are naturally produced by causal models. They could also be obtained for predictive models. For example, we could enumerate all actions that flip the predicted outcome $\hat{y}$, then build a filtered flipset using actions that are likely to flip a true outcome $y$ (e.g., using a technique to estimate treatment effects from observational data).

In practice, the potential drawbacks of gaming have not stopped the development of laws and tools to empower consumers with actionable information. In the United States, for example, the adverse action requirement of the Equal Credit Opportunity Act is designed – in part – to educate consumers on how to obtain credit (see e.g., Taylor, 1980, for a discussion). In addition, credit bureaus provide credit score simulators that allow consumers to find actions that will change their credit score in a desired way.See, for example, https://www.transunion.com/product/credit-score-simulator.

Policy Implications

While regulations for algorithmic decision-making are still in their infancy, existing efforts have sought to ensure human agency indirectly, through laws that focus on transparency and explanation (see e.g., regulations for credit scoring in the United States such as United States Congress, 2003). In light of these efforts, we argue that recourse should be treated as a standalone policy goal when it is desirable. This is because recourse is a precise concept with several options for meaningful consumer protection. For example, one could mandate that a classifier must be paired with a recourse audit for its target population, or mandate that consumers who are assigned an undesirable outcome are shown a list of actions to obtain a desired outcome.

References

Appendix A Omitted Proofs

Given a classifier $f:\mathcal{X}\to\{-1,+1\}$, let us define the space of feature vectors that are assigned a negative and positive label as $H^{-}=\{\bm{x}\in\mathcal{X}~{}|~{}f(\bm{x})=-1\}$ and $H^{+}=\{\bm{x}\in\mathcal{X}~{}|~{}f(\bm{x})=+1\}$, respectively. Since the classifier $f$ does not trivially predict a single class over the target population, there must exist at least one feature vector $\bm{x}\in H^{-}$ and at least one feature vector $\bm{x}^{\prime}\in H^{+}$.

Given any feature vector $\bm{x}\in H^{-}$, choose a fixed point $\bm{x}^{\prime}\in H^{+}$. Since all features are actionable, the set of feasible actions from $\bm{x}$ must contain an action vector $\bm{a}=\bm{x}^{\prime}-\bm{x}.$ Thus, the classifier provides $\bm{x}$ with recourse as $f(\bm{x}+\bm{a})=f(\bm{x}+\bm{x}^{\prime}-\bm{x})=f(\bm{x}^{\prime})=+1$. Since our choice of $\bm{x}$ was arbitrary, the previous result holds for all feature vectors $\bm{x}\in H^{-}$. Thus, the classifier provides recourse to all individuals in the target population. ∎

Remark 2

Remark 3

Suppose we have $d$ actionable features $x_{j}\in\{0,1\}$ for $j\in\{1,\ldots,d\}$ and 1 immutable feature $x_{d+1}\in\{0,1\}$. Consider a linear classifier with the score function $\sum_{j=1}^{d}x_{j}+\alpha x_{j+1}\geq d$ where $\alpha<-1$. For any $\bm{x}$ with $x_{d+1}=1$, we have that $\sum_{j=1}^{d}x_{j}+\alpha x_{j+1}<\sum_{j=1}^{d}x_{j}-1\leq d-1$. Thus, $\bm{x}$ will not have recourse. ∎

Theorem 2.3

In what follows, we denote the unit score of actionable features from $\bm{x}$ as ${u_{\bm{x}}}{}=\frac{\bm{w}_{A}^{\top}\bm{x}_{A}}{||\bm{w}_{A}||_{2}^{2}}$. Our proof uses the following lemma from Fawzi et al. (2018), which we have reproduced below for completeness:

Given a non-trivial linear classifier where $\bm{w}_{A}\neq 0$, the optimal cost of recourse from $\bm{x}\in H^{-}$ obeys

Using the definition of $\overline{\textnormal{cost}}_{H^{-}{}}({f})$, we can express:

Using Lemma A.1, we can write the expectation term in line (5) as:

Applying Lemma A.1 to the expectation terms in lines (6) to (8), we can write $\overline{\textnormal{cost}}_{H^{-}{}}({f})$ as follows:

We observe that the quantity in line (9) can be bounded as follows:

Here, the inequality follows from the definition of $\gamma^{\max}_{A}$.

We observe that the quantity in line (7) can also be bounded in a similar manner:

Combining these inequalities with Equation (10), we obtain:

Appendix B Discretization Guarantees

In Section 3, we state that discretization will not affect the feasibility or cost of recourse if we choose a suitable grid. In what follows, we present formal guarantees for this claim. Specifically, we show that:

Discretization does not affect the feasibility of recourse if the actions for real-valued features are discretized onto a grid with the same upper and lower bounds.

The maximum discretization error in the cost of recourse can be bounded and controlled by refining the grid.

When the set of actions for each feature belong to a bounded interval $A_{j}(\bm{x})=[a_{j}^{\textnormal{min}},a_{j}^{\textnormal{max}}]$, we have that:

Observe that IP (2) is infeasible whenever $\max_{\bm{a}\in A^{\textrm{disc}}(\bm{x})}f(\bm{x}+\bm{a})<0,$ because this would violate constraint (2). Since

it follows that the IP is infeasible whenever the person has no recourse under the original action set. ∎

B.2. Cost Guarantee

We present a bound on the maximum error in the cost of recourse due to the discretization of the cost function $\textnormal{cost}({\bm{a}};{\bm{x}})=c_{\bm{x}}{}\cdot\left\|\bm{a}\right\|$, where $c:\mathcal{X}\to(0,+\infty)$ is a strictly positive scaling function for actions from $\bm{x}$. Given a feature vector $\bm{x}\in\mathcal{X}$, we denote the discretized action set from $\bm{x}$ as $A(\bm{x})$ and the continuous action set as $B(\bm{x})$. We denote the minimal-cost action over $A(\bm{x})$ as:

and the minimal-cost action over $B(\bm{x})$ as:

Here $\delta_{j}=\max_{k=0,..,m_{j}-1}|a_{j,{k+1}}-a_{j,k}|.$ In Proposition B.2, we show that the difference in the cost of recourse due to discretization can be bounded in terms of the maximum discretization gap.

Given a linear classifier with coefficients $\bm{w}$, consider evaluating the cost of recourse for an individual with features $\bm{x}\in\mathcal{X}.$ If the features belong to a bounded space $\bm{x}\in\mathcal{X}$, then the cost can be bounded as:

Let $N(\bm{b}^{*})$ be a neighborhood of real-valued vectors centered at $\bm{x}+\bm{b}^{*}$ and with radius $\sum_{j=1}^{d}\delta_{j}$:

Observe that $N(\bm{b}^{*})$ must contain an action $\hat{\bm{a}}\in A(\bm{x})$ such that $f(\bm{x}+\hat{\bm{a}})=+1$. By the triangle inequality, we can see that:

Here the inequality in (13) follows from the fact that $\bm{x}+\hat{\bm{a}}\in N(\bm{b}^{*})$. Since $\bm{a}^{*}$ is optimal, we have that $\left\|\bm{a}^{*}\right\|\leq\left\|\hat{\bm{a}}\right\|$. Thus we have,

B.3. IP Formulation without Discretization

In what follows, we present an IP formulation that does not require discretizing real-valued features, which we mention in Section 3. Given a linear classifier with coefficients $\bm{w}=[w_{0},\ldots,w_{d}]$ and a person with features $\bm{x}=[1,x_{1},\ldots,x_{d}]$, we can recover the solution to the optimization problem in (LABEL:Eq::RecourseProblem) for a linear cost function with the form $\textnormal{cost}({\bm{a}};{\bm{x}})=\sum_{j}c_{j}a_{j},$ by solving the IP:

a_j ∈[a_j^min, a_j^max] j ∈J_cts a_j = ∑_k=1^m_j a_jk v_jk j ∈J_disc 1 = u_j + ∑_k=1^m_j v_jk j ∈J_disc a_j ∈R j ∈J_disc u_j ∈{0,1} j ∈J_disc v_jk ∈{0,1} k=1,…,m_j j ∈J_disc Here, we denote the indices of actionable features as $J_{A}=J_{\textnormal{cts}}\cup J_{\textnormal{disc}}$, where $J_{\textnormal{cts}}$ and $J_{\textnormal{disc}}$ correspond to the indices of real-valued features and discrete-valued features, respectively. This formulation differs from the discretized formulation in Section 3 in that: (i) it represents actions for real-valued features via continuous variables $a_{j}\in[a_{j}^{\textnormal{min}},a_{j}^{\textnormal{max}}]$ in (B.3); (ii) it only includes indicator variables $u_{j}$ and $v_{jk}$ and constraints (B.3) for discrete-valued variables $j\in J_{\textnormal{disc}}$;

The formulation in (14) has the following drawbacks:

It forces users to use linear cost functions. This significantly restricts the ability of users to specify useful cost functions. Examples include cost functions based on percentile shifts, such as those in (3) and (4), which are non-convex.

It is harder to optimize when we introduce constraints on feasible actions. If we wish to limit the number of features that can be altered in IP (14), for example, we must add indicator variables of the form $u_{j}=1[a_{j}\neq 0]$ for real-valued features $j\in J_{\textnormal{cts}}$. These variables must be set via “Big-M” constraints, which produce weak LP relaxations and numerical instability (see e.g., Belotti et al., 2016, for a discussion).

Appendix C Supporting Material for Section 4

C.2. Supporting Material for Section 4.2

C.3. Supporting Material for Section 4.3