TT-FSI: Scalable Faithful Shapley Interactions via Tensor-Train
The Faithful Shapley Interaction (FSI) index uniquely satisfies the faithfulness axiom among Shapley interaction indices, but computing FSI requires $O(d^\ell \cdot 2^d)$ time and existing implementations use $O(4^d)$ memory. We present TT-FSI, which exploits FSI's algebraic structure via Matrix Product Operators (MPO). Our main theoretical contribution is proving that the linear operator $v \mapsto \text{FSI}(v)$ admits an MPO representation with TT-rank $O(\ell d)$, enabling an efficient sweep algorithm with $O(\ell^2 d^3 \cdot 2^d)$ time and $O(\ell d^2)$ core storage an exponential improvement over existing methods. Experiments on six datasets ($d=8$ to $d=20$) demonstrate up to 280$\times$ speedup over baseline, 85$\times$ over SHAP-IQ, and 290$\times$ memory reduction. TT-FSI scales to $d=20$ (1M coalitions) where all competing methods fail.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Faith-Shap: The Faithful Shapley Interaction Index
Shapley values, which were originally designed to assign attributions to individual players in coalition games, have become a commonly used approach in explainable machine learning to provide attributions to input featur…
Computational EfficiencyInteraction Tensor SHAP
This study proposes Interaction Tensor SHAP (IT-SHAP), a tensor algebraic formulation of the Shapley Taylor Interaction Index (STII) that makes its computational structure explicit. STII extends the Shapley value to high…
Tractable Shapley Values and Interactions via Tensor Networks
We show how to replace the O(2^n) coalition enumeration over n features behind Shapley values and Shapley-style interaction indices with a few-evaluation scheme on a tensor-network (TN) surrogate: TN-SHAP. The key idea i…
TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions
Shapley values are a widely used tool for attributing importance and interactions among input variables in black-box models, but their computation involves a function defined over an exponentially large space of subsets.…
Beyond Additive Decompositions: Interpretability Through Separability
Interpretable machine learning requires models that are accurate and structurally faithful to the data. Existing explainability methods rely heavily on additive representations (e.g., Generalized Additive Models (GAMs), …
Interpretable Machine Learning