Even-if Explanations: Formal Foundations, Priorities and Complexity
Authors: Gianvincenzo Alfano, Sergio Greco, Domenico Mandaglio, Francesco Parisi, Reza Shahbazian, Irina Trubitsyna
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We formally introduce the concepts of semifactual over three classes of models: (i) perceptrons (ii) free binary decision diagrams (FBBDs), and (iii) multi-layer perceptrons (MLP), intuitively encoding local post-hoc explainable queries within the even-if thinking setting. We investigate the computational complexity of interpretability problems concerning semifactuals, showing that they are not more difficult than analogous problems related to counterfactuals (Barceló et al. 2020). We introduce a framework that empowers users to prioritize explanations according to their subjective preferences. We investigate the complexity of several interpretability problems related to best semifactuals and best counterfactuals. Table 1 summarizes our complexity results. Finally, focusing on a restricted yet expressive class of feature preferences, we identify tractable cases for which we propose algorithms for their computation. |
| Researcher Affiliation | Academia | Department of Informatics, Modeling, Electronics and System Engineering, University of Calabria, Italy EMAIL EMAIL |
| Pseudocode | Yes | Algorithm 1: Computing a (best) semifactual for perceptrons Algorithm 2: Computing a (best) semifactual for FBDDs |
| Open Source Code | No | No explicit statement or link for open-source code for the methodology described in this paper is provided. The paper discusses future work on adapting algorithms and investigating different preference criteria, implying current code is not released. |
| Open Datasets | No | The paper uses illustrative examples such as a "hiring scenario" (Example 1) to explain concepts but does not refer to any specific publicly available datasets used for empirical experimentation or evaluation. It primarily focuses on theoretical analysis. |
| Dataset Splits | No | No datasets are used for empirical experimentation or evaluation, therefore no dataset splits are mentioned or provided in the paper. |
| Hardware Specification | No | The paper focuses on theoretical foundations, computational complexity, and algorithms. It does not describe any empirical experiments, and consequently, no specific hardware specifications are mentioned for running such experiments. |
| Software Dependencies | No | The paper focuses on theoretical foundations and algorithms. It does not provide details of any specific ancillary software components or their version numbers that would be required to replicate experiments. |
| Experiment Setup | No | The paper is theoretical in nature, focusing on formal foundations, complexity analysis, and algorithms. It does not describe empirical experiments, and therefore, no specific experimental setup details such as hyperparameters or training configurations are provided. |