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 is a very interesting and relevant paper, attempting to prove that
a deep neural net composed of rectified linear units and a linear output
layer is potentially significantly more powerful than a single layer
net with the same number of units.

A strength of the paper is its constructive approach, building up
an understanding of the expressiveness of a model, in terms of the
number of regions it represents. It is also notable that the authors pull 
in techniques from computational geometry for this construction.

But there are several problems with the paper.  The writing is unclear,
and overall the paper feels like a preliminary draft, not ready for prime 
time.

The introduction can be tightened up.  A more significant comment
concerns the important attempt to give some intuition, at the top of
page 3.  The paragraph starting with 'Specifically' doesn't make sense
to me. How can all but one hidden unit be 0 for different intervals
along the real line?  Each hidden unit will be active above (or below)
its threshold value, so many positive ones will be active at the same
time.  We could compose two hidden units to construct one that is only
active within an interval in R, but I don't see how to do this in one
layer.  I must be missing something simple here. 

I think the basic intuition is that a higher-level unit can act as an
OR of several lower level regions, and gain expressivity by repeating
its operation on these regions, is the idea.  But the construction is
not clear.  Also, one would expect that the ability to represent AND
operations would also lead to significant expressivity gains.  Is this
also part of the construction?  These basic issues should be clarified.

In addition, it would be very helpful to have some concrete example
of a function that can be computed by a deep net of the sort analyzed
here, which cannot be computed by a shallow net of the same size.  
As it stands the characterization of the difference between the deep 
and equivalent one-layer network is too abstract to be very compelling.

I also found the proof of Theorem 8 very hard to understand.  This
is not a key problem, as the authors do a good job building up to
this main theorem, in sections 3 and 4.  But it does mean that I am
not confident that the proof is correct.

Finally, I would recommend exploring the relationship between the ideas
in this paper and the extensive work in circuit complexity that deals 
with multi-level circuits, for example the paper by Hajnal et al on 'Threshold circuits of bounded depth'.