arXiv:2409.15318v2 宣告类型: replace-cross 摘要：叠加，神经网络表示比神经元更多特征的能力，现在越来越被视为大型模型高效性的关键。本文探讨了在叠加中进行计算的理论基础，为可验证正确的显式算法设定了复杂性界限。 我们首次为在叠加中进行计算的神经网络设定了下界，表明对于包括排列和两两逻辑操作在内的广泛问题类别，计算 \(m'\) 个特征在叠加中需要至少 \(\Omega(\sqrt{m' \log m'})\) 个神经元和 \(\Omega(m' \log m')\) 个参数。这意味着叠加容量的第一个次指数上限：一个具有 \(n\) 个神经元的网络最多可以计算 \(\mathcal{O}(n^2 / \log n)\) 个特征。相反，我们提供了几乎最佳的构造性上限：像两两 AND 这样的逻辑操作可以使用 \(\mathcal{O}(\sqrt{m'} \log m')\) 个神经元和 \(\mathcal{O}(m' \log^2 m')\) 个参数来计算。因此，在计算在叠加中计算特征的复杂性（本文的主题）与仅表示特征所需的基于 Johnson-Lindenstrauss 引理的最小 \(\mathcal{O}(\log m')\) 个神经元之间存在指数级差距。 我们希望本文的结果能够为使用计算复杂性技术推动神经网络解释性研究开辟一条路径。