13 papers
Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks
David Boetius, Shahaf Bassan, Guy Katz +2
Shapley additive explanations (SHAP) are widely recognised as computationally intractable for neural networks, since they induce an exponential search space over the input features…
SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
Reda Marzouk, Shahaf Bassan, Guy Katz
Although Shapley additive explanations (SHAP) can be computed in polynomial time for simple models like decision trees, they unfortunately become NP-hard to compute for more expres…
FAME: Formal Abstract Minimal Explanation for Neural Networks
Ryma Boumazouza, Raya Elsaleh, Melanie Ducoffe +2
We propose FAME (Formal Abstract Minimal Explanations), a new class of abductive explanations grounded in abstract interpretation. FAME is the first method to scale to large neural…
Unifying Formal Explanations: A Complexity-Theoretic Perspective
Shahaf Bassan, Xuanxiang Huang, Guy Katz
Previous work has explored the computational complexity of deriving two fundamental types of explanations for ML model predictions: (1) *sufficient reasons*, which are subsets of i…
Provably Explaining Neural Additive Models
Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner +4
Despite significant progress in post-hoc explanation methods for neural networks, many remain heuristic and lack provable guarantees. A key approach for obtaining explanations with…
Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees
Itamar Hadad, Guy Katz, Shahaf Bassan
*Automated circuit discovery* is a central tool in mechanistic interpretability for identifying the internal components of neural networks responsible for specific behaviors. While…