Learning Efficient Algorithms with Hierarchical Attentive Memory

Abstract

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.

Added soft attention appendix

References in corpus (10)

• Adam: A Method for Stochastic Optimization
• Sequence to Sequence Learning with Neural Networks
• Gated Graph Sequence Neural Networks
• Grid Long Short-Term Memory
• Neural Programmer-Interpreters
• Neural GPUs Learn Algorithms
• Gradient Estimation Using Stochastic Computation Graphs
• Learning to Transduce with Unbounded Memory
• Reinforcement Learning Neural Turing Machines - Revised
• Learning Simple Algorithms from Examples

Cited by in corpus (12)

• Deep Multi-Task Learning with Shared Memory
• Focused Hierarchical RNNs for Conditional Sequence Processing
• Improving the Neural GPU Architecture for Algorithm Learning
• Strong Generalization and Efficiency in Neural Programs
• Neural Shuffle-Exchange Networks -- Sequence Processing in O(n log n) Time
• Extensions and Limitations of the Neural GPU
• AlignNet: Unsupervised Entity Alignment
• Summary - TerpreT: A Probabilistic Programming Language for Program Induction
• Contextual Memory Trees
• Progress Extrapolating Algorithmic Learning to Arbitrary Sequence Lengths
• Grammar Filtering For Syntax-Guided Synthesis
• Type-driven Neural Programming by Example