量子科技中心_量科网

尽管夏普利加法解释（SHAP）对于决策树等简单模型可在多项式时间内计算，但遗憾的是，对于神经网络等更具表达力的黑盒模型——这类模型往往最需要生成解释——其计算复杂度会变为NP难。本工作系统分析了*张量网络（TN）*的SHAP解释计算问题，该类模型比现有精确SHAP算法适用的模型族更广泛且更具表达力，并广泛应用于神经网络抽象与压缩领域。首先，研究人员提出了一个通用框架，用于计算任意结构通用TN的可证明精确SHAP解释。值得注意的是，当TN被限制为*张量链（TT）*结构时，SHAP计算可通过*并行*计算在*拟对数级*时间内完成。借助TT的表达能力，该复杂性结论可推广至决策树、树集成、线性模型和线性RNN等多种流行ML模型，从而强化了此前针对这些模型族报告的复杂性结果。最终，通过将二值化神经网络约化为张量网络表示，该团队证明：当网络*宽度*固定时，SHAP计算可*高效实现*；而即使*深度*恒定，计算依然保持困难。这揭示了一个重要发现：对于此类模型，宽度（而非深度）才是SHAP计算中的主要计算瓶颈。