arXiv:2410.08025v3 公告类型：替换 摘要：许多在机器学习、认知/脑科学和社会中提出的神经网络应用依赖于通过电路发现实现内在可解释性的可行性。这呼唤对可行算法选项进行实证和理论探索。尽管在设计和测试启发式方法方面取得了进展，但在缺乏对它们所部署解决的问题复杂性属性的理解时，人们对其可扩展性和忠实性表示担忧。为了应对这一挑战，我们使用经典计算复杂性和参数化计算复杂性理论研究电路发现：（1）我们描述了一个概念性框架，用于用描述、解释、预测和控制方面的 affordance 来推理电路查找查询；（2）我们形式化了一套全面的查询，用于机制性解释，并提出了一个分析它们的形式框架；（3）我们使用它来确定许多具有实际兴趣的查询变体和放宽形式的复杂性。我们的研究发现揭示了一个具有挑战性的复杂性景观。许多查询是不可处理的，相对于模型/电路特征仍然保持固定参数不可处理，并且在加性、乘性以及概率近似方案下不可逼近。为了应对这一景观，我们证明了一些难以处理的问题可以通过理解较好的启发式方法来解决，并证明了一些保留有用 affordance 的较适度查询的可处理性和固定参数可处理性。该框架使我们能够理解解释查询的范围和局限性，探索可行的选项，并比较其在现有和未来架构上的资源需求。