Counterfactual explanations are usually obtained by identifying the smallest
change made to an input to change a prediction made by a fixed model (hereafter
called sparse methods). Recent work, however, has revitalized an old insight:
there often does not exist one superior solution to a prediction problem with
respect to commonly used measures of interest (e.g. error rate). In fact, often
multiple different classifiers give almost equal solutions. This phenomenon is
known as predictive multiplicity (Breiman, 2001; Marx et al., 2019). In this
work, we derive a general upper bound for the costs of counterfactual
explanations under predictive multiplicity. Most notably, it depends on a
discrepancy notion between two classifiers, which describes how differently
they treat negatively predicted individuals. We then compare sparse and data
support approaches empirically on real-world data. The results show that data
support methods are more robust to multiplicity of different models. At the
same time, we show that those methods have provably higher cost of generating
counterfactual explanations under one fixed model. In summary, our theoretical
and empiricaln results challenge the commonly held view that counterfactual
recommendations should be sparse in general.

本文研究了如何以更低的成本生成对于多个分类器表现相等情况下对于分类结果的对抗讲解，在理论和实证研究中，对于解释成本与解释鲁棒性进行了概念的阐述，发现基于数据支持的方法相较于仅仅基于稀疏方法更加鲁棒，但是它们在成本方面会有所提高。因此，缘由推荐为稀疏方法在多分类器表现差异大的情况下不宜一概而论。