On the Number of Linear Regions of Deep Neural Networks
By Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, Yoshua Bengio. 2014
1,419 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Model Architectures, Scaling & Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Quoc V. Le
- Dacheng Tao
- Mohit Bansal
- Percy Liang
- Sergey Levine
- Jianfeng Gao
- Ruslan Salakhutdinov
In Model Architectures
- Yoshua Bengio
- Quoc V. Le
- Greg Yang
- Kyunghyun Cho
- Aaron C. Courville
- Dacheng Tao
- Sam Schoenholz
- J. Urgen Schmidhuber
In Scaling & Learning Theory
- Greg Yang
- Sam Schoenholz
- Yuanzhi Li
- Jeffrey Pennington
- Quanquan Gu
- Jascha Narain Sohl-Dickstein
- Surya Ganguli
- Yoshua Bengio
Citations in the corpus
- Deep Residual Learning for Image Recognition (2015, neutral): “See [28].”
- Training Very Deep Networks (2015, background): “This enables the study of extremely deep and efficient architectures.”
- FitNets: Hints for Thin Deep Nets (2014, background): “…of depth has been verified (1) theoretically: deep representations are exponentially more expressive than shallow ones for some families of functions (Montufar et al., 2014); and (2) empirically: the two top-performers of ImageNet use deep convolutional networks with 19 and 22 layers, respectively…”
- Wide Residual Networks (2016, background): “The superiority of deep networks has been spotted in several works in the recent years [3, 20].”
- Learning Energy-Based Spatial-Temporal Generative ConvNets for Dynamic Patterns (2019, background): “As a result, the scoring function fðI; uÞ is piecewise linear [25], and each linear piece is defined by the mul-”
- A Theory of Generative ConvNet (2016, background): “It makes the ConvNet scoring function piecewise linear (Montufar et al., 2014).”
- High Fidelity Visualization of What Your Self-Supervised Representation Knows About (2021, background): “In fact, the regions ω ∈ Ω are often extremely localized in the input space, especially as the architecture involves many layers (Montúfar et al., 2014; Balestriero et al., 2019).”
- The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, background): “their ability to build complex functions with a much smaller number of parameters than needed for shallow networks [9–13].”
- ReZero is All You Need: Fast Convergence at Large Depth (2020, background): “Networks with a depth of L layers and width w often have an expressive power that scales exponentially in depth, but not in width [12, 5].”
- Sharp Minima Can Generalize For Deep Nets (2017, background): “From a representational point of view, it has been argued that deep networks can efficiently approximate certain functions (e.g. Montufar et al., 2014; Raghu et al., 2016).”
- Efficient Formal Safety Analysis of Neural Networks (2018, background): “While piece-wise linear pieces can be partitioned into two linear constraints and efficiently check separately, these linear pieces grow exponentially with the number of nodes in the network [19, 21].”
- Robust Large Margin Deep Neural Networks (2016, background): “On the other hand, it was shown in [10] that a deep network can divide the space into an exponential number of sets, which can not be achieved by shallow networks that use the same number of parameters.”
- Methods for interpreting and understanding deep neural networks (2017, background): “More specifically, they are subject to the problem of shattered gradients [7, 49] which characterizes deep ReLU networks: The number of piecewise-linear regions tends to grow very quickly with depth, and thus cause the gradient to become strongly discontinuous and loose its information content.”
- Why ReLU Networks Yield High-Confidence Predictions Far Away From the Training Data and How to Mitigate the Problem (2018, background): “Note that explicit upper bounds on the number of linear regions have been given [25].”
- Sorting out Lipschitz function approximation (2018, background): “Montufar et al. [34] provide an in-depth analysis of the expressivity of neural networks built with activations that can perform folding.”
- Representing smooth functions as compositions of near-identity functions with implications for deep network optimization (2018, background): “A number of authors have investigated how using deep architecture affects the set of functions computed by a network (see Montufar et al., 2014; Telgarsky, 2015; Poole et al., 2016; Mhaskar et al., 2016).”