On the number of response regions of deep feed forward networks with piece-wise linear activations

By Razvan Pascanu, Guido Montúfar, Yoshua Bengio. 2013

285 citations recorded by the source corpus.

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 $\Omega(\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.

Subfields: Cognitive Neuroscience, Electrical and Electronic Engineering, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Cognitive Neuroscience

In Electrical and Electronic Engineering

In Model Architectures

Citations in the corpus

On the Number of Linear Regions of Deep Neural Networks (2014, methodology): “Our result is a significant improvement over the bound Ω ( (/n0) L−1 n0 ) obtained by Pascanu et al. (2013). In particular, our result demonstrates that even for small values of L and n, deep rectifier models are able to produce substantially more linear regions than shallow rectifier models. Additi”
How to Construct Deep Recurrent Neural Networks (2013, methodology): “RNNs have been successfully used for various task such as language modeling (see, e.g., Graves, 2013; Pascanu et al. , 2013a; Mikolov, 2012; Sutskever et al. , 2011), learning word embeddings (see, e.g., Mikolov et al. , 2013a), online handwritten recognition (Graves et al. , 2009) and speech…”
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].”
On the Expressive Power of Deep Neural Networks (2016, background): “Even if the weight values used in these constructions are robust to small perturbations (as in (Pascanu et al., 2013; Montufar et al., 2014)), the functions that arise from these constructions tend toward extremal properties by design, and there is no evidence that a network trained on data ever…”
Understanding intermediate layers using linear classifier probes (2016, background): “rain the model. The authors like to refer to that phenomenon as garbage forwardprop, garbage backprop, in reference to the popular concept of garbage in, garbage out in computer science. The works of Pascanu et al. (2013) and Montufar et al. (2014) explore the possibility of counting the exponential”
Cooperative Training of Descriptor and Generator Networks (2016, background): “Then g ( X ; W G ) is linear on each piece (Pascanu et al., 2013), so that the model is piecewise linear factor analysis, and P G ( Y ; W G ) is essentially piecewise Gaussian.”
Inductive biases for deep learning of higher-level cognition (2020, background): “There are theoretical arguments about why distributed representations can bring a potentially exponential advantage (Pascanu et al., 2013), if this matches properties of the underlying data distribution.”
Deep convolutional neural networks for eigenvalue problems in mechanics (2018, background): “In the machine learning community, it has been well established that deep CNN models signiﬁcantly overpower both shallow and deep MLPs due to the following[23, 24, 25, 26]: • Shallow networks show poorer generalization capabilities for highly nonlinear input-output relationships.”
SSN: Learning Sparse Switchable Normalization via SparsestMax (2019, background): “To uncover the great success in practice of deep models in recent years, researchers further make efforts to understand why deep networks can have superior expressive power than shallow ones (Advani and Saxe 2017; Pascanu et al. 2013).”
Nonparametric regression using deep neural networks with ReLU activation function (2017, unknown): “Composition : Suppose that f ∈ F (L, p ) and g ∈ F (L (cid:21) , p (cid:21) ) with p L + 1 = p 0 .”
Sensitivity and Generalization in Neural Networks: an Empirical Study (2018, background): “It was argued in (Pascanu et al., 2013; Mont ´ ufar et al., 2014) that an upper bound to the number of linear regions scales exponentially with depth but polynomially in width, and a speciﬁc construction was examined.”
On the Expressive Power of Overlapping Architectures of Deep Learning (2017, methodology): “, 1993), and the more recent studies covering the types of networks used in practice (Pascanu et al., 2013; Montúfar et al., 2014; Eldan and Shamir, 2016; Cohen et al., 2016a; Cohen and Shashua, 2016; Telgarsky, 2016; Safran and Shamir, 2016; Raghu et al., 2016; Poole et al., 2016).”
Liquid Time-constant Networks (2020, background): “In this context, [37] and [40] suggested to count the number of linear regions of neural networks as a measure of expressivity, [13] showed that there exists a class of radial functions that smaller networks fail to produce, and [43] studied the exponential expressivity of neural networks by…”
PredRNN: A Recurrent Neural Network for Spatiotemporal Predictive Learning (2021, background): “It is largely inspired by the theoretical argument that distributed representation has a great potential to match the underlying properties of data distribution [22].”
Understanding Locally Competitive Networks (2014, methodology): “A version of this paper was submitted to NIPS 2014 on 06-06-2014”