# A General Computational Framework to Measure the Expressiveness of Complex
Networks using a Tight Upper Bound of Linear Regions

Yutong Xie & Gaoxiang Chen
Academy for Advanced Interdisciplinary Studies
Peking University
Beijing, 100871, China
<EMAIL_ADDRESS>
Quanzheng Li
MGH/BWH Center for Clinical Data Science, Department of Radiology
Massachusetts General Hospital and Harvard Medical School
Boston, MA 02114, USA
<EMAIL_ADDRESS>

###### 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.

##  1 Introduction

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, rectiﬁed 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 $\gamma$,
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.

##  2 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 et al. (2014) give a simple but improved
upper bound compared with Pascanu et al. (2013). Montú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 Montú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;
Montúfar, 2017; Serra et al., 2018)

###  2.2 Notations, definitions and properties

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({\bm{x}})={\bm{W}}^{(L)}\underbrace{\sigma({\bm{W}}^{(L-1)}\cdots\sigma}_{(L-1)}({\bm{W}}^{(1)}{\bm{x}}+{\bm{b}}^{(1)})\cdots+{\bm{b}}^{(L-1)})+{\bm{b}}^{(L)}$
(1)

where ${\bm{x}}\in\mathbb{R}^{n_{0}},{\bm{W}}^{(i)}\in\mathbb{R}^{n_{i}\times
n_{i-1}},{\bm{b}}^{(i)}\in\mathbb{R}^{n_{i}}$ and
$\sigma({\bm{x}})=\max({\bm{x}},0)$ denoting the ReLU function.
${\bm{W}}^{(i)}$ is the weights in the $i^{\text{th}}$ layer and
${\bm{b}}^{(i)}$ is the bias vector. $f({\bm{x}})$ can also be written as:

$\displaystyle{h_{0}}({\bm{x}})$
$\displaystyle={\bm{x}},{h_{i}}({\bm{x}})=\sigma({\bm{W}}^{(i)}h_{i-1}({\bm{x}})+{\bm{b}}^{(i)}),1\leq
i<L,$ (2) $\displaystyle f({\bm{x}})$
$\displaystyle={h_{L}}({\bm{x}})={\bm{W}}^{(L)}h_{L-1}({\bm{x}})+{\bm{b}}^{(L)}$
(3)

Firstly, we define the linear region in the following way.

######  Definition 1.

For a PWL function
$f({\bm{x}}):\mathbb{R}^{n_{0}}\rightarrow\mathbb{R}^{n_{L}}$, we define
${\mathbb{D}}$ is a linear region, if ${\mathbb{D}}$ satisfies that: (a)
${\mathbb{D}}$ is connected; (b) $f$ is an affine function on ${\mathbb{D}}$;
(c) Any ${{\mathbb{D}}}^{\prime}\supsetneqq{\mathbb{D}}$, $f$ is not affine on
${{\mathbb{D}}}^{\prime}$.

For a PWL function $f$, the domain can be partitioned into different linear
regions. Let

${\mathbb{P}}(f)=\\{{\mathbb{D}}_{i}|{\mathbb{D}}_{i}\text{ is a linear region
of
}f,\forall{\mathbb{D}}_{i}\neq{\mathbb{D}}_{j},{\mathbb{D}}_{i}\cap{\mathbb{D}}_{j}=\emptyset\\}$

represent all the linear regions of $f$. We then define the activation pattern
of ReLU DNNs as follows.

######  Definition 2.

For any ${\bm{x}}\in\mathbb{R}^{n_{0}}$, we define the activation pattern of
${\bm{x}}$ in $i^{\text{th}}$ layer
${\bm{s}}_{{h}_{i}}({\bm{x}})\in\\{0,1\\}^{n_{i}}$ as follows.

${\bm{s}}_{{h}_{i}}({\bm{x}})_{j}=\left\\{\begin{matrix}1,&\text{ if
}{\bm{W}}^{(i)}_{j,:}{h}_{i-1}({\bm{x}})+{b}^{(i)}_{j}>0\\\ 0,&\text{ if
}{\bm{W}}^{(i)}_{j,:}{h}_{i-1}({\bm{x}})+{b}^{(i)}_{j}\leq
0\end{matrix}\right.,\text{ for
}i\in\\{1,2,\dots,L-1\\},j\in\\{1,2,\dots,n_{i}\\},$

where ${\bm{W}}^{(i)}_{j,:}$ is the $j^{\text{th}}$ row of ${\bm{W}}^{(i)}$,
${b}^{(i)}_{j}$ is the $j^{\text{th}}$ component of ${\bm{b}}^{(i)}$. (Hinz &
Van de Geer, 2019)

For any ${\bm{x}}$, $h_{i}({\bm{x}})$ can be rewritten as
$h_{i}({\bm{x}})={\bm{W}}^{(i)}({\bm{x}})h_{i-1}({\bm{x}})+{\bm{b}}^{(i)}({\bm{x}})$,
where ${\bm{W}}^{(i)}({\bm{x}})$ is a matrix with some rows of zeros and
${\bm{b}}^{(i)}({\bm{x}})$ is a vector with some zeros. More precisely,

${\bm{W}}^{(i)}({\bm{x}})_{j,:}=\left\\{\begin{matrix}{\bm{W}}^{(i)}_{j,:},&\text{if
}s_{h_{i}}({\bm{x}})_{j}=1;\\\ \bm{0},&\text{if
}s_{h_{i}}({\bm{x}})_{j}=0.\end{matrix}\right.\quad\quad
b^{(i)}({\bm{x}})_{j}=\left\\{\begin{matrix}b^{(i)}_{j},&\text{if
}s_{h_{i}}({\bm{x}})_{j}=1;\\\ 0,&\text{if
}s_{h_{i}}({\bm{x}})_{j}=0.\end{matrix}\right.$ (4)

To conveniently represent activation patterns of multi-layer in a MLP, we
denote ${\bm{h}}^{(i)}=\\{h_{1},...,h_{i}\\}$, where $h_{i}$ is defined in
Eq.2, and
$\bm{S}_{{\bm{h}}^{(i)}}({\bm{x}})=({\bm{s}}_{{h}_{1}}({\bm{x}}),...,{\bm{s}}_{{h}_{i}}({\bm{x}}))$,
${\mathbb{S}}({\bm{h}}^{(i)})=\\{\bm{S}_{{\bm{h}}^{(i)}}({\bm{x}})|{\bm{x}}\in\mathbb{R}^{n_{0}}\\}$.
Given a fixed ${\bm{x}}$, it is easy to prove that $h_{i}({\bm{x}})$ is an
affine transform ($i=1,2,\dots,L$). Suppose that
${\bm{s}}\in\\{0,1\\}^{n_{1}}\times\cdots\times\\{0,1\\}^{n_{L-1}},{\bm{h}}=\\{h_{1},...,h_{L-1}\\}$
and ${\bm{h}}({\bm{x}})$ represents $h_{L-1}({\bm{x}})$, if
${\mathbb{D}}=\\{{\bm{x}}|\bm{S}_{{\bm{h}}}({\bm{x}})={\bm{s}}\\}\neq\emptyset$,
then $f$ is an affine transform in ${\mathbb{D}}$. And it is easy to prove
that there exists a linear region ${\mathbb{D}}^{\prime}$ so that
${\mathbb{D}}\subseteq{\mathbb{D}}^{\prime}$. Therefore we have
$|{\mathbb{P}}(f)|\leq|{\mathbb{S}}({\bm{h}})|$.

In our computational framework, histogram is a key concept and defined as
follows.

######  Definition 3.

Define a histogram ${\bm{v}}$ as follows. (Hinz & Van de Geer, 2019)

${\bm{v}}\in{\mathbb{V}}=\left\\{{\bm{x}}\in\mathbb{N}^{\mathrm{N}}|\ \|\
{\bm{x}}\|_{1}=\sum_{j=0}^{\infty}x_{j}<\infty\right\\}$ (5)

A histogram is used to represent a discrete distribution of $\mathbb{N}$. For
example, the histogram of non-negative integers
${\mathbb{G}}=\\{1,0,1,4,3,2,3,1\\}$ is $(1,3,1,2,1)^{\top}$. For convenience,
let $v_{i}=\sum_{x\in{\mathbb{G}}}\bm{1}_{x=i}$ and the histogram of $G$ is
denoted by $\mathrm{Hist}({\mathbb{G}})$. We can then define an order
relation.

######  Definition 4.

For any two histograms ${\bm{v}},{\bm{w}}$, define the order relation
$\preceq$ as follows. (Hinz & Van de Geer, 2019)

${\bm{v}}\preceq{\bm{w}}:\Leftrightarrow\forall
J\in\mathbb{N},\sum_{j=J}^{\infty}v_{j}\leq\sum_{j=J}^{\infty}w_{j}$ (6)

It is obvious that any two histograms are not always comparable. But we can
define a $\max$ operation such that
${\bm{v}}^{(i)}\preceq\max\left(\\{{\bm{v}}^{(i)}|i\in I\\}\right)$ where $I$
is an index collection. More precisely:

######  Definition 5.

For a finite index collection $I$, let
${\mathbb{V}}_{I}=\\{{\bm{v}}^{(i)}|i\in I\\}$, define $\max$ operation as
follows.

$\max\left({\mathbb{V}}_{I}\right)_{J}=\max_{i\in
I}\left(\sum_{j=J}^{\infty}{v}^{(i)}_{j}\right)-\max_{i\in
I}\left(\sum_{j=J+1}^{\infty}{v}^{(i)}_{j}\right)\quad\text{ for
}J\in\mathbb{N}$ (7)

where ${v}^{(i)}_{j}$ is the $j^{\text{th}}$ component of the histogram
${\bm{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 ${\mathbb{D}}\subseteq\mathbb{R}^{n}$, if there
exists a set of linear independent vectors
$\left\\{{\bm{v}}^{(i)}|{\bm{v}}^{(i)}\in\mathbb{R}^{n},i=1,\dots,k,k\leq
n\right\\}$ and a fixed vector ${\bm{c}}\in\mathbb{R}^{n}$, s.t. (a) any
${\bm{x}}\neq{\bm{c}}\in{\mathbb{D}}$,
${\bm{x}}={\bm{c}}+\sum^{k}_{i=1}a_{i}{\bm{v}}^{(i)}$ where $\\{a_{i}\\}$ are
not all $0$; (b) there exists $a_{i}\neq 0$ s.t.
$a_{i}{\bm{v}}^{(i)}+{\bm{c}}\in{\mathbb{D}}$. Then the space dimension of
${\mathbb{D}}$ is $k$ and denote it as $\mathrm{Sd}({\mathbb{D}})=k$.

The following proposition shows the change of space dimension after an affine
transform.

######  Proposition 1.

Suppose ${\mathbb{D}}\subseteq\mathbb{R}^{n}$ is a connected and convex set
with space dimension of $k$ ($k\leq n$), $f$ is an affine transform with
domain of ${\mathbb{D}}$ and can be written as
$f({\bm{x}})={\bm{A}}{\bm{x}}+{\bm{b}}$, where ${\bm{A}}\in\mathbb{R}^{m\times
n}$ and ${\bm{b}}\in\mathbb{R}^{m}$. Then $f({\mathbb{D}})$ is a connected and
convex set and

$\mathrm{Sd}(f({\mathbb{D}}))\leq\min(k,\mathrm{rank}({\bm{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 $1$st layer in an MLP $f$.
${\bm{W}}^{(1)}_{j,:}$ and ${b}^{(1)}_{j}$ construct a hyperplane
(${\bm{W}}^{(1)}_{j,:}{\bm{x}}+{b}^{(1)}_{j}=0$) in $\mathbb{R}^{n_{0}}$ and
this hyperplane divides the whole region of $\mathbb{R}^{n_{0}}$ into two
parts. One part corresponds to successful activation of the $j^{\text{th}}$
node in the $1$st layer and the other to unsuccessful activation. This can be
represented by the $j^{\text{th}}$ component of ${\bm{s}}_{h_{1}}({\bm{x}})$.
Therefore all the possible activation pattern ${\bm{s}}_{h_{1}}({\bm{x}})$ is
one by one correspondent to the divided regions by $n_{1}$ hyperplanes of
$\\{{\bm{W}}^{(1)}_{j,:}{\bm{x}}+{b}^{(1)}_{j}=0,j=1,\dots,n_{1}\\}$, which
are denoted as ${\mathbb{H}}_{h_{1}}$. For any region ${\mathbb{D}}$ divided
by ${\mathbb{H}}_{h_{1}}$, we have
$h_{1}({\bm{x}})={\bm{W}}^{(1)}({\bm{x}}^{(0)}){\bm{x}}+{\bm{b}}^{(1)}({\bm{x}}^{(0)})$
where ${\bm{x}}^{(0)}$ is any point in ${\mathbb{D}}$ and
$\mathrm{rank}({\bm{W}}^{(1)}({\bm{x}}^{(0)}))\leq|{\bm{s}}|_{1}$ where
${\bm{s}}$ is the correspondent activation pattern of ${\mathbb{D}}$.
According to proposition 1, $h_{1}({\mathbb{D}})$ satisfies that
$\mathrm{Sd}(h_{1}({\mathbb{D}}))\leq\min\\{n_{0},|{\bm{s}}|_{1}\\}$.
Similarly, ${\mathbb{H}}_{h_{2}}$ divides $h_{1}({\mathbb{D}})$ into different
parts, and this corresponds to divide ${\mathbb{D}}$ into more sub-regions. In
general, every element of ${\mathbb{S}}({\bm{h}}^{(i)})$ is correspondent to
one of regions that are partitioned by
${\mathbb{H}}_{h_{1}},{\mathbb{H}}_{h_{2}},\dots,{\mathbb{H}}_{h_{i}}$. The
next two definitions are used to describe the relationship between the change
of space dimension and activation patterns.

######  Definition 7.

Define $\mathcal{H}_{\mathrm{sd}}({\mathbb{S}}_{{\bm{h}}})$ as the space
dimension histogram of regions partitioned by a ReLU network defined by Eq.1
where ${\bm{h}}=\\{h_{1},\dots,h_{L-1}\\}$, i.e.

$\mathcal{H}_{\mathrm{sd}}({\mathbb{S}}_{{\bm{h}}})=\mathrm{Hist}\left(\left\\{\mathrm{Sd}\left(\bm{h}\left({\mathbb{D}}\left({\bm{s}}\right)\right)\right)\mid{\mathbb{D}}\left({\bm{s}}\right)=\left\\{{\bm{x}}|\bm{S}_{\bm{h}}\left({\bm{x}}\right)={\bm{s}}\right\\},\bm{s}\in{\mathbb{S}}\left({\bm{h}}\right)\right\\}\right).$
(9)

######  Definition 8.

Define $\mathcal{H}_{\mathrm{d}}\left({\mathbb{S}}_{{\bm{h}}}\right)$ as the
dimension histogram of regions partitioned by a ReLU network defined by Eq.1
where ${\bm{h}}=\\{h_{1},\dots,h_{L-1}\\}$, i.e.

$\mathcal{H}_{\mathrm{d}}\left({\mathbb{S}}_{{\bm{h}}}\right)=\mathrm{Hist}\left(\left\\{\min\left\\{n_{0},\left|{\bm{s}}_{h_{1}}\right|_{1},...,|{\bm{s}}_{h_{L-1}}|_{1}\right\\}|\bm{s}\in{\mathbb{S}}({\bm{h}})\right\\}\right).$
(10)

We then have the following proposition.

######  Proposition 2.

Given a ReLU network defined by Eq.1, let
${\bm{h}}=\\{h_{1},\dots,h_{L-1}\\}$, then
$\mathcal{H}_{\mathrm{sd}}({\mathbb{S}}_{{\bm{h}}})\preceq\mathcal{H}_{\mathrm{d}}\left({\mathbb{S}}_{{\bm{h}}}\right)$.

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 $\mathrm{RL}(n,{n}^{\prime})$ as one layer of a ReLU MLP with $n$
input nodes and $n^{\prime}$ output nodes (containing one linear transform and
one ReLU activation function), and define its activation histogram as follows.

######  Definition 9.

Given $h\in\mathrm{RL}(n,n^{\prime})$, define
$\mathcal{H}_{\mathrm{a}}({\mathbb{S}}_{h})$ as the activation histogram of
regions partitioned by $h$, i.e.

$\mathcal{H}_{\mathrm{a}}({\mathbb{S}}_{h})=\mathrm{Hist}\left(\left\\{\left|{\bm{s}}\right|_{1}\mid{\bm{s}}\in\left\\{\bm{s}_{h}\left({\bm{x}}\right)\mid{\bm{x}}\in\mathbb{R}^{n}\right\\}\right\\}\right).$
(11)

The activation histogram is similar to the dimension histogram, and it is used
to define $\gamma$ which is a key parameter to construct an upper bound.

######  Definition 10.

If $\gamma_{n,{n}}^{\prime}$ satisfies following conditions: (a) $\forall
n^{\prime}\in\mathbb{N}_{+},n\in\left\\{0,\ldots,n^{\prime}\right\\}$,
$\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}\left(n,n^{\prime}\right)\right\\}\preceq\gamma_{n,n^{\prime}}$;
(b) $\forall
n^{\prime}\in\mathbb{N}_{+},n,\tilde{n}\in\left\\{0,\ldots,n^{\prime}\right\\},n\leq\tilde{n}\Longrightarrow\gamma_{n,n^{\prime}}\preceq\gamma_{\tilde{n},n^{\prime}}$.
Then, $\gamma_{n,{n}^{\prime}}$
(${n}^{\prime}\in\mathbb{N}_{+},n\in{1,...,{n}^{\prime}}$) satisfies the bound
condition. (Hinz & Van de Geer, 2019)

Here, for $h\in\mathrm{RL}(0,n^{\prime})$, we define
$\mathcal{H}({\mathbb{S}}_{h})={\bm{e}}^{0}=(1,0,0,\dots)^{\top}$. Let
$\Gamma$ be the set of all
$(\gamma_{n,n^{\prime}})_{n^{\prime}\in\mathbb{N}_{+},n\in\left\\{0,\ldots,n^{\prime}\right\\}}$
that satisfy the bound conditions. When $n>n^{\prime}$,
$\gamma_{n,n^{\prime}}$ is defined to be equal to
$\gamma_{n^{\prime},n^{\prime}}$ since
$\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}\left(n,n^{\prime}\right)\right\\}$
is equal to
$\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}\left(n^{\prime},n^{\prime}\right)\right\\}$
(Hinz & Van de Geer, 2019). By the definition $\gamma_{n,n^{\prime}}$
represents an upper bound of the activation histogram of regions which are
derived from $n$-dimension space partitioned by $n^{\prime}$ hyperplanes.
According to Proposition 1, this upper bound is also related to the upper
bound of space dimension. Therefore when $\gamma_{n,n^{\prime}}$ 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^{*}\in\mathbb{N}$, define a clipping function
$\mathrm{cl}_{i^{*}}(\cdot):{\mathbb{V}}\rightarrow{\mathbb{V}}$ as follows.
(Hinz & Van de Geer, 2019)

$\mathrm{cl}_{i^{*}}(\bm{v})_{i}=\left\\{\begin{array}[]{ll}v_{i}&\text{ for
}i<i^{*}\\\ \sum_{j=i^{*}}^{\infty}v_{j}&\text{ for }i=i^{*}\\\ 0&\text{ for
}i>i^{*}\end{array}\right.$ (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 $\gamma\in\Gamma$, define the matrix
${\bm{B}}^{(\gamma)}_{n^{\prime}}\in\mathbb{N}^{(n^{\prime}+1)\times(n^{\prime}+1)}$
as

$\left(B_{n^{\prime}}^{(\gamma)}\right)_{i,j}=\left(\mathrm{cl}_{j-1}\left(\gamma_{j-1,n^{\prime}}\right)\right)_{i-1},\quad
i,j\in\left\\{1,\ldots,n^{\prime}+1\right\\}.$

Then, the upper bound of linear regions number of an MLP in Eq.1 is

$\left\|{\bm{B}}_{n_{L-1}}^{(\gamma)}{\bm{M}}_{n_{L-2},n_{L-1}}\ldots{\bm{B}}_{n_{1}}^{(\gamma)}{\bm{M}}_{n_{0},n_{1}}{\bm{e}}^{n_{0}+1}\right\|_{1},$
(13)

where
${\bm{M}}_{n,n^{\prime}}\in\mathbb{R}^{(n^{\prime}+1)\times(n+1)},(M)_{i,j}=\delta_{i,\min\left(j,n^{\prime}+1\right)}$.
(Hinz & Van de Geer, 2019)

##  3 Main results

In this section, we introduce a better choice of $\gamma$ and compare it to
Serra et al. (2018). We also extend the computational framework to some widely
used network structures.

###  3.1 A tighter upper bound on the number of regions

Before giving our main results, we define a new function of histograms as
follows.

######  Definition 12.

Define a downward-move function
$\mathrm{dm}(\cdot):{\mathbb{V}}\rightarrow{\mathbb{V}}$ by
$\mathrm{dm}(\bm{v})_{i}=v_{i-1}$. When $i=0$, set
$\mathrm{dm}({\bm{v}})_{0}=0$.

We then prove the following two theorems used to compute $\gamma$.

######  Theorem 1.

If $\gamma_{n,n^{\prime\prime}}$ satisfies the bound condition in Definition
10 when $n^{\prime\prime}<n^{\prime}$, then

$\gamma_{n,n^{\prime}}=\gamma_{n-1,n^{\prime}-1}+\mathrm{dm}(\gamma_{n,n^{\prime}-1})$
(14)

also satisfies the bound condition.

######  Theorem 2.

Given any $h\in\mathrm{RL}(1,n)$, its activation histogram
$\mathcal{H}_{\mathrm{a}}({\mathbb{S}}_{h})$ denoted by ${\bm{v}}$ satisfies
$\sum^{n}_{i=t}v_{i}\leq 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 $\gamma_{1,n}$ whose form
is

$\gamma_{1,n}=(\underset{\left\lceil\frac{n}{2}\right\rceil-1}{\underbrace{0,\dots,0}},n\
\mathrm{mod}\ 2,\
\underset{\left\lfloor\frac{n}{2}\right\rfloor}{\underbrace{2,\dots,2}},1)^{\top}$
(15)

For example, $\gamma_{1,4}=(0,0,2,2,1)^{\top}$. Since there exists
$h\in\mathrm{RL}(1,n)$ such that
$\mathcal{H}_{\mathrm{a}}({\mathbb{S}}_{h})=\gamma_{1,n}$ (the proof can be
seen in the Appendix A.1.5), Eq.15 is the tightest upper bound, i.e.
$\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}\left(1,n\right)\right\\}$
satisfies Eq.15. With the fact that
$\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}\left(2,1\right)\right\\}=(1,1)^{\top}$,
any $\gamma_{n,n^{\prime}}$ can be computed.

###  3.2 Comparison with other bounds

We use $\gamma_{n,n^{\prime}}^{\text{ours}}$ and
$\gamma_{n,n^{\prime}}^{\text{serra}}$ to represent the ones proposed by us
and Serra et al. (2018). According to Hinz & Van de Geer (2019),

$(\gamma_{n,n^{\prime}}^{\text{serra}})_{i}=\left\\{\begin{matrix}0,&0\leq
i<n^{\prime}-n\\\ \binom{n^{\prime}}{i},&n^{\prime}-n\leq i\leq
n^{\prime}\end{matrix}\right.$

It is easy to verify that $\gamma_{n,n^{\prime}}^{\text{serra}}$ also
satisfies Eq.14. But the initial value of
$\gamma_{n,n^{\prime}}^{\text{serra}}$ is different from
$\gamma_{n,n^{\prime}}^{\text{ours}}$ and we have that
$\gamma^{\text{serra}}_{1,n}=(0,...,0,n,1)^{\top}$. Obviously,
$\gamma^{\text{ours}}_{1,n}\preceq\gamma^{\text{serra}}_{1,n}$. Since the two
operations, $+$ and $\rm{dm}(\cdot)$, keep the relation of $\preceq$, for any
$n,n^{\prime}\in\mathbb{N}_{+}$,
$\gamma_{n,n^{\prime}}^{\text{ours}}\preceq\gamma_{n,n^{\prime}}^{\text{serra}}$
(see an example in Appendix A.2.1). By the following theorem, the upper bound
computed by Eq.1 using $\gamma_{n,n^{\prime}}^{\text{ours}}$ is tighter than
$\gamma_{n,n^{\prime}}^{\text{serra}}$.

######  Theorem 3.

Given $\gamma^{(1)},\gamma^{(2)}\in\Gamma$, if for any
$n,n^{\prime}\in\mathbb{N}_{+}$ such that
$\gamma_{n,n^{\prime}}^{(1)}\preceq\gamma_{n,n^{\prime}}^{(2)}$, then upper
bound computed by Eq.13 using $\gamma^{(1)}$ is less than or equal to the one
using $\gamma^{(2)}$.

The proof of Theorem 3 is in Appendix A.1.6. Theorem 3 shows that if we can
get a ”smaller” $\gamma_{n,n^{\prime}}$ then the upper bound will be tighter.
And Theorem 1 implies that if we have a more accurate initial value, e.g.
”smaller” $\gamma_{2,n}$ or $\gamma_{3,n}$, the upper bound could be further
improved. Therefore Theorem 1 provides a potential approach to achieve even
tighter bound.

###  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 or unpooling layer can be written as a linear
transform., e.g. average-pooling and linear interpolation, it can be denoted
by ${\bm{y}}=A{\bm{x}}$. Suppose ${\bm{v}}$ is the space dimension of input
region and ${\bm{w}}$ is the histogram of the output regions. Then we have the
following proposition.

######  Proposition 4.

Suppose $\mathrm{rank}({\bm{A}})=k$, then
${\bm{w}}\preceq\mathrm{cl}_{k}({\bm{v}})$.

Since $\mathrm{cl}_{k}({\bm{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$-$\mathrm{rank}$ maxout
layer with $n$ input nodes and $n_{l}$ output nodes. Let $c=(k^{2}-k)n_{l}$,
then

${\bm{w}}\preceq\mathrm{cl}_{n_{l}}\left(\operatorname{diag}\left\\{|\gamma_{0,c}|_{1},\ldots,|\gamma_{n,c}|_{1}\right\\}{\bm{v}}\right)$
(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 ${\bm{v}}$ is the space dimension histogram of
the input regions of the $i^{\text{th}}$ layer and ${\bm{w}}$ the histogram of
the output regions of the $j^{\text{th}}$ layer. And we have that
${\bm{w}}\preceq\prod^{j}_{k=i}{\bm{A}}_{k}{\bm{v}}$. When the input of the
$i^{\text{th}}$ layer is concatenated to the $j^{\text{th}}$ layer, i.e. a
skip connection, then the computation of ${\bm{w}}$ will change and satisfies
that ${\bm{w}}\preceq\sum
v_{n}\left|{\bm{B}}{\bm{e}}^{n}\right|_{1}{\bm{e}}^{n}$ where
${\bm{B}}=\prod^{j}_{k=i}{\bm{A}}_{k}$. 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 $i^{\text{th}}$
layer to the output of the $j^{\text{th}}$ layer. ${\bm{v}},{\bm{w}},{\bm{B}}$
have the same meaning in Proposition 6. Then we have that ${\bm{w}}\preceq\sum
v_{n}\left|{\bm{B}}{\bm{e}}^{n}\right|_{1}{\bm{e}}^{n}$.

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.

##  4 Experiments

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 $n_{0}$.
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
$\gamma_{n,n^{\prime}}$, we only consider networks of relatively small sizes
(network input size is $24\times 24$ or $16\times 16$). In addition,
convolutional layers are regarded as fully-connected layers in the
computation.

(a) $n_{0}=10$

(b) $n_{0}=100$

(c) $n_{0}=10,n_{i}=10$

Figure 1: The comparison of our upper bound and Serra et 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_{0}$-$n_{i}$-$n_{i}$-$\cdots$-$n_{i}$-$1$ with $k$ hidden layers. (a) Setting is $n_{0}=10,n_{i}=6,8,10,15,20,25,k=1,2,...,10$. (b) Setting is $n_{0}=10,n_{i}=6,8,10,15,20,25,k=1,2,...,10$. (c) The setting is $n_{0}=n_{i}=10,k=10,20,...,100$. Table 1: The upper bound of AEs and U-nets. The channels setting means the architecture of networks. For instance, $4$-$8$-$16$-$32$ represents an 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.1). The input size in the first four experiments is $(24\times 24)$ while the last two is $(16\times 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
---|---|---|---|---
1 | 4-8-16-32 | $5.431\times 10^{2031}$ | $5.027\times 10^{1626}$ | $1.080\times 10^{405}$
2 | 4-16-64-128 | $1.712\times 10^{3111}$ | $3.333\times 10^{2956}$ | $3.517\times 10^{154}$
3 | 4-8-16 | $9.354\times 10^{1901}$ | $1.407\times 10^{1643}$ | $6.648\times 10^{258}$
4 | 4-16-64 | $2.211\times 10^{2591}$ | $3.328\times 10^{2450}$ | $6.644\times 10^{140}$
5 | 8-16-64 | $3.504\times 10^{1395}$ | $5.470\times 10^{1330}$ | $6.406\times 10^{64}$
6 | 8-32-128 | $1.268\times 10^{1642}$ | $1.230\times 10^{1642}$ | $1.031$
Table 2: The upper bound of a 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). ”p16” means that there is a pooling layer before the convolutional layer with 16 channels. And ”r16” represents that a residual structure is added in the convolutional layer with $16$ channels. The last three columns in this table is similar to Table 1. In this part, the input size in all the experiments is $(24\times 24)$. No. | Channels setting | w/ res-structure | w/o res-structure | ratio
---|---|---|---|---
1 | 4-p16-p16-r16-r16-r16 | $7.313\times 10^{1930}$ | $3.720\times 10^{1930}$ | $1.966$
2 | 4-p4-4-r4-r4-r4 | $5.052\times 10^{1542}$ | $3.393\times 10^{1542}$ | $1.489$
3 | 4-p16-p16-r16-16-16 | $5.232\times 10^{1930}$ | $3.720\times 10^{1930}$ | $1.406$
4 | 4-p16-p16-r16-r16-r16-r16-r16 | $3.012\times 10^{2277}$ | $5.882\times 10^{2276}$ | $5.121$
5 | 4-p16-p32-r32-r32-r32 | $7.180\times 10^{2623}$ | $7.166\times 10^{2623}$ | $1.002$

##  5 Discussion

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
$n_{i}$ increases from $0.6n_{0}$ to $1.5n_{0}$, the ratio curve of two bounds
moves upward. However, when $n_{i}$ increases to $2n_{0}$, the curve moves
downward. And when $n_{i}$ increases further and is much larger than $n_{0}$,
the two bounds are the same. This trend is related to the extent of similarity
in ${\bm{B}}^{(\text{ours})}_{n}$ and ${\bm{B}}^{(\text{serra})}_{n}$. When
$n_{i}<n_{0}$, ${\bm{B}}_{n_{i}}$ affects the upper bound most. And the
difference between ${\bm{B}}^{(\text{ours})}_{n_{i}}$ and
${\bm{B}}^{(\text{serra})}_{n_{i}}$ is more significant when $n_{i}$
decreases. When $n_{i}>n_{0}$, $({\bm{B}}_{n})_{:,n_{0}+1}$, the
$(n_{0}+1)^{\text{th}}$ column of $B_{n}$, is the main source of difference.
It is easy to find that the middle part of ${\bm{B}}^{(\text{ours})}_{n}$ and
${\bm{B}}^{(\text{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.

##  6 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
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.

## References

  * Arora et al. (2016) Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee.  Understanding deep neural networks with rectified linear units.  _arXiv preprint arXiv:1611.01491_ , 2016.
  * Cybenko (1989) George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _Advances in neural information processing systems_ , pp. 2672–2680, 2014.
  * Hanin (2019) Boris Hanin.  Universal function approximation by deep neural nets with bounded width and relu activations.  _Mathematics_ , 7(10):992, 2019.
  * Hanin & Rolnick (2019a) Boris Hanin and David Rolnick.  Complexity of linear regions in deep networks.  _arXiv preprint arXiv:1901.09021_ , 2019a.
  * Hanin & Rolnick (2019b) Boris Hanin and David Rolnick.  Deep relu networks have surprisingly few activation patterns.  In _Advances in Neural Information Processing Systems_ , pp. 359–368, 2019b.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hinton et al. (2012) 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 in speech recognition: The shared views of four research groups.  _IEEE Signal processing magazine_ , 29(6):82–97, 2012.
  * Hinz & Van de Geer (2019) Peter Hinz and Sara Van de Geer.  A framework for the construction of upper bounds on the number of affine linear regions of relu feed-forward neural networks.  _IEEE Transactions on Information Theory_ , 65(11):7304–7324, 2019.
  * Hornik et al. (1989) Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Huang et al. (2017) Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger.  Densely connected convolutional networks.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , July 2017.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pp. 1097–1105, 2012.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  _nature_ , 521(7553):436–444, 2015.
  * Mhaskar & Poggio (2016) Hrushikesh N Mhaskar and Tomaso Poggio.  Deep vs. shallow networks: An approximation theory perspective.  _Analysis and Applications_ , 14(06):829–848, 2016.
  * Montúfar (2017) Guido Montúfar.  Notes on the number of linear regions of deep neural networks.  _Sampling Theory Appl., Tallinn, Estonia, Tech. Rep_ , 2017.
  * Montufar et al. (2014) 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.
  * Pascanu et al. (2013) Razvan Pascanu, Guido Montufar, and Yoshua Bengio.  On the number of response regions of deep feed forward networks with piece-wise linear activations.  _arXiv preprint arXiv:1312.6098_ , 2013.
  * Raghu et al. (2017) 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 70_ , pp. 2847–2854. JMLR. org, 2017.
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image computing and computer-assisted intervention_ , pp. 234–241. Springer, 2015.
  * Serra & Ramalingam (2018) Thiago Serra and Srikumar Ramalingam.  Empirical bounds on linear regions of deep rectifier networks.  _arXiv preprint arXiv:1810.03370_ , 2018.
  * Serra et al. (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.
  * Yarotsky (2017) Dmitry Yarotsky.  Error bounds for approximations with deep relu networks.  _Neural Networks_ , 94:103–114, 2017.

##  Appendix A Appendix

###  A.1 Proofs

####  A.1.1 The proof of Proposition 1

###### Proof.

By Definition 6, suppose
$\\{{\bm{v}}^{(1)},{\bm{v}}^{(2)},\dots,{\bm{v}}^{(k)}\\}$ and ${\bm{c}}$ can
be used to represent any ${\bm{x}}\in{\mathbb{D}}$ and $\\{a_{i}\neq 0\\}$
satisfies that $a_{i}\\{{\bm{v}}^{(i)}+{\bm{c}}\in{\mathbb{D}}$. Let
${\mathbb{D}}^{\prime}={\mathbb{D}}-{\bm{c}}$, then ${\mathbb{D}}^{\prime}$ is
a translation of ${\mathbb{D}}$. Since ${\mathbb{D}}$ is convex,
${\mathbb{D}}^{\prime}$ and $f({\mathbb{D}}^{\prime})$ is also convex. Because
$f({\mathbb{D}})=f({\mathbb{D}}^{\prime}+{\bm{c}})={\bm{A}}{\mathbb{D}}^{\prime}+{\bm{A}}{\bm{c}}+{\bm{b}}$,
then
$\mathrm{Sd}(f({\mathbb{D}}))=\mathrm{Sd}({\bm{A}}{\mathbb{D}}^{\prime})$.
Suppose that
${\mathbb{D}}^{\prime\prime}={\bm{A}}({\mathbb{D}}^{\prime})=\\{{\bm{A}}{\bm{x}}|{\bm{x}}\in
R^{\prime}\\}$. For any ${\bm{y}}\in{\mathbb{D}}^{\prime\prime}$, there exists
${\bm{x}}\in{\mathbb{D}}^{\prime}$, s.t. ${\bm{y}}={\bm{A}}{\bm{x}}$. Denote
${\bm{A}}{\bm{v}}^{(i)}$ by ${\bm{w}}^{(i)}$, then ${\bm{y}}$ can be
represented by $\\{{\bm{w}}^{(1)},{\bm{w}}^{(2)},\dots,{\bm{w}}^{(k)}\\}$ and
$a_{i}{\bm{w}}^{(i)}\in{\mathbb{D}}^{\prime\prime}$. From
$\\{{\bm{w}}^{(1)},{\bm{w}}^{(2)},\dots,{\bm{w}}^{(k)}\\}$ choose a set of
vectors which are linear independent and can linearly represent
$\\{{\bm{w}}^{(1)},{\bm{w}}^{(2)},\dots,{\bm{w}}^{(k)}\\}$. For convenience,
suppose they are $\\{{\bm{w}}^{(1)},{\bm{w}}^{(2)},\dots,{\bm{w}}^{(t)}\\}$,
$t\leq k$. Therefore any ${\bm{y}}\in{\mathbb{D}}^{\prime\prime}$ can be
represented by $\\{{\bm{w}}^{(1)},{\bm{w}}^{(2)},\dots,{\bm{w}}^{(t)}\\}$.
Thus,
$\mathrm{Sd}({\mathbb{D}}^{\prime\prime})=\mathrm{Sd}(f({\mathbb{D}}))=t$ and
we have that

$\displaystyle t$ $\displaystyle=\mathrm{rank}(\left[{\bm{w}}^{(1)}\ \dots\
{\bm{w}}^{(t)}\right])$ $\displaystyle=\mathrm{rank}(\left[{\bm{w}}^{(1)}\
\dots\ {\bm{w}}^{(k)}\right])$
$\displaystyle=\mathrm{rank}({\bm{A}}\left[{\bm{v}}^{(1)}\ \dots\
{\bm{v}}^{(k)}\right])$
$\displaystyle\leq\min\\{\mathrm{rank}({\bm{A}}),\mathrm{rank}(\left[{\bm{v}}^{(1)}\
\dots\ {\bm{v}}^{(k)}\right])\\}$
$\displaystyle=\min\\{\mathrm{rank}({\bm{A}}),k\\}.$

The last equality is derived from that
$\\{{\bm{v}}^{(1)},{\bm{v}}^{(2)},\dots,{\bm{v}}^{(k)}\\}$ are $k$ linear
independent vectors. ∎

####  A.1.2 The proof of Proposition 2

###### Proof.

For any ${\bm{s}}\in{\mathbb{S}}({\bm{h}})$, suppose
${\mathbb{D}}({\bm{s}})=\\{{\bm{x}}|\bm{S}_{{\bm{h}}}({\bm{x}})={\bm{s}}\\}$.
As long as
$\mathrm{Sd}\left({\bm{h}}\left({\mathbb{D}}\left({\bm{s}}\right)\right)\right)\leq\min\\{n_{0},\left|{\bm{s}}_{h_{1}}\right|_{1},\left|{\bm{s}}_{h_{2}}\right|_{1},...,\left|\bm{s}_{h_{L-1}}\right|_{1}\\}$
is established, the proposition can be proved. Apparently,
$\mathrm{Sd}({\mathbb{D}}({\bm{s}}))=n_{0}$. Through the analysis in Section
2, ${\bm{h}}(\cdot)$ in ${\mathbb{D}}({\bm{s}})$ is an affine transform. For
any ${\bm{x}}^{(1)},{\bm{x}}^{(2)}\in{\mathbb{D}}({\bm{s}})$,
${\bm{W}}^{(i)}({\bm{x}}^{(1)})={\bm{W}}^{(i)}({\bm{x}}^{(2)}),{\bm{b}}^{(i)}({\bm{x}}^{(1)})={\bm{b}}^{(i)}({\bm{x}}^{(2)})$.
Therefore we use ${\bm{x}}^{(0)}\in{{\mathbb{D}}({\bm{s}})}$ to represent
them. Then ${\bm{h}}(\cdot)$ in ${\mathbb{D}}({\bm{s}})$ can be written as

$\displaystyle{\bm{h}}({\bm{x}})$
$\displaystyle={\bm{W}}^{(L-1)}({\bm{x}}^{(0)})(\dots\bm{W}^{(1)}({\bm{x}}^{(0)}){\bm{x}}+{\bm{b}}^{(1)}({\bm{x}}^{(0)}))+{\bm{b}}^{(L-1)}({\bm{x}}^{(0)})$
$\displaystyle={\bm{W}}({\bm{x}}^{(0)}){\bm{x}}+{\bm{b}}({\bm{x}}^{(0)})$

By Proposition 1, we have

$\displaystyle\mathrm{Sd}\left({\bm{h}}\left({\mathbb{D}}\left({\bm{s}}\right)\right)\right)$
$\displaystyle\leq\min\left\\{\mathrm{rank}({\bm{W}}({\bm{x}}^{(0)})),n_{0}\right\\}$
$\displaystyle=\min\left\\{n_{0},\mathrm{rank}\left(\prod^{L-1}_{i=1}{\bm{W}}^{(i)}({\bm{x}}^{(0)})\right)\right\\}$
$\displaystyle\leq\min\left\\{n_{0},\min\left\\{\mathrm{rank}\left({\bm{W}}^{(1)}({\bm{x}}^{(0)})\right),\dots,\mathrm{rank}\left({\bm{W}}^{(L-1)}({\bm{x}}^{(0)})\right)\right\\}\right\\}$
$\displaystyle\leq\min\\{n_{0},\left|{\bm{s}}_{h_{1}}\right|_{1},\left|{\bm{s}}_{h_{2}}\right|_{1},...,\left|{\bm{s}}_{h_{L-1}}\right|_{1}\\}$

The last two inequality are derived from that

$\mathrm{rank}\left(\prod^{L-1}_{i=1}{\bm{W}}^{(i)}({\bm{x}}^{(0)})\right)\leq\min\\{\mathrm{rank}({\bm{W}}^{(1)}({\bm{x}}^{(0)})),...,{\bm{W}}^{(L-1)}({\bm{x}}^{(0)}))\\}$

and
$\mathrm{rank}({\bm{W}}^{(i)}({\bm{x}}^{(0)}))\leq\left|{\bm{s}}_{h_{i}}\right|_{1}$.
∎

####  A.1.3 The proof of Theorem 1

###### Proof.

Obviously, $\gamma_{n,n^{\prime}}$ satisfies the second condition. As for the
first condition, consider that hyperplanes
$\\{L_{1},L_{2},...,L_{n^{\prime}}\\}$ divide $\mathbb{R}^{n}$. These
hyperlanes correspond to one $h\in\mathrm{RL}(n,n^{\prime})$ and its
activation histogram is denoted by ${\bm{v}}_{1}$. Here, we assume that
$L_{1},L_{2},\dots,L_{n^{\prime}}$ are not parallel to each other since in
parallel case it is easy to imagine and verify that there exists a
$h^{\prime}\in\mathrm{RL}(n,n^{\prime})$ which satisfies
$\mathcal{H}_{\mathrm{a}}({\mathbb{S}}_{h})\preceq\mathcal{H}_{\mathrm{a}}({\mathbb{S}}_{h^{\prime}})$.
Suppose that hyperplanes $\\{L_{1},L_{2},\dots,L_{n^{\prime}-1}\\}$ divide
$\mathbb{R}^{n}$ into $t$ regions $\\{R_{1},R_{2},...,R_{t}\\}$ and their
activation histogram is denoted by ${\bm{v}}_{2}$. Assume that
$L_{n^{\prime}}$ crosses $\\{R_{1},R_{2},...,R_{p}\\},p\leq t$ and divides
them into $2p$ regions. Let ${\bm{v}}_{3}$ denote the activation histogram of
$\\{R_{1},R_{2},\ldots,R_{p}\\}$. $p$ regions of them are active by
$L_{n^{\prime}}$ while other $p$ regions are not. Part of
$\\{R_{p+1},R_{p+2},...,R_{t}\\}$ are active by $L_{n^{\prime}}$ while the
rest regions are not. Their activation histogram are denoted as ${\bm{v}}_{4}$
and ${\bm{v}}_{5}$ respectively. Then we have the following equations:

$\displaystyle{\bm{v}}_{2}$
$\displaystyle={\bm{v}}_{3}+{\bm{v}}_{4}+{\bm{v}}_{5}$ (17)
$\displaystyle{\bm{v}}_{1}$
$\displaystyle={\bm{v}}_{3}+\mathrm{dm}({\bm{v}}_{3})+\mathrm{dm}({\bm{v}}_{4})+{\bm{v}}_{5}$
(18)

Let us only focus on $\\{R_{1}.R_{2},...,R_{p}\\}$. Suppose
$\\{L_{1},L_{2},...,L_{m}\\}(m\leq n^{\prime}-1)$ are borders of these
regions. $\\{L_{n^{\prime}}\cap L_{1},L_{n^{\prime}}\cap
L_{2},...,L_{n^{\prime}}\cap L_{m}\\}$ are hyperplanes in $L_{n^{\prime}}$,
and their active directions are projections of $\\{L_{1},L_{2},...,L_{m}\\}$
in $\mathbb{R}^{n}$. So the activation histogram of $\\{L_{n^{\prime}}\cap
L_{1},L_{n^{\prime}}\cap L_{2},...,L_{n^{\prime}}\cap L_{m}\\}$ in
$L_{n^{\prime}}$ which is denoted by $\bm{v}_{6}$ is equal to ${\bm{v}}_{3}$.
By the assumption that when $n^{\prime\prime}<n^{\prime}$,
$\gamma_{n,n^{\prime\prime}}$ satisfies the bound condition, we have

${\bm{v}}_{3}={\bm{v}}_{6}\preceq\gamma_{n-1,m}\preceq\gamma_{n-1,n^{\prime}-1}.$
(19)

By Eq.17, Eq.18 and Eq.19, ${\bm{v}}_{1}$ satisfies

$\displaystyle{\bm{v}}_{1}$
$\displaystyle\preceq\gamma_{n-1,n^{\prime}-1}+\mathrm{dm}({\bm{v}}_{3}+{\bm{v}}_{4}+{\bm{v}}_{5})$
(20) $\displaystyle=\gamma_{n-1,n^{\prime}-1}+\mathrm{dm}({\bm{v}}_{2})$
$\displaystyle\preceq\gamma_{n-1,n^{\prime}-1}+\mathrm{dm}(\gamma_{n,n^{\prime}-1})$

Because of the arbitrariness of ${\bm{v}}_{1}$, we can get
$\gamma_{n,n^{\prime}}=\gamma_{n-1,n^{\prime}-1}+\mathrm{dm}(\gamma_{n,n^{\prime}-1})$
which satisfies the first condition. ∎

####  A.1.4 The proof of Theorem 2

###### 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\in\mathbb{R}$, its activation number is at most $n$. Therefore if
$t<\lceil\frac{n}{2}\rceil$, then $\sum^{n}_{i=t}v_{i}\leq n+1\leq 2(n-t)+1$.
If $t\geq\lceil\frac{n}{2}\rceil$, the activation pattern of $n+1$ regions in
$\mathbb{R}$ is denoted by
$\\{{\bm{s}}_{1},{\bm{s}}_{2},\dots,{\bm{s}}_{n+1}\\}$ (see Figure 2(a)). No
matter how the activation directions of $n$ points are, we have
$\lvert{\bm{s}}_{1}\rvert+\lvert{\bm{s}}_{n+1}\rvert=n$ since $|{\bm{s}}_{1}|$
is equal to the number of left activation directions and $|{\bm{s}}_{n+1}|$ is
equal to the number of right activation direction. Another obvious conclusion
is that $\lvert{\bm{s}}_{i}\rvert-\lvert{\bm{s}}_{i+1}\rvert=\pm 1$ as the
activation patterns of neighboring regions only differ at the $i^{\text{th}}$
point. Without loss of generality, let
$\lvert{\bm{s}}_{1}\rvert\leq\lceil\frac{n}{2}\rceil$. 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 $a^{th}$ and $b^{th}$ region. Apparently, the number of regions among
$a^{th}$ and $b^{th}$ region is $2(n-t)+1$. So $\sum^{n}_{i=t}v_{i}\leq
2(n-t)+1$. ∎

(a) Number axis

(b) Activation number of each region

Figure 2: (a) The number axis is partitioned into $n+1$ parts. ${\bm{s}}_{i}$
represents the $i^{\text{th}}$ region. (b). An example of a partition and the
activation number of each region. The abscissa axis corresponds to the
position and the vertical axis represents the number of activation

####  A.1.5 The proof of Eq.15

###### Proof.

Suppose the $n$ points of $h$ in the number axis are $p_{1},p_{2},...,p_{n}$.
Let the direction sof $p_{1},...,p_{\lfloor\frac{n}{2}\rfloor}$are right and
other points left. It is easy to verify that
$\mathcal{H}_{\text{a}}({\mathbb{S}}_{h})=\gamma_{1,n}$ where $\gamma_{1,n}$
is defined by

$\gamma_{1,n}=\underbrace{(0,\dots,0}_{\left\lceil\frac{n}{2}\right\rceil-1},n\bmod
2,\underbrace{2,\dots,2}_{\left\lfloor\frac{n}{2}\right\rfloor},1)^{\top}$

Then
$\gamma_{1,n}\preceq\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}(1,n)\right\\}$.
Since
$\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}(1,n)\right\\}\preceq\gamma_{1,n}$,
$\gamma_{1,n}=\max\left\\{\mathcal{H}_{\mathrm{a}}\left({\mathbb{S}}_{h}\right)|h\in\operatorname{RL}(1,n)\right\\}$.
∎

####  A.1.6 The proof of Theorem 3

###### Proof.

Different ${\bm{B}}_{n^{\prime}}^{\gamma}$ can be derived from different
$\gamma_{n,n^{\prime}}$. Since the clipping function keep the order relation
$\preceq$, every column of ${\bm{B}}^{\gamma^{(1)}}_{n^{\prime}}$ and
$B^{\gamma^{(2)}}_{n^{\prime}}$in the same position satisfy that

$\left({\bm{B}}^{\gamma^{(1)}}_{n^{\prime}}\right)_{:,j}\preceq\left({\bm{B}}^{\gamma^{(2)}}_{n^{\prime}}\right)_{:,j}$

Another fact is that when ${\bm{v}}\preceq{\bm{w}}$, then
$\left|{\bm{v}}\right|_{1}\leq\left|{\bm{w}}\right|_{1}$. Here we prove that
if ${\bm{v}}\preceq{\bm{w}}$, then

${\bm{M}}_{n_{i},n_{i+1}}{\bm{v}}\preceq{\bm{M}}_{n_{i},n_{i+1}}{\bm{w}}$ (21)

and

${\bm{B}}^{\gamma^{(1)}}_{n_{i}}{\bm{v}}\preceq{\bm{B}}^{\gamma^{(2)}}_{n_{i}}{\bm{w}}$
(22)

Then the theorem can derived easily from Eq.21 and Eq.22.

Because ${\bm{M}}_{n_{i},n_{i+1}}\bm{v}=\mathrm{cl}_{n_{i+1}}(\bm{v})$, Eq.21
is easy to verified. For ${\bm{B}}^{\gamma^{(k)}}_{n_{i}},k=1,2$, we have that
$\left({\bm{B}}^{\gamma^{(k)}}_{n_{i}}\right)_{:,j_{1}}\preceq\left({\bm{B}}^{\gamma^{(k)}}_{n_{i}}\right)_{:,j_{2}}$
when $j_{1}\leq j_{2}$ because of the second condition in Definition 10 and
the property of the clipping function. For convenience,
$\left(B^{\gamma^{(k)}}_{n_{i}}\right)_{m,j}$ is denoted by $B^{(k)}_{m,j}$,
$k=1,2$. By Definition 5, we have that

$\displaystyle\sum^{\infty}_{m=M}\left({\bm{B}}^{(1)}{\bm{v}}\right)_{m}\leq\sum^{\infty}_{m=M}\left({\bm{B}}^{(2)}{\bm{w}}\right)_{m}$
$\displaystyle\Longleftrightarrow\sum^{\infty}_{m=M}\left(\sum^{\infty}_{j=0}B^{(1)}_{m,j}v_{j}\right)_{m}\leq\sum^{\infty}_{m=M}\left(\sum^{\infty}_{j=0}B^{(2)}_{m,j}w_{j}\right)_{m}$
$\displaystyle\Longleftrightarrow\sum^{\infty}_{j=0}\left(\sum^{\infty}_{m=M}B^{(1)}_{m,j}\right)v_{j}\leq\sum^{\infty}_{j=0}\left(\sum^{\infty}_{m=M}B^{(2)}_{m,j}\right)w_{j}$

Because ${\bm{B}}^{(1)}_{:,j}\preceq{\bm{B}}^{(2)}_{:,j}$, i.e. $\forall M\geq
0,\sum^{\infty}_{m=M}B^{(1)}_{m,j}\leq\sum^{\infty}_{m=M}B^{(2)}_{m,j}$. Let
$a_{j}=\sum^{\infty}_{m=M}B^{(1)}_{m,j},b_{j}=\sum^{\infty}_{m=M}B^{(2)}_{m,j}$,
then $a_{j}\leq b_{j}$. Because
${\bm{B}}^{(k)}_{:,j_{1}}\preceq{\bm{B}}^{(k)}_{:,j_{2}}$ when $j_{1}<j_{2}$,
then

$a_{0}\leq a_{1}\leq a_{2}\leq...$ (23)

and

$b_{0}\leq b_{1}\leq b_{2}\leq...$ (24)

By the notations, we have that

$\displaystyle\sum^{\infty}_{j=0}\left(\sum^{\infty}_{m=M}B^{(1)}_{m,j}\right)v_{j}\leq\sum^{\infty}_{j=0}\left(\sum^{\infty}_{m=M}B^{(2)}_{m,j}\right)w_{j}$
$\displaystyle\Longleftrightarrow$
$\displaystyle\sum^{\infty}_{j=0}a_{j}v_{j}\leq\sum^{\infty}_{j=0}b_{j}w_{j}$
$\displaystyle\Longleftrightarrow$
$\displaystyle\sum^{n_{i}}_{j=0}a_{j}v_{j}\leq\sum^{n_{i}}_{j=0}b_{j}w_{j}$

The last equivalence is derived from that $v_{j}=w_{j}=0$ when $j>n_{i}$.
Consider the left part of last inequality. Employing
${\bm{v}}\preceq{\bm{w}}\Leftrightarrow\sum_{j=J}^{n_{i}}v_{j}\leq\sum_{j=J}^{n_{i}}w_{j}$
and Eq.24, the following inequality can be derived

$\displaystyle\ \ \ \
\sum^{n_{i}}_{j=0}a_{j}v_{j}\leq\sum^{n_{i}}_{j=0}b_{j}v_{j}=b_{0}v_{0}+\sum^{n_{i}}_{j=1}b_{j}v_{j}\leq
b_{0}\left(\sum^{n_{i}}_{j=0}w_{j}-\sum^{n_{i}}_{j=1}v_{j}\right)+\sum^{n_{i}}_{j=1}b_{j}v_{j}$
$\displaystyle\leq
b_{0}w_{0}+b_{1}\left(\sum^{n_{i}}_{j=1}w_{j}-\sum^{n_{i}}_{j=1}v_{j}\right)+\sum^{n_{i}}_{j=1}b_{j}v_{j}=b_{0}w_{0}+b_{1}w_{1}+b_{1}\left(\sum^{n_{i}}_{j=2}w_{j}-\sum^{n_{i}}_{j=2}v_{j}\right)+\sum^{n_{i}}_{j=2}b_{j}v_{j}$
$\displaystyle\leq\sum^{1}_{j=0}b_{j}w_{j}+b_{2}\left(\sum^{n_{i}}_{j=2}w_{j}-\sum^{n_{i}}_{j=2}v_{j}\right)+\sum^{n_{i}}_{j=2}b_{j}v_{j}=\sum^{2}_{j=0}b_{j}w_{j}+b_{2}\left(\sum^{n_{i}}_{j=3}w_{j}-\sum^{n_{i}}_{j=3}v_{j}\right)+\sum^{n_{i}}_{j=3}b_{j}v_{j}$
$\displaystyle...$
$\displaystyle\leq\sum^{n_{i}-1}_{j=0}b_{j}w_{j}+b_{n_{i}}\left(w_{n_{i}}-v_{n_{i}}\right)+b_{n_{i}}v_{n_{i}}=\sum^{n_{i}}_{j=0}b_{j}w_{j}$

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 ${\mathbb{D}}$. Let ${\mathbb{D}}^{\prime}$ is the
corresponding output region, i.e.
${\mathbb{D}}^{\prime}={\bm{A}}({\mathbb{D}})$. By Proposition 1,
$\mathrm{Sd}({\mathbb{D}}^{\prime})\leq\min\\{\mathrm{Sd}({\mathbb{D}}),k\\}$.
Because

$\mathrm{Hist}(\\{\min\\{\mathrm{Sd}({\mathbb{D}}),k\\}|\ {\mathbb{D}}\text{
is any input region}\\})=\mathrm{cl}_{k}({\bm{v}})$

then ${\bm{w}}\preceq\mathrm{cl}_{k}({\bm{v}})$. Suppose
${\bm{v}}\in\mathbb{R}^{n+1}$, i,e, $v_{i}=0$ when $i>n$, it is easy to verify
that $\mathrm{cl}_{k}({\bm{v}})={\bm{M}}_{n,k}{\bm{v}}$, where

${\bm{M}}_{n,k}\in\mathbb{R}^{\left(k+1\right)\times(n+1)},(M)_{i,j}=\delta_{i,\min\left(j,n+1\right)}$

∎

####  A.1.8 The proof of Proposition 5

Before the proof, we show the following lemma.

######  Lemma 1.

Suppose $\gamma_{n,n^{\prime}}$ satisfies the recursion formula in Theorem 1
and the initial value satisfies that
$|\gamma_{n_{1},n_{2}}|_{1}=\sum_{s=0}^{n_{1}}\left(\begin{array}[]{c}n_{2}\\\
s\end{array}\right)$, then any $\gamma_{n,n^{\prime}}$ satisfies
$|\gamma_{n,n^{\prime}}|_{1}=\sum_{s=0}^{n}\left(\begin{array}[]{c}n^{\prime}\\\
s\end{array}\right)$.

###### Proof.

Since
$\gamma_{n,n^{\prime}}=\gamma_{n-1,n^{\prime}-1}+\mathrm{dm}(\gamma_{n,n^{\prime}-1})$
and $\mathrm{dm}(\cdot)$ does not change $|\cdot|_{1}$, we have
$|\gamma_{n,n^{\prime}}|_{1}=|\gamma_{n-1,n^{\prime}-1}|_{1}+|\gamma_{n,n^{\prime}-1}|_{1}$.
By the assumption, suppose that
$|\gamma_{n_{1},n_{2}}|_{1}=\sum_{s=0}^{n_{1}}\left(\begin{array}[]{c}n_{2}\\\
s\end{array}\right)$ is established when $n_{1}\leq n$ and $n_{2}<n^{\prime}$.
Then

$\displaystyle|\gamma_{n,n^{\prime}}|_{1}$
$\displaystyle=\sum_{s=0}^{n-1}\left(\begin{array}[]{c}n^{\prime}-1\\\
s\end{array}\right)+\sum_{s=0}^{n}\left(\begin{array}[]{c}n^{\prime}-1\\\
s\end{array}\right)$
$\displaystyle=\sum_{s=1}^{n}(C^{n^{\prime}-1}_{s}+C^{n^{\prime}-1}_{s-1})+C^{n^{\prime}-1}_{0}$
$\displaystyle=\sum_{s=1}^{n}C^{n^{\prime}}_{s}+C^{n^{\prime}}_{0}$
$\displaystyle=\sum_{s=0}^{n}\left(\begin{array}[]{c}n^{\prime}\\\
s\end{array}\right)$

Therefore any $\gamma_{n,n^{\prime}}$ satisfies the formula. ∎

It is easy to verify that
$|\gamma_{1,n}|_{1}=n+1=\sum^{1}_{s=0}\left(\begin{array}[]{c}n\\\
s\end{array}\right)$ and
$|\gamma_{2,1}|_{1}=2=\sum^{2}_{s=0}\left(\begin{array}[]{c}1\\\
s\end{array}\right)$. By Lemma 1, $\gamma_{n,n^{\prime}}$ proposed by us
satisfies that
$|\gamma_{n,n^{\prime}}|_{1}=\left(\begin{array}[]{c}n^{\prime}\\\
s\end{array}\right)$. 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 $n_{l}$ output nodes corresponds
to divide one region by $\dfrac{k(k-1)}{2}n_{l}$ hyperplanes. Suppose $R$ is
one input region with $\mathrm{Sd}(R)=n^{\prime}$ and partitioned into $p$
sub-regions $\\{r_{1},...,r_{p}\\}$. Since one $d$-dimension space is at most
partitioned into $\sum_{s=0}^{d}\left(\begin{array}[]{c}m\\\
s\end{array}\right)$ sub-regions by $m$ hyperplanes, then by Lemma 1

$p\leq\sum_{s=0}^{n^{\prime}}\left(\begin{array}[]{c}\frac{k(k-1)n_{l}}{2}\\\
s\end{array}\right)=|\gamma_{n^{\prime},c}|_{1}$

For any sub-region $p_{i}$, $\mathrm{Sd}(p_{i})=n^{\prime}$. Since $h$ is
equivalent to an affine transform in $p_{i}$ with matrix $A$ of rank $n_{A}$,
we have that $\mathrm{Sd}(h(p_{i}))\leq\min\\{n_{A},n^{\prime}\\}$ by
Proposition 1. Another fact is that $n_{A}\leq n_{l}$. Therefore
$\mathrm{Sd}(h(p_{i}))\leq\min\\{n_{l},n^{\prime}\\}$. That is to say, $R$
with $n^{\prime}$ space dimension is divided in to at most
$|\gamma_{n^{\prime},c}|_{1}$ sub-regions and the space dimension of each
output sub-region is no larger than $\min\\{n_{l},n^{\prime}\\}$. If the space
dimension histogram of input regions is $\bm{v}$ ($\in\mathbb{R}^{n}$) , then
it is easy to verify that after the partition by $h$, the histogram of sub-
regions $\bm{v}^{\prime}$ satisfies that
$\bm{v}^{\prime}\preceq\operatorname{diag}\left\\{|\gamma_{0,c}|_{1},\ldots,|\gamma_{n,c}|_{1}\right\\}{\bm{v}}$.
In addition, $h$ change their space dimension. Thus

${\bm{w}}\preceq\mathrm{cl}_{n_{l}}({\bm{v}}^{\prime})\preceq\mathrm{cl}_{n_{l}}(\operatorname{diag}\left\\{|\gamma_{0,c}|_{1},\dots,|\gamma_{n,c}|_{1}\right\\}{\bm{v}}).$

Let
${\bm{C}}=\operatorname{diag}\left\\{|\gamma_{0,c}|_{1},\dots,|\gamma_{n,c}|_{1}\right\\}$,
then
$\mathrm{cl}_{n_{l}}(\operatorname{diag}\left\\{|\gamma_{0,c}|_{1},\ldots,|\gamma_{n,c}|_{1}\right\\}{\bm{v}})={\bm{M}}_{n,n_{l}}{\bm{C}}{\bm{v}}$.
∎

####  A.1.9 The proof of Proposition 6

###### Proof.

When the skip connection is not added, $\bm{w}\preceq{\bm{B}}\bm{v}$. Let
$\bm{v}=\bm{e}^{n}$, i.e. the the number of the input regions is one. Suppose
the region is $R\subseteq\mathbb{R}^{m}$ and $R$ is divided into $p$ sub-
regions. Apparently $p\leq|{\bm{B}}\bm{e}^{n}|$ and
$\mathrm{Sd}(R)=\mathrm{Sd}(r)=n\leq m$ where $r$ is one of the sub-regions.
Suppose the part of network which is from the $i^{\text{th}}$ layer to the
$j^{\text{th}}$ layer is equivalent to an affine transform with matrix
${\bm{C}}$. Let $r^{\prime}={\bm{C}}(r)$. When the skip connection is added,
the output of $r$ is $\begin{bmatrix}{\bm{C}}\\\ {\bm{I}}\end{bmatrix}(r)$
denoted by $r^{\prime\prime}$. Since
$\mathrm{rank}\left(\begin{bmatrix}{\bm{C}}\\\
{\bm{I}}\end{bmatrix}\right)=m$,
$\mathrm{Sd}(r^{\prime\prime})\leq\min\\{m,\mathrm{Sd}(r)\\}=n$. This implies
that the space dimension of $r^{\prime}$ may be enhanced to $n$. Therefore the
space dimension histogram of $p$ sub-regions $\bm{w}_{R}$ satisfies that

$\bm{w}_{R}\preceq|B\bm{e}^{n}|_{1}\bm{e}^{n}.$ (25)

For any input region with $n$ space dimension, Eq.25 is always established.
Thus, when the space dimension histogram of input regions is $\bm{v}$ the
histogram of output regions satisfies

$\bm{w}\preceq\sum_{R}\bm{w}_{R}\preceq\sum_{R}|{\bm{B}}\bm{e}^{\mathrm{Sd}(R)}|_{1}\bm{e}^{\mathrm{Sd}(R)}=\sum_{n}v_{n}\left|{\bm{B}}\bm{e}^{n}\right|_{1}\bm{e}^{n}.$
(26)

Let
${\bm{C}}=\operatorname{diag}\\{|{\bm{B}}\bm{e}^{0}|_{1},|{\bm{B}}\bm{e}^{2}|_{1},...,|{\bm{B}}\bm{e}^{n}|_{1},...\\}$,
then
$\sum_{n}v_{n}\left|{\bm{B}}\bm{e}^{n}\right|_{1}\bm{e}^{n}={\bm{C}}\bm{v}$. ∎

####  A.1.10 The proof of Proposition 7

###### Proof.

Any residual structure can be regarded as the composition of one skip
connection and an linear transform. For any input region
$r\subseteq\mathbb{R}^{m}$ partitioned by the network, the residual structure
part has the following form.

${\bm{y}}=\mathrm{Res}({\bm{x}})=\begin{bmatrix}{\bm{I}}&{\bm{I}}\end{bmatrix}\begin{bmatrix}{\bm{C}}\\\
{\bm{I}}\end{bmatrix}{\bm{x}},{\bm{x}}\in r$

By Proposition 6, the space dimension histogram of output regions
$\begin{bmatrix}{\bm{C}}\\\ {\bm{I}}\end{bmatrix}(r)$ denoted by ${\bm{w}}$
satisfies that

${\bm{w}}\preceq\sum v_{n}\left|{\bm{B}}\bm{e}^{n}\right|_{1}\bm{e}^{n}$

Since
$\mathrm{rank}(\begin{bmatrix}{\bm{I}}&{\bm{I}}\end{bmatrix})=m\geq\mathrm{Sd}(r)$,
according to Proposition 1 the linear transform will not change the histogram.
∎

####  A.1.11 Proposition 8 and its proof

######  Proposition 8.

For an MLP, let $f_{m}$ represent the first $m$ layers $(1\leq m\leq l)$, i.e.
$f_{m}(\bm{x})$ is the output of the $m^{\text{th}}$ layer, and
$F_{l+1}({\bm{z}})=\sigma({\bm{W}}^{(l+1)}\bm{z}+{\bm{b}}^{(l+1)})$
representing the $(l+1)^{\text{th}}$ layer in the MLP. Consider another
network layer,

$G_{l+1}(\bm{z},\bm{y})=\sigma\left({\bm{W}}^{(l+1,\prime)}\begin{bmatrix}\bm{z}\\\
\bm{y}\end{bmatrix}+{\bm{b}}^{(l+1,\prime)}\right)$

where
$\bm{z}=f_{l}(\bm{x})\in\mathbb{R}^{n_{l}},\bm{y}=f_{m}(\bm{x})\in\mathbb{R}^{n_{m}},1<m<l$.
Then, given a specific $F_{l+1}$, there exists a $G_{l+1}$ such that the the
total number of regions partitioned by $G_{l+1}$ is no more less than that by
$F_{l+1}$.

###### Proof.

For a connected set $R\subseteq$ input space, $f_{l}(R)$ and $f_{m}(R)$ are
still connected sets. For each hyperplane $H_{i}$ represented by
$\sum_{j=1}^{n_{l}}a_{i,j}z_{j}+b_{i}=0$ in $F_{l+1}$, design corresponding
hyperplane $H_{i}^{\prime}$,
$\sum_{j=1}^{n_{l}}a_{i,j}z_{j}+\sum_{j=1}^{n_{m}}c_{i,j}y_{j}+b_{i}=0$, in
$G_{l+1}$, where $c_{i,j}=0$. Suppose $H_{i}$ crosses
$\\{R_{1},R_{2},...,R_{k_{i}}\\}$ and take $k_{i}$ intersections
$\\{\bm{p}_{1},\bm{p}_{2},...,\bm{p}_{k_{i}}\\}$ where $\bm{p}_{j}$ is a
interior point in $R_{j}(1\leq j\leq k_{i})$. Let
$f_{l}(\bm{x}_{j})=\bm{p}_{j}$, then
$(f_{l}(\bm{x}_{j}),(f_{m}(\bm{x}_{j}))\in H_{i}^{\prime}$ and it is also a
interior point in $R_{j}^{\prime}$ which is the same as $R_{j}$ when cutting
last $n_{m}$ dimensions. So $H_{i}^{\prime}$ crosses at least $k_{i}$ regions
which indicates the total number of regions partitioned by $G_{l+1}$ is no
more less than that by $F_{l+1}$. ∎

####  A.1.12 Proposition 9 and its proof

######  Proposition 9.

For a three-layer MLP which has two hidden layers, i.e.

$f(x)=\bm{W}^{(3)}\sigma(\bm{W}^{(2)}\sigma(\bm{W}^{(1)}{\bm{x}}+\bm{b}_{1})+\bm{b}^{(2)})+\bm{b}^{(3)},$
(27)

suppose that $n_{0}=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 $(n_{1}+1)(n_{2}+1)$.
Specifically, without the special structure (just like an MLP) and assume that
$n_{1}=3$, there exists some parameters in the first layer such that the
practical maximum number is no more than $(n_{1}+1)(n_{2}+1)-n_{2}$.

###### Proof.

Denote $h_{1}({\bm{x}})=\sigma(\bm{W}^{(1)}{\bm{x}}+{\bm{b}}^{(1)})$. The
first layer divides input space into $n_{1}+1$ regions
$\\{r_{1},r_{2},...r_{n_{1}+1}\\}$, then $h_{1}(r_{i})\subseteq\mathbb{R}$.
Because of the skip connection, the dimension of hyperplanes in the second
layer is $n_{1}$. It is apparent that for any $n_{1}+1$ points there always
exits a hyperplane containing them. Thus, for any interior point $x_{i}\in
r_{i}(1\leq i\leq n_{1}+1)$, there exists a hyperplane contaning them and
therefore crossing $n_{1}+1$ regions. We have $n_{2}$ hyperplanes in the
second layer, which shows the number of linear regions is
$(n_{1}+1)(n_{2}+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

$\mathbb{W}_{1}=\begin{bmatrix}\frac{1}{t_{1}}\\\ -\frac{1}{t_{2}}\\\
\frac{1}{t_{3}}\end{bmatrix},\mathbb{b}_{1}=\begin{bmatrix}-1\\\ 1\\\
-1\end{bmatrix}$ (28)

Then we get four output regions in $\mathbb{R}^{3}$ shown in Figure 3. We can
see that $R_{1},R_{2}$ and $R_{3}$ are on the same plane, i.e. the x-y plane.
For any interior points ${\bm{p}}_{i}\in R_{i},i=1,2,3$, the only hyperplane
crossing them is x-y plane which is not able to divide $R_{1},R_{2}$ and
$R_{3}$. So the practical maximum number is no more than
$(n_{1}+1)(n_{2}+1)-n_{2}$. ∎

Figure 3: The four output regions in $\mathbb{R}^{3}$

###  A.2 Examples

####  A.2.1 An example of $\gamma^{\mathrm{new}}_{n,n^{\prime}}$ and
$\gamma^{\mathrm{serra}}_{n,n^{\prime}}$

Here $n^{\prime}=6$. Then $\gamma^{\text{ours}}_{n,n^{\prime}}$ and
$\gamma^{\text{serra}}_{n,n^{\prime}}$ are shown as follows.

$\underset{\gamma_{\cdot,6}^{\text{ours}}}{\left[\begin{matrix}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\end{matrix}\right]}\quad\quad\quad\underset{\gamma_{\cdot,6}^{\text{serra}}}{\left[\begin{matrix}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\end{matrix}\right]}$ (29)

####  A.2.2 An example of upper bound computation for U-net

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 fully-connected layers denoted by
${\bm{C}}_{i}$. Suppose pooling layers are average pooling layers and
unpooling ones are filling-zero ones. They are denoted by ${\bm{P}}_{i}$ and
${\bm{U}}_{i}$. Here, the subscript $i$ means the order in the network. Then
according to Proposition 3 and Proposition 4 we have

$\displaystyle{\bm{C}}_{1}={\bm{B}}_{2304},{\bm{C}}_{2}={\bm{B}}_{1152},{\bm{C}}_{3}={\bm{B}}_{576},{\bm{C}}_{4}={\bm{B}}_{288},$
$\displaystyle{\bm{C}}_{5}={\bm{B}}_{144},{\bm{C}}_{6}={\bm{B}}_{288},{\bm{C}}_{7}=B_{576},{\bm{C}}_{8}={\bm{B}}_{2304}$
$\displaystyle{\bm{P}}_{1}={\bm{M}}_{2304,576},{\bm{P}}_{2}={\bm{M}}_{1152,288},{\bm{P}}_{3}={\bm{M}}_{576,144},$
$\displaystyle{\bm{U}}_{1}={\bm{M}}_{144,144}={\bm{I}}_{144},{\bm{U}}_{2}={\bm{M}}_{288,288}={\bm{I}}_{288},{\bm{U}}_{3}={\bm{M}}_{576,576}={\bm{I}}_{576}.$

where ${\bm{B}}$, ${\bm{M}}$ are defined by Proposition 3. By Proposition 6,
the upper bound $N$ is computed as follows.

$\displaystyle{\bm{S}}_{3}^{\prime}$
$\displaystyle={\bm{U}}_{1}{\bm{C}}_{5}{\bm{M}}_{288,144}{\bm{C}}_{4}{\bm{M}}_{144,288}{\bm{P}}_{3}\in\mathbb{R}^{144\times
576}$ $\displaystyle{\bm{S}}_{3}$
$\displaystyle=\operatorname{diag}\\{|{\bm{S}}_{3}^{\prime}\bm{e}^{0}|_{1},|{\bm{S}}_{3}^{\prime}\bm{e}^{2}|_{1},\dots,|{\bm{S}}_{3}^{\prime}\bm{e}^{576}|_{1},\\}\in\mathbb{R}^{576\times
576}$ $\displaystyle{\bm{S}}_{2}^{\prime}$
$\displaystyle={\bm{U}}_{2}{\bm{C}}_{6}{\bm{M}}_{576,288}{\bm{S}}_{3}{\bm{C}}_{3}{\bm{M}}_{288,576}{\bm{P}}_{2}\in\mathbb{R}^{288,1152}$
$\displaystyle{\bm{S}}_{2}$
$\displaystyle=\operatorname{diag}\\{|{\bm{S}}_{2}^{\prime}\bm{e}^{0}|_{1},|{\bm{S}}_{2}^{\prime}\bm{e}^{2}|_{1},\dots,|{\bm{S}}_{2}^{\prime}\bm{e}^{1152}|_{1},\\}\in\mathbb{R}^{1152\times
1152}$ $\displaystyle{\bm{S}}_{1}^{\prime}$
$\displaystyle={\bm{U}}_{1}{\bm{C}}_{7}{\bm{M}}_{1152,576}{\bm{S}}_{2}{\bm{C}}_{2}{\bm{M}}_{576,1152}{\bm{P}}_{1}\in\mathbb{R}^{576,2304}$
$\displaystyle{\bm{S}}_{1}$
$\displaystyle=\operatorname{diag}\\{|{\bm{S}}_{1}^{\prime}\bm{e}^{0}|_{1},|{\bm{S}}_{1}^{\prime}\bm{e}^{2}|_{1},\dots,|{\bm{S}}_{1}^{\prime}\bm{e}^{2304}|_{1},\\}\in\mathbb{R}^{1152\times
1152}$ $\displaystyle N$
$\displaystyle=|{\bm{C}}_{8}{\bm{S}}_{1}{\bm{C}}_{1}{\bm{M}}_{576,2304}\bm{e}^{576}|_{1}$

####  A.2.3 The comparison of $B^{\mathrm{ours}}_{n}$ and
$B^{\mathrm{serra}}_{n}$

Here we consider $n=6$. By Eq.29 and the definition of clipping function, we
have

$\underset{B_{6}^{\text{ours}}}{\left[\begin{matrix}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\end{matrix}\right]}\quad\quad\quad\underset{B_{6}^{\text{serra}}}{\left[\begin{matrix}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\end{matrix}\right]}$

####  A.2.4 An simple example of imperfect partition

In this part, we use a simple example (in Figure 4) to illustrate imperfect
partition. Consider a two-layer MLPs with $n_{0}=1,n_{1}=2$. The original
input space is $\mathbb{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 $\mathbb{R}^{2}$ 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.

(a) input regions

(b) output of the first layer

(c) hyperplanes in the second layer

Figure 4: (a) The input region $\mathbb{R}$ is divided into three parts in
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

###  A.3 Network architectures

####  A.3.1 Network architectures in Table 1

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\times 3)$ with $\text{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.

Figure 5: Network architecture with skip connections in No.1 of Table 1

####  A.3.2 Network architectures in Table 2

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.

Figure 6: Network architecture with residual structures in No.1 of Table 2