In this paper, we study the representational power of deep neural networks (DNN) that belong to the family of piecewise-linear (PWL) functions, based on PWL activation units such as rectifier or maxout. We investigate the complexity of such networks by studying the number of linear regions of the PWL function. Typically, a PWL function from a DNN can be seen as a large family of linear functions acting on millions of such regions. We directly build upon the work of Mont´ufar et al. (2014), Mont´ufar (2017), and Raghu et al. (2017) by refining the upper and lower bounds on the number of linear regions for rectified and maxout networks. In addition to achieving tighter bounds, we also develop a novel method to perform exact numeration or counting of the number of linear regions with a mixed-integer linear formulation that maps the input space to output. We use this new capability to visualize how the number of linear regions change while training DNNs.   We have witnessed an unprecedented success of deep learning algorithms in computer vision, speech, and other domains (Krizhevsky et al., 2012; Ciresan et al., 2012; Goodfellow et al., 2013; Hinton et al., 2012) . While the popular deep learning architectures such as AlexNet (Krizhevsky et al., 2012) , GoogleNet (Szegedy et al., 2015) , and residual networks (He et al., 2016) have shown record beating performance on various image recognition tasks, empirical results still govern the design of network architecture in terms of depth and activation functions. Two important practical considerations that are part of most successful architectures are greater depth and the use of PWL activation functions such as rectified linear units (ReLUs). Due to the large gap between theory and practice, many researchers have been looking at the theoretical modeling of the representational power of DNNs (Cybenko, 1989; BID0 Pascanu et al., 2014; Montúfar et al., 2014; BID4 Eldan & Shamir, 2016; Telgarsky, 2015; Mhaskar et al., 2016; Raghu et al., 2017; Montúfar, 2017) .Any continuous function can be approximated to arbitrary accuracy using a single hidden layer of sigmoid activation functions (Cybenko, 1989 ). This does not imply that shallow networks are sufficient to model all problems in practice. Typically , shallow networks require exponentially more number of neurons to model functions that can be modeled using much fewer activation functions in deeper ones (Delalleau & Bengio, 2011) . There have been a wide variety of activation functions such as threshold (f (z) = (z > 0)), logistic (f (z) = 1/(1 + exp(−e))), hyperbolic tangent (f (z) = tanh(z)), rectified linear units (ReLUs f (z) = max{0, z}), and maxouts (f (z 1 , z 2 , . . . , z k ) = max{z 1 , z 2 , . . . , z k }). The activation functions offer different modeling capabilities. For example, sigmoid networks are shown to be more expressive than similar-sized threshold networks (Maass et al., 1994) . It was recently shown that ReLUs are more expressive than similar-sized threshold networks by deriving transformations from one network to another (Pan & Srikumar, 2016) .The complexity of neural networks belonging to the family of PWL functions can be analyzed by looking at how the network can partition the input space to an exponential number of linear response regions (Pascanu et al., 2014; Montúfar et al., 2014) . The basic idea of a PWL function is simple: we can divide the input space into several regions and we have individual linear functions for each of these regions. Functions partitioning the input space to a larger number of linear regions are considered to be more complex ones, or in other words, possess better representational power. In the case of ReLUs, it was shown that deep networks separate their input space into exponentially more linear response regions than their shallow counterparts despite using the same number of activation functions (Pascanu et al., 2014) . The results were later extended and improved (Montúfar et al., 2014; Raghu et al., 2017; Montúfar, 2017; BID1 . In particular, Montúfar et al. (2014) shows both upper and lower bounds on the maximal number of linear regions for a ReLU DNN and a single layer maxout network, and a lower bound for a maxout DNN. Furthermore, Raghu et al. (2017) and Montúfar (2017) improve the upper bound for a ReLU DNN. This upper bound asymptotically matches the lower bound from Montúfar et al. (2014) when the number of layers and input dimension are constant and all layers have the same width. Finally, BID1 improves the lower bound by providing a family of ReLU DNNS with an exponential number of regions given fixed size and depth.In this work, we directly improve on the results of Montúfar et al. (Pascanu et al., 2014; Montúfar et al., 2014; Montúfar, 2017) and Raghu et al. (Raghu et al., 2017) in better understanding the representational power of DNNs employing PWL activation functions. The representational power of a DNN can be studied by observing the number of linear regions of the PWL function that the DNN represents. In this work, we improve on the upper and lower bounds on the linear regions for rectified networks derived in prior work (Montúfar et al., 2014; Raghu et al., 2017; Montúfar, 2017; BID1 and introduce a first upper bound for multi-layer maxout networks. We obtain several valuable insights from our extensions.Our ReLU upper bound indicates that small widths in early layers cause a bottleneck effect on the number of regions. If we reduce the width of an early layer, the dimensions of the linear regions become irrecoverably smaller throughout the network and the regions will not be able to be partitioned as much. Moreover, the dimensions of the linear regions are not only driven by width, but also the number of activated ReLUs corresponding to the region. This intuition allowed us to create a 1-dimensional construction with the maximal number of regions by eliminating a zero-dimensional bottleneck. An unexpected and useful consequence of our result is that shallow networks can attain more linear regions when the input dimensions exceed the number of neurons of the DNN.In addition to achieving tighter bounds, we use a mixed-integer linear formulation that maps the input space to the output to show the exact counting of the number of linear regions for several small-sized DNNs during the training process. In the first experiment, we observed that the number of linear regions correctly classifying each digit of the MNIST benchmark increases and vary in proportion to the depth of the network during the first training epochs. In the second experiment, we count the total number of linear regions as we vary the width of two layers with a fixed number of neurons, and we experimentally validate the bottleneck effect by observing that the results follow a similar pattern to the upper bound that we show.Our current results suggest new avenues for future research. First, we believe that the study of linear regions may eventually lead to insights in how to design better DNNs in practice, for example by further validating the bottleneck effect found in this study. Other properties of the bounds may turn into actionable insights if confirmed as these bounds get sufficiently close to the actual number of regions. For example, the plots in Appendix O show that there are particular network depths that maximize our ReLU upper bound for a given input dimension and number of neurons. In a sense, the number of neurons is a proxy to the computational resources available. We also believe that analyzing the shape of the linear regions is a promising idea for future work, which could provide further insight in how to design DNNs. Another important line of research is to understand the exact relation between the number of linear regions and accuracy, which may also involve the potential for overfitting. We conjecture that the network training is not likely to generalize well if there are so many regions that each point can be singled out in a different region, in particular if regions with similar labels are unlikely to be compositionally related. Second, applying exact counting to larger networks would depend on more efficient algorithms or on using approximations instead. In any case, the exact counting at a smaller scale can assess the quality of the current bounds and possibly derive insights for tighter bounds in future work, hence leading to insights that could be scaled up.
We empirically count the number of linear regions of rectifier networks and refine upper and lower bounds. This paper presents improved bounds for counting the number of linear regions in ReLU networks.