A Mathematical Theory of Deep Convolutional Neural Networks for Feature Extraction

I Introduction

Acentral task in machine learning is feature extraction as, e.g., in the context of handwritten digit classification . The features to be extracted in this case correspond, for example, to the edges of the digits. The idea behind feature extraction is that feeding characteristic features of the signals—rather than the signals themselves—to a trainable classifier (such as, e.g., a support vector machine (SVM) ) improves classification performance. Specifically, non-linear feature extractors (obtained, e.g., through the use of a so-called kernel in the context of SVMs) can map input signal space dichotomies that are not linearly separable into linearly separable feature space dichotomies . Sticking to the example of handwritten digit classification, we would, moreover, want the feature extractor to be invariant to the digits’ spatial location within the image, which leads to the requirement of translation invariance. In addition, it is desirable that the feature extractor be robust with respect to (w.r.t.) handwriting styles. This can be accomplished by demanding limited sensitivity of the features to certain non-linear deformations of the signals to be classified.

Spectacular success in practical machine learning tasks has been reported for feature extractors generated by so-called deep convolutional neural networks (DCNNs). These networks are composed of multiple layers, each of which computes convolutional transforms, followed by non-linearities and poolingIn the literature “pooling” broadly refers to some form of combining “nearby” values of a signal (e.g., through averaging) or picking one representative value (e.g, through maximization or sub-sampling). operators. While DCNNs can be used to perform classification (or other machine learning tasks such as regression) directly , typically based on the output of the last network layer, they can also act as stand-alone feature extractors with the resulting features fed into a classifier such as a SVM. The present paper pertains to the latter philosophy.

The mathematical analysis of feature extractors generated by DCNNs was pioneered by Mallat in . Mallat’s theory applies to so-called scattering networks, where signals are propagated through layers that compute a semi-discrete wavelet transform (i.e., convolutions with filters that are obtained from a mother wavelet through scaling and rotation operations), followed by the modulus non-linearity, without subsequent pooling. The resulting feature extractor is shown to be translation-invariant (asymptotically in the scale parameter of the underlying wavelet transform) and stable w.r.t. certain non-linear deformations. Moreover, Mallat’s scattering networks lead to state-of-the-art results in various classification tasks .

DCNN-based feature extractors that were found to work well in practice employ a wide range of i) filters, namely pre-specified structured filters such as wavelets , pre-specified unstructured filters such as random filters , and filters that are learned in a supervised or an unsupervised fashion, ii) non-linearities beyond the modulus function , namely hyperbolic tangents , rectified linear units , and logistic sigmoids , and iii) pooling operators, namely sub-sampling , average pooling , and max-pooling . In addition, the filters, non-linearities, and pooling operators can be different in different network layers . The goal of this paper is to develop a mathematical theory that encompasses all these elements (apart from max-pooling) in full generality.

Convolutional transforms as employed in DCNNs can be interpreted as semi-discrete signal transforms (i.e., convolutional transforms with filters that are countably parametrized). Corresponding prominent representatives are curvelet and shearlet transforms, both of which are known to be highly effective in extracting features characterized by curved edges in images. Our theory allows for general semi-discrete signal transforms, general Lipschitz-continuous non-linearities (e.g., rectified linear units, shifted logistic sigmoids, hyperbolic tangents, and modulus functions), and incorporates continuous-time Lipschitz pooling operators that emulate discrete-time sub-sampling and averaging. Finally, different network layers may be equipped with different convolutional transforms, different (Lipschitz-continuous) non-linearities, and different (Lipschitz-continuous) pooling operators.

Regarding translation invariance, it was argued, e.g., in , that in practice invariance of the features is crucially governed by network depth and by the presence of pooling operators (such as, e.g., sub-sampling , average-pooling , or max-pooling ). We show that the general feature extractor considered in this paper, indeed, exhibits such a vertical translation invariance and that pooling plays a crucial role in achieving it. Specifically, we prove that the depth of the network determines the extent to which the extracted features are translation-invariant. We also show that pooling is necessary to obtain vertical translation invariance as otherwise the features remain fully translation-covariant irrespective of network depth. We furthermore establish a deformation sensitivity bound valid for signal classes such as, e.g., band-limited functions, cartoon functions , and Lipschitz functions . This bound shows that small non-linear deformations of the input signal lead to small changes in the corresponding feature vector.

In terms of mathematical techniques, we draw heavily from continuous frame theory . We develop a proof machinery that is completely detached from the structuresStructure here refers to the structural relationship between the convolution kernels in a given layer, e.g., scaling and rotation operations in the case of the wavelet transform. of the semi-discrete transforms and the specific form of the Lipschitz non-linearities and Lipschitz pooling operators. The proof of our deformation sensitivity bound is based on two key elements, namely Lipschitz continuity of the feature extractor and a deformation sensitivity bound for the signal class under consideration, namely band-limited functions (as established in the present paper) or cartoon functions and Lipschitz functions as shown in . This “decoupling” approach has important practical ramifications as it shows that whenever we have deformation sensitivity bounds for a signal class, we automatically get deformation sensitivity bounds for the DCNN feature extractor operating on that signal class. Our results hence establish that vertical translation invariance and limited sensitivity to deformations—for signal classes with inherent deformation insensitivity—are guaranteed by the network structure per se rather than the specific convolution kernels, non-linearities, and pooling operators.

Notation

II Scattering networks

where $\Phi_{W}^{0}(f):=\{f\ast\psi_{(-J,0)}\}$, and

The family of functions $\{\psi_{\lambda}\}_{\lambda\in\Lambda_{\text{W}}}$ is taken to form a semi-discrete Parseval frame

It is shown in [22, Theorem 2.10] that the feature extractor $\Phi_{W}$ is translation-invariant in the sense of

Note that this upper bound goes to infinity as translation invariance through $J\to\infty$ is induced. In practice signal classification based on scattering networks is performed as follows. First, the function $f$ and the wavelet frame atoms $\{\psi_{\lambda}\}_{\lambda\in\Lambda_{\text{W}}}$ are discretized to finite-dimensional vectors. The resulting scattering network then computes the finite-dimensional feature vector $\Phi_{W}(f)$, whose dimension is typically reduced through an orthogonal least squares step , and then feeds the result into a trainable classifier such as, e.g., a SVM. State-of-the-art results for scattering networks were reported for various classification tasks such as handwritten digit recognition , texture discrimination , and musical genre classification .

III General deep convolutional feature extractors

As already mentioned, scattering networks follow the architecture of DCNNs in the sense of cascading convolutions (with atoms $\{\psi_{\lambda}\}_{\lambda\in\Lambda_{\text{W}}}$ of the wavelet frame $\Psi_{\Lambda_{\text{W}}}$) and non-linearities, namely the modulus function, but without pooling. General DCNNs as studied in the literature exhibit a number of additional features:

a wide variety of filters are employed, namely pre-specified unstructured filters such as random filters , and filters that are learned in a supervised or an unsupervised fashion.

a wide variety of non-linearities are used such as, e.g., hyperbolic tangents , rectified linear units , and logistic sigmoids .

convolution and the application of a non-linearity is typically followed by a pooling operator such as, e.g., sub-sampling , average-pooling , or max-pooling .

the filters, non-linearities, and pooling operators are allowed to be different in different network layers .

and amounts to simply retaining every $S$-th sample of $f_{\text{d}}$. The discrete-time Fourier transform of $h_{\text{d}}$ is given by a summation over translated and dilated copies of $\widehat{f_{\text{d}}}$ according to [62, Sec. 4]

The translated copies of $\widehat{f_{\text{d}}}$ in (6) are a consequence of the $1$-periodicity of the discrete-time Fourier transform. We therefore emulate the discrete-time sub-sampling operation in continuous time through the dilation operation

which in the frequency domain amounts to dilation according to $\widehat{h}=S^{-d/2}\widehat{f}(S^{-1}\cdot)$. The scaling by $S^{d/2}$ in (7) ensures unitarity of the continuous-time sub-sampling operation. The overall operation in (7) fits into our general definition of pooling as it can be recovered from (5) simply by taking $P$ to equal the identity mapping (which is, of course, Lipschitz-continuous with Lipschitz constant $R=1$ and satisfies $\text{Id}f=0$ for $f=0$). Next, we consider average pooling. In discrete time average pooling is defined by

We next state definitions and collect preliminary results needed for the analysis of the general DCNN feature extractor considered. The basic building blocks of this network are the triplets $(\Psi_{n},M_{n},P_{n})$ associated with individual network layers $n$ and referred to as modules.

The following definition introduces the concept of paths on index sets, which will prove useful in formalizing the feature extraction network. The idea for this formalism is due to .

For the inequality in (11) we used the Lipschitz continuity of $P_{n}$ according to $\|P_{n}f-P_{n}h\|^{2}_{2}\leq R_{n}^{2}\|f-h\|^{2}_{2}$, together with $P_{n}h=0$ for $h=0$ to get $\|P_{n}f\|_{2}^{2}\leq R_{n}^{2}\|f\|^{2}_{2}$. Similar arguments lead to the first inequality in (12). The last step in (12) is thanks to

which follows from the frame condition (30) on $\Psi_{n}$. We will also need the extension of the operator $U_{n}$ to paths $q\in\Lambda_{1}^{n}$ according to

with $U[e]f:=f$. Note that the multi-stage operation (13) is again well-defined thanks to

We are now ready to define the feature extractor $\Phi_{\Omega}$ based on the module-sequence $\Omega$.

As condition (16) is of central importance, we formalize it as follows.

is referred to as admissibility condition. Module-sequences that satisfy (17) are called admissible.

We emphasize that condition (17) is easily met in practice. To see this, first note that $B_{n}$ is determined through the frame $\Psi_{n}$ (e.g., the directional wavelet frame introduced in Section II has $B=1$), $L_{n}$ is set through the non-linearity $M_{n}$ (e.g., the modulus function $M=|\cdot|$ has $L=1$, see Appendix D), and $R_{n}$ depends on the operator $P_{n}$ in (5) (e.g., pooling by sub-sampling amounts to $P=\text{Id}$ and has $R=1$). Obviously, condition (17) is met if

which can be satisfied by simply normalizing the frame elements of $\Psi_{n}$ accordingly. We refer to Proposition 3 in Appendix A for corresponding normalization techniques, which, as explained in Section IV, affect neither our translation invariance result nor our deformation sensitivity bounds.

The following theorem states that under very mild decay conditions on the Fourier transforms $\widehat{\chi_{n}}$ of the output-generating atoms $\chi_{n}$, the feature extractor $\Phi_{\Omega}$ exhibits vertical translation invariance in the sense of the features becoming more translation-invariant with increasing network depth. This result is in line with observations made in the deep learning literature, e.g., in , where it is informally argued that the network outputs generated at deeper layers tend to be more translation-invariant.

The features $\Phi_{\Omega}^{n}(f)$ generated in the $n$-th network layer satisfy

If, in addition, there exists a constant $K>0$ (that does not depend on $n$) such that the Fourier transforms $\widehat{\chi_{n}}$ of the output-generating atoms $\chi_{n}$ satisfy the decay condition

In contrast, the translation invariance result (3) in is asymptotic in the wavelet scale parameter $J$, and does not depend on the network depth, i.e., it guarantees full translation invariance in every network layer. We honor this difference by referring to (3) as horizontal translation invariance and to (22) as vertical translation invariance.

We emphasize that vertical translation invariance is a structural property. Specifically, if $P_{n}$ is unitary (such as, e.g., in the case of pooling by sub-sampling where $P_{n}$ simply equals the identity mapping), then so is the pooling operation in (5) owing to

IV-B Deformation sensitivity bound

This class of deformations encompasses non-linear distortions $f(x-\tau(x))$ as illustrated in Fig. 5, and modulation-like deformations $e^{2\pi i\omega(x)}f(x)$ which occur, e.g., if the signal $f$ is subject to an undesired modulation and we therefore have access to a bandpass version of $f$ only.

The deformation sensitivity bound we derive is signal-class specific in the sense of applying to input signals belonging to a particular class, here band-limited functions. The proof technique we develop applies, however, to all signal classes that exhibit “inherent” deformation insensitivity in the following sense.

Our signal-class specific deformation sensitivity bound is based on the following two ingredients. First, we establish—in Proposition 4 in Appendix I—that the feature extractor $\Phi_{\Omega}$ is Lipschitz-continuous with Lipschitz constant $L_{\Omega}=1$, i.e.,

The deformation sensitivity bound for the feature extractor is then obtained by setting $h=F_{\tau,\omega}f$ in (24) and using (25) (see Appendix H for the corresponding technical details). This “decoupling” into Lipschitz continuity of $\Phi_{\Omega}$ and a deformation sensitivity bound for the signal class under consideration (here, band-limited functions) has important practical ramifications as it shows that whenever we have a deformation sensitivity bound for the signal class, we automatically get a deformation sensitivity bound for the feature extractor thanks to its Lipschitz continuity. The same approach was used in to derive deformation sensitivity bounds for cartoon functions and for Lipschitz functions.

We proceed to the formal statement of our deformation sensitivity result.

The bound (II) for scattering networks reported in [22, Theorem 2.12] depends upon first-order $(D\tau)$ and second-order $(D^{2}\tau)$ derivatives of $\tau$. In contrast, our bound (26) depends on $(D\tau)$ implicitly only as we need to impose the condition $\|D\tau\|_{\infty}\leq\frac{1}{2d}$ for the bound to holdWe note that the condition $\|D\tau\|_{\infty}\leq\frac{1}{2d}$ is needed for the bound (II) to hold as well.. We honor this difference by referring to (II) as deformation stability bound and to our bound (26) as deformation sensitivity bound.

The dependence of the upper bound in (26) on the bandwidth $R$ reflects the intuition that the deformation sensitivity bound should depend on the input signal class “description complexity”. Many signals of practical significance (e.g., natural images) are, however, either not band-limited due to the presence of sharp (and possibly curved) edges or exhibit large bandwidths. In the latter case, the bound (26) is effectively rendered void owing to its linear dependence on $R$. We refer the reader to where deformation sensitivity bounds for non-smooth signals were established. Specifically, the main contributions in are deformation sensitivity bounds—again obtained through decoupling—for non-linear deformations $(F_{\tau}f)(x)=f(x-\tau(x))$ according to

Finally, the deformation stability bound (II) for scattering networks reported in [22, Theorem 2.12] applies to the space

V Final remarks and outlook

Appendix A Semi-discrete frames

This appendix gives a brief review of the theory of semi-discrete frames. A list of structured example frames of interest in the context of this paper is provided in Appendix B for the $1$-D case, and in Appendix C for the $2$-D case. Semi-discrete frames are instances of continuous frames , and appear in the literature, e.g., in the context of translation-covariant signal decompositions , and as an intermediate step in the construction of various fully-discrete frames . We first collect some basic results on semi-discrete frames.

The functions $\{g_{\lambda}\}_{\lambda\in\Lambda}$ are called the atoms of the frame $\Psi_{\Lambda}$. When $A=B$ the frame is said to be tight. A tight frame with frame bound $A=1$ is called a Parseval frame.

The proof is standard and can be found, e.g., in [30, Theorem 5.11]. ∎

What is behind Proposition 2 is a result on the unitary equivalence between operators [70, Definition 5.19.3]. Specifically, Proposition 2 follows from the fact that the multiplier $\sum_{\lambda\in\Lambda}|\widehat{g_{\lambda}}|^{2}$ is unitarily equivalent to the frame operator $S_{\Lambda}$ in (31) according to

The following proposition states normalization results for semi-discrete frames that come in handy in satisfying the admissibility condition (17) as discussed in Section III.

Appendix B Examples of semi-discrete frames in 111-D

General $1$-D semi-discrete frames are given by collections

Semi-discrete curvelet frames: Curvelets, introduced in , are well-suited to the extraction of signal features characterized by curve-like singularities (such as, e.g., curved edges in images), and have been applied successfully in various practical feature extraction tasks .

Appendix C Examples of semi-discrete frames in 222-D

Semi-discrete wavelet frames: Two-dimensional wavelets are well-suited to the extraction of signal features characterized by point singularities (such as, e.g., stars in astronomical images ), and have been applied successfully in various practical feature extraction tasks, e.g., in . Prominent families of two-dimensional wavelet frames are tensor wavelet frames and directional wavelet frames:

Semi-discrete ridgelet frames: Ridgelets, introduced in , are well-suited to the extraction of signal features characterized by straight-line singularities (such as, e.g., straight edges in images), and have been applied successfully in various practical feature extraction tasks .

For further examples of interesting structured semi-discrete frames, we refer to , which discusses semi-discrete shearlet frames, and , which deals with semi-discrete $\alpha$-curvelet frames.

Appendix D Non-linearities

All non-linearities considered here are pointwise (memoryless) operators in the sense of

has been applied successfully in the deep learning literature, e.g., in , and most prominently in scattering networks . Lipschitz continuity with $L=1$ follows from

where we used the triangle inequality in (44),

where, again, we used the triangle inequality. In order to further upper-bound (47), we show that $\tanh$ is Lipschitz-continuous. To this end, we make use of the following result.

which establishes Lipschitz continuity of $P$ with $L=\frac{1}{2}$. Since $\text{sig}(0)=0$, we trivially have $Pf=0$ for $f=0$. Finally, (43) is satisfied with $\rho(x):=\text{sig}(\operatorname{Re}(x))+i\text{sig}(\operatorname{Im}(x))$.

Appendix E Proof of Proposition 1

The key step is then to establish that $a_{n}$ can be upper-bounded according to

By (51) this then implies (50). We start by noting that (52) reads

Substituting the second term on the RHS of (55) by (56) now yields

Next, note that the second term inside the sum on the left hand side (LHS) of (57) can be written as

Substituting the second term inside the sum on the LHS of (57) by the upper bound resulting from insertion of (59) into (58) yields

in (61) yields (57) and thereby completes the proof.

Appendix F Proof of Theorem 1

To establish (62), we first define the unitary operator

The key step is then to establish the upper bound

where $K>0$ corresponds to the constant in the decay condition (20), and to note that

The identity (67) together with the inequalities (68) and (72) then directly imply

where in the last step we employed the Cauchy-Schwartz inequality. Substituting (75) into (74) yields

Appendix G Proof of Corollary 1

The key step is then to establish the upper bound

where $K>0$ corresponds to the constant in the decay condition (20). Arguments similar to those leading to (73) then complete the proof. It remains to prove (80):

where, again, we employed the Cauchy-Schwartz inequality. Substituting (82) into (81), and employing arguments similar to those leading to (77), establishes (80) and thereby completes the proof.

Appendix H Proof of Theorem 2

As already mentioned at the beginning of Section IV-B, the proof of the deformation sensitivity bound (26) is based on two key ingredients. The first one, stated in Proposition 4 in Appendix I, establishes that the feature extractor $\Phi_{\Omega}$ is Lipschitz-continuous with Lipschitz constant $L_{\Omega}=1$, i.e.,

and needs the admissibility condition (17) only. The second ingredient, stated in Proposition 5 in Appendix J, is an upper bound on the deformation error $\|f-F_{\tau,\omega}f\|_{2}$ given by

obtained through the change of variables $u=x-\tau(x)$, together with

The second inequality in (86) is a consequence of the assumption $\|D\tau\|_{\infty}\leq\frac{1}{2d}$. The proof is finalized by replacing the RHS of (85) by the RHS of (84).

Appendix I Proposition 4

Proposition 4 generalizes [22, Proposition 2.5], which shows that the wavelet-modulus feature extractor $\Phi_{W}$ generated by scattering networks is Lipschitz-continuous with Lipschitz constant $L_{W}=1$. Specifically, our generalization allows for general semi-discrete frames (i.e., general convolution kernels), general Lipschitz-continuous non-linearities $M_{n}$, and general Lipschitz-continuous operators $P_{n}$, all of which can be different in different layers. Moreover, thanks to the admissibility condition (17), the Lipschitz constant $L_{\Omega}=1$ in (87) is completely independent of the frame upper bounds $B_{n}$ and the Lipschitz-constants $L_{n}$ and $R_{n}$ of $M_{n}$ and $P_{n}$, respectively.

As in the proof of Proposition 1 in Appendix E, the key step is to show that $a_{n}$ can be upper-bounded according to

Writing out (88), it follows that we need to establish

Substituting (90) into (89) and rearranging terms, we obtain

We next note that the second term inside the sum on the LHS of (91) satisfies

where we employed arguments similar to those leading to (58). Substituting the second term inside the sum on the LHS of (91) by the upper bound (92), and using the Lipschitz property of $M_{n+1}$ and $P_{n+1}$ yields

in (94) we get (91) and hence (88). This completes the proof. ∎

Appendix J Proposition 5

A similar bound was derived in [22, App. B] for scattering networks, namely

satisfying the signal-class specific identity

and then upper-bound the deformation error $\|f-F_{\tau,\omega}f\|_{2}$ according to

that the integral operator $K=F_{\tau,\omega}A_{\gamma}-A_{\gamma}$, i.e.,

where the first term in (100) follows by the change of variables $y=x-\tau(x)-u$, together with

Next, we integrate (108) w.r.t. $u$ to establish (i) in (98):

which establishes an upper bound of the form (i) in (98) that exhibits the desired structure for $\alpha$. Condition (ii) in (98) is established similarly by integrating (108) w.r.t. $x$ according to

Acknowledgments

The authors would like to thank P. Grohs, S. Mallat, R. Alaifari, M. Tschannen, and G. Kutyniok for helpful discussions and comments on the paper.

References