Source-linked AI summary
Dynamic Deep Neural Networks: Optimizing Accuracy-Efficiency Trade-offs by Selective Execution
Lanlan Liu, Jia Deng
TL;DR
The paper addresses computational efficiency in deep networks when different inputs require different amounts of computation. It introduces D2NNs, which use learned controller modules for selective execution and train the network end to end with backpropagation and reinforcement learning. Experiments report flexible and effective optimization of accuracy-efficiency trade-offs, subject to assumptions such as input difficulty variation.
Problem
D2NNs address the need for computational efficiency by adapting computation to inputs while supporting deployment constraints in mobile devices and data centers.
Method
D2NNs augment feed-forward DAGs with controller modules that select executable subnetworks, jointly training regular and controller modules with backpropagation and reinforcement learning.
Results
Extensive experiments across various architectures and tasks demonstrate that D2NNs are general, flexible, and effective for optimizing accuracy-efficiency trade-offs.
Takeaways & Limitations
D2NN provides a unified framework for designing computationally efficient neural networks with dynamic selective execution, including cascade and coarse-to-fine designs.
Takeaways & Limitations
On CIFAR-10, efficiency gains are modest because all inputs are low-resolution and few images are likely to be significantly easier to classify than others.
Abstract
from arXiv · showhide
We introduce Dynamic Deep Neural Networks (D2NN), a new type of feed-forward deep neural network that allows selective execution. Given an input, only a subset of D2NN neurons are executed, and the particular subset is determined by the D2NN itself. By pruning unnecessary computation depending on input, D2NNs provide a way to improve computational efficiency. To achieve dynamic selective execution, a D2NN augments a feed-forward deep neural network (directed acyclic graph of differentiable modules) with controller modules. Each controller module is a sub-network whose output is a decision that controls whether other modules can execute. A D2NN is trained end to end. Both regular and controller modules in a D2NN are learnable and are jointly trained to optimize both accuracy and efficiency. Such training is achieved by integrating backpropagation with reinforcement learning. With extensive experiments of various D2NN architectures on image classification tasks, we demonstrate that D2NNs are general and flexible, and can effectively optimize accuracy-efficiency trade-offs.
1. Introduction
Dynamic Deep Neural Networks selectively execute input-dependent subsets of neurons, using learned controllers to prune unnecessary computation. The framework jointly trains regular and controller modules to optimize accuracy and efficiency, and experiments support its flexibility and effectiveness.
- D2NNs execute only an input-dependent subset of neurons rather than the fixed computation sequence of standard feed-forward networks.
- A D2NN augments a directed acyclic graph of differentiable modules with control modules whose decisions determine whether other modules execute.A controller can skip an unnecessary module and invoke a dummy node with a default behavior, enabling early classification for some inputs.
- Selective execution prunes unnecessary computation, targeting mobile-device energy constraints and data-center throughput and operating costs.The framework can also use a larger network within a computation budget by executing only a subset of neurons per input.
- D2NNs jointly train regular and controller modules end to end, integrating backpropagation with reinforcement learning because controller decisions are non-differentiable.
- The framework supports end-to-end learned selective-execution decisions, flexible topologies and sequences, arbitrary user-defined efficiency metrics, and global metrics such as F-score.
- Extensive experiments across various D2NN architectures and several tasks demonstrate generality, flexibility, and improved computational efficiency.
- D2NN is presented as a unified framework for augmenting static feed-forward networks with controllers across designs including cascade and coarse-to-fine architectures.
2. Related work
Related work improves efficiency through input-independent simplification or input-dependent execution, while D2NNs emphasize jointly learned control and features. D2NNs also target flexible control topologies and direct optimization of user-defined global metrics.
- Earlier input-dependent vision systems often hand-design features, thresholds, or control policies, whereas D2NNs learn visual features and execution decisions jointly end to end.
- Prior efficiency methods remove input-independent redundancy through pruning, layer approximation, or limited-precision representations.
- D2NNs directly optimize arbitrary user-defined global performance metrics, unlike conditional-computation methods focused on encouraging sparse activations or sparse experts.
- D2NN control modules can be inserted anywhere to control arbitrary subnetworks, and one framework supports multiple controller parameterizations and flexible topologies.
- Hard attention performs input-dependent execution by processing salient parts only, whereas soft attention processes all parts and merely up-weights salient ones.
- The cited prior hard-attention work had not directly optimized accuracy-efficiency trade-offs, while DSNNs lacked a proposed method for optimizing efficiency.
3. Definition and Semantics of D2NNs
A D2NN is a directed acyclic graph of input, output, and differentiable function nodes connected by data or control edges. During topological inference, control decisions selectively activate nodes, while skipped or null outputs determine downstream execution.
- A D2NN is a directed acyclic graph without duplicated edges containing input nodes, output nodes, and differentiable function nodes.
- Function nodes are regular when their outgoing edges carry data and control nodes when their outgoing edges carry control decisions; constant-output function nodes are dummy nodes.
- Inference traverses the graph in topological order, as in conventional DNNs, except control nodes can cause computation to be skipped.
- A control node activates the outgoing control edge with the highest score, thereby allowing its controlled node to execute.In the illustrated case, the controller chooses between alternative modules according to their control scores.
- Skipped nodes output either null or a user-defined default value, and null outputs can propagate downstream to skip dependent nodes.A downstream node with a default-valued input edge can still execute despite an upstream null output.
- A node with multiple incoming control edges executes if any incoming control edge is active, while nodes with null inputs are skipped.
- D2NN semantics can be viewed as conditional program execution, with data edges acting as variables and control edges as boolean conditions.
4. D2NN Learning
D2NN learning combines reinforcement learning for discrete control decisions with backpropagation for jointly optimizing accuracy and efficiency. Mini-bags extend this approach to set-based metrics whose rewards cannot be defined independently per example.
- Control-node learning: Control nodes make direct backpropagation infeasible because their discretized outputs determine network execution.The method therefore treats control decisions as actions in a reinforcement-learning problem.
- Control-node learning: Q-learning trains each control node to predict the reward associated with selecting each action for a given input.Training selects the highest-Q action, executes the remaining network, observes a user-defined reward, and applies an L2 loss; epsilon-greedy exploration is also used.
- Reward design: The reward combines an accuracy metric with an efficiency metric to optimize their trade-off.The accuracy metric can include F-score, while efficiency can be represented by a metric such as inverse computation.
- Mini-bags for set-based metrics: Set-based metrics such as precision and F-score cannot generally be optimized by averaging rewards defined independently on individual examples.Their values must be computed jointly over a set of examples.
- Mini-bags for set-based metrics: Mini-bags define the state as a set of inputs, allowing set-based metrics to determine a joint reward while retaining per-example actions.Training computes gradients using a mini-batch of mini-bags and constrains the joint action-value to decompose across examples.
- Joint training: The decomposed action-value makes the best joint action equal to the concatenation of each example’s best action, so test-time inference remains independent per example.For regular nodes, skipped examples receive no gradient from those nodes, while regular-node losses and control-node losses are backpropagated together.
5. Experiments
Experiments evaluate four D2NN architectures across image-classification tasks, showing that input-dependent execution can achieve favorable accuracy-efficiency trade-offs. The experiments also examine execution paths, wall-time costs, and a scope boundary on CIFAR-10.
- Experimental setup: Four D2NN structures are evaluated to demonstrate flexibility and effectiveness in efficient network design.The experiments compare D2NNs with prior work on several image-classification tasks.
- High-low capacity D2NN: The high-low D2NN learns to match the low-capacity path’s speed and the high-capacity path’s accuracy at different trade-off settings.Increasing λ places more weight on accuracy, sending more examples through the high-capacity node.
- Cascade D2NN: The cascade D2NN achieves a near-optimal trade-off, substantially reducing computation with negligible accuracy loss and outperforming varied static-network baselines.This result also demonstrates successful joint training of multiple control nodes.
- Efficiency measurement: 82% wall-time cost corresponds to 53% multiplication cost, while 95% wall-time cost corresponds to 70% multiplication cost in the cascade experiment.Defining the reward directly using wall time can further reduce this gap.
- Chain D2NN: The chain D2NN achieves a near-optimal accuracy-cost curve with little accuracy loss, demonstrating effectiveness on a general DAG whose paths can merge.Its cost is measured by multiplications normalized to the highest-capacity baseline.
- Hierarchical D2NN: The hierarchical D2NN matches the full network’s accuracy at about half the computational cost, while larger λ activates more nodes.Its execution can involve many different sequences because of D2NN parallelism.
6. Conclusion
The paper concludes that D2NNs enable selective execution and effectively optimize accuracy-efficiency trade-offs across experiments.
- D2NNs allow selective execution in feed-forward deep neural networks.
- Extensive experiments demonstrate that D2NNs are flexible and effective for optimizing accuracy-efficiency trade-offs.
A. Implementation Details
The implementation represents user-defined D2NNs as directed acyclic graphs, tracks per-example execution and output states, and processes nodes in topological order during training.
- The framework lets users define subnetwork architectures with existing Torch modules while managing forward- and backward-pass communication.
- D2NN execution tracking distinguishes activated nodes from nodes that produce outputs through default values.
- Preprocessing traverses the model breadth-first to order the DAG, check structure, build relationships, and calculate node costs.
- Training uses a forward pass in topological order and a backward pass in reverse order, similarly to conventional DNN training.
B. ILSVRC-10 Semantic Hierarchy
ILSVRC-10 is a 10-class subset organized into a three-layer semantic hierarchy with superclasses, coarse classes, and leaf classes.
- ILSVRC-10 contains 10 classes arranged as 2 superclasses, 5 coarse classes, and 10 leaf classes.Each class has 500 training images, 50 validation images, and 150 test images.
- Each class is split into 500 training images, 50 validation images, and 150 test images.
C. Configurations
The configurations cover high-low capacity, cascade, chain, and hierarchical D2NNs with varied regular and control-node designs, including convolutional, pooling, fully connected, and identity layers.
- High-Low Capacity D2NN: The high-low capacity D2NN uses one control node and three regular nodes.
- Cascade D2NN: The cascade D2NN uses seven regular nodes and three control nodes arranged into four cascade stages.
- Across the configurations, regular nodes include convolutional, pooling, fully connected, and identity layers.
- Control nodes use convolutional or reshaped fully connected architectures that produce two-action outputs.
- Chain D2NN: The chain D2NN is organized as a sequence in which each link uses a control node to select between two regular nodes.
- Hierarchical D2NN: The hierarchical D2NN uses a design associated with the ILSVRC-10 semantic hierarchy.
- Comparison with Dynamic Capacity Networks: The comparison setup trains a chain D2NN of length 4, with additional configurations specifying convolutional, pooling, identity, and control nodes.
- Convolutional and fully connected layers generally use ReLU activations unless individually specified otherwise.