Exact Learning of Arithmetic with Differentiable Agents
This work addresses the challenge of enabling exact learning of algorithms in machine learning, which could benefit fields requiring precise computation, though it is incremental in advancing differentiable methods.
The paper tackles the problem of exact algorithmic learning with gradient-based methods by introducing Differentiable Finite-State Transducers (DFSTs), achieving strong length generalization on arithmetic tasks like binary and decimal addition and multiplication, with models generalizing without error to inputs thousands of times longer than training examples.
We explore the possibility of exact algorithmic learning with gradient-based methods and introduce a differentiable framework capable of strong length generalization on arithmetic tasks. Our approach centers on Differentiable Finite-State Transducers (DFSTs), a Turing-complete model family that avoids the pitfalls of prior architectures by enabling constant-precision, constant-time generation, and end-to-end log-parallel differentiable training. Leveraging policy-trajectory observations from expert agents, we train DFSTs to perform binary and decimal addition and multiplication. Remarkably, models trained on tiny datasets generalize without error to inputs thousands of times longer than the training examples. These results show that training differentiable agents on structured intermediate supervision could pave the way towards exact gradient-based learning of algorithmic skills. Code available at \href{https://github.com/dngfra/differentiable-exact-algorithmic-learner.git}{https://github.com/dngfra/differentiable-exact-algorithmic-learner.git}.