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]:
The authors of this paper analyse feed-forward networks of linear rectifier units (RELUs) in terms of the number of regions in which they act linearly.  They give an upper bound on the number of regions for networks with a single hidden layer based on known results in geometry, and then show how deeper networks can have a much larger number of regions by constructing examples.   The constructions form the main novel technical contribution, and they seem non-trivial and interesting.

Overall I think this is a good and interesting paper.  It is well written with the notable exception of the proof of theorem 8 and the latter half of the introduction.  In most spots, the math is precise and accessible (to me anyway), the results nicely broken into lemmas, and the diagrams are very useful for providing intuition.

These results can be interpreted as separating networks with a single hidden layer from deep networks in terms of the types of functions they can efficiently compute.  However, number of linear regions is a pretty abstract notion, and it isn't obvious what these results can say about the expressibility by neural nets of functions that we can actually write down.  Do you know of any natural examples of functions that require a finite but super-exponential number of regions?  

Unfortunately, region counting can't say anything about the representability of functions defined on such input spaces of the form S^n0 where S is a finite set, since there are only |S|^n0 input values, and |S|^n0 << n^n0 = region upper bound.


About Theorem 8: 

After hours trying to understand the proof of Theorem 8 I gave up.  However, I was able to use Prop 7, and intuition provided from the diagrams, to prove a slightly different version of Thm 8 myself, and so I think the result is correct, and the proof is probably trying to describe basically the same thing I came up with (except my proof went from the top layer down, instead of the bottom layer up).  So while I don't doubt the correctness of the statement of Thm 8, but the write-up of the proof of Thm 8 needs to be completely redone to be understandable and intuitive.  I don't think you need to make it 100% formal (Prop 7 isn't completely formal either, but it's fine as is), but you need to make it possible to understand with a reasonable amount of effort.




Detailed comments:
---

Title: Please pick a different title.  These are feed-forward networks so calling the regions 'inference regions' doesn't make sense.

Abs: Why is it 'computational geometry' and not just 'geometry'?  What is specifically computational about arrangements of hyperplanes?

Page 2: Missing from the review of previous results about the power networks is all of the work done on threshold units (see the papers of Wolfgang Maass for example, or the seminal of Hajnal et al. proving lower bounds for shallow threshold networks).  Unlike the single paper by Hastad et al. cited, none of these require the weights to be non-negative.  Moreover, these results are hardly non-realistic, as neural networks with sigmoids can easily simulate thresholds, and under certain assumptions the reverse simulation can be done approximately and reasonably efficiently too.

Also missing from this review is recent work of Montufar et al. and Martens et al. analysing the expressive power of generative models (RBMs).

Beginning of page 3: I have a hard time following this high-level discussion.  I think this doesn't belong in the introduction, as it is too long and convoluted.  Instead, I think you should include such discussion as intuition about your formal constructions *as you give them*.  The way it is written right now, the discussion tries to be intuitive, precise, and comprehensive, and it doesn't really succeed at being any of these.


Page 3: You should formally define what you mean by 'hyperplane' and 'arrangement'.   In particular, a hyperplane is the set of points defined by the equation, not the equation itself.  And if an arrangement is taken to be a set of hyperplanes (as per the usual definition), then the statement in Prop 6 isn't formal (although its meaning is still obvious).  In particular, how does a ball S 'intersect' with a set of hyperplanes?  Do you mean that it intersects with the union of the hyperplanes in the arrangement?  I know these are nit-picky points, but if you should try to be technically precise.

Page 5: There is a missing reference here: 'Zaslavsky's theorem (?, Theorem A)'

Page 5: You should explain the concept of general position precisely.  I don't know what 'generic weights' is supposed to mean, the actual definition has to do with lack of colinearity.  You might want to point out that any choice of hyperplanes can be infinitesimally perturbed so that they end up in general position.

Page 6: 'Relative position' is never formally defined, and it's not immediately obvious what it means.

Page 6: The explanation after the statement of Prop 6 is much clearer.  Perhaps you should just prove this (stronger) statement directly, and not the fairly opaque and abstract statement made in Prop 6.

Figure 3: Why are there 2 dotted circles instead of just 1?

Page 7: 'arrangements 2-dimensional essentialization'?

Page 7: '{0,...,n}, a < b'  ->  '{0,...,n} s.t. a < b'

Page 7: What do you mean by 'independent groups of n0 units within the n units of a layer'?  How can a unit be 'within' a unit?

Page 7: What do you mean by an 'enumeration' of a 2-dimensional arrangement?  


Page 9:  Below the statement of prop 7, it was suggested that the construction would be top down, where each group in a lower layer 'duplicates' the number of regions constructed by the layer above.  But the construction given here seems to proceed bottom up... at least in the structure of the proof.  This makes it less intuitive.

Page 9:  The proof starts out very confusingly.  I wasn't able to follow the sentence 'Then we find...'.  These 'groups' haven't been formally defined at this stage, only informally alluded to.  

And I have another question:  how is Prop 7 actually used here?  Merely to establish the existence of network where there is n/n0 regions that each only turn on for different groups Ii?  Isn't it trivial to construct such a thing?  i.e. take the input weights to the units in a given group to be all the same, and make sure the square n0xn0 matrix formed by taking the weight vector for each group is full-rank (e.g. the identity matrix)? 

I suspect the reason this doesn't work is that the dimensions would collapse to 1 since each unit in a group would behave identically.  However, one could then perturb the final expanded weight matrix to get a general position matrix, so that the subspace associated with each group wouldn't collapse to dimension 1.  Is there anything wrong with this?  


Page 9: Don't say 'decompose' here.  'Decompose' implies you already have weights and are decomposing them into factors.  Instead, what you are doing is defining some weights to be a product of particular matrices.

You should emphasize that it is a common V shared by all the i.  This is easy to miss.


Page 9: What does it mean for a linear map to be 'with Ii-coordinates equal to...'?  The 'Ii-coordinates' are the inputs to this map?  The outputs?

Page 9: What is R_i^(1)?  It is never defined.  Is it different from the version without the superscript?  Is it defined implicitly the first time it is used?  If so, what is a 'region of activation values'?

What is very confusing is that you use x to define this function, when I had the impression that x was for the original inputs only.  This isn't consistent with the h notation you use in figure 1 for example.


Page 9: You say that something 'passed through' rho^2 is the 'input' to the second layer.  This is the input to the rectifier units without their weights (which I'm guessing are contained in rho^2)?  Or is it these units with the 'V' factor part of their weights only, but not the 'U' part?  This is all extremely confusing.  Without careful definitions of your notation it requires a lot more work on the part of the reader to understand what is going on. 

Page 9: How can rho_i^(2)(R_i^(1)) be a 'subset' of an subspace that lives in R^(n1)?  rho_i^(2)(R_i^(1)) is going to be a set of vectors living in R^(n0)!


Page 10:  What do you mean when you say that 'this arrangement is repeated once in each region'?  What does it mean for an arrangement to be 'repeated in a region'? 

I feel like the proof becomes mostly a proof-by-diagram as this point.  Maybe you should have started off with this kind of diagram and the intuition of 'duplicating regions', explaining how composing piece-wise linear functions can achieve this kind of thing (which is really the critical point that gets glossed over), and then proceeding to show that you could formally construct each 'piece' required to do this.   And you should have done the construction starting at the top layer going down.

Having reconstructed the proof in a way that I actually understood it, it seemed that one could also proof that one can (prod_{i=1}^{k-1} n_i)/2^{k-1} * sum_i=0^2 (n_k choose i) regions, which in some cases might be a lot larger than the expression you arrived at.   Unlike your Thm 8 does, this version would actually need to use the fact the constructions are 2-dimensional in Prop 7.

Page 11:  The asymptotic analysis is just very routine and uninteresting computations and should be in the appendix.  It breaks the flow of your paper.  I would much prefer to see more detailed commentary about the implications of Thm 8.