Learning Models for Actionable Recourse

Background: adversarial training. Consider a classifier $f_{\theta}:\mathcal{X}\to\mathcal{Y}$ and perturbations $\Delta\subseteq\mathbb{R}^{n_{X}}$. Given $x\in\mathcal{X}$, an adversarial example (Szegedy et al., 2014) for $x$ is a perturbation $\delta\in\Delta$ such that $f_{\theta}(x+\delta)\neq f_{\theta}(x)$—i.e., the perturbation $\delta$ (restricted to be small) changes the predicted label of $x$.

Adversarial examples are undesirable because they indicate that $f_{\theta}$ is not robust to small changes to the input that should not affect the class label (e.g., according to human predictions). Thus, there has been a great deal of interest in designing algorithms for improving robustness to adversarial examples. The basic approach is adversarial training (Goodfellow et al., 2015b), which dynamically computes adversarial examples for inputs in the training set and adds these to the objective as additional training examples, as in data augmentation. In particular, given a loss function $\ell:\mathbb{R}\times\mathcal{Y}\to\mathbb{R}$, where $\ell(g_{\theta}(x),y)$ is the loss for training example $(x,y)$, they seek to compute

$\displaystyle\theta^{*}$

$\displaystyle=\operatorname*{\arg\min}_{\theta\in\Theta}\ell_{A}(\theta)\quad\text{where}\quad\ell_{A}(\theta)=\mathbb{E}_{p(x,y)}\left[\ell(g_{\theta}(x),y)+\lambda\cdot\max_{\delta\in\Delta}\ell(g_{\theta}(x+\delta),y)\right].$

In $\ell_{A}(\theta)$, the first term is the supervised learning loss, the second is the adversarially robust loss (i.e., encourage $g_{\theta}$ to be robust to adversarial examples $x+\delta$), and $\lambda\in\mathbb{R}_{\geq 0}$ is a hyperparameter.

The challenge in optimizing $\ell_{A}(\theta)$ is computing the maximum over $\delta\in\Delta$. To address this challenge, existing adversarial training algorithms leverage approximations enabling efficient computation of $\delta$.

Our approach. We use adversarial training to learn a model $f_{\theta}$ for which inputs $x\in\mathcal{X}$ have recourse at higher rates compared to models trained using conventional approaches. There are two key differences compared to adversarial training. First, we want recourse to exist, which corresponds to encouraging the existence of adversarial examples. Second, we only care about changing negative labels $f_{\theta}(x)=0$ to positive ones $f_{\theta}(x+\delta)=1$, not vice versa. Thus, we want to solve

$\displaystyle\theta^{*}$

$\displaystyle=\operatorname*{\arg\min}_{\theta\in\Theta}\ell_{R}(\theta)\quad\text{where}\quad\ell_{R}(\theta)=\mathbb{E}_{p(x,y)}\left[\ell(g_{\theta}(x),y)+\lambda\cdot\min_{\delta\in\Delta}\ell(g_{\theta}(x+\delta),1)\right].$

(1)

Compared to $\ell_{A}$, $\ell_{R}$ has a different second term in two ways: (i) the maximum over $\delta$ with a minimum, and (ii) the label $y$ is replaced with the label $1$. We note that when $\lambda=0$, Eq. 1 is supervised learning.

We optimize Eq. 1 using adversarial training  (Goodfellow et al., 2015a; Shaham et al., 2018; Lakkaraju et al., 2020a), which performs stochastic gradient descent on $\ell_{R}(\theta)$. The key challenge to computing $\nabla_{\theta}\ell_{R}(\theta)$ is computing the gradient of the second term, which can be rewritten as follows:

$\displaystyle\nabla_{\theta}\min_{\delta\in\Delta}\ell(g_{\theta}(x+\delta),1)=\nabla_{\theta}\ell(g_{\theta}(x+\delta^{*}),1),$

where $\delta^{*}$ is the perturbation that maximizes the likelihood of positive outcome, or minimizes the loss between predicted and positive outcomes—i.e.,

$\displaystyle\delta^{*}=\operatorname*{\arg\min}_{\delta\in\Delta}\ell(g_{\theta}(x+\delta),1).$

(2)

Computing $\delta^{*}$ is computationally challenging; thus, we use a Taylor approximation of the loss $\ell(g_{\theta}(x+\delta),1)\approx\ell(g_{\theta}(x),1)+\nabla_{x}\ell(g_{\theta}(x),1)^{\top}\delta$. Using this approximation, Eq. 2 becomes

$\displaystyle\delta^{*}$

$\displaystyle=\operatorname*{\arg\min}_{\delta\in\Delta}\ell(g_{\theta}(x+\delta),1)\approx\operatorname*{\arg\min}_{\delta\in\Delta}\nabla_{x}\ell(g_{\theta}(x),1)^{\top}\delta,$

where we have dropped the term $\ell(g_{\theta}(x),1)$ since it is constant with respect to $\delta$. Finally, note that the optimization problem on the last step is a linear program (LP), since we have assumed that $\delta\in\Delta$ can be expressed as a set of affine constraints and since the objective is linear in $\delta$. In summary, we optimize Eq. 1 using stochastic gradient descent, where at each step we solve an LP to approximate the second term—i.e., given parameters $\theta_{i}$ and example $(x_{i},y_{i})$ on gradient step $i$, and step size $\eta_{i}\in\mathbb{R}_{>0}$ on step $i$, we use the stochastic gradient update

$\displaystyle\theta_{i+1}$

$\displaystyle=\theta_{i}+\eta_{i}\left(\nabla_{\theta}\ell(g_{\theta}(x),y)+\lambda\cdot\nabla_{\theta}\ell(g_{\theta}(x+\delta^{*}_{i},1)\right)~{}~{}~{}\text{where}~{}~{}~{}\delta^{*}_{i}=\operatorname*{\arg\min}_{\delta\in\Delta}\nabla_{x}\ell(g_{\theta}(x),1)^{\top}\delta.$

So far, we have focused on how to train a model $f_{\theta}$ that provides recourse. Once we have trained $f_{\theta}$, we still need a way to compute recourse for a given individual $x$—i.e., an algorithm $\mathcal{A}:\mathcal{X}\to\Delta$ for computing $\delta_{x}=\mathcal{A}(x)$ such that $f(x+\delta_{x})=1$. We describe three such algorithms; in general, any algorithm designed to output recourses can be used (Karimi et al., 2020a; Poyiadzi et al., 2020).

Gradient descent. The approach proposed in Wachter et al. (2017) can directly be applied to compute recourse. They solve the problem

$\displaystyle\delta_{x}=\operatorname*{\arg\min}_{\delta\in\Delta}\{\ell(g_{\theta}(x+\delta,1)+\lambda^{\prime}\cdot\|\delta\|_{2}\},$

where $\lambda^{\prime}\in\mathbb{R}_{\geq 0}$ is a hyperparameter, using gradient descent on $\delta$. The term $\|\delta\|_{2}$ is designed to encourage the recourse $\delta$ to be small, which is often desirable in practice (we have excluded it from our formulation for simplicity). While this approach is generally effective, it can be very slow since we need to solve an optimization problem for each individual.

Adversarial training. We can also use adversarial training to compute recourse—i.e.,

$\displaystyle\delta_{x}=\operatorname*{\arg\min}_{\delta\in\Delta}\nabla_{x}\ell(g_{\theta}(x),1)^{\top}\delta.$

This approach approximates the gradient descent approach, but can be computed much more efficiently. Furthermore, since our objective in Eq. 1 is designed to encourage this specific perturbation to provide recourse, it performs nearly as well as gradient descent when $f_{\theta}$ is trained with $\lambda>0$.

Linear approximation. Finally, Ustun et al. (2019) propose an approach to compute recourse when $f_{\theta}(x)=\mathbbm{1}(\beta^{\top}x\geq\beta_{0})$ is a linear model. In this case, they compute $\delta_{x}$ using an integer linear program (ILP). For nonlinear models, we can instead use the linear approximation of $g_{\theta}$ near $x$. Letting $\delta_{x}=\mathcal{A}(x;\beta_{0},\beta)$ be the recourse generated by their algorithm, and using the Taylor expansion $g_{\theta}(x^{\prime})\approx g_{\theta}(x)+\nabla_{x}g_{\theta}(x)^{\top}(x^{\prime}-x)$, we can use their approach to compute the recourse

$\displaystyle\delta_{x}=\mathcal{A}(x;\theta_{0}-g_{\theta}(x),\nabla_{x}g_{\theta}(x)).$

However, this approach only works well when $g_{\theta}$ is approximately linear as a function of $x$; otherwise, the Taylor approximation may be poor and $\delta_{x}$ may not satisfy the desired condition $f_{\theta}(x+\delta_{x})=1$.

Finally, we describe how we choose $\theta_{0}$ to ensure $f_{\theta}$ provides recourse with high probability. Note that $\theta_{0}$ also controls the fraction of individuals given a positive outcome without the need for recourse; thus, we choose $\theta_{0}$ to optimize the performance of $f_{\theta}$ subject to a constraint that $f_{\theta}$ is PARE.

Background: PAC confidence sets. We build on work constructing PAC confidence sets (Park et al., 2020). Given $x\in\mathcal{X}$, they construct a model $\tilde{h}_{\theta,\tau}:\mathcal{X}\to\mathcal{P}(\mathcal{Y})$ (where $\mathcal{P}$ is the power set) that returns the set of all labels $y$ with score above threshold $\tau\in\mathbb{R}$—i.e.,

$\displaystyle\tilde{h}_{\theta,\tau}(x)$

$\displaystyle=\{y\in\mathcal{Y}\mid h_{\theta}(x,y)\geq\tau\}\quad\text{where}\quad h_{\theta}(x,y)=\begin{cases}g_{\theta}(x)&\text{if }y=1\\ 1-g_{\theta}(x)&\text{if }y=0.\end{cases}$

Given $\epsilon\in\mathbb{R}_{>0}$, we say $\tau$ is approximately correct if

$\displaystyle\mathbb{P}_{p(x,y)}[y\in\tilde{h}_{\theta,\tau}(x)]\geq 1-\epsilon,$

i.e., $\tilde{h}_{\theta,\tau}(x)$ contains the true label for $x$ with high probability over $p(x,y)$. Note that $\tau=0$ satisfies this condition, since $\tilde{h}_{\theta,0}(x)=\{0,1\}$ for all $x$. The goal is to choose $\tau$ as large as possible while ensuring approximate correctness.

Park et al. (2020) proposes an estimator $\hat{\tau}$ that takes as input (i) the pretrained model $g_{\theta}:\mathcal{X}\to[0,1]$, (ii) a calibration dataset $Z\subseteq\mathcal{X}\times\mathcal{Y}$ of i.i.d. samples $(x,y)\sim p$, and (iii) confidence levels $\epsilon,\alpha\in\mathbb{R}_{>0}$, and constructs a threshold $\hat{\tau}(Z)\in[0,1]$ that is probably approximately correct (PAC):

$\displaystyle\mathbb{P}_{p(Z)}[\hat{\tau}(Z)\text{ is approximately correct}]\geq 1-\alpha.$

(3)

In other words, $\hat{\tau}(Z)$ is approximately correct with probability at least $1-\alpha$ according to $p(Z)$. Their approach leverages the fact that $\hat{\tau}(Z)$ is an estimator for a single parameter; thus, they can use learning theory to obtain PAC guarantees (Kearns et al., 1994).

PARE models via PAC confidence sets. Given a model $g_{\theta}:\mathcal{X}\to\mathbb{R}$, an algorithm $\mathcal{A}:\mathcal{X}\to\Delta$ for computing recourse, and a calibration set $Z\subseteq\mathcal{X}\times\mathcal{Y}$, our algorithm leverages PAC confidence sets to choose a threshold $\theta_{0}=\hat{\theta}_{0}(Z)$ that ensures the resulting model $f_{\hat{\theta}}$ satisfies the PARE constraint.

First, our algorithm uses the PAC confidence set algorithm to construct the new calibration dataset

$\displaystyle Z^{\prime}=\{(x+\mathcal{A}(x),1)\mid(x,y)\in Z\}.$

Intuitively, $Z^{\prime}$ says that the “correct” label for every input $x+\mathcal{A}$ should be $1$—i.e., the recourse constructed by $\mathcal{A}$ should satisfy $f_{\theta}(x+\mathcal{A}(x))=1$.

Then, our algorithm constructs $\tilde{h}_{\theta,\hat{\tau}(Z)}$ using $g_{\theta}$, $Z^{\prime}$, and the given $\epsilon,\alpha$. The PAC guarantee in Eq. 3 says that with probability at least $1-\alpha$ over $p(Z)$, we have

$\displaystyle\mathbb{P}_{p(Z)}\left[\mathbb{P}_{p(x,y)}[y^{\prime}\in\tilde{h}_{\theta,\hat{\tau}(Z^{\prime})}(x^{\prime})]\geq 1-\epsilon\right]\geq 1-\alpha,$

(4)

where $(x^{\prime},y^{\prime})\in Z^{\prime}$ is the example constructed from $(x,y)\in Z$ as described above. Note that the outer probability is over $p(Z)$ since $Z^{\prime}$ is a deterministic function of the random variable $Z$. Plugging in the definitions $x^{\prime}=x+\mathcal{A}(x)$ and $y^{\prime}=1$, Eq. 4 becomes

$\displaystyle\mathbb{P}_{p(Z)}\left[\mathbb{P}_{p(x,y)}[1\in\tilde{h}_{\theta,\hat{\tau}(Z^{\prime})}(x+\mathcal{A}(x))]\geq 1-\epsilon\right]\geq 1-\alpha,$

and plugging in the definition of $\tilde{h}_{\theta,\tau}$, it becomes

$\displaystyle\mathbb{P}_{p(Z)}\left[\mathbb{P}_{p(x,y)}[g_{\theta}(x+\mathcal{A}(x))\geq\hat{\tau}(Z^{\prime})]\geq 1-\epsilon\right]\geq 1-\alpha.$

(5)

Then, our algorithm returns $\hat{\theta}_{0}(Z)=\hat{\tau}(Z^{\prime})$ (with given parameters $\theta$ as the remaining parameters). Since Eq. 5 is equivalent to the PARE condition, we have:

Datasets. We use four real-world datasets. The first contains adult income information from the 1994 United States Census Bureau (Dua and Graff, 2017). It includes information about adults’ demographics, education, and occupations. Each adult is labeled as making below or $>$ $50K a year, which can be thought of as a proxy for whether an individual will be able to repay a loan or not. The second contains information collected by Propublica about criminal defendants’ compas recidivism scores (Angwin et al., 2016). This dataset includes information about defendants’ demographics and crimes, and each defendant is labeled as having either a high or low likelihood of reoffending, as measured by the compas assessment tool. The third dataset represents bail outcomes from two different U.S. state courts from 1990-2009 (Schmidt and Witte, 1988). It includes information about individuals’ criminal histories and demographics. Each defendant is labeled as having a high or low risk of recidivism. The fourth dataset is the german credit dataset (Dua and Graff, 2017), which contains individuals’ demographic, personal, and financial information. Each applicant is labeled as either having high or low credit risk.

We standardize all continuous features to have mean $0$ and variance $1$. We randomly split each dataset into $80\%$ train and $20\%$ validation sets. We use 3 random data splits and report the mean across splits for the rest of this section, unless otherwise specified. For compas and adult, we hold out $500$ examples from the validation set to form a test set; for german, we hold out $100$ examples. For bail, we evaluate on a 500-instance subset of the test set. All results are reported on the test set.³³3Our processed datasets have sizes: adult $\approx 32.5K$, compas $\approx 6K$, bail $\approx 8K$, german $\approx 1K$.

Models. All models are neural networks with 3 100-node hidden layers, dropout probability $0.3$, and tanh activations. For evaluation, we choose the epoch achieving the highest validation $F_{1}$ score.

Parameters. We experimented with $\lambda$ values between $0.0$ to $2.0$ in increments of $0.2$ and found that $\lambda=0.8$ provided the best tradeoff between $F_{1}$ score and recourse rate across all datasets; we evaluate how our results vary with $\lambda$ below. For $\Delta$, we choose the set of actionable features (i.e., features that can be changed as part of the recourse) based on the dataset (two features for adult, bail, german; one for compas); we set $\delta_{\text{max}}=0.75$ after standardizing features. (See Appendix B.2 for experiments investigating the effect of varying values of $\delta_{max}$). We also include domain-specific linear constraints in $\Delta$—e.g., for the adult dataset, recourse can only require that hours worked increases. See Appendix A.3 for more details about our choices of $\Delta$.

We choose the decision threshold $\theta_{0}$ to maximize F1 score rather than to obtain PAC guarantees, since our goal is to understand the tradeoffs between model performance and recourse rates with a fixed underlying predictive model $f_{\theta}$. We evaluate the effects of rigorously choosing $\theta_{0}$ in Section 4.2.

Baselines. To the best of our knowledge, our approach is the first to train models with the objective of providing recourse at a higher rate. Thus, we compare to a baseline that omits our recourse loss—i.e., $\lambda=0.0$. For our approach and this baseline, we evaluate the performance of each of the three different algorithms for computing recourse described in Section 3.2. We use the alibi implementation (Klaise et al., 2019) of the gradient descent algorithm for computing recourse (Wachter et al., 2017) and set the initial value of the hyperparameter $\lambda^{\prime}=0.001$. We use LIME (Ribeiro et al., 2016a) as our linear approximation method with the approach proposed by Ustun et al. (2019).

Metrics. We evaluate our approach and the baselines with the following metrics: (i) standard performance metrics of accuracy and $F_{1}$ score, (ii) “recourse neg,” the proportion of instances $x$ with negative original outcomes that receive recourse such that $f(x)=0$ but $f(x+\delta^{*})=1$, and (iii) “recourse all,” the proportion of all instances $x$ such that either $f(x)=1$ or $f(x)=0$ but $f(x+\delta^{*})=1$. Metric (iii) is most useful for measuring rate of positive outcomes, since we want to include individuals who are originally assigned a positive outcome.

In Table 1, we show the performance and recourse rates of models trained with our approach and baseline models. Overall, our approach significantly improves recourse without sacrificing performance. Across datasets, models trained using our approach offer recourse at significantly higher rates than the baseline model, for both the “adversarial training” and “gradient descent” approaches to computing recourse. We do not observe this trend when using “linear approximation” to compute recourse; in this case, both the baseline and our approach perform poorly. We believe this effect can be explained by poor LIME approximations of $f_{\theta}$, which are exacerbated by adversarial training since it increases the nonlinearity of $f_{\theta}$. Figure 1 shows how these results vary with $\lambda$: $F_{1}$ scores and accuracies are relatively stable as a function of $\lambda$.

In Figure 2, we plot how these results vary with $\theta_{0}$ (for classifiers trained with $\lambda=0$ and $\lambda=0.8$ on a single data split), using the “adversarial training” method of computing recourse.⁴⁴4Note that the “recourse neg” values are low for $\lambda=0$ because we use the “adversarial training” method to compute recourse, which builds on a fast linear approximation and thus does not exhaustively find recourses. We use this method instead of the more effective “gradient descent” method for efficiency, since the latter is less efficient and would require recomputing recourses for each threshold. High values of $\theta_{0}$ lead to lower recourse rates in all cases. The curves for performance are similar for the baseline and for our approach, but the decline in recourse values begins at lower thresholds in the case of the baseline. Thus, our approach improves recourse for most choices of $\theta_{0}$ without sacrificing performance. The trade-off between recourse and performance depends on the dataset. For adult, performance increases while recourse decreases since the majority label in this dataset is negative, whereas for bail and compas, performance and recourse both decrease as $\theta_{0}$ increases since the majority label is positive.

Performance under PARE guarantees. Next, we show that we can often obtain PARE guarantees without significantly reducing performance. We compare the performance of choosing the decision threshold $\theta_{0}$ to maximize $F_{1}$ score to that of $\theta_{0}$ chosen to obtain PARE classifiers. Specifically, for the latter, we compute $\theta_{0}$ using the approach described in Section 3.3 with parameters $\epsilon=\alpha=0.05$. Then, we evaluate models at thresholds in $10$ equally spaced increments from $0$ to the upper bound and fix $\theta_{0}$ to maximize F1 score. For these experiments, we use the “adversarial training” algorithm to compute recourse; we observed similar trends for the “gradient descent” algorithm.

Results are shown in Table 2. In all cases, choosing $\theta_{0}$ to satisfy the PARE condition yields a classifier that returns recourse at a rate $\geq 1-\epsilon=0.95$, which validates our theoretical guarantees. Furthermore, on all three datasets, the $F_{1}$ score does not significantly decrease when imposing the PARE condition. We do see a decrease in $F_{1}$ score for the baseline model on the adult dataset, but the decrease for our model is smaller, suggesting that our end-to-end framework of training models and fixing $\theta_{0}$ is successful at guaranteeing recourse without a big drop in accuracy.⁵⁵5We can obtain a weaker theoretical guarantee at a smaller cost in performance. For instance, applying PARE to our model in Table 2 with $\epsilon=\alpha=0.25$ results in an F1 score of 0.613 on the adult dataset.

Groundedness of recourses. One key question is whether the recourses of models trained with our approach are grounded in reality—i.e., whether they are plausible modifications of the ground truth label. For instance, if an individual is denied a loan, they should be given a recourse such that if they take the specified action, they actually increase their likelihood of paying back the loan; an individual may increase their income and be given a loan, but still fail to repay it. We want to ensure that our training approach increases the rate of recourses that obey causal relationships in the world, rather than recourses that exploit spurious correlations between features. Directly evaluating groundedness of recourses is challenging, since we do not know the ground truth labels for suggested recourses. Thus, we evaluate whether they are causally grounded and in-distribution.

First, we measure the rate at which causally grounded recourses are offered by models trained with our approach. We apply the algorithm for computing causal recourses (CR) introduced by Karimi et al. (2020b) to evaluate whether our proposed training algorithm improves the rate at which causally grounded recourses are offered. Because CR requires access to an underlying structural causal model (SCM) of the world, we only experiment with the german dataset, for which Karimi et al. (2020b) provide an associated SCM. We measure the proportion of test instances $x$ for which the CR algorithm computes a valid recourse that satisfies the constraint that perturbations be bounded by $\delta_{\text{max}}$—i.e. “recourse neg”.⁶⁶6We select hyperparameters for the CR algorithm that maximize “recourse neg” on the train set. As shown in Figure 3, with increasing $\lambda$, the rate at which recourses are by the CR algorithm increases. This finding suggests that our training algorithm encourages the existence of causally grounded recourses.

Second, we evaluate whether the recourses offered by models trained with our approach are in-distribution with respect to the original training data. In line with prior work (Slack et al., 2020), we train classifiers to distinguish between original data instances and recourses computed by the “gradient descent” algorithm for models trained with our approach ($\lambda=0.8$). In Table 3, we report the accuracies of these classifiers on a held out test set. The low classifier accuracies across all datasets indicate that these recourses are indistinguishable from original data instances. Thus, our framework encourages the existence of recourses that are in-distribution to the original data.

Robustness. Another key question is whether the recourses generated using our approach are robust—i.e., whether small changes to the recourse result in valid recourses. For instance, if an individual increases their income by more (or even slightly less) than the amount suggested in the recourse, they would expect to still be provided with a positive decision.

For each computed recourse $\delta$, we compute a noisy recourse $\delta^{\prime}$ by adding i.i.d. Gaussian noise to each actionable feature of $\delta$—i.e., $\delta_{i}^{\prime}=\delta_{i}+\mathcal{N}(0,\,0.1)$. We consider a recourse $\delta$ robust if its noisy recourse $\delta^{\prime}$ is valid—i.e. if $f(x+\delta^{\prime})=1$. In the top row of Table 4, we report the percentage of recourses found that are robust for a baseline model and model trained with our adversarial approach. As shown, our training approach does not significantly reduce the robustness of recourses: There is a slight drop in robustness for the adult dataset and for the “gradient descent” recourse algorithm for the german dataset; however, for compas and bail, recourses remain robust.

Effect on classifier brittleness. We also investigate the effect of our adversarial training approach on model brittleness. In particular, we measure how sensitive models trained with our adversarial algorithm are to noises in the recourse dimensions, as compared to baseline models. We add i.i.d. Gaussian noise, as described above, to the actionable dimensions of original inputs, and compute the proportion of test instances for which the trained model is robust to this noise. As shown in the bottom row of Table 4, our training approach does not significantly increase model brittleness—we observe a small drop in model robustness in the recourse dimensions for the adult and german datasets and a small increase in robustness for the compas and bail datasets. These results suggest that our training approach effectively ensures recourse without rendering classifiers brittle.