Title: INDUCTIVE BIAS OF DEEP CONVOLUTIONAL NETWORKS THROUGH POOLING GEOMETRY

Abstract: Our formal understanding of the inductive bias that drives the success of convolutional networks on computer vision tasks is limited. In particular, it is unclear what makes hypotheses spaces born from convolution and pooling operations so suitable for natural images. In this paper we study the ability of convolutional networks to model correlations among regions of their input. We theoretically analyze convolutional arithmetic circuits, and empirically validate our findings on other types of convolutional networks as well. Correlations are formalized through the notion of separation rank, which for a given partition of the input, measures how far a function is from being separable. We show that a polynomially sized deep network supports exponentially high separation ranks for certain input partitions, while being limited to polynomial separation ranks for others. The network's pooling geometry effectively determines which input partitions are favored, thus serves as a means for controlling the inductive bias. Contiguous pooling windows as commonly employed in practice favor interleaved partitions over coarse ones, orienting the inductive bias towards the statistics of natural images. Other pooling schemes lead to different preferences, and this allows tailoring the network to data that departs from the usual domain of natural imagery. In addition to analyzing deep networks, we show that shallow ones support only linear separation ranks, and by this gain insight into the benefit of functions brought forth by depth -they are able to efficiently model strong correlation under favored partitions of the input.

1. INTRODUCTION:

A central factor in the application of machine learning to a given task is the inductive bias, i.e. the choice of hypotheses space from which learned functions are taken. The restriction posed by the inductive bias is necessary for practical learning, and reflects prior knowledge regarding the task at hand. Perhaps the most successful exemplar of inductive bias to date manifests itself in the use of convolutional networks (LeCun and Bengio (1995) ) for computer vision tasks. These hypotheses spaces are delivering unprecedented visual recognition results (e.g. Krizhevsky et al. (2012) ; Szegedy et al. (2015) ; Simonyan and Zisserman (2014) ; He et al. (2015) ), largely responsible for the resurgence of deep learning (LeCun et al. (2015) ). Unfortunately, our formal understanding of the inductive bias behind convolutional networks is limited -the assumptions encoded into these models, which seem to form an excellent prior knowledge for imagery data, are for the most part a mystery.

Existing works studying the inductive bias of deep networks (not necessarily convolutional) do so in the context of depth efficiency, essentially arguing that for a given amount of resources, more layers result in higher expressiveness. More precisely, depth efficiency refers to a situation where a function realized by a deep network of polynomial size, requires super-polynomial size in order to be realized (or approximated) by a shallower network. In recent years, a large body of research was devoted to proving existence of depth efficiency under different types of architectures (see for example Delalleau and Bengio (2011) ; Pascanu et al. (2013) ; Montufar et al. (2014) ; Telgarsky (2015) ; Eldan and Shamir (2015) ; Poggio et al. (2015) ; Mhaskar et al. (2016) ). Nonetheless, despite the wide attention it is receiving, depth efficiency does not convey the complete story behind the inductive bias of deep networks. While it does suggest that depth brings forth functions that are otherwise unattainable, it does not explain why these functions are useful. Loosely speaking, the hypotheses space of a polynomially sized deep network covers a small fraction of the space of all functions. We would like to understand why this small fraction is so successful in practice.

A specific family of convolutional networks gaining increased attention is that of convolutional arithmetic circuits. These models follow the standard paradigm of locality, weight sharing and pooling, yet differ from the most conventional convolutional networks in that their point-wise activations are linear, with non-linearity originating from product pooling. Recently, Cohen et al. (2016b) analyzed the depth efficiency of convolutional arithmetic circuits, showing that besides a negligible (zero measure) set, all functions realizable by a deep network require exponential size in order to be realized (or approximated) by a shallow one. This result, termed complete depth efficiency, stands in contrast to previous depth efficiency results, which merely showed existence of functions efficiently realizable by deep networks but not by shallow ones. Besides their analytic advantage, convolutional arithmetic circuits are also showing promising empirical performance. In particular, they are equivalent to SimNets -a deep learning architecture that excels in computationally constrained settings (Cohen and Shashua (2014) ; Cohen et al. (2016a) ), and in addition, have recently been utilized for classification with missing data (Sharir et al. (2016) ). Motivated by these theoretical and practical merits, we focus our analysis in this paper on convolutional arithmetic circuits, viewing them as representative of the class of convolutional networks. We empirically validate our conclusions with both convolutional arithmetic circuits and convolutional rectifier networks -convolutional networks with rectified linear (ReLU, Nair and Hinton (2010) ) activation and max or average pooling. Adaptation of the formal analysis to networks of the latter type, similarly to the adaptation of the analysis in Cohen et al. (2016b) carried out by Cohen and Shashua (2016) , is left for future work.

Our analysis approaches the study of inductive bias from the direction of function inputs. Specifically, we study the ability of convolutional arithmetic circuits to model correlation between regions of their input. To analyze the correlations of a function, we consider different partitions of input regions into disjoint sets, and ask how far the function is from being separable w.r.t. these partitions. Distance from separability is measured through the notion of separation rank (Beylkin and Mohlenkamp (2002) ), which can be viewed as a surrogate of the L 2 distance from the closest separable function. For a given function and partition of its input, high separation rank implies that the function induces strong correlation between sides of the partition, and vice versa.

We show that a deep network supports exponentially high separation ranks for certain input partitions, while being limited to polynomial or linear (in network size) separation ranks for others. The network's pooling geometry effectively determines which input partitions are favored in terms of separation rank, i.e. which partitions enjoy the possibility of exponentially high separation rank with polynomial network size, and which require network to be exponentially large. The standard choice of square contiguous pooling windows favors interleaved (entangled) partitions over coarse ones that divide the input into large distinct areas. Other choices lead to different preferences, for example pooling windows that join together nodes with their spatial reflections lead to favoring partitions that split the input symmetrically. We conclude that in terms of modeled correlations, pooling geometry controls the inductive bias, and the particular design commonly employed in practice orients it towards the statistics of natural images (nearby pixels more correlated than ones that are far apart). Moreover, when processing data that departs from the usual domain of natural imagery, prior knowledge regarding its statistics can be used to derive respective pooling schemes, and accordingly tailor the inductive bias.

With regards to depth efficiency, we show that separation ranks under favored input partitions are exponentially high for all but a negligible set of the functions realizable by a deep network. Shallow networks on the other hand, treat all partitions equally, and support only linear (in network size) separation ranks. Therefore, almost all functions that may be realized by a deep network require a replicating shallow network to have exponential size. By this we return to the complete depth efficiency result of Cohen et al. (2016b) , but with an added important insight into the benefit of functions brought forth by depth -they are able to efficiently model strong correlation under favored partitions of the input.

The remainder of the paper is organized as follows. Sec. 2 provides a brief presentation of necessary background material from the field of tensor analysis. Sec. 3 describes the convolutional arithmetic circuits we analyze, and their relation to tensor decompositions. In sec. 4 we convey the concept of separation rank, on which we base our analyses in sec. 5 and 6. The conclusions from our analyses are empirically validated in sec. 7. Finally, sec. 8 concludes.

2. PRELIMINARIES:

The analyses carried out in this paper rely on concepts and results from the field of tensor analysis. In this section we establish the minimal background required in order to follow our arguments1 , referring the interested reader to Hackbusch (2012) for a broad and comprehensive introduction to the field.

The core concept in tensor analysis is a tensor, which for our purposes may simply be thought of as a multi-dimensional array. The order of a tensor is defined to be the number of indexing entries in the array, which are referred to as modes. The dimension of a tensor in a particular mode is defined as the number of values that may be taken by the index in that mode. For example, a 4-by-3 matrix is a tensor of order 2, i.e. it has two modes, with dimension 4 in mode 1 and dimension 3 in mode 2. If A is a tensor of order N and dimension M i in each mode i ∈ [N ] := {1, . . . , N }, the space of all configurations it can take is denoted, quite naturally, by R . Notice that in the case P = Q = 1, the tensor product reduces to the standard outer product between vectors, i.e. if u ∈ R M1 and v ∈ R M2 , then u ⊗ v is no other than the rank-1 matrix uv ∈ R M1×M2 .

We now introduce the important concept of matricization, which is essentially the rearrangement of a tensor as a matrix. Suppose A is a tensor of order N and dimension M i in each mode i ∈ [N ], and let (I, J) be a partition of [N ], i.e. I and J are disjoint subsets of [N ] whose union gives [N ] . We may write

I = {i 1 , . . . , i |I| } where i 1 < • • • < i |I| , and similarly J = {j 1 , . . . , j |J| } where j 1 < • • • < j |J| . The matricization of A w.r.t. the partition (I, J), denoted A I,J , is the |I| t=1 M it -by- |J| t=1 M jt matrix holding the entries of A such that A d1...d N is placed in row index 1 + |I| t=1 (d it - 1) |I| t =t+1 M i t and column index 1 + |J| t=1 (d jt -1) |J| t =t+1 M j t . If I = ∅ or J = ∅, then by definition A I,J is a row or column (respectively) vector of dimension N t=1 M t holding A d1...d N in entry 1 + N t=1 (d t -1) N t =t+1 M t .

A well known matrix operator is the Kronecker product, which we denote by . For two matrices A ∈ R M1×M2 and B ∈ R N1×N2 , A B is the matrix in R M1N1×M2N2 holding A ij B kl in row index (i -1)N 1 + k and column index (j -1)N 2 + l. Let A and B be tensors of orders P and Q respectively, and let (I, J) be a partition of [P + Q]. The basic relation that binds together the tensor product, the matricization operator, and the Kronecker product, is:

EQUATION

where I -P and J -P are simply the sets obtained by subtracting P from each of the elements in I and J respectively. In words, eq. 1 implies that the matricization of the tensor product between A and B w.r.t. the partition (I, J) of [P + Q], is equal to the Kronecker product between two matricizations: that of A w.r.t. the partition of [P ] induced by the lower values of (I, J), and that of B w.r.t. the partition of [Q] induced by the higher values of (I, J).

3. CONVOLUTIONAL ARITHMETIC CIRCUITS:

The convolutional arithmetic circuit architecture on which we focus in this paper is the one considered in Cohen et al. (2016b) , portrayed in fig. 1 (a) . Instances processed by a network are represented as N -tuples of s-dimensional vectors. They are generally thought of as images, with the s-dimensional vectors corresponding to local patches. For example, instances could be 32-by-32 RGB images, with local patches being 5 × 5 regions crossing the three color bands. In this case, assuming a patch is taken around every pixel in an image (boundaries padded), we have N = 1024 and s = 75. Throughout the paper, we denote a general instance by X = (x 1 , . . . , x N ), with x 1 . . . x N ∈ R s standing for its patches.

   :

,

d i rep i d f   x input representation 1x1 conv pooling 1x1 conv pooling dense (output) hidden layer 0 hidden layer L-1 i x M 0 r 0 r 1 L r  1 L r  Y     0, 0 , , ,: conv j rep j    a     0 0 ' , ', j window j pool j conv j          1 1 ' covers space ', L L j pool conv j           , 1

, :

L y L out y pool   a X (a)     , d i rep i d f   x input representation 1x1 conv global pooling dense (output) hidden layer i x M 0 r 0 r Y     0, , , ,: conv i rep i    a     covers space , i pool conv i         1 ,

, : (c) Illustration of input patch ordering for deep network with 2 × 2 pooling windows, along with patterns induced by the partitions (I odd , J even ) and (I low , J high ) (eq. 8 and 9 respectively).

The first layer in a network is referred to as representation. It consists of applying M representation functions f θ1 . . .f θ M : R s → R to all patches, thereby creating M feature maps. In the case where representation functions are chosen as

f θ d (x) = σ(w d x + b d ), with parameters θ d = (w d , b d ) ∈ R s × R

and some point-wise activation σ(•), the representation layer reduces to a standard convolutional layer. More elaborate settings are also possible, for example modeling the representation as a cascade of convolutional layers with pooling in-between. Following the representation, a network includes L hidden layers indexed by l = 0. . .L -1. Each hidden layer l begins with a 1 × 1 conv operator, which is simply a three-dimensional convolution with r l channels and filters of spatial dimensions 1-by-1. 2 This is followed by spatial pooling, that decimates feature maps by taking products of non-overlapping two-dimensional windows that cover the spatial extent.

The last of the L hidden layers (l = L-1) reduces feature maps to singletons (its pooling operator is global), creating a vector of dimension r L-1 . This vector is mapped into Y network outputs through a final dense linear layer.

Altogether, the architectural parameters of a network are the type of representation functions (f θ d ), the pooling window shapes and sizes (which in turn determine the number of hidden layers L), and the number of channels in each layer (M for representation, r 0 . . .r L-1 for hidden layers, Y for output). Given these architectural parameters, the learnable parameters of a network are the representation weights (θ d for channel d), the conv weights (a l,γ for channel γ of hidden layer l), and the output weights (a L,y for output node y).

For a particular setting of weights, every node (neuron) in a given network realizes a function from (R s ) N to R. The receptive field of a node refers to the indexes of input patches on which its function may depend. For example, the receptive field of node j in channel γ of conv oper-2 Cohen et al. (2016b) consider two settings for the 1 × 1 conv operator. The first, referred to as weight sharing, is the one described above, and corresponds to standard convolution. The second is more general, allowing filters that slide across the previous layer to have different weights at different spatial locations. It is shown in Cohen et al. (2016b) that without weight sharing, a convolutional arithmetic circuit with one hidden layer (or more) is universal, i.e. can realize any function if its size (width) is unbounded. This property is imperative for the study of depth efficiency, as that requires shallow networks to ultimately be able to replicate any function realized by a deep network. In this paper we limit the presentation to networks with weight sharing, which are not universal. We do so because they are more conventional, and since our entire analysis is oblivious to whether or not weights are shared (applies as is to both settings). The only exception is where we reproduce the depth efficiency result of Cohen et al. (2016b) . There, we momentarily consider networks without weight sharing.

ator at hidden layer 0 is {j}, and that of an output node is [N ], corresponding to the entire input. Denote by h (l,γ,j) the function realized by node j of channel γ in conv operator at hidden layer l, and let I (l,γ,j) ⊂ [N ] be its receptive field. By the structure of the network it is evident that I (l,γ,j) does not depend on γ, so we may write I (l,j) instead. Moreover, assuming pooling windows are uniform across channels (as customary with convolutional networks), and taking into account the fact that they do not overlap, we conclude that I (l,j1) and I (l,j2) are necessarily disjoint if j 1 =j 2 . A simple induction over l = 0. . .L -1 then shows that h (l,γ,j) may be expressed as h (l,γ,j) (x i1 , . . . ,

x i T ) = M d1...d T =1 A (l,γ,j) d1...d T T t=1 f θ d t (x it )

, where {i 1 , . . . , i T } stands for the receptive field I (l,j) , and A (l,γ,j) is a tensor of order T = |I (l,j) | and dimension M in each mode, with entries given by polynomials in the network's conv weights {a l,γ } l,γ . Taking the induction one step further (from last hidden layer to network output), we obtain the following expression for functions realized by network outputs:

h y (x 1 , . . . , x N ) = M d1...d N =1 A y d1...d N N i=1 f θ d i (x i ) (2) y ∈ [Y ]

here is an output node index, and h y is the function realized by that node. A y is a tensor of order N and dimension M in each mode, with entries given by polynomials in the network's conv weights {a l,γ } l,γ and output weights a L,y . Hereafter, terms such as function realized by a network or coefficient tensor realized by a network, are to be understood as referring to h y or A y respectively. Next, we present explicit expressions for A y under two canonical networks -deep and shallow.

Deep network. Consider a network as in fig. 1 (a), with pooling windows set to cover four entries each, resulting in L = log 4 N hidden layers. The linear weights of such a network are {a 0,γ ∈ R M } γ∈[r0] for conv operator in hidden layer 0, {a l,γ ∈ R r l-1 } γ∈[r l ] for conv operator in hidden layer l = 1. . .L -1, and {a L,y ∈ R r L-1 } y∈[Y ] for dense output operator. They determine the coefficient tensor A y (eq. 2) through the following recursive decomposition:

EQUATION

a l,γ α and a L,y α here are scalars representing entry α in the vectors a l,γ and a L,y respectively, and the symbol ⊗ with a superscript stands for a repeated tensor product, e.g. ⊗ 4 a 0,α := a 0,α ⊗a 0,α ⊗a 0,α ⊗ a 0,α . To verify that under pooling windows of size four A y is indeed given by eq. 3, simply plug the rows of the decomposition into eq. 2, starting from bottom and continuing upwards. For context, eq. 3 describes what is known as a hierarchical tensor decomposition (see chapter 11 in Hackbusch (2012)), with underlying tree over modes being a full quad-tree (corresponding to the fact that the network's pooling windows cover four entries each).

Shallow network. The second network we pay special attention to is shallow, comprising a single hidden layer with global pooling -see illustration in fig. 1(b ). The linear weights of such a network are {a 0,γ ∈ R M } γ∈[r0] for hidden conv operator and {a 1,y ∈ R r0 } y∈[Y ] for dense output operator. They determine the coefficient tensor A y (eq. 2) as follows:

EQUATION

where a 1,y γ stands for entry γ of a 1,y , and again, the symbol ⊗ with a superscript represents a repeated tensor product. The tensor decomposition in eq. 4 is an instance of the classic CP decomposition, also known as rank-1 decomposition (see Kolda and Bader (2009) for a historic survey).

To conclude this section, we relate the background material above, as well as our contribution described in the upcoming sections, to the work of Cohen et al. (2016b) . The latter shows that with arbitrary coefficient tensors A y , functions h y as in eq. 2 form a universal hypotheses space. It is then shown that convolutional arithmetic circuits as in fig. 1 (a) realize such functions by applying tensor decompositions to A y , with the type of decomposition determined by the structure of a network (number of layers, number of channels in each layer etc.). The deep network (fig. 1 (a) with size-4 pooling windows and L = log 4 N hidden layers) and the shallow network (fig. 1(b) ) presented hereinabove are two special cases, whose corresponding tensor decompositions are given in eq. 3 and 4 respectively. The central result in Cohen et al. (2016b) relates to inductive bias through the notion of depth efficiency -it is shown that in the parameter space of a deep network, all weight settings but a set of (Lebesgue) measure zero give rise to functions that can only be realized (or approximated) by a shallow network if the latter has exponential size. This result does not relate to the characteristics of instances X = (x 1 , . . . , x N ), it only treats the ability of shallow networks to replicate functions realized by deep networks.

In this paper we draw a line connecting the inductive bias to the nature of X, by studying the relation between a network's architecture and its ability to model correlation among patches x i . Specifically, in sec. 4 we consider partitions (I,

J) of [N ] (I • ∪J = [N ]

, where • ∪ stands for disjoint union), and present the notion of separation rank as a measure of the correlation modeled between the patches indexed by I and those indexed by J. In sec. 5.1 the separation rank of a network's function h y w.r.t. a partition (I, J) is proven to be equal to the rank of A y I,J -the matricization of the coefficient tensor A y w.r.t. (I, J). Sec. 5.2 derives lower and upper bounds on this rank for a deep network, showing that it supports exponential separation ranks with polynomial size for certain partitions, whereas for others it is required to be exponentially large. Subsequently, sec. 5.3 establishes an upper bound on rank A y I,J for shallow networks, implying that these must be exponentially large in order to model exponential separation rank under any partition, and thus cannot efficiently replicate a deep network's correlations. Our analysis concludes in sec. 6, where we discuss the pooling geometry of a deep network as a means for controlling the inductive bias by determining a correspondence between partitions (I, J) and spatial partitions of the input. Finally, we demonstrate experimentally in sec. 7 how different pooling geometries lead to superior performance in different tasks. Our experiments include not only convolutional arithmetic circuits, but also convolutional rectifier networks, i.e. convolutional networks with ReLU activation and max or average pooling.

4. SEPARATION RANK:

In this section we define the concept of separation rank for functions realized by convolutional arithmetic circuits (sec. 3), i.e. real functions that take as input X = (x 1 , . . . , x N ) ∈ (R s ) N . The separation rank serves as a measure of the correlations such functions induce between different sets of input patches, i.e. different subsets of the variable set {x 1 , . . . , x N }.

Let (I, J) be a partition of input indexes, i.e. I and J are disjoint subsets of [N ] whose union gives [N ] . We may write

I = {i 1 , . . . , i |I| } where i 1 < • • • < i |I| , and similarly J = {j 1 , . . . , j |J| } where j 1 < • • • < j |J| . For a function h : (R s ) N → R, the separation rank w.r.t. the partition (I, J) is defined as follows: 3 sep(h; I, J) := min R ∈ N ∪ {0} : ∃g 1 . . .g R : (R s ) |I| → R, g 1 . . .g R : (R s ) |J| → R s.t.

(5)

h(x 1 , . . . , x N ) = R ν=1 g ν (x i1 , . . . , x i |I| )g ν (x j1 , . . . , x j |J| )

In words, it is the minimal number of summands that together give h, where each summand is separable w.r.t. (I, J), i.e. is equal to a product of two functions -one that intakes only patches indexed by I, and another that intakes only patches indexed by J. One may wonder if it is at all possible to express h through such summands, i.e. if the separation rank of h is finite. From the theory of tensor products between L 2 spaces (see Hackbusch (2012) for a comprehensive coverage), we know that any h∈L 2 ((R s ) N ), i.e. any h that is measurable and square-integrable, may be approximated arbitrarily well by summations of the form R ν=1 g ν (x i1 , . . . , x i |I| )g ν (x j1 , . . . , x j |J| ). Exact realization however is only guaranteed at the limit R → ∞, thus in general the separation rank of h need not be finite. Nonetheless, as we show in sec. 5, for the class of functions we are interested in, namely functions realizable by convolutional arithmetic circuits, separation ranks are always finite.

The concept of separation rank was introduced in Beylkin and Mohlenkamp (2002) for numerical treatment of high-dimensional functions, and has since been employed for various applications, e.g. quantum chemistry (Harrison et al. (2003) ), particle engineering (Hackbusch (2006) ) and machine learning (Beylkin et al. (2009) ). If the separation rank of a function w.r.t. a partition of its input is equal to 1, the function is separable, meaning it does not model any interaction between the sets of variables. Specifically, if sep(h; I, J) = 1 then there exist g : (R s ) |I| → R and g : (R s ) |J| → R such that h(x 1 , . . . , x N ) = g(x i1 , . . . , x i |I| )g (x j1 , . . . , x j |J| ), and the function h cannot take into account consistency between the values of {x i1 , . . . , x i |I| } and those of {x j1 , . . . , x j |J| }. In a statistical setting, if h is a probability density function, this would mean that {x i1 , . . . , x i |I| } and {x j1 , . . . , x j |J| } are statistically independent. The higher sep(h; I, J) is, the farther h is from this situation, i.e. the more it models dependency between {x i1 , . . . , x i |I| } and {x j1 , . . . , x j |J| }, or equivalently, the stronger the correlation it induces between the patches indexed by I and those indexed by J.

The interpretation of separation rank as a measure of deviation from separability is formalized in app. B, where it is shown that sep(h; I, J) is closely related to the L 2 distance of h from the set of separable functions w.r.t. (I, J). Specifically, we define D(h; I, J) as the latter distance divided by the L 2 norm of h4 , and show that sep(h; I, J) provides an upper bound on D(h; I, J). While it is not possible to lay out a general lower bound on D(h; I, J) in terms of sep(h; I, J), we show that the specific lower bounds on sep(h; I, J) underlying our analyses can be translated into lower bounds on D(h; I, J). This implies that our results, facilitated by upper and lower bounds on separation ranks of convolutional arithmetic circuits, may equivalently be framed in terms of L 2 distances from separable functions.

5. CORRELATION ANALYSIS:

In this section we analyze convolutional arithmetic circuits (sec. 3) in terms of the correlations they can model between sides of different input partitions, i.e. in terms of the separation ranks (sec. 4) they support under different partitions (I, J) of [N ]. We begin in sec. 5.1, establishing a correspondence between separation ranks and coefficient tensor matricization ranks. This correspondence is then used in sec. 5.2 and 5.3 to analyze the deep and shallow networks (respectively) presented in sec. 3. We note that we focus on these particular networks merely for simplicity of presentation -the analysis can easily be adapted to account for alternative networks with different depths and pooling schemes.

5.1. FROM SEPARATION RANK TO MATRICIZATION RANK:

Let h y be a function realized by a convolutional arithmetic circuit, with corresponding coefficient tensor A y (eq. 2). Denote by (I, J) an arbitrary partition of

[N ], i.e. I • ∪J = [N ].

We are interested in studying sep(h y ; I, J) -the separation rank of h y w.r.t. (I, J) (eq. 5). As claim 1 below states, assuming representation functions {f θ d } d∈[M ] are linearly independent (if they are not, we drop dependent functions and modify A y accordingly5 ), this separation rank is equal to the rank of A y I,J -the matricization of the coefficient tensor A y w.r.t. the partition (I, J). Our problem thus translates to studying ranks of matricized coefficient tensors.

Claim 1. Let h y be a function realized by a convolutional arithmetic circuit (fig. 1(a) ), with corresponding coefficient tensor A y (eq. 2). Assume that the network's representation functions f θ d are linearly independent, and that they, as well as the functions g ν , g ν in the definition of separation rank (eq. 5), are measurable and square-integrable.6 Then, for any partition (I, J) of [N ], it holds that sep(h y ; I, J) = rank A y I,J .

Proof. See app. A.1.

As the linear weights of a network vary, so do the coefficient tensors (A y ) it gives rise to. Accordingly, for a particular partition (I, J), a network does not correspond to a single value of rank A y I,J , but rather supports a range of values. We analyze this range by quantifying its maximum, which reflects the strongest correlation that the network can model between the input patches indexed by I and those indexed by J. One may wonder if the maximal value of rank A y I,J is the appropriate statistic to measure, as a-priori, it may be that rank A y I,J is maximal for very few of the network's weight settings, and much lower for all the rest. Apparently, as claim 2 below states, this is not the case, and in fact rank A y I,J is maximal under almost all of the network's weight settings. Claim 2. Consider a convolutional arithmetic circuit (fig. 1(a) ) with corresponding coefficient tensor A y (eq. 2). A y depends on the network's linear weights -{a l,γ } l,γ and a L,y , thus for a given partition (I, J) of [N ], rank A y I,J is a function of these weights. This function obtains its maximum almost everywhere (w.r.t. Lebesgue measure).

Proof. See app. A.2.

5.2. DEEP NETWORK:

In this subsection we study correlations modeled by the deep network presented in sec. 3 (fig. 1(a) with size-4 pooling windows and L = log 4 N hidden layers). In accordance with sec. 5.1, we do so by characterizing the maximal ranks of coefficient tensor matricizations under different partitions.

Recall from eq. 3 the hierarchical decomposition expressing a coefficient tensor A y realized by the deep network. We are interested in matricizations of this tensor under different partitions of [N ] . Let (I, J) be an arbitrary partition, i.e.

I • ∪J = [N ].

Matricizing the last level of eq. 3 w.r.t. (I, J), while applying the relation in eq. 1, gives:

A y I,J = r L-1 α=1 a L,y α • φ L-1,α ⊗ φ L-1,α ⊗ φ L-1,α ⊗ φ L-1,α I,J = r L-1 α=1 a L,y α • φ L-1,α ⊗ φ L-1,α I∩[2•4 L-1 ],J∩[2•4 L-1 ] φ L-1,α ⊗ φ L-1,α (I-2•4 L-1 )∩[2•4 L-1 ],(J-2•4 L-1 )∩[2•4 L-1 ]

Applying eq. 1 again, this time to matricizations of the tensor φ L-1,α ⊗ φ L-1,α , we obtain:

A y I,J = r L-1 α=1 a L,y α • φ L-1,α I∩[4 L-1 ],J∩[4 L-1 ] φ L-1,α (I-4 L-1 )∩[4 L-1 ],(J-4 L-1 )∩[4 L-1 ] φ L-1,α (I-2•4 L-1 )∩[4 L-1 ],(J-2•4 L-1 )∩[4 L-1 ] φ L-1,α (I-3•4 L-1 )∩[4 L-1 ],(J-3•4 L-1 )∩[4 L-1 ] For every k ∈ [4] define I L-1,k := (I -(k -1)•4 L-1 )∩[4 L-1 ] and J L-1,k := (J -(k -1)•4 L-1 )∩ [4 L-1 ]. In words, (I L-1,k , J L-1,k

) represents the partition induced by (I, J) on the k'th quadrant of [N ], i.e. on the k'th size-4 L-1 group of input patches. We now have the following matricized version of the last level in eq. 3:

A y I,J = r L-1 α=1 a L,y α • 4 t=1 φ L-1,α I L-1,t ,J L-1,t

where the symbol with a running index stands for an iterative Kronecker product. To derive analogous matricized versions for the upper levels of eq. 3, we define for l ∈ {0. .

.L -1}, k ∈ [N/4 l ]: I l,k := (I -(k -1) • 4 l ) ∩ [4 l ] J l,k := (J -(k -1) • 4 l ) ∩ [4 l ]

(6) That is to say, (I l,k , J l,k ) represents the partition induced by (I, J) on the set of indexes {(k -1) • 4 l + 1, . . . , k • 4 l }, i.e. on the k'th size-4 l group of input patches. With this notation in hand, traversing upwards through the levels of eq. 3, with repeated application of the relation in eq. 1, one arrives at the following matrix decomposition for A y I,J :

EQUATION

Eq. 7 expresses A y I,J -the matricization w.r.t. the partition (I, J) of a coefficient tensor A y realized by the deep network, in terms of the network's conv weights {a l,γ } l,γ and output weights a L,y . As discussed above, our interest lies in the maximal rank that this matricization can take. Theorem 1 below provides lower and upper bounds on this maximal rank, by making use of eq. 7, and of the rank-multiplicative property of the Kronecker product (rank(A B) = rank(A)•rank(B)). Theorem 1. Let (I, J) be a partition of [N ], and A y I,J be the matricization w.r.t. (I, J) of a coefficient tensor A y (eq. 2) realized by the deep network (fig. 1 (a) with size-4 pooling windows). For every l ∈ {0. . .L -1} and k ∈ [N/4 l ], define I l,k and J l,k as in eq. 6. Then, the maximal rank that A y I,J can take (when network weights vary) is:

• No smaller than min{r 0 , M } S , where S := |{k ∈ [N/4] :

I 1,k = ∅ ∧ J 1,k = ∅}|.

• No greater than min{M min{|I|,|J|} , r L-1

4 t=1 c L-1,t }, where c 0,k := 1 for k ∈ [N ], and c l,k := min{M min{|I l,k |,|J l,k |} , r l-1 4 t=1 c l-1,4(k-1)+t } for l ∈ [L -1], k ∈ [N/4 l ].

Proof. See app. A.3.

The lower bound in theorem 1 is exponential in S, the latter defined to be the number of size-4 patch groups that are split by the partition (I, J), i.e. whose indexes are divided between I and J. Partitions that split many of the size-4 patch groups will thus lead to a large lower bound. For example, consider the partition (I odd , J even ) defined as follows:

EQUATION

This partition splits all size-4 patch groups (S = N/4), leading to a lower bound that is exponential in the number of patches (N ).

The upper bound in theorem 1 is expressed via constants c l,k , defined recursively over levels l = 0. . .L -1, with k ranging over 1. . .N/4 l for each level l. What prevents c l,k from growing double-exponentially fast (w.r.t. l) is the minimization with

M min{|I l,k |,|J l,k |} . Specifically, if min{|I l,k | , |J l,k |} is small, i.e.

if the partition induced by (I, J) on the k'th size-4 l group of patches is unbalanced (most of the patches belong to one side of the partition, and only a few belong to the other), c l,k will be of reasonable size. The higher this takes place in the hierarchy (i.e. the larger l is), the lower our eventual upper bound will be. In other words, if partitions induced by (I, J) on size-4 l patch groups are unbalanced for large values of l, the upper bound in theorem 1 will be small. For example, consider the partition (I low , J high ) defined by:

EQUATION

Under (I low , J high ), all partitions induced on size-4 L-1 patch groups (quadrants of

[N ]) are com- pletely one-sided (min{|I L-1,k |, |J L-1,k |} = 0 for all k ∈ [4]

), resulting in the upper bound being no greater than r L-1 -linear in network size.

To summarize this discussion, theorem 1 states that with the deep network, the maximal rank of a coefficient tensor matricization w.r.t. (I, J), highly depends on the nature of the partition (I, J) -it will be exponentially high for partitions such as (I odd , J even ), that split many size-4 patch groups, while being only polynomial (or linear) for partitions like (I low , J high ), under which size-4 l patch groups are unevenly divided for large values of l. Since the rank of a coefficient tensor matricization w.r.t. (I, J) corresponds to the strength of correlation modeled between input patches indexed by I and those indexed by J (sec. 5.1), we conclude that the ability of a polynomially sized deep network to model correlation between sets of input patches highly depends on the nature of these sets.

5.3. SHALLOW NETWORK:

We now turn to study correlations modeled by the shallow network presented in sec. 3 (fig. 1(b) ).

In line with sec. 5.1, this is achieved by characterizing the maximal ranks of coefficient tensor matricizations under different partitions.

Recall from eq. 4 the CP decomposition expressing a coefficient tensor A y realized by the shallow network. For an arbitrary partition (I, J) of [N ], i.e. I • ∪J = [N ], matricizing this decomposition with repeated application of the relation in eq. 1, gives the following expression for A y I,J -the matricization w.r.t. (I, J) of a coefficient tensor realized by the shallow network:

EQUATION

|I| a 0,γ and |J| a 0,γ here are column vectors of dimensions M |I| and M |J| respectively, standing for the Kronecker products of a 0,γ ∈ R M with itself |I| and |J| times (respectively). Eq. 10 immediately leads to two observations regarding the ranks that may be taken by A y I,J . First, they depend on the partition (I, J) only through its division size, i.e. through |I| and |J|. Second, they are no greater than min{M min{|I|,|J|} , r 0 }, meaning that the maximal rank is linear (or less) in network size. In light of sec. 5.1 and 5.2, these findings imply that in contrast to the deep network, which with polynomial size supports exponential separation ranks under favored partitions, the shallow network treats all partitions (of a given division size) equally, and can only give rise to an exponential separation rank if its size is exponential.

Suppose now that we would like to use the shallow network to replicate a function realized by a polynomially sized deep network. So long as the deep network's function admits an exponential separation rank under at least one of the favored partitions (e.g. (I odd , J even ) -eq. 8), the shallow network would have to be exponentially large in order to replicate it, i.e. depth efficiency takes place.7 Since all but a negligible set of the functions realizable by the deep network give rise to maximal separation ranks (sec 5.1), we obtain the complete depth efficiency result of Cohen et al. (2016b) . However, unlike Cohen et al. (2016b) , which did not provide any explanation for the usefulness of functions brought forth by depth, we obtain an insight into their utility -they are able to efficiently model strong correlation under favored partitions of the input.

6. INDUCTIVE BIAS THROUGH POOLING GEOMETRY:

The deep network presented in sec. 3, whose correlations we analyzed in sec. 5.2, was defined as having size-4 pooling windows, i.e. pooling windows covering four entries each. We have yet to specify the shapes of these windows, or equivalently, the spatial (two-dimensional) locations of nodes grouped together in the process of pooling. In compliance with standard convolutional network design, we now assume that the network's (size-4) pooling windows are contiguous square blocks, i.e. have shape 2 × 2. Under this configuration, the network's functional description (eq. 2 with A y given by eq. 3) induces a spatial ordering of input patches 8 , which may be described by the following recursive process:

• Set the index of the top-left patch to 1.

• For l = 1, . . ., L = log 4 N : Replicate the already-assigned top-left 2 l-1 -by-2 l-1 block of indexes, and place copies on its right, bottom-right and bottom. Then, add a 4 l-1 offset to all indexes in the right copy, a 2 • 4 l-1 offset to all indexes in the bottom-right copy, and a 3 • 4 l-1 offset to all indexes in the bottom copy.

With this spatial ordering (illustrated in fig. 1(c )), partitions (I, J) of [N ] convey a spatial pattern.

For example, the partition (I odd , J even ) (eq. 8) corresponds to the pattern illustrated on the left of fig. 1(c ), whereas (I low , J high ) (eq. 9) corresponds to the pattern illustrated on the right. Our analysis (sec. 5.2) shows that the deep network is able to model strong correlation under (I odd , J even ), while being inefficient for modeling correlation under (I low , J high ). More generally, partitions for which S, defined in theorem 1, is high, convey patterns that split many 2 × 2 patch blocks, i.e. are highly entangled. These partitions enjoy the possibility of strong correlation. On the other hand, partitions for which min{|I l,k | , |J l,k |} is small for large values of l (see eq. 6 for definition of I l,k and J l,k ) convey patterns that divide large 2 l × 2 l patch blocks unevenly, i.e. separate the input to distinct contiguous regions. These partitions, as we have seen, suffer from limited low correlations.

We conclude that with 2 × 2 pooling, the deep network is able to model strong correlation between input regions that are highly entangled, at the expense of being inefficient for modeling correlation between input regions that are far apart. Had we selected a different pooling regime, the preference of input partition patterns in terms of modeled correlation would change. For example, if pooling windows were set to group nodes with their spatial reflections (horizontal, vertical and horizontalvertical), coarse patterns that divide the input symmetrically, such as the one illustrated on the right of fig. 1(c ), would enjoy the possibility of strong correlation, whereas many entangled patterns would now suffer from limited low correlation. The choice of pooling shapes thus serves as a means for controlling the inductive bias in terms of correlations modeled between input regions. Square contiguous windows, as commonly employed in practice, lead to a preference that complies with our intuition regarding the statistics of natural images (nearby pixels more correlated than distant ones). Other pooling schemes lead to different preferences, and this allows tailoring a network to data that departs from the usual domain of natural imagery. We demonstrate this experimentally in the next section, where it is shown how different pooling geometries lead to superior performance in different tasks.

7. EXPERIMENTS:

The main conclusion from our analyses (sec. 5 and 6) is that the pooling geometry of a deep convolutional network controls its inductive bias by determining which correlations between input regions can be modeled efficiently. We have also seen that shallow networks cannot model correlations efficiently, regardless of the considered input regions. In this section we validate these assertions empirically, not only with convolutional arithmetic circuits (subject of our analyses), but also with convolutional rectifier networks -convolutional networks with ReLU activation and max or average pooling. For conciseness, we defer to app. C some details regarding our implementation. The latter is fully available online at https://github.com/HUJI-Deep/inductive-pooling.

8 The network's functional description assumes a one-dimensional full quad-tree grouping of input patch indexes. That is to say, it assumes that in the first pooling operation (hidden layer 0), the nodes corresponding to patches x1, x2, x3, x4 are pooled into one group, those corresponding to x5, x6, x7, x8 are pooled into another, and so forth. Similar assumptions hold for the deeper layers. For example, in the second pooling operation (hidden layer 1), the node with receptive field {1, 2, 3, 4}, i.e. the one corresponding to the quadruple of patches {x1, x2, x3, x4}, is assumed to be pooled together with the nodes whose receptive fields are {5, 6, 7, 8}, {9, 10, 11, 12} and {13, 14, 15, 16}. In each task, the objective is to distinguish between blobs whose respective property (closedness/symmetry) is high, and ones for which it is low. The tasks differ in nature -closedness requires modeling correlations between neighboring pixels, whereas symmetry requires modeling correlations between pixels and their reflections.

Our experiments are based on a synthetic classification benchmark inspired by medical imaging tasks. Instances to be classified are 32-by-32 binary images, each displaying a random distorted oval shape (blob) with missing pixels in its interior (holes). For each image, two continuous scores in range [0, 1] are computed. The first, referred to as closedness, reflects how morphologically closed a blob is, and is defined to be the ratio between the number of pixels in the blob, and the number of pixels in its closure (see app. D for exact definition of the latter). The second score, named symmetry, reflects the degree to which a blob is left-right symmetric about its center. It is measured by cropping the bounding box around a blob, applying a left-right flip to the latter, and computing the ratio between the number of pixels in the intersection of the blob and its reflection, and the number of pixels in the blob. To generate labeled sets for classification (train and test), we render multiple images, sort them according to their closedness and symmetry, and for each of the two scores, assign the label "high" to the top 40% and the label "low" to the bottom 40% (the mid 20% are considered ill-defined). This creates two binary (two-class) classification tasks -one for closedness and one for symmetry (see fig. 2 for a sample of images participating in both tasks). Given that closedness is a property of a local nature, we expect its classification task to require a predictor to be able to model strong correlations between neighboring pixels. Symmetry on the other hand is a property that relates pixels to their reflections, thus we expect its classification task to demand that a predictor be able to model correlations across distances.

We evaluated the deep convolutional arithmetic circuit considered throughout the paper (fig. 1(a) with size-4 pooling windows) under two different pooling geometries. The first, referred to as square, comprises standard 2 × 2 pooling windows. The second, dubbed mirror, pools together nodes with their horizontal, vertical and horizontal-vertical reflections. In both cases, input patches (x i ) were set as individual pixels, resulting in N = 1024 patches and L = log 4 N = 5 hidden layers. M = 2 representation functions (f θ d ) were fixed, the first realizing the identity on binary inputs (f θ1 (b) = b for b ∈ {0, 1}), and the second realizing negation (f θ2 (b) = 1 -b for b ∈ {0, 1}). Classification was realized through Y = 2 network outputs, with prediction following the stronger activation. The number of channels across all hidden layers was uniform, and varied between 8 and 128. Fig. 3 shows the results of applying the deep network with both square and mirror pooling, to both closedness and symmetry tasks, where each of the latter has 20000 images for training and 4000 images for testing. As can be seen in the figure, square pooling significantly outperforms mirror pooling in closedness classification, whereas the opposite occurs in symmetry classification. This complies with our discussion in sec. 6, according to which square pooling supports modeling correlations between entangled (neighboring) regions of the input, whereas mirror pooling puts focus on correlations between input regions that are symmetric w.r.t. one another. We thus obtain a demonstration of how prior knowledge regarding a task at hand may be used to tailor the inductive bias of a deep convolutional network by designing an appropriate pooling geometry.

In addition to the deep network, we also evaluated the shallow convolutional arithmetic circuit analyzed in the paper (fig. 1(b) ). The architectural choices for this network were the same as those 

Deep convolutional arithmetic circuit:

Figure 3 : Results of applying a deep convolutional arithmetic circuit to closedness and symmetry classification tasks. Two pooling geometries were evaluated -square, which supports modeling correlations between neighboring input regions, and mirror, which puts focus on correlations between regions that are symmetric w.r.t. one another. Each pooling geometry outperforms the other on the task for which its correlations are important, demonstrating how prior knowledge regarding a task at hand may be used to tailor the inductive bias through proper pooling design.

described above for the deep network besides the number of hidden channels, which in this case applied to the network's single hidden layer, and varied between 64 and 4096. The highest train and test accuracies delivered by this network (with 4096 hidden channels) were roughly 62% on closedness task, and 77% on symmetry task. The fact that these accuracies are inferior to those of the deep network, even when the latter's pooling geometry is not optimal for the task at hand, complies with our analysis in sec. 5. Namely, it complies with the observation that separation ranks (correlations) are sometimes exponential and sometimes polynomial with the deep network, whereas with the shallow one they are never more than linear in network size.

Finally, to assess the validity of our findings for convolutional networks in general, not just convolutional arithmetic circuits, we repeated the above experiments with convolutional rectifier networks. Namely, we placed ReLU activations after every conv operator, switched the pooling operation from product to average, and re-evaluated the deep (square and mirror pooling geometries) and shallow networks. We then reiterated this process once more, with pooling operation set to max instead of average. The results obtained by the deep networks are presented in fig. 4 . The shallow network with average pooling reached train/test accuracies of roughly 58% on closedness task, and 55% on symmetry task. With max pooling, performance of the shallow network did not exceed chance. Altogether, convolutional rectifier networks exhibit the same phenomena observed with convolutional arithmetic circuits, indicating that the conclusions from our analyses likely apply to such networks as well. Formal adaptation of the analyses to convolutional rectifier networks, similarly to the adaptation of Cohen et al. (2016b) carried out in Cohen and Shashua (2016) , is left for future work.

8. DISCUSSION:

Through the notion of separation rank, we studied the relation between the architecture of a convolutional network, and its ability to model correlations among input regions. For a given input partition, the separation rank quantifies how far a function is from separability, which in a probabilistic setting, corresponds to statistical independence between sides of the partition.

Our analysis shows that a polynomially sized deep convolutional arithmetic circuit supports exponentially high separation ranks for certain input partitions, while being limited to polynomial or linear (in network size) separation ranks for others. The network's pooling window shapes effectively determine which input partitions are favored in terms of separation rank, i.e. which partitions enjoy the possibility of exponentially high separation ranks with polynomial network size, and which require network to be exponentially large. Pooling geometry thus serves as a means for controlling the inductive bias. The particular pooling scheme commonly employed in practice -square contiguous windows, favors interleaved partitions over ones that divide the input to distinct areas, thus orients the inductive bias towards the statistics of natural images (nearby pixels more correlated than distant ones). Other pooling schemes lead to different preferences, and this allows tailoring the network to data that departs from the usual domain of natural imagery.

As opposed to deep convolutional arithmetic circuits, shallow ones support only linear (in network size) separation ranks. Therefore, in order to replicate a function realized by a deep network (exponential separation rank), a shallow network must be exponentially large. By this we derive the depth efficiency result of Cohen et al. (2016b) , but in addition, provide an insight into the benefit of functions brought forth by depth -they are able to efficiently model strong correlation under favored partitions of the input.

We validated our conclusions empirically, with convolutional arithmetic circuits as well as convolutional rectifier networks -convolutional networks with ReLU activation and max or average pooling.

Our experiments demonstrate how different pooling geometries lead to superior performance in different tasks. Specifically, we evaluate deep networks in the measurement of shape continuity, a task of a local nature, and show that standard square pooling windows outperform ones that join together nodes with their spatial reflections. In contrast, when measuring shape symmetry, modeling correlations across distances is of vital importance, and the latter pooling geometry is superior to the conventional one. Shallow networks are inefficient at modeling correlations of any kind, and indeed lead to poor performance on both tasks.

Finally, our analyses and results bring forth the possibility of expanding the coverage of correlations efficiently modeled by a deep convolutional network. Specifically, by blending together multiple pooling geometries in the hidden layers of a network, it is possible to facilitate simultaneous support for a wide variety of correlations suiting data of different types. Investigation of this direction, from both theoretical and empirical perspectives, is viewed as a promising avenue for future research.

A DEFERRED PROOFS

A.1 PROOF OF CLAIM 1:

We prove the equality in two steps, first showing that sep(hy; I, J)≤rank A y I,J , and then establishing the converse. The first step is elementary, and does not make use of the representation functions' (f θ d ) linear independence, or of measurability/square-integrability. The second step does rely on these assumptions, and employs slightly more advanced mathematical machinery. Throughout the proof, we assume without loss of generality that the partition (I, J) of [N ] is such that I takes on lower values, while J takes on higher ones. That is to say, we assume that I = {1, . . . , |I|} and J = {|I| + 1, . . . , N }. 9

To prove that sep(hy; I, J)≤rank A y I,J , denote by R the rank of A y I,J . The latter is an M |I| -by-M |J| matrix, thus there exist vectors u1.

. .uR ∈ R M |I| and v1. . .vR ∈ R M |J| such that A y I,J = R ν=1 uν v ν . For every ν ∈ [R]

, let B ν be the tensor of order |I| and dimension M in each mode whose arrangement as a column vector gives uν , i.e. whose matricization w.r.t. the partition

([|I|], ∅) is equal to uν . Similarly, let C ν , ν ∈ [R],

be the tensor of order |J| = N -|I| and dimension M in each mode whose matricization w.r.t. the partition (∅, [|J|] ) (arrangement as a row vector) is equal to v ν . It holds that:

A y I,J = R ν=1 uν v ν = R ν=1 B ν [|I|],∅ C ν ∅,[|J|] = R ν=1 B ν I∩[|I|],J∩[|I|] C ν (I-|I|)∩[|J|],(J-|I|)∩[|J|] = R ν=1 B ν ⊗ C ν I,J = R ν=1 B ν ⊗ C ν I,J

where the third equality relies on the assumption I = {1, . . . , |I|}, J = {|I| + 1, . . . , N }, the fourth equality makes use of the relation in eq. 1, and the last equality is based on the linearity of the matricization operator. Since matricizations are merely rearrangements of tensors, the fact that

A y I,J = R ν=1 B ν ⊗C ν I,J implies A y = R ν=1 B ν ⊗ C ν , or equivalently, A y d 1 ...d N = R ν=1 B ν d 1 ...d |I| • C ν d |I|+1 ...d N for every d1. . .dN ∈ [M ]

. Plugging this into eq. 2 gives:

EQUATION

For every ν ∈ [R], define the functions gν : (R s ) |I| → R and g ν : (R s ) |J| → R as follows:

gν (x1, . . . , x |I| ) := M d 1 ...d |I| =1 B ν d 1 ...d |I| |I| i=1 f θ d i (xi) g ν (x1, . . . , x |J| ) := M d 1 ...d |J| =1 C ν d 1 ...d |J| |J| i=1 f θ d i (xi)

9 To see that this does not limit generality, denote I = {i1, . . . , i |I| } and J = {j1, . . . , j |J| }, and define an auxiliary function h y by permuting the entries of hy such that those indexed by I are on the left and those indexed by J on the right, i. ) is equivalent to matricizing A y w.r.t. (I, J), i.e. A y I ,J = A y I,J , and in particular rank A y I ,J = rank A y I,J . Moreover, since by definition A y is a coefficient tensor corresponding to hy (eq. 2), A y will be a coefficient tensor that corresponds to h y . Now, our proof will show that sep(h y ; I , J ) = rank A y I ,J , which, in light of the equalities above, implies sep(hy; I, J) = rank A y I,J , as required.

Substituting these into eq. 11 leads to:

hy (x1, . . . , xN ) = R ν=1 gν (x1, . . . , x |I| )g ν (x |I|+1 , . . . , xN )

which by definition of the separation rank (eq. 5), implies sep(hy; I, J)≤R. By this we have shown that sep(hy; I, J)≤rank A y I,J , as required.

For proving the converse inequality, i.e. sep(hy; I, J)≥rank A y I,J , we rely on basic concepts and results from functional analysis, or more specifically, from the topic of L 2 spaces. While a full introduction to this topic is beyond our scope (the interested reader is referred to Rudin (1991) ), we briefly lay out here the minimal background required in order to follow our proof. For any n ∈ N, L 2 (R n ) is formally defined as the Hilbert space of Lebesgue measurable square-integrable real functions over R n10 , equipped with standard (pointwise) addition and scalar multiplication, as well as the inner product defined by integration over point-wise multiplication. For our purposes, L 2 (R n ) may simply be thought of as the (infinite-dimensional) vector space of functions g : R n → R satisfying g 2 < ∞, with inner product defined by g1, g2 := g1•g2. Our proof will make use of the following basic facts related to L 2 spaces:

Fact 1. If V is a finite-dimensional subspace of L 2 (R n ),

then any g∈L 2 (R n ) may be expressed as g = p + δ, with p∈V and δ∈V ⊥ (i.e. δ is orthogonal to all elements in V ). Moreover, such a representation is unique, so in the case where g∈V , we necessarily have p = g and δ ≡ 0.

Fact 2. If g∈L 2 (R n ), g ∈L 2 (R n ), then the function (x1, x2) →g(x1)•g (x2) belongs to L 2 (R n × R n ). Fact 3. Let V and V be finite-dimensional subspaces of L 2 (R n ) and L 2 (R n ) respectively, and de- fine U ⊂L 2 (R n × R n ) to be the subspace spanned by {(x1, x2) →p(x1)•p (x2) : p∈V, p ∈V }. Given g∈L 2 (R n ), g ∈L 2 (R n ), consider the function (x1, x2) →g(x1)•g (x2) in L 2 (R n × R n ). This function be- longs to U ⊥ if g∈V ⊥ or g ∈V ⊥ . Fact 4. If g1. . .gm∈L 2 (R n ) are linearly independent, then for any k ∈ N, the set of functions {(x1, . . . , x k ) → k i=1 g d i (xi)} d 1 ...d k ∈[m] is linearly independent in L 2 ((R n ) k ).

To facilitate application of the theory of L 2 spaces, we now make use of the assumption that the network's representation functions f θ d , as well as the functions gν , g ν in the definition of separation rank (eq. 5), are measurable and square-integrable. Taking into account the expression given in eq. 2 for hy, as well as fact 2 above, one readily sees that f θ 1 . . .f θ M ∈L 2 (R s ) implies hy∈L 2 ((R s ) N ). The separation rank sep(hy; I, J) will be the minimal non-negative integer R such that there exist g1. . .gR∈L 2 ((R s ) |I| ) and g 1 . . .g R ∈L 2 ((R s ) |J| ) for which:

EQUATION

We would like to show that sep(hy; I, J)≥rank A y I,J . Our strategy for achieving this will be to start from eq. 12, and derive an expression for A y I,J comprising a sum of R rank-1 matrices. As an initial step along this path, define the following finite-dimensional subspaces:

EQUATION

EQUATION

EQUATION

Notice that hy∈U (eq. 2), and that U is the span of products from V and V , i.e.:

EQUATION

Returning to eq. 12, we apply fact 1 to obtain orthogonal decompositions of g1. . .gR w.r.t. V , and of g 1 . . .g R w.r.t. V . This gives p1. . .pR∈V , δ1. . .δR∈V ⊥ , p 1 . . .p R ∈V and δ 1 . . .δ R ∈V ⊥ , such that gν = pν + δν and

g ν = p ν + δ ν for every ν ∈ [R]

. Plug this into eq. 12:

hy(x1, . . . , xN ) = R ν=1 gν (x1, . . . , x |I| )•g ν (x |I|+1 , . . . , xN ) = R ν=1 pν (x1, . . . , x |I| ) + δν (x1, . . . , x |I| ) • p ν (x |I|+1 , . . . , xN ) + δ ν (x |I|+1 , . . . , xN ) = R ν=1 pν (x1, . . . , x |I| )•p ν (x |I|+1 , . . . , xN ) + R ν=1 pν (x1, . . . , x |I| )•δ ν (x |I|+1 , . . . , xN ) + R ν=1 δν (x1, . . . , x |I| )•p ν (x |I|+1 , . . . , xN ) + R ν=1 δν (x1, . . . , x |I| )•δ ν (x |I|+1 , . . . , xN )

Given that U is the span of products from V and V (eq. 16), and that pν ∈V, δν ∈V ⊥ , p ν ∈V , δ ν ∈V ⊥ , one readily sees that the first term in the latter expression belongs to U , while, according to fact 3, the second, third and fourth terms are orthogonal to U . We thus obtained an orthogonal decomposition of hy w.r.t. U . Since hy is contained in U , the orthogonal component must vanish (fact 1), and we amount at:

EQUATION

For every ν ∈ [R], let B ν and C ν be coefficient tensors of pν and p ν w.r.t. the functions that span V and V (eq. 13 and 14), respectively. Put formally, B ν and C ν are tensors of orders |I| and |J| (respectively), with dimension M in each mode, meeting:

pν (x1, . . . , x |I| ) = M d 1 ...d |I| =1 B ν d 1 ...d |I| |I| i=1 f θ d i (xi) p ν (x1, . . . , x |J| ) = M d 1 ...d |J| =1 C ν d 1 ...d |J| |J| i=1 f θ d i (xi)

Substitute into eq. 17:

hy (x1, . . . , xN ) = R ν=1 M d 1 ...d |I| =1 B ν d 1 ...d |I| |I| i=1 f θ d i (xi) • M d |I|+1 ...d N =1 C ν d |I|+1 ...d N N i=|I|+1 f θ d i (xi) = R ν=1 M d 1 ...d N =1 B ν d 1 ...d |I| • C ν d |I|+1 ...d N N i=1 f θ d i (xi) = M d 1 ...d N =1 R ν=1 B ν d 1 ...d |I| • C ν d |I|+1 ...d N N i=1 f θ d i (xi)

Compare this expression for hy to that given in eq. 2:

EQUATION

At this point we utilize the given linear independence of f θ 1 . . .f θ M ∈L 2 (R s ), from which it follows (fact 4) that the functions spanning U (eq. 15) are linearly independent in L 2 ((R s ) N ). Both sides of eq. 18 are linear combinations of these functions, thus their coefficients must coincide:

A y d 1 ...d N = R ν=1 B ν d 1 ...d |I| • C ν d |I|+1 ...d N , ∀d1. . .dN ∈ [M ] ⇐⇒ A y = R ν=1 B ν ⊗ C ν

Matricizing the tensor equation on the right w.r.t. (I, J) gives:

A y I,J = R ν=1 B ν ⊗ C ν I,J = R ν=1 B ν ⊗ C ν I,J = R ν=1 B ν I∩[|I|],J∩[|I|] C ν (I-|I|)∩[|J|],(J-|I|)∩[|J|] = R ν=1 B ν [|I|],∅ C ν ∅,[|J|]

where the second equality is based on the linearity of the matricization operator, the third equality relies on the relation in eq. 1, and the last equality makes use of the assumption I = {1, . . . , |I|}, J = {|I| + 1, . . . , N }.

For every ν ∈ [R], B ν [|I|],∅ is a column vector of dimension M |I| and C ν ∅,[|J|]

is a row vector of dimension M |J| . Denoting these by uν and v ν respectively, we may write:

A y I,J = R ν=1 uν v ν

This shows that rank A y I,J ≤R. Since R is a general non-negative integer that admits eq. 12, we may take it to be minimal, i.e. to be equal to sep(hy; I, J) -the separation rank of hy w.r.t. (I, J). By this we obtain rank A y I,J ≤sep(hy; I, J), which is what we set out to prove.

A.2 PROOF OF CLAIM 2:

The claim is framed in measure theoretical terms, and in accordance, so will its proof be. While a complete introduction to measure theory is beyond our scope (the interested reader is referred to Jones ( 2001)), we briefly convey here the intuition behind the concepts we will be using, as well as facts we rely upon. The Lebesgue measure is defined over sets in a Euclidean space, and may be interpreted as quantifying their "volume". For example, the Lebesgue measure of a unit hypercube is one, of the entire space is infinity, and of a finite set of points is zero. In this context, when a phenomenon is said to occur almost everywhere, it means that the set of points in which it does not occur has Lebesgue measure zero, i.e. is negligible. An important result we will make use of (proven in Caron and Traynor (2005) for example) is the following. Given a polynomial defined over n real variables, the set of points in R n on which it vanishes is either the entire space (when the polynomial in question is the zero polynomial), or it must have Lebesgue measure zero. In other words, if a polynomial is not identically zero, it must be different from zero almost everywhere.

Heading on to the proof, we recall from sec. 3 that the entries of the coefficient tensor A y (eq. 2) are given by polynomials in the network's conv weights {a l,γ } l,γ and output weights a L,y . Since A y I,J -the matricization of A y w.r.t. the partition (I, J), is merely a rearrangement of the tensor as a matrix, this matrix too has entries given by polynomials in the network's linear weights. Now, denote by r the maximal rank taken by A y I,J as network weights vary, and consider a specific setting of weights for which this rank is attained. We may assume without loss of generality that under this setting, the top-left r-by-r block of A y I,J is non-singular. The corresponding minor, i.e. the determinant of the sub-matrix ( A y I,J )1:r,1:r, is thus a polynomial defined over {a l,γ } l,γ and a L,y which is not identically zero. In light of the above, this polynomial is different from zero almost everywhere, implying that rank( A y I,J )1:r,1:r = r almost everywhere. Since rank A y I,J ≥rank( A y I,J )1:r,1:r, and since by definition r is the maximal rank that A y I,J can take, we have that rank A y I,J is maximal almost everywhere.

A.3 PROOF OF THEOREM 1:

The matrix decomposition in eq. 7 expresses A I,J in terms of the network's linear weights -{a 0,γ ∈ R M } γ∈[r 0 ] for conv operator in hidden layer 0, {a l,γ ∈ R r l-1 } γ∈[r l ] for conv operator in hidden layer l = 1. . .L-1, and a L,y ∈ R r L-1 for node y of dense output operator. We prove lower and upper bounds on the maximal rank that A I,J can take as these weights vary. Our proof relies on the rank-multiplicative property of the Kronecker product (rank(A B) = rank(A)•rank(B) for any real matrices A and B -see Bellman (1970) for proof), but is otherwise elementary.

Beginning with the lower bound, consider the following weight setting (eγ here stands for a vector holding 1 in entry γ and 0 at all other entries, 0 stands for a vector holding 0 at all entries, and 1 stands for a vector holding 1 at all entries, with the dimension of a vector to be understood by context):

EQUATION

a 1,γ = 1 , γ = 1 0 , otherwise a l,γ = e1 , γ = 1 0 , otherwise for l = 2. . .L -1 a L,y = e1 Let n ∈ [N/4].

Recalling the definition of I l,k and J l,k from eq. 6, consider the sets I1,n and J1,n, as well as I 0,4(n-1)+t and J 0,4(n-1)+t for t ∈ [4]. (I1,n, J1,n) is a partition of [4], i.e. I1,n • ∪J1,n = [4], and for every t ∈ [4] we have I 0,4(n-1)+t = {1} and J 0,4(n-1)+t = ∅ if t belongs to I1,n, and otherwise I 0,4(n-1)+t = ∅ and J 0,4(n-1)+t = {1} if t belongs to J1,n. This implies that for an arbitrary vector v, the matricization v I 0,4(n-1)+t ,J 0,4(n-1)+t is equal to v if t∈I1,n, and to v if t∈J1,n. Accordingly, for any γ ∈ [r0]:

4 t=1 a 0,γ I 0,4(n-1)+t ,J 0,4(n-1)+t =           

(a 0,γ a 0,γ a 0,γ a 0,γ ) , |I1,n| = 4 |J1,n| = 0 (a 0,γ a 0,γ a 0,γ )(a 0,γ ) , |I1,n| = 3 |J1,n| = 1 (a 0,γ a 0,γ )(a 0,γ a 0,γ ) , |I1,n| = 2 |J1,n| = 2 (a 0,γ )(a 0,γ a 0,γ a 0,γ ) , |I1,n| = 1 |J1,n| = 3 (a 0,γ a 0,γ a 0,γ a 0,γ ) , |I1,n| = 0 |J1,n| = 4

Assume that γ ≤ min{r0, M }. By our setting a 0,γ = eγ, so the above matrix holds 1 in a single entry and 0 in all the rest. Moreover, if the matrix is not a row or column vector, i.e. if both I1,n and J1,n are non-empty, the column index and row index of the entry holding 1 are both unique w.r.t. γ, i.e. they do not repeat as γ ranges over 1 . . . min{r0, M }. We thus have:

rank min{r 0 ,M } γ=1 4 t=1 a 0,γ I 0,4(n-1)+t ,J 0,4(n-1)+t = min{r0, M } , I1,n = ∅ ∧ J1,n = ∅ 1 , I1,n = ∅ ∨ J1,n = ∅

Since we set a 1,1 = 1 and a 0,γ = 0 for γ > min{r0, M }, we may write:

rank r 0 γ=1 a 1,1 γ • 4 t=1 a 0,γ I 0,4(n-1)+t ,J 0,4(n-1)+t = min{r0, M } , I1,n = ∅ ∧ J1,n = ∅ 1 , I1,n = ∅ ∨ J1,n = ∅

The latter matrix is by definition equal to φ 1,1 I 1,n ,J 1,n (see top row of eq. 7), and so for every n ∈ [N/4]:

rank φ 1,1 I 1,n ,J 1,n = min{r0, M } , I1,n = ∅ ∧ J1,n = ∅ 1 , I1,n = ∅ ∨ J1,n = ∅ (20)

Now, the fact that we set a L,y = e1 and a l,1 = e1 for l = 2. . .L -1, implies that the second to last levels of the decomposition in eq. 7 collapse to:

A y I,J = N/4 t=1 φ 1,1 I 1,t ,J 1,t

Applying the rank-multiplicative property of the Kronecker product, and plugging in eq. 20, we obtain:

rank A y I,J = N/4 t=1 rank φ 1,1 I 1,t ,J 1,t = min{r0, M } S

where S := |{t ∈ [N/4] : I1,t = ∅ ∧ J1,t = ∅}|. This equality holds for the specific weight setting we defined in eq. 19. Maximizing over all weight settings gives the sought after lower bound:

max {a l,γ } l,γ ,a L,y rank A y I,J ≥ min{r0, M } S

Moving on to the upper bound, we show by induction over l = 1. . .L -1 that for any k ∈ [N/4 l ] and γ ∈ [r l ], the rank of φ l,γ I l,k ,J l,k is no greater than c l,k , regardless of the chosen weight setting. For the base case l = 1 we have:

φ 1,γ I 1,k ,J 1,k = r 0 α=1 a 1,γ α • 4 t=1 a 0,α I 0,4(k-1)+t ,J 0,4(k-1)+t The M |I 1,k | -by-M |J 1,k | matrix φ 1,γ I 1,k ,J 1,k

is given here as a sum of r0 rank-1 terms, thus obviously its rank is no greater than min{M min{|I 1,k |,|J 1,k |} , r0}. Since by definition c 0,t = 1 for all t ∈ [N ], we may write:

rank φ 1,γ I 1,k ,J 1,k ≤ min M min{|I 1,k |,|J 1,k |} , r0 4 t=1 c 0,4(k-1)+t

c 1,k is defined by the right hand side of this inequality, so our inductive hypotheses holds for l = 1. For l > 1:

φ l,γ I l,k ,J l,k = r l-1 α=1 a l,γ α • 4 t=1 φ l-1,α I l-1,4(k-1)+t ,J l-1,4(k-1)+t

Taking ranks:

rank φ l,γ I l,k ,J l,k = rank r l-1 α=1 a l,γ α • 4 t=1 φ l-1,α I l-1,4(k-1)+t ,J l-1,4(k-1)+t ≤ r l-1 α=1 rank 4 t=1 φ l-1,α I l-1,4(k-1)+t ,J l-1,4(k-1)+t = r l-1 α=1 4 t=1 rank φ l-1,α I l-1,4(k-1)+t ,J l-1,4(k-1)+t ≤ r l-1 α=1 4 t=1 c l-1,4(k-1)+t = r l-1 4 t=1 c l-1,4(k-1)+t

where we used rank sub-additivity in the second line, the rank-multiplicative property of the Kronecker product in the third line, and our inductive hypotheses for l -1 in the fourth line. Since the number rows and columns in φ l,γ I l,k ,J l,k is M |I l,k | and M |J l,k | respectively, we may incorporate these terms into the inequality, obtaining:

rank φ l,γ I l,k ,J l,k ≤ min M min{|I l,k |,|J l,k |} , r l-1 4 t=1 c l-1,4(k-1)+t

The right hand side here is equal to c l,k by definition, so our inductive hypotheses indeed holds for all l = 1. . .L -1. To establish the sought after upper bound on the rank of A y I,J , we recall that the latter is given by:

A y I,J = r L-1 α=1 a L,y α • 4 t=1 φ L-1,α I L-1,t ,J L-1,t

Carry out a series of steps similar to before, while making use of our inductive hypotheses for l = L -1:

rank A y I,J = rank r L-1 α=1 a L,y α • 4 t=1 φ L-1,α I L-1,t ,J L-1,t ≤ r L-1 α=1 rank 4 t=1 φ L-1,α I L-1,t ,J L-1,t = r L-1 α=1 4 t=1 rank φ L-1,α I L-1,t ,J L-1,t ≤ r L-1 α=1 4 t=1 c L-1,t = rL-1 4 t=1 c L-1,t

Since A y I,J has M |I| rows and M |J| columns, we may include these terms in the inequality, thus reaching the upper bound we set out to prove.

B SEPARATION RANK AND THE L 2 DISTANCE FROM SEPARABLE FUNCTIONS Our analysis of correlations modeled by convolutional networks is based on the concept of separation rank, conveyed in sec. 4. When the separation rank of a function w.r.t. a partition of its input is equal to 1, the function is separable, meaning it does not model any interaction between sides of the partition. We argued that the higher the separation rank, the farther the function is from this situation, i.e. the stronger the correlation it induces between sides of the partition. In the current appendix we formalize this argument, by relating separation rank to the L 2 distance from the set of separable functions. We begin by defining and characterizing a normalized (scale invariant) version of this distance (app. B.1). It is then shown (app. B.2) that separation rank provides an upper bound on the normalized distance. Finally, a lower bound that applies to deep convolutional arithmetic circuits is derived (app. B.3), based on the lower bound for their separation ranks established in sec. 5.2. Together, these steps imply that our entire analysis, facilitated by upper and lower bounds on separation ranks of convolutional arithmetic circuits, can be interpreted as based on upper and lower bounds on (normalized) L 2 distances from separable functions.

In the text hereafter, we assume familiarity of the reader with the contents of sec. 2, 3, 4, 5 and the proofs given in app. A. We also rely on basic knowledge in the topic of L 2 spaces (see discussion in app. A.1 for minimal background required in order to follow our arguments), as well as several results concerning singular values of matrices. In line with sec. 5, an assumption throughout this appendix is that all functions in question are measurable and square-integrable (i.e. belong to L 2 over the respective Euclidean space), and in app. B.3, we also make use of the fact that representation functions (f θ d ) of a convolutional arithmetic circuit can be regarded as linearly independent (see sec. For a function h∈L 2 ((R s ) N ) (which is not identically zero), the normalized L 2 distance from the set of separable functions w.r.t. (I, J), is defined as follows:

EQUATION

where • refers to the norm of L 2 space, e.g. h := ( (R s ) N h 2 ) 1/2 . In words, D(h; I, J) is defined as the minimal L 2 distance between h and a function that is separable w.r.t. (I, J), divided by the norm of h. The normalization (division by h ) admits scale invariance to D(h; I, J), and is of critical importance -without it, rescaling h would accordingly rescale the distance measure, rendering the latter uninformative in terms of deviation from separability.

It is worthwhile noting the resemblance between D(h; I, J) and the concept of mutual information (see Cover and Thomas (2012) for a comprehensive introduction). Both measures quantify the interaction that a normalized function11 induces between input variables, by measuring distance from separable functions. The difference between the measures is threefold. First, mutual information considers probability density functions (non-negative and in L 1 ), while D(h; I, J) applies to functions in L 2 . Second, the notion of distance in mutual information is quantified through the Kullback-Leibler divergence, whereas in D(h; I, J) it is simply the L 2 metric. Third, while mutual information evaluates the distance from a specific separable function -product of marginal distributions, D(h; I, J) evaluates the minimal distance across all separable functions.

We now turn to establish a spectral characterization of D(h; I, J), which will be used in app. B.2 and B.3 for deriving upper and lower bounds (respectively). Assume we have the following expression for h:

EQUATION

where m and m are positive integers, A is an m-by-m real matrix, and {φµ} m µ=1 , {φ µ } m µ =1 are orthonormal sets of functions in L 2 ((R s ) |I| ), L 2 ((R s ) |J| ) respectively. We refer to such expression as an orthonormal separable decomposition of h, with A being its coefficient matrix. We will show that for any orthonormal separable decomposition, D(h; I, J) is given by the following formula:

EQUATION

where σ1(A) ≥ • • • ≥ σ min{m,m } (A) ≥ 0 are the singular values of the coefficient matrix A. This implies that if the largest singular value of A accounts for a significant portion of the spectral energy, the normalized L 2 distance of h from separable functions is small. On the other hand, if all but a fraction of the spectral energy is attributed to trailing singular values, h is far from being separable (D(h; I, J) is close to 1).

As a first step in deriving eq. 23, we show that

EQUATION

Equality (1) here originates from the definition of L 2 norm.

(2) is obtained by plugging in the expression in eq. 22.

(3) is merely an arithmetic manipulation. (4) follows from the linearity of integration. (5) makes use

B.2 UPPER BOUND THROUGH SEPARATION RANK:

We now relate D(h; I, J) -the normalized L 2 distance of h∈L 2 ((R s ) N ) from the set of separable functions w.r.t. (I, J) (eq. 21), to sep(h; I, J) -the separation rank of h w.r.t. (I, J) (eq. 5). Specifically, we make use of the formula in eq. 23 to derive an upper bound on D(h; I, J) in terms of sep(h; I, J).

Assuming h has finite separation rank (otherwise the bound we derive is trivial), we may express it as: This is an orthonormal separable decomposition of h (eq. 22), with coefficient matrix A = R ν=1 αν (α ν ) , where αν := [αν,1 . . . αν,m] and α ν := [α ν,1 . . . α ν,m ] for every ν∈R. Obviously the rank of A is no greater than R, implying:

σ 2 1 (A) σ 2 1 (A) + • • • + σ 2 min{m,m } (A) ≥ 1 R

where as in app. B.1, σ1(A) ≥ • • • ≥ σ min{m,m } (A) ≥ 0 stand for the singular values of A. Introducing this inequality into eq. 23 gives:

D(h; I, J) = 1 - σ 2 1 (A) σ 2 1 (A) + • • • + σ 2 min{m,m } (A) ≤ 1 - 1 R

The latter holds for any R ∈ N that admits eq. 26, so in particular we may take it to be minimal, i.e. to be equal to sep(h; I, J)12 , bringing forth the sought after upper bound: D(h; I, J) ≤ 1 -1 sep(h; I, J)

By eq. 27, low separation rank implies proximity (in normalized L 2 sense) to a separable function. We may use the inequality to translate the upper bounds on separation ranks established for deep and shallow convolutional arithmetic circuits (sec. 5.2 and 5.3 respectively), into upper bounds on normalized L 2 distances from separable functions. To completely frame our analysis in terms of the latter measure, a translation of the lower bound on separation ranks of deep convolutional arithmetic circuits (sec. 5.2) is also required. Eq. 27 does not facilitate such translation, and in fact, it is easy to construct functions h whose separation ranks are high yet are very close (in normalized L 2 sense) to separable functions. 13 However, as we show in app. B.3 below, the specific lower bound of interest can indeed be translated, and our analysis may entirely be framed in terms of normalized L 2 distance from separable functions.

B.3 LOWER BOUND FOR DEEP CONVOLUTIONAL ARITHMETIC CIRCUITS:

Let hy∈L 2 ((R s ) N ) be a function realized by a deep convolutional arithmetic circuit (fig. 1 (a) with size-4 pooling windows and L = log 4 N hidden layers), i.e. hy is given by eq. 2, where f θ 1 . . .f θ M ∈L 2 (R s ) are linearly independent representation functions, and A y is a coefficient tensor of order N and dimension M in each mode, determined by the linear weights of the network ({a l,γ } l,γ , a L,y ) through the hierarchical decomposition in eq. 3. Rearrange eq. 2 by grouping indexes d1. . .dN in accordance with the partition (I, 

[N/4]) that are split by the partition (I, J). To prove this lower bound, we presented in app. A.3 a specific setting for the linear weights of the network ({a l,γ } l,γ , a L,y ) under which rank A y I,J = min{r0, M } S . Careful examination of the proof shows that with this particular weight setting, not only is the rank of A y I,J equal to min{r0, M } S , but also, all of its non-zero singular values are equal to one another. 14 This implies that σ 2 1 ( A y I,J )/(σ 2 1 ( A y I,J ) + • • • + σ 2 min{m,m } ( A y I,J )) = min{r0, M } -S , and since we currently assume that f θ 1 . . .f θ M are orthonormal, eq. 30 applies and we obtain D(hy; I, J) = 1 -min{r0, M } -S . Maximizing over all possible weight settings, we arrive at the following lower bound for the normalized L 2 distance from separable functions brought forth by a deep convolutional arithmetic circuit: sup {a l,γ } l,γ , a L,y D hy| {a l,γ } l,γ ,a L,y ; I, J ≥ 1 -1 min{r0, M } S (31)

Turning to the general case, we omit the assumption that representation functions f θ 1 . . .f θ M ∈L 2 (R s ) are orthonormal, and merely rely on their linear independence. The latter implies that the dimension of span{f θ 1 . . .f θ M } is M , thus there exist orthonormal functions ϕ1. . .ϕM ∈L 2 (R s ) that span it. Let F ∈ R M ×M be a transition matrix between the bases -the matrix defined by ϕc = M d=1 F c,d •f θ d , ∀c ∈ [M ]. Suppose now that we replace the original representation functions f θ 1 . . .f θ M by the orthonormal ones ϕ1. . .ϕM . Using the latter, the lower bound in eq. 31 applies, and there exists a setting for the linear weights of the network -{a l,γ } l,γ , a L,y , such that D(hy; I, J)≥ 1 -min{r0, M } -S . Recalling the structure of convolutional arithmetic circuits (fig. 1(a) ), one readily sees that if we return to the original representation functions f θ 1 . . .f θ M , while multiplying conv weights in hidden layer 0 by F (i.e. mapping a 0,γ →F a 0,γ ), the overall function hy remains unchanged, and in particular D(hy; I, J)≥ 1 -min{r0, M } -S still holds. We conclude that the lower bound in eq. 31 applies, even if representation functions are not orthonormal.

To summarize, we translated the lower bound from sec. 5.2 on the maximal separation rank realized by a deep convolutional arithmetic circuit, into a lower bound on the maximal normalized L 2 distance from separable functions (eq. 31). This, along with the translation of upper bounds facilitated in app. B.2, implies that the analysis carried out in the paper, which studies correlations modeled by convolutional networks through the notion of separation rank, may equivalently be framed in terms of normalized L 2 distance from separable functions. We note however that there is one particular aspect in our original analysis that does not carry through the translation. Namely, in sec. 5.1 it was shown that separation ranks realized by convolutional arithmetic circuits are maximal almost always, i.e. for all linear weight settings but a set of (Lebesgue) measure zero. Put differently, for a given partition (I, J), the maximal separation rank brought forth by a network characterizes almost all functions realized by it. An equivalent statement does not hold with the continuous measure of normalized L 2 distance from separable functions. The behavior of this measure across the hypotheses space of a network is non-trivial, and forms a subject for future research.

C IMPLEMENTATION DETAILS:

In this appendix we provide implementation details omitted from the description of our experiments in sec. 7. Our implementation, available online at https://github.com/HUJI-Deep/inductive-pooling, is based on the SimNets branch (Cohen et al. (2016a) ) of Caffe toolbox (Jia et al. (2014) ). The latter realizes convolutional arithmetic circuits in log-space for numerical stability.

When training convolutional arithmetic circuits, we followed the hyper-parameter choices made by Sharir et al. (2016) . In particular, our objective function was the cross-entropy loss with no L 2 regularization (i.e. with weight decay set to 0), optimized using Adam (Kingma and Ba (2014) ) with step-size α = 0.003 and moment decay rates β1 = β2 = 0.9. 15000 iterations with batch size 64 (48 epochs) were run, with the step-size α decreasing by a factor of 10 after 12000 iterations (38.4 epochs). We did not use dropout (Srivastava et al. (2014) ), as the limiting factor in terms of accuracies was the difficulty of fitting training data (as opposed to overfitting) -see fig. 3 .

For training the conventional convolutional rectifier networks, we merely switched the hyper-parameters of Adam to the recommended settings specified in Kingma and Ba (2014) (α = 0.001, β1 = 0.9, β2 = 0.999), and set weight decay to the standard value of 0.0001. 14 To see this, note that with the specified weight setting, for every n ∈ [N/4], φ 1,1 I 1,n ,J 1,n has one of two forms: it is either a non-zero (row/column) vector, or it is a matrix holding 1 in several entries and 0 in all the rest, where any two entries holding 1 reside in different rows and different columns. The first of the two forms admits a single non-zero singular value. The second brings forth several singular values equal to 1, possibly accompanied by null singular values. In both cases, all non-zero singular values of φ 1,1 I 1,n ,J 1,n are equal to one another. Now, since A y I,J = N/4 n=1 φ 1,1 I 1,n ,J 1,n , and since the Kronecker product multiplies singular values (see Bellman (1970) ), we have that all non-zero singular values of A y I,J are equal, as required.

:

The definitions we give are actually concrete special cases of more abstract algebraic definitions as given inHackbusch (2012). We limit the discussion to these special cases since they suffice for our needs and are easier to grasp.

If I = ∅ or J = ∅ then by definition sep(h; I, J) = 1 (unless h ≡ 0, in which case sep(h; I, J) = 0).

The normalization (division by norm) is of critical importance -without it rescaling h would accordingly rescale D(h; I, J), rendering the latter uninformative in terms of deviation from separability.

Suppose for example that f θ M is dependent, i.e. there exist α1 . .. αM-1 ∈ R such that f θ M (x) = M -1 d=1 α d •f θ d (x).We may then plug this into eq. 2, and obtain an expression for hy that has f θ 1 . . .f θ M -1 as representation functions, and a coefficient tensor with dimension M -1 in each mode. Continuing in this fashion, one arrives at an expression for hy whose representation functions are linearly independent.

Square-integrability of representation functions f θ d may seem as a limitation at first glance, as for example neuronsf θ d (x) = σ(w d x + b d ), with parameters θ d = (w d , b d ) ∈ R s × Rand sigmoid or ReLU activation σ(•), do not meet this condition. However, since in practice our inputs are bounded (e.g. they represent image pixels by holding intensity values), we may view functions as having compact support, which, as long as they are continuous (holds in all cases of interest), ensures square-integrability.

Convolutional arithmetic circuits as we have defined them (sec. 3) are not universal. In particular, it may very well be that a function realized by a polynomially sized deep network cannot be replicated by the shallow network, no matter how large (wide) we allow it to be. In such scenarios depth efficiency does not provide insight into the complexity of functions brought forth by depth. To obtain a shallow network that is universal, thus an appropriate gauge for depth efficiency, we may remove the constraint of weight sharing, i.e. allow the filters in the hidden conv operator to hold different weights at different spatial locations (seeCohen et al. (2016b) for proof that this indeed leads to universality). All results we have established for the original shallow network remain valid when weight sharing is removed. In particular, the separation ranks of the network are still linear in its size. This implies that as suggested, depth efficiency indeed holds.

More precisely, elements of the space are equivalence classes of functions, where two functions are considered equivalent if the set in R n on which they differ has measure zero.

An equivalent definition of D(h; I, J) is the minimal L 2 distance between h/ h and a function separable w.r.t. (I, J). Accordingly, we may view D(h; I, J) as operating on normalized functions.

We disregard the trivial case where sep(h; I, J) = 0 (h is identically zero).

This will be the case, for example, if h is given by an orthonormal separable decomposition (eq. 22), with coefficient matrix A that has high rank but whose spectral energy is highly concentrated on one singular value.

Figures and Tables:

Figure 1: Best viewed in color. (a) Convolutional arithmetic circuit architecture analyzed in this paper (see description in sec. 3). (b) Shallow network with global pooling in its single hidden layer.(c) Illustration of input patch ordering for deep network with 2 × 2 pooling windows, along with patterns induced by the partitions (I odd , J even ) and (I low , J high ) (eq. 8 and 9 respectively).

Figure2: Sample of images from our synthetic classification benchmark. Each image displays a random blob with holes, whose morphological closure and left-right symmetry about its center are measured. Two classification tasks are defined -one for closedness and one for symmetry. In each task, the objective is to distinguish between blobs whose respective property (closedness/symmetry) is high, and ones for which it is low. The tasks differ in nature -closedness requires modeling correlations between neighboring pixels, whereas symmetry requires modeling correlations between pixels and their reflections.

Figure 4: Results of applying deep convolutional rectifier networks to closedness and symmetry classification tasks. The same trends observed with the deep convolutional arithmetic circuit (fig. 3) are apparent here.

e. h y (xi 1 , . . . , xi |I| , xj 1 , . . . , xj |J| ) = hy(x1, . . . , xN ). Obviously sep(hy; I, J) = sep(h y ; I , J ), where the partition (I , J ) is defined by I = {1, . . . , |I|} and J = {|I| + 1, . . . , N }. Analogously to the definition of h y , let A y be the tensor obtained by permuting the modes of A y such that those indexed by I are on the left and those indexed by J on the right, i.e. A y d i 1 ...d i |I| d j 1 ...d j |J| = A y d 1 ...d N . It is not difficult to see that matricizing A y w.r.t. (I , J

5.1). Finally, for convenience, we now fix (I, J) -an arbitrary partition of [N ]. Specifically, I and J are disjoint subsets of [N ] whose union gives [N ], denoted by I = {i1, . . . , i |I| } with i1 < • • • < i |I| , and J = {j1, . . . , j |J| } with j1 < • • • < j |J| . B.1 NORMALIZED L 2 DISTANCE FROM SEPARABLE FUNCTIONS

J): hy (x1, . . . , xN ) = M d i 1 ...d i |I| =1 M d j 1 ...d j |J| =1 A y d 1 ...d N • |I| t=1 f θ d i t (xi t ) |J| t=1 f θ d j t (xj t )

M1×

Table content: <table/>

•×M N .A fundamental operator in tensor analysis is the tensor product, which we denote by ⊗. It is an operator that intakes two tensors A ∈ R

Table content: <table/>

M1×

Table content: <table/>

•×M P and B ∈ R M P +1

Table content: <table/>

•×M P +Q (orders P and Q respectively), and returns a tensor A ⊗ B ∈ R

Table content: <table/>

M1×

Table content: <table/>

•×M P +Q (order P + Q) defined by: (A ⊗ B) d1...d P +Q = A d1...d P • B d P +1 ...d P +Q

Table content: <table/>

, . . . , xi |I| )g ν (xj 1 , . . . , xj |J| ) (26)where R is some positive integer (necessarily greater than or equal to sep(h; I, J)), and g1. . .gR∈L 2 ((R s ) |I| ), g 1 . . .g R ∈L 2 ((R s ) |J| ). Let {φ1, . . . , φm}⊂L 2 ((R s ) |I| ) and {φ 1 , . . . , φ m }⊂L 2 ((R s ) |J| ) be two sets of orthonormal functions spanning span{g1. . .gR} and span{g 1 . . .g R } respectively. By definition, for every ν∈R there exist αν,1 . . . αν,m ∈ R and α ν,1 . . . α ν,m ∈ R such that gν = • φµ(xi 1 , . . . , xi |I| )φ µ (xj 1 , . . . , xj |J| )

Table content: <table><tr><td colspan="3">h(x1, . . . , xN ) =</td><td>R ν=1</td><td colspan="2">gν (xi 1 m µ=1 αν,µ • φµ and</td></tr><tr><td colspan="6">g ν = m µ =1 α ν,µ • φ µ . Plugging this into eq. 26, we obtain:</td></tr><tr><td>h(x1, . . . , xN ) =</td><td>m µ=1</td><td>m µ =1</td><td colspan="2">R ν=1</td><td>αν,µα ν,µ</td></tr></table>

Peer review (iclr2017):
The paper provides a highly complex algebraic machinery to analyze the type of functions covered by convolutional network. As in most attempts in this direction in the literature, the ideal networks described in paper, which have to be interpretable as polynomials over tensors, do not match the type of CNNs used in practice: for instance the Relu non-linearity is replaced with a product of linear functions (or a sum of logs). While the paper is very technical to read, every concept is clearly stated and mathematical terminology properly introduced. Still, I think some the authors could make some effort to make the key concepts more accessible, and give a more intuitive understanding of what the separation rank means rather before piling up different mathematical interpretation. My SVM-era algebra is quite rusted, and I am not familiar with the separation rank framework: it would have been much easier for me to first fully understand a simple and gentle case (shallow network in section 5.3), than the general deep case. To summarize my understanding of the key theorem 1 result: - The upper bound of the separation rank is used to show that in the shallow case, this rank grows AT MOST linearly with the network size (as measured by the only hidden layer). So exponential network sizes are caused by this rank needing to grow exponentially, as required by the partition. - In the deep case, one also uses the case that the upper bound is linear in the size of the network (as measured by the last hidden layer), however, this situation is caused by the selection of a partition (I^low, J^high), and the maximal rank induced by this partition is only linear anyway, hence the network size can remain linear. If tried my best to summarize the key point of this paper and still probably failed at it, which shows how complex is this notion of partition rank, and that its linear growth with network size can either be a good or bad thing depending on the setting. Hopefully, someone will come one day with an explanation that holds in a single slide. While this is worth publishing as conference paper in its present form, I have two suggestions that, IMHO, would make this work more significant: On the theory side, we are still very far from the completeness of the PAC bound papers of the *shallow era*. In particular, the non-probabilistic lower and upper bound in theorem 1 are probably loose, and there is no PAC-like theory to tell us which one to use and what is the predicted impact on performance (not just the intuition). Also, in the prediction of the inductive bias, the other half is missing. This paper attempts to predict the maximal representation capacity of a DNN under bounded network size constraints, but one of the reason why this size has to be bounded is overfitting (justified by PAC or VC-dim like bounds). If we consider the expected risk as the sum of the empirical risk and the structural risk, this paper only seems to address fully the empirical risk minimization part, freezing the structural risk. On the practice side, an issue is that experiments in this paper mostly confirm what is obvious through intuition, or some simpler form of reasonings. For instance to use convolutions that join pixels which are symmetrical in images to detect symmetry. Basic hand-crafted pattern detectors, as they have been used in computer vision for decades, would just do the job. What would be a great motivation for using this framework is if it answered questions that simple human intuition cannot, and for which we are still in the dark: one example I could think of in the recent use of gated convolutions *a trous* for 1D speech signal, popularized in Google WaveNet (https://deepmind.com/blog/wavenet-generative-model-raw-audio/). Note that 1D inputs would also simplify the notation!