Research map / Learning theory and algorithms / Prediction and decision losses

Even-if Explanations: Formal Foundations, Priorities and Complexity

AAAI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Counterfactual explanations and recourse · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formalizes semifactual ("even-if") explanations for binary perceptrons, FBDDs and MLPs, analyzes their complexity against counterfactuals, and adds a preference-based framework with polynomial algorithms for linear preferences on perceptrons and FBDDs.

Problem

Local post-hoc explanations for binary classifiers have focused on counterfactuals ("if only"), with little formal treatment of semifactuals ("even-if"), and no way for users to prioritize which features should change in explanations.

Approach

Defines semifactuals as maximum-distance instances keeping the same prediction, studies complexity of MCA/cb-MCR/cb-MCA queries across model classes, and introduces a BCMp preference framework (preference rules with degree-based semantics, akin to Answer Set Optimization) so that best semifactuals and counterfactuals are selected according to user feature preferences.

Key results

• MCA (maximum change allowed) is in PTIME for perceptrons and FBDDs and NP-complete for MLPs, matching the complexity of MCR for counterfactuals.
• cb-MCR and cb-MCA (checking best explanations) are coNP-complete for MLPs and in coNP for FBDDs and perceptrons.
• cbl-MCR and cbl-MCA (linear preferences) are in PTIME for perceptrons and FBDDs, with polynomial algorithms provided.

Limitations

• Restricted to binary features and inputs in {0,1}^n
• Polynomial algorithms only for perceptrons/FBDDs and a single linear preference; MLP case remains hard
• Interpretability notion depends on the chosen set of queries; counting queries left to future work

Experimental setup

Metrics: computational complexity classes (P, NP-complete, coNP-compl

Baselines: MCR complexity results (counterfactuals)

Builds on: counterfactual explanations Answer Set Optimization Minimum Change Required complexity results

Closest papers by meaning

• Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable? (ICLR 2025 · similarity 0.88)
• Local vs. Global Interpretability: A Computational Complexity Perspective (ICML 2024 · similarity 0.87)
• Generating Likely Counterfactuals Using Sum-Product Networks (ICLR 2025 · similarity 0.87)
• Navigating the Maze of Explainable AI: A Systematic Approach to Evaluating Methods and Metrics (NeurIPS 2024 · similarity 0.86)
• DiCoFlex: Model-Agnostic Diverse Counterfactuals with Flexible Control (NeurIPS 2025 · similarity 0.86)
• Towards Unifying Evaluation of Counterfactual Explanations: Leveraging Large Language Models for Human-Centric Assessments (AAAI 2025 · similarity 0.85)