Source-linked AI summary
On the Number of Linear Regions of Deep Neural Networks
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, Yoshua Bengio
TL;DR
The paper studies how deep feedforward networks with piecewise linear activations achieve complex functions through repeated computation across input regions. It develops a general framework for analyzing linear regions in rectifier and maxout networks, improving rectifier complexity bounds and showing favorable behavior for depth with moderate hidden layers.
Problem
The paper addresses the limited theoretical understanding of deep networks with piecewise linear activations, despite their practical success.
Method
The paper develops a general framework that analyzes how layer-wise composition and input-region reuse determine linear-region complexity in rectifier and maxout networks.
Results
The rectifier analysis improves prior complexity results and shows favorable behavior for deep over shallow networks with a moderate number of hidden layers.
Takeaways & Limitations
Piecewise linear deep networks can compute highly complex and structured functions by exponentially reusing lower-level computations across input regions.
Takeaways & Limitations
The paper leaves open how parameter-space regions correspond to functions with a given number of linear regions.
Abstract
from arXiv · showhide
We study the complexity of functions computable by deep feedforward neural networks with piecewise linear activations in terms of the symmetries and the number of linear regions that they have. Deep networks are able to sequentially map portions of each layer's input-space to the same output. In this way, deep models compute functions that react equally to complicated patterns of different inputs. The compositional structure of these functions enables them to re-use pieces of computation exponentially often in terms of the network's depth. This paper investigates the complexity of such compositional maps and contributes new theoretical results regarding the advantage of depth for neural networks with piecewise linear activation functions. In particular, our analysis is not specific to a single family of models, and as an example, we employ it for rectifier and maxout networks. We improve complexity bounds from pre-existing work and investigate the behavior of units in higher layers.
1 Introduction
Deep networks can achieve high functional complexity by composing piecewise linear transformations that reuse computations across input regions. The paper develops a general analysis of this behavior and reports a depth advantage for rectifier and maxout networks.
- Recent theoretical results on rectifier networks show exponentially more linear response regions for deep models than shallow models with the same number of units.
- The paper develops a general framework for piecewise linear activations and estimates linear-region counts for rectifier and maxout networks.
- Deep rectifier results improve prior bounds and show favorable behavior over shallow networks with a moderate number of hidden layers.
- A two-layer model with the same number of hidden units as a shallow model captures a decision boundary more accurately using more linear pieces.
- Deep networks can reuse and compose features across layers, achieving exponential complexity despite a low-dimensional function class.This complexity comes from mapping multiple input pieces to common intermediate outputs and replicating higher-layer computations.
2 Feedforward Neural Networks and their Compositional Properties
Deep networks compose piecewise-linear layers that identify multiple input neighborhoods and replicate higher-layer computations across them, producing complex functions with relatively few units. The section formalizes linear regions and this identification mechanism, including shallow rectifier bounds and stability under parameter perturbations.
- 2.1 Definitions: Rectifier and rank-k maxout units provide the piecewise-linear activations analyzed in the framework.Rectifiers switch between zero and linear behavior, while maxout units select the maximum among k affine inputs.
- A linear region is a maximal connected input subset on which a piecewise-linear network function is linear.
- 2.2 Shallow Neural Networks: A shallow rectifier network reaches its maximal linear-region count when its hidden-unit hyperplanes are in general position.The bound is inherited from the maximal region count of a hyperplane arrangement.
- 2.3 Deep Neural Networks: Each layer can map distinct input regions to a common output, allowing later computations to be replicated across all corresponding preimages.This recursive identification mechanism underlies the exponential growth of replicated computations with network depth.
- 2.3 Deep Neural Networks: Deep constructions use earlier layers to identify many input neighborhoods and map them into activation neighborhoods associated with distinct regions of the last hidden layer.Lemma 2 states a lower bound on the maximal number of linear regions for an L-layer network, though the supplied passage truncates its formula.
- 2.5 Stability to Perturbation: For any finite-region function, sufficiently small parameter perturbations preserve at least as many linear regions, giving a nonzero-probability neighborhood around the parameter choice.The neighborhood is an epsilon-ball of nonzero volume under a uniform measure on a bounded parameter domain.
3 Deep Rectifier Networks
Deep rectifier networks admit a tighter lower bound on linear regions than earlier analyses, while a folding construction explains how depth replicates computations across input-space regions.
- 2^N bounds the maximal number of linear regions for any rectifier network with N hidden units.
- Illustration of the Construction: Alternating sums of rectifiers fold each input coordinate into p linear regions across equal-length intervals.The construction uses p = floor(n/n0) rectifiers per input coordinate and ignores the remainder.
- Illustration of the Construction: p^n0 hypercubes arise because the folded map identifies repeated input-space strips along all n0 coordinates.The resulting function is locally symmetric about hyperplanes at integer coordinate values.
- Formal Result: The construction extends to L hidden layers with widths ni ≥ n0, yielding the paper’s lower bound for deep rectifier networks.The layer-wise replication composes the identified regions across depth.
- Formal Result: Deep models produce exponentially many regions in L and polynomially many in width n, outperforming shallow models with nL hidden units.The advantage remains substantial for small L and n, and is also exponential when measured per parameter.
4 Deep Maxout Networks
The maxout analysis characterizes region formation through upper envelopes and hyperplane arrangements, then shows that depth yields exponential growth in linear regions.
- A rank-k maxout unit has at most k linear regions because its output is the upper envelope of k linear functions.Each function can uniquely maximize on a neighborhood, attaining k regions.
- Intersecting m maxout units gives a trivial upper bound of k^m regions, while parallel-hyperplane arrangements attain k^m when m ≤ n.For m > n, the same construction yields k^n regions.
- A rank-k maxout unit identifies k cones associated with the positive half-rays of its k gradient vectors.
- k^L−1 k^n0 lower-bounds the regions computable by a width-n0, rank-k maxout network with L layers.
- Deep maxout region counts grow exponentially with layers and faster than shallow models with the same number of units.The exponential behavior also holds with respect to the number of network parameters.
- The rectifier construction is not generally computable by maxout networks, except in the rank-2 case.
5 Conclusions and Outlook
The paper concludes that piecewise-linear depth creates exponentially many replicated input regions, while noting broader applicability and unresolved questions about parameter-space structure.
- Deep piecewise-linear networks recursively identify input pieces, exponentially replicating higher-layer computations across input regions.
- Replication makes deep functions complex but intrinsically rigid, which may help them generalize better than shallow models.
- The framework applies beyond the analyzed models, including convolutional networks whose pooling recursively identifies image patches.
- The parameter space is partitioned according to the linear-region structures of the resulting functions, but these combinatorial structures are generally hard to compute.The paper leaves open whether many parameter-space regions correspond to functions with a given number of linear regions.
A Identification of Input-Space Neighborhoods
The identification argument counts input-space preimages of output neighborhoods to lower-bound the full network’s number of linear regions.
- Each output neighborhood has input-space preimages under the activations computed by the first L layers.
- Distinct output neighborhoods with distinct final-layer regions force their preimages into different regions of the entire network.Summing the preimage counts yields a lower bound on the network’s total linear regions.
B Rectifier Networks
The rectifier construction divides the network into coordinate-specific parts that repeatedly fold each input coordinate into a common unit interval. Composing these foldings creates many input neighborhoods mapped to the same effective output cube, after which the final layer partitions that cube with hyperplanes.
- Construction: The first L−1 layers are divided into n0 independent parts, each sensitive to one input coordinate and folding it once per unit per layer.The construction chooses each part’s parameters so its foldings map successive intervals into (0,1).
- Construction: Each layer forms a grid of ∏i=1^n0 pi regions, and each region maps to the n0-dimensional unit cube for reuse by the next layer.Repeating this construction multiplies the number of identified regions layer by layer.
- Region count: The first L−1 layers map multiple input-space neighborhoods onto the open cube (0,1)^n0, with the count determined by the group sizes pl,i.The passage identifies pl,i as the number of units in group i of layer l.
- Region count: The last hidden layer can partition the effective neighborhood (0,1)^n0 using an arrangement of nL hyperplanes in general position.This supplies the final partition after the preceding layers create the repeated effective inputs.
- Region count: Balancing each layer’s units across the n0 groups gives the theorem’s bound when all remainders vanish and a larger count otherwise.The group sizes use floor division, assigning the remainder units to selected groups.
C Our Bounds in terms of Parameters
The paper rewrites linear-region bounds in terms of network parameters to compare how region complexity scales with model size. Deep models achieve exponential growth in maximal regions with parameters, whereas shallow models grow polynomially.
- Parameter scaling: The bounds are expressed in terms of network parameters to obtain asymptotic growth rates for linear regions per added parameter.The paper frames this as an expansion of earlier parameter-based analyses.
- Parameter scaling: Deep models’ maximal number of linear regions grows exponentially with the number of parameters, while shallow models’ growth is polynomial.This is the section’s direct comparison between depth regimes.
D Maxout Networks
For maxout networks, the paper bounds single-layer complexity through hyperplane arrangements and constructs deep layers that identify exponentially many input regions. The construction yields at least k^(L−1) regions for width n0 and rank k.
- Arrangements: The paper also relates selected maxout constructions to hyperplane arrangements, including the Shi and Catalan arrangements.These examples provide structured arrangements corresponding to particular rank choices.
- Single-layer bounds: A rank-k maxout unit partitions input space through boundaries where pairs of its k affine preactivations are equal.Extending these boundaries to hyperplanes provides an arrangement-based upper-bound strategy.
- Single-layer bounds: A maxout layer’s regions are intersections of unit regions and are loosely upper-bounded by an arrangement of k^2m hyperplanes in n-dimensional space.The arrangement count is polynomial in k and m for fixed input dimension n.
- Deep construction: The construction chooses maxout unit seeds along positive and negative coordinate directions, discarding excess units when k exceeds 2n0.The resulting units are symmetric about selected coordinate hyperplanes and provide separate linear regions.
- Deep construction: The composed units divide input space into cones whose gradients form a basis, so each cone’s image contains an open region in the output space.Independent slight rotations are used to obtain the cones and preserve full-dimensional gradients.
- Deep construction: A maxout layer of width n0 and rank k identifies at least k input regions, and L−1 such layers identify k^(L−1) regions.This is the paper’s stated depth-dependent lower-bound construction.
E Other Networks
The framework extends to convolutional networks with piecewise linear activations because convolution is linear and therefore fits the paper’s preactivation form. The distinction is that convolutional weight matrices belong to restricted classes.
- Convolutional networks: Convolutional networks with piecewise linear activations fall within the analyzed class because convolution is a linear map.Their feature outputs can be written as vectors like the paper’s preactivation outputs.
- Convolutional networks: The remaining difference is that convolutional networks use input weight matrices from restricted classes.Thus the general framework applies while parameter structure remains specialized.
F Sinusoidal Boundary Experiment
The experiment compares shallow and deep MLPs trained on the same synthetic dataset while minimizing optimization effects. The deep model misclassified substantially fewer examples than the shallow model.
- The experiment compared an MLP with one hidden layer of 20 units against an MLP with two hidden layers of 10 units each.Both models were trained on the same synthetic dataset using a conjugate natural gradient.
- 123 examples were misclassified by the shallow model, compared with 24 by the deep model.
- The reported results used the best of several training runs.
G Visualizing the Behaviour of Hidden Units in Higher Layers
The paper visualizes the piecewise linear maps of hidden units by tracing their layer-wise linear pieces and examining distinct responses. These visualizations indicate that higher-layer units can represent abstract invariances and map distinct input points to the same activation.
- Linear-map representation: A piecewise linear function is represented by linear maps defined on distinct regions of the input space.Each region has an affine map fi(x) = u⊤x + c, whose weight vector can be interpreted as a response template.
- Linear-map construction: A hidden unit’s linear map is computed by tracking the selected linear piece through preceding layers and multiplying by the relevant weight-matrix row.The construction applies to rectifier MLPs and can be adapted to other piecewise linear architectures, including maxout convolutional networks.
- Visualization procedure: Different hidden-unit responses are identified by traversing input points and clustering positive activations into four representative linear responses.For higher layers, 20 units per layer were sampled and four were selected using maximal Euclidean distance between their responses.
- Visualization procedure: The TFD rectifier MLP had three hidden layers with 1000, 1000, and 100 units, respectively, and used regularization to obtain cleaner filters.Training used stochastic gradient descent, L2 regularization, dropout in the first two hidden layers, column-wise weight normalization, and sigmoid output units.
- Observed behavior: The visualizations suggest that higher-layer hidden units learn invariance to more abstract translations.The figures compare normalized and unnormalized hidden-layer maps, output-unit maps for seven facial-expression classes, and differences among distinct linear regions.
- Relation to prior visualization: The visualization approach identifies input regions mapping to the same activation rather than approximately inverting the network’s feedforward computation.
- Observed behavior: Three distinct input points were found that produced activation 2.5 for the same third-hidden-layer unit.The points indicate invariance to features other than a wide-open mouth and open eyes; perturbation analysis supports an open set around each point with the same identification.