Learning Efficient Algorithms with Hierarchical Attentive Memory

By Marcin Andrychowicz, Karol Kurach. 2016

53 citations recorded by the source corpus.

In this paper, we propose and investigate a novel memory architecture for neural networks called Hierarchical Attentive Memory (HAM). It is based on a binary tree with leaves corresponding to memory cells. This allows HAM to perform memory access in O(log n) complexity, which is a significant improvement over the standard attention mechanism that requires O(n) operations, where n is the size of the memory. We show that an LSTM network augmented with HAM can learn algorithms for problems like merging, sorting or binary searching from pure input-output examples. In particular, it learns to sort n numbers in time O(n log n) and generalizes well to input sequences much longer than the ones seen during the training. We also show that HAM can be trained to act like classic data structures: a stack, a FIFO queue and a priority queue.

Subfields: Artificial Intelligence, Model Architectures

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 Model Architectures

Citations in the corpus

Making Neural Programming Architectures Generalize via Recursion (2017, background): “Numerous models have been proposed for learning programs; to name a few, this includes the Differentiable Neural Computer (Graves et al., 2016), Neural Turing Machine (Graves et al., 2014), Neural GPU (Kaiser & Sutskever, 2015), Neural Programmer (Neelakantan et al., 2015), Pointer Network (Vinyals ”
Learning Explanatory Rules from Noisy Data (2017, background): “Recently, a different approach to program induction has emerged from the deep learning community [Graves et al. , 2014; Reed and de Freitas, 2015; Neelakantan et al. , 2015; Kaiser, 2015; Andrychowicz and Kurach, 2016; Graves et al. , 2016].”
TerpreT: A Probabilistic Programming Language for Program Induction (2016, background): “…with components that resemble computer programs [Giles et al., 1989, Joulin and Mikolov, 2015, Grefenstette et al., 2015, Graves et al., 2014, Weston et al., 2014, Kaiser and Sutskever, 2016, Reed and de Freitas, 2016, Neelakantan et al., 2016, Kurach et al., 2015, Andrychowicz and Kurach, 2016].”
Neural Program Meta-Induction (2017, methodology): “…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 Induction) Inducing…”
Towards Neural Theorem Proving at Scale (2018, background): “Recent approaches in this direction focused on learning algorithmic behaviour without the explicit symbolic representations of a program (Graves et al., 2014; 2016; Kaiser and Sutskever, 2016; Neelakantan et al., 2016; Andrychowicz and Kurach, 2016), and consequently with it (Reed and de Freitas, 20”
Neural Program Lattices (2016, methodology): “…et al., 2014; Sukhbaatar et al., 2015b; Neelakantan et al., 2016; Gaunt et al., 2016; Feser et al., 2016), while others have used REINFORCE (Williams, 1992) to train neural networks that use sampling-based components to model memory access (Andrychowicz & Kurach, 2016; Zaremba & Sutskever, 2015).”
Neural Functional Programming (2016, methodology): “…et al., 1989; Graves et al., 2014; Weston et al., 2015; Joulin & Mikolov, 2015; Grefenstette et al., 2015; Kurach et al., 2016; Kaiser & Sutskever, 2016; Reed & de Freitas, 2016; Andrychowicz & Kurach, 2016; Zaremba et al., 2016; Graves et al., 2016), enabling them to learn program-like behavior.”
Differentiable Programs with Neural Libraries (2016, background): “…Weston et al., 2014; Joulin & Mikolov, 2015; Grefenstette et al., 2015; Kurach et al., 2015; Kaiser & Sutskever, 2016; Reed & de Freitas, 2016; Bunel et al., 2016; Andrychowicz & Kurach, 2016; Zaremba et al., 2016; Graves et al., 2016; Riedel et al., 2016; Gaunt et al., 2016; Feser et al., 2016).”
Divide and Conquer with Neural Networks (2017, methodology): “Whereas CNN and RNN models define algorithms with linear complexity, attention mechanisms [3] generally correspond to quadratic complexity, with notable exceptions [2].”
Recent Advances in Neural Program Synthesis (2018, background): “In "Hierarchical Attentive Memory" [11], the researchers specifically attempt to optimize the efficiency and usability of this memory structure.”
Focused Hierarchical RNNs for Conditional Sequence Processing (2018, methodology): “Following previous work (Williams, 1992; Andrychowicz & Kurach, 2016), we add an exploration term αH(πb) that prevents the policy from collapsing too soon during training.”
Contextual Memory Trees (2018, background): “In (Andrychowicz & Kurach, 2016) the authors learn a hier-Contextual archical data structure over a pre-partitioned set of memories with a parameterized JOIN operator shared across nodes.”
Neural Shufﬂe-Exchange Networks − Sequence Processing in O( n log n ) Time (2019, background): “A hierarchical memory layout with logarithmic access time is introduced in Andrychowicz and Kurach (2016), however, the model is discrete and has to be trained with reinforcement learning to achieve the claimed performance.”
Learning Knowledge Base Inference with Neural Theorem Provers (2016, background): “Recent neural network architectures such as Neural Turing Machines (Graves et al., 2014, NTMs), Memory Networks (Weston et al., 2015b), Neural Stacks/Queues (Grefenstette et al., 2015; Joulin and Mikolov, 2015), Neural Programmer (Neelakantan et al., 2016), Neural Programmer-Interpreters (Reed and d”
Learning Graphical State Transitions (2016, background): “Hierarchical Attentive Memory (HAM) is a memory-based architecture that consists of a binary tree built on top of an input sequence (Andrychowicz & Kurach, 2016).”