用信息论分析掩码解释方法的极限,揭示为何现有方法在高精度下会失效。
The Query Channel: Information-Theoretic Limits of Masking-Based Explanations

- 将掩码解释建模为查询信道,用熵和信道容量刻画解释复杂度与信息速率
- 证明当解释速率超限,精确恢复概率必然趋近于零;低于容量则可可靠恢复
- 揭示高分辨率解释受噪声和非线性限制,标准方法在此区间仍失败
基于掩码的后处理解释方法(如KernelSHAP和LIME)通过随机扰动查询黑箱模型以估计局部特征重要性。本文将该过程建模为查询信道中的通信:潜在解释作为消息,每次掩码评估即为一次信道使用。解释的复杂度由假设类的熵表征,而查询接口的信息传输速率由每查询的识别容量决定。我们推导出一个强逆定理:若解释速率超过此容量,任何解释器与解码器序列的精确恢复错误概率必然收敛至1。同时证明可实现性结果,表明稀疏最大似然解码器在速率低于容量时可实现可靠恢复。基于蒙特卡洛的互信息估计算法提供非渐近查询基准,用于对比最优解码与类LIME、KernelSHAP的Lasso及OLS方法。实验显示,在某些查询预算范围内,信息论允许可靠解释,但标准凸近似仍失败。最后,我们将超像素分辨率与语言模型分词视为源编码选择,影响解释熵;并指出高斯噪声与非线性曲率会劣化查询信道,导致瀑布效应与误差平台,使高分辨率解释不可行。
原文摘要 · Abstract (English)
Masking-based post-hoc explanation methods, such as KernelSHAP and LIME, estimate local feature importance by querying a black-box model under randomized perturbations. This paper formulates this procedure as communication over a query channel, where the latent explanation acts as a message and each masked evaluation is a channel use. Within this framework, the complexity of the explanation is captured by the entropy of the hypothesis class, while the query interface supplies information at a rate determined by an identification capacity per query. We derive a strong converse showing that, if the explanation rate exceeds this capacity, the probability of exact recovery necessarily converges to one in error for any sequence of explainers and decoders. We also prove an achievability result establishing that a sparse maximum-likelihood decoder attains reliable recovery when the rate lies below capacity. A Monte Carlo estimator of mutual information yields a non-asymptotic query benchmark that we use to compare optimal decoding with Lasso- and OLS-based procedures that mirror LIME and KernelSHAP. Experiments reveal a range of query budgets where information theory permits reliable explanations but standard convex surrogates still fail. Finally, we interpret super-pixel resolution and tokenization for neural language models as a source-coding choice that sets the entropy of the explanation and show how Gaussian noise and nonlinear curvature degrade the query channel, induce waterfall and error-floor behavior, and render high-resolution explanations unattainable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。