  Work in Counterfactual Explanations tends to focus on the principle of "the
closest possible world" that identifies small changes leading to the desired
outcome. In this paper we argue that while this approach might initially seem
intuitively appealing it exhibits shortcomings not addressed in the current
literature. First, a counterfactual example generated by the state-of-the-art
systems is not necessarily representative of the underlying data distribution,
and may therefore prescribe unachievable goals(e.g., an unsuccessful life
insurance applicant with severe disability may be advised to do more sports).
Secondly, the counterfactuals may not be based on a "feasible path" between the
current state of the subject and the suggested one, making actionable recourse
infeasible (e.g., low-skilled unsuccessful mortgage applicants may be told to
double their salary, which may be hard without first increasing their skill
level). These two shortcomings may render counterfactual explanations
impractical and sometimes outright offensive. To address these two major flaws,
first of all, we propose a new line of Counterfactual Explanations research
aimed at providing actionable and feasible paths to transform a selected
instance into one that meets a certain goal. Secondly, we propose FACE: an
algorithmically sound way of uncovering these "feasible paths" based on the
shortest path distances defined via density-weighted metrics. Our approach
generates counterfactuals that are coherent with the underlying data
distribution and supported by the "feasible paths" of change, which are
achievable and can be tailored to the problem at hand.
