Bounding and Counting Linear Regions of Deep Neural Networks

By Thiago Serra, Christian Tjandraatmadja, Srikumar Ramalingam. 2017

303 citations recorded by the source corpus.

We investigate the complexity of deep neural networks (DNN) that represent piecewise linear (PWL) functions. In particular, we study the number of linear regions, i.e. pieces, that a PWL function represented by a DNN can attain, both theoretically and empirically. We present (i) tighter upper and lower bounds for the maximum number of linear regions on rectifier networks, which are exact for inputs of dimension one; (ii) a first upper bound for multi-layer maxout networks; and (iii) a first method to perform exact enumeration or counting of the number of regions by modeling the DNN with a mixed-integer linear formulation. These bounds come from leveraging the dimension of the space defining each linear region. The results also indicate that a deep rectifier network can only have more linear regions than every shallow counterpart with same number of neurons if that number exceeds the dimension of the input.

How researchers see this paper

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

Citations in the corpus

Continual Learning in Low-rank Orthogonal Subspaces (2020, methodology): “…and assuming that the non-linearity remains in the linear region during the 1We generate a random matrix and apply the Gram–Schmidt process offline, before the continual learning experience begins. training [Serra et al., 2017, Arora et al., 2019], we assume the Jacobian matrix to be an identity.”
Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective (2021, background): “Following Raghu et al. (2017); Serra et al. (2018); Hanin & Rolnick (2019a;b); Xiong et al. (2020), we introduce the definition of activation patterns and linear regions for ReLU networks.”
Understanding Deep Neural Networks with Rectified Linear Units (2016, methodology): “An analysis of this complexity measure is done using integer programming techniques in (Serra et al., 2017).”
Deep neural networks and mixed integer linear optimization (2018, methodology): “We recently became aware that a 0-1 MILP model similar to the one studied in the present paper, has been independently proposed (almost at the same time) in [2, 13, 15].”
Optimization Models for Machine Learning: A Survey (2019, background): “In [187], the aim is to count or bound the number of linear regions that a piecewise linear classifier represented by a DNN can attain.”
Learning Strict Identity Mappings in Deep Residual Networks (2018, background): “Another key contributing factor is the depth, which has been proven to be extremely beneficial in model expressiveness [12, 29, 38].”
Strong mixed-integer programming formulations for trained neural networks (2018, background): “Our contributions are depicted in Figure 1. It serves as a roadmapof the paper. 1.3 Relevant prior work In recent years a number of authors have used MIP formulations to model trained neural networks [19,22,24,29,40,47,54,64,66,67,70,80,81], mostly applying big-M formulation techniques to ReLU-based”
Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study (2017, methodology): “As in [11], the MNIST [2] dataset was used to train a simple DNN with 3 hidden layers with (8, 8, 8) ReLUs, plus a last layer made by 10 units to classify digits “0” to “9”, reaching (after 50 epochs) an accuracy of 93.04% on the test set.”
CAQL: Continuous Action Q-Learning (2019, methodology): “…MIP model have been used in neural network veriﬁcation (Cheng et al., 2017; Lomuscio & Maganti, 2017; Bunel et al., 2018; Dutta et al., 2018; Fischetti & Jo, 2018; Anderson et al., 2019; Tjeng et al., 2019) and analysis (Serra et al., 2018; Kumar et al., 2019), but its application to RL is novel .”
Liquid Time-constant Networks (2020, background): “By establishing a lower-bound for the growth of the trajectory length, one can set a barrier between neural networks of shallow and deep architectures, regardless of any assumptions on the network’s weight configuration [46], unlike many other measures of expressivity [40, 37, 51, 17, 19, 20, 36].”
Model complexity of deep learning: a survey (2021, background): “[92] prove that the maximal number of linear regions of this neural network is lower bounded by”
Limits to Depth Efficiencies of Self-Attention (2020, background): “With that, we point out that a variety of results which directly bound different complexity properties of deep networks have been put forward, shedding light on their operation [Montufar et al., 2014, Bianchini and Scarselli, 2014, Raghu et al., 2017, Serra et al., 2017, Inoue, 2019].”