用算法信息论揭示AI可解释性的根本局限，说明简单解释必然有误差。
The Limits of AI Explainability: An Algorithmic Information Theory Approach
- 用柯尔莫哥洛夫复杂度量化模型与解释的复杂度差异
- 证明解释越简单，必在某些输入上与原模型不同
- 揭示局部解释可远比全局解释更简洁且准确
本文通过算法信息论建立理解AI可解释性根本限制的理论基础。我们将可解释性形式化为用更简单模型逼近复杂模型的过程，利用柯尔莫哥洛夫复杂度量化逼近误差与解释复杂度。关键理论贡献包括：(1) 复杂度差距定理，证明任何显著比原模型简单的解释，在某些输入上必然与原模型不同；(2) 精确边界表明，对Lipschitz函数，解释复杂度随输入维度指数增长，但随误差容忍度多项式增长；(3) 揭示局部与全局可解释性之间的差距，表明局部解释可在相关区域保持精度的同时显著更简单。此外，我们建立了监管不可能性定理，证明不存在能同时实现无限制AI能力、人类可理解解释和可忽略误差的治理框架。这些结果对可解释AI系统的设计、评估与监管具有重要意义。
原文摘要 · Abstract (English)
This paper establishes a theoretical foundation for understanding the fundamental limits of AI explainability through algorithmic information theory. We formalize explainability as the approximation of complex models by simpler ones, quantifying both approximation error and explanation complexity using Kolmogorov complexity. Our key theoretical contributions include: (1) a complexity gap theorem proving that any explanation significantly simpler than the original model must differ from it on some inputs; (2) precise bounds showing that explanation complexity grows exponentially with input dimension but polynomially with error tolerance for Lipschitz functions; and (3) a characterization of the gap between local and global explainability, demonstrating that local explanations can be significantly simpler while maintaining accuracy in relevant regions. We further establish a regulatory impossibility theorem proving that no governance framework can simultaneously pursue unrestricted AI capabilities, human-interpretable explanations, and negligible error. These results highlight considerations likely to be relevant to the design, evaluation, and oversight of explainable AI systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。