Source-linked AI summary
On the Expressive Power of Deep Neural Networks
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, Jascha Sohl-Dickstein
TL;DR
The paper asks how neural-network architecture affects the functions networks can compute, amid limited connections between general expressivity theory and practical trained networks. It introduces architecture-wide expressivity measures unified by trajectory length, then reports exponential depth dependence, greater sensitivity to lower-layer weights, and trajectory regularization with batch-normalization performance.
Problem
Neural-network expressivity remains difficult to characterize across architectures and to connect with practical performance, while prior deep-network results rely on hand-coded weight constructions.
Method
The paper defines interrelated expressivity measures for standard architectures, analyzes them across weights encountered during training, and unifies them through trajectory length.
Results
The measures grow exponentially with depth, trained networks are more sensitive to lower-layer weights, and trajectory regularization matches batch normalization performance.
Takeaways & Limitations
Expressivity analysis can connect architectural depth and trajectory behavior to trained-network sensitivity and motivate a more computationally efficient alternative to batch normalization.
Takeaways & Limitations
Earlier expressivity constructions targeted extremal hand-coded weights, and the trajectory-length relation for bounded nonlinearities assumes neurons remain saturated except during rapid transitions.
Abstract
from arXiv · showhide
We propose a new approach to the problem of neural network expressivity, which seeks to characterize how structural properties of a neural network family affect the functions it is able to compute. Our approach is based on an interrelated set of measures of expressivity, unified by the novel notion of trajectory length, which measures how the output of a network changes as the input sweeps along a one-dimensional path. Our findings can be summarized as follows: (1) The complexity of the computed function grows exponentially with depth. (2) All weights are not equal: trained networks are more sensitive to their lower (initial) layer weights. (3) Regularizing on trajectory length (trajectory regularization) is a simpler alternative to batch normalization, with the same performance.
1. Introduction
The paper addresses gaps in understanding how architecture affects neural-network expressivity by introducing broadly applicable measures unified by trajectory length. It finds exponential depth dependence, greater lower-layer sensitivity, and a computationally efficient regularization alternative to batch normalization.
- Motivation: Prior expressivity results often emphasize shallow networks or hand-coded deep-network weights, leaving typical trained-network behavior and matching upper bounds insufficiently understood.The paper frames these as gaps between worst-case constructions, practical settings, and general upper bounds.
- Approach: The paper defines interrelated expressivity measures that apply across standard architectures independently of specific weight choices.The framework begins after random initialization and connects expressivity analysis to performance during training.
- Approach: Trajectory length unifies the analysis by measuring how activation patterns and network outputs change as inputs move along one-dimensional trajectories.Transitions occur when nearby inputs change which threshold-based units are active.
- Findings: Trajectory-length analysis suggests that lower-layer weights are especially important because comparable parameter changes there induce larger network changes.The paper reports this sensitivity in trained-network experiments and links better lower-layer optimization to performance.
- Findings: The measures exhibit exponential growth with network depth, providing an upper-bound analysis applicable to all possible weight settings.This differs from earlier lower-bound constructions based on particular hand-coded weights.
- Applications: Trajectory regularization is proposed as a more computationally efficient method that offers the same advantages and performance as batch normalization.The method is motivated by understanding how batch normalization affects trajectory length.
2. Measures of Expressivity
The paper measures neural-network expressivity through activation patterns, transitions, linear regions, and trajectory length. These measures support general bounds and empirical findings about how depth, width, initialization, and network architecture affect complexity.
- Neuron Transitions: A neuron transition occurs when its activation switches linear region, and output-neuron transitions correspond to changes between linear regions.For ReLU, this is an off/on switch; for hard tanh, it can involve transitions among saturation and linear regions.
- Activation Patterns: Activation patterns encode each neuron's linear region, and counting distinct patterns measures how much more expressive a network is than a linear mapping.For ReLUs, patterns use {0, 1}; for hard tanh, they use {-1, 0, 1}.
- Activation Patterns: O(k^(mn)) activation patterns upper-bound fully connected ReLU networks with n hidden layers of width k and inputs in R^m; hard tanh has O((2k)^(mn)).The bound applies over all weight settings and is asymptotically tight for the considered fully connected networks.
- Linear Regions: Deep piecewise-linear networks partition input space into convex polytopes, with the network representing a different linear function on each region.The regions arise from nested activation boundaries that can bend across boundaries established by earlier layers.
- Empirical Measures: Empirical transition counts grow exponentially with depth, while increasing width does not produce the same growth rate; initialization scale also affects the observations.These effects were observed when sweeping a trajectory through networks with bounded nonlinearities, especially tanh and hard tanh.
- Trajectory Length: Trajectory length grows exponentially with network depth, with width appearing only as the base of the exponent; under a saturation assumption, transitions are proportional to trajectory length.The transition result is stated for hard tanh networks initialized with weight and bias scales σw and σb.
3. Insights from Network Expressivity
The paper uses trajectory length to connect expressivity with parameter sensitivity and training stability, then proposes trajectory regularization as a simpler alternative to batch normalization.
- Parameter sensitivity: 0.25-magnitude noise causes a 0.7 accuracy drop in the first layer but only a 0.02 drop in the fifth layer.This lower-layer sensitivity pattern persists across multiple initialization scales.
- Parameter sensitivity: Trajectory-length analysis links a perturbation at any layer to exponential growth across the remaining depth.The paper uses this relationship to study parameter and functional stability.
- Parameter sensitivity: Training exactly one layer produces monotonically better performance when the trained layer is lower in the network.The experiment trains one layer while other layers remain frozen after random initialization.
- Training and stability: Trajectory length increases during training on both CIFAR10 and MNIST, while weight norms also increase and can push networks into the exponential-growth regime.This growth occurs even when the CIFAR10 initialization is not initially in that regime.
- Training and stability: Batch normalization reduces trajectory length after initial training steps, stabilizing representations without sacrificing expressivity.The batch-normalization layers are poorly behaved at the very beginning because of division by a near-zero variance.
- Trajectory regularization: Trajectory regularization achieves comparable performance to batch normalization while requiring the same computations during training and testing.It adds a trajectory-length penalty and scales outgoing activations by a learned parameter; the method is computationally simpler in deployment.
4. Discussion
The discussion presents exponential depth bounds and trajectory regularization as contributions, while identifying links to performance and more sophisticated regularization as future work.
- Contributions: The paper presents an interrelated set of expressivity measures with tight exponential depth bounds.These measures are intended to characterize how architecture affects network expressiveness.
- Future work: Future work includes linking expressivity measures to other properties of neural-network performance.The discussion frames this as a broad direction for principled understanding.
- Future work: The paper connects trajectory length to adversarial perturbations and suggests studying trajectory growth between original inputs and adversarial examples.It also suggests that more sophisticated trajectory regularization could yield further performance gains.
Proof of Theorem 2
The proof partitions input space into convex polytopes using activation-transition hyperplanes and shows that affine one-dimensional trajectories encounter unique activation patterns across intervals.
- Input-space partitioning: First-layer neuron transitions define hyperplanes that partition input space into polytopes with fixed activation patterns.For ReLUs the transition occurs at zero, while hard-tanh transitions occur at ±1.
- Input-space partitioning: Inductively, deeper-layer transitions further partition each existing polytope because preceding-layer activations are linear within it.The resulting regions remain convex polytopes.
- Trajectory transitions: A one-dimensional trajectory that does not double back cannot repeat an activation pattern after crossing into a new region.Straight lines provide a simple example of such trajectories.
- Trajectory transitions: For an affine trajectory x(t) = x0 + t(x1 − x0), the parameter axis is partitioned into intervals at neuron transitions, with one unique activation pattern per interval.This converts network-region changes along the input path into transition counts over t.
- Activation-pattern counting: Counting distinct activation patterns over the full input space becomes a question about the regions formed by hyperplane arrangements.The proof introduces this generalization after establishing the one-dimensional case.
Proof of Theorem 5
The proof establishes the hyperplane-region bound through a recurrence: adding one hyperplane increases regions by the number of regions induced on that hyperplane.
- Recursive region counting: A hyperplane arrangement’s region count equals the regions without one hyperplane plus the regions created by its intersection with the remaining arrangement.This gives the recursive formula used in the proof.
- Inductive proof: The proof proceeds by induction on the sum of the number of hyperplanes and the ambient dimension.The base cases r(1, 0) = r(0, 1) = 1 are treated as immediate.
- Inductive proof: The induction concludes using a standard combinatorial identity, completing the theorem’s proof.The text then applies the established result to prove Theorem 1.
Proof of Theorem 1
The proof bounds the number of input-space regions by multiplying the contributions of successive hidden layers. ReLU yields O(k^mn), while hard tanh yields O((2k)^mn).
- Each hidden layer contributes at most r(k, m) regions for every region established by preceding layers.The second hidden layer therefore multiplies the first layer’s contribution by another factor of r(k, m).
- O(k^2m) bounds the total regions generated by the first two hidden layers.
- O(k^mn) bounds the total number of input-space regions for a ReLU network with n hidden layers.
- O((2k)^mn) bounds the corresponding number of regions for hard tanh because each neuron produces two hyperplanes.
B.1. Notation and Preliminary Results
This section establishes notation for trajectories, network representations, and matrix decompositions, then develops Gaussian projection facts used in later trajectory-length arguments.
- A trajectory is analyzed through the difference between network representations at neighboring inputs, δz(d) = z(d)(x + δx) − z(d)(x).
- Vectors are decomposed into components parallel and perpendicular to a specified direction, with the direction stated explicitly by context.
- A matrix is partitioned into four components according to row- and column-space directions induced by the chosen vectors.
- For Gaussian matrices, components parallel and perpendicular to a fixed vector are independent random variables.
- The preliminaries provide expected-norm and projection results for Gaussian vectors and matrices, including bounds derived from chi-distribution and Gamma-function properties.
- Network notation defines inputs, hidden representations, nonlinearities, weights, and biases recursively across layers.
Proof of Theorem 4
The theorem proof connects transitions across layers to trajectory growth, while the weight-sweeping analysis uses a statistical duality with input sweeping to study dichotomies and remaining depth.
- For large weight variance, a neuron transition is related to whether one Gaussian contribution exceeds the magnitude of the remaining contributions.
- The relevant ratio of independent centered normal variables follows a Cauchy distribution, enabling calculation of the transition probability.
- Figure 13 measures trajectory length after propagating a circular trajectory through each layer and compares simulated growth with theoretical bounds.
- The number of transitions in a layer is analyzed through neuron-level transitions and their sensitivity to transitions in the preceding layer.
- Sweeping first-layer weights after random initialization is statistically similar to sweeping the input along a trajectory.
- The proportionality between transitions and trajectory length extends to dichotomies, as does the dependence of expressive power on remaining depth.
C. Addtional Experiments from Section 3
Additional experiments examine dichotomies, remaining-depth effects, transition accumulation, layer-specific training, and trajectory-length changes during training.
- Figure 14 reports exponentially increasing dichotomies with architecture depth and much slower increases with width when first-layer weights are swept.
- Figure 15 indicates that expressive power depends on remaining network depth rather than total network depth.
- Figure 16 tracks unique dichotomies against transition count and compares deep-network results with a random-walk simulation.
- On CIFAR-10, training lower layers mostly produces better performance, although training only one layer limits overall performance.
- In the constrained hard-tanh setting, the theory applies to training error while generalization accuracy remains low.
- Training increases trajectory length for smaller initialization values of σw, potentially increasing input-output expressivity and accuracy.