Synthesizing Action Sequences for Modifying Model Decisions

Goutham Ramakrishnan, Yun Chan Lee, Aws Albarghouthi

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:

  1. 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.
  2. 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.
Efficiency comparison of vanilla, objective-based, and gradient-based score 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.

Comparison of search methods across datasets and sequence lengths.

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

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.
BibTeX
@inproceedings{ramakrishnan2020synthesizing,
  author = {Goutham Ramakrishnan and Yun Chan Lee and Aws Albarghouthi},
  title = {{Synthesizing Action Sequences for Modifying Model Decisions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5996},
}
Figure