# Equalizing Recourse across Groups

Vivek Gupta
School of Computing
University of Utah
<EMAIL_ADDRESS>
&Pegah Nokhiz∗
School of Computing
University of Utah
<EMAIL_ADDRESS>
&Chitradeep Dutta Roy∗
School of Computing
University of Utah
<EMAIL_ADDRESS>
Suresh Venkatasubramanian
School of Computing
University of Utah
<EMAIL_ADDRESS>
represents equal contribution.

###### Abstract

The rise in machine learning-assisted decision-making has led to concerns
about the fairness of the decisions and techniques to mitigate problems of
discrimination. If a negative decision is made about an individual (denying a
loan, rejecting an application for housing, and so on) justice dictates that
we be able to ask how we might change circumstances to get a favorable
decision the next time. Moreover, the ability to change circumstances (a
better education, improved credentials) should not be limited to only those
with access to expensive resources. In other words, _recourse_ for negative
decisions should be considered a desirable value that can be equalized across
(demographically defined) groups. This paper describes how to build models
that make accurate predictions while still ensuring that the penalties for a
negative outcome do not disadvantage different groups disproportionately.

We measure recourse as the distance of an individual from the decision
boundary of a classifier. We then introduce a regularized objective to
minimize the difference in recourse across groups. We explore linear settings
and further extend recourse to non-linear settings as well as model-agnostic
settings where the exact distance from boundary cannot be calculated. Our
results show that we can successfully decrease the unfairness in recourse
while maintaining classifier performance. 111This research was supported in
part by the NSF under grant IIS-1633724.

_K_ eywords Fairness $\cdot$ Recourse $\cdot$ Kernels $\cdot$ Machine Learning

##  1 Introduction

Algorithm-assisted decision making is now ubiquitous in domains as diverse as
employment, education, credit, insurance, and criminal justice. How can we be
sure that the decisions made through such systems will be fair and
justifiable? One way in which we have traditionally placed checks on the power
of decision-making systems, especially in settings where the decisions may
have significant effects on our lives, is by providing the subject of the
decision with a mechanism for recourse [USL19]: the ability to ask how the
decision was made and what can be done to change it. This idea of recourse is
a part of the Equal Credit Opportunity Act –an individual can demand that
reasons for a loan denial be provided – and research suggests that it might
also eventually be a component of the right to explanation implicated in the
General Data Protection Regulation of the European Union. But the idea of
recourse is more than a legal concept: it can be viewed as an ethical and just
way to make decision-making more transparent. If a decision that materially
affects us is made using factors that we cannot realistically change (for
example a decision based on our gender or race), then this decision eliminates
our agency and is therefore unjust [RCP]. Thus providing opportunities for
recourse is a valuable goal independent of concerns about fairness and non-
discrimination.

Recourse must be feasible to be useful. If an individual is rejected for a
small business loan because of a low credit score and the recommended
“recourse” is to attempt double their net worth, this is not a reasonable
outcome. The situation is even worse if individuals from a different
demographic are given a different recommendation – for example, to take an
(inexpensive) course on money management for small businesses – that is easier
to act on. In other words, providing an explanation is useful, but providing
paths for recourse that are feasible and do not unduly burden disadvantaged
groups is crucial to provide transparent opportunities for advancement.

#### Our Work.

In this paper, we build classifiers that maintain prediction accuracy while
also ensuring opportunities for feasible recourse across groups. To do this,
we define a general notion of recourse as the distance from the decision
boundary (inspired by the work of [USL19]) and utilize it as a regularizer. In
addition, we extend previous linear approaches for recourse [USL19] to non-
linear settings, including both SVMs as well as models defined by black-box
classifiers where we cannot explicitly compute the distance to the decision
boundary. Our results show that we can successfully equalize recourse across
groups in both SVM and model agnostic settings while maintaining accuracy.

On the ethical validity of equalized recourse. Recourse as a good is different
from fairness/nondiscrimination. Regardless of the decision process, recourse
captures the ethical notion of agency: that individuals should be able take
actions to rectify their circumstances, and that decisions are not based on
immutable factors. Recourse might not be cheap – but it should not be
intrinsically infeasible. The idea of equalizing recourse across groups is
then more than “if it’s good it should be good for all”. Rather, if we like
recourse we don’t want a system to provide token recourse to one group whilst
covertly discriminating. That is the justification for our work. We don’t
claim that recourse must be universally applicable. Rather, it focuses on a
specific kind of unfairness and seeks to address it when appropriate. We also
strenuously push back on the idea that equalizing recourse (or even other
fairness measures) “lowers the bar for the disadvantaged”. This perspective
assumes that the bar was set correctly to begin with, rather than potentially
being evidence of structural disadvantage.

##  2 Related work

The idea of recourse as a desirable property of a classifier was introduced
and formalized by [USL19]. In their work they analyze a linear classifier and
show how to use integer linear programming to generate a set of actionable
input variables (flipsets) to change the prediction for any individual. Their
work can be thought of as part of a larger effort in fairness via
_counterfactual analysis_ [WMR17] where the goal was to define fairness in
terms of counterfactual properties of classifications. Strategic
classification techniques [HMPW16, HIV19, MMDH19] which aim to modify the
input in order to trick the classifier and achieve the desired decision are
another concept related to recourse.

Our work fits within the larger setting of methods that try to find
classifiers that satisfy some notion of fairness via constraints during the
model learning process such as for demographic parity, equalized odds [ZVRG17,
ZVGRG17] and individual fairness [DHP+12]. But recourse is orthogonal to those
notions of fairness being studied. That is, it makes sense to talk about
recourse even if the classification is unfair in other respects, because
measures of fairness apply at the point of decision, whereas recourse is a
post-decision analysis. Equalizing recourse affects distance to the boundary,
but does not necessarily affect the decision itself. Having said that,
studying the interaction between fair classification and recourse is a
worthwhile topic for further exploration. Our approach in this paper involves
shifting a baseline classifier through (iterated) processing which is similar
to works such as [FKL16, GCGF16, DIKL18, PRW+17, WGOS17]. Recourse can be
viewed as a kind of explanation: an indicator of how to change one’s
classification. We employ the well-known method LIME [RSG16, RSG18] to
construct local explanations that guide our search for a classifier that
equalizes recourse. [DCL+18] recently proposed a method to provide minimal
absent feature sets from examples which are sufficient for flipping their
prediction.

##  3 Definitions

Recourse (as defined by [USL19]) is the cost of changing a decision from
negative to positive. Formally, assume that we are given a classifier
$h:\mathbb{R}^{d}\to\\{-1,1\\}$ and a metric
$d:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$. The distance metric $d$
captures the “cost” of changing the features of a point $\mathbf{x}$, i.e.,
the effort involved in moving from $\mathbf{x}$ to $\mathbf{x}^{\prime}$ is
$d(\mathbf{x},\mathbf{x}^{\prime})$.

Given a point $\mathbf{x}$ such that $h(\mathbf{x})=-1$, the _recourse_ of
$\mathbf{x}$ is defined as
$r(\mathbf{x})=\min_{h(\mathbf{x}^{\prime})=1}d(\mathbf{x},\mathbf{x}^{\prime})$.
In other words, the recourse of a point is the (closest) distance from that
point to the classifier.

The recourse of a set $S$ is the average recourse of all points in $S$. Given
a set of labeled pairs $(\mathbf{x}_{i},y_{i})_{i=1\ldots
n}\in\mathbb{R}^{d}\times\\{-1,1\\}$ with a _group membership_ function
$g:\mathbb{R}^{d}\to\\{-1,1\\}$, let $G_{j}=\\{\mathbf{x}_{i}\mid
g(\mathbf{x}_{i})=j\\}$.

######  Problem 1 (Equalizing Recourse)

Given a set of labeled pairs $(\mathbf{x}_{i},y_{i})_{i=1\ldots
n}\in\mathbb{R}^{d}\times\\{-1,1\\}$ and $\epsilon>0$, find a classifier $h$
such that the loss $L=\sum_{i}\ell(h(\mathbf{x}_{i}),y_{i})$ is minimized
under the constraint that $u^{+}=|r(G^{-}_{1})-r(G^{-}_{-1})|\leq\epsilon$
where $G^{-}_{i}=\\{\mathbf{x}\in G_{i}\mid h(\mathbf{x})=-1\\}$.

#### Note.

While we borrow the definition of recourse from [USL19], we do not also adopt
their notion of a set of permissible actions to achieve recourse. This is
motivated by the fact that we are trying to optimize recourse across groups
rather than generate a flip set for a specific individual.

##  4 Optimizing for recourse

We now present our optimization frameworks for solving Problem 1. We start
with the case where the classifier can be written explicitly.

###  4.1 Optimizing for recourse with an explicit classifier

For a classifier with a clear functional expression $h:X\to Y$, we can write
down expressions for the minimum distance of a point $x$ to the boundary of
the classifier that is recourse $r(x)$. We then can simultaneously optimize
the loss as well as the recourse.

Below, we show the optimization for equal recourse in kernelizable support
vector machines; however, our method is quite general and can be transferred
to other kernelizable classifiers such as Perceptron.

Support Vector Machines: Consider the case of support vector machines. For any
linear classifier of the form $h(\mathbf{x})=\mathbf{w}^{\top}\mathbf{x}+b$,
the distance to the decision boundary from a point $x$ is
$\frac{\mathbf{w}^{\top}\mathbf{x}+b}{\|\mathbf{w}\|}$. In general, different
features might be harder to modify, which can be modeled by scaling each
dimension $j$ with a factor $c_{j}$. Effectively this amounts to applying a
linear transformation $\mathbf{x}\to\mathbf{C}\mathbf{x}$ via a diagonal
matrix $\mathbf{C}$ where $C_{jj}=c_{j}$, and then computing the corresponding
distance $\frac{\mathbf{w}^{\top}\mathbf{C}\mathbf{x}+b}{\|\mathbf{w}\|}$. If
we now introduce a kernel $\mathbf{K(\cdot,\cdot)}$, the above distance
calculation must happen in the lifted _feature space_ where
$\mathbf{C}\mathbf{x}$ is mapped to $\Phi(\mathbf{C}\mathbf{x})$, and so the
corresponding distance to the boundary is given by

$r(\mathbf{x})=\frac{\mathbf{w}^{\top}\Phi(\mathbf{C}\mathbf{x})+b}{\|\mathbf{w}\|}$

The recourse of a set $(G^{-}_{i})$ is merely the average recourse of the
points in the set and the recourse difference
$u^{+}=|r(G^{-}_{1})-r(G^{-}_{-1})|$.

SVM primal form. We formulate a data-driven primal-form constraint of kernel
SVM inspired from [DC12] with an explicit recourse constraint.

$\displaystyle\text{min}_{\mathbf{w},b,\mathcal{E},\epsilon}$
$\displaystyle\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\lambda\mathcal{E}+\nu\sum_{i=1}^{n}\epsilon_{i}$
such that $\displaystyle-\mathcal{E}\leq u\leq\mathcal{E}$ $\displaystyle
y_{i}(\mathbf{w}^{T}\mathbf{\mathbf{x_{i}}}+b)\geq 1-\epsilon_{i}\text{ and
}\epsilon_{i}\geq 0\qquad\qquad\forall i\in[1\ldots n]$ where $\displaystyle
u=r(G^{-}_{1})-r(G^{-}_{-1})$

$\mathcal{E}$ specifies a bound on recourse difference and $\lambda$ controls
the relative weight of $\mathcal{E}$ in the optimization. $\nu,\epsilon$ are
slack variables and $\epsilon$ is the slack for SVM classification.

SVM dual form. The dual form of the kernel SVM with implicit recourse
constraints is the following:

$\displaystyle
L(\mathbf{w},b,\mathcal{E},\epsilon,\rho_{1},\rho_{2},\gamma,\delta)$
$\displaystyle=\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\lambda\mathcal{E}+\nu\sum_{i=1}^{n}\epsilon_{i}+\rho_{1}(u-\mathcal{E})-\rho_{2}(u+\mathcal{E})$
$\displaystyle-\sum_{i=1}^{n}\gamma_{i}(y_{i}(\mathbf{w}^{T}\mathbf{x_{i}}+b)+\epsilon_{i}-1)-\sum_{i=1}^{n}\delta_{i}\epsilon_{i}$
(1)

where $\rho_{1}$, $\rho_{2}$, $\gamma$, and $\delta$ are dual variables.

We use the $KKT$ conditions with respect to $\mathbf{w},b,\mathcal{E},$ and
$\epsilon$ (equating gradient to 0) to find the optimal parameters.

$\displaystyle\frac{\partial{L}}{\partial{\mathbf{w}}}$
$\displaystyle=\mathbf{w}+\rho_{1}\frac{\partial{u}}{\partial{\mathbf{w}}}-\rho_{2}\frac{\partial{u}}{\partial{\mathbf{w}}}-\sum_{i=1}^{n}\gamma_{i}\mathbf{x_{i}}y_{i}=0$
(2) $\displaystyle\frac{\partial{L}}{\partial{b}}$
$\displaystyle=\rho_{1}\frac{\partial{u}}{\partial{b}}-\rho_{2}\frac{\partial{u}}{\partial{b}}-\sum_{i=1}^{n}\gamma_{i}y_{i}=0$
(3) $\displaystyle\frac{\partial{L}}{\partial{\mathcal{E}}}$
$\displaystyle=\lambda-\rho_{1}-\rho_{2}=0$ (4)
$\displaystyle\frac{\partial{L}}{\partial{\mathcal{\epsilon}_{i}}}$
$\displaystyle=\nu-\gamma_{i}-\delta_{i}=0$ (5)

Iterative Procedure: Since recourse is dependent on the prediction labels,
that is which example is classified as negative, to calculate recourse for
next iteration ($t+1$), we can use the predictions of the last iteration($t$)
of SVM ($y^{t}=h^{t}(x)$) when defining $u$. Then, we can re-write $u$ as the
following for the optimization,

$\displaystyle u$
$\displaystyle=\sum_{i=1}^{n}g(\mathbf{x_{i}})\frac{\left(1-h^{t}(\mathbf{x_{i}})\right)}{2|G_{g(\mathbf{x_{i}})}|}(\mathbf{w}^{T}\mathbf{C}\mathbf{x_{i}}+b)$
(6)

where, $h^{t}(\mathbf{x_{i}})$ $\in$ $\\{1,-1\\}$ denote the classification of
the $\mathbf{x_{i}}$ sample at iteration $t$, and $|G_{g(\mathbf{x_{i}})}|$ is
the cardinality of set $G_{g(\mathbf{x_{i}})}$ to which $\mathbf{x_{i}}$
belongs.

Recourse Scaling:  We scale the recourse by $\|\mathbf{w}\|$, similar to
[DC12], because we care mostly about the relative difference between recourse.
moving across the boundary requires traveling at least
$\frac{1}{2\|\mathbf{w}\|}$ and so we can measure the difference in recourse
in units of the margin by dividing by the margin $\frac{1}{\|\mathbf{w}\|}$
which is equivalent to multiplying by $\|\mathbf{w}\|$.

Let’s denote $p_{i}$ =
$\frac{\left(1-h^{t}(\mathbf{x_{i}})\right)}{2{|G_{g(\mathbf{x_{i}})}|}}$, C
as the diagonal cost matrix, by substituting in equations (6), (2) and (3),

$\displaystyle u$
$\displaystyle=\sum_{i=1}^{n}g(\mathbf{x_{i}})p_{i}(\mathbf{w}^{T}\mathbf{C}\mathbf{x_{i}}+b)$
(7) $\displaystyle\frac{\partial{L}}{\partial{\mathbf{w}}}$
$\displaystyle=\mathbf{w}+\sum_{i=1}^{n}\left(g(\mathbf{x_{i}})p_{i}(\rho_{1}-\rho_{2})\mathbf{C}\mathbf{x_{i}}-\gamma_{i}y_{i}\mathbf{x_{i}}\right)=0$
(8) $\displaystyle\frac{\partial{L}}{\partial{b}}$
$\displaystyle=\sum_{i=1}^{n}\left(g(\mathbf{x_{i}})p_{i}(\rho_{1}-\rho_{2})-\gamma_{i}y_{i}\right)=0$
(9)

Equating equations 4 and 5 to zero cancels the terms involving $\mathcal{E}$
and $\epsilon_{i}$ in the Lagrangian (equation 1).

$\displaystyle L$
$\displaystyle=\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\rho_{1}u-\rho_{2}u-\sum_{i=1}^{n}\gamma_{i}y_{i}(\mathbf{w}^{T}\mathbf{x_{i}}+b)+\sum_{i=1}^{n}\gamma_{i}$
(10)

We now simplify the terms in the Lagrangian to obtain 10 by equating equations
8, 9 to zero and substituting $\mathbf{w}$.

$\displaystyle L$
$\displaystyle=\frac{1}{2}\left[\sum_{i=1}^{n}\left(\gamma_{i}y_{i}\mathbf{x_{i}}-g(\mathbf{x_{i}})p_{i}(\rho_{1}-\rho_{2})\mathbf{C}\mathbf{x_{i}}\right)\sum_{j=1}^{n}\left(\gamma_{j}y_{j}\mathbf{x_{j}}-g(\mathbf{x_{j}})p_{j}(\rho_{1}-\rho_{2})\mathbf{C}\mathbf{x_{j}}\right)\right]$
$\displaystyle+\sum_{i=1}^{n}g(\mathbf{x_{i}})p_{i}(\rho_{1}-\rho_{2})\left((\mathbf{C}\mathbf{x_{i}})^{T}\sum_{j=1}^{n}\left(\gamma_{j}y_{j}\mathbf{x_{j}}-g(\mathbf{x_{j}})p_{j}(\rho_{1}-\rho_{2})\mathbf{C}\mathbf{x_{j}}\right)+b\right)$
$\displaystyle-\sum_{i=1}^{n}\gamma_{i}y_{i}\left(\left(\sum_{j=1}^{n}(\gamma_{j}y_{j}\mathbf{x_{j}}-g(\mathbf{x_{j}})p_{j}(\rho_{1}-\rho_{2})\mathbf{C}\mathbf{x_{j}}\right)^{T}\mathbf{x_{i}}+b\right)+\sum_{i=1}^{n}\gamma_{i}$
(11)

Substitute $K_{i}$ $=$ $g(\mathbf{x_{i}})p_{i}(\rho_{1}-\rho_{2})$ and $H_{i}$
$=$ $\gamma_{i}y_{i}$, we get the following

$\displaystyle L$
$\displaystyle=\frac{1}{2}\left[\sum_{i=1}^{n}\left(H_{i}\mathbf{x_{i}}-K_{i}\mathbf{C}\mathbf{x_{i}}\right)\sum_{j=1}^{n}\left(H_{j}\mathbf{x_{j}}-K_{j}\mathbf{C}\mathbf{x_{j}}\right)\right]+\sum_{i=1}^{n}\left(K_{i}(\mathbf{C}\mathbf{x_{i}})^{T}\sum_{j=1}^{n}\left(H_{j}\mathbf{x_{j}}-K_{j}\mathbf{C}\mathbf{x_{j}}\right)+K_{i}b\right)$
$\displaystyle-\sum_{i=1}^{n}H_{i}\left(\left(\sum_{j=1}^{n}(H_{j}\mathbf{x_{j}}-K_{j}\mathbf{C}\mathbf{x_{j}}\right)^{T}\mathbf{x_{i}}+b\right)+\sum_{i=1}^{n}\gamma_{i}$
(12)

Upon further simplification and cancelling the $b$ terms using equation 9, we
obtain the following:

$\displaystyle L$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}H_{i}K_{j}(\mathbf{C}\mathbf{x_{i}})^{T}\mathbf{x_{j}}-\frac{1}{2}\left[\sum_{i=1}^{n}\sum_{j=1}^{n}H_{i}H_{j}\mathbf{x_{i}}^{T}\mathbf{x_{j}}+\sum_{i=1}^{n}\sum_{j=1}^{n}K_{i}K_{j}(\mathbf{C}\mathbf{x_{i}})^{T}\mathbf{C}\mathbf{x_{j}}\right]$
$\displaystyle+\sum_{i=1}^{n}\gamma_{i}$ (13)

The final Lagrangian formulation after simplification would be:

$\displaystyle\text{min}_{\rho_{1},\rho_{2},\gamma_{i}}$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}\gamma_{i}(\rho_{1}-\rho_{2})g(\mathbf{x_{j}})p_{j}y_{i}(\mathbf{C}\mathbf{x_{j}})^{T}\mathbf{x_{i}}$
$\displaystyle-\frac{1}{2}\left[\sum_{i=1}^{n}\sum_{j=1}^{n}\gamma_{i}\gamma_{j}y_{i}y_{j}\mathbf{x_{i}}^{T}\mathbf{x_{j}}+\sum_{i=1}^{n}\sum_{j=1}^{n}g(\mathbf{x_{i}})g(\mathbf{x_{j}})p_{i}p_{j}(\rho_{1}-\rho_{2})^{2}(\mathbf{C}\mathbf{x_{i}})^{T}\mathbf{C}\mathbf{x_{j}}\right]$
$\displaystyle+\sum_{i=1}^{n}\gamma_{i}$ (14) s.t $\displaystyle
0\leq\rho_{1},\rho_{2}\leq\lambda\quad;\quad\rho_{1}+\rho_{2}=\lambda$
$\displaystyle 0\leq\gamma_{i}\leq\nu\qquad\qquad\forall i\in[1\ldots n]$
$\displaystyle\sum_{i}^{n}(g(\mathbf{x_{i}})p_{i}(\rho_{1}-\rho_{2})-\gamma_{i}y_{i})=0$

We denote $p_{i}$ =
$\frac{\left(1-h^{t}(\mathbf{x_{i}})\right)}{2{|G_{g(\mathbf{x_{i}})}|}}$,
where $h^{t}(\mathbf{x_{i}})$ $\in$ $\\{1,-1\\}$ is the classification of the
$\mathbf{x_{i}}$ sample at iteration $t$, and $|G_{g(\mathbf{x_{i}})}|$ is the
cardinality of set $G_{g(\mathbf{x_{i}})}$ to which $\mathbf{x_{i}}$ belongs.
Here, $C$ is the diagonal cost matrix.

To write the final Quadratic formulation, we need to introduce a pseudo
recourse point ($x_{n+1},y_{n+1}$), where
$\mathbf{x_{n+1}}=\sum_{j=1}^{n}g(\mathbf{x_{j}})p_{j}\mathbf{C}\mathbf{x_{j}}$
and $y_{n+1}=1$, where, $p_{i}$ =
$\frac{\left(1-\textnormal{sgn}(h^{t}(\mathbf{x_{i}}))\right)}{2{|G_{g(\mathbf{x_{i}})}|}}$,
where $|G_{g(\mathbf{x_{i}})}|$ is the cardinality of the set
$G_{g(\mathbf{x_{i}})}$ to which $\mathbf{x_{i}}$ belongs. Let’s denote a new
dual variable $\gamma_{n+1}=\rho_{2}-\rho_{1}$ and new constraint constant
$y^{c}=\sum_{j=1}^{n}g(\mathbf{x_{j}})p_{j}$.

Simplified Lagrangian dual formulation with the pseudo recourse point will be:

$\displaystyle\text{min}_{\gamma_{i}}\quad-\frac{1}{2}\sum_{i=1}^{n+1}\sum_{j=1}^{n+1}\gamma_{i}\gamma_{j}y_{i}y_{j}\mathbf{x_{i}}^{T}\mathbf{x_{j}}+\sum_{i=1}^{n}\gamma_{i}$
$\displaystyle\text{s.t}\quad\quad-\lambda\leq\gamma_{n+1}\leq\lambda$ (15)
$\displaystyle\quad\quad\quad\quad 0\leq\gamma_{i}\leq\nu\qquad\qquad\forall
i\in[1\ldots n]$
$\displaystyle\quad\quad\quad\quad\sum_{i}^{n}\gamma_{i}y_{i}+\gamma_{n+1}y^{c}=0$

The final Quadratic form (QuadForm) for dual SVM is :

$\displaystyle\text{min}_{\mathbf{\mu}}\quad\frac{1}{2}\mathbf{\mu}^{T}\mathbf{M}\mathbf{\mu}+\mathbf{e}^{T}\mathbf{\mathbf{\mu}}$
$\displaystyle
s.t.\quad\mathbf{A}\mathbf{\mu}=\mathbf{0};\quad\mathbf{I^{-}}\mathbf{\mu}\leq\mathbf{a};\quad\mathbf{I^{+}}\mathbf{\mu}\leq\mathbf{b}$
(16)

Here, $\mathbf{M}$ has entries $\mathbf{M}_{(i\leq n,j\leq
n)}=y_{i}y_{j}\mathbf{K(x_{i},x_{j})}$,
$\mathbf{M}_{(n+1,n+1)}=\sum_{(i,j=1)}^{n}g(\mathbf{x_{i}})g(\mathbf{x_{j}})p_{i}p_{j}\mathbf{K(Cx_{i},Cx_{j})}$,
and $\mathbf{M}_{(i\leq
n,n+1)}=\sum_{(j=1)}^{n}g(\mathbf{x_{j}})y_{i}p_{j}\mathbf{K(x_{i},Cx_{j})}$,
where
$\mathbf{K(x_{i},x_{j})}=\langle\Phi(\mathbf{x_{i}})\cdot\Phi(\mathbf{x_{j}})\rangle$,
$\mathbf{K(x_{i},Cx_{j})}=\langle\Phi(\mathbf{x_{i}})\cdot\Phi(\mathbf{Cx_{j}})\rangle$,
and
$\mathbf{K(Cx_{i},Cx_{j})}=\langle\Phi(\mathbf{Cx_{i}})\cdot\Phi(\mathbf{Cx_{j}})\rangle$
$\forall$ $\\{i,j\\}$ $\in$ $\\{1,\dots,n\\}$. Note that $\mathbf{M}$ is a
symmetric and positive semi definite matrix.

Here, we have variables
$\mathbf{\mu}=[\gamma_{1}\gamma_{2}\dots\gamma_{n+1}]$, equality matrix
$\mathbf{A}=[y_{1}\ldots y_{n},y^{c}]$, where
$y^{c}=\sum_{j=1}^{n}g(\mathbf{x_{j}})p_{j}$ inequality matrices
$\mathbf{I^{-}}=-\mathbf{I}_{(n+1)}$ and $\mathbf{I^{+}}=\mathbf{I}_{(n+1)}$,
where $\mathbf{I}_{(n+1)}$ is the identity matrix,
$\mathbf{a}=[0_{n}\lambda]$, $\mathbf{b}=[\nu_{n}\lambda]$ and
$\mathbf{e}=[-1_{n}0]$.

This form is compatible with any quadratic programming solver (CVXOPT) [ADV13]
which results in the optimal values of $\mathbf{\mu}^{*}$, i.e., the optimal
values of $\gamma^{*}$. Sometimes, solving a complete QP is intractable as it
take an order $n^{3}$. However, we can solve sub-problem to speed out the QP.
We can use the standard SMO technique [ZYX+08, KSBM01] which optimise the dual
variable’s efficiently.

We can calculate $\mathbf{w}$ by equating 8 to $0$ and substituting
$\gamma_{n+1}^{*}=\rho_{2}-\rho_{1}$ :

$\mathbf{w^{*}}=\sum_{i=1}^{n}\left(g(\mathbf{x_{i}})p_{i}\gamma_{n+1}^{*}\mathbf{C}\mathbf{x_{i}}+\gamma_{i}y_{i}\mathbf{x_{i}}\right)$
(17)

For a linear kernel $\mathbf{w}$ will be a vector expressed in a closed form.
However, for any other kernel, we cannot calculate $\mathbf{w}^{*}$ explicitly
because of the kernel; however, we can explicitly calculate
$\|\mathbf{w}^{*}\|$ as follows because of kernel property (obtained by
applying $\mathbf{w}^{T}\mathbf{w}$ and some simplification):

$\|\mathbf{w}^{*}\|=\mathbf{\mu}^{*T}\mathbf{M}\mathbf{\mu}^{*}$ (18)

For calculating the bias $b^{*}$, we need to use the support vectors, and
those samples whose $\gamma_{i}^{*}$ is significantly above a certain
threshold $t$ should be on margins. To calculate the final $b^{*}$ value, we
can take means of all values from support vectors:

$b_{i}=y_{i}-\mathbf{w^{*}}^{T}\mathbf{x_{i}}$ (19)
$b_{i}=y_{i}-\sum_{j=1}^{n}\left(g(\mathbf{x_{j}})p_{j}\gamma_{n+1}^{*}\mathbf{K(\mathbf{C}\mathbf{x_{j}}},\mathbf{x_{i}})+\gamma_{i}y_{j}\mathbf{K(\mathbf{x_{j}},\mathbf{x_{i}}})\right)$
(20) $b^{*}=\frac{\sum_{i=1}^{\\#suppvec}b_{i}}{\\#suppvec}$ (21)

The final classifier decision for a new prediction example $x_{p}$ can be
obtained as follows:

$h(x_{p})=\textnormal{sgn}(\mathbf{w}^{T}\mathbf{x_{p}}+b^{*})$ (22)

Substitute $\mathbf{w}$ from 17 into 22 yielded the final expression,

$h(x_{p})=\textnormal{sgn}(\sum_{i=1}^{n}\gamma_{i}^{*}y_{i}\mathbf{K(x_{i},x_{p}))}+\gamma_{n+1}^{*}\sum_{i=1}^{n}g(\mathbf{x_{i}})p_{i}\mathbf{K(Cx_{i},x_{p})}+b^{*})$
(23)

We can similarly calculate the final recourse ($u^{+}$)) by substituting
$\mathbf{w}$ from 17 into 6 as follows,

$\displaystyle\Big{|}\frac{\sum_{j=1}^{n}g(\mathbf{x_{j}})\frac{\left(1-\textnormal{sgn}(h(\mathbf{x_{j}}))\right)}{2{|G_{g(\mathbf{x_{j}})}|}}\left(\sum_{i=1}^{n}\gamma_{i}^{*}y_{i}\mathbf{K(x_{i},Cx_{j}))}+\gamma_{n+1}^{*}\sum_{i=1}^{n}g(\mathbf{x_{i}})p_{i}\mathbf{K(Cx_{i},Cx_{j})}+b^{*}\right)}{\|\mathbf{w}^{*}\|}\Big{|}$
(24)

where, $\|\mathbf{w}^{*}\|=\mathbf{\mu}^{*T}\mathbf{M}\mathbf{\mu}^{*}$ from
18 , and the rest of terms are as defined before.

Here, in equations 23 and 24 we can use any suitable kernel, e.g., polynomial,
linear, radial etc. to obtain the kernel matrix terms.

#### An iterative procedure

While the above formulation allows us to equalize recourse, it cannot be
solved as written. This is because the specification of the dual requires the
knowledge of which points are classified negatively due to the calculation of
$h(x_{j})$. However, for any _fixed_ classifier ($h(x)$), we can identify the
points that are classified negatively and use that to compute a new recourse-
equalized classifier. This suggests an iterative strategy where the classifier
from the previous round (t) i.e. $h^{t}(x)$ is used to identify negatively-
classified points which are then used to compute the classifier for this round
(t+1) i.e. ($h^{t+1}(x)$). We summarize this in Algorithm 2.

#### An example.

We applied Algorithm 2 to two synthetic toy datasets to analyze our approach.
In 1, we can see the motivation behind introducing recourse as a regularizer
to be equalized across groups. We illustrate the positive class on the solid
orange region with red datapoints. Conversely, the negative class is shown on
the solid white background. The decision boundary is a solid black line that
distinguishes the two areas. The dashed lines are the indicators of the
margins. Our goal is to equalize recourse for the negatively classified groups
$G^{-}_{1}$ in the brown transparent region that is closer to the boundary and
the farther $G^{-}_{-1}$ in the gray transparent region which has a larger
recourse. As we increase $\lambda$ and thus the importance of equalizing
recourse, we observe that in the linear case, the decision boundary tilts such
that the under-represented negative group will get closer to the decision
boundary and the recourse is equalized. In the non-linear case, the boundary
margins (dashed lines) are uni-modal around the positive class (brown), thus
making it farther from the outer negative class (gray). As we increase
$\lambda$, the boundary margins (dashed lines) become bi-modal with two dashed
margins around both groups which means recourse is equalized.

Figure 1: Equalizing recourse across groups, from left (vanilla SVM ) to right
($\lambda$ increased).

Flipset generation. Similar to [USL19], we can generate flipsets by finding
the closest points to the classifier boundary according to our notion of
recourse. This is similar to the linear programming optimization approach
proposed by [USL19]. One difference is since our attributes are continuous, we
have more freedom in finding the flipsets since we know the exact closest
boundary points according to our recourse definition. Besides, if we have
constraints on attributes (e.g., some features are immutable and cannot be
changed such as gender) we can use the ILP/LP idea used in [USL19] and utilize
it in our balanced recourse classifier to obtain the required flipsets. Thus,
our approach is orthogonal to [USL19]’s ILP/LP and can generate flipsets.

One might think of extending the ILP-based formulation [USL19] for obtaining
fairness in recourse on top of generating flipsets without changing the
boundary. For example, to achieve equal recourse one could optimize
$\min|\sum_{x_{i}\in G^{-}_{1}}c_{i}{v_{i}}-\sum_{x_{j}\in
G^{-}_{-1}}c_{j}{v_{j}}|$ using linear programming for finding flip-sets which
ensure equal recourse. Here, $c_{i}v_{i}$ is the cost of changing features of
$x_{i}$ to achieve recourse using the action set $v_{i}$ as defined in
[USL19]. However, this idea contradicts the original notion of minimum
actionable flipsets, which is achieved by minimizing $\min|\sum_{x_{i}\in
G^{-}_{\\{1,-1\\}}}c_{i}{v_{i}}|$. The flipset solution for equal recourse
might not necessarily be of the minimum cost. So there might be other low-cost
flipsets for actionable recourse. Thus, the individuals always have the right
to choose the other flipsets that have a lower cost for them compared to the
ones that remove the unfairness. Hence, changing the boundary is essential for
yielding equal recourse across groups. In our case, we are changing the
boundary to ensure that the minimum flipsets yields equal recourse.

###  4.2 Model agnostic settings

The previous approach for equalizing recourse is only applicable where we have
an explicit mathematical formulation of the distance of a point from a
classifier boundary and also we know the full objective of the underlying
model. This is not the case with any arbitrary non-linear classifier. Also
this scheme is not feasible in the model agnostic setting with black-box
access. Moreover, finding a closed-form formula of the minimum distance of a
point from a non-linear boundary (hence recourse) is either hard or infeasible
in general.

To remedy this situation, we propose an approach that is based on LIME, a
technique introduced by [RSG16] to provide a local explanation for black-box
classifiers. LIME works by sampling points from a normal distribution centered
at a particular point or the mean of the dataset. LIME then fits a linear
model using weighted regression for the sampled points against the decision
produced by a black-box classifier. Our method hinges on the idea that LIME
lets us approximate a complex decision boundary by training a linear
classifier for every individual datapoint, and therefore, allowing us to
compute the approximate distance of a point from the actual non-linear
decision boundary. Once we have distances (and therefore the estimates for
recourse $r(G_{i})$ for each group), we can build a new classifier. However,
since the classifier is a black-box we cannot explicitly introduce a
regularization term as before.

Therefore, to change the black box non-linear boundary to equalize recourse,
we propose an example-dependent weighted learning approach. The idea is that
we can retrain the black-box classifier by passing the weight parameters for
each sample point. Intuitively, we will re-weight points so that groups with
large recourse (i.e., a larger distance to the decision boundary) are given a
lower weight than groups with small recourse. The effect of this is to move
the decision boundary _away_ from the highly weighted points and towards the
lower-weighted points, which is the desired effect.

#### Algorithm.

At first, we generate a set of samples (neighborhood) using multivariate
normal centered at the mean of the dataset and scaled accordingly. We then
train the black-box classifier. For every datapoint in the training set 10
most important features are chosen using a weighted regression using an
exponential kernel with Euclidean distance metric for the sample weights. Now
finally a ridge linear classifier is trained on the samples using only the
selected features. This classifier is used to calculate the approximate
distance of the datapoint from the original black-box classifiers boundary. We
do this for all the training points from the trained classifier’s boundary.
And we average it over several sets of samples normalized by the difference
between maximum and minimum distances for the negative class. We keep the
weights of points in the positive class ($h(x)=1$), unchanged (i.e. 1). To
calculate the weight of point ($x_{i}$) in the negative class ($h(x_{i})=-1$),
we estimate the normalized minimum average distance (namd($x_{i}$)) of $x_{i}$
from the decision boundary

$\text{namd}{(x_{i})}=\frac{\min_{x_{l}\in
X^{-}}(dist^{AVG}(x_{l}))}{dist^{AVG}(x_{i})}$

Here $X^{-}$ is set of negatively classified points, We can set the weight
$sw(x_{k})$ of any $x_{k}$ point by using the following formula,

$\displaystyle sw(x_{k})=\begin{cases}1&\text{$h(x_{k})=1$}\\\
namd(x_{k})&\text{otherwise}\end{cases}$ (25)

Now, we retrain the classifier with these new sample weights. The classifier
tries to be more certain in predicting the class of a point which is weighed
more than the ones that are weighed less. Therefore, the above weighing scheme
shifts the classifier’s boundary closer to the negative points that are
farther (in other words have smaller weights) while maintaining the distances
of the closer ones and the positive class mostly unchanged. Refer to Algorithm
2 for a pseudo-code description.

Data: $\mathbf{X}$, $\mathbf{Y}$, $\mathbf{C}$, g, $\lambda$

Result: $\mathbf{w}$, $b$ and $\mathbf{Y}^{p}$

/* Initialization by Vanilla SVM */

1 $\lambda_{init}=0$ ; $\mathbf{Y}^{p}$ = $\mathbf{Y}$;

2 $\mathbf{\mu}=$ QuadForm($\mathbf{X}$, $\mathbf{Y}$, $\mathbf{C}$, g,
$\mathbf{Y}^{p}$, $\lambda_{init}$);

3 Update $\mathbf{Y}^{p}$ = h($\mathbf{X}$);

/* SVM with a Recourse Constraint */

4 for  _$\mathbf{Y}!=\mathbf{Y}^{p}$_ do

5 $\mu$ $=$ QuadForm($\mathbf{X},\mathbf{Y},\mathbf{C},g,\mathbf{Y}^{p}$,
$\lambda$);

6 Update $\mathbf{Y}^{p}$ = h($\mathbf{X}$);

7

8 end for

return $h$

(a) Recourse regularized SVM classification

Data: $h$, $sw$, $n$

Result: $h*$

/* Choose best LIME fit */

1 Choose best LIME samples $L^{*}$ in terms of prediction accuracy.;

2 $sw_{0}\leftarrow 1$;

3 Train classifier ($h$) with samples weights ($sw_{0}$);

4 Find average recourse against $h$ using $L^{*}$;

5 Update sample weights ($sw$) using Eq.25;

6 Train classifier ($h^{*}$) with sample weights ($sw$);

7 Find average recourse against $h^{*}$ using $L^{*}$;

return $h^{*}$

(b) Recourse equalization in black-box classification

Figure 2: Algorithms for Recourse Equalization a) Regularised SVM and b)
Black-Box Classification

##  5 Experiments

In this section, we will provide the details of our datasets and the
experimental settings.

Dataset description. We evaluate both of our approaches on 4 datasets, credit
[YL09], german [BL13], givemecredit and propublica.222german:
https://github.com/algofairness/fairness-
comparison/tree/master/fairness/data/preprocessed, givemecredit:
https://www.kaggle.com/c/GiveMeSomeCredit, propublica:
https://github.com/propublica/compas-analysis. We set the target variable as
binary with labels +1 and -1 for all datasets. Positive sensitive attribute
for credit was chosen to be _Married_ and everything else as negative, the
target value is -1 if the person defaults on a future credit card payment (we
use a preprocessed version from [USL19] that uses the financial features). In
the case of givemecredit, after removing rows with missing information, the
negative sensitive class was individuals with age _under 35_ and target is if
the individual will be in financial distress in the next two years. We used
_gender_ as sensitive attribute and set female as the negative class for both
german and propublica. The target attribute for german is credit risk of a
person and for propublica it is whether an individual would recommit a crime
within 2 years from release.

#### Experimental settings.

For every run, we choose a random sample from a dataset. We choose a random
sample out of all 4 datasets which is $5,000$ datapoints for credit (13
features), and $1,000$ for givemecredit (10 features), and propublica (402
features) and german (59 features). We then use a $80/20$ split for train and
test respectively. We perform 10-fold cross-validation in terms of minimizing
recourse difference to choose the best parameter set for both linear and non-
linear kernels. We search over $\lambda=\\{0.2,0.5,1,2,10,50,100\\}$ and
polynomial kernel with $degree=\\{2,3,5\\}$. We then perform 10 iterations of
our SVM-based algorithm using the optimum parameter set to obtain the final
classifier. The costs for all the features are set to 1, and $\upsilon$ (cost
parameter) is set to 10. We use the CVXOPT package [ADV13] for solving the
quadratic formulation, shown in 16.

In the agnostic setting, we run our experiments with $1000$ datapoints for all
datasets using the following parameters. We execute 5 runs to choose 2 best
set of samples for approximating black box classifier by LIME in terms of
accuracy. We execute 10 independent runs of algorithm 2 and aggregate the
results to generate the plots for all 4 datasets. We present our results on
three black-box classifiers, namely Random Forest, Logistic Regression, and
AdaBoost from the scikit-learn (v0.21) package [PVG+11].333Specifically,
sklearn.ensemble.RandomForestClassifier, sklearn.linear_model.
LogisticRegression, sklearn.ensemble.AdaBoostClassifier We choose both
Adaboost and Random forest primarily because they are non-linear in nature and
lack the closed-form mathematical objective function that our previous method
was based on. Our reason for choosing Logistic classifier is mainly to check
how the black-box strategy works for simple linear classifiers. We use the
Logistic and Adaboost classifier with default parameters and RandomeForest is
trained with _max-depth_ (tree depth) set to 4 to avoid over-fitting and
everything else is set as default.

In the SVM and model agnostic settings, we evaluate our proposed approaches
for equalizing recourse _before_ and _after_ regularization and sample re-
weighting, respectively. All results are reported with box and whisker plots
for complete details on the mean, median, and the percentiles of the accuracy
and the recourse difference distributions. The outliers are not shown in the
plot; however, they are considered in the computations.

Figure 3: Linear (upper) and polynomial (lower) kernels’ results on recourse
and accuracy. Yellow circle is the mean, and the orange line is the median.

###  5.1 SVM results

We start by discussing the results of applying Algorithm 2, listed in Table 1.
We can summarize these results by showing the percentage reduction in recourse
difference ($\frac{\text{recourse\,\,
before}-\text{recourse\,\,after}}{\text{recourse\,\,before}}$) for different
data sets (mean of the distributions). For this summary, we focus on the
polynomial and linear kernels.

Table 1: Summary of percentage reduction in recourse difference for polynomial and linear kernels | Linear | Polynomial
---|---|---
Dataset | Train | Test | Train | Test
german | 80% | 0% | 91% | 23%
credit | 52% | 29% | 51% | 50%
propublica | 84% | 16% | 99% | 23%
givemecredit | 90% | 9% | 100% | 55%

In general, we observe that we are yielding an improvement in the unfairness
of recourse across groups in terms of the means of the difference. We also
observe that the medians are decreasing (and we have smaller ranges of
percentile distributions after applying our algorithm), which means at least
around half of the runs are yielding a smaller recourse difference compared to
_before_ even though the mean might remain the same due to outliers, e.g., in
german the test recourse difference is not decreasing significantly ‘after’
applying our algorithm compared to other datasets. However, more than $50\%$
(e.g., lower $50$th percentile for both kernels) of the runs have a smaller
recourse difference _after_ according to the median, or up to $75$th
percentile of givemecredit data have a smaller recourse. In addition, we
observe that the accuracy roughly stays the same (it decreases no more than 1%
and sometimes even slightly increases). Furthermore, the improvement we
acquired using the linear kernel is less compared to polynomial, we assume
this is due to fewer degrees of freedom (fewer model parameters) in linear
kernel compared to polynomial to change the decision boundary.

Figure 4: RandomForest (left), LogisticRegression (middle), AdaBoost (right)
classifier’s results on recourse and accuracy. Yellow circle is the mean and
the orange line is the median.

###  5.2 Model agnostic results

We have listed the results of applying Algorithm 2 in Table 2. Similar to SVM,
both train and test sets show improvements in terms of the mean, median and
percentile distributions of the recourse difference _before_ and _after_
equalization. In addition, the mean accuracies for credit, german, and
propublica are not reduced by more than 2%, except for the training accuracy
during logistic regression for german ($6$% drop), test/train accuracies for
propublica (around 7% and 5% drops, respectively), and test/train accuracies
for givemecredit (around 7% for both).

General Analysis. Overall, these results show that our proposition to define
recourse for a group as the mean of the distances from the decision boundary
and its incorporation in the SVM formulation as a regularizer can reduce the
unfairness in the recourse across groups. Additionally, the simple re-
weighting strategy works well in terms of recourse difference reduction for
classifiers that support sample weights and could be useful for black-box
scenarios where more fine-grained control cannot be obtained for explicit
distances from the boundary in terms of model parameters. Both methods yield
these results without affecting the accuracy significantly. In addition, the
median and percentage-based distributions of the recourse difference across
various runs decrease after equalization.

Table 2: Summary of percentage reduction in recourse difference for Model Agnostic | Random Forest | Logistic Regression | AdaBoost
---|---|---|---
Dataset | Train | Test | Train | Test | Train | Test
credit | 41% | 99% | 90% | 100% | 83% | 95%
german | 64% | 42% | 8% | 53% | 37% | 60%
propublica | 59% | 43% | 29% | 52% | 49% | 56%
givemecredit | 83% | 70% | 20% | 100% | 66% | 14%

##  6 Conclusion and future work

In summary, this work introduces a new notion of fairness in recourse
(Equalizing Recourse), i.e., classifiers that maintain a good performance
while providing opportunities for feasible recourse across groups. We proposed
various approaches based on a general definition of recourse as the absolute
value of the difference between the average of the distance of all points from
the boundary in a group. We then utilized this definition to make
classification models fair in terms of recourse. Our approach is generalizable
to linear and non-linear settings, including kernelizable (support vector
machines) and non-kernelizable (decision trees) models. We empirically
validated these methods through intensive experiments. This is the first work
on outcome-independent fairness in terms of recourse (equal costs for changing
the outcome) as far as our knowledge. Incorporating multiple groups/sensitive
attributes is a possible future direction. In addition, instead of only
equalizing the means of the distributions, we can equalize the distributions
themselves using correlation or KL divergence.

## References

  * [ADV13] M Andersen, Joachim Dahl, and Lieven Vandenberghe.  Cvxopt: A python package for convex optimization.  abel. ee. ucla. edu/cvxopt, 2013.
  * [BL13] Kevin Bache and Moshe Lichman.  Uci machine learning repository, 2013.
  * [DC12] Sune Darkner and Line H Clemmensen.  Data driven constraints for the svm.  In International Workshop on Machine Learning in Medical Imaging, pages 70–77. Springer, 2012.
  * [DCL+18] Amit Dhurandhar, Pin-Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das.  Explanations based on the missing: Towards contrastive explanations with pertinent negatives.  In Advances in Neural Information Processing Systems, pages 592–603, 2018.
  * [DHP+12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness through awareness.  In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226. ACM, 2012.
  * [DIKL18] Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson.  Decoupled classifiers for group-fair and efficient machine learning.  In Conference on Fairness, Accountability and Transparency, pages 119–133, 2018.
  * [FKL16] Benjamin Fish, Jeremy Kun, and Ádám D Lelkes.  A confidence-based approach for balancing fairness and accuracy.  In Proceedings of the 2016 SIAM International Conference on Data Mining, pages 144–152. SIAM, 2016.
  * [GCGF16] Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander.  Satisfying real-world goals with dataset constraints.  In Advances in Neural Information Processing Systems, pages 2415–2423, 2016.
  * [HIV19] Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan.  The disparate effects of strategic manipulation.  In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259–268. ACM, 2019.
  * [HMPW16] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.  Strategic classification.  In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111–122. ACM, 2016.
  * [KSBM01] S. Sathiya Keerthi, Shirish Krishnaj Shevade, Chiranjib Bhattacharyya, and Karuturi Radha Krishna Murthy.  Improvements to platt’s smo algorithm for svm classifier design.  Neural computation, 13(3):637–649, 2001.
  * [MMDH19] Smitha Milli, John Miller, Anca Dragan, and Moritz Hardt.  The social cost of strategic classification.  In Proceedings of ACM FAT*, 2019.
  * [PRW+17] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger.  On fairness and calibration.  In Advances in Neural Information Processing Systems, pages 5680–5689, 2017.
  * [PVG+11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [RCP] Alan Rubel, Clinton Castro, and Adam Pham.  Algorithms, bias, and the importance of agency.  Jo Bates Paul D. Clough Robert Jäschke, page 9.
  * [RSG16] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Why should i trust you?: Explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144. ACM, 2016.
  * [RSG18] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Anchors: High-precision model-agnostic explanations.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * [USL19] Berk Ustun, Alexander Spangher, and Yang Liu.  Actionable recourse in linear classification.  In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 10–19. ACM, 2019.
  * [WGOS17] Blake Woodworth, Suriya Gunasekar, Mesrob I Ohannessian, and Nathan Srebro.  Learning non-discriminatory predictors.  arXiv preprint arXiv:1702.06081, 2017.
  * [WMR17] Sandra Wachter, Brent Mittelstadt, and Chris Russell.  Counterfactual explanations without opening the black box: Automated decisions and the gdpr.  Harvard Journal of Law & Technology, 31(2):2018, 2017.
  * [YL09] I-Cheng Yeh and Che-hui Lien.  The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients.  Expert Systems with Applications, 36(2):2473–2480, 2009.
  * [ZVGRG17] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi.  Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment.  In Proceedings of the 26th International Conference on World Wide Web, pages 1171–1180. International World Wide Web Conferences Steering Committee, 2017.
  * [ZVRG17] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi.  Fairness constraints: Mechanisms for fair classification.  In Artificial Intelligence and Statistics, pages 962–970, 2017\.
  * [ZYX+08] Zhi-Qiang Zeng, Hong-Bin Yu, Hua-Rong Xu, Yan-Qi Xie, and Ji Gao.  Fast training support vector machines using parallel sequential minimal optimization.  In 2008 3rd international conference on intelligent system and knowledge engineering, volume 1, pages 997–1001. IEEE, 2008.