用可解释性方法揭示图灵机中的算法结构
Interpretability for Turing Machines
- 通过探测噪声图灵机的局部损失景观识别算法特征
- 对称性和路径分离导致敏感度矩阵出现低秩块
- 主成分分析可恢复确定性有限自动机的算法特征
我们证明，用于神经网络的可解释性技术——敏感度，能够通过探测由Murfet和Troiani（arXiv:2504.08075）引入的噪声图灵机的学习问题局部损失景观，识别出图灵机中算法结构的存在。我们理论证明，图灵机所实现算法中的对称性和路径分离会在其敏感度矩阵中诱导出排列对称性和低秩块。我们在一组确定性有限自动机（DFAs）上进行了实证研究，结果表明，通过主成分分析和聚类方法可在敏感度空间中恢复出算法特征。
原文摘要 · Abstract (English)
We show that susceptibilities, an interpretability technique developed for neural networks, can identify the presence of algorithmic structure in Turing machines by probing the local loss landscape of a learning problem for noisy Turing machines introduced by Murfet and Troiani (arXiv:2504.08075). We prove that symmetries and path separation in the algorithm implemented by a Turing machine induce permutation symmetries and low-rank blocks in its susceptibility matrix. We study this empirically on a set of deterministic finite automata (DFAs) and demonstrate that algorithmic features can be recovered by principal component analysis and clustering methods in susceptibility space.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。