Year: 2020

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 Hinz & Van de Geer (2019), 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.

heading: 1 INTRODUCTION
text: Deep nerual network (DNN) (LeCun 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 et al., 2012; Devlin et al., 2018; Goodfellow et al., 2014). However, it has not been completely understood why DNNs can perform well with satisfying generalization on different tasks. Expressiveness is one perspective used to address this open question. More specifically, one can 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 a 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 a ReLU DNN represents a piece-wise linear (PWL) function, which can be regarded to have different 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 a meaningful 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 as a figure of metrics to characterize the expressiveness. Inspired by the computational framework in (Hinz & Van de Geer, 2019), we improve the upper bound in Serra et al. (2018) for multilayer perceptrons (MLPs) and extend the framework to more complex networks. More importantly, we propose a 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 a geometric analysis, we derive a recursive formula for γ, which is a key parameter to construct a tight upper bound. Employing a better initial value, we propose a tighter upper bound for deep fully-connected ReLU networks. In addition, the recursive formula provide a potential to further improve the upper bound given an improved initial value.
• Different from Hinz & Van de Geer (2019), we not only consider deep fully-connected ReLU networks, but also extend the computational framework to more widely used network architectures, such as skip connections, pooling layers and so on. With the extension, the upper bound of U-Net (Ronneberger et al., 2015) or other common networks can be computed. By comparing the upper bound of different networks, we show the relation between expressiveness of networks with or without special structures. • Our experiments show that novel network structures enhance the upper bound in most
cases. For cases in which the upper bound is almost not enhanced by novel network settings, we explain it by analysing the partition efficiency and the practical number of linear regions.

heading: 2 RELATED WORK AND PRELIMINARIES

heading: 2.1 RELATED WORK
text: 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 et al. (2014) give a simple but improved upper bound compared with Pascanu et al. (2013). Montúfar (2017) proposes a even tighter upper bound than Montufar et al. (2014). And Raghu et al. (2017) also prove a similar result which has the same order compared to Montúfar (2017). Later, Serra et al. (2018) propose a tighter upper bound and a method to count the practical number of linear regions. Furthermore, Serra & Ramalingam (2018); Hanin & Rolnick (2019a;b) explore the properties of the practical number of linear regions. Finally, Hinz & Van de Geer (2019) employ the form of matrix computation to erect a framework to compute the upper bound, which is a generalization of previous work (Montufar et al., 2014; Montúfar, 2017; Serra et al., 2018)

heading: 2.2 NOTATIONS, DEFINITIONS AND PROPERTIES
text: In this section, we will introduce some definitions and propositions. Since the main computational framework is inspired by Hinz & Van de Geer (2019), some notations and definitions are similar.
Let us assume a ReLU MLP has the form as follows.
f(x) = W (L) σ(W (L−1) · · ·σ︸ ︷︷ ︸ (L−1) (W (1)x + b(1)) · · ·+ b(L−1)) + b(L) (1)
where x ∈ Rn0 ,W (i) ∈ Rni×ni−1 , b(i) ∈ Rni and σ(x) = max(x, 0) denoting the ReLU function. W (i) is the weights in the ith layer and b(i) is the bias vector. f(x) can also be written as:
h0(x) = x, hi(x) = σ(W (i)hi−1(x) + b (i)), 1 ≤ i < L, (2) f(x) = hL(x) = W (L)hL−1(x) + b (L) (3)
Firstly, we define the linear region in the following way. Definition 1. For a PWL function f(x) : Rn0 → RnL , we define D is a linear region, if D satisfies that: (a) D is connected; (b) f is an affine function on D; (c) Any D′ % D, f is not affine on D′.
For a PWL function f , the domain can be partitioned into different linear regions. Let
P(f) = {Di|Di is a linear region of f, ∀Di 6= Dj ,Di ∩ Dj = ∅}
represent all the linear regions of f . We then define the activation pattern of ReLU DNNs as follows. Definition 2. For any x ∈ Rn0 , we define the activation pattern of x in ith layer shi(x) ∈ {0, 1}ni as follows.
shi(x)j =
{ 1, if W (i)j,: hi−1(x) + b (i) j > 0
0, if W (i)j,: hi−1(x) + b (i) j ≤ 0
, for i ∈ {1, 2, . . . , L− 1}, j ∈ {1, 2, . . . , ni},
where W (i)j,: is the j th row of W (i), b(i)j is the j th component of b(i). (Hinz & Van de Geer, 2019)
For any x, hi(x) can be rewritten as hi(x) = W (i)(x)hi−1(x) + b(i)(x), where W (i)(x) is a matrix with some rows of zeros and b(i)(x) is a vector with some zeros. More precisely,
W (i)(x)j,: =
{ W
(i) j,: , if shi(x)j = 1; 0, if shi(x)j = 0.
b(i)(x)j = { b (i) j , if shi(x)j = 1; 0, if shi(x)j = 0.
(4)
To conveniently represent activation patterns of multi-layer in a MLP, we denote h(i) = {h1, ..., hi}, where hi is defined in Eq.2, and Sh(i)(x) = (sh1(x), ..., shi(x)), S(h(i)) = {Sh(i)(x)|x ∈ Rn0}. Given a fixed x, it is easy to prove that hi(x) is an affine transform (i = 1, 2, . . . , L). Suppose that s ∈ {0, 1}n1 × · · · × {0, 1}nL−1 ,h = {h1, ..., hL−1} and h(x) represents hL−1(x), if D = {x|Sh(x) = s} 6= ∅, then f is an affine transform in D. And it is easy to prove that there exists a linear region D′ so that D ⊆ D′. Therefore we have |P(f)| ≤ |S(h)|. 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 ∈ V = x ∈ NN| ‖ x‖1 = ∞∑ j=0 xj <∞  (5) A histogram is used to represent a discrete distribution of N. For example, the histogram of nonnegative integers G = {1, 0, 1, 4, 3, 2, 3, 1} is (1, 3, 1, 2, 1)>. For convenience, let vi = ∑ x∈G 1x=i and the histogram of G is denoted by Hist(G). We can then define an order relation. Definition 4. For any two histograms v,w, define the order relation as follows. (Hinz & Van de Geer, 2019)
v w :⇔ ∀J ∈ N, ∞∑ j=J vj ≤ ∞∑ j=J wj (6)
It is obvious that any two histograms are not always comparable. But we can define a max operation such that v(i) max ( {v(i)|i ∈ I} ) where I is an index collection. More precisely:
Definition 5. For a finite index collection I , let VI = {v(i)|i ∈ I}, define max operation as follows.
max (VI)J = maxi∈I  ∞∑ j=J v (i) j −max i∈I  ∞∑ j=J+1 v (i) j  for J ∈ N (7) where v(i)j is the j th component of the histogram v(i). (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 a connected and convex set D ⊆ Rn, if there exists a set of linear independent vectors { v(i)|v(i) ∈ Rn, i = 1, . . . , k, k ≤ n } and a fixed vector c ∈ Rn, s.t. (a) any x 6= c ∈ D,
x = c + ∑k i=1 aiv
(i) where {ai} are not all 0; (b) there exists ai 6= 0 s.t. aiv(i) + c ∈ D. Then the 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 1. Suppose D ⊆ Rn is a connected and convex set with space dimension of k (k ≤ n), f is an affine transform with domain of D and can be written as f(x) = Ax+b, where A ∈ Rm×n and b ∈ Rm. Then f(D) is a connected and convex set and
Sd(f(D)) ≤ min(k, rank(A)) (8)
The proof of proposition 1 is given in Appendix A.1.1.
Now we can analyze the relationship between the change of space dimension and activation patterns. Let us first consider the 1st layer in an MLP f . W (1)j,: and b (1) j construct a hyperplane (W (1) j,: x +
b (1) j = 0) in Rn0 and this hyperplane divides the whole region of Rn0 into two parts. One part corresponds to successful activation of the jth node in the 1st layer and the other to unsuccessful activation. This can be represented by the jth component of sh1(x). Therefore all the possible activation pattern sh1(x) is one by one correspondent to the divided regions by n1 hyperplanes of {W (1)j,: x+b (1) j = 0, j = 1, . . . , n1}, which are denoted as Hh1 . For any region D divided by Hh1 , we have h1(x) = W (1)(x(0))x+b(1)(x(0)) where x(0) is any point in D and rank(W (1)(x(0))) ≤ |s|1 where s is the correspondent activation pattern of D. According to proposition 1, h1(D) satisfies that Sd(h1(D)) ≤ min{n0, |s|1}. Similarly, Hh2 divides h1(D) into different parts, and this corresponds to divide D into more sub-regions. In general, every element of S(h(i)) is correspondent to one of regions that are partitioned by Hh1 ,Hh2 , . . . ,Hhi . The next two definitions are used to describe the relationship between the change of space dimension and activation patterns. Definition 7. Define Hsd(Sh) as the space dimension histogram of regions partitioned by a ReLU network defined by Eq.1 where h = {h1, . . . , hL−1}, i.e.
Hsd(Sh) = Hist ({Sd (h (D (s))) | D (s) = {x|Sh (x) = s} , s ∈ S (h)}) . (9) Definition 8. DefineHd (Sh) as the dimension histogram of regions partitioned by a ReLU network defined by Eq.1 where h = {h1, . . . , hL−1}, i.e.
Hd (Sh) = Hist ({ min { n0, |sh1 |1 , ..., |shL−1 |1 } |s ∈ S(h) }) . (10)
We then have the following proposition. Proposition 2. Given a ReLU network defined by Eq.1, let h = {h1, . . . , hL−1}, then Hsd(Sh) Hd (Sh).
The proof of Proposition 2 is given in the Appendix A.1.2. Proposition 2 shows that space dimension is limited by dimension histogram. This idea is used to compute the upper bound.
We can then start to introduce our computational framework. For convenience, we denote RL(n, n′) as one layer of a ReLU MLP with n 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 ∈ RL(n, n′), define Ha(Sh) as the activation histogram of regions partitioned by h, i.e.
Ha(Sh) = Hist ({|s|1 | s ∈ {sh (x) | x ∈ R n}}) . (11)
The activation histogram is similar to the dimension histogram, and it is used to define γ which is a key parameter to construct an upper bound. Definition 10. If γ′n,n satisfies following conditions: (a) ∀n′ ∈ N+, n ∈ {0, . . . , n′}, max {Ha (Sh) |h ∈ RL (n, n′)} γn,n′ ; (b) ∀n′ ∈ N+, n, ñ ∈ {0, . . . , n′} , n ≤ ñ =⇒ γn,n′ γñ,n′ . Then, γn,n′ (n′ ∈ N+, n ∈ 1, ..., n′) satisfies the bound condition. (Hinz & Van de Geer, 2019)
Here, for h ∈ RL(0, n′), we define H(Sh) = e0 = (1, 0, 0, . . . )>. Let Γ be the set of all (γn,n′)n′∈N+,n∈{0,...,n′} that satisfy the bound conditions. When n > n
′, γn,n′ is defined to be equal to γn′,n′ since max {Ha (Sh) |h ∈ RL (n, n′)} is equal to max {Ha (Sh) |h ∈ RL (n′, n′)} (Hinz & Van de Geer, 2019). By the definition γn,n′ represents an upper bound of the activation histogram of regions which are derived from n-dimension space partitioned by n′ hyperplanes. According to Proposition 1, this upper bound is also related to the upper bound of space dimension. Therefore when γn,n′ 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 i∗ ∈ N, define a clipping function cli∗(·) : V → V as follows. (Hinz & Van de Geer, 2019)
cli∗(v)i =  vi for i < i ∗∑∞ j=i∗ vj for i = i ∗
0 for i > i∗ (12)
With the definitions and notations above, we can introduce the computational framework to compute the upper bound of linear regions number as follows.
Proposition 3. For a γ ∈ Γ, define the matrix B(γ)n′ ∈ N(n ′+1)×(n′+1) as(
B (γ) n′ ) i,j = (clj−1 (γj−1,n′))i−1 , i, j ∈ {1, . . . , n ′ + 1} .
Then, the upper bound of linear regions number of an MLP in Eq.1 is∥∥∥B(γ)nL−1MnL−2,nL−1 . . .B(γ)n1 Mn0,n1en0+1∥∥∥ 1 , (13) where Mn,n′ ∈ R(n ′+1)×(n+1), (M)i,j = δi,min(j,n′+1). (Hinz & Van de Geer, 2019)

heading: 3 MAIN RESULTS
text: 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.

heading: 3.1 A TIGHTER UPPER BOUND ON THE NUMBER OF REGIONS
text: Before giving our main results, we define a new function of histograms as follows. Definition 12. Define a downward-move function dm(·) : V→ V by dm(v)i = vi−1. When i = 0, set dm(v)0 = 0.
We then prove the following two theorems used to compute γ. Theorem 1. If γn,n′′ satisfies the bound condition in Definition 10 when n′′ < n′, then
γn,n′ = γn−1,n′−1 + dm(γn,n′−1) (14) also satisfies the bound condition. Theorem 2. Given any h ∈ RL(1, n), its activation histogram Ha(Sh) denoted by v satisfies∑n i=t vi ≤ 2(n− t) + 1.
The proofs of Theorem 1 and 2 are in Appendix A.1.3 and A.1.4 respectively.
From Theorem 2, we can derive a feasible choice of γ1,n whose form is γ1,n = (0, . . . , 0︸ ︷︷ ︸
dn2 e−1 , n mod 2, 2, . . . , 2︸ ︷︷ ︸ bn2 c , 1)> (15)
For example, γ1,4 = (0, 0, 2, 2, 1)>. Since there exists h ∈ RL(1, n) such that Ha(Sh) = γ1,n (the proof can be seen in the Appendix A.1.5), Eq.15 is the tightest upper bound, i.e. max {Ha (Sh) |h ∈ RL (1, n)} satisfies Eq.15. With the fact that max {Ha (Sh) |h ∈ RL (2, 1)} = (1, 1)>, any γn,n′ can be computed.

heading: 3.2 COMPARISON WITH OTHER BOUNDS
text: We use γoursn,n′ and γ serra n,n′ to represent the ones proposed by us and Serra et al. (2018). According to Hinz & Van de Geer (2019),
(γserran,n′)i = { 0, 0 ≤ i < n′ − n( n′
i
) , n′ − n ≤ i ≤ n′
It is easy to verify that γserran,n′ also satisfies Eq.14. But the initial value of γ serra n,n′ is different from γ ours n,n′ and we have that γserra1,n = (0, ..., 0, n, 1) >. Obviously, γours1,n γserra1,n . Since the two operations, + and dm(·), keep the relation of , for any n, n′ ∈ N+, γoursn,n′ γserran,n′ (see an example in Appendix A.2.1). By the following theorem, the upper bound computed by Eq.1 using γoursn,n′ is tighter than γserran,n′ .
Theorem 3. Given γ(1), γ(2) ∈ Γ, if for any n, n′ ∈ N+ such that γ(1)n,n′ γ (2) n,n′ , then upper bound computed by Eq.13 using γ(1) is less than or equal to the one using γ(2).
The proof of Theorem 3 is in Appendix A.1.6. Theorem 3 shows that if we can get a ”smaller” γn,n′ then the upper bound will be tighter. And Theorem 1 implies that if we have a more accurate initial value, e.g. ”smaller” γ2,n or γ3,n, the upper bound could be further improved. Therefore Theorem 1 provides a potential approach to achieve even tighter bound.

heading: 3.3 EXPANSION TO COMMON NETWORK STRUCTURES
text: 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 or unpooling layer can be written as a linear transform., e.g. average-pooling and linear interpolation, it can be denoted by y = Ax. Suppose v is the space dimension of input region and w is the histogram of the output regions. Then we have the following proposition.
Proposition 4. Suppose rank(A) = k, then w clk(v).
Since clk(v) has a matrix computation form which is similar to M in Eq.13, the effect of this type of layer on the space dimension histogram can be regarded as another matrix in Eq.13. Similarly, we have the following proposition for Max-pooling layers.
Proposition 5. Suppose the max-pooling layer is equivalent to a k-rank maxout layer with n input nodes and nl output nodes. Let c = (k2 − k)nl, then
w clnl (diag {|γ0,c|1, . . . , |γn,c|1}v) (16)
The proofs of Proposition 4, Proposition 5 are in 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 a 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 a 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 ∏j k=iAkv. When the input of the i
th layer is concatenated to the jth layer, i.e. a skip connection, then the computation of w will change and satisfies that w ∑ vn |Ben|1 en where
B = ∏j k=iAk. It also has a matrix multiplication form.
Residual structures (He et al., 2016) are similar to skip connections and can be regarded as a skip connection plus a simple full-rank square matrix computation. Therefore its effect on space dimension histogram is the same as the skip connection. Concatenation is equivalent to addition in upper bound computation. Thus, we have the following proposition.
Proposition 7. Suppose that the residual structure adds the input of the ith layer to the output of the jth layer. v,w,B have the same meaning in Proposition 6. Then we have that w ∑ vn |Ben|1 en.
The proofs of Proposition 6 and Proposition 7 are in Appendix A.1.9 and A.1.10. In addition, the analysis for dense connections (Huang et al., 2017) is similar to skip connections and is further discussed in Section 5.
With the above analysis, we can deal with more complex network. For example, a U-net (Ronneberger et al., 2015) is composed of convolutional layers, pooling layers, unpooling layers and skip connections. If we regard convolutional layers as fully-connected layers, then we 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 to Proposition 1 and by using our computational 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.

heading: 4 EXPERIMENTS
text: We perform two experiments in this work. The first one is to compare the bound proposed by us and by Serra et al. (2018) which is illustrated by Figure 1. The upper bounds of MLPs computed and their ratio is calculated to measure the difference. Figure1(a) and Figure 1(b) show how the ratio
changes as the number of hidden layers increases from 1 to 10 with different n0. Figure 1(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, as illustrated in Table 1 and Table 2. 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 to 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×24 or 16×16). In addition, convolutional layers are regarded as fully-connected layers in the computation.

heading: 5 DISCUSSION
text: The proposed upper bound has been theoretically proved to be tighter than Serra et al. (2018). Furthermore, Figure 1(a) and Figure 1(b) show that when ni increases from 0.6n0 to 1.5n0, the ratio curve of two bounds moves upward. However, when ni increases to 2n0, the curve moves downward. And when ni increases further and is much larger than n0, the two bounds are the same. This trend is related to the extent of similarity in B(ours)n and B (serra) n . When ni < n0, Bni affects the upper bound most. And the difference between B(ours)ni and B (serra) ni is more significant when ni decreases. When ni > n0, (Bn):,n0+1, the (n0 + 1) th column of Bn, is the main source of
difference. It is easy to find that the middle part of B(ours)n and B (serra) n differ most while the left and right part are similar (see detials in Appendix A.2.3). As for the Figure 1(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 Serra et al. (2018).
The result in Table 1, 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.1, 3 and 4 in Table 2). However, it seems that when the number of channels is larger, the enhancement is weaker (comparing No.1 to 2, 3 to 4, and No.5 to No.6 in Tabel 1). Similar result can be observed in Table 2 (comparing No.1 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 Pascanu et al. (2013); Montufar et al. (2014); Serra 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 a special case of skip connection but can further increase the dimension 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 A.1.12.

heading: 6 CONCLUSION
text: 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 a 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.

heading: A APPENDIX

heading: A.1 PROOFS

heading: A.1.1 THE PROOF OF PROPOSITION 1
text: Proof. By Definition 6, suppose {v(1),v(2), . . . ,v(k)} and c can be used to represent any x ∈ D and {ai 6= 0} satisfies that ai{v(i) + c ∈ D. Let D′ = D − c, then D′ is a translation of D. Since D is convex, D′ and f(D′) is also convex. Because f(D) = f(D′ + c) = AD′ + Ac + b, then Sd(f(D)) = Sd(AD′). Suppose that D′′ = A(D′) = {Ax|x ∈ R′}. For any y ∈ D′′, there exists x ∈ D′, s.t. y = Ax. Denote Av(i) by w(i), then y can be represented by {w(1),w(2), . . . ,w(k)} and aiw(i) ∈ D′′. From {w(1),w(2), . . . ,w(k)} choose a set of vectors which are linear independent and can linearly represent {w(1),w(2), . . . ,w(k)}. For convenience, suppose they are {w(1),w(2), . . . ,w(t)}, t ≤ k. Therefore any y ∈ D′′ can be represented by {w(1),w(2), . . . ,w(t)}. Thus, Sd(D′′) = Sd(f(D)) = t and we have that
t = rank( [ w(1) . . . w(t) ] )
= rank( [ w(1) . . . w(k) ] )
= rank(A [ v(1) . . . v(k) ] )
≤ min{rank(A), rank( [ v(1) . . . v(k) ] )}
= min{rank(A), k}.
The last equality is derived from that {v(1),v(2), . . . ,v(k)} are k linear independent vectors.

heading: A.1.2 THE PROOF OF PROPOSITION 2
text: Proof. For any s ∈ S(h), suppose D(s) = {x|Sh(x) = s}. As long as Sd (h (D (s))) ≤ min{n0, |sh1 |1 , |sh2 |1 , ..., ∣∣shL−1∣∣1} is established, the proposition can be proved. Apparently, Sd(D(s)) = n0. Through the analysis in Section 2, h(·) in D(s) is an affine transform. For any x(1),x(2) ∈ D(s), W (i)(x(1)) = W (i)(x(2)), b(i)(x(1)) = b(i)(x(2)). Therefore we use x(0) ∈ D(s) to represent them. Then h(·) in D(s) can be written as
h(x) = W (L−1)(x(0))(. . .W (1)(x(0))x + b(1)(x(0))) + b(L−1)(x(0))
= W (x(0))x + b(x(0))
By Proposition 1, we have Sd (h (D (s))) ≤ min { rank(W (x(0))), n0 } = min { n0, rank
( L−1∏ i=1 W (i)(x(0)) )} ≤ min { n0,min { rank ( W (1)(x(0)) ) , . . . , rank ( W (L−1)(x(0))
)}} ≤ min{n0, |sh1 |1 , |sh2 |1 , ...,
∣∣shL−1∣∣1} The last two inequality are derived from that
rank ( L−1∏ i=1 W (i)(x(0)) ) ≤ min{rank(W (1)(x(0))), ...,W (L−1)(x(0)))}
and rank(W (i)(x(0))) ≤ |shi |1.

heading: A.1.3 THE PROOF OF THEOREM 1
text: Proof. Obviously, γn,n′ satisfies the second condition. As for the first condition, consider that hyperplanes {L1, L2, ..., Ln′} divide Rn. These hyperlanes correspond to one h ∈ RL(n, n′) and its activation histogram is denoted by v1. Here, we assume that L1, L2, . . . , Ln′ are not parallel to each other since in parallel case it is easy to imagine and verify that there exists a h′ ∈ RL(n, n′) which satisfies Ha(Sh) Ha(Sh′). Suppose that hyperplanes {L1, L2, . . . , Ln′−1} divide Rn into t regions {R1, R2, ..., Rt} and their activation histogram is denoted by v2. Assume that Ln′ crosses {R1, R2, ..., Rp}, p ≤ t and divides them into 2p regions. Let v3 denote the activation histogram of {R1, R2, . . . , Rp}. p regions of them are active by Ln′ while other p regions are not. Part of {Rp+1, Rp+2, ..., Rt} are active by Ln′ while the rest regions are not. Their activation histogram are denoted as v4 and v5 respectively. Then we have the following equations:
v2 = v3 + v4 + v5 (17) v1 = v3 + dm(v3) + dm(v4) + v5 (18)
Let us only focus on {R1.R2, ..., Rp}. Suppose {L1, L2, ..., Lm}(m ≤ n′ − 1) are borders of these regions. {Ln′ ∩ L1, Ln′ ∩ L2, ..., Ln′ ∩ Lm} are hyperplanes in Ln′ , and their active directions are projections of {L1, L2, ..., Lm} in Rn. So the activation histogram of {Ln′ ∩L1, Ln′ ∩L2, ..., Ln′ ∩ Lm} in Ln′ which is denoted by v6 is equal to v3. By the assumption that when n′′ < n′, γn,n′′ satisfies the bound condition, we have
v3 = v6 γn−1,m γn−1,n′−1. (19)
By Eq.17, Eq.18 and Eq.19, v1 satisfies
v1 γn−1,n′−1 + dm(v3 + v4 + v5) = γn−1,n′−1 + dm(v2)
γn−1,n′−1 + dm(γn,n′−1) (20)
Because of the arbitrariness of v1, we can get γn,n′ = γn−1,n′−1 + dm(γn,n′−1) which satisfies the first condition.

heading: A.1.4 THE PROOF OF THEOREM 2
text: Proof. For 1-dimension space, its hyperlane is one point in the number axis and the activation direction is either left or right. It is apparent that n segmentation points divide one line into n + 1 parts. And for any x ∈ R, its activation number is at most n. Therefore if t < dn2 e, then∑n i=t vi ≤ n + 1 ≤ 2(n − t) + 1. If t ≥ d n 2 e, the activation pattern of n + 1 regions in R is denoted by {s1, s2, . . . , sn+1} (see Figure 2(a)). No matter how the activation directions of n points are, we have |s1|+ |sn+1| = n since |s1| is equal to the number of left activation directions and |sn+1| is equal to the number of right activation direction. Another obvious conclusion is that
|si| − |si+1| = ±1 as the activation patterns of neighboring regions only differ at the ith point. Without loss of generality, let |s1| ≤ dn2 e. Any line chart of active numbers with dotted line is under the line chart with solid line (see Figure 2(b)). So regions with active numbers larger than or equal to t are among ath and bth region. Apparently, the number of regions among ath and bth region is 2(n− t) + 1. So ∑n i=t vi ≤ 2(n− t) + 1.

heading: A.1.5 THE PROOF OF EQ.15
text: Proof. Suppose the n points of h in the number axis are p1, p2, ..., pn. Let the direction sof p1, ..., pbn2 care right and other points left. It is easy to verify that Ha(Sh) = γ1,n where γ1,n is defined by
γ1,n = (0, . . . , 0︸ ︷︷ ︸ dn2 e−1 , n mod 2, 2, . . . , 2︸ ︷︷ ︸ bn2 c , 1)>
Then γ1,n max {Ha (Sh) |h ∈ RL(1, n)}. Since max {Ha (Sh) |h ∈ RL(1, n)} γ1,n, γ1,n = max {Ha (Sh) |h ∈ RL(1, n)}.

heading: A.1.6 THE PROOF OF THEOREM 3
text: Proof. Different Bγn′ can be derived from different γn,n′ . Since the clipping function keep the order relation , every column of Bγ (1)
n′ and B γ(2)
n′ in the same position satisfy that( Bγ (1)
n′ ) :,j ( Bγ (2) n′ ) :,j
Another fact is that when v w, then |v|1 ≤ |w|1. Here we prove that if v w, then
Mni,ni+1v Mni,ni+1w (21)
and
Bγ (1) ni v B γ(2) ni w (22)
Then the theorem can derived easily from Eq.21 and Eq.22.
Because Mni,ni+1v = clni+1(v), Eq.21 is easy to verified. For B γ(k) ni , k = 1, 2, we have that( Bγ (k)
ni ) :,j1 ( Bγ (k) ni ) :,j2 when j1 ≤ j2 because of the second condition in Definition 10 and the
property of the clipping function. For convenience, ( Bγ (k)
ni ) m,j is denoted by B(k)m,j , k = 1, 2. By
Definition 5, we have that ∞∑
m=M
( B(1)v ) m ≤ ∞∑ m=M ( B(2)w ) m
⇐⇒ ∞∑
m=M  ∞∑ j=0 B (1) m,jvj  m ≤ ∞∑ m=M  ∞∑ j=0 B (2) m,jwj  m
⇐⇒ ∞∑ j=0 ( ∞∑ m=M B (1) m,j ) vj ≤ ∞∑ j=0 ( ∞∑ m=M B (2) m,j ) wj
Because B(1):,j B (2) :,j , i.e. ∀M ≥ 0, ∑∞ m=M B (1) m,j ≤ ∑∞ m=M B (2) m,j . Let aj = ∑∞ m=M B
(1) m,j , bj =∑∞
m=M B (2) m,j , then aj ≤ bj . Because B (k) :,j1 B(k):,j2 when j1 < j2, then
a0 ≤ a1 ≤ a2 ≤ ... (23) and b0 ≤ b1 ≤ b2 ≤ ... (24) By the notations, we have that
∞∑ j=0 ( ∞∑ m=M B (1) m,j ) vj ≤ ∞∑ j=0 ( ∞∑ m=M B (2) m,j ) wj
⇐⇒ ∞∑ j=0 ajvj ≤ ∞∑ j=0 bjwj
⇐⇒ ni∑ j=0 ajvj ≤ ni∑ j=0 bjwj
The last equivalence is derived from that vj = wj = 0 when j > ni. Consider the left part of last inequality. Employing v w ⇔ ∑ni j=J vj ≤ ∑ni j=J wj and Eq.24, the following inequality can be derived
ni∑ j=0 ajvj ≤ ni∑ j=0 bjvj = b0v0 + ni∑ j=1 bjvj ≤ b0  ni∑ j=0 wj − ni∑ j=1 vj + ni∑ j=1 bjvj
≤ b0w0 + b1  ni∑ j=1 wj − ni∑ j=1 vj + ni∑ j=1 bjvj = b0w0 + b1w1 + b1  ni∑ j=2 wj − ni∑ j=2 vj + ni∑ j=2 bjvj ≤ 1∑ j=0 bjwj + b2  ni∑ j=2 wj − ni∑ j=2 vj + ni∑ j=2 bjvj = 2∑ j=0 bjwj + b2  ni∑ j=3 wj − ni∑ j=3 vj + ni∑ j=3 bjvj
...
≤ ni−1∑ j=0 bjwj + bni (wni − vni) + bnivni = ni∑ j=0 bjwj
Therefore the left part is less than the right part, i.e. Eq.22 is established and the theorem is proved.

heading: A.1.7 THE PROOF OF PROPOSITION 4
text: Proof. Consider any input region D. Let D′ is the corresponding output region, i.e. D′ = A(D). By Proposition 1, Sd(D′) ≤ min{Sd(D), k}. Because
Hist({min{Sd(D), k}| D is any input region}) = clk(v)
then w clk(v). Suppose v ∈ Rn+1, i,e, vi = 0 when i > n, it is easy to verify that clk(v) = Mn,kv, where
Mn,k ∈ R(k+1)×(n+1), (M)i,j = δi,min(j,n+1)

heading: A.1.8 THE PROOF OF PROPOSITION 5
text: Before the proof, we show the following lemma. Lemma 1. Suppose γn,n′ satisfies the recursion formula in Theorem 1 and the initial value satisfies
that |γn1,n2 |1 = ∑n1 s=0 ( n2 s ) , then any γn,n′ satisfies |γn,n′ |1 = ∑n s=0 ( n′ s ) .
Proof. Since γn,n′ = γn−1,n′−1 + dm(γn,n′−1) and dm(·) does not change | · |1, we have |γn,n′ |1 = |γn−1,n′−1|1 + |γn,n′−1|1. By the assumption, suppose that |γn1,n2 |1 = ∑n1 s=0 ( n2 s ) is established when n1 ≤ n and n2 < n′. Then
|γn,n′ |1 = n−1∑ s=0 ( n′ − 1 s ) + n∑ s=0 ( n′ − 1 s )
= n∑ s=1 (Cn ′−1 s + C n′−1 s−1 ) + C n′−1 0
= n∑ s=1 Cn ′ s + C n′ 0
= n∑ s=0 ( n′ s ) Therefore any γn,n′ satisfies the formula. It is easy to verify that |γ1,n|1 = n + 1 = ∑1 s=0 ( n s ) and |γ2,1|1 = 2 = ∑2 s=0 ( 1 s ) . By
Lemma 1, γn,n′ proposed by us satisfies that |γn,n′ |1 = ( n′
s
) . Next we prove Proposition 5.
Proof. Denote the maxout layer by h, according to the proof of Theorem 10 in Serra et al. (2018), one k-rank maxout layer with nl output nodes corresponds to divide one region by k(k − 1)
2 nl
hyperplanes. Suppose R is one input region with Sd(R) = n′ and partitioned into p sub-regions {r1, ..., rp}. Since one d-dimension space is at most partitioned into ∑d s=0 ( m s ) sub-regions by
m hyperplanes, then by Lemma 1
p ≤ n′∑ s=0 ( k(k−1)nl 2 s ) = |γn′,c|1
For any sub-region pi, Sd(pi) = n′. Since h is equivalent to an affine transform in pi with matrix A of rank nA, we have that Sd(h(pi)) ≤ min{nA, n′} by Proposition 1. Another fact is that nA ≤ nl. Therefore Sd(h(pi)) ≤ min{nl, n′}. That is to say, R with n′ space dimension is divided in to at most |γn′,c|1 sub-regions and the space dimension of each output sub-region is no larger than min{nl, n′}. If the space dimension histogram of input regions is v (∈ Rn) , then it is easy to verify that after the partition by h, the histogram of sub-regions v′ satisfies that v′ diag {|γ0,c|1, . . . , |γn,c|1}v. In addition, h change their space dimension. Thus
w clnl(v′) clnl(diag {|γ0,c|1, . . . , |γn,c|1}v). Let C = diag {|γ0,c|1, . . . , |γn,c|1}, then clnl(diag {|γ0,c|1, . . . , |γn,c|1}v) = Mn,nlCv.

heading: A.1.9 THE PROOF OF PROPOSITION 6
text: Proof. When the skip connection is not added, w Bv. Let v = en, i.e. the the number of the input regions is one. Suppose the region isR ⊆ Rm andR is divided into p sub-regions. Apparently p ≤ |Ben| and Sd(R) = Sd(r) = n ≤ m where r is one of the sub-regions. Suppose the part of network which is from the ith layer to the jth layer is equivalent to an affine transform with matrix
C. Let r′ = C(r). When the skip connection is added, the output of r is [ C I ] (r) denoted by r′′.
Since rank ([
C I
]) = m, Sd(r′′) ≤ min{m,Sd(r)} = n. This implies that the space dimension
of r′ may be enhanced to n. Therefore the space dimension histogram of p sub-regions wR satisfies that wR |Ben|1en. (25) For any input region with n space dimension, Eq.25 is always established. Thus, when the space dimension histogram of input regions is v the histogram of output regions satisfies
w ∑ R wR ∑ R |BeSd(R)|1eSd(R) = ∑ n vn |Ben|1 e n. (26)
Let C = diag{|Be0|1, |Be2|1, ..., |Ben|1, ...}, then ∑ n vn |Ben|1 en = Cv.

heading: A.1.10 THE PROOF OF PROPOSITION 7
text: Proof. Any residual structure can be regarded as the composition of one skip connection and an linear transform. For any input region r ⊆ Rm partitioned by the network, the residual structure part has the following form.
y = Res(x) = [I I] [ C I ] x,x ∈ r
By Proposition 6, the space dimension histogram of output regions [ C I ] (r) denoted by w satisfies
that w ∑ vn |Ben|1 e n
Since rank([I I]) = m ≥ Sd(r), according to Proposition 1 the linear transform will not change the histogram.

heading: A.1.11 PROPOSITION 8 AND ITS PROOF
text: Proposition 8. For an MLP, let fm represent the first m layers (1 ≤ m ≤ l), i.e. fm(x) is the output of the mth layer, and Fl+1(z) = σ(W (l+1)z + b(l+1)) representing the (l+ 1)th layer in the MLP. Consider another network layer,
Gl+1(z,y) = σ
( W (l+1,′) [ z y ] + b(l+1,′) ) where z = fl(x) ∈ Rnl ,y = fm(x) ∈ Rnm , 1 < m < l. Then, given a specific Fl+1, there exists a Gl+1 such that the the total number of regions partitioned by Gl+1 is no more less than that by Fl+1.
Proof. For a connected set R ⊆ input space, fl(R) and fm(R) are still connected sets. For each hyperplane Hi represented by ∑nl j=1 ai,jzj + bi = 0 in Fl+1, design corresponding hyperplane H
′ i ,∑nl j=1 ai,jzj+ ∑nm j=1 ci,jyj+bi = 0, inGl+1, where ci,j = 0. SupposeHi crosses {R1, R2, ..., Rki} and take ki intersections {p1,p2, ...,pki} where pj is a interior point in Rj(1 ≤ j ≤ ki). Let fl(xj) = pj , then (fl(xj), (fm(xj)) ∈ H ′i and it is also a interior point in R′j which is the same as Rj when cutting last nm dimensions. So H ′i crosses at least ki regions which indicates the total number of regions partitioned by Gl+1 is no more less than that by Fl+1.

heading: A.1.12 PROPOSITION 9 AND ITS PROOF
text: Proposition 9. For a three-layer MLP which has two hidden layers, i.e.
f(x) = W (3)σ(W (2)σ(W (1)x + b1) + b (2)) + b(3), (27)
suppose that n0 = 1 and every segment partitioned by the first layer keeps their space dimension, i.e. their output of the first layer is still segment. If the input is concatenated to the output of the first layer (just like a skip connection), then no matter what the parameters in the first layer are, the practical maximum number of linear regions is (n1 + 1)(n2 + 1). Specifically, without the special structure (just like an MLP) and assume that n1 = 3, there exists some parameters in the first layer such that the practical maximum number is no more than (n1 + 1)(n2 + 1)− n2.
Proof. Denote h1(x) = σ(W (1)x + b(1)). The first layer divides input space into n1 + 1 regions {r1, r2, ...rn1+1}, then h1(ri) ⊆ R. Because of the skip connection, the dimension of hyperplanes in the second layer is n1. It is apparent that for any n1 + 1 points there always exits a hyperplane containing them. Thus, for any interior point xi ∈ ri(1 ≤ i ≤ n1 + 1), there exists a hyperplane contaning them and therefore crossing n1 + 1 regions. We have n2 hyperplanes in the second layer, which shows the number of linear regions is (n1 +1)(n2 +1). And obviously the maximum number is not larger than it (see Theorem 7 in Serra et al. (2018))
As for the special case, take [0, 1] as input space without loss of generality. Let
W1 =  1t1− 1t2 1 t3  , 1 = [−11 −1 ] (28)
Then we get four output regions in R3 shown in Figure 3. We can see that R1, R2 and R3 are on the same plane, i.e. the x-y plane. For any interior points pi ∈ Ri, i = 1, 2, 3, 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 (n1 + 1)(n2 + 1)− n2.

heading: A.2 EXAMPLES
text: A.2.1 AN EXAMPLE OF γnewn,n′ AND γ serra n,n′
Here n′ = 6. Then γoursn,n′ and γ serra n,n′ are shown as follows.
0 0 0 0 0 0 1 0 0 0 0 1 6 6 0 0 1 4 14 15 15 0 2 5 16 20 20 20 0 2 9 15 15 15 15 0 2 6 6 6 6 6 1 1 1 1 1 1 1  γours·,6

0 0 0 0 0 0 1 0 0 0 0 0 6 6 0 0 0 0 15 15 15 0 0 0 20 20 20 20 0 0 15 15 15 15 15 0 6 6 6 6 6 6 1 1 1 1 1 1 1  γserra·,6
(29)

heading: A.2.2 AN EXAMPLE OF UPPER BOUND COMPUTATION FOR U-NET
text: We take the U-net in Appendix A.3.1 as example. Firstly, we use matrices to represent all layers except skip connections. When computing upper bound convolutional layers are regarded as fullyconnected layers denoted by Ci. Suppose pooling layers are average pooling layers and unpooling ones are filling-zero ones. They are denoted by Pi and Ui. Here, the subscript i means the order in the network. Then according to Proposition 3 and Proposition 4 we have
C1 = B2304,C2 = B1152,C3 = B576,C4 = B288,
C5 = B144,C6 = B288,C7 = B576,C8 = B2304
P1 = M2304,576,P2 = M1152,288,P3 = M576,144,
U1 = M144,144 = I144,U2 = M288,288 = I288,U3 = M576,576 = I576.
where B, M are defined by Proposition 3. By Proposition 6, the upper bound N is computed as follows.
S′3 = U1C5M288,144C4M144,288P3 ∈ R144×576 S3 = diag{|S′3e0|1, |S′3e2|1, . . . , |S′3e576|1, } ∈ R576×576 S′2 = U2C6M576,288S3C3M288,576P2 ∈ R288,1152 S2 = diag{|S′2e0|1, |S′2e2|1, . . . , |S′2e1152|1, } ∈ R1152×1152 S′1 = U1C7M1152,576S2C2M576,1152P1 ∈ R576,2304 S1 = diag{|S′1e0|1, |S′1e2|1, . . . , |S′1e2304|1, } ∈ R1152×1152
N = |C8S1C1M576,2304e576|1
A.2.3 THE COMPARISON OF Boursn AND B serra n
Here we consider n = 6. By Eq.29 and the definition of clipping function, we have
1 0 0 0 0 0 1 0 7 0 0 1 6 6 0 0 22 4 14 15 15 0 0 0 38 20 20 20 0 0 0 0 22 15 15 0 0 0 0 0 7 6 0 0 0 0 0 0 1  Bours6

1 0 0 0 0 0 1 0 7 0 0 0 6 6 0 0 22 0 15 15 15 0 0 0 42 20 20 20 0 0 0 0 22 15 15 0 0 0 0 0 7 6 0 0 0 0 0 0 1  Bserra6

heading: A.2.4 AN SIMPLE EXAMPLE OF IMPERFECT PARTITION
text: In this part, we use a simple example (in Figure 4) to illustrate imperfect partition. Consider a two-layer MLPs with n0 = 1, n1 = 2. The original input space is 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 R2 are shown in Figure 4(b). In Figure 4(c), it is easy to observe that any hyperplane can not partition all three regions simultaneously.

heading: A.3 NETWORK ARCHITECTURES

heading: A.3.1 NETWORK ARCHITECTURES IN TABLE 1
text: We take the first setting in Table 1 as example. The numbers of ”4-8-16-32” correspond to one in red color in Figure 5 and 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 in every convolutional layer is (3 × 3) with stride = 1. We keep the size unchanged after the convolutional layer by padding zero. We use average-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.

heading: A.3.2 NETWORK ARCHITECTURES IN TABLE 2
text: We also take the first setting in Table 2 as example. The numbers of ”4-p16-p16-r16-r16-r16” correspond to one in red color in Figure 6. ”p” means that before the convolutional layer, there exists a 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.

Review summaries:
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. 

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.