GraCo: Towards GRammar Assisted COunterfactuals

Counterfactual explanations effectively interpret model decisions by identifying input modifications that lead to different outputs. However, generating realistic and actionable counterfactuals is challenging due to the lack of methodologies that effectively capture complex feature relationships and user-imposed constraints. This study introduces GraCo, a novel counterfactual generation (CG) method driven by Grammatical Evolution. GraCo automatically incorporates feature-domain knowledge and user preferences to generate plausible and actionable counterfactuals. We evaluate its effectiveness through empirical validation against state-of-the-art methods across multiple datasets. We propose a goodness metric for CG that accounts for class probability shifts and the differences between the counterfactual and the original input. GraCo achieves an average goodness score of 0.6231 across four datasets, outperforming all the compared approaches.