Source-linked AI summary
Deep Learning with Dynamic Computation Graphs
Moshe Looks, Marcello Herreshoff, DeLesley Hutchins, Peter Norvig
TL;DR
Neural networks over structured inputs use a different computation graph for each input, complicating batching and use of static-graph libraries. The paper presents dynamic batching and a compositional library for DCG models; its experiments report speedups and reimplementations of prior models that were extended to achieve superior performance.
Problem
Input-specific computation graphs complicate efficient batching, while static-graph libraries make building a new graph for each input costly.
Source: §1 · p. 1Method
Results
The authors report that literature models were reimplemented in Fold and extended to achieve superior performance, while dynamic batching yielded 120x speedup on GPU and 28x on CPU over batch size 1.
Source: §2.1 · p. 4, §4 · p. 8Takeaways & Limitations
Fold provides concise model definitions and faster execution, making it easier to rapidly explore novel model variants.
Source: §3.5.1 · p. 7Dynamic batching's added concat and gather operations cost 20% for GPU inference at batch size 1 and 60% for training with backpropagation.
Source: §2.1 · p. 4
Abstract
from arXiv · showhide
Neural networks that compute over graph structures are a natural fit for problems in a variety of domains, including natural language (parse trees) and cheminformatics (molecular graphs). However, since the computation graph has a different shape and size for every input, such networks do not directly support batched training or inference. They are also difficult to implement in popular deep learning libraries, which are based on static data-flow graphs. We introduce a technique called dynamic batching, which not only batches together operations between different input graphs of dissimilar shape, but also between different nodes within a single input graph. The technique allows us to create static graphs, using popular libraries, that emulate dynamic computation graphs of arbitrary shape and size. We further present a high-level library of compositional blocks that simplifies the creation of dynamic graph models. Using the library, we demonstrate concise and batch-wise parallel implementations for a variety of models from the literature.
1 INTRODUCTION
Dynamic computation graphs (DCGs) support neural networks over structured inputs, but their input-specific graph structures complicate batching and implementation in static-graph libraries. The paper introduces dynamic batching and a compositional library for building DCG models.
1 INTRODUCTION
- Mini-batch training on tensors or tensor sequences exploits parallel SIMD capabilities of modern GPUs and multi-core CPUs.The passage describes this as a basis for the success of deep learning libraries built around differentiable tensor data-flow graphs.Source: §1 · p. 1
- DCGs represent neural networks over structures such as parse trees, logical terms, and molecular graphs, with a different computation graph for each input.Recent applications include sentiment classification, semantic relatedness, question-answering, and chemical-compound screening.Source: §1 · p. 1
- Input-specific graph structures make efficient batching difficult, while static-graph libraries make constructing a new graph for every input costly.The introduction notes that practitioners avoid DCGs for implementation reasons.Source: §1 · p. 1
- The paper introduces dynamic batching for efficient DCG training and inference, and a combinator library for concise model implementations.It also reports empirical results for its TensorFlow implementation.Source: §1 · p. 1
2 DYNAMIC BATCHING
Dynamic batching rewrites differently shaped computation graphs so operations can be batched across graphs and within a graph, while a static graph emulates inputs of varying size and topology. The experiments report substantial speedups, alongside overhead from the additional concat and gather operations.
2 DYNAMIC BATCHING
- Dynamic batching groups instances of the same operation at the same graph depth, using concat and gather operations whose indices encode input-graph topology.The algorithm requires the possible operations to be specified in advance; operation inputs and outputs must have fixed tensor types and be polymorphic in batch size.Source: §2 · p. 2
- A static TensorFlow graph with one instance of each operation can emulate input graphs of arbitrary size and topology, with differentiable concat, gather, and while_loop operations.For the binary TreeRNN example, the loop evaluates operations at each depth using a schedule derived from the input tree.Source: §2 · p. 3
2.1 EXPERIMENTAL RESULTS
- The timing benchmark used random binary trees of the same shape for the native TensorFlow comparison, a best-case setting for manual batching.The implementation comparison also included dynamic batching on trees of different shapes; no measurable penalty for different shapes was reported.Source: §2.1 · p. 3
- The benchmark reports inference wall-clock averages in seconds.Its table is Table 1.Source: Table 1 · p. 4
- Dynamic batching's extra concat and gather operations cost 20% for GPU inference at batch size 1 and 60% for training with backpropagation.The cost is mainly visible at large batch sizes, where the benefit of within-tree batching is smaller.Source: §2.1 · p. 4
- 120x speedup on GPU and 28x on CPU over batch size 1 were reported for dynamic batching on random shapes.The comparison uses per-tree time; the authors note batch size 1 is not feasible for TensorFlow because graph-construction overhead is excluded.Source: §2.1 · p. 4
3 A COMBINATOR LIBRARY FOR NEURAL NETWORKS
TensorFlow Fold combines dynamic batching with compositional blocks for building neural networks over dynamic computation graphs. Its blocks support varied model structures, including sequence pipelines, attention, recursive Tree-LSTMs, and molecule graph convolutions.
3 A COMBINATOR LIBRARY FOR NEURAL NETWORKS
- TensorFlow Fold’s combinators simplify DCG model construction, with the stated aim of accelerating exploration of model variants.The library structures computations compositionally from blocks that map inputs to outputs.Source: §3 · p. 4
3.1 TYPE SYSTEM
- Blocks have static input and output types, including host-language inputs, tensors, tuples, sequences, and a unit type.Types may be inferred where possible and explicitly specified in some cases.Source: §3.1 · p. 5
3.2 BLOCKS AND COMBINATORS
- Blocks compose hierarchically as a tree, with combinators as internal nodes and atomic blocks as leaves.Reduce uses a balanced tree to limit computation depth and provide more batching opportunities.Source: §3.2 · p. 5
3.3 PIPELINES
- A text pipeline splits sentences into words, embeds them, folds the vectors through an RNN, and computes a label-prediction loss.The example uses a fully connected layer as the RNN cell and a zero initial state.Source: §3.3 · p. 6
3.4 COMPLEX COMPOSITIONS
- The feed-forward attention model generalizes average pooling and uses a directed acyclic block graph rather than a simple pipeline.A Composition block supports composing the blocks into DAGs.Source: §3.4 · p. 7
3.5 RECURSIVE DEFINITIONS
- The recursive Tree-LSTM applies a learnable function to each node’s input and child states, while ForwardDeclaration supports recursive model definitions.At internal nodes, the model takes zero as input and uses the states from both children.Source: §3.5 · p. 7
3.5.1 EXPERIMENTAL RESULTS
- The 30-model ensemble sets a new state-of-the-art on both Stanford Sentiment Treebank subtasks.The authors note the dataset’s small size; the ensemble comprises thirty independently trained models.Source: §3.5.1 · p. 8, Table 2 · p. 8
3.6 GRAPH CONVOLUTIONS
- Fold implements Kearnes et al.’s molecule graph convolution model using nested Composition blocks.The authors note that its code is more complex than their earlier examples.Source: §3.6 · p. 8
4 DISCUSSION
Dynamic batching addresses inefficient batching, while Fold targets the tooling burden of dynamic computation graphs. The discussion also qualifies both the library comparison and reported results.
4 DISCUSSION
- Fold is intended to help practitioners rapidly develop and iterate on dynamic-computation-graph architectures through a high-level combinator library.SPINN also supports efficient batching, but is limited to binary trees and uses padding or truncation for differently sized trees.Source: §4 · p. 8
- The authors believe dynamic batching solves inefficient batching for dynamic computation graphs in full generality, for the first time.SPINN is an alternative stack-based approach, but is limited to binary trees and requires padding or truncation for trees of different sizes.Source: §4 · p. 8
- Fold implementations can be concise, and literature models reimplemented in Fold were extended to achieve superior performance; line counts are only a rough comparison.The authors caution that brevity would be suboptimal if it came at the cost of flexibility.Source: §4 · p. 8
- Munkhdalai & Yu (2016a;b) report neither standard deviations nor the number of runs.The paper contrasts this with its own results, based on thirty independent runs.Source: §4 · p. 8
A FEED-FORWARD ATTENTION
The feed-forward attention example composes blocks to exponentiate inputs, normalize them, and compute a weighted sum. Composition scopes connect blocks without directed cycles.
A FEED-FORWARD ATTENTION
- The attention block exponentiates its input values, sums and broadcasts the total, then divides each exponential by that total to obtain weights.Sum performs elementwise addition, ZipWith applies a function elementwise across sequences, and Broadcast repeats a single value as a sequence.Source: A FEED-FORWARD ATTENTION · p. 10
- It multiplies the normalized weights by the input vectors, sums the products, and exposes the result as the attention output.Source: A FEED-FORWARD ATTENTION · p. 10
- A composition scope wires blocks together with reads, defines the composition’s inputs and outputs, and disallows directed cycles.The example uses Sum, ZipWith, and Broadcast as additional block types.Source: A FEED-FORWARD ATTENTION · p. 10
B GRAPH CONVOLUTIONS
The graph-convolution example represents molecules with atom and pair features, then uses a weave module to update both feature levels with learnable functions. The module can be stacked to form deep models.
B GRAPH CONVOLUTIONS
- For a molecule with N atoms, each atom has a real-valued feature vector and each atom pair has a symmetric feature vector, with p_i_i = 0.Source: B GRAPH CONVOLUTIONS · p. 10
- The weave module combines atom-level and pair-level features using six learnable functions, and can be stacked to build deep graph-convolution models.The example concerns molecules represented as undirected graphs of atoms.Source: B GRAPH CONVOLUTIONS · p. 10
- The atom update combines an atom-to-atom transform with a sum of pair-to-atom transforms, then applies the atom-level function.The implementation maps over atom features and sums along the inner pair dimension before combining the sequences.Source: B GRAPH CONVOLUTIONS · pp. 10–11
- The pair update combines pair-to-pair transforms with pairwise atom-to-pair transforms; the latter uses a nested scan over atoms.The implementation broadcasts atom features, forms pairwise inputs in both directions, and sums the resulting vectors elementwise.Source: B GRAPH CONVOLUTIONS · pp. 10–11
- The weave composition takes atom and pair feature sequences as input and returns updated atom and pair feature sequences.Its implementation applies the atom and pair transformations and exposes both resulting sequences as outputs.Source: B GRAPH CONVOLUTIONS · p. 11
C CALCULATING LINES OF CODE
The paper compares implementation length for a defined model-building task and notes that Fold’s concise syntax partly reflects reduced manual batching. The comparison does not measure the full training pipeline.
C CALCULATING LINES OF CODE
- The comparison counts nonblank, noncomment lines for a single file implementing only the input-output mapping, after removing imports and other nonfunctional code.The functional unit is creating the model for Raffel & Ellis (2016, sec. 2.3)’s variable-length experiment.Source: C CALCULATING LINES OF CODE · p. 11
- The Fold implementation is more concise partly because it eliminates manual batching, using implicitly batched block composition instead of explicit batch-axis handling.The comparison is also affected by differences between TensorFlow and Lasagne.Source: C CALCULATING LINES OF CODE · p. 11
- The comparison includes loss and accuracy calculations but excludes the training loop and training-data creation.The source implementations were formatted to 80-column lines, with a small exception for Tree-LSTM.Source: C CALCULATING LINES OF CODE · p. 11
TREE-LSTM
The Tree-LSTM comparison covers creating the model and training one epoch for fine-grained sentiment classification. Fold makes the implementation more concise, using OneOf to distinguish leaves from internal nodes rather than explicit recursive traversal.
TREE-LSTM
- Fold makes the Tree-LSTM implementation more concise than the Lua/Torch version for creating the model and training one epoch on fine-grained sentiment classification.The comparison excludes loading word embeddings and the dataset, which are provided as inputs.Source: TREE-LSTM · p. 12
- Manual batching is not a factor in this comparison because the original implementation computes gradients and losses one tree at a time.Source: TREE-LSTM · p. 12
- Fold uses a OneOf block to distinguish leaves from internal nodes instead of explicitly traversing the tree with a recursive function.Source: TREE-LSTM · p. 12
GRAPH CONVOLUTION
For a single weave module, Fold eliminates manual batching in an implementation that uses the same language and deep learning library as the original. Its Broadcast block replaces explicit tensor copying in the atoms-to-pairs calculation.
GRAPH CONVOLUTION
- Fold eliminates manual batching when implementing a single weave module in Python and TensorFlow, the same language and library used by the original.Source: GRAPH CONVOLUTION · p. 12
- In atoms-to-pairs, TensorFlow explicitly copies an n × d matrix into an n × n × d tensor, while Fold uses Broadcast to determine copy count lazily from subsequent computations.Source: GRAPH CONVOLUTION · p. 12
- The comparison concerns creating a single weave module, not a broader end-to-end training or inference benchmark.Source: GRAPH CONVOLUTION · p. 12