神经网络可精确执行二进制算法指令，仅需对数级数据量。
Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
- 通过构造比特级训练数据并控制核相关性，实现精确算法执行。
- 在无限宽两层网络中，高概率精确完成加法、乘法等四类任务。
- 适用于需要精准计算的场景，如可计算函数与程序验证。
神经网络擅长近似光滑函数，但在离散操作上难以完美泛化，而这类操作是算法任务的核心，常作为神经网络算法执行能力的测试基准。本文探讨：神经网络能否精确执行二进制编码的算法指令？基于神经正切核（NTK）框架，在无限宽两层全连接网络下研究训练动态，证明足够大的模型集合可高概率精确执行四类基本任务：二进制排列、二进制加法、二进制乘法以及减法并分支若负（SBN）指令。由于SBN具有图灵完备性，该框架可扩展至可计算函数。我们仅需对数级训练数据即可高效实现，并依赖两种技术：将训练数据结构化以分离比特级规则，以及在NTK regime中控制相关性，使模型预测与目标算法执行对齐。
原文摘要 · Abstract (English)
Neural networks are known for their ability to approximate smooth functions, yet they fail to generalize perfectly to unseen inputs when trained on discrete operations. Such operations lie at the heart of algorithmic tasks such as arithmetic, which is often used as a test bed for algorithmic execution in neural networks. In this work, we ask: can neural networks learn to execute binary-encoded algorithmic instructions exactly? We use the Neural Tangent Kernel (NTK) framework to study the training dynamics of two-layer fully connected networks in the infinite-width limit and show how a sufficiently large ensemble of such models can be trained to execute exactly, with high probability, four fundamental tasks: binary permutations, binary addition, binary multiplication, and Subtract and Branch if Negative (SBN) instructions. Since SBN is Turing-complete, our framework extends to computable functions. We show how this can be efficiently achieved using only logarithmically many training data. Our approach relies on two techniques: structuring the training data to isolate bit-level rules, and controlling correlations in the NTK regime to align model predictions with the target algorithmic executions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。