Introduction
As machine learning models increasingly automate consequential decisions such as mortgage underwriting and job screening, the need for transparency and "recourse" has become paramount. While existing interpretability methods like LIME or SHAP identify influential features, they often fail to provide actionable paths for users to reverse a negative outcome. Furthermore, traditional counterfactual explanations frequently suggest unrealistic changes, such as altering one's age or marital status. This paper proposes a framework to generate realistic, low-cost sequences of real-world actions—like "increase savings by $1,000"—to achieve a desired model decision.
Methodology: Recourse as Program Synthesis
The authors frame the search for actionable feedback as a program synthesis problem. They define a Domain-Specific Language (DSL) where each action is associated with a cost function and specific preconditions (e.g., age requirements). The approach consists of two main components:
- Discrete Search: The system explores the space of possible action sequences. To manage the combinatorial complexity, the authors introduce score functions—Vanilla (breadth-first), Objective-based, and Gradient-based—to prioritize the most promising sequences.
- Continuous Optimization: For a given sequence, the system determines optimal parameters (the "how much") by adapting Carlini-Wagner adversarial attack techniques. To handle non-differentiable Boolean preconditions, they employ a "relaxation" trick, converting hard constraints into continuous penalty functions.
Experimental Evaluation
The framework was evaluated across four distinct domains:
- German Credit Data: Loan risk prediction (20 features, 7 actions).
- Adult Dataset: Income level prediction (14 features, 6 actions).
- Fannie Mae Loan Performance: Mortgage application evaluation (21 features, 5 actions).
- Quick, Draw!: A deep CNN for sketch recognition, where the goal was to modify a drawing to change its classification (e.g., to "cat") by adding a single stroke.
Key Results and Insights
The algorithm demonstrated high effectiveness, finding valid action sequences for 100% of instances in the German Credit model and 90% in the Adult dataset. Performance on the Fannie Mae model was lower (62%), likely due to the complexity of the underlying deep neural network.
A critical finding was the efficiency of the search strategies. While Vanilla breadth-first search is sufficient for short sequences (1-2 actions), Gradient-based and Objective-based score functions are significantly more effective at discovering deeper, more complex solutions (3-4 actions). The use of the model's loss gradient to guide the search (score_g) proved particularly potent for navigating high-dimensional spaces.
Conclusion and Future Work
By treating recourse as a synthesized program, this work provides a path toward more realistic and complex feedback for algorithmic decisions. However, the method currently requires white-box access to the model for gradient calculations and depends on a well-defined DSL of actions. Future research may explore black-box adaptations and the potential for malicious "gaming" of such systems, balanced against the ethical necessity of providing legitimate recourse.
Summary updated