Abstract
When a model makes a consequential decision, e.g., denying someone a loan, it needs to additionally generate actionable, realistic feedback on what the person can do to favorably change the decision. We cast this problem through the lens of program synthesis, in which our goal is to synthesize an optimal (realistically cheapest or simplest) sequence of actions that if a person executes successfully can change their classification. We present a novel and general approach that combines search-based program synthesis and test-time adversarial attacks to construct action sequences over a domain-specific set of actions. We demonstrate the effectiveness of our approach on a number of deep neural networks.
Introduction
As predictive models increasingly handle consequential decisions such as mortgage approvals, hiring, and healthcare, the demand for transparency has grown. However, traditional "explainable AI" (XAI) methods often focus on feature attribution—identifying which features (e.g., "debt-to-income ratio") most influenced a decision. While informative, attribution is often insufficient for the end-user. Knowing that "marital status" was a factor is frustrating if that feature is unactionable.
This paper addresses the need for actionable recourse: specific, realistic steps a person can take to flip an unfavorable algorithmic decision. The authors propose a framework to find the "cheapest" sequence of real-world actions (e.g., "increase down payment by $1,000") that changes the model's output, while respecting domain-specific constraints and costs.
Methodology
The authors frame the search for recourse as a program synthesis problem over a Domain-Specific Language (DSL) of actions.
DSL and Search Strategy
A domain expert defines a set of possible actions, each associated with a cost function and preconditions (e.g., a credit score cannot exceed a maximum threshold). The search for the optimal recourse is split into two components:
- Discrete Search: An enumerative search explores the space of action sequences (e.g., Action A followed by Action B).
- Continuous Optimization: For a given sequence, the framework employs a relaxation of the Carlini-Wagner (C&W) adversarial attack to determine the optimal parameters for those actions (e.g., the exact amount of a payment increase).
Differentiable Relaxation and Guided Search
To ensure efficiency, Boolean preconditions are transformed into continuous, differentiable penalty functions. This allows the use of gradient-based optimizers like Adam to solve for action parameters. Furthermore, the authors introduce a "gradient-based score" to prioritize action sequences. By analyzing an action's "footprint"—the features it modifies—the search prioritizes actions that align with the model's steepest gradients, significantly accelerating convergence on complex models.
Experimental Setup
The framework was evaluated across four distinct tasks ranging from tabular financial data to high-dimensional image data.
As shown in the table above, the models varied significantly in depth and complexity, from simple 2-layer networks to a 5-layer network for mortgage performance and a 1D convolutional network for drawing recognition.
Results and Discussion
The proposed approach demonstrated high effectiveness across the test cases:
- Success Rates: The algorithm achieved a 100% success rate in finding valid recourse for the German Credit model and 90% for the Adult dataset. Success dropped to 62% for the deeper Fannie Mae model, highlighting challenges with local minima in complex optimization landscapes.
- Efficiency: The gradient-based scoring function proved essential for longer action sequences, outperforming standard breadth-first search.
- Qualitative Realism: In the "Quick, Draw!" task, the framework successfully modified a sketch (e.g., turning a "non-cat" into a "cat") by adding minimal, realistic lines, proving its applicability to high-dimensional data.
Limitations and Future Work
The current method is a "white-box" approach requiring access to model gradients. Future research may explore black-box settings. Additionally, the authors note the potential for "strategic gaming," where users manipulate features solely to bypass the model. Addressing this may require "strategic classification" techniques to ensure models remain robust against such manipulation.
Summary updated