Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis

Abstract

Being able to provide counterfactual interventions - sequences of actions we would have had to take for a desirable outcome to happen - is essential to explain how to change an unfavourable decision by a black-box machine learning model (e.g., being denied a loan request). Existing solutions have mainly focused on generating feasible interventions without providing explanations on their rationale. Moreover, they need to solve a separate optimization problem for each user. In this paper, we take a different approach and learn a program that outputs a sequence of explainable counterfactual actions given a user description and a causal graph. We leverage program synthesis techniques, reinforcement learning coupled with Monte Carlo Tree Search for efficient exploration, and rule learning to extract explanations for each recommended action. An experimental evaluation on synthetic and real-world datasets shows how our approach generates effective interventions by making orders of magnitude fewer queries to the black-box classifier with respect to existing solutions, with the additional benefit of complementing them with interpretable explanations.

References in corpus (14)

• Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations
• Actionable Recourse in Linear Classification
• The Hidden Assumptions Behind Counterfactual Explanations and Principal Reasons
• Local Rule-Based Explanations of Black Box Decision Systems
• Multi-Objective Counterfactual Explanations
• Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking
• Model-Agnostic Counterfactual Explanations for Consequential Decisions
• Algorithmic recourse under imperfect causal knowledge: a probabilistic approach
• Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis
• Learning Compositional Neural Programs with Recursive Tree Search and Planning
• Consequence-aware Sequential Counterfactual Generation
• Decisions, Counterfactual Explanations and Strategic Behavior
• Extracting Incentives from Black-Box Decisions
• Learning compositional programs with arguments and sampling

Cited by in corpus (2)

• Exploiting Preference Elicitation in Interactive and User-centered Algorithmic Recourse: An Initial Exploration
• Time Can Invalidate Algorithmic Recourse