Learning Simple Algorithms from Examples

By Wojciech Zaremba, Tomas Mikolov, Armand Joulin, Rob Fergus. 2015

102 citations recorded by the source corpus.

We present an approach for learning simple algorithms such as copying, multi-digit addition and single digit multiplication directly from examples. Our framework consists of a set of interfaces, accessed by a controller. Typical interfaces are 1-D tapes or 2-D grids that hold the input and output data. For the controller, we explore a range of neural network-based models which vary in their ability to abstract the underlying algorithm from training instances and generalize to test examples with many thousands of digits. The controller is trained using $Q$-learning with several enhancements and we show that the bottleneck is in the capabilities of the controller rather than in the search incurred by $Q$-learning.

Subfields: Artificial Intelligence, Prompting & Reasoning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Prompting & Reasoning

Citations in the corpus

Programmable Agents (2017, background): “Different approaches to this problem focus on networks that infer programs [3, 10, 22], on networks that execute programs [39, 30, 5] and on networks that jointly do both [14, 17, 38, 29, 13]; although there is much overlap between many of these approaches.”
An Actor-Critic Algorithm for Sequence Prediction (2016, methodology): “A similar trick was used in the context of learning simple algorithms with Q-learning (Zaremba et al., 2015).”
Making Neural Programming Architectures Generalize via Recursion (2017, methodology): “Although the model is exposed to more and more data, it might learn spurious and overly complex representations of the program, as suggested in Zaremba et al. (2016).”
Neural Programmer-Interpreters (2015, neutral): “(Zaremba & Sutskever, 2015; Zaremba et al., 2015; Kaiser & Sutskever, 2015; Kurach et al., 2015; Neelakantan et al., 2015).”
Inferring and Executing Programs for Visual Reasoning (2017, background): “Such models can take the form of a feedforward scoring function over operators in a domain-specific language that can be used to guide program search [4], or of a recurrent network that decodes a vectorial program representation into the actual program [22, 26, 34, 46, 47, 48].”
DeepCoder: Learning to Write Programs (2016, background): “…2015; Joulin & Mikolov, 2015; Grefenstette et al., 2015; Sukhbaatar et al., 2015; Neelakantan et al., 2016; Kaiser & Sutskever, 2016; Reed & de Freitas, 2016; Zaremba et al., 2016; Graves et al., 2016), but none of these can write programs; that is, they do not generate human-readable source code.”
Learning to Optimize (2016, background): “Subsequent work proposes variants of this model that use different primitive memory access operations [14], more expressive operations [16, 28] or other non-differentiable operations [30, 29].”
Control of Memory, Active Perception, and Action in Minecraft (2016, methodology): “In addition, there are deep RL approaches to tasks other than Atari such as learning algorithms (Zaremba et al., 2016) and text-based games (Sukhbaatar et al., 2015a; Narasimhan et al., 2015).”
Automatic differentiation in machine learning: a survey (2015, background): “, 2014), a range of controller–interface abstractions (Graves et al., 2016; Zaremba et al., 2016; Joulin and Mikolov, 2015; Sukhbaatar et al., 2015), and differentiable versions of data structures such as stacks, queues, deques (Grefenstette et al.”
Automatically Composing Representation Transformations as a Means for Generalization (2018, background): “The ﬁrst as-Automatically sumes pre-speciﬁed transformations and learns the structure (from dense supervision on execution traces to sparse-rewards) [13, 14, 18, 22, 25, 28, 65, 87, 90].”
Lifelong Learning of Compositional Structures (2020, background): “Many different compositional representations for handling multiple tasks have been proposed over the last few years [32, 9, 13, 19].”
TerpreT: A Probabilistic Programming Language for Program Induction (2016, background): “ A number of recent advances build on this observation to learn algorithms from input-output data (Graves et al., 2014; Joulin and Mikolov, 2015; Neelakantan et al., 2016a; Reed and de Freitas, 2016; Zaremba et al., 2016). While these approaches diﬀer in (a) the underlying execution models (e.g., Tu”
Neural Program Synthesis with Priority Queue Training (2018, background): “…2017; Bhoopchand et al., 2016; Gaunt et al., 2016; Khanh Dam et al., 2016; Neelakantan et al., 2017; Riedel et al., 2016; Schaechtle et al., 2016; Zaremba et al., 2016; Barone & Sennrich, 2017; Beltramelli, 2017; Cai et al., 2017; Devlin et al., 2017; Hu et al., 2017; Guu et al., 2017; Johnson…”
Neural Program Meta-Induction (2017, methodology): “…evaluate the four techniques Novel Architectures Applied to Program Induction NTM [7], Stack RNN [11], NRAM [12] Neural Transducers [8], Learn Algo [21] Others [4, 20, 2, 13] Trace-Augmented Induction NPI [18] Recursive NPI [3], NPL [14] Non Example-Driven Induction (e.g., Natural Language-Driven…”
Learning Efficient Algorithms with Hierarchical Attentive Memory (2016, methodology): “In two recent papers (Zaremba & Sutskever, 2015; Zaremba et al., 2015) authors consider extending neural networks with nondif-ferentiable memories based on pointers and trained using Reinforcement Learning.”
Neural Program Lattices (2016, methodology): “More recently, Zaremba et al. (2015) showed that an RNN architecture using modern LSTM or GRU controllers can perfectly generalize to inputs 20 times as long as than those seen in the training data when trained in either a supervised or reinforcement learning setting.”
Towards Synthesizing Complex Programs From Input-Output Examples (2017, background): “…Zaremba et al., 2016; Zaremba & Sutskever, 2015), but in these works, either extra supervision on execution traces is needed during training (Reed & De Freitas, 2016; Cai et al., 2017; Li et al., 2017), or the trained model cannot generalize well (Zaremba et al., 2016; Zaremba & Sutskever, 2015).”
How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition (2022, background): “For example, Andreas et al. (2016) assume that the structure in which modules are combined must be given (explicit information), Zaremba et al. (2016) assume that the modules themselves are given and the agent must discover how to combine them (explicit information), Hu et al. (2017) assume textual…”
MazeBase: A Sandbox for Learning from Games (2015, background): “originally designed for human enjoyment, rather than any speciﬁc task. It also differs from the recent surge of work on learning simple algorithms (Zaremba & Sutskever, 2015; Graves et al., 2014; Zaremba et al., 2015), which lack grounding. 1 arXiv:1511.07401v2 [cs.LG] 7 Jan 2016 Under review as”