揭示机器学习解释的计算难题，指出反事实解释难以生成与近似。
On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI
- 分析反事实与半反事实解释的计算复杂性，发现多数情况难求解。
- 证明在特定假设下，解释不仅难生成，也难近似，存在不可逼近性。
- 为可解释人工智能研究者与政策制定者提供理论警示。
为使机器学习模型在关键应用中部署，提供清晰的决策解释至关重要。反事实与半反事实解释已成为帮助用户理解模型输出的两种机制。本文综述了现有文献中生成这些解释的计算复杂性结果，发现许多情况下生成解释是计算困难的。我们进一步提出新的不可逼近性结果，强化了这一论点：解释不仅难以生成，且在某些假设下也难以近似。这些复杂性结果对可解释人工智能（XAI）社区及致力于规范人工智能解释的政策制定者具有重要启示。
原文摘要 · Abstract (English)
Providing clear explanations to the choices of machine learning models is essential for these models to be deployed in crucial applications. Counterfactual and semi-factual explanations have emerged as two mechanisms for providing users with insights into the outputs of their models. We provide an overview of the computational complexity results in the literature for generating these explanations, finding that in many cases, generating explanations is computationally hard. We strengthen the argument for this considerably by further contributing our own inapproximability results showing that not only are explanations often hard to generate, but under certain assumptions, they are also hard to approximate. We discuss the implications of these complexity results for the XAI community and for policymakers seeking to regulate explanations in AI.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。