11 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…
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…
Additive Models Explained: A Computational Complexity Approach
Shahaf Bassan, Michal Moshkovitz, Guy Katz
Generalized Additive Models (GAMs) are commonly considered *interpretable* within the ML community, as their structure makes the relationship between inputs and outputs relatively…