PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Expressive Power of Deep Learning: A Tensor Analysis

Nadav Cohen, Or Sharir, Amnon Shashua

arXiv:1509.05009v3cs.NEcs.LGmath.NAstat.ML

TL;DR

The paper addresses limited theoretical support for depth efficiency in practical convolutional networks, whose locality, sharing, and pooling had been omitted from prior analyses. It introduces convolutional arithmetic circuits linked to tensor decompositions and proves that, outside a negligible set, polynomial-size deep functions require exponential-size shallow realizations or approximations.

  • Problem

    Prior depth-efficiency theory largely concerns architectures unlike practical convolutional networks and omits locality, sharing, and pooling.

  • Method

    The paper constructs convolutional arithmetic circuits incorporating locality, sharing, and pooling, and identifies shallow and deep networks with CP and Hierarchical Tucker decompositions.

  • Results

    Almost all score functions produced by polynomial-size deep networks cannot be approximated by shallow networks unless the latter have exponential size in N.

  • Takeaways & Limitations

    The theory supports depth efficiency for convolutional-style architectures and connects it to the greater representational scope of hierarchical tensor decompositions.

  • Takeaways & Limitations

    The analysis uses a special HT decomposition corresponding to practical convolutional arithmetic circuits, while broader claims about receptive-field size remain conjectural and are left for future work.

Abstract

from arXiv · show

It has long been conjectured that hypotheses spaces suitable for data that is compositional in nature, such as text or images, may be more efficiently represented with deep hierarchical networks than with shallow ones. Despite the vast empirical evidence supporting this belief, theoretical justifications to date are limited. In particular, they do not account for the locality, sharing and pooling constructs of convolutional networks, the most successful deep learning architecture to date. In this work we derive a deep network architecture based on arithmetic circuits that inherently employs locality, sharing and pooling. An equivalence between the networks and hierarchical tensor factorizations is established. We show that a shallow network corresponds to CP (rank-1) decomposition, whereas a deep network corresponds to Hierarchical Tucker decomposition. Using tools from measure theory and matrix algebra, we prove that besides a negligible set, all functions that can be implemented by a deep network of polynomial size, require exponential size in order to be realized (or even approximated) by a shallow network. Since log-space computation transforms our networks into SimNets, the result applies directly to a deep learning architecture demonstrating promising empirical performance. The construction and theory developed in this paper shed new light on various practices and ideas employed by the deep learning community.

1. Introduction

The paper develops a theory of depth efficiency for convolutional-style networks, addressing prior analyses that omitted locality, sharing, and pooling. Its convolutional arithmetic circuits connect deep networks to hierarchical tensor decompositions and yield almost-everywhere exponential separations from shallow networks.

  • Existing depth-efficiency results mainly analyze architectures unlike practical networks and do not apply to convolutional networks.
  • Convolutional networks use locality, sharing, and pooling to reflect compositional structure and spatially reused semantics.
  • The proposed convolutional arithmetic circuits implement convolutions with sum nodes and pooling with product nodes.
  • The architecture is equivalent to SimNets and realizes hierarchical tensor decompositions, enabling mathematical and algorithmic analysis.
  • Almost all functions realized by polynomial-size deep networks require exponential size for realization or approximation by shallow networks.
  • Removing layers while preserving representational power can require resources that grow double exponentially with the number of removed layers.

2. Preliminaries

The preliminaries define tensors, tensor products, CP decompositions, symmetry, and measure-zero sets used throughout the analysis. They also establish the notation and scope needed to connect network representations with tensor factorizations.

  • Vectors use boldface, tensor entries use regular subscripts, and tensors are denoted by calligraphic letters such as A and B.
  • The notation [k] denotes the set {1, . . . , k}, while (R^s)^N abbreviates an N-fold Cartesian product.
  • A tensor is a multidimensional array whose order is the number of indexing modes.
  • The tensor product combines tensors of orders P and Q into one of order P + Q through entrywise multiplication across indexed factors.
  • Pure tensors are rank-1 tensor products, and general tensors can be represented as sums of rank-1 terms.
  • A CP decomposition expresses a tensor as a sum of rank-1 terms, with CP-rank defined as the minimum number of terms.
  • A symmetric tensor is invariant under permutations of its indices; symmetric CP decompositions use repeated vector factors.
  • A measure-zero set has zero Lebesgue volume and is hit with probability zero by a continuous random draw.

3. Convolutional Arithmetic Circuits

The paper constructs shallow and deep convolutional arithmetic circuits corresponding to CP and hierarchical tensor decompositions, respectively. These models incorporate convolutional structure and reveal expressive advantages for hierarchical networks, including under coefficient sharing.

  • The classifier represents instances as collections of vectors and computes per-label score functions for classification.
  • 3.1. Shallow Network as a CP Decomposition of Ay: The CP model is a shallow single-hidden-layer convolutional arithmetic circuit implementing a CP decomposition of the coefficient tensors.Its hidden layer uses a 1 × 1 convolution followed by pooling and produces class scores.
  • 3.1. Shallow Network as a CP Decomposition of Ay: The CP model is universal with sufficiently many components, but generic tensors have exponential CP-rank, making universality exponentially large.The required component count Z is exponential in the tensor order N.
  • 3.2. Deep Network as a Hierarchical Decomposition of Ay: Hierarchical decomposition is universal and contains CP representations with only a polynomial parameter penalty.With equal ranks r, the hierarchical model uses N · M · r + N · r^2 + Y · r parameters, while retaining the CP model as a special case.
  • 3.2. Deep Network as a Hierarchical Decomposition of Ay: The HT model is a deep network with L = log2 N hidden layers, using local 1 × 1 convolutions and size-2 product pooling.Unlike the CP model’s global pooling, successive layers hierarchically combine neighboring feature-map locations.
  • 3.3. Shared Coefficients for Convolution: With coefficient sharing, the CP model can represent only symmetric tensors, whereas the shared HT model is not restricted to symmetric tensors.Sharing constrains coefficients across spatial locations; the shared HT construction therefore retains an expressive advantage over the shared shallow model.

4. Theorems of Network Capacity

The paper establishes an equivalence between convolutional arithmetic circuits and tensor decompositions, then uses matricization, matrix algebra, and measure theory to prove depth-efficiency results. Except for a negligible set, polynomial-size deep HT networks produce functions that shallow CP networks require exponential size to realize or approximate.

  • Architecture–decomposition equivalence: The paper’s first contribution is an equivalence between practical convolutional arithmetic circuits and hierarchical tensor decompositions.The construction connects architectures such as SimNets with tensor-decomposition representations.
  • Capacity theorem: Almost every HT-generated tensor has CP-rank at least min{r0, M}^N/2, including under weight sharing.The configurations with lower CP-rank form a Lebesgue-measure-zero set.
  • Capacity theorem: With probability one, HT score functions cannot be approximated arbitrarily well by CP models with fewer than min{r0, M}^N/2 hidden channels.This remains true when the HT model uses weight sharing and the CP model remains general.
  • Capacity theorem: Except for a negligible set, polynomial-size HT functions require exponential-size CP models for realization or approximation.This strengthens earlier depth-separation results from existence claims to an almost-everywhere statement.
  • Proof strategy: The proof matricizes tensors, bounds CP matricization rank by the number of terms, and lower-bounds HT matricization rank through induction.Kronecker-product rank identities provide the matrix-algebra step, while parameter-space measure theory supports the almost-everywhere claim.

5. Discussion

The discussion connects the theory to convolutional-network design, suggesting roles for pooling, sharing, and locality beyond their usual interpretations. It also identifies scope for future investigation, especially regarding receptive-field size.

  • Connection to practice: The theory is translated to SimNets through log-space convolution and product-pooling computations.SimNets are described as having demonstrated state-of-the-art accuracy in computationally limited settings.
  • Pooling: The framework suggests pooling may factorize computed functions rather than primarily provide translation invariance.This interpretation is consistent with the typically small pooling windows used in state-of-the-art convolutional networks.
  • Pooling: Pooling over large windows while reducing network depth may cause an exponential decrease in expressive efficiency.The paper presents this as a consequence within its tensor-factorization framework.
  • Sharing: Weight sharing severely limits shallow CP models to symmetric tensors and location-invariant representations.The corresponding limitation is less strict in deep HT models, whose tensors need not be symmetric.
  • Sharing: Deep networks can combine sharing’s statistical and computational advantages with multiple layers that mitigate its expressive limitations.The paper presents this as an argument related to the empirical success of deep convolutional networks.
  • Locality: The construction favors 1 × 1 receptive fields, which factorize tensors while providing universality with minimal parameters.The paper notes that larger receptive fields may add redundancy when training data is limited, but leaves this conjecture for future work.

Appendix A. Generalized Theorem of Network Capacity

The appendix generalizes the capacity theorem from full-depth versus shallow networks to intermediate depths, quantifying the cost of removing layers. Almost everywhere, shallower networks require exponentially more channels, with the penalty growing double exponentially in layers removed.

  • Generalized comparison: The generalized theorem compares truncated hierarchical tensor decompositions with L1 levels against representations using fewer L2 levels.The corresponding networks differ in depth and use premature global pooling when truncation occurs.
  • Generalized comparison: Almost everywhere, matching a tensor generated with L1 levels using L2 < L1 levels requires at least (r)2L−L2 composition rank.Configurations with r(2)L2−1 < (r)2L−L2 form a measure-zero set, and the result also holds under weight sharing.
  • Approximation consequence: The corresponding network result holds with probability one for randomized deeper-network weights, even when the deeper network uses weight sharing.Approximation in L2 is impossible for shallower networks below the stated last-hidden-layer channel threshold.
  • Relation to the fundamental theorem: The original capacity theorem is recovered as the extreme case L1 = L and L2 = 1, contrasting full depth with a single hidden layer.CP and HT models represent these depth extremes through global pooling and minimal size-2 pooling windows, respectively.
  • Scope: The construction is not limited to CP, HT, and truncated HT models; analogous results may extend to other pooling-window sizes and depths.The appendix presents these decompositions as initial exemplars for the broader theoretical approach.

B.1. Proof of Theorems 1 and 3

The proofs establish rank-based lower bounds for hierarchical tensor decompositions and transfer them to network capacity results. Measure-theoretic arguments show that the required rank properties hold almost everywhere, including under shared compositions.

  • Measure-theoretic machinery: A polynomial that is not identically zero vanishes only on a zero-measure set, enabling almost-everywhere rank claims.The analysis uses Lebesgue measure on Euclidean parameter spaces and closure properties of zero-measure sets.
  • Matrix and tensor preliminaries: Matricization converts tensor products into Kronecker products, while Kronecker-product ranks multiply; these identities support the proof’s rank-growth argument.A CP decomposition with Z terms yields a matricization of rank at most Z.
  • Rank lemmas: For generic parameters, the product matrix U(x) = A(x)D(x)B(x)⊤ has rank min{M, N}, including when A(x) and B(x) share entries.The proof constructs one nonsingular minor and uses its determinant polynomial to exclude only a zero-measure exceptional set.
  • Rank lemmas: Linear combinations of continuously parameterized matrices preserve the almost-everywhere lower-rank guarantee under the lemma’s assumptions.The proof analyzes rank-deficient fibers and applies Fubini’s theorem, followed by monotone convergence.
  • Proof of the capacity theorem: These rank bounds establish exponential efficiency of HT over CP decomposition for almost all coefficient choices.The proof explicitly frames theorem 1 as an exponential-efficiency comparison between the two decompositions.
  • Proof of the capacity theorem: Induction over decomposition levels shows that hierarchical tensors have matricization rank at least r2l/2 almost everywhere.At level L2, a specific parameter assignment yields rank r, and a nonzero determinant polynomial extends the claim almost everywhere.

B.2. Proof of Corollaries 2 and 4

The corollaries transfer tensor nonrepresentability into function-space nonapproximation. Linear independence of representation functions and matricization-rank separation yield a strictly positive L2 distance.

  • From tensors to functions: The corollaries extend the theorems from coefficient-tensor realization to approximation of the associated score functions.This extension is needed because CP-expressible tensor sets are not necessarily topologically closed.
  • From tensors to functions: Linearly independent representation functions allow tensor rank separation to imply function-space separation.The mapping h associates each coefficient tensor with a score function in L2.
  • Rank-based nonapproximation: The proof represents approximating functions by coefficient tensors and uses finite-dimensional norm convergence to transfer function convergence into coefficient convergence.This contradicts the positive tensor-space distance implied by the target’s higher matricization rank.
  • Rank-based nonapproximation: If every approximating tensor has lower matricization rank than the target, the target function remains at strictly positive L2 distance from the approximating family.The proof reduces function-space distance to tensor-space distance and then to matrix-rank separation.

Appendix C. Derivation of Hypotheses Space

The appendix derives the paper’s hypotheses space from L2 function spaces and tensor products. Product functions inherit totality or linear independence, while point-wise multiplication identifies the tensor-product space with an L2 space on a product domain.

  • L2 foundations: The hypotheses-space derivation starts from L2 spaces of square-integrable functions and develops a universal representation using tensor products.The construction is presented as the foundation for the finite-dimensional hypotheses space used in the paper.
  • L2 foundations: A total set approximates every L2 function arbitrarily well through finite linear combinations, while a linearly independent set admits only trivial finite linear relations.These properties provide the functional basis for constructing representations.
  • Tensor-product construction: Products of functions from a total or linearly independent set remain total or linearly independent in the corresponding product-space L2 space.The result applies to functions formed as products across N input coordinates.
  • Tensor-product construction: Tensor products of Hilbert spaces provide the abstract structure underlying the paper’s tensor representations.The appendix connects concrete tensor operations with the tensor product of vector spaces and Hilbert spaces.
  • Tensor-product construction: For L2(Rs) spaces, point-wise multiplication maps tensor products of functions to products of functions and induces a Hilbert-space isomorphism.This identifies the tensor-product representation with functions on the product domain.

C.2. Construction

The construction represents score functions as finite or universal combinations of point-wise products, with coefficient tensors encoding the combination. Total function families, including Gaussians and neurons, provide the required basis choices.

  • C.2. Construction: The instance space is represented by local vectors, and score functions are expanded in point-wise products of parametric functions.The coefficient functions are selected from a family F of functions mapping R^s to R.
  • C.2. Construction: A total countable function set yields a universal hypotheses space capable of approximating every function in L2(X).Wavelets, Gaussians, and neurons are identified as possible basis families, with Gaussians and neurons receiving particular attention.
  • C.2. Construction: Gaussians use centers and variances as parameters, while neurons use weights, biases, and point-wise nonlinear activations.The listed neuron activations include threshold, ReLU, and sigmoid functions.
  • C.2. Construction: A finite coefficient tensor A_y specifies the weights of the product-function expansion for each label y.When the one-vector functions are linearly independent, the coefficient tensor uniquely determines the score function.

C.3. Finite Function Bases for Classification of Natural Data

The classification construction uses score functions over local input vectors and seeks low approximation error to optimal scores. Under natural-data assumptions, a moderate finite basis can represent these scores with negligible classification error.

  • C.3. Finite Function Bases for Classification of Natural Data: The classifier assigns labels by maximizing per-label score functions over instances composed of N local vectors.The score functions are defined on X = (R^s)^N and compared against ground-truth scores.
  • C.3. Finite Function Bases for Classification of Natural Data: A total basis also makes the score-function family universal as M tends to infinity.The universality requirement is that a countable subset of the one-vector function family be total in L2(R^s).
  • C.3. Finite Function Bases for Classification of Natural Data: The classification error is bounded by optimal expected hinge-loss plus twice the score approximation error.With deterministic labels, the optimal hinge-loss is essentially zero, so approximation error dominates.
  • C.3. Finite Function Bases for Classification of Natural Data: Natural-data assumptions concentrate local vectors near M templates and require score functions to be approximately constant in the resulting regions.The analysis does not assume statistical independence among local vectors.
  • C.3. Finite Function Bases for Classification of Natural Data: Gaussians or neurons can be chosen to separate the templates, making the discretized score approximation error zero.Gaussians use narrow centers, while neurons use separating hyperplanes; the coefficient tensors are then assigned accordingly.
  • C.3. Finite Function Bases for Classification of Natural Data: M on the order of 100 can suffice for natural data, although the template-quantization assumption is substantially restrictive and only approximately satisfied.The resulting classification error is described as negligible compared with other error sources under the stated assumptions.

Appendix D. Related Work

Prior work analyzes depth efficiency through Boolean, arithmetic, and neural-network frameworks, but differs in approximation scope, universality, or breadth of separating cases. Tensor-based neural architectures provide related precedents.

  • Appendix D. Related Work: Boolean-circuit results show that some depth-k functions with polynomial size require exponentially larger circuits at depth k−1 or less.Later work also established hardness of approximation for some shallow Boolean circuits.
  • Appendix D. Related Work: Arithmetic circuits and Sum-Product Networks compute weighted sums and products, connecting prior expressiveness analyses to the operations used here.Arithmetic-circuit networks have also been studied for training properties and probabilistic computation.
  • Appendix D. Related Work: Earlier SPN analyses were limited by exact-realization settings, non-universal families, or narrow depth separations and did not establish how frequent hard functions are.These limitations leave open whether most deep-network functions might still be efficiently realized by shallow networks.
  • Appendix D. Related Work: ReLU-network studies characterize the number of linear regions as a function of depth and width.This provides an alternative route for studying depth-dependent expressiveness.
  • Appendix D. Related Work: Several prior architectures incorporate tensor-based elements for expressiveness or training, but use different constructions from the present analysis.The cited examples include tensor-based neural architectures and tensor-decomposition training methods.

Appendix E. Computation in Log-Space with SimNets

Log-space computation avoids numerical instability in arithmetic circuits by replacing products with sums and sums with log-sum-exp operations. SimNets implement these operations stably and have demonstrated competitive image-recognition performance.

  • Appendix E. Computation in Log-Space with SimNets: Products with many inputs can overflow or underflow, motivating computation in log-space with non-negative activations.In this representation, product operations become sums of logarithms.
  • Appendix E. Computation in Log-Space with SimNets: A naive log-space implementation maps convolutions to locally connected linear transformations, product pooling to sum pooling, and pooling outputs to exponentiation.The direct use of logarithm and exponential activations is not numerically stable without additional input handling.
  • Appendix E. Computation in Log-Space with SimNets: SimNets combine a flexible similarity layer with the MEX operator to implement logarithmic basis evaluations, log-sum-exp, and sum-pooling stably.The similarity layer can compute convolutional operators and weighted lp norms.
  • Appendix E. Computation in Log-Space with SimNets: SimNets have matched state-of-the-art convolutional networks on several image-recognition benchmarks and outperformed them when computational resources were limited.This supplies an existing practical architecture capable of implementing the analyzed networks.
  • Appendix E. Computation in Log-Space with SimNets: Numerical stability can be restored for log-sum-exp by subtracting the maximum log input before exponentiation and adding it back afterward.This ensures exponentiated values are non-positive in the exponent, with at least one equal to zero.
Loading 1509.05009v3…