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]:
We have posted a new revision (v5) of out manuscript. In this revision we address the reviewers' comments. 
The most important changes are: 

* We reduced the length of the introduction and moved some of the detailed descriptions or intuitions near the relevant propositions or theorems. 

* We fixed some shortcomings of an example that was given in the Introduction of the previous version of the manuscript. 

* We added missing formal definitions and worked on making our notation more consistent and rigorous. 

* We overworked the proof of the former Theorem 8 (now Theorem 1). We included new diagrams illustrating the steps of the proof. We also included an example (Example 1) illustrating how the components of the proof are put together in the proof. 

* We added a new section (Section 5) describing a construction of weights for which deep models exhibit more linear regions than shallow ones, even for a small number of hidden layers. In this section we also illustrate specific functions that can be represented with this choice of weights. 

* We formulated bounds in terms of the number of regions per parameter computable by rectifier networks. These bounds behave similarly to the bounds expressed in terms of the number of units, showing that deep models are exponentially more efficient than shallow models.