用张量网络加速特征重要性计算，速度提升百倍以上
Tractable Shapley Values and Interactions via Tensor Networks
- 将模型局部行为建模为可分解的多元线性映射，用张量网络替代全组合枚举
- 一阶与二阶交互作用计算复杂度仅为O(n·poly(χ)+n²)，χ为张量最大截断秩
- 在UCI数据集上比KernelSHAP-IQ快25-1000倍，且保持相近精度
我们提出一种基于张量网络（TN）的近似方法——TN-SHAP，将传统Shapley值与交互指数中耗时的O(2^n)特征组合枚举，替换为少量目标评估。核心思想是将预测器的局部行为表示为可分解的多元线性映射，使组合量变为系数张量的线性探测。该方法仅需少量针对性评估即可提取k阶Shapley交互。具体地，一阶（单特征）与二阶（成对）计算复杂度为O(n·poly(χ)+n²)，其中χ为张量网络的最大截断秩。我们提供了近似误差和可计算性的理论保证。在UCI数据集上，该方法在拟合代理模型上的表现接近精确枚举，评估次数减少多个数量级，相比KernelSHAP-IQ实现25-1000倍的墙钟速度提升，同时可跨局部群体摊销训练成本。
原文摘要 · Abstract (English)
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 is to represent a predictor's local behavior as a factorized multilinear map, so that coalitional quantities become linear probes of a coefficient tensor. TN-SHAP replaces exhaustive coalition sweeps with just a small number of targeted evaluations to extract order-k Shapley interactions. In particular, both order-1 (single-feature) and order-2 (pairwise) computations have cost O(n*poly(chi) + n^2), where chi is the TN's maximal cut rank. We provide theoretical guarantees on the approximation error and tractability of TN-SHAP. On UCI datasets, our method matches enumeration on the fitted surrogate while reducing evaluation by orders of magnitude and achieves 25-1000x wall-clock speedups over KernelSHAP-IQ at comparable accuracy, while amortizing training across local cohorts.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。