A General Computational Framework to Measure the Expressiveness of Complex Networks using a Tight Upper Bound of Linear Regions
Authors: Yutong Xie
Gaoxiang Chen
Quanzheng Li
Venue:  (2021)

Abstract: The expressiveness of deep neural network (DNN) is a perspective to understand the surprising performance of DNN. The number of linear regions, i.e. pieces that a piece-wise-linear function represented by a DNN, is generally used to measure the expressiveness. And the upper bound of regions number partitioned by a rectifier network, instead of the number itself, is a more practical measurement of expressiveness of a rectifier DNN. In this work, we propose a new and tighter upper bound of regions number. Inspired by the proof of this upper bound and the framework of matrix computation in \citet{hinz2019framework}, we propose a general computational approach to compute a tight upper bound of regions number for theoretically any network structures (e.g. DNN with all kind of skip connections and residual structures). Our experiments show our upper bound is tighter than existing ones, and explain why skip connections and residual structures can improve network performance.

Under review as a conference paper at ICLR 2021
A GENERAL COMPUTATIONAL FRAMEWORK TO MEA- SURE THE EXPRESSIVENESS OF COMPLEX NETWORKS USING A TIGHT UPPER BOUND OF LINEAR REGIONS
Anonymous authors Paper under double-bline review
ABSTRACT
The expressiveness of deep neural network (DNN) is perspective understand the surprising performance of DNN. The number of linear regions, i.e. pieces that piece-wise-linear function represented by DNN, is generally used to measure the expressiveness. And the upper bound of regions number partitioned by a rec- tifier network, instead of the number itself, is a more practical measurement of expressiveness of a rectifier DNN. In this work, we propose new and tighter up- per bound of regions number. Inspired by the proof of this upper bound and the framework of matrix computation in Hinz & Van de Geer (2099), we propose a general computational approach to compute a tight upper bound of regions number for theoretically any network structures (e.g. DNN with all kind of skip connec- tions and residual structures). Our experiments show our upper bound tighter than existing ones, and explain why skip connections and residual structures improve network performance.
INTRODUCTION
Deep nerual network (DNN) (eCunn et al. 2015) has obtained great success in many fields such as computer vision, speech recognition and neural language process (Krizhevsky et al. 2012: Hinton al. 2012 Devlin al. 2018 Goodfellow et al. 2014). However, it has not been completely under-
stood why DNNs can perform well with satisfying generalization on different tasks. Expressiveness is one perspective used to address this open question. More specifically. one theoretically study
expressiveness of DNNs using approximation theory (Cybenko) 1989 Hornik et al.. 1989 Hanin
2019 Mhaskar & Poggio 2016 Arora et al. 2016), or measure the expressiveness of DNN. While
sigmoid or tanh functions are employed as the activation functions in early work of DNNs, rectified linear units (ReLU) or other piece-wise linear functions are more popular in nowadays. Yarotsky (2017) has proved that any DNN with piece-wise linear activation functions can be transformed to a DNN with ReLU. Thus, the study of expressiveness usually focuses on ReLU DNNs. It is known that ReLU DNN represents a piece-wise linear (PWL) function, which can be regarded to have dif- ferent linear transforms for each region. And with more regions the PWL function is more complex and has stronger expressive ability. Therefore, the number of linear regions is intuitively meaning- ful measurement of expressiveness (Pascanu et al. 2013 Montufar et al. 2014: Raghu et al. 2017 Serra et al. 2018 Hinz & Van de Geer] 2019).
A direct measurement of linear regions number is difficult, if not impossible, and thus the upper bound of linear regions number is practically used figure of metries characterize the expres- siveness. Inspired by the computational framework in (Hinz & Van de Geer] (019), we improve the upper bound Serra et al. (2018) for multilayer perceptrons (MLPs) and extend the framework to more complex networks. More importantly, we propose general approach to construct a more accurate upper bound for almost any type of network. The contributions of this paper are listed as follows.
Through geometric analysis, we derive a recursive formula for which a key parameter construct tight upper bound. Employing better initial value, propose tighter upper bound for deep fully-connected ReLU networks. In addition, the recursive formula provide potential to further improve the upper bound given improved initial value.

---

Under review as a conference paper at ICLR 2021
not only consider deep fully connectdd ReLU networks, but also extend the computational framework to more widely used network architectures, such skip connections, pooling layers and the upper bound of U-Net (Ronneherger et al. 2015) or other common networks can be computed. By comparing the upper bound of different networks, show the relation between expressiveness of networks with or without special structures.
Different from Hinz & Van de Geer (2019).
With the extension,
Our experiments show that novel network structures enhance the upper bound most cases. For cases in which the upper bound is almost not enhanced by novel network set- tings, we explain it by analysing the partition efficiency and the practical number of linear regions.
RELATED WORK AND PRELIMINARIES
2.1
RELATED WORK
There are literature on the linear regions number in the case of ReLU DNNs. Pascanu et al. (2013)
compare the linear regions number of shallow networks by providing a lower bound. Montufar
(2014) give simple but improved upper bound compared with Pascanu et al. (2013). Montufar
(2017) proposes even tighter upper bound than Montufar al. (2014). And Raghu al. (2017)
also prove a similar result which has the same order compared to Montúfar (2017). Later, /Sera et al. (2018) propose tighter upper bound and a method to count the practical number of linear regions. Furthermore, Seeraa & Ramalingam (2018); Hanin & Rolnick (2019a b) explore the properties of the practical number linear regions. Finally, Hinz & Van de Geer (2019) employ the form of matrix computation erect framework compute the upper bound, which is generalization of previous work (Montufar et al., 2014 Montúfar
2017 Serra et al. 2018
2.2 NOTATIONS, DEFINITIONS AND PROPERTIES
In this section, will introduce some definitions and propositions. Since the main computational framework is inspired by Hinz & Van de Geer 22119, some notations and definitions are similar.
Let us assume a ReLU MLP has the form as follows.
f(x) (()) (w x +b) +b(l-1) ((())
(L-1)
where x E 12, W E 1 ((0) I and (xx) = m 0) denoting the ReLU function. ( the weights in the 7th layer and (6) is the bias vector. f(z) can also written as:
ho(x)= = x, (x) o( (+)))) f(x) hr)
(2)
(())
Firstly, we define the linear region in the following way. Definition 1. For a PWL functionoon f(x) R. - R we define is linear region, if I satisfies that: (a) TB is connected; (b) an affine function TB; (c) Any TDV 2 TD, f is not affine TDy
For PWL function f. the domain can be partitioned into different linear regions. Let
P(f) = [D, is linear region of f, VD; + D,, nD, =
represent all the linear regions of f. We then define the activation pattern of ReLU DNNs as follows. Definition 2. For any E Ro define the activation pattern of x in ith layer 8n, (a) E 1)% as follows.
(1, [1, i (=)) + +1 >
8h, (x); = (0. W (x) ( +b, 5
for (1,2,...,
1-,1 {1,2, ... n.)
where W(() is the jth now of W(), (60 is the jth component of (60 Hinz & Van de Geer 20190
2

---

Under review as a conference paper at ICLR 2021
For any æ, (z)))) can be rewritten as (a) (( (x=), where ( is matrix with some rows of zeros and (xx) is vector with some zeros. More preciscly,
(w)),
W sh,
Jit Sh, (m); = 1; if Sh. (x); = O.
(x)) [b/ if sn, = 1; 0, if (h. =0 0.
(4)
O,
To conveniently represent activation patterns of multi-layer in MLP, denote h( {1i,,... hi).
where h4 is defined in 2q and Sp (a) (8h, (z)).-., 81, (a=)). ((h (Spt)) (ar) Rom). Given a fixed æ, it is easy to prove that (2) is an affine transform (i = 1.,...., L). Suppose that 8 {0, 1m ...... {0, 1 h {/1,.... hg-1) } and h(x) represents h (a), if ID
{o| (r (x) = 8} * 0. then ff is an afline transform in D. And it is easy to prove that there exists a linear region ID' so that D S ID' Therefore we have [P()) S [sh)).
In our computational framework, histogram is a key concept and defined as follows.
Definition 3. Define a histogram v as follows. Hinz & Van de Geer 2019
v VEV-
I ZENI
- = Σ
2j < 00
(5)
1=0
histogram is used to represent a discrete distribution of For example, the histogram of non- negative integers G {1, 0, 1, 4, 3, 3, 1} is 1, For convenience, let = Exrc 1==
and the histogram of G' is denoted by (G). We can then define order relation.
Definition 4. For any two histograms
define the order relation - as follows. (Hinz & Van de
Geer 2079
Σ
(6)
It is obvious that any two histograms not always comparable. But define operation
such that (x() 3 max (fo I}) where I is index collection. More precisely:
Definition 5. For a finite index collection I, let V = (v(0)i E l), define max operation as follows.
max (V1), max Σ
max RET
Σ
for J E N
(7)
J=
where u is the j component of the histogram (()) Hinz & Van de Geer 2019
When a region is divided by hyperplanes, the partitioned regions number will be affected by the space dimension which is defined as:
Definition 6. For connected and convex set ID C R", if there exists a set of linear independent vectors {or (+) (3) E ER" 1,..., k., l S n and a fixed vector e E R", s.t. (a) any x # c E D, (1)( where {a:} are all 0; (b) there exists a; o s.t. ()) + D. Then the
c Ei= +k+> space dimension of D is k and denote it as Sd(D)) = k.
The following proposition shows the change of space dimension after an affine transform.
Proposition Suppose D C R is a connected and convex set with space dimension of k (k n), is affine transform with domain of D and can be written as f(x) Ax + b, where A E mxn and b E Tm Then (DD is a connected and convex set and
Sd(f(D)) & min(k, rank (A))
(8)
The proof of proposition] I given in Appendix A.I.I
Now we can analyze the relationship between the change of space dimension and activation patterns.
Let first consider the 1st layer in ML. f. w and b(4) construct hyperplane (W(1)
j::

---

Under review as a conference paper at ICLR 2021
of 0) in Rn and this hyperplane divides the whole region of T into two parts. One part corresponds to successful activation of the 3th node in the 1st layer and the other to unsuccessful activation. This can be represented by the jth component of $h, (z). Therefore all the possible activation pattern Sh, (z) is one by one correspondent to the divided regions by nı hyperplanes of (W/ x x-b (1) 0.j = 1, .....,,, m1). which are denoted [ For any region ID divided by Hal,, have 4y (z) = (x (ax b where (0))) is any point in ID and rank (xx) < [s] where 8 is the correspondent activation pattern of D. According proposition hn (T) satisfies that Sd(A, (ID) I min(no, | 1.) Similarly, AH divides h (ID) into different parts, and this corresponds to divide DD into more sub-regions. In general, every element of S(h()) is correspondent to one of regions that are partitioned by lila, H HR,, The next two definitions are used to describe the relationship between the change of space dimension and activation patterns.
Definition 7. Define (Sh) as the space dimension histogram of regions partitioned by a ReLU network defined by 7 where h = (hi...., h1.-1 i.e.
Hea Hist ((Sd (h (D (s))) DD (s) = {z|Sn, (x) = sE
(9)
Definition 8. Define Ha (Sp) as the dimension histogram of regions partitioned by a ReLU network
defined by Eq where h = (hi....,hh..1) i.e.
Ha (s+) Hist (fmin {no, (hali..... 18 SES)))
(10)
We then have the following proposition. Proposition 2. Given ReLU network defined by Eq let h {hr,... ( Ha (S
hr-1). 1.. then Had (Sh) =
The proof of Proposition is given in the Appendix A.1.2 Proposition shows that space dimension is limited by dimension histogram. This idea is used to compute the upper bound.
We can then start to introduce computational framework. For convenience, denote RL(n, n²) as one layer of a ReLU MIP with input nodes and n' output nodes (containing one linear transform and one ReLU activation function), and define its activation histogram as follows.
Definition 9. Given h E RL(n, n'), define Ha (Sh) as the activation histogram of regions parti- tioned by h, i.e.
(S,) = Hist ([|s), s {sy (z)
R"}))
(11)
The activation histogram is similar the dimension histogram, and it is used to define y which is key parameter to construct an upper bound.
Definition 10. If Tn satisfies following conditions: (a) Vn' E N4,n E fo.....n' n'), max (Hs (Sx) RL n'), 1 "nw' (b) Vn' E N. {O....,n'}
= 'na' Ha.n' Then, Yn (n' E N4, E 1, I,...,n') satisfies the bound condition. (Hinz & Van de Geer 2079)
Here, for h E RT((0,n)). n'), we define H(S.) = e = 01. Let T be the set of all that satisfy the bound conditions. When n > n', Tn is defined to be equal to nn' since max H4 (Sn) E RL (n, n')} is equal to max (7a, (Sx) h E RL (n', n')) (Hinz & Van de Geer 2019). By the definition "Y.w' represents an upper bound of the activation histogram regions which are derived from n-dimension space partitioned by n'' hyperplanes. Ac- cording to Proposition I this upper bound is also related to the upper bound of space dimension. Therefore when ", is tighter the computation of upper bound of linear regions number will be more accurate. The following function is used to describe the relationship between upper bounds of activation histogram and space dimension.
Definition 11. For 1" E N, define clipping function cl-(()) V- + V follows. (Hinz Van de Geer 2019
1i By
for i < 1* for i i* for i i*
cl.- (v);
00 Σ
j=
(12)
With the definitions and notations above, we can introduce the computational framework to compute the upper bound of linear regions number as follows.
4

---

Under review as a conference paper at ICLR 2021
Proposition 3. For 7 I, define the matrix B NN
BB (1) (B,) (clz-1
8,3 nI....,
Then, the upper bound of linear regions number of an MLP in E
B DL-1 M 2:
B(() M Magan enot1
(13)
where M RR (g(n'+1)x(++)) (M)ss 6 0s,
HHin Van de Geer 2019)
MAIN RESULTS
In this section, we introduce a better choice of and compare it to Serra et al. (2018). We also extend the computational framework to some widely used network structures.
3.1 TIGHTER UPPER BOUND ON NUMBER REGIONS
Before giving our main results, we define new function of histograms as follows. Definition 12. Define downward function dm(() V + V by dm((v); U--1 When i 0, ser dm u)o
We then prove the following two theorems used to compute 7, Theorem 1. To satisfies the bound condition in Definition 10 when n" < n', then
Tn,nn 7n-1,1 + (nn
(14)
also satisfies the bound condition. Theorem 2. Civen any h E RL(1, n), its activation histogram (a() denoted by v satisfies
Σ di 2(n 1) +1.
The proofs of Theorem
I and are Appendix A.1.3 and A. respectively.
From Theorem
we can derive a feasible choice of Yi. whose form is
71,
(O..... 0. n mod 2, 2, 2,....2.1]
(15)
For example, 71.4 (0,0,2,2,
T. Since there exists RL(1,,) n)) such that H. (8x)
N. (the proof can be seen in the Appendix A..1.5., Eq 15 is the tightest upper bound, i.e. max (Ha (S,) (h RL (1, satisfies Eq 15 With the fact that max (Ha (5,) 1h E RL (2, 1)]
(1, any "In,n" can be computed.
3.2 COMPARISON WITH OTHER BOUNDS
We use ours and sem to represent the ones proposed by us and Serra al. (0188. According to In.n' Hinz & Van de Geer (2019).
05i n n' - n Sis
serra Tn,
It is easy to verify that y.m also satisfies Eq But the initial value of oum is different from 2 and we have that serra (0, .... 0, n, T) Obviously, ours seraa Since the two operations, + and dm(+), keep the relation of z, for any n, n' E N_, 7 I nnn' (see an example Appendix
sena
A.2.I. By the following theorem, the upper bound computed by Eq using ours, is tighter than Tn.n
3 Inn' then upper bound computed by Fg using (1) is less than or equal to the one using (2))
Theorem 3. Given (1), (2) E T, for any n.n' E N such that In
(1)
(2)
The proof of Theorem 3 is in Appendix then the upper bound will be tighter. And Theorem I limplies that if we have more accurate initial value, e.g. "smaller" 22.,. or 33.., the upper bound could be further improved. Therefore Theorem T provides potential approach to achieve even tighter bound.
Theorem shows that we can get a "smaller" Yo.n'
5

---

Under review as a conference paper at ICLR 2021
3.3 EXPANSION TO COMMON NETWORK STRUCTURES
Proposition 3 is only applied for ReLU MLPs. In this section we extend it to widely used network structures by introducing the corresponding matrix computation.
Pooling an unpooling layers Since the pooling layer unpooling layer can be written linear transform., e.g. average-pooling and linear interpolation, can be denoted by = Az. Suppose w the space dimension of input region and is the histogram of the output regions. Then we have the following proposition.
Proposition Suppose rank (A) k, then w cl
Since clę (v) has matrix computation form which similar M in Eq 13 the effect of this type of layer on the space dimension histogram can be regarded as another matrxx in Eq 13 Similarly, we have the following proposition for Max-pooling layers.
Proposition 5. Suppose the max-pooling layer is equivalent a k-rank maxout layer with n input nodes and nu output nodes. Let c = (k² k)m, then
w 3 clay (diag {
(170,els.......... Ma,eli) 3 v)
(16)
The proofs of Proposition Proposition
5 are Appendix A.1.7 and A.1.8
Skip connection and residual structure The skip connection is very popular in current network architecture design. When network is equipped with a skip connection, the upper bound will be changed. The following Proposition gives the correspondent method to compute the upper bound with skip connection.
Proposition 6. Given network, suppose that v is the space dimension histogram of the input regions of the ith layer and w the histogram of the output regions of the jth layer. And we have that w < II' Agu. When the inpul of the 7th layer concatenated to the jth layer, i.e. a skip connection, then the computation of u will change and satisfies that u 3 > Un |Be"), en where
B = Ag. It also has a matrix multiplication form.
Residual structures (He connection plus a simple full-rank square matrix computation. Therefore its effect on space dimen- sion histogram the same as the skip connection. Concatenation is equivalent to addition in upper bound computation. Thus, we have the following proposition.
2016) are similar skip connections and be regarded skip
Proposition 7. Suppose that the residual structure adds the input of the 8th layer to the out- pul of the jth layer. 1. w. have the same meaning in Proposition 6 w Σ Un Be"lee"
Then have that
The proofs of Proposition 0 and Proposition are in Appendix A.1.9 and A.1.I0 In addition, the analysis for dense connections (Huang et al. 2017) is similar to skip connections and is further discussed in Section
deal with complex network. For example, U-net (Ron- neberger et al.) 2015) is composed of convolutional layers, pooling layers, unpooling layers and skip connections. If we regard convolutional layers fully-connected layers, then could compute the upper bound of it (see details in Appendix [A.2.3). Though in this paper we have not extend to all possible network structures and architecture, according Proposition and by using our compu- tational framework, it is possible to compute the change of the space dimension histogram for any other network structure and architecture. Based on these bricks of different layers or structures, we may derive the upper bound of much more complex and practically used networks.
With the above analysis,
4 EXPERIMENTS
We perform two experiments in this work. The first one is to compare the bound proposed by and by Serra et al. (2018) which is illustrated by Figure [ The upper bounds of MLPs computed and their ratio is calculated to measure the difference. Figure ((a) and Figure [(b) show how the ratio

---

Under review as a conference paper at ICLR 2021
-00
ofupper hound
Rallo of Upppr bound
Rarto upper bound
1.
1.9
339
20
Layer number
Layer number
number
(a) 730 10
(b) noo
100
(c) no 10,
The comparison of our upper bound and Serra al. (2018) The y axis represents the ratio of them which can be used to measure the difference. The MPLs are in the form of - -.--n-- with & hidden layers. (a) Setting is no 10, n4 Setting is ni = 10, n4 = 6, 8, 10, 15, 20, 25, k = 1,2, 10. (c) The setting is no = n2 = 10, A 10, 20, ..., 100.
Figure 1:
10, 15, 20, 25, k 1, 2. .... 10. (h)
Table I: The upper bound of AEs and U-nets. The channels setting means the architecture of networks. For instance, 4-8-16332 represents AE which encoder has three down-sampling layers and the channels in different layers are 4, 8, 16, 32 respectively (see details in Appendix A.3.II. The input size in the first four experiments is (24 24) while the last is (16 16). The upper bounds are listed in the third and fourth column. The former corresponds to U-nets while the latter to AEs. Besides, the ratios of two them are listed in the last column.
No.
Channels setting
w/ skip connection
w/o skip connection
ratio
16-32
5.431 X 102031
5.027 x 1026
1.080
10405
4-16-64-128
1.712 x 103111
3.333 x 102956
3.517 x 10154
4-8-16
9.354 X 10
1.407 x 10
6.648 x 10258
4-16-64
2.211 102591
3.328 102150
6.644
10140
5
8-16-64
3.504 X 101395
5.470 X 101330
6.406 x 1064
6
8-32-128
1.268 x 104642
1.230 X 102642
1.031
changes as the number of hidden layers increases from to 10 with different no. Figure I(c) shows how the ratio changes when the depth of the network becomes larger.
The second one is to verify the effectiveness of skip connections and residual structures on the improvement of expressiveness, illustrated in Table[]and Table We compute the upper bound of auto-encoders (AE) and U-nets. AEs and correspondent U-nets have the same network architecture except the skip connection. As for residual structures, we build two identical networks for the image classification task with or without residual structure. For each pair of networks (with or without one special structure), the ratio of their bounds are computed measure how the upper bound will be enhanced with special structure. Different network architecture settings are tried in experiments. Because of the large memory required by complete "n,n' we only consider networks of relatively small sizes (network input size is 24 x 24 or 16 16). In addition, convolutional layers are regarded as fully-connected layers the computation.
5 DISCUSSION
The proposed upper bound has been theoretically proved to be tighter than Serra al. (2018). Fur- thermore, Figure ((a) and Figure ((b) show that when n; increases from 0.6ng to 1.5mg. the ratio curve of two bounds moves upward. However, when n; increases to 2ng, the curve moves down- ward. And when n, increases further and is much larger than no, the two bounds are the same.
(serra) When n. < fig, B,, affects the upper bound most. And the difference between ( and B((em)) is more significant when n, decreases. When n: no, (Ba).not1, the (no 1) column of B., is the main source of
This trend is related the extent of similarity in Bi (ours)
(( and B(seraa

---

Under review as a conference paper at ICLR 2021
The upper bound of simple network for the classification task with or without residual structure. The channels setting represents where main differences in architectures are (see details in Appendix A.3.2). "pI6" means that there is a pooling layer before the convolutional layer with 16 channels. And "r16" represents that residual structure is added in the convolutional layer with 16 channels. The last three columns in this table is similar to Table T
Table 2:
In this part, the input size in all
the experiments is (24 x 24).
No.
Channels setting
w/ res-structure
w/o res-structure
ratio
1
4p16-p16-116-11---6
7.313 x 10
3.720
10 10
1.966
2
4-p4-4-44-44-r4
5.052 x 10
3.393 x 10
1.489
3
4-116-116-16611-116
5.232 x 101930
3.720 x 10
1.406
4 4p16-p66-16--116-1666661666
3.012 x 102277
5.882
102276
5.121
5
4p16::33-132--12--222
7.180 x 102623
7.166 x 102623
1.002
difference. It is easy to find that the middle part of B (ours) right part are similar (see detials in Appendix (A.2.3). As for the Figure [[c) it shows the difference between two upper bounds will be enlarged when the depth of networks increases. In general, both theoretical analysis and experimental results show our bound is tighter than [Srra et al. (2018).
and B, (serra) differ most while the left and
The result in Table T. Table 2 shows that special structure such as skip connection and residual structure will enhance the upper bound. And when the residual structure is used in more layers, the enhancement will increase (comparing comparing No. 3 and 4 in Table However, it seems that when the number of channels is larger, the enhancement is weaker (comparing No.1 to 2, to 4, and No.5 to No.6 in Tabel [ Similar result can be observed in Table [ (comparing No.1 I to No.5). These results explain why skip connection and residual structure are effective from the perspective of expressiveness. However, there also exist some settings such that the two upper bounds are close.
We provide an explanation for the observation through the concept of partition efficiency. First of all, we note that it is not the upper bound but the practical number of linear regions that is directly related to the network expressiveness. Though upper bound measures the expressiveness in some extent, there is a gap between upper bound and the real practical maximum. Actually, any upper bound which can be computed by the framework of matrix computation, including [ascanu et al. (2013); Montufar et al.] (2014); SSrra et al.) (2018) etc., assume that all the output regions of the current layer will be further divided at the same time by all the hyperplanes which the next layer implies. However, this assumption is not always sound (see detail in Appendix (A.2.4). When the number of regions far exceeds the dimension of hyperplanes, it is hard to imagine that one hyperplane can partition all the regions. But the special structure (e.g. skip connection) may increase the number of regions partitioned by one hyperlane such that the practical number can be increased even if the upper bound is not enhanced. Intuitively, skip connections increase the dimension of input space and the partition efficiency may be higher. An good example is dense connections (Huang et al., 2017) which is only special case of skip connection but can further increase the dimenston and thus lead to better expressiveness; this may explain the success of DenseNets. Though we have not completely proved the partition efficiency of skip connections, some evidences seem to confirm our intuition, as shown in Appendix A.1.11 and 1.1.12
CONCLUSION
In this paper, we study the expressiveness of ReLU DNNs using the upper bound of number of regions that are partitioned by the network in input space. We then provide a tighter upper bound than previous work and propose a computational framework to compute the upper bounds of more complex and practically more useful network structures. Our experiments verify that special network structures (e.g. skip connection and residue structure) can enhance the upper bound, Our work reveals that the number of linear regions is good measurement of expressiveness, and it may guide us to design more efficient new network architectures since our computational framework is able to practically compute its upper bound.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint 1rXiv:1611.011 2016.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 2(4):303-314, 1989.
Jacob Devlin, Ming-Wed Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint /8Xiv://10004880) 2018.
lan Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Boris Hanin. Universal function approximation by deep neural nets with bounded width and relu activations. Mathematics, 7(10)999,, 2019.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. arXiv preprint arXiv: /tt.//9110.0000 09021, 2019a.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, pp. 359-368, 2019b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling speech recognition: The shared views of four research groups. IEEE Signal processing magazine, 296))82-977,00
Peter Hinz and Sara Van de Geer. framework for the construction of upper bounds the number of affine linear regions of relu feed-forward neural networks. IEEE Transactions on Information Theory, 6534144730, 2019.
Kurt Homiik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), July 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436-444 2015.
Hrushikesh N Mhaskar and Tomaso Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14((6):829-8)) 848, 2016.
Guido Montúfar. Notes on the number of linear regions of deep neural networks. Sampling Theory Appl. Tallinn, Estonia, Tech. Rep, 2017.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp- 2924-2932, 2014.
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with fise linear activations. arXiv preprint arXiv: 1312.669 2013.

---

Under review as a conference paper at ICLR 2021
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power of deep neural networks. In Proceedings of the 34th International Conference on Machine Learning-Volume Volume 70, pp. 2847-28544 JMLR. org, 2017.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedi- cal image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234 244. Springer, 2015.
Thiago Serra and Srikumar Ramalingam. Empirical bounds linear regions of deep rectifier net- works, arXiv preprint arXiv:/810.03370, 2018.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pp. 4558- 4566, 2018.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
A APPENDIX
A.1 PROOFS
A.1.1 THE PROOF OF PROPOSITION 1
Proof. By Definition 6, suppose (n(1), v(2) ,...., ((k) and be used represent any I and fa; # 0} satisfies that a, ((( + c D. Let D' D c, then DV is translation of DD. Since Di is convex, D' and f(ID') is also convex. Because f(D) = f (ID' + c) AD' + Ac + b, then (dD)
Sd(AD'). Suppose that D'" A(D')
(Aæl x E R'.. For any y TDV, y Av. Denote An(i) by w((), then y
DV", there exists (w (2) ..... (A)) } and a, E DV. From {w(*), wx(2) ..... w(() choose set of vectors which are linear independent and can linearly represent {w((), w( (....,((()) (()) }. For convenience, ....,
be represented by
suppose they are (1) (²)) ..... (())), }. < k. Therefore any y D can be represented by (w (2) (()),, Thus, Sd(DD) = Sd(f(D)) and we have that
t rank (1) w (1)
rank( (1) w {
(1)) o b(b))
rank(A A min(rank( A), rank( (1)) o(0)))
min(rank(A),
The last equality is derived from that (,()), ( are linear independent vectors.
A.1.2 THE PROOF OF PROPOSITION
S(h), suppose D(s) (x|Sn(x) s}. As long Sd (h (D)))) < 1 is established, the proposition can be proved. Apparently, Sd(DDs))) = ng- Through the analysis in Section 2, h(.) in D(s)) is an affine transform. For
Proof. For any
min(no, 18nl11 18h211 s.... 8hg
any (1), (2) E (Ds)), (xx) (x))) ((0)
(x(()) (zx Therefore we use (0) E D(s) represent them. Then h(.) in (s)) can be written as
h(#)= = (l.11) (0) [...
(0)) (x))) + 66 (L-1)) (0)
((x (0))
10

---

Under review as a conference paper at ICLR 2021
By Proposition 1, we have
Sd (h (ID (s))) < min
raakk W W(x (). mom
1-1 II
w ( (2oo
min
nop rank
no, min rank (2x))
rank (w(L-))(z101))
min
S min no: 1ha (8hal1 1he-
The last two inequality are derived from that
L-1
rank
II
w W (x(0))
& min (z."). (x)-)(xx0)))
and rank(W(() (0))) s 1-h/11
L
A.1.3 THE PROOF OF THEOREM
Proof. Obviously, Tn,n' satisfies the second condition. As for the first condition, consider that hyperplanes (L1 L2,,,, Lec) divide RR. These hyperlanes correspond to one h E RL(n, n') and its activation histogram denoted by v1. Here, we assume that L1, L2.... Lnd are not parallel to each other since in parallel case it is casy to imagine and verify that there exists h' E RL(n,, n') which satisfies (S,) H. (Sw.). Suppose that hyperplanes [[, Iz..... -1) divide R into t regions {R1, R2.... ..., R and their activation histogram is denoted by 22. Assume that T,, crosses R Ro..... Rp P S & and divides them into 2p regions. Let 83 denote the activation histogram of {RI, R2,.... RR), p regions of them are active by L." while other regions are not. Part of {Rp+1, Rp+2,..... R&} are active by Lon while the rest regions are not. Their activation histogram denoted U4 and Us respectively. Then have the following equations:
122 + + US
(17)
01 = ug + dm( + dm ddm(vs))
(24) + 05
(18)
Let us only focus on {R R2, .... Ry Suppose {L1, L2, .... Lm (m n 11) are borders of these regions. (Lr n LI, Lnn O L2, L n Lm} } are hyperplanes in Lut, and their active directions are projections of (L1, L2,... ... Im } in R So the activation histogram of (Lnw L1, Lon L2, ... Las Lm} in L,d' which is denoted by Us is equal to Uz. By the assumption that when r" < n', Tn.n" satisfies the bound condition, we have
U3 U6 I 7n- I 1n-1,n'
(19)
By Eq 17
Eq 18
and Eq 19
satisfies
V J In-1xn + dm + U4 + Us)
In-1x' dm(
(20)
3 m1 + ddmm7,nn-1)
Because of the arbitrariness of U1, we can get Tn,n' Yn 1,n' -1 + dmm(mnmn which satisfies the first condition.
A.1.4 THE PROOF OF THEOREM 2
Proof. For 1-dimension space, its hyperlane is one point the number axis and the activation direc- tion is either left right. It is apparent that n segmentation points divide one line into n parts. And for any x E IR, its activation number is at most n. Therefore
< [. then 1. If > [ the activation pattern of n + regions IR
EL 24 < n + 1 < 2(n - t) denoted by {$1, $2.... .... snt1 } (see Figure 2(a)). No matter how the activation directions of points are, we have |s| + | = n since $ IS equal to the number of left activation directions and (s, is equal to the number of right activation direction. Another obvious conclusion is that
11

---

Under review as a conference paper at ICLR 2021
S1
S2
S3
S4
Sn
Sn+1
22
2
3
n-1
(a) Number axis
Region
3 4
b a+1
(b) Activation number of each region
Figure 2: (a) The number axis is partitioned into n + parts. 8, represents the hhh region. (b), An example of partition and the activation number of each region. The abscissa axis corresponds to the position and the vertical axis represents the number activation
|s,| |s;4|| = +1 the activation patterns of neighboring regions only differ at the 1hh point. Without loss of generality, let [81| - 1 Any line chart active numbers with dotted line is under the line chart with solid line (see Figure 2 So regions with active numbers larger than or equal to are among th and 5thh region. Apparently, the number of regions among at and 8th region is 2(n t) + 1. So Ei= 1 < 2n t) 1.
A.1.5 THE PROOF OF EQ
Proof. Suppose the points of h in the number axis are Pl, P1.P2.... Pr. Let the direction sof
P1, P1 y are right and other points left. It easy to verify that H. (S,) = him where 71,1 is defined by
Mi. = (O,..., 0. mod 2, ........11)
1
Then 11. 3 max (Ma (St) h E R)( Since max (Ha (Sx) |h E n), 3 n.m n.n
max (Ha (Sh) hh RL(1.n)].
A.1.6 THE PROOF OF THEOREM 3
Proof. Different B, can be derived from different Tn,a' Since the clipping function keep the order
relation 3, every column of (2)()) n'
and B (2)
in the same position satisfy that
B
B
:j
Another fact that when v 3 w. then |0|1 I |wl,-
Here we prove that v I w. then
Mnnnne v 3 MR. w
(21)
and
(1)
B (2)
B V -
w
(22)
n;
Then the theorem can derived easily from Eq
21 and Eq 22
cla.s (b), 21 is easy verified. For B (k)
Because Mn,
Mn.
1,2, we have that when j1 S ja because of the second condition in Definition 10 and the
(B,0) (4)
:ch
:
is denoted by B(k) k 1,2. By property of the clipping function. For convenience, (Ba" m.j
12

---

Under review as a conference paper at ICLR 2021
Definition 5, we have that
xC
B
1
Σ
B w
M=M
m
m=M
m
00
00
00
B
B Uj
B (2)
m.j Wij
M
1=0
m=M
m
m
30
B m
Dj
Wi
m.j
==
m=
j=0
M
: Because ( 3 B :j. i.e. vM 2 0. Em=M (())
S Σm -== M
B m.j Let = Em=>
B by
M
m.jj
Em=M _ then aj S bj. Because B (b)
i 1 B 1k)
when j1 < j2. then
.
au s 01 02 S ...
(23)
and
bo bi b2 ...
(24)
By the notations, we have that
Σ
((1) mid
VjS S
Bla)
Wj
0
>==M
M
j=0
m==
6j0g
1=0
84
ni
0
S
by w
1=
The last equivalence is derived from that Uy w 0 when j
ng. Consider the left part of last
inequality. Employing v 1 w + Dj=j V/ S j=z wy and Eq 24 derived
the following incquality can be
B2 byU
n,
124
n2
Σ
0
20
Σ
b bo Σ
W/y
Σ
Uj
6
j=0
n2
12
< bowo + bi
Wj- Σ
0j
+ j=1
0o + 61 + +61
W
8j
+
byu3
j=1
2=2
n1
bywy + bz
Σ
Wj
>
F3j
+
Σ
رyU =
Σ j=0
bywg + b2
Σ
Wj Σ
0j
by
0=
1-2
j=2
j=2
j=3
3=3
3=3
n:-1
ni
bywy + bn. (Wn, Un.) + bn, Vns
=
Σ
6,00
0=0
Therefore the left part is less than the right part, i.e. Eq 22 is established and the theorem is proved.
A.1.7 THE PROOF OF PROPOSITION 4
Proof. Consider any input region D. Let DD is the corresponding output region, i.c. D' A(D)). By Proposition 1, Sd(()) & (i) k)). Because
(Sdn(((mi(Sd( k]] D is any input region)) cla
13

---

Under review as a conference paper at ICLR 2021
then 3 (v). Suppose R=+! i,, D2 = 0 when it is easy to verify that cly(0) U, where
Mn,k E (((+t)x(n+t)) (MM)) (000),==0mmin ..min(i.nn1)
A.1.8 THE PROOF OF PROPOSITION 5
Before the proof, we show the following lemma.
Lemma 1. Suppose "n.n! satisfies the recursion formulaa in Theorem
and the initial value satisfies
1/2 ). then any "In satisfies (Ti,,r = >>= n''
that [mmim2ll = >0
Proof. Since Tn,n' Vo 1,n'-1 + dm and dm(-) does not change 1 |1, we have
1/n,n'11 = In- + P11 By the assumption, suppose that hes.ng l = Ex=
112
established when ny I n and m2 n'. Then
1m = Σ
n' -
+ Σ
n'
-
8
0=0
8=0
n
C + --- + C
C
+ Ca
n'
==0
Therefore any "nw satisfies the formula.
It is easy to verify that 1n.h m++1= ( n and 12,111 2 Σ
Es=o
By
ni' Next prove Proposition
Lemma I Na proposed by satisfies that 17,,
Proof. Denote the maxout layer by h. according to the proof of Theorem 10 in Serra et al. (0188) one k-rank maxout layer with ny output nodes corresponds to divide one region by hyperplanes. Suppose R is one input region with Sd(R) nn' and partitioned into sub-regions
k(K 1)
n
2
{ri...,,Tp) Since one d-dimension space most partitioned into Σ ( m sub-regions by m hyperplanes, then by Lemma
n'
k(k- 2
) )= = |nte,ll1
==0
For any sub-region pt, Sd(p:) n'. Since h is equivalent an affine transform p; with matrix A of rank nAs we have that Sd(h(p:)) &
nn) by Proposition [1] Another fact is that nA S ny. Therefore Sd(h(p;)) S min(m,,n'). That is to say, R with n' space dimension divided in to at most hineel sub-regions and the space dimension of each output sub-region is no larger than min(n4, n'). If the space dimension histogram of input regions is v (E IR"). then easy to verify that after the partition by h, the histogram of sub-regions o' satisfies that o' I diag { //o.cll....,,///... v. In addition, h change their space dimension. Thus
~ cln, (v') I cla, (diag (/o..ch..... ... |m,cl1) })). Let C diag (1m.chi,.... hmch ). then cl,, (diag (ho.chh. hinel (1) v) M Cv.
14

---

Under review as a conference paper at ICLR 2021
A.1.9 THE PROOF OF PROPOSITION 6
Proof. When the skip connection is not added, w 3 Bv. Let c", i.e. the the number of the input regions is one. Suppose the region is R S R and is divided into sub-regions. Apparently p Be"l and Sd(R) Sd(r) = n S m where r is one of the sub-regions. Suppose the part of network which is from the 7th layer to the l layer is equivalent to an affine transform with matrix
C'
C. Let r' = C(r). When the skip connection is added, the output of is (r) denoted by r".
(
Since rank
= m, Sd(r") & mm, Sd(r)) = n. This implies that the space dimension
of r' may be enhanced to n. Therefore the space dimension histogram of sub-regions wo satisfies that
w 3 Be" lee..
(25)
For any imput region with space dimension, 25 is always established. Thus, when the space dimension histogram of input regions v the histogram of output regions satisfies
w 3
Σ WR Σ
Be Sd(R)
le sd(R)
Un Be Σ
(26)
R
n
Let C diag Be"
1, Be² 1,... Be" 11.... then En Un Be" e" Cv.
A.1.10 THE PROOF OF PROPOSITION
Proof. Any residual structure can be regarded as the composition of one skip connection and an linear transform. For any input region C I partitioned by the network, the residual structure part has the following form.
C I
y == Res(x))==))))))
I
E
By Proposition the space dimension histogram of output regions that
(r) denoted by w satisfies
2/ Be"l,
Since rank([ the histogram.
1]) m Sd(r). according to Proposition
the linear transform will not change
A.1.11 PROPOSITION 8 AND PROOF
Proposition For an MLP, let fm represent the first m layers (1 < m S 1), Lee fm(x)) is the output of the mh layer, and Fi+1(z) = (I11)) + b(++1) representing the (1 + 1)th layer in the ML.. Consider another network layer,
[z] (((,11))
G141(z,y)
= (1-)(zy)=0
6 ((++1,))
y
where z = f(()) E y fz) E R== ,1 m < Then, given a specific F1+1- there exists G441 such that the the total number regions partitioned by G1+1 is more less than that by F
Proof. For connected set R C input space, f((R) and fm are still connected sets. For each hyperplane H, represented by = 0j.j2j + by = 0 in F1+1, design corresponding hyperplane Hi, Ej=1 di. Eym + 0, in G1+1, where Gr2j = 0. Suppose H; crosses (R,, R2, ..., Re, and take K; intersections {pr,P2. .... Pk. where Pj is a interior point in R1 j k.). Let fi(x,) Pj. then (fi(zz), (m,) E Hi and it is also a interior point in R2 which is the same as R, when cutting last n. dimensions. So H' crosses at least k; regions which indicates the total number of regions partitioned by G441 is more less than that by Fr+1-
my
15

---

Under review as a conference paper at ICLR 2021
y
(0.1,0)
R1
4
(0.1
22-
1,0,0)
R3
1,0,0)
R4
1,0,
1)
2
Figure 3: The four output regions in R
A.1.12 PROPOSITION 9
AND PROOF
Proposition 9. For a three-layer MLP which has two hidden layers, i.e.
((x) (W x b.) ((2)) b(3)
(27)
suppose that no and every segment partitioned by the first layer keeps their space dimension, Le. their outpul of the first layer still segment. If the input is concatenated to the output of the first layer (just like skip connection), then no matter what the parameters in the first layer are, the practical maximum number of linear regions is structure (just like an MLP) and assume that nı there exists some parameters in the first layer such that the practical maximum number is no more than (n1 + 1)(
(n1 + 1) + +). Specifically, without the special
Proof. Denote (xx) o (W + b()). The first layer divides input space into + 1 regions (r1. Tn,...n, +1}, then h1 (r:) R. Because of the skip connection, the dimension of hyperplanes in the second layer is n2. It is apparent that for any nı + 1 points there always exits hyperplane containing them. Thus, for any interior point x; rs(1 contaning them and therefore crossing 11 + regions. We have hyperplanes in the second layer, which shows the number of linear regions (n, 1)(n + 1). And obviously the maximum number not larger than it (see Theorem 7 in Serra al. (2018)
n1 1), there exists hyperplane
As for special case, take [0, 1] as input space without loss of generality. Let
W
(28)
Then we get four output regions in Rd shown in Figure 3 the same plane, i.e. the x-y plane. For any interior points p. R, 1, the only hyperplane crossing them is x-y plane which is not able to divide R1 R2 and R3. So the practical maximum number is no more than (n) + 1) + 1) n2.
We can see that R1, Re and R3 are on
16

---

Under review as a conference paper at ICLR 2021
A.2 EXAMPLES
A.2.1
AN EXAMPLE OF new
AND Serra
'n,n'
"2,"
Here n'
6. Then ours and serra are shown as follows. 1,,n'
0
0
0
1
0
0
0
0
0
0
1
6
6
0
0
0
0
0
6
6
1
14
15
0
15
15
15
2
5
16
20
20
20
0
0
0
20
20
20
20
(29)
9
15
15
15
15
15
15
15
2
6
6
6
6
6
6
6
6
6
6
6
L1
1
1
1
1
1
1
A.2.2 AN EXAMPLE UPPER BOUND COMPUTATION FOR U-NET
We take the U-net Appendix A.3.I as example. Firstly, we use matrices to represent all layers except skip connections. When computing upper bound convolutional layers regarded as fully- connected layers denoted by C. Suppose pooling layers are average pooling layers and unpooling are filling-zero ones. They denoted by P. and U, Here, the subseript means the order in the network. Then according to Proposition and Proposition 4 we have
C B2304, C2 B C3 B576, C4 B
C B444, Cs B2ss, C7 = B376, Cs B2304
P M2304,576 P2 M1152,288, P3 = M576, 144:
U1 M144,144 1144, U2 M288,288 12ss, U3 = M570,576 1576-
where B. M are defined by Proposition follows.
By Proposition 6 the upper bound N is computed as
S/- U,C M2s 144 C. M14,288
P3
E R 144x576
S3 diagi] S I
I...., S 576
11 576xx76
S U,CaMs77.288 S, 288 285.376
P3 R 1152
576
S2 diag(] S ..... S 1152
E
R 1152
S U U,C;M 162. C2 152 P1
276,2304
S diag{|5]e"|,, S ..... S/e
2304
1.
}
R 1152x1152
CC 2
A.2.3
THE COMPARISON OF Bous AND Reerra
Here we consider = 6. By Eq
29
and the definition of clipping function, we have
1
0
0
0
0
0
0
0
0
1
6
0
7
0
0
0
6
22
14
15
15
0
0
22
0
15
15
15
0
0
38
20
20
20
0
0
0
42
20
20
20
0
22
15
0
0
15
0
0
0
0
7
6
0
0
0
0
0
7
6
0
0
0
0
0
A.2.4 AN SIMPLE EXAMPLE OF IMPERFECT PARTITION
In this part, we two-layer MLPs with ny = 1, nı 2. The original input space R, i.e. the number axis or one line. The first layer partition the line into three parts (see Figure 4(a)) and the corresponding output regions in ? are shown in Figure 4(b) Figure 4(c) is easy to observe that any hyperplane can not partition all three regions simultaneously.
simple example (in Figure to illustrate imperfect partition. Consider
17

---

Under review as a conference paper at ICLR 2021
(a) input regions
output of the first layer
hyperplanes in the second layer
Figure 4: (a) The input region R divided into three parts three colors and activation directions of blue points are drawn above the line; (b) The output regions of the first layer; (c) The blue lines represent hyperplanes in the second layer
tensor
convolutional layer pooling layer unpooling layer skip connection
16
32
16
Figure 5: Network architecture with skip connections in No.1 of Table !
A.3 NETWORK ARCHITECTURES
A.3.1 NETWORK ARCHITECTURES TABLE
We take the first setting in Table as example. The numbers of 14-8--1--32" correspond to one in red color in Figure[5land all the numbers represent the channel number of current tensor. For all setting in Table 1, the channel numbers of input and output are 1. The kernel size every convolutional layer is (3 3) with stride 1. We keep the size unchanged after the convolutional layer by padding zero. We use weolang-pooling as pooling layers and filling-zero as unpooling layers. The down-sampling rate and up-sampling rate are both 2. Except from the last convolutional layer, ReLU is added in other ones. The only differences in setting are channel numbers and the depth of down-sampling.
A.3.2 NETWORK ARCHITECTURES IN TABLE
We also take the first setting in Table 2 example. The numbers of "4pp66p16-11--166116 correspond to one red color in Figure 6 "p" means that before the convolutional layer, there exists pooling layer. The last part of network is three fully-connected layers and ReLU is not added in the final layer. Other setting is the same as Appendix A.3.1
18

---

Under review as a conference paper at ICLR 2021
16
16
16
16
16
4
16
128
tensor, vector convolutional layer pooling layer
256
fully-connected layer residual structure
Figure 6: Network architecture with residual structures in No.1 of Table 2
19


Reviews:
[{"review_id": "zlX8MOJIgxR", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-------------- Overview of the paper -----------------\n\nThe number of regions can indicate the expressive power of neural networks. The paper provides a tighter upper bound of the regions number by providing a better choice of the \\gamma parameter. The idea is built upon the work Hinz & Van de Geer, 2019, and the results is compared with Serra et al. (2018). The authors also study networks with pooling or skip connections.\n\n-------------- Contribution and strength -----------------\n\nI may not have a good sense of the contributions in the paper, since I am not very familiar with the related works. The main contribution is Theorem 1 and 2, which gives a better choice of \\gamma. The experimental results then verifies the chosen \\gamma parameters yields a tighter upper bound of the linear regions.\n\n-------------- Questions and comments -----------------\n\nThe paper provides many background materials from Hinz&VandeGeer, 2019. Yet I feel like some intuitive explanations are missing, which makes it not very easy to follow closely. For example, what is the implication of the space dimension in definition 6?  Does it say something about the structure of a set or the size of a set? It should be helpful to provide some examples for finding the space dimension.\n\nThe better choice of \\gamma in Theorem 1 and Theorem 2 also appear to be mysterious to me. Why we consider the downward-move function in definition 12? I am eager to look at an intuitive idea behind Theorem 1 and Theorem 2, rather a pure comparison between \\gamma^{ours} v.s. \\gamma^{serra}. By the way, \\gamma^{ours} is not clearly defined in the paper.\n\nCan the authors further elaborate on the extreme large ratio in Table 1?\n\n-------------- Educated guess on the rating -----------------\n\nI make an initial rating of the paper, yet it is quite open to discuss given my understanding of the topic. It seems the current paper lacks some transitions between the rather dense definitions and theorems in Section 2. This makes the paper hard to follow for diverse background.\n\nI will reconsider the rating after the author response and seeing other reviews to reevaluate the value and soundness of the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "axwq1hdqw2V", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a method to give upper bounds on the total number of linear regions in a deep ReLU network. These bounds are tighter than those previously obtained and they apply not only to fully connected networks but also to networks with skip connections.\n\nStrong Points: \n1. Understanding the complexity of the function computed by a deep ReLU networks is of significant interest. \n2. The authors state sharper bounds than previously available for this complexity, as measured by the number of linear regions. \n\nWeak Points:\nMany parts of the paper are not clear or imprecise:\n1. Definition 1 is incompatible with the definition P(f) of the linear regions of f. For example, consider a ReLU networks with a single neuron. The partition R^{n_0} into linear regions simply divides the input space into two half-spaces. Thus, the regions D of this function are the closures of these half-spaces and hence are not disjoint (they share the same hyperplane as their boundary). \n\n2. The definition of RL(n,n’) just before Definition 9 is not clear. Is there a bound on the number of neurons in the hidden layer? If one interprets “containing … one ReLU activation function” as having a single neuron, then it appears that (11) is a trivial histogram. If there can be any number of neurons, then in the definition 10 of when\\gamma_{n,n’} satisfies the bound condition, the max of H_a(S_h) over h in RL(n,n’) appears to be a histogram whose entries are not well-defined since they are infinite. I am probably missing something but really didn’t understand what is meant here.\n\n3. For a given ReLU network architecture, bounding the total number of linear regions in the worst case over all configurations of weights/biases is typically of no practical value (thought it is certainly an interesting problem in extremal combinatorics). The reason is that this number, even on average, is unbelievably large. This is true even in extremely simple networks. Take for instance a single hidden layer ReLU network in input dimension n_0, one hidden layer of size n_1 and output dimension 1. For generic configurations of the weights and biases, the number of linear regions grows like the sum of the binomial coefficients (n_1, j) as j goes from 0 to n_0 by Zaslavsky’s Theorem. So in the case when n_1 > n_0, for example, we get 2^{n_1} regions. This in no way reflects the fact that single layer ReLU networks often learn very simple functions. This is exemplified by the shocking numbers in Table 1 (where we see numbers like 10^{2956}).\n\nRecommendation: I found that this paper was difficult to read. The results could be interesting from the point of view of a theoretical analysis of deep ReLU networks, so I encourage the authors to rewrite the body of the paper to increase the clarity and precision around the definitions of linear regions. Ultimately, I don’t think this paper is ready for publication. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Tz9i2hFUJa2", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the counting of linear regions of a multi-layer ReLU network and gives an upper bound on the number of linear regions that is tighter than existing results. Networks with skip connections and pooling layers are also considered. The authors then compare their bounds for standard multi-layer networks and networks with skip connections/pooling layers and conclude that the latter has certain advantages in expressive power. \n\nThe paper is not written very clearly. It is very notion-heavy and lacks necessary explanations of the results. The definitions in this paper are pretty confusing and do not seem to be very rigorous. For example in Definition 3, a histogram v is defined as an infinite vector with non-negative integer entries and finite sum. However, in the discussion below the histogram is of length 5. More importantly, the definition of \\gamma is very confusing: Definition 10 is not well-written, and I’m not quite sure if gamma can be any quantity satisfying the bound condition, or is it chosen more specifically. \n\nThe theoretical results are not presented very clearly either. It is not obvious to me what is the upper bound for the number of linear regions of a multi-layer ReLU network. \n\nThe discussion on pooling and skip connection is given without an explanation of the network structure. It is not clear to me how the matrix A and the skip connections appear in the network. \n\nThe comparison between the vanilla feed-forward network and the ones with skip connections/pooling layers may not be logically correct. Since the authors only compared the upper bounds of the number of linear regions, the experimental results do not necessarily demonstrate the advantage of networks with skip connections/pooling layers. It is possible that the bound for these types of networks are too loose. \n\nFrom the technical aspect, it seems that the proof framework of this paper is mainly the same as previous works, except that a tighter bound of gamma is implemented. This makes the technical contribution of this paper limited.\n\nFor the above reasons, I would like to suggest that the authors should improve the presentation of the paper and explain the contributions more clearly and more convincingly.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Dm1r3iUkxc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper extends on the framework of matrix computation in Hinz & Van d Geer (2019) to give a tight upper bound for linear regions. In particular, the paper shows improvement over the bounds derived in Serra et al. 2018 and extends the bounds for more complex networks with skip and residual connections. The paper also shows why skip and residual connections can be beneficial by showing that they lead to networks with larger number of linear regions. \n\nPros:\n\n1) The work of Hinz & Van d Geer (2019) can be seen as generalization of the results shown in Serra et al. 2018. Through some choice of lambda parameters used in the expression for bounds, this paper provides a tighter upper bound compared to Serral et al. 2018\n\n2) The paper shows that in the presence of residual connections (ResNets), the number of linear regions is larger. This is understandable since there is no bottleneck effect in the case of ResNets as shown by Serra et al. 2018. The bottleneck effect leads to reduced dimensions if the dimension of the earlier layers are small. Having earlier layers with smaller dimensions can lead to decrease in the number of linear regions. However, in the case of residual networks, such an effect can not be observed. Thus we tend to have more linear regions in the case of residual connections.  \n\nCons:\n\n1) The paper needs significant improvement in the presentation. The parameter lambda, that is used in deriving the bounds, is not formally introduced, but the paper starts discussing this from the introduction.  It is difficult to appreciate the contributions or novelty, when the paper does not carefully explain the insights/ideas of the proposed formulation, nor the differences with prior work. \n\n2) The results shown in this paper seem incremental in light of the work of Hinz & Van d Geer (2019). \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the number of linear regions of a multi-layer ReLU network and gives a new upper bound. Reviewers concern about the writing and the results are incremental compared with previous results.
Decision: Reject