A model-agnostic and data-independent tabu search algorithm to generate counterfactuals for tabular, image, and text data

The growing prevalence of artificial decision systems has prompted a keen interest in their efficiency, yet this progress is accompanied by their inherent complexity. This poses a significant challenge for various domains, including operational research, where decisions hold crucial influence over outcomes and thus must not remain undisclosed. Counterfactual explanations are greatly remarked as a simple (to understand) yet efficient way to explain the decisions made by a machine learning model by finding a minimal set of changes required to change the prediction outcome for a specific instance. We, then, present a novel algorithmic approach, called CFNOW, which implements a modular, fast, two-step process using tabu search, a well-known metaheuristic framework, to find counterfactuals for multiple data types (tabular, image, and text) with high efficiency. We run an extensive benchmark study with more than 5000 factual points from 25 datasets to demonstrate that CFNOW can generate high-quality counterfactual results in terms of metrics such as speed, coverage, distance, and sparsity, surpassing the state-of-the-art. These characteristics, associated with the simple code implementation, may aid embedding explainability to complex models which are often necessary for compliance requirements.