Source-linked AI summary
Actionable Recourse in Linear Classification
Berk Ustun, Alexander Spangher, Yang Liu
TL;DR
The paper addresses whether people subject to machine-learning decisions can obtain desired outcomes through feasible changes to actionable inputs. It develops integer-programming tools for evaluating and generating recourse in linear classifiers, finding that standard modeling practices can substantially affect recourse and motivating practical evaluation.
Problem
People affected by machine-learning decisions need recourse, but existing practice does not adequately establish whether actionable changes exist or how difficult they are across decision subjects.
Method
The paper formulates recourse as a constrained discrete optimization problem and develops integer-programming tools to evaluate feasibility and difficulty and generate flipsets for linear classifiers.
Results
Recourse is significantly affected by model-development and deployment choices, including regularization, feature selection, operating thresholds, and the deployment population.
Takeaways & Limitations
Recourse should be evaluated for individuals in a model’s target population rather than assumed from model transparency or predictive modeling practice alone.
Takeaways & Limitations
Abridged flipsets may fail if people unknowingly alter undisclosed actionable features, unless additional constraints or robust actions are provided.
Abstract
from arXiv · showhide
Machine learning models are increasingly used to automate decisions that affect humans - deciding who should receive a loan, a job interview, or a social service. In such applications, a person should have the ability to change the decision of a model. When a person is denied a loan by a credit score, for example, they should be able to alter its input variables in a way that guarantees approval. Otherwise, they will be denied the loan as long as the model is deployed. More importantly, they will lack the ability to influence a decision that affects their livelihood. In this paper, we frame these issues in terms of recourse, which we define as the ability of a person to change the decision of a model by altering actionable input variables (e.g., income vs. age or marital status). We present integer programming tools to ensure recourse in linear classification problems without interfering in model development. We demonstrate how our tools can inform stakeholders through experiments on credit scoring problems. Our results show that recourse can be significantly affected by standard practices in model development, and motivate the need to evaluate recourse in practice.
1 INTRODUCTION
The paper frames recourse as a person’s ability to obtain a desired outcome from a fixed model through feasible, actionable changes. It develops integer-programming tools to evaluate recourse and generate actionable changes for linear classifiers, addressing how modeling choices can restrict or burden that ability.
- Motivation: Recourse is the ability to obtain a desired outcome from a fixed model by changing actionable inputs, preserving a person’s ability to influence consequential decisions.Without recourse, a person denied a loan remains denied while the model is deployed.
- Motivation: Transparent linear classifiers may still deny recourse because of immutable or inappropriate features, deployment-population differences, operating thresholds, or drastic required changes.These failure modes motivate evaluating both whether recourse exists and how difficult it is.
- Approach: The paper answers recourse questions by formulating an integer program that searches for feasible changes to flip a fixed linear classifier while respecting actionable constraints.The formulation excludes immutable changes and infeasible mutable changes such as changing n_credit_cards from 5 to 0.5.
- Contributions: The authors provide a procedure that estimates recourse feasibility and difficulty across a target population by solving the optimization problem for each negatively classified point.The procedure is intended for model development, procurement, or impact assessment.
- Contributions: They also introduce flipsets: lists of actionable changes intended to help a person obtain a desired outcome from a linear classifier.The paper connects flipsets to adverse action notices, which may otherwise fail to provide actionable information.
- Related Work: The tools extend counterfactual methods by enforcing discrete constraints, proving when actionable explanations do not exist, enumerating explanations, and selecting among them with custom costs.The paper distinguishes these capabilities from explanation methods that may not reveal actionable changes or verify their feasibility.
2 PROBLEM STATEMENT
The paper formulates recourse as finding feasible, actionable changes that flip an undesirable linear-classifier prediction, and characterizes when such changes exist and how costly they are. Recourse depends on feature actionability, feature bounds, classifier behavior, and the alignment of actionable scores with outcomes.
- Optimization framework: Recourse seeks an action a from a feasible set A(x) that changes a person’s prediction from f(x) = −1 to f(x + a) = +1.Immutable features permit only zero change, while conditionally immutable features may permit no change for some individuals.
- Optimization framework: If the optimization problem is feasible, its optimal solution is the minimal-cost action that flips the prediction.
- Optimization framework: If the optimization problem is infeasible, no action can attain the desired outcome, certifying that the classifier provides no actionable recourse for that person.
- Feasibility guarantees: A linear classifier guarantees recourse for all individuals when it uses only actionable features and predicts both classes.Conversely, classifiers using immutable features exclusively or predicting one class consistently deny recourse to all individuals.
- Feasibility guarantees: When all features are bounded, a classifier with at least one immutable feature may deny recourse to some individuals.Feasibility therefore depends on judicious bounds for actionable features; loose bounds can allow recourse only through drastic changes with large costs.
- Cost guarantees: The expected cost guarantee is tighter when the actionable score component aligns perfectly with true outcomes, yielding internal risk RA(f) = 0.The bound can also be reduced by decreasing the maximum unit cost of actionable changes.
3 INTEGER PROGRAMMING TOOLS
The paper converts actionable recourse search into an integer program and uses it to optimize feasible actions, audit populations, and generate flipsets. The formulation supports discrete action spaces, customizable constraints, broad cost functions, and certificates of optimality or infeasibility.
- IP formulation: The integer-program formulation searches over actionable changes for binary, ordinal, and categorical features while enforcing feasibility constraints.Users can add logical constraints, including restrictions on which features may change together.
- IP formulation: The formulation can optimize non-linear and non-convex cost functions because cost values are encoded in precomputed parameters.Some non-separable cost functions can also be represented with minor formulation changes.
- IP formulation: Discretizing real-valued actions over a suitably refined grid preserves recourse feasibility and cost while enabling richer cost functions.An alternative formulation can represent real-valued actions with continuous variables.
- Auditing recourse: The audit solves the integer program for sampled negative predictions to estimate the proportion with feasible recourse and the distribution of minimal recourse costs.The procedure requires the classifier coefficients and feature vectors sampled from the target population.
- Cost functions: The maximum percentile-shift cost measures difficulty by the largest percentile change required across altered features.An optimal cost of 0.25 means every feasible action must change some feature by at least 25 percentiles.
- Flipsets: Flipsets enumerate minimal-cost actions that alter distinct feature subsets by repeatedly solving the integer program and excluding previously used subsets.Each returned action becomes a flipset item listing current and desired feature values.
4 DEMONSTRATIONS
Credit-scoring experiments show that standard modeling and deployment choices can substantially alter recourse, even when predictive performance changes little. The tools audit recourse feasibility and cost, generate minimal-cost flipsets, and reveal disparities across populations.
- Credit-data setup: Credit experiments use integer-program audits of actionable recourse for logistic classifiers, alongside flipsets showing minimal-cost changes for denied applicants.The credit dataset contains 30,000 individuals and 16 features; discrete, immutable, and directionally constrained features define actionable changes.
- Model Selection: ℓ1-penalty tuning has a minor effect on test error but a major effect on recourse feasibility and cost.Small penalties provide recourse to all individuals, whereas larger penalties reduce recourse as regularization removes actionable features.
- Model Selection: Increasing the ℓ1-penalty nearly doubles median recourse cost from 0.20 to 0.39.A cost of q means changing a feature by at least q percentiles; the corresponding median changes are 20 and 39 percentiles.
- Model Selection: Models selected for predictive performance may preclude recourse for some individuals even when similarly performing models provide recourse to everyone.The experiment uses standard feature selection and parameter tuning to illustrate this deployment risk rather than claim a general ℓ1-regularization relationship.
- Model Selection: Audits with alternative action sets identify whether immutable features, such as prior-default indicators, drive a lack of recourse.Replacing an immutable credit-history feature with a mutable recent-default variant could yield a model that provides recourse.
- Dataset Shift: Among young adults, median recourse cost is 0.66 under the biased model versus 0.14 under the baseline model.Both classifiers approve 10% of examples, and the comparison controls the action set and cost function; the observed difference depends on age-distribution shift.
- Protected-group disparities: Recourse cost can differ between males and females even when gender is omitted from the classifier.The analysis compares individuals with the same true outcome and similar predicted risk, using cost distributions and matched-pair flipsets.
5 CONCLUDING REMARKS
The concluding remarks position recourse as a precise form of human agency and describe audits and flipsets as ways to evaluate it. They also identify limits involving nonlinear models, incomplete flipsets, model theft, and actions that may change predictions without improving true outcomes.
- Scope and limitations: For nonlinear classifiers, local linear approximations may find actionable changes but cannot prove infeasibility.The authors are extending their tools beyond linear models, so non-recourse claims remain unsupported in this approach.
- Extensions: Recourse audits with different action sets can compare incentives from changing only causal features versus causal and manipulable ancillary features.The proposed comparisons can price incentives induced by a model in a target population.
- Extensions: Enumerating all minimal-cost actions makes flipset size a measure of recourse flexibility.The procedure lists actions until the integer program becomes infeasible, with each action altering a different feature subset.
- Scope and limitations: Abridged flipsets may fail after implementation because undisclosed actionable features can change unnoticed.Additional information can specify features that must not change or must change in a certain way.
- Scope and limitations: Consumers may not receive flipsets because model owners fear proprietary model theft.The paper suggests lower bounds on the number of actions needed to reconstruct a model as one possible safeguard-oriented response.
- Policy significance: Recourse formalizes human agency as the ability to alter model predictions in domains such as lending, hiring, and public services.The paper connects this concept to procedural fairness where no universal right to recourse exists.
- Policy significance: Periodic audits and per-person flipsets can check recourse, with empty flipsets detecting violations during deployment.The per-person approach can identify a failure on the first instance for which no actionable flipset is produced.
- Policy significance: A flipset can harm a borrower when changing the predicted outcome does not improve the true ability to repay.Actions that improve both predicted and true outcomes could instead benefit the consumer and model owner.
A OMITTED PROOFS
The omitted proofs establish when linear classifiers provide recourse and derive expressions for recourse cost using actionable-feature scores. They also show that unrestricted actionability or a single arbitrarily adjustable feature can guarantee recourse, while immutable features can prevent it.
- Recourse guarantees: If all features are actionable, every negatively classified individual has recourse by moving directly to any positively classified feature vector.The proof chooses an action a = x′ − x that transforms the individual’s vector into a positive-class vector.
- Recourse guarantees: An arbitrarily adjustable feature with a positive coefficient provides recourse to every negatively classified individual.Changing only that feature can make the linear score positive while leaving all other feature changes at zero.
- Recourse failures: An immutable feature can eliminate recourse even when all other features are actionable.With α < −1 and xd+1 = 1, the score is at most d − 1, so the individual cannot reach the positive class.
- Cost analysis: The optimal recourse cost for a negatively classified individual is expressed through the actionable-feature unit score and its sign.The derivation applies Lemma A.1 to expectation terms partitioned by whether the unit score is nonpositive or nonnegative.
- Cost analysis: The aggregate cost of recourse is decomposed by positive-class probability and conditional expectations over actionable-feature score signs.The proof rewrites costH−(f) and combines bounds for the relevant expectation terms.
B DISCRETIZATION GUARANTEES
The discretization guarantees state that a suitable grid preserves recourse feasibility and makes discretization-induced cost error controllable through grid refinement.
- Guarantees: Matching the continuous action space’s upper and lower bounds preserves the feasibility of recourse after discretization.The guarantee concerns real-valued features discretized onto a grid with the same bounds.
- Guarantees: Refining the discretization grid bounds and controls the maximum error in recourse cost.The paper presents a bound whose error decreases as the grid becomes finer.
B.1 Feasibility Guarantee
The feasibility guarantee shows that discretized integer programs preserve the original feasibility diagnosis when each bounded action interval’s endpoints are included in the discrete action set.
- Feasibility guarantee: Including both endpoints of every bounded action interval ensures the integer program is infeasible whenever the person lacks recourse.The result follows because the discretized maximum classifier value equals the maximum over the original bounded action set.
- Feasibility guarantee: The discretized optimization is infeasible when its maximum achievable classification value is negative.A negative maximum violates the integer program’s positive-class feasibility constraint, establishing the guarantee for the original action set.
B.2 Cost Guarantee
The cost guarantee bounds the recourse-cost difference caused by discretizing bounded feature actions, while a separate formulation avoids discretizing real-valued features but restricts costs and complicates action constraints.
- Cost guarantee: The maximum discretization error in recourse cost is bounded using the largest gap between adjacent feasible action values.The grid refinement measure is δj = maxk |aj,k+1 − aj,k|, and the proposition bounds cost differences in terms of these gaps.
- Cost guarantee: The cost guarantee assumes bounded feature space and compares minimum-cost actions over discrete and continuous feasible action sets.The paper defines cost(a;x) = cx · ∥a∥ and distinguishes the discrete set A(x) from the continuous set B(x).
- Non-discretized formulation: A continuous-variable integer-program formulation represents real-valued actions without discretization while retaining indicator variables for discrete-valued features.The formulation uses continuous aj variables for real-valued features and binary variables for discrete-valued features.
- Non-discretized formulation: The non-discretized formulation requires linear cost functions and becomes harder to optimize when feasible-action constraints require Big-M indicators.These constraints can produce weak LP relaxations and numerical instability.
C.1 Supporting Material for Section 4.1
The supporting material presents the credit feature/action overview alongside coefficient paths for ℓ1-penalized logistic regression models.
- Table 1 provides an overview of features and the action set for the credit task.
- Figure 8 shows coefficients of ℓ1-penalized logistic regression models across the full ℓ1-regularization path for credit.
C.2 Supporting Material for Section 4.2
The supporting material describes the givemecredit features and actions and reports performance for baseline and biased logistic regression models.
- Table 2 provides an overview of features and actions for givemecredit.
- 0.693 mean 10-CV AUC is reported for the baseline model, with 0.698 training AUC.
- 0.710 mean 10-CV test AUC is reported for the biased model, with 0.725 training AUC.
C.3 Supporting Material for Section 4.3
The supporting material describes the german features and actions and reports test and training AUC for its logistic regression model.
- Table 5 provides an overview of features and actions for german.
- 0.713 mean 10-CV test AUC and 0.749 training AUC are reported for the german logistic regression model.