PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithmic recourse under imperfect causal knowledge: a probabilistic approach

Amir-Hossein Karimi, Julius von Kügelgen, Bernhard Schölkopf, Isabel Valera

arXiv:2006.06831v3cs.LGcs.AIstat.ML

TL;DR

Algorithmic recourse should account for causal relationships, but reliable guarantees require structural equations that are generally unknown. The paper proves this limitation and proposes two probabilistic recourse approaches, finding more reliable recommendations than non-probabilistic baselines under imperfect causal knowledge.

  • Problem

    Counterfactual explanations do not directly provide actionable recommendations, while causal recourse requires the generally unavailable true structural equations.

  • Method

    The paper averages over additive Gaussian SCMs for individualized counterfactual recourse and estimates intervention effects in similar individuals for subpopulation-based recourse.

  • Results

    The proposed probabilistic approaches produce more reliable recommendations than point-based baselines, which can be invalid or more costly under imperfect model assumptions.

  • Takeaways & Limitations

    Subpopulation-based recourse is appropriate when additive-noise assumptions do not hold, while probabilistic methods allow validity-cost trade-offs through γ_LCB.

  • Takeaways & Limitations

    The methods assume a known causal graph and causal sufficiency, and partial or confounded graphs require restricting actions to identifiable interventions.

Abstract

from arXiv · show

Recent work has discussed the limitations of counterfactual explanations to recommend actions for algorithmic recourse, and argued for the need of taking causal relationships between features into consideration. Unfortunately, in practice, the true underlying structural causal model is generally unknown. In this work, we first show that it is impossible to guarantee recourse without access to the true structural equations. To address this limitation, we propose two probabilistic approaches to select optimal actions that achieve recourse with high probability given limited causal knowledge (e.g., only the causal graph). The first captures uncertainty over structural equations under additive Gaussian noise, and uses Bayesian model averaging to estimate the counterfactual distribution. The second removes any assumptions on the structural equations by instead computing the average effect of recourse actions on individuals similar to the person who seeks recourse, leading to a novel subpopulation-based interventional notion of recourse. We then derive a gradient-based procedure for selecting optimal recourse actions, and empirically show that the proposed approaches lead to more reliable recommendations under imperfect causal knowledge than non-probabilistic baselines.

1 Introduction

Algorithmic recourse requires actionable recommendations that respect causal relationships, but the true structural equations are generally unavailable. The paper therefore develops probabilistic approaches for recourse under limited causal knowledge.

  • Motivation: Counterfactual explanations identify nearby feature values that change predictions but do not directly specify actions individuals can perform.Prior approaches also treat features as independently manipulable, ignoring causal relationships between them.
  • Causal recourse: Causal recourse frames actions as interventions and seeks a minimal, actionable set that guarantees a more favourable outcome.This formulation requires computing counterfactuals in the true underlying structural causal model.
  • Causal uncertainty: Complete knowledge of the true structural equations is generally unavailable, and assumptions about their form are not testable in many applications.Expert knowledge may provide a causal diagram without identifying the structural equations.
  • Contributions: The paper proposes one approach averaging over additive Gaussian structural causal models and another estimating intervention effects for similar individuals without assumptions on structural-equation form.The approaches target individualized counterfactual and subpopulation-based interventional recourse, respectively.
  • Empirical findings: Experiments show that probabilistic approaches provide more reliable recourse than point estimates, which can recommend invalid actions or achieve recourse only at higher cost.Subpopulation-based recourse is identified as preferable when additive-noise assumptions do not hold.

2 Background and related work

The paper introduces structural causal models, interventions, and counterfactuals, then contrasts causal algorithmic recourse with distance-based counterfactual explanations. Causal recourse optimizes actionable interventions rather than merely finding similar feature configurations.

  • Structural causal models: An SCM represents each variable as a function of its causal parents and an unobserved noise variable, with a causal graph encoding parent-to-child relationships.Independent noise variables correspond to causal sufficiency.
  • Interventions: An intervention do(X_I = θ) replaces the structural equations for the intervened variables and induces a distribution over the remaining variables.The resulting interventional distribution comes from the manipulated SCM.
  • Counterfactuals: Counterfactual distributions are computed by abducting background variables, performing the intervention, and predicting under the modified structural equations.The three stages are abduction, action, and prediction.
  • Illustrative setting: The running example uses a binary probabilistic classifier for loan approval, with h(x) ≥ 0.5 denoting approval and h(x) < 0.5 denial.The recourse question concerns what a denied individual would need to change for a more favourable prediction.
  • Counterfactual explanations and recourse: Nearest counterfactual explanations minimize distance to a different-prediction instance, while algorithmic recourse optimizes the cost of actions available to the individual.A nearby counterfactual does not itself tell the person what actions would produce that outcome.
  • Causal algorithmic recourse: Causal recourse treats actions as interventions and uses structural counterfactuals to select a minimum-cost action whose classifier output meets the approval threshold.The formulation optimizes over intervention targets and values subject to h(x_SCF(a)) ≥ 0.5.

3 Negative result: no recourse guarantees for unknown structural equations

The paper shows that empirical data cannot generally identify the structural equations needed for guaranteed causal recourse. It then introduces probabilistic approaches for unknown structural equations while assuming the causal graph is known.

  • Non-identifiability: Two SCMs can imply identical observational and interventional distributions while predicting different structural counterfactuals.Thus, empirical data cannot distinguish the models relevant to counterfactual recourse.
  • Constructive example: In the example, observing x_F = (1, 0, 0) and intervening to set X1 = 0 yields counterfactuals (0, 0, 0) and (0, 0, K) under the two indistinguishable SCMs.The disagreement occurs despite matching observational and interventional distributions.
  • Negative result: Unless intervened variables have no descendants, recourse can generally be guaranteed only when the true structural equations are known.The proposition holds regardless of the amount or type of available data.
  • Response to the negative result: The paper proposes two approaches under unknown structural equations: an additive-Gaussian counterfactual model and a subpopulation-based intervention-effect model.Both approaches assume that the causal graph is known.

4 Individualised algorithmic recourse via (probabilistic) counterfactuals

This section models uncertainty in structural equations to obtain counterfactual outcome distributions for individualised probabilistic recourse. Under additive Gaussian noise, Gaussian-process Bayesian averaging supports probability-based recourse constraints.

  • A learned SCM can produce wrong counterfactuals because finite data and structural-equation misspecification introduce model uncertainty.The probabilistic approach addresses this limitation rather than relying on a single point estimate.
  • The GP-SCM assumes additive Gaussian noise and places Gaussian-process priors over the structural functions.This yields a family of nonlinear structural equations rather than one fixed fitted function.
  • GP uncertainty is used to average over structural functions and obtain a posterior over noise values for counterfactual inference.The resulting uncertainty is incorporated into the counterfactual distribution through posterior inference and ancestral sampling.
  • The counterfactual distribution is generated by ancestrally sampling descendants of intervention targets using the posterior noise distribution.Descendants are evaluated according to the causal graph after the intervention.
  • Probabilistic recourse replaces a hard prediction-change constraint with an expected classifier-output constraint over counterfactual outcomes.The optimisation minimises cost subject to the expected output exceeding a threshold.
  • The lower-confidence-bound threshold becomes more conservative as γLCB increases, while γLCB = 0 requires only at least 50% decision-boundary-crossing probability.The threshold may depend on the action through the counterfactual-output variance.

5 Subpopulation-based algorithmic recourse via interventions and CATEs

This section avoids assumptions about individual structural equations by evaluating interventions over a subpopulation similar to the person seeking recourse. The interventional distribution is identified from observational data and estimated with latent-variable density models.

  • The subpopulation approach removes assumptions about structural equations and evaluates intervention effects on individuals sharing characteristics with the factual subject.It therefore targets average effects in a similar subpopulation rather than an individualised counterfactual distribution.
  • Its recourse optimisation takes the expectation over the corresponding interventional distribution rather than the counterfactual distribution.The objective remains cost minimisation under an expected classifier-output constraint.
  • The interventional distribution generally differs from the conditional distribution because observational spurious correlations may not transfer after intervention.The paper gives a causal-graph example where conditioning on an additional variable changes the observational relation without matching intervention semantics.
  • Under causal sufficiency, the relevant interventional distribution is identifiable from the observational distribution.This enables computation of the subpopulation-based recourse objective from observational data.
  • For general graphs and intervention sets, the method estimates stable conditional causal Markov kernels to compute interventional expectations.The implementation uses latent-variable implicit density models, while other conditional-density estimators are possible.
  • The CVAE implementation learns encoder and decoder parameters by variational inference and evidence-lower-bound maximisation.Its learned decoder collection can be interpreted as an approximate SCM.
  • The CVAE family may not identify the true SCM without additional assumptions, and exact posterior inference over latent variables is intractable.Consequently, the counterfactual interpretation of approximate posterior sampling remains unclear.

6 Solving the probabilistic-recourse optimisation problems

This section solves probabilistic recourse optimisation by Monte Carlo estimation and differentiable gradient-based search. The gradient method handles continuous intervention values while considering intervention targets in parallel.

  • Both recourse formulations differ only in whether their expectation uses a counterfactual or interventional distribution.Both distributions arise after applying actions of the form do(XI = θ).
  • Monte Carlo sampling approximates the expectations required by the probabilistic constraints.Samples are drawn from the relevant counterfactual or interventional distribution.
  • Brute-force search evaluates feasible actions, estimates constraints, and selects the cheapest satisfying action, but can be computationally prohibitive and discretisation-sensitive.Discretisation may also yield suboptimal interventions.
  • The gradient-based method considers intervention-target choices in parallel and efficiently optimises intervention values for each target set.Target selection remains combinatorial, whereas continuous intervention values are handled by gradients for differentiable classifiers.
  • The constrained problem is rewritten with a Lagrangian and solved as a saddle-point problem using stochastic gradient descent.The method differentiates through reparameterised GP-SCM and CVAE distributions.
  • Descendant samples are computed in topological order, using either CVAE decoders or Gaussian reparameterisation for GP-SCMs.A similar gradient estimator handles the variance term when γLCB ≠ 0.

7 Experimental results

Experiments on synthetic and semi-synthetic loan-approval SCMs show that probabilistic recourse is more robust to structural-model misspecification and supports a validity–cost trade-off.

  • The experiments compare point-based baselines with GP-SCM, CVAE, CATE, and oracle recourse methods on synthetic and semi-synthetic data.They evaluate cost, validity under the true oracle SCM, and a lower confidence bound for probabilistic methods.
  • Synthetic tests cover linear, nonlinear additive-noise, and multimodal non-additive SCMs to assess robustness to structural-equation assumptions.
  • Point-based methods perform well when their assumptions match the SCM but lose validity under misspecification, whereas probabilistic methods remain competitive across settings.CATECVAE achieves perfect validity as the only non-oracle method on the challenging non-additive SCM.
  • On the seven-variable loan-approval SCM, increasing γLCB raises validity toward oracle performance and can outperform point-based approaches.Lower γLCB values reduce both validity and cost, especially for CATE methods.
  • The seven-variable experiments use gradient-based optimisation for logistic classifiers and brute-force discretisation for the non-differentiable random forest.Table 2 reports averages and standard deviations over 100 runs with γLCB = 2.5.

8 Discussion

The discussion treats a known causal graph and causal sufficiency as baseline assumptions for causal reasoning from observational data, while distinguishing individualised from subpopulation-based recourse.

  • The framework assumes a known causal graph and causal sufficiency, described as the minimal assumptions for causal reasoning from observational data alone.Instrumental variables or experimental data may help relax these assumptions.
  • With a partial graph or known confounding, recourse actions must be restricted to interventions that remain identifiable.The paper leaves latent-variable, proxy-variable, and causal-effect-bound approaches for future work.
  • Counterfactual recourse fixes background variables, whereas interventional recourse allows them to vary when estimating effects for a subpopulation.

9 Conclusion

The paper shows that guaranteed recourse requires perfect knowledge of the underlying SCM, then proposes probabilistic individual-level and subpopulation-based alternatives for imperfect causal knowledge.

  • The GP-based approach averages over additive Gaussian SCMs to approximate an individual’s counterfactual outcome distribution.
  • The CVAE-based approach uses conditional average treatment effects for a subpopulation similar to the person seeking recourse, assuming only the causal graph is known.
  • Experiments find the probabilistic approaches more robust than point-estimate SCM methods and show that γLCB trades off validity against cost.

Broader Impact

The paper frames causal algorithmic recourse as guidance for overcoming unfavourable automated decisions, while emphasizing practical robustness and broader ethical boundaries.

  • Algorithmic recourse aims to give individuals efficient, low-cost recommendations for recovering from unfavourable automated decisions.
  • The proposed methods avoid assumptions beyond the causal graph and use γLCB to trade robustness against the effort required for recourse.
  • Because the classifier is treated as given, the framework does not directly address discriminatory or biased decision rules.Successful recourse examples might help debias a system over time, according to the paper.
  • The framework could also be used to game protective systems, although specifying a causal graph generally requires domain understanding.

B Additional results

Additional experiments largely confirm the main findings, while further analysis shows that causal models are generally not identifiable from observational information alone and describes CVAE training details.

  • Additional experimental results: Varying γLCB with MLP and random-forest classifiers exposes a validity–cost trade-off for probabilistic recourse methods.Random-forest optimisation is restricted to the brute-force approach because the classifier is non-differentiable.
  • Additional experimental results: CATE approaches select intervention targets more predictably because they are less sensitive to model assumptions under imperfect causal knowledge.On three synthetic datasets, individual-based methods deviate from their individual-level oracle in intervention-variable selection.
  • Additional experimental results: The brute-force 20-bin discretization experiments report relative trends matching those in Table 1.Results average over 100 runs and 100 Monte Carlo samples with γLCB = 2.
  • SCM identifiability: Even with a known causal graph, conditional distributions alone do not uniquely determine structural equations without further assumptions.The construction shifts noise variables and structural equations while preserving the observational distribution and causal graph.
  • SCM identifiability: The CVAE-SCM setting assumes isotropic fixed-dimensional Gaussian noise and feedforward-neural-network structural equations, but identifiability results are unavailable.The paper relates this setting to nonlinear extensions of identifiable linear Gaussian models and leaves further investigation for future work.
  • CVAE implementation: CVAE structural models are trained using amortised variational inference, ELBO optimisation, Monte Carlo reparameterisation, and architecture or hyperparameter selection.Encoder and decoder parameters are learned simultaneously, with separate variable-wise pairs trained in parallel.

E.1 Specification of SCMs used in our experiments

The experiments use synthetic and semi-synthetic SCMs with specified structural equations, noise distributions, label-generation processes, and gradient-based variance estimation.

  • Label generation: Training labels for the semi-synthetic data are used only to train a new classifier and are then disregarded in favor of that classifier.The trained classifier may be logistic regression, a multilayer perceptron, or a random forest.
  • Three-variable synthetic SCMs: The experimental SCMs include three-variable linear, nonlinear additive-noise, and non-additive models sharing a causal graph.These settings test robustness to different assumptions about structural-equation form.
  • Seven-variable loan SCM: The semi-synthetic loan SCM encodes relationships involving gender, age, loan amount, duration, savings, income, and education.Examples include loan duration increasing with amount, income increasing with age, and education initially increasing before saturation.
  • Seven-variable loan SCM: The loan SCM specifies distributions and equations for gender, age, loan duration, debt, and income, with variables often centered as deviations from means.Age, for example, is centered around a mean of 35.
  • Gradient estimation: The gradient procedure estimates the derivative of classifier-output standard deviation under an interventional or counterfactual distribution.Reparameterisation and Monte Carlo samples enable differentiation through the expectation and variance calculations.
Loading 2006.06831v3…