Source-linked AI summary
On the number of response regions of deep feed forward networks with piece-wise linear activations
Razvan Pascanu, Guido Montufar, Yoshua Bengio
TL;DR
The paper asks how the representational complexity of deep rectifier networks compares with shallow networks, given limited theoretical tools for analyzing deep compositions. It uses computational geometry to count response regions and finds that deep, narrow rectifier MLPs can generate substantially more regions, including more regions per parameter, while identifying extensions for future analysis.
Problem
Theoretical results on the representational power of deep models are limited, especially for networks using nonlinear compositions and piecewise linear activations.
Method
The paper counts the linear regions defined by deep and shallow rectifier MLPs, treating these regions as a computational-geometry measure of model flexibility.
Results
Deep and narrow rectifier MLPs can generate many more response regions per parameter than shallow counterparts, exponentially more with depth and at least polynomially more with width.
Takeaways & Limitations
Response-region counting provides a framework for comparing piecewise linear models and relating their representational flexibility to approximation of curved shapes.
Takeaways & Limitations
The framework is presented as a first step, with extensions to constraints such as shared weights and to convolutional or maxout networks left for future study.
Abstract
from arXiv · showhide
This paper explores the complexity of deep feedforward networks with linear pre-synaptic couplings and rectified linear activations. This is a contribution to the growing body of work contrasting the representational power of deep and shallow network architectures. In particular, we offer a framework for comparing deep and shallow models that belong to the family of piecewise linear functions based on computational geometry. We look at a deep rectifier multi-layer perceptron (MLP) with linear outputs units and compare it with a single layer version of the model. In the asymptotic regime, when the number of inputs stays constant, if the shallow model has $kn$ hidden units and $n_0$ inputs, then the number of linear regions is $O(k^{n_0}n^{n_0})$. For a $k$ layer model with $n$ hidden units on each layer it is $Ω(\left\lfloor {n}/{n_0}\right\rfloor^{k-1}n^{n_0})$. The number $\left\lfloor{n}/{n_0}\right\rfloor^{k-1}$ grows faster than $k^{n_0}$ when $n$ tends to infinity or when $k$ tends to infinity and $n \geq 2n_0$. Additionally, even when $k$ is small, if we restrict $n$ to be $2n_0$, we can show that a deep model has considerably more linear regions that a shallow one. We consider this as a first step towards understanding the complexity of these models and specifically towards providing suitable mathematical tools for future analysis.
1 Introduction
The paper addresses limited theoretical analysis of deep rectifier networks by using computational geometry to compare their response-region complexity with shallow models. It argues that rectifier compositions can yield substantially more linear regions while retaining structured representations.
- Deep models are hypothesized to represent some functions exponentially more efficiently than shallow counterparts.
- Theoretical analysis of deep models remains limited because composing nonlinear functions makes mathematical treatment difficult.
- The paper analyzes deep multilayer perceptrons with rectifier units, exploiting their piecewise linear structure.
- Response regions count the linear pieces available for approximating nonlinear functions, but their slopes are not necessarily independently learnable.
- The framework may extend to other piecewise linear activations and architectures, including maxout and rectifier convolutional networks.
- Deep models can produce many more linear regions than shallow models with the same number of hidden units.
2 Preliminaries
The paper defines rectifier feedforward networks and response regions, then formalizes how layerwise piecewise linear structure determines network complexity. It also notes that output dimensionality does not change the maximal number of realizable regions.
- A rectifier feedforward network is a layered MLP whose hidden units apply rect(s) = max{0, s} after affine transformations.
- The output layer is linear and computes unrectified linear combinations of the final hidden activations.
- The represented functions are continuous piecewise linear maps from the input space to the output space.
- A response region is a maximal connected open input subset on which the network function is linear.
- Layer response regions arise from intersections of the coordinate functions’ linearity regions.
- The number of linear output units does not affect the maximal number of response regions a rectifier network can realize.
3 One hidden layer
For one-hidden-layer rectifier MLPs, activation boundaries form hyperplane arrangements in the input space. Their maximal response-region count is therefore obtained from arrangements in general position.
- Each hidden rectifier unit switches between zero and a linear mode across a hyperplane in the input space.
- The response regions of a single-hidden-layer MLP equal the regions formed by its hidden units’ hyperplanes.
- A hyperplane arrangement is a finite set of hyperplanes in a common Euclidean space, whose regions are connected components of their complement.
- General-position arrangements realize the maximal possible number of regions for a fixed number of hyperplanes.
- Adding a new line intersecting m existing lines in general position creates m + 1 new regions.
- The one-hidden-layer model’s maximal region count is given by the maximal arrangement of n1 hyperplanes in n0-dimensional space.
4 Multiple hidden layers
The paper constructs deep rectifier networks by arranging active-unit regions and mapping them into a shared ball so later-layer partitions are replicated across inputs. This yields exponentially many subdivisions across layers and establishes a lower bound on response regions.
- Region construction: Any arrangement can be scaled and shifted so that all its regions intersect a chosen unit ball.The transformation scales by r/(2d) and shifts by the ball center.
- Layer composition: The first hidden layer activates only the units associated with each input region, while the intermediary map sends every such region to a set containing the unit ball.Consequently, the later-layer computation can be replicated across all those input regions.
- Region construction: Proposition 4 provides arrangements where every consecutive list of hyperplanes corresponds to a region with exactly those units active.The construction uses general-position lines in two dimensions and extends it to higher-dimensional arrangements.
- Layer composition: Affine maps with shared bias can map multiple regions with non-empty interiors to sets containing the same unit ball.This lets a subsequent rectifier layer apply a common arrangement within each earlier input region.
- Main result: A later rectifier layer partitions the shared ball inside every input region, producing exponentially many pieces as the number of layers increases.Theorem 1 formalizes this construction as a lower bound on the network’s maximal number of linear regions.
5 A special class of deep models
The section constructs deep rectifier models that repeatedly map equivalent inputs to shared activations, multiplying later-layer partitions across the input space. With width 2n_0 per layer, this yields many response regions even for few layers.
- Construction: Width 2n_0 is used in each hidden layer to construct an efficient deep model with many response regions.The restriction is designed to establish a strong region count with relatively few hidden layers.
- Recursive replication: Applying the absolute-value construction repeatedly recursively divides the input space while preserving shared representations across regions.The same procedure is applied to the image of the preceding absolute-value layer.
- Construction: Each rectifier pair computes the absolute value of an input coordinate, mapping every input quadrant to the positive quadrant.This creates equivalent activations for inputs from different quadrants.
- Recursive replication: A later-layer partition is copied into every input-space region that produces the same activation for that layer.Thus, a partition created near the output can be replicated across earlier equivalent regions.
- Region count: For n_0 inputs and k hidden layers of width 2n_0, Theorem 2 gives a constructive lower bound on the maximal number of linear regions.The theorem formalizes the repeated replication construction; its displayed formula is incomplete in the supplied passage.
- Region count: For n_0 = 2, shallow models with 4n_0 and 6n_0 units reach at most 37 and 79 regions, whereas equivalent deep models reach 44 and 176.The comparisons use two- and three-layer deep models, respectively.
6 Discussion and conclusions
The paper proposes response-region counting as a computational-geometry framework for analyzing piecewise-linear network expressiveness and comparing deep with shallow models. It reports substantially greater region counts per parameter for deep models while retaining linear output units as the analyzed setting.
- Framework: Response regions quantify how well piecewise-linear networks can approximate arbitrary curved shapes.The paper calls these regions of linearity and uses their count as an expressiveness measure.
- Deep–shallow comparison: Deep and narrow rectifier MLPs generate many more regions of linearity than shallow counterparts with the same computational units or parameters.The comparison is made between the two model classes using response-region counts.
- Deep–shallow comparison: Deep models can produce exponentially more regions per parameter as hidden-layer count k increases and at least order (k −2) polynomially more as width n increases.The paper also reports deep models that use fewer parameters while producing more linear regions.
- Scope and extensions: The analysis considers linear output units, with nonlinear output activations handled indirectly by modeling a suitable pre-activation function.For non-invertible activations such as softmax, the paper suggests choosing one compatible pre-image, such as log(ftarg).
- Scope and extensions: The framework is presented as extensible to shared-weight constraints, maxout networks, and convolutional networks with rectifier activations.These are proposed directions for applying the response-region approach beyond the analyzed setting.
A Asymptotic
The asymptotic analysis compares response-region counts and parameter efficiency for deep and shallow rectifier MLPs with fixed input and output dimensions. Deep models gain increasingly many regions per parameter as width or depth grows.
- Response regions: Deep models’ response-region advantage grows exponentially with hidden layers when width and input dimension are fixed.For fixed n0 and fixed width n > 2n0, the factor floor(n/n0)^(k-1) grows exponentially in k.
- Response regions: For fixed depth and input dimension, deep models’ response-region advantage grows polynomially with width.The asymptotic deep-model factor floor(n/n0)^(k-1) is polynomial in n when k and n0 are fixed.
- Parameter counts: A deep model with k hidden layers of width n has parameter count O(kn^2).The dominant contribution comes from the n × n weight matrices between hidden layers.
- Parameter counts: A shallow model with kn hidden units has parameter count O(kn).Its parameter count is kn(n0 + nout) + n + nout under fixed input and output dimensions.
- Regions per parameter: Deep models can produce many more response regions per parameter than shallow models, including cases using fewer parameters.The ratio is exponential in k and at least polynomial in n, according to the paper’s asymptotic comparison.