Attribution-based Explanations that Provide Recourse Cannot be Robust
Different users of machine learning methods require different explanations,
depending on their goals. To make machine learning accountable to society, one
important goal is to get actionable options for recourse, which allow an
affected user to change the decision $f(x)$ of a machine learning system by
making limited changes to its input $x$. We formalize this by providing a
general definition of recourse sensitivity, which needs to be instantiated with
a utility function that describes which changes to the decisions are relevant
to the user. This definition applies to local attribution methods, which
attribute an importance weight to each input feature. It is often argued that
such local attributions should be robust, in the sense that a small change in
the input $x$ that is being explained, should not cause a large change in the
feature weights. However, we prove formally that it is in general impossible
for any single attribution method to be both recourse sensitive and robust at
the same time. It follows that there must always exist counterexamples to at
least one of these properties. We provide such counterexamples for several
popular attribution methods, including LIME, SHAP, Integrated Gradients and
SmoothGrad. Our results also cover counterfactual explanations, which may be
viewed as attributions that describe a perturbation of $x$. We further discuss
possible ways to work around our impossibility result, for instance by allowing
the output to consist of sets with multiple attributions. Finally, we
strengthen our impossibility result for the restricted case where users are
only able to change a single attribute of x, by providing an exact
characterization of the functions $f$ to which impossibility applies.