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]:
Your point is well taken and we are well aware of it, motivating current work that would provide a stronger bound. Within that new construction, even for reasonably models like 3 layers with only 2 n_0 units on each layer, we still get more regions in the deep model than in the shallow one. In that new theorem we count every region of the deep model. In the proof presented in the paper, we only look at a lower bound on the maximal number of regions for the deep model, a bound that is not necessarily tight. The reason is that we only count certain regions and ignore the rest. Unfortunately counting all regions for the deep model construction given in the paper is difficult. 

The second comment we would like to make is that we recover a high ratio of n to n_0 if the data live near a low-dimensional manifold (effectively like reducing the input size n_0). One-layer models can reach the upper bound of regions only by spanning all the dimensions of the input. That is, for any subspace of the input we can not concentrate most of the regions in that subspace. If, as commonly assumed, data live near a lower dimensional manifold, then we care only about the number of regions we can get in the directions of that manifold. One way of thinking about it is if you do a PCA on your data. You will have a lot of directions (say on MNIST) where few variations are seen in the data (and if you see some, it is mostly due to noise that you want to ignore). In such a situation you care about how many regions you have within the directions in which the data do change. In such situations n >> n_0, making the proof of the paper more relevant.

Lastly, we'll argue that the paper is making an important contribution to the asymptotic case but covers neural network architectures (with rectifiers) that were not previously covered. The paper is showing an important representational advantage from using deep models versus shallow ones, at least asymptotically. This kind of result is important to motivate the importance of deep models. Although there are previous results with the same objective, they have not been with the kind of commonly used non-linearity (rectified linear units) that we are able to cover here.