On the number of inference regions of deep feed forward networks with piece-wise linear activations
Authors: Razvan Pascanu, Guido F. Montufar, Yoshua Bengio
ICLR 2014

Abstract: This paper explores the complexity of deep feed forward networks with linear presynaptic 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 piece-wise linear functions based on computational geometry. We look at a deep (two hidden layers) rectifier multilayer perceptron (MLP) with linear outputs units and compare it with a single layer version of the model. In the asymptotic regime as the number of units goes to infinity, if the shallow model has $2n$ hidden units and $n_0$ inputs, then the number of linear regions is $O(n^{n_0})$. A two layer model with $n$ number of hidden units on each layer has $Omega(n^{n_0})$. We consider this as a first step towards understanding the complexity of these models and argue that better constructions in this framework might provide more accurate comparisons (especially for the interesting case of when the number of hidden layers goes to infinity).


Peer review:
[Review]:
David, thanks a lot for your comments. We will definitely consider them in the next version of the paper. I have to wonder however, which version of the paper did you look at? Version 2 (which is online since 6th Jan) does not have an equation 13, while the first draft did. My hope is that the version 2, that is online, already
answers most of your questions. Note that we have a different construction that changes much of the flow of the paper as well as 
the final result. 

I would quickly try to summarize some specific answers to your questions:

 (1) Regarding the scope of the paper. We do not generalize Zaslavsky's Theorem to scenarios that arise in deep models, as you suggest.  For a single layer rectifier MLP it turns out that each hidden unit partitions the space using a hyperplane. This means that the number of regions we have is the number of regions you can get from an arrangement of $n$ hyperplanes. The answer to this question is given by Zaslavsky's Theorem. This offers as an upper bound to the maximal number of regions a single hidden layer model has. To make our point (that deep models are more efficient) we only need to show now that there exist deep models that result in more regions. We do so by constructing a specific deep model for which we can compute lower bound to the number of linear regions it generates. Asymptotically this lower bound is much larger than the maximal number of regions a single layer model has. 

 (2) 'region'/'region of linearity'/'input space partition space' means the same thing. It is a connected region of the input space U, such that within this region every hidden unit either stays positive or is equal to 0. Or in other words, within this region the MLP is a linear function with respect to its input.

 (3) Regarding figure 2, we do use a new construction now that is depicted in more detail. 

 (4) Proposition 8 and 9 have been replaced completely. Proposition 8 describes a lower bound on how many new regions you can get within a layer, given the number of regions you have generated up to that layer. Proposition 9 used proposition 8 to give a lower bound on the total number of regions of a deep model.

 (5) Regarding the statement about the output activation function. We simply meant to say that it is sufficient to study models with linear output activation function to get a sense for MLPs with sigmoids or softmax output activations. To see this do the following. Consider you have some rectifier MLP with sigmoids at the output layer, and some target function $f$. Let $s$ stand for the sigmoid activation function. To get a sense of how well we can approximate $f$, we can look at how well we can approximate $s^{-1}(f)$ with a rectifer MLP that has a linear output activation function.