Title: A THEORETICAL FRAMEWORK FOR DEEP AND LO-CALLY CONNECTED RELU NETWORK

Abstract: Understanding theoretical properties of deep and locally connected nonlinear network, such as deep convolutional neural network (DCNN), is still a hard problem despite its empirical success. In this paper, we propose a novel theoretical framework for such networks with ReLU nonlinearity. The framework bridges data distribution with gradient descent rules, favors disentangled representations and is compatible with common regularization techniques such as Batch Norm, after a novel discovery of its projection nature. The framework is built upon teacher-student setting, by projecting the student's forward/backward pass onto the teacher's computational graph. We do not impose unrealistic assumptions (e.g., Gaussian inputs, independence of activation, etc). Our framework could help facilitate theoretical analysis of many practical issues, e.g. disentangled representations in deep networks.

:

In this paper, we propose a novel theoretical framework for deep and locally connected ReLU network that is applicable to general data distributions. Specifically, we embrace a teacher-student setting. The teacher computes classification labels via a computational graph that has local structures (e.g., CNN): intermediate variables in the graph, (called summarization variables), are computed from a subset of the input dimensions. The student network, with similar local structures, updates the weights to fit teacher's labels with gradient descent, without knowing the summarization variables.

One ultimate goal is to show that after training, each node in the student network is highly selective with respect to the summarization variable in the teacher. Achieving this goal will shed light to how the training of practically effective methods like CNN works, which remains a grand challenge. As a first step, we reformulate the forward/backward pass in gradient descent by marginalizing out the input data conditioned on the graph variables of the teacher at each layer. The reformulation has nice properties: (1) it relates data distribution with gradient update rules, (2) it is compatible with existing Receptive fields form a hierarchy. The entire input is denoted as x (or x ω ). A local region of an input x is denoted as x α . (b) For each region α, we have a latent multinomial discrete variable z α which is computed from its immediate children {z β } β∈ch(α) . Given the input x, z α = z α (x α ) is a function of the image content x α at α. Finally, z ω at the top level is the class label. (c) A locally connected neural network is trained with pairs (x, z ω (x)), where z ω (x) is the class label generated from the teacher. (d) For each node j, f j (x) is the activation while g j (x) is the back-propagated gradient, both as function of input x (and weights at different layers).

state-of-the-art regularization techniques such as Batch Normalization (Ioffe & Szegedy, 2015) , and

(3) it favors disentangled representation when data distributions have factorizable structures. To our best knowledge, our work is the first theoretical framework to achieve these properties for deep and locally connected nonlinear networks.

Previous works have also proposed framework to explain deep networks, e.g., renormalization group for restricted Boltzmann machines (Mehta & Schwab, 2014) , spin-glass models (Amit et al., 1985; Choromanska et al., 2015a) , transient chaos models (Poole et al., 2016) , differential equations (Su et al., 2014; Saxe et al., 2013) , information bottleneck (Achille & Soatto, 2017; Tishby & Zaslavsky, 2015; Saxe et al., 2018) , etc. In comparison, our framework (1) imposes mild assumptions rather than unrealistic ones (e.g., independence of activations), (2) explicitly deals with back-propagation which is the dominant approach used for training in practice, and relates it with data distribution, and

(3) considers spatial locality of neurons, an important component in practical deep models.

2. PROBLEM SETTING:

We consider multi-layer (deep) and locally connected network with ReLU nonlinearity. We consider supervised setting, in which we have a dataset {(x, y)}, where x is the input image and y is its label computed from x deterministically. It is hard to analyze y which does not have a structure (e.g., random labels). Here our analysis assumes the generation of y from x has a specific hierarchical structure. We use teacher-student setting to study the property: a student network learns teacher's label y via gradient descent, without knowing teacher's internal representations.

2.1. RECEPTIVE FIELDS:

An interesting characteristics in locally connected network is that each neuron only covers a fraction of the input dimension. Furthermore, for deep and locally connected network, neurons in the lower layer cover a small region while neurons in the upper layer cover a large region.

We use Greek letters {α, β, . . . , ω} to represent receptive fields. For a receptive field α, x α is the content in that region. We use ω to represent the entire image (Fig. 1(a) ).

Receptive fields form a hierarchy: α is a parent of β, denoted as α ∈ pa(β) or β ∈ ch(α), if α ⊇ β and there exists no other receptive field γ / ∈ {α, β} so that α ⊇ γ ⊇ β. Note that siblings can have substantial overlaps (e.g., β 1 and β 2 in Fig. 1(a) ). With this partial ordering, we can attach layer number l to each receptive field: α ∈ pa(β) implies l(β) = l(α) + 1. For top-most layer (closest to classification label), l = 0 and for bottom-most layer, l = L.

For locally connected network, a neuron (or node) j ∈ α means its receptive field is α. Denote n α as the number of nodes covering the same region (e.g., multi-channel case, Fig. 2(a) ). The image content is x α(j) , abbreviated as x j if no ambiguity. The parent j's receptive field covers its children's.

2.2. THE TEACHER:

We assume the label y of the input x is computed by a teacher in a bottom-up manner: for each region α, we compute a summarization variable z α from the summarization variables of its children:

(b) (a)

Figure 2 : (a) Multiple nodes (neurons) share the same receptive field α. Note that n α is the number of nodes sharing the receptive field α. (b) Grouping nodes with the same receptive fields together. By abuse of notation, α also represents the collection of all nodes with the same receptive field.

z α = φ α ({z β } β∈ch(α)

). This procedure is repeated until the top-level summarization z ω is computed, which is the class label y. We denote φ = {φ α } as the collection of all summarization functions.

For convenience, we assume z α be discrete variables that takes m α possible values. Intuitively, m α is exponential w.r.t the area of the receptive field sz(α), for binary input, m α ≤ 2 sz (α) . We call a particular assignment of z α , z α = a, an event. For the bottom-most layers, z is just the (discretized) value in each dimension.

At each stage, the upward function is deterministic but lossy: z α does not contain all the information in {z β } for β ∈ ch(α). Indeed, it keeps relevant information in the input region x α with respect to the class label, and discards the irrelevant part. During training, all summarization variables Z = {z α } are unknown to the student, except for the label y.

Example of teacher networks. Locally connected network itself is a good example of teacher network, in which nodes of different channels located at one specific spatial location form some encoding of the variable z α . Note that the relationship between a particular input x and the corresponding values of the summarization variable z at each layer is purely deterministic.

The reason why probabilistic quantities (e.g., P(z α ) and P(z α |z β )) appear in our formulation, is due to marginalization over z (or x). This marginalization implicitly establishes a relationship between the conditional probabilities P(z α |z β ) and the input data distribution P(x). If we have specified P(z α |z β ) at each layer, then we implicitly specify a certain kind of data distribution P(x). Conversely, given a certain kind of P(x) and summarization function φ, we can compute P(z α |z β ) by sampling x, compute summarization variable z α , and accumulate frequency statistics of P(z α |z β ). If there is an overlap between sibling receptive fields, then it is likely that some relationship among P(z α |z β ) might exist, which we leave for future work.

Although such an indirect specification may not be as intuitive and mathematically easy to deal with as common assumptions used in previous works (e.g., assuming Gaussian input (Tian, 2017; Du et al., 2018; Brutzkus & Globerson, 2017) ), it gives much more flexibility of the distribution x and is more likely to be true empirically.

Comparison with top-down generative model. An alternative (and more traditional) way to specify data distribution is to use a top-down generative model: first sample the label y, then sample the latent variables z α at each layer in a top-down manner, until the input layer. Marginalizing over all the latent variables z α yields a class-conditioned data distribution P(x|y).

The main difficulty of this top-down modeling is that when the receptive fields α and α of sibling latent variables overlap, the underlying graphical model becomes loopy. This makes the population loss function, which involves an integral over the input data x, very difficult to deal with. As a result, it is nontrivial to find a concise relationship between the parameters in the top-down modeling (e.g., conditional probability) and the optimization techniques applied to neural network (e.g., gradient descent). In contrast, as we will see in Sec. 3, our modeling naturally gives relationship between gradient descent rules and conditional probability between nearby summarization variables.

2.3. THE STUDENT:

We consider a neuron (or node) j. Denote f j as its activation after nonlinearity and g j as the (input) gradient it receives after filtered by ReLU's gating (Fig. 1(d) ). Note that both f j and g j are deterministic functions of the input x and label y, and are abbreviated as f j (x) and g j (x).1 .

The activation f j and gradient g k can be written as (note that f j is the binary gating function):

EQUATION

And the weight update for gradient descent is

∆w jk = E x [f k (x)g j (x)].

Here is the expectation is with respect to a training dataset (or a batch), depending on whether GD or SGD has been used. We also use f raw j and g raw j as the counterpart of f j and g j before nonlinearity.

For locally connected network, the activation f j of node j is only dependent on the region x j , rather than the entire image x. This means that f j (x) = f j (x j ) and f j (x j ) = f j (x j ) k w jk f k (x k ). However, the gradient g j is determined by the entire image x, and its label y, i.e., g j = g j (x, y).

Note that since the label y is a deterministic (but unknown) function of x, for gradient we just write g j = g j (x).

Marginalized Gradient. For locally connected network, the gradient g j has some nice structures.

From Eqn. 17 we knows that

∆w jk = E x [f k (x)g j (x)] = E x k f k (x k )E x -k |x k [g j (x)] . Define x -k = x\x k as the input image x except for x k .

Then we can define the marginalized gradient:

EQUATION

as the marginalization (average) of x -k , while keep x k fixed. With this notation, we can write

∆w jk = E x k [f k (x k )g j (x k )].

On the other hand, the gradient which back-propagates to a node k can be written as

EQUATION

where f k is the derivative of activation function of node k (for ReLU it is just a gating function). If we take expectation with respect to x -k |x k on both side, we get

EQUATION

Note that all marginalized gradients g j (x k ) are independently computed by marginalizing with respect to all regions that are outside the receptive field x k . Interestingly, there is a relationship between these gradients that respects the locality structure: Theorem 1 (Recursive Property of marginalized gradient).

g j (x k ) = E x j,-k |x k [g j (x j )]

This shows that there is a recursive structure in marginal gradient: we can first compute g j (x j ) for top node j, then by marginalizing over the region within x j but outside x k , we get its projection g j (x k ) on child k, then by Eqn. 20 we collect all projections from all the parents of node k, to get g k (x k ). This procedure can be repeated until we arrive at the leaf nodes.

3. THE FRAMEWORK AND ITS GOAL:

Let's first consider the following quantity. For each neural node j, we want to compute the expected gradient given a particular factor z α , where α = rf(j) (the reception field of node j):

g j (z α ) ≡ E Xj |zα [g j (X j )] = g j (x j )P(x j |z α )dx j (5) And gj (z α ) = g j (z α )P(z α ). Similarly, f j (z α ) = E Xj |zα [f j (X j )] and f j (z α ) = E Xj |zα f j (X j ) .

Note that P(x j |z α ) is the frequency count of x j for z α . If z α captures all information of x j , then P(x j |z α ) is a delta function. Throughout the paper, we use frequentist interpretation of probabilities.

Goal. Intuitively, if we have g j (z α = a) > 0 and g j (z α = a) < 0, then the node j learns about the hidden event z α = a. For multi-class classification, the top level nodes (just below the softmax layer) already embrace such correlations (here j is the class label): g j (y = j) > 0 and g j (y = j) < 0, where we know z ω = y is the top level factor. A natural question now arises:

Does gradient descent automatically push g j (z α ) to be correlated with the factor z α ? If this is true, then gradient descent on deep models is essentially a weak-supervised approach that automatically learns the intermediate events at different levels. Giving a complete answer of this question is very difficult and is beyond the scope of this paper. As a first step, we build a theoretical framework that enables such analysis. We start with the relationship between neighboring layers: Theorem 2 (Reformulation). For node j and k and their receptive field α and β. If the following two conditions holds:

Dimension Description F α , Gα , D α m α -by-n α Activation f j (z α ),

1) Onsite Conditional independence. P(x j |z rf(j) , z ... ) = P(x j |z rf(j) ).

2) Decorrelation. Given z β , g raw k (•) and f raw k (•) are uncorrelated with f k (•): E x k |z β [f k g raw k ] = E x k |z β [f k ] E x k |z β [g raw k ] , E x k |z β [f k f raw k ] = E x k |z β [f k ] E x k |z β [f raw k ] (6)

Then the following iterative equations hold:

EQUATION

The reformulation becomes exact if z α contains all information of the region. Theorem 3. If P(x j |z α ) is a delta function for all α, then all conditions in Thm. 2 hold.

While Thm. 3 holds in the ideal (and maybe trivial) case, both assumptions are still practically reasonable. For assumption (1), the main idea is that the image content x α is most related to the summarization variable z α located at the same receptive field α, and less related to others. On the other hand, assumptions (2) holds approximately if the summarization variable is fine-grained.

Intuitively, P(x j |z α ) is a distribution encoding how much information gets lost if we only know the factor z α . Climbing up the ladder, more and more information is lost while keeping the critical part for the classification. This is consistent with empirical observations (Bau et al., 2017) , in which the low-level features in DCNN are generic, and high-level features are more class-specific.

One key property of this formulation is that, it relates conditional probabilities P(z α , z β ), and thus input data distribution P(x) into the gradient descent rules. This is important since running backpropagation on different dataset is now formulated into the same framework with different probability, i.e., frequency counts of events. By studying which family of distribution leads to the desired property, we could understand backpropagation better.

Furthermore, the property of stochastic gradient descent (SGD) can be modeled as using an imperfect estimate P(z α , z β ) of the true probability P(z α , z β ) when running backpropagation. This is because each batch is a rough sample of the data distribution so the resulting P(z α , z β ) will also be different. This could also unite GD and SGD analysis.

For boundary conditions, in the lowest level L, we could treat each input pixel (or a group of pixels) as a single event:

f k (z β ) = I [k = z β ].

For top level, each node j corresponds to a class label j while the summarization variable z α also take class labels:

g j (z α ) = a 1 I [j = z α ] -a 2 I [j = z α ].

If we group the nodes with the same reception field at the same level together (Fig. 2 ), we have the matrix form of Eqn. 7 (• is element-wise multiplication): Theorem 4 (Matrix Representation of Reformulation).

F α = D α • β∈ch(α) P αβ F β W βα , Gβ = D β • α∈pa(β) P T αβ Gα W T βα , ∆W βα = (P αβ F β ) T Gα (8)

See Tbl. 3 for the notation. For this dynamics, we want F * ω = I nω , i.e., the top n ω neurons faithfully represents the classification labels. Therefore, the top level gradient is G ω = I nω -F ω . On the other side, for each region β at the bottom layer, we have F β = I n β , i.e., the input contains all the preliminary factors. For all regions α in the top-most and bottom-most layers, we have n α = m α . 

4. BATCH NORMALIZATION UNDER REFORMULATION:

Our reformulation naturally incorporates empirical regularization technique like Batch Normalization (BN) (Ioffe & Szegedy, 2015) .

4.1. BATCH NORMALIZATION AS A PROJECTION:

We start with a novel finding of Batch Norm: the back-propagated gradient through Batch Norm layer at a node j is a projection onto the orthogonal complementary subspace spanned by all one vectors and the current activations of node j.

Denote pre-batchnorm activations as:

f = [f j (x 1 ), . . . f j (x N )]

where N is the batchsize. In Batch Norm, f is whitened to be f , then linearly transformed to yield the output f bn (note that we omit node subscript j for clarity):

EQUATION

where µ = 1 N f T 1 and σ 2 = 1 N f T f and c 1 , c 0 are learnable parameters.

The original Batch Norm paper (Ioffe & Szegedy, 2015) derives complicated and unintuitive weight update rules. With vector notation, the update has a compact form with a clear geometric meaning.

Theorem 5 (Backpropagation of Batch Norm). For a top-down pre-BN gradient g bn (a vector of size N -by-1,N is the batchsize), the gradient after passing BN layer is the following:

EQUATION

Here P ⊥ f ,1 is the orthogonal complementary projection onto subspace {f , 1} and S(f

) ≡ [ f , 1].

Intuitively, the back-propagated gradient g is zero-mean and perpendicular to the input activation f of BN layer, as illustrated in Fig. 3 . Unlike (Kohler et al., 2018) that analyzes BN in an approximate manner, in Thm. 5 we do not impose any assumptions.

4.2. BATCH NORM UNDER THE REFORMULATION:

In our reformulation, we take the expectation of input x so there is no explicit notation of batch. However, we could regard each sample in the batch as i.i.d. samples from the data distribution P(x).

Then the analysis of Batch Norm in Sec. 4.1 could be applied in the reformulation and yield similar results, using the quantity that

E x [f j (x)] = E zα [f j (z α )].

In this case, we have µ = E zα [f j ] and σ 2 = E zα (f j (z α ) -µ) 2 , and J BN (f ) = c1 σ P ⊥,zα f ,1 . Note that the projection matrix P ⊥,zα f ,1 is under the new inner product f j , g j zα = E zα [f j (z α )g j (z α )] and

norm f zα = f, f 1/2 zα . In comparison, Sec. 4.1 is a special case with P(z α ) = 1 N N i=1 δ(z α - φ α (x i ))

, where x 1 , . . . , x N are the batch samples.

One consequence is that for Gα , we have

1 T Gα = [E zα [g 1 (z α )] , . . . , E zα [g nα (z α )]] = 0 since g j (•

) is in the null space of 1 under the inner product •, • zα . This property will be used in Sec. 5.2. 

5. EXAMPLE APPLICATIONS OF PROPOSED THEORETICAL FRAMEWORK:

With the help of the theoretical framework, we now can analyze interesting structures of gradient descent in deep models, when the data distribution P(z α , z β ) satisfies specific conditions. Here we give two concrete examples: the role played by nonlinearity and in which condition disentangled representation can be achieved. Besides, from the theoretical framework, we also give general comments on multiple issues (e.g., overfitting, GD versus SGD) in deep learning.

5.1. NONLINEAR VERSUS LINEAR:

In the formulation, m α is the number of possible events within a region α, which is often exponential with respect to the size sz(α) of the region. The following analysis shows that a linear model cannot handle it, even with exponential number of nodes n α , while a nonlinear one with ReLU can. Definition 1 (Convex Hull of a Set). We define the convex hull Conv(P ) of m points P ⊂ R n to be Conv(P ) = P a, a ∈ ∆ n-1 , where ∆ n-1 = {a ∈ R n , a i ≥ 0, i a i = 1}. A row p j is called vertex if p j / ∈ Conv(P \p j ). Definition 2. A matrix P of size m-by-n is called k-vert, or vert(P ) = k ≤ m, if its k rows are vertices of the convex hull generated by its rows. P is called all-vert if k = m. Theorem 6 (Expressibility of ReLU Nonlinearity). Assuming m α = n α = O(exp(sz(α))), where sz(α) is the size of receptive field of α. If each P αβ is all-vert, then: (ω is top-level receptive field)

EQUATION

Note that here Loss(W ) ≡ F ω -I 2 F . This shows the power of nonlinearity, which guarantees full rank of output, even if the matrices involved in the multiplication are low-rank. The following theorem shows that for intermediate layers whose input is not identity, the all-vert property remains. Theorem 7. (1) If F is full row rank, then vert(P F ) = vert(P ). (2) P F is all-vert iff P is all-vert. This means that if all P αβ are all-vert and its input F β is full-rank, then with the same construction of Thm. 6, F α can be made identity. In particular, if we sample W randomly, then with probability 1, all F β are full-rank, in particular the top-level input F 1 . Therefore, using top-level W 1 alone would be sufficient to yield zero generalization error, as shown in the previous works that random projection could work well.

5.2. DISENTANGLED REPRESENTATION:

The analysis in Sec. 5.1 assumes that n α = m α , which means that we have sufficient nodes, one neuron for one event, to convey the information forward to the classification level. In practice, this is never the case. When n α m α = O(exp(sz(α))) and the network needs to represent the information in a proper way so that it can be sent to the top level. Ideally, if the factor z α can be written down as a list of binary factors:

z α = z α[1] , z α[2] , . . . , z α[j]

, the output of a node j could represent z α[j] , so that all m α events can be represented concisely with n α nodes.

Symbols Description z α[j]:

The j-th binary factor of region α. z α[j] can take 0 or 1. p α [j] 2-by-1 marginal probability vector of binary factor z α

[j] . f α[j] , g α[j]

, gα[j] The j-th column of F α , G α and Gα corresponding to j-th binary factor z α [j] .

1 / 0 All-1 / All-0 vector. Its dimension depends on context.

F 1 ⊗ F 2 Out (or tensor) product of F 1 and F 2 . ⊗ K k=1 F k is the product of multiple F k . {S αβ i }

Disjoint collection of n α indices sets. S αβ i are the indices of downstream nodes in β to i-th binary factor in α (Fig. 4(b) ). W βα [S αβ j , j] The j-th subcolumn of weight matrix W βα , whose rows are selected by S αβ j .

Table 2 : Symbols used in Sec. 5.2.

To come up with a complete theory for disentangled representation in deep nonlinear network is far from trivial and beyond the scope of this paper. In the following, we make an initial attempt by constructing factorizable P αβ so that disentangled representation is possible in the forward pass. First we need to formally define what is disentangled representation: Definition 3. The activation F α is disentangled, if its j-th column F α,:j = 1 ⊗ . . .⊗f α[j] ⊗. . .⊗1, where each f α[j] and 1 is a 2-by-1 vector.

Definition 4. The gradient Gα is disentangled, if its j-th column Gα,:

j = p α[1] ⊗ . . .⊗ gα[j] ⊗. . .⊗ p α[nα]

, where p α[j] = [P(α[j] = 0), P(α[j] = 1)] T and gα[j] is a 2-by-1 vector.

Intuitively, this means that each node j represents the binary factor z α [j]. A follow-up question is whether such disentangled properties carries over layers in the forward pass. It turns out that the disentangled structure carries if the data distribution and weights have compatible structures:

Definition 5. The weights W βα is separable with respect to a disjoint set

{S αβ i }, if W βα = diag W βα [S αβ 1 , 1], W βα [S αβ 2 , 2], . . . , W βα [S αβ nα , n α ]

. Theorem 8 (Disentangled Forward). If for each β ∈ ch(α), P αβ can be written as a tensor product

P αβ = i P α[i]β[S αβ i ]

where {S αβ i } are αβ-dependent disjointed set, W βα is separable with respect to {S αβ i }, F β is disentangled, then F α is also disentangled (with/without ReLU /Batch Norm). If the bottom activations are disentangled, by induction, all activations will be disentangled. The next question is whether gradient descent preserves such a structure. The answer is also conditionally yes: Theorem 9 (Separable Weight Update). If P αβ = i P α[i]β[Si] , F β and Gα are both disentangled, 1 T Gα = 0, then the gradient update ∆W βα is separable with respect to {S i }.

Therefore, with disentangled F β and Gα and centered gradient 1 T Gα = 0, the separable structure is conserved over gradient descent, given the initial W (0) βα is separable. Note that centered gradient is guaranteed if we insert Batch Norm (Eqn. 83) after linear layers. And the activation F remains disentangled if the weights are separable.

The hard part is whether Gβ remains disentangled during backpropagation, if { Gα } α∈pa(β) are all disentangled. If so, then the disentangled representation is self-sustainable under gradient descent. This is a non-trivial problem and generally requires structures of data distribution. We put some discussion in the Appendix and leave this topic for future work.

6. EXPLANATION OF COMMON BEHAVIORS IN DEEP LEARNING:

In the proposed formulation, the input x in Eqn. 7 is integrated out, and the data distribution is now encoded into the probabilistic distribution P(z α , z β ), and their marginals. A change of such distribution means the input distribution has changed. For the first time, we can now analyze many practical factors and behaviors in the DL training that is traditionally not included in the formulation.

Over-fitting. Given finite number of training samples, there is always error in estimated factor-factor distribution P(z α , z β ) and factor-observation distribution P(x α |z α ). In some cases, a slight change of distribution would drastically change the optimal weights for prediction, which is overfitting. On the other hand, as shown in Fig. 5 , P(x α |z α ) contains a lot of detailed structures and is almost impossible to separate in the finite sample case, while P(x γ |z γ ) could be well separated for z γ = 0/1. Therefore, for node j with rf(j) = α, f j (z α ) ≈ constant (input almost indistinguishable):

EQUATION

)

where

g 0 (z α ) = E zω|zα [g 0 (z ω )] = 1 z α = 1 -1 z α = 0

, which is a strong gradient signal backpropagated from the top softmax level, since z α is strongly correlated with z ω . For node k with rf(k) = γ, an easy separation of the input (e.g., random initialization) yields distinctive f k (z γ ). Therefore,

EQUATION

)

where g 0 (z γ ) = E zω|zγ [g 0 (z ω )] = 2 z γ = 1 -2 z γ = 0 , a weak signal because of z γ is (almost) unrelated to the label. Therefore, we see that the weight w j that links to meaningful receptive field z α does not receive strong gradient, while the weight w k that links to irrelevant (but spurious) receptive field z γ receives strong gradient. This will lead to overfitting.

With more data, over-fitting is alleviated since (1) P(z ω |z γ ) becomes more accurate and → 0; (2) P(x α |z α ) starts to show statistical difference for z α = 0/1 and thus f j (z α ) shows distinctiveness.

Note that there exists a second explanation: we could argue that z γ is a true but weak factor that contributes to the label, while z α is a fictitious discriminative factor, since the appearance difference between z α = 0 and z α = 1 (i.e., P(x α |z α ) for α = 0/1) could be purely due to noise and thus should be neglected. With finite number of samples, these two cases are essentially indistinguishable. Models with different induction bias might prefer one to the other, yielding drastically different generalization error. For neural network, SGD prefers the second explanation but if under the pressure of training, it may also explore the first one by pushing gradient down to distinguish subtle difference in the input. This may explain why the same neural networks can fit random-labeled data, and generalize well for real data (Zhang et al., 2016) .

Gradient Descent: Stochastic or not? Previous works (Keskar et al., 2017) show that empirically stochastic gradient decent (SGD) with small batch size tends to converge to "flat" minima and offers better generalizable solution than those uses larger batches to compute the gradient.

From our framework, SGD update with small batch size is equivalent to using a perturbed/noisy version of P(z α , z β ) at each iteration. Such an approach naturally reduces aforementioned over-fitting issues, which is due to hyper-sensitivity of data distribution and makes the final weight solution invariant to changes in P(z α , z β ), yielding a "flat" solution.

7. CONCLUSION AND FUTURE WORK:

In this paper, we propose a novel theoretical framework for deep (multi-layered) nonlinear network with ReLU activation and local receptive fields. The framework utilizes the specific structure of neural networks, and formulates input data distributions explicitly. Compared to modeling deep models as non-convex problems, our framework reveals more structures of the network; compared to recent works that also take data distribution into considerations, our theoretical framework can model deep networks without imposing idealistic analytic distribution of data like Gaussian inputs or independent activations. Besides, we also analyze regularization techniques like Batch Norm, depicts its underlying geometrical intuition, and shows that BN is compatible with our framework.

Using this novel framework, we have made an initial attempt to analyze many important and practical issues in deep models, and provides a novel perspective on overfitting, generalization, disentangled representation, etc. We emphasize that in this work, we barely touch the surface of these core issues in deep learning. As a future work, we aim to explore them in a deeper and more thorough manner, by using the powerful theoretical framework proposed in this paper.

8. APPENDIX:



We consider a neuron (or node) j. Denote f j as its activation after nonlinearity and g j as the (input) gradient it receives after filtered by ReLU's gating. Note that both f j and g j are deterministic functions of the input x and label y. Since y is a deterministic function of x, we can write f j = f j (x) and g j = g j (x). Note that all analysis still holds with bias terms. We omit them for brevity.

The activation f j and gradient g k can be written as (note that f j is the binary gating function):

EQUATION

And the weight update for gradient descent is:

EQUATION

Here is the expectation is with respect to a training dataset (or a batch), depending on whether GD or SGD has been used. We also use f raw j and g raw j as the counterpart of f j and g j before nonlinearity.

8.2. MARGINALIZED GRADIENT:

Given the structure of locally connected network, the gradient g j has some nice structures. From Eqn. 17 we knows that

∆w jk = E x [f k (x)g j (x)] = E x k f k (x k )E x -k |x k [g j (x)] . Define x -k =

x\x k as the input image x except for x k . Then we can define the marginalized gradient:

EQUATION

as the marginalization (average) of x -k , while keep x k fixed. With this notation, we can write

∆w jk = E x k [f k (x k )g j (x k )].

On the other hand, the gradient which back-propagates to a node k can be written as

EQUATION

where f k is the derivative of activation function of node k (for ReLU it is just a gating function). If we take expectation with respect to x -k |x k on both side, we get

EQUATION

Note that all marginalized gradients g j (x k ) are independently computed by marginalizing with respect to all regions that are outside the receptive field x k . Interestingly, there is a relationship between these gradients that respects the locality structure: Theorem 1 (Recursive Property of marginalized gradient).

EQUATION

Proof. We have:

g j (x k ) = E x -k |x k [g j (x)] = E x-j ,x j,-k |x k [g j (x)] = E x-j |x j,-k ,x k E x j,-k |x k [g j (x)] = E x-j |xj E x j,-k |x k [g j (x)] = E x j,-k |x k E x-j |xj [g j (x)] = E x j,-k |x k [g j (x j )]

8.3. NETWORK THEOREM:

Theorem 2 (Reformulation). Denote α = rf(j) and β = rf(k). k is a child of j. If the following two conditions hold:

• Focus of knowledge. P(x k |z α , z β ) = P(x k |z β ).

• Broadness of knowledge. P(x j |z α , z β ) = P(x j |z α ).

• Decorrelation. Given z β , (g raw k (•) and f k (•)) and (f raw k (•) and f k (•)) are uncorrelated

Then the following two conditions holds:

EQUATION

EQUATION

Proof. For Eqn. 22a, we have:

f raw j (z α ) = f raw j (x)P(x|z α )dx (23) = f raw j (x j )P(x j |z α )dx j (24) =   k∈ch(j) w jk f k (x k )   P(x j |z α )dx j (25)

And for each of the entry, we have:

EQUATION

For P(x k |z α ), using focus of knowledge, we have:

EQUATION

Therefore, following Eqn. 26, we have:

EQUATION

Putting it back to Eqn. 25 and we have:

EQUATION

For Eqn. 22b, similarly we have:

g raw k (z β ) = g raw k (x)P(x|z β )dx (35) = j∈pa(k)

w jk g j (x)P(x|z β )dx (36)

Notice that we have:

EQUATION

since x j covers x k which determines z β . Therefore, for each item we have: g j (x)P(x|z β )dx = g j (x)P(x j |z β )P(x -j |x j )dx (38) = g j (x)P(x -j |x j )dx -j P(x j |z β )dx j (39) = g j (x j )P(x j |z β )dx j (40)

Then we use the broadness of knowledge:

EQUATION

Following Eqn. 40, we now have:

EQUATION

Putting it back to Eqn. 36 and we have:

EQUATION

Using the definition of g k (z β ):

EQUATION

The un-correlation between g raw k (•) and f k (•) means that

EQUATION

Similarly for f j (z α ).

8.4. EXACTNESS OF REFORMULATION:

The following theorem shows that the reformulation is exact if z α has all information of the region.

Theorem 3. If P(x j |z α ) is a delta function for all α, then the conditions of Thm. 2 hold and the reformulation becomes exact.

Proof. The fact that P(x j |z α ) is a delta function means that there exists a function φ j so that:

EQUATION

That is, z α contains all information of x j (or x α ). Therefore,

• Broadness of knowledge. z α contains strictly more information than z β for β ∈ ch(α), therefore P(x j |z α , z β ) = P(x j |z α ).

• Focus of knowledge. z β captures all information of z k , so P(x k |z α , z β ) = P(x k |z β ).

• Decorrelation. For any h 1 (x j ) and h 2 (x j ) we have

EQUATION

= h 1 (x j )P(x j |z α )dx j h 2 (x j )P(x j |z α )dx j (57)

EQUATION

8.5. MATRIX FORM:

Theorem 4 (Matrix Representation of Reformulation). Proof. We first consider one certain group α and β, which uses x α and x β as the receptive field. For this pair, we can write Eqn. 22 in the following matrix form:

F α = D α • β∈ch(α) P αβ F β W βα , Gβ = D β • α∈pa(β) P T αβ Gα W T βα , ∆W βα = (P αβ F β ) T Gα (59)

F raw α = P αβ F β W βα (60a) F α = F raw α • D α (60b) G raw β = P b αβ T G β W T βα (60c) G β = G raw β • D β (60d)

Using Λ β (P b αβ ) T = P T αβ Λ α and Gα = Λ α G α , we could simplify Eqn. 60 as follows:

EQUATION

Therefore, using the fact that j∈pa(k) = α∈pa(β) j∈α (where β = rf(k)) and k∈ch(j) = β∈ch(α)

k∈β (where α = rf(j)), and group all nodes that share the receptive field together, we have:

F α = D α • β∈ch(α) P αβ F β W βα (62a) Gβ = D β • α∈pa(β) P T αβ Gα W T βα (62b)

For the gradient update rule, from Eqn. 17 notice that:

EQUATION

We assume decorrelation so we have: To achieve that, we first write down the vector form of forward pass of batch normalization:

EQUATION

EQUATION

where f , f , f and f bn are vectors of size N , P ⊥ 1 ≡ I -11 T N is the projection matrix that centers the data, σ

= f uni = 1 √ N f 2 and c ≡ [c 1 , c 0 ] T are the parameters in Batch Normalization and S(f ) ≡ [ f , 1] is the standardized data. Note that S(f ) T S(f ) = N • I 2 (I 2 is 2-by-2 identity matrix)

and thus S(x) is an column-orthogonal N -by-2 matrix. If we put everything together, then we have:

EQUATION

Using this notation, we can compute the Jacobian of batch normalization layer. Specifically, for any vector f , we have:

EQUATION

where P ⊥ f projects a vector into the orthogonal complementary space of f . Therefore we have:

EQUATION

where

P ⊥ f ,1 = I -S(f )S(f ) T N

is a symmetric projection matrix that projects the input gradient to the orthogonal complement space spanned by x and 1 (Fig. 3(b) ). Note that the space spanned by f and 1 is also the space spanned by f and 1, since f = (f -µ1)/σ can be represented linearly by f and 1.

Therefore P ⊥ f ,1 = P ⊥ f ,1 .

An interesting property is that since f bn returns a vector in the subspace of f and 1, for the N -by-N Jacobian matrix of Batch Normalization, we have:

EQUATION

Following the backpropagation rule, we get the following gradient update for batch normalization. If g bn = ∂L/∂ f is the gradient from top, then

EQUATION

Therefore, any gradient (vector of size N ) that is back-propagated to the input of BN layer will be automatically orthogonal to that activation (which is also a vector of size N ).

8.6.1. BATCH NORMALIZATION IN THE REFORMULATION:

The analysis of Batch Norm is compatible with the reformulation and we arrive at similar backpropagation rule, by noticing that E x [f j (x)] = E zα [f j (z α )]:

EQUATION

Note that we still have the projection property, but under the new inner product f j , g j zα =

E zα [f j (z α )g j (z α )] and norm f zα = f, f One can find an interesting quantity, by multiplying g j (x) on both side of the forward equation in Eqn. 16 and taking expectation:

E x [g j f j ] = E x   k∈ch(j) w jk f k g j   = k∈ch(j)

w jk ∆w jk (84)

Using the language of differential equation, we know that:

EQUATION

where E j = 1 2 k∈ch(j) w 2 jk = 1 2 W j• 2 . If we place Batch Normalization layer just after ReLU activation and linear layer, by BN property, since E x [g j f j ] ≡ 0 for all iterations, the row energy E j (t) of weight matrix W of the linear layer is conserved over time. This might be part of the reason why BN helps stabilize the training. Otherwise energy might "leak" from one layer to nearby layers.

With the help of the theoretical framework, we now can analyze interesting structures of gradient descent in deep models, when the data distribution P(z α , z β ) satisfies specific conditions. Here we give two concrete examples: the role played by nonlinearity and in which condition disentangled representation can be achieved. Besides, from the theoretical framework, we also give general comments on multiple issues (e.g., overfitting, GD versus SGD) in deep learning.

In the formulation, m α is the number of possible events within a region α, which is often exponential with respect to the size sz(α) of the region. The following analysis shows that a linear model cannot handle it, even with exponential number of nodes n α , while a nonlinear one with ReLU can. Definition 1 (Convex Hull of a Set). We define the convex hull Conv(P ) of m points P ⊂ R n to be Conv(P ) = P a, a ∈ ∆ n-1 , where ∆ n-1 = {a ∈ R n , a i ≥ 0, i a i = 1}. A row p j is called vertex if p j / ∈ Conv(P \p j ). Definition 2. A matrix P of size m-by-n is called k-vert, or vert(P ) = k ≤ m, if its k rows are vertices of the convex hull generated by its rows. P is called all-vert if k = m. Theorem 6 (Expressibility of ReLU Nonlinearity). Assuming m α = n α = O(exp(sz(α))), where sz(α) is the size of receptive field of α. If each P αβ is all-vert, then: (ω is top-level receptive field) (86)

Here we define Loss(W ) ≡ F ω -I 2 F .

Proof. We prove that in the case of nonlinearity, there exists a weight so that the activation F α = I for all α. We prove by induction. The base case is trivial since we already know that F α = I for all leaf regions.

Suppose F β = I for any β ∈ ch(α). Since P αβ is all-vert, every row is a vertex of the convex hull, which means that for i-th row p i , there exists a weight w i and b i so that w T i p i + b i = 1/|ch(α)| > 0 and w T i p j + b i < 0 for j = i. Put these weights and biases together into W βα and we have In the linear case, we know that rank(F α ) ≤ β rank(P αβ F β W βα ) ≤ β rank(F β ), which is on the order of the size sz(α) of α's receptive field (Note that the constant relies on the overlap between

Note that all analysis still holds with bias terms. We omit them for brevity.

Figures and Tables:

Figure 1: Problem setting. (a) We use Greek letters {α, β, . . . ω} to represent receptive fields.Receptive fields form a hierarchy. The entire input is denoted as x (or x ω ). A local region of an input x is denoted as x α . (b) For each region α, we have a latent multinomial discrete variable z α which is computed from its immediate children {z β } β∈ch(α) . Given the input x, z α = z α (x α ) is a function of the image content x α at α. Finally, z ω at the top level is the class label. (c) A locally connected neural network is trained with pairs (x, z ω (x)), where z ω (x) is the class label generated from the teacher. (d) For each node j, f j (x) is the activation while g j (x) is the back-propagated gradient, both as function of input x (and weights at different layers).

Figure 3: Batch Normalization (BN) as a projection. (a) Add BN by inserting a new node j bn . (b) Forward/backward pass in BN and relevant quantities. (c) The gradient g that is propagated down is a projection of input gradient g bn onto the orthogonal complementary space spanned by {f , 1}.

Figure 4: Disentangled representation. (a) Nodes are grouped according to regions. (b) An example of one parent region α (2 nodes) and two child regions β 1 and β 2 (5 nodes each). We assume factorization property of data distribution P . (c) disentangled activations, (d) Separable weights.

Figure 5: Overfitting Example

Figure 6: Notation used in Thm. 1.

Figure 8: Batch Normalization (BN) as a projection. (a) Add BN by inserting a new node j bn . (b) Forward/backward pass in BN and relevant quantities. (c) The gradient g that is propagated down is a projection of input gradient g bn onto the orthogonal complementary space spanned by {f , 1}.

min W Loss ReLU (W ) = 0, min W Loss Linear (W ) = O(exp(sz(ω)))

αβ F β W βα = β P αβ W βα (87) All diagonal elements of F raw α are 1 while all off-diagonal elements are negative. Therefore, after ReLU, F α = I. Applying induction, we get F ω = I and G ω = I -F ω = 0. Therefore, Loss ReLU (W ) = G ω 2 = 0.

gradient gj (z α ) and gating prob f j (z α ) at group α. W βα n β -by-n α Weight matrix that links group α and β P αβ m α -by-m β Prob P(z β |z α ) of events at group α and β Matrix Notation. See Eqn. 8 and Eqn. 59.

Table content: <table/>

Dimension Description F α , D α m α -by-n α Activation f j (z α ) and gating prob f j (z α ) in group α. G α , Gα m α -by-n α Gradient g j (z α ) and unnormalized gradient gj (z α ) in group α. W βα n β -by-n α Weight matrix that links group β and α. P αβ , P b αβ m α -by-m β Prob P(z β |z α ), P(z α |z β ) of events between group β and α. Λ α m α -by-m α Diagonal matrix encoding prior prob P(z α ).

Table content: <table/>

Matrix Notation. See Eqn. 59.

Table content: <table/>

CONSERVED QUANTITY IN BATCH NORMALIZATION FOR RELU ACTIVATION

Table content: <table><tr><td>8.6.2</td></tr><tr><td>1/2 zα .</td></tr></table>

Peer review (iclr2019):
 The authors propose a framework that utilizes the teacher-student setting to evaluate deep locally connected ReLU network. The framework explicitly formulates data distribution, which has not been considered by previous works. The authors also show that their framework is compatible with Batch Normalization and favors disentangled representation when data distributions have factorizable structures. Based on this framework, the authors re-explain some common issues of deep learning, such as overfitting. My major concerns are as follows. 1. The framework is based on the teacher-student setting, and the authors claim that "the teacher generates classification label via a hidden computational graph". However, how the teacher can be designed is not clear in the paper. 2. The data distribution included in this paper is , where and are all summarization variables. From this perspective, it only has an indirect connection with original data distribution or , and thus it could be questionable whether is a convincing representation. 3. The authors may want to conduct more experiments to better support their claims.