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]:
This paper studies the representation power of deep nets with piecewise linear activation functions. The main idea is to show that deep net with the same number units can represent (in terms of generating linear regions) more complex mappings than the shallow model.

This is an interesting paper: it leverages known results in arranging hyperplanes in the space and then cleverly show how those can be used to show how linear regions can be learnt by multiple layers. 

While the theoretical results seem right, I could not help but wondering whether the comparison is 'fair':  using the same number of units does not necessarily imply the deep net is 'restricted' in any way -- in fact, the deep net has more parameters than the shallow model. Is not that enough to argue (at least qualitatively) that deep net must have more representation power than the shallow model? (Of course, the value of the analysis is to show more precisely how many regions there are.)

Additionally, the learning process does not necessarily mean that the deep net indeed constructs that many regions --- thus, purely comparing the number of regions is unlikely to explain how well the model is able to generalize well than shallow model or how the model is prevented from overfitting.

Nonetheless, the paper presents a novel direction to pursuit to instigate further research.