Universality of Deep Convolutional Neural Networks

Introduction and Main Results

Deep learning provides various models and algorithms to process data as efficiently as biological nervous systems or neuronal responses in the human brain . It is based on deep neural network architectures and those structures bring essential tools for obtaining data features and function representations in practical applications. A main concern about deep learning which has attracted much scientific attention and some criticism is its lack of theories supporting its practical efficiency caused by its network structures, though there have been some theoretical attempts from approximation theory viewpoints . In particular, for deep CNNs having convolutional structures without fully connected layers, it is unknown which kinds of functions can be approximated. This paper provides a rigorous mathematical theory to answer this question and to illustrate the role of convolutions.

The deep CNNs considered in this paper have two essential ingredients: a rectified linear unit (ReLU) defined as a univariate nonlinear function $\sigma$ given by

and a sequence of convolutional filter masks ${\bf w}=\{w^{(j)}\}_{j}$ inducing sparse convolutional structures. Here a filter mask $w=(w_{k})_{k=-\infty}^{\infty}$ means a sequence of filter coefficients. We use a fixed integer filter length $s\geq 2$ to control the sparsity, and assume that $w^{(j)}_{k}\not=0$ only for $0\leq k\leq s$. The convolution of such a filter mask $w$ with another sequence $v=(v_{0},\ldots,v_{D})$ is a sequence $w{*}v$ given by $\left(w{*}v\right)_{i}=\sum_{k=0}^{D}w_{i-k}v_{k}$. This leads to a $(D+s)\times D$ Toeplitz type convolutional matrix $T$ which has constant diagonals:

Sparse matrices of this form induce deep CNNs which are essentially different from the classical neural networks involving full connection matrices. Note that the number of rows of $T$ is $s$ greater than that of columns. This leads us to take a sequence of linearly increasing widths $\{d_{j}=d+js\}$ for the network, which enables the deep CNN to represent functions of richer structures.

where $T^{(j)}=\left(w^{(j)}_{i-k}\right)$ is a $d_{j}\times d_{j-1}$ convolutional matrix, $\sigma$ acts on vectors componentwise, and ${\bf b}$ is a sequence of bias vectors $b^{(j)}$.

The hypothesis space of a learning algorithm is the set of all possible functions that can be represented or produced by the algorithm. For the deep CNN of depth $J$ considered here, the hypothesis space is a set of functions defined by

while the widths of the deep CNN are bounded by $12Ld$ and the total number of free parameters by

We can even take $L=1$ and $\tau=1/2$ to get a bound for the relative error

achieved by a deep CNN of depth $\lceil 4\sqrt{d}\rceil$ and at most $75d$ free parameters, which decreases as the dimension $d$ increases. This interesting observation is new for deep CNNs, and does not exist in the literature of fully connected neural networks. It explains the strong approximation ability of deep CNNs.

A key contribution in our theory of deep CNNs is that an arbitrary pre-assigned sequence $W=(W_{k})_{-\infty}^{\infty}$ supported in $\{0,\ldots,{\mathcal{M}}\}$ can be factorized into convolutions of a mask sequence $\{w^{(j)}\}_{j=1}^{J}$. It is proved by the same argument as in for the case with the special restriction $W_{0}\not=0$. Convolutions are closely related to translation-invariance in speeches and images , and also in some learning algorithms .

Theorem C. Let $s\geq 2$ and $W=(W_{k})_{-\infty}^{\infty}$ be a sequence supported in $\{0,\ldots,{\mathcal{M}}\}$ with ${\mathcal{M}}\geq 0$. Then there exists a finite sequence of filter masks $\{w^{(j)}\}_{j=1}^{J}$ supported in $\{0,\ldots,s\}$ with $J<\frac{{\mathcal{M}}}{s-1}+1$ such that the convolutional factorization $W=w^{(J)}{*}\ldots{*}w^{(2)}{*}w^{(1)}$ holds true.

A multi-layer neural network is a sequence of function vectors $h^{(j)}(x)$ satisfying an iterative relation

Here $T^{(j)}$ is a full connection matrix without special structures. So a deep CNN is a special multi-layer neural network with sparse convolutional matrices. This sparsity gives difficulty in developing a mathematical theory for deep CNNs, since the techniques in the literature of fully connected shallow or multi-layer neural networks do not apply. Our novelty to overcome the difficulty is to factorize an arbitrary finitely supported sequence into convolutions of filter masks $\{w^{(j)}\}_{j=1}^{J}$ supported in $\{0,1,\ldots,s\}$. Our method can be applied to distributed learning algorithms .

Recently there have been quite a few papers on approximation and representation of functions by deep neural networks and benefit of depth, but all these results are for fully connected networks without pre-specified structures, not for deep CNNs. In particular, it was shown in that the rate of approximaton of some function classes by multi-layer fully connected neural networks may be achieved by networks with sparse connection matrices $T^{(j)}$, but the locations of the sparse connections are unknown. This sparsity of unknown pattern is totally different from that of deep CNNs, the latter enables computing methods like stochastic gradient descent to learn values of the free parameters efficiently.

For approximation in $C(\Omega)$ we can only consider those Sobolev spaces which can be embedded into the space of continuous functions, that is, those spaces with the regularity index $r>\frac{d}{2}$. To establish rates of approximation we require $r>\frac{d}{2}+2$ in Theorem B. In this case, the set $H^{r}(\Omega)$ is dense in $C(\Omega)$, so Theorem A follows from Theorem B by scaling.

with $\beta_{k}\in,\|\alpha_{k}\|_{1}=1,t_{k}\in,\beta_{0}=F(0),\alpha_{0}=\nabla F(0)$ and $|v|\leq 2v_{F,2}$ such that

Now we turn to the key step of constructing the filter mask sequence ${\bf w}$. Define a sequence $W$ supported in $\{0,\ldots,(m+1)d-1\}$ by stacking the vectors $\alpha_{0},\alpha_{1},\ldots,\alpha_{m}$ (with components reversed) by

We apply Theorem C to the sequence $W$ with support in $\{0,1,\ldots,(m+1)d\}$ and find a sequence of filter masks ${\bf w}=\{w^{(j)}\}_{j=1}^{\hat{J}}$ supported in $\{0,1,\ldots,s\}$ with $\hat{J}<\frac{(m+1)d}{s-1}+1$ such that $W=w^{(\hat{J})}{*}w^{(\hat{J}-1)}{*}\ldots{*}w^{(2)}{*}w^{(1)}.$ The choice of $m$ implies $\frac{(m+1)d}{s-1}\leq J$. So $\hat{J}\leq J$ and by taking $w^{(\hat{J}+1)}=\ldots=w^{(J)}$ to be the delta sequence, we have $W=w^{(J)}{*}w^{(J-1)}{*}\ldots{*}w^{(2)}{*}w^{(1)}.$ This tells us that

Then we construct ${\bf b}$. Denote $\|w\|_{1}=\sum_{k=-\infty}^{\infty}|w_{k}|$, $B^{(0)}=\max_{x\in\Omega}\max_{k=1,\ldots,d}|x_{k}|$ and $B^{(j)}=\|w^{(j)}\|_{1}\ldots\|w^{(1)}\|_{1}B^{(0)}$ for $j\geq 1$. Then we have

Take $b^{(1)}=-B^{(1)}{\bf 1}_{d_{1}}:=-B^{(1)}(1,\ldots,1)^{T}$, and

Thus, we can take $f^{{\bf w},{\bf b}}_{J}=F_{m}|_{\Omega}\in\hbox{span}\{h^{(J)}_{k}(x)\}_{k=1}^{d_{J}}={\mathcal{H}}^{{\bf w},{\bf b}}_{J}$ and know that the error $\|f-f^{{\bf w},{\bf b}}_{J}\|_{C(\Omega)}\leq\left\|F-F_{m}\right\|_{C(^{d})}$ can be bounded as

This proves Theorem B by taking $c=2c_{0}c^{\prime}$.

Convolutional factorizations have been considered in our recent work for sequences $W$ supported in $\{0,1,\ldots,S\}$ with $S\geq d$ under the special restrictions $W_{0}>0$ and $W_{S}\not=0$. Theorem C gives a more general result by improving the bound for $J$ in and removing the special restrictions on $W_{0}$ and $W_{S}$.

where $2K$ is the number of complex roots with multiplicity, and $M-2K$ is the number of real roots with multiplicity. By taking groups of up to $s/2$ quadratic factors (or $(s-1)/2$ quadratic factors with a linear factor) and $s$ linear factors in the above factorization, we get $\widetilde{W}(z)=\widetilde{w^{(J)}}(z)\ldots\widetilde{w^{(2)}}(z)\widetilde{w^{(1)}}(z)$, a factorization of $\widetilde{W}$ into polynomials of degree up to $s$, which yields a desired convolutional factorization $W=w^{(J)}{*}w^{(J-1)}{*}\ldots{*}w^{(2)}{*}w^{(1)}$ and proves Theorem C.

Acknowledgments

The author would like to thank Gilbert Strang and Steve Smale for their detailed suggestions and encouragement. The work described in this paper is supported partially by the Research Grants Council of Hong Kong [Project No CityU 11306617] and by National Nature Science Foundation of China [Grant No 11461161006].

References