用张量网络加速精准交互效应计算，规模突破现有方法极限。
TT-FSI: Scalable Faithful Shapley Interactions via Tensor-Train
- 利用矩阵乘积算子重构福尔克希交互指数的代数结构
- 在20维特征下实现100万联盟的高效计算，速度提升280倍
- 适合需要高精度特征交互分析的大规模模型可解释性研究
福尔克希交互指数（FSI）是唯一满足忠实性公理的交互效应度量，但其计算复杂度高达$O(d^\l \cdot 2^d)$，现有实现内存需求达$O(4^d)$。本文提出TT-FSI，通过矩阵乘积算子（MPO）挖掘FSI的代数结构。理论证明线性映射$ v \mapsto \text{FSI}(v) $存在TT秩为$O(\ell d)$的MPO表示，从而实现$O(\ell^2 d^3 \cdot 2^d)$时间与$O(\ell d^2)$核心存储的高效扫描算法，相比已有方法实现指数级提升。六组实验（维度$d=8$至$20$）表明，相较基线提速最高达280倍，比SHAP-IQ快85倍，内存降低290倍。TT-FSI成功扩展至$ d=20 $（100万联盟），而所有对比方法均无法处理。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。