TT-FSI: Scalable Faithful Shapley Interactions via Tensor-Train
By: Ungsik Kim, Suwon Lee
Potential Business Impact:
Makes AI understand how its decisions work.
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.
Similar Papers
Interaction Tensor Shap
Machine Learning (CS)
Explains how many parts work together in smart programs.
Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks
Machine Learning (CS)
Explains how AI understands complex connections.
Privacy-Preserving Feature Valuation in Vertical Federated Learning Using Shapley-CMI and PSI Permutation
Cryptography and Security
Helps train AI without sharing private user data.