PaperlayerView exact revision on arXiv

Source-linked AI summary

Convolutional Rectifier Networks as Generalized Tensor Decompositions

Nadav Cohen, Amnon Shashua

arXiv:1603.00162v2cs.NEcs.LG

TL;DR

The paper addresses limited theoretical understanding of convolutional rectifier networks and their depth efficiency. It constructs a generalized-tensor-decomposition bridge from convolutional arithmetic circuits, then shows distinct universality and depth-efficiency results for max and average pooling. The authors conclude that convolutional arithmetic circuits may have a provable expressive advantage.

  • Problem

    The expressive properties and depth efficiency of convolutional rectifier networks are less understood than those of convolutional arithmetic circuits.

  • Method

    The paper uses generalized tensor decompositions to transform convolutional arithmetic circuits into convolutional rectifier networks and apply arithmetic-circuit analysis.

  • Results

    Convolutional rectifier networks are universal with max pooling but not average pooling, and their depth efficiency is weaker than that of convolutional arithmetic circuits.

  • Takeaways & Limitations

    The analysis indicates that convolutional arithmetic circuits may offer a provable expressive advantage over widely used convolutional rectifier networks.

  • Takeaways & Limitations

    For ReLU activation with max pooling, depth efficiency becomes more prevalent with more hidden channels but is never complete.

Abstract

from arXiv · show

Convolutional rectifier networks, i.e. convolutional neural networks with rectified linear activation and max or average pooling, are the cornerstone of modern deep learning. However, despite their wide use and success, our theoretical understanding of the expressive properties that drive these networks is partial at best. On the other hand, we have a much firmer grasp of these issues in the world of arithmetic circuits. Specifically, it is known that convolutional arithmetic circuits possess the property of "complete depth efficiency", meaning 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 implemented (or even approximated) by a shallow network. In this paper we describe a construction based on generalized tensor decompositions, that transforms convolutional arithmetic circuits into convolutional rectifier networks. We then use mathematical tools available from the world of arithmetic circuits to prove new results. First, we show that convolutional rectifier networks are universal with max pooling but not with average pooling. Second, and more importantly, we show that depth efficiency is weaker with convolutional rectifier networks than it is with convolutional arithmetic circuits. This leads us to believe that developing effective methods for training convolutional arithmetic circuits, thereby fulfilling their expressive potential, may give rise to a deep learning architecture that is provably superior to convolutional rectifier networks but has so far been overlooked by practitioners.

1. Introduction

Convolutional rectifier networks are widely used deep-learning models, but their expressive properties and depth efficiency remain poorly understood. This paper transfers tools from arithmetic circuits to analyze those questions.

  • Architecture: Convolutional rectifier networks stack convolution, ReLU activation, and max or average pooling layers.ReLU computes σ(z) = max{0,z}; pooling aggregates feature-map values by maxima or means.
  • Open problem: Formal evidence for depth efficiency in convolutional rectifier networks remains scarce, including evidence about how prevalent it is across weight settings.Complete depth efficiency would hold for all weight settings except a negligible set.
  • Related theory: Arithmetic circuits have a more developed theory of depth efficiency, but their established results do not directly apply to convolutional rectifier networks.Arithmetic circuits use sum and product nodes, whereas convolutional rectifier networks use ReLU activation and pooling.
  • Approach: The paper uses generalized tensor decompositions to transform convolutional arithmetic circuits into convolutional rectifier networks and analyze their expressive power.The approach also supports new results concerning depth efficiency.

2. Related Work

Prior depth-efficiency analyses provide substantial results for arithmetic circuits and some ReLU networks, but largely omit convolutional networks. The paper closes this gap by generalizing tensor decompositions.

  • Arithmetic circuits: Arithmetic-circuit research has developed extensive mathematical tools for studying computational complexity and depth efficiency.This literature spans more than five decades and draws on geometry, algebra, analysis, and combinatorics.
  • ReLU networks: ReLU-network analyses establish depth-efficiency examples using combinatorics, semi-algebraic geometry, and Fourier analysis.One result gives Θ(k^3)-layer networks with Θ(1) nodes per layer that require Ω(2^k) nodes at O(k) layers for approximation.
  • Gap: These prior analyses do not account for convolutional networks, so they do not directly address the architecture most commonly used in practice.Convolutional arithmetic circuits were introduced as a related model with linear activation and product pooling.
  • Contribution: The paper generalizes tensor decompositions to apply mathematical machinery from convolutional arithmetic circuits to convolutional rectifier networks.This enables analysis of depth efficiency for convolutional rectifier networks.

3. Generalized Tensor Decompositions

The paper develops generalized tensor decompositions by replacing the standard tensor product with an operator-based generalization. These decompositions retain the weighted-sum and tensor-product structure used by classical decompositions.

  • Tensor basics: A tensor is treated as a multidimensional array whose indexing entries are modes, each with a specified dimension.The tensor space contains all possible configurations of such arrays.
  • Tensor basics: The tensor product combines two tensors into a higher-order tensor by concatenating their modes.For tensors of orders P and Q, the result has order P + Q.
  • Tensor basics: When both inputs are vectors, the tensor product becomes their outer product and produces a rank-1 matrix.For u and v, u ⊗ v = uv^T.
  • Tensor decompositions: Tensor decompositions express tensors through weighted sums and tensor products, including Tucker, CP, and Hierarchical Tucker forms.These decompositions differ in structure but iterate between tensor products and weighted sums.
  • Generalization: Generalized tensor decompositions replace the standard tensor product with ⊗g induced by an associative and commutative binary operator g.The construction uses tensors as inputs and returns a tensor whose modes combine those of the inputs.
  • Scope: The discussion restricts the algebraic definitions to concrete special cases sufficient for the paper’s analysis.This restriction is intended to make the needed definitions easier to grasp.

4. From Networks to Tensors

The analyzed ConvNet receives a collection of input patches, applies a representation followed by hidden convolution-and-pooling layers, and maps the final pooled features to outputs.

  • Input and representation: The input X consists of N patches, each in R^s, representing local regions such as image patches.A 32-by-32 RGB image with 5 × 5 patches can yield N = 1024 and s = 75.
  • Input and representation: The representation applies a generalized convolution, with conventional convolution obtained from affine filtering followed by an activation function.The representation may also be a cascade of convolutional layers with intervening pooling.
  • Hidden layers: Each hidden layer applies a 1×1 convolution with r_l channels and pointwise activation, followed by spatial pooling over non-overlapping windows.The convolution may use shared weights or location-dependent unshared weights.
  • Outputs: The final hidden layer uses global pooling to produce a feature vector, which a dense linear layer maps to Y outputs.The final pooled vector has dimension r_{L−1}.
  • Architecture parameters: The architecture is parameterized by representation functions, pooling-window sizes, weight sharing, and channel counts across representation, hidden, and output layers.Pooling-window sizes determine the number of hidden layers L.

hidden layer L-1

The paper represents shallow and deep ConvNets through generalized tensor decompositions, with activation and pooling choices determining the resulting network family.

  • Architecture: The architecture applies representation functions to input patches, followed by hidden 1×1 convolutions, activation, pooling, and a final linear output layer.The representation may be viewed as a generalized convolution, while hidden layers can use shared or location-specific coefficients.
  • Network families: Linear activation with product pooling yields convolutional arithmetic circuits, whereas ReLU with max or average pooling yields convolutional rectifier networks.These operator choices define the network type analyzed in the paper.
  • Grid tensors: The grid tensor records score-function values on an exponentially large grid formed from sequences of selected templates.This construction enables the subsequent analysis of expressive power and depth efficiency.
  • Tensor representations: A deep ConvNet with size-2 pooling and L = log2 N hidden layers corresponds to a hierarchical generalized tensor decomposition.This factorization generalizes the Hierarchical Tucker decomposition and is called the generalized HT decomposition.
  • Tensor representations: A shallow ConvNet with global pooling corresponds to a generalized CP decomposition of its grid tensor.The decomposition uses hidden-layer channel weights and output weights, generalizing the classic CP decomposition.

5. Capacity Analysis

The capacity analysis studies universality, depth efficiency, and coefficient sharing for shallow and deep convolutional rectifier networks through their grid-tensor representations.

  • Scope: The analysis compares ReLU networks with max or average pooling against linear networks with product pooling using grid tensors.The compared models are shallow networks with global pooling and deep networks with L = log2 N layers.
  • Universality: Universality asks whether networks of unlimited size can realize any score function.The paper treats universality before analyzing depth efficiency and coefficient sharing.
  • Depth efficiency: Depth efficiency concerns functions computed efficiently by deep networks that require super-polynomial size in shallow networks.The section studies when depth provides this computational advantage.
  • Coefficient sharing: Coefficient sharing is analyzed by comparing standard convolutions with the more general locally connected operators.This isolates the effect of tying convolutional coefficients across spatial locations.

5.1. Preliminaries

The preliminaries introduce measure-theoretic and tensor-analytic tools used to analyze generic expressivity and depth efficiency.

  • Measure theory: Lebesgue measure is used to characterize the volume of parameter or tensor sets, including zero-measure exceptional cases.The paper uses these notions when evaluating completeness of depth efficiency.
  • Functional independence: Products of linearly independent functions remain linearly independent over product domains.This functional-analytic fact is used in arguments involving representation functions and grid tensors.
  • Tensor rank: Tensor rank is the minimum number of rank-1 tensors whose sum produces a tensor.For order-2 tensors, this reduces to ordinary matrix rank.
  • Tensor rank: The preliminaries state generic lower and upper rank bounds for tensors with specified mode dimensions.These bounds support later comparisons between tensor representations induced by shallow and deep networks.
  • Tensor rank: Tensor rank is sub-additive under addition and sub-multiplicative under tensor products.Permuting tensor modes does not change rank.

5.2. Templates and Representation Functions

The paper formalizes assumptions on templates and representation functions, then shows that common neuron families can satisfy the required non-degeneracy condition.

  • Assumptions: Non-degeneracy requires that distinct templates admit representation functions whose evaluation matrix F is non-singular.This condition ensures that the template evaluations retain sufficient diversity for the tensor analysis.
  • Representation functions: The standard neuron family fθ(x) = σ(w⊤x + b) satisfies non-degeneracy for sigmoidal or ReLU activations.The proof constructs separating projections and suitable biases for distinct templates.
  • ReLU construction: For ReLU activation, choosing biases to order sign changes makes F lower triangular with non-zero diagonal entries.Therefore, the resulting evaluation matrix is non-singular.
  • Sigmoidal construction: For sigmoidal activation, scaling the separating projection makes F approach a non-singular limiting matrix, so sufficiently large scaling preserves non-singularity.The construction uses α → +∞ to obtain the limiting structure.
  • Template selection: A linearly independent set of continuous representation functions admits templates for which F is non-singular.This follows because the determinant is a non-zero function of the templates.
  • Covering templates: Covering templates make the correspondence from score functions to grid tensors injective for classification purposes.The paper notes that structured compositional data may satisfy this assumption with M ∈ Ω(100).

5.3. Matricization

The paper matricizes grid tensors so tensor decompositions become matrix factorizations that expose rank constraints. These rank bounds are then used to compare shallow and deep convolutional networks.

  • Matricization: Matricization arranges tensor entries into a matrix with odd modes indexing rows and even modes indexing columns.For even-order tensors, the matrix has dimensions (M1·M3·...·MN−1) × (M2·M4·...·MN).
  • Matricization: The Kronecker product is the matrix analogue of the tensor product under matricization.The relation [A ⊗ B] = [A] ⊙ [B] preserves the corresponding tensor operation in matrix form.
  • Generalized products: The generalized Kronecker product applies a function g entrywise to pairs of matrix entries and preserves the matricization correspondence.It satisfies [A ⊗g B] = [A] ⊙g [B].
  • Network decompositions: The matricized generalized CP and HT decompositions represent shallow and deep ConvNet grid tensors, respectively.The resulting expressions provide the matrix forms used throughout the depth-efficiency proofs.
  • Rank comparison: Depth-efficiency analysis compares a lower bound on the deep grid tensor’s matricized rank with an upper bound on the shallow network’s rank.Because the shallow upper bound is linear in its hidden-channel count, deep-network rank yields a lower bound on the shallow width needed for replication.

5.4. Universality

The universality analysis distinguishes pooling schemes: ReLU networks are universal with max pooling under covering-template assumptions, but average pooling remains non-universal even with expanded receptive fields.

  • Definition and setup: Universality asks whether a network can realize or approximate any function when its size is unrestricted.The paper studies this question for convolutional rectifier networks using grid tensors on selected templates.
  • Product pooling: With linear activation and product pooling, the shallow ConvNet is universal when covering templates exist, and the deep ConvNet inherits this universality.The construction reduces to a standard CP decomposition that can express arbitrary tensors with sufficiently large size.
  • Max pooling: With ReLU activation and max pooling, the shallow ConvNet is universal under the assumption that covering templates exist.The generalized CP construction represents arbitrary indicator tensors with Z = 2, giving a sufficient width of Z≥2·M^N.
  • Average pooling: With ReLU activation and average pooling, both shallow and deep ConvNets are not universal.The proof uses low-rank properties of the matricized generalized CP and HT decompositions.
  • Expanded receptive fields: Expanding the convolutional receptive field does not restore universality when windows cover less than half the preceding feature maps.For w·h < N/2+1−log_M N, the ReLU average-pooling network remains non-universal.
  • Fully connected expansion: A fully connected network obtained by expanding the receptive field across the entire spatial extent is universal with ReLU under non-recurring-row and nonzero-column conditions on F.Appropriate hidden and output weights can then make the grid tensor take any value.

5.5. Depth Efficiency

Depth efficiency is complete for convolutional arithmetic circuits but incomplete for ReLU networks with max pooling, although it becomes more prevalent as deep-network width grows. The rank-based analysis also extends the resulting lower bounds from exact realization to arbitrarily close approximation.

  • Depth Efficiency: Depth efficiency is defined as deep networks expressing functions with polynomial size that require super-polynomial size when shallow.The definition presupposes universality: some shallow network size must be able to express the target function.
  • Depth Efficiency: Under linear activation and product pooling, almost all deep-network weight settings yield complete depth efficiency against shallow networks.The result holds with probability one under continuous randomization of the linear weights.
  • Depth Efficiency: Under ReLU activation and max pooling, depth-efficient weight settings exist, but depth efficiency is incomplete because a positive-measure set remains efficiently realizable by shallow networks.The existence result requires the shallow network to have fewer than min{r0, M} hidden channels.
  • Depth Efficiency: Compared with ReLU-max networks, linear-product convolutional arithmetic circuits benefit more from depth’s expressive power.The paper attributes this comparison to complete versus incomplete depth efficiency and presents it as motivation for improving arithmetic-circuit training.
  • Approximation: The rank method establishes lower bounds against arbitrarily-well approximation, not only exact realization.Matricization separates deep and shallow grid tensors by rank and yields a corresponding Frobenius-distance lower bound.

5.6. Shared Coefficients for Convolution

With shared convolutional coefficients, universality is lost for all activation and pooling choices, while depth efficiency remains complete for linear activation with product pooling but incomplete for ReLU with max pooling.

  • Shared generalized tensor decompositions: Weight sharing replaces location-specific 1 × 1 filter coefficients with one coefficient vector per hidden channel and layer.The resulting shallow and deep networks correspond to shared generalized CP and HT decompositions, respectively.
  • Universality: Universality is absent in the shared setting regardless of the activation and pooling operators.This differs from the unshared setting, where ReLU with max pooling is universal but ReLU with average pooling is not.
  • Universality: Shared-weight shallow networks generate symmetric tensors, while shared-weight deep networks generate tensors invariant to swapping their first and second halves.Neither constraint holds for most tensors, so neither architecture is universal.
  • Depth efficiency: Depth efficiency remains complete for linear activation with product pooling under shared coefficients.Almost all randomized deep-network score functions cannot be realized by shallow networks with fewer than min{r0, M} hidden channels.
  • Depth efficiency: ReLU activation with max pooling retains depth efficiency, but not completely, when the deep network uses shared weights.Some deep-network score functions require at least min{r0, M}·2^(M·N/2) shallow hidden channels, while another positive-probability set is realizable with one shallow hidden channel.
  • Overall conclusion: The shared analysis concludes that weight sharing disrupts universality but leaves depth efficiency intact, either completely or incompletely depending on the operators.The conclusion applies to standard convolutions obtained by constraining locally connected linear mappings.

6. Discussion

The paper introduces generalized tensor decompositions to transfer arithmetic-circuit analysis to convolutional rectifier networks and uses them to characterize universality and depth efficiency. It finds max-pooling universality but weaker-than-complete depth efficiency, motivating further work on training convolutional arithmetic circuits.

  • Contributions: Generalized tensor decompositions transform convolutional arithmetic circuits into convolutional rectifier networks and enable arithmetic-circuit tools for analyzing their expressive properties.This constitutes the paper’s two contributions: a construction and new expressiveness results.
  • Universality: Convolutional rectifier networks are universal with max pooling but not with average pooling.If nonlinearity comes solely from ReLU activation, increasing network size alone is insufficient for expressing arbitrary functions.
  • Depth efficiency: Depth efficiency exists in convolutional rectifier networks but is not complete, unlike the complete depth efficiency established for convolutional arithmetic circuits.A positive-measure set of functions generated by deep rectifier networks can be efficiently realized by shallow networks.
  • Implications: The analysis indicates that convolutional rectifier networks are inferior to convolutional arithmetic circuits from the perspective of depth efficiency.The paper presents this as a motivation for investigating arithmetic circuits as alternative deep-learning architectures.
  • Implications: Effective training methods for convolutional arithmetic circuits may enable a provably superior deep-learning architecture that practitioners have overlooked.The paper notes that arithmetic circuits have received less training-focused attention than convolutional rectifier networks.

A. Existence of Covering Templates

The analysis represents network score functions through grid tensors evaluated on combinations of image-patch templates. Covering templates are needed in practically relevant numbers, and natural-image patch statistics motivate their existence for moderate template counts.

  • Grid tensors: A grid tensor records a score function’s values on inputs whose patches are selected from a finite template set.For N patches and M templates, it forms an order-N tensor with template-indexed modes.
  • Covering-template requirement: The construction requires covering templates with counts tied to the first representation layer, so arbitrarily large template sets do not by themselves suffice.The target regime is practical network sizes, including M ∈ Ω(100).
  • Natural-image assumption: Natural-image patch statistics motivate moderate covering-template counts for receptive-field-sized patches.Patches up to 16×16 have been modeled with as few as 64 Gaussian-mixture components, supporting the assumption that local patch appearances are relatively limited.
Loading 1603.00162v2…