PaperlayerView exact revision on arXiv

Source-linked AI summary

Expressive power of recurrent neural networks

Valentin Khrulkov, Alexander Novikov, Ivan Oseledets

arXiv:1711.00811v2cs.LG

TL;DR

The paper addresses the lack of an expressive-power result for recurrent neural networks, connecting them to Tensor Train decomposition and proving a width bound for shallow emulation. It also compares TT networks with other tensor-based architectures and reports numerical evidence for a special equal-core case.

  • Problem

    Although expressive-power results existed for deep CNNs, no corresponding result was available for recurrent neural networks.

    Source: §1 · p. 1

  • Method

    The paper connects recurrent neural networks to Tensor Train decomposition and proves an expressive-power theorem for that representation.

    Source: §1 · p. 1

  • Results

    Exactly emulating a recurrent neural network requires a shallow non-recurrent architecture of exponentially larger width.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The paper compares expressive power across recurrent TT, convolutional HT, and shallow CP networks.

    Source: §1 · p. 2

    For equal TT-cores, the theorem is hypothesized rather than analytically established; the authors leave a maximal-rank example for future work and report numerical verification.

    Source: §5 · p. 8

Abstract

from arXiv · show

Deep neural networks are surprisingly efficient at solving practical tasks, but the theory behind this phenomenon is only starting to catch up with the practice. Numerous works show that depth is the key to this efficiency. A certain class of deep convolutional networks -- namely those that correspond to the Hierarchical Tucker (HT) tensor decomposition -- has been proven to have exponentially higher expressive power than shallow networks. I.e. a shallow network of exponential width is required to realize the same score function as computed by the deep architecture. In this paper, we prove the expressive power theorem (an exponential lower bound on the width of the equivalent shallow network) for a class of recurrent neural networks -- ones that correspond to the Tensor Train (TT) decomposition. This means that even processing an image patch by patch with an RNN can be exponentially more efficient than a (shallow) convolutional network with one hidden layer. Using theoretical results on the relation between the tensor decompositions we compare expressive powers of the HT- and TT-Networks. We also implement the recurrent TT-Networks and provide numerical evidence of their expressivity.

1 INTRODUCTION

The introduction frames expressive power as a way to study why deep networks can be efficient, while noting that recurrent networks lacked a corresponding result. The paper connects RNNs to Tensor Train decomposition and proves an exponential width requirement for shallow exact emulation.

1 INTRODUCTION

  • No expressive-power result for recurrent neural networks existed, despite a prior result showing deep CNNs can be exponentially more expressive than shallow counterparts.The CNN result is tied to the Hierarchical Tucker decomposition.Source: §1 · p. 1
  • The paper connects recurrent neural networks with Tensor Train decomposition.Source: §1 · p. 1, Figure 1 · p. 2
  • Exactly emulating a recurrent neural network requires a shallow non-recurrent architecture of exponentially larger width.Source: §1 · p. 1
  • The paper compares the expressive power of recurrent TT, convolutional HT, and shallow CP networks.Source: §1 · p. 2

2 DEEP LEARNING AND TENSOR NETWORKS

This section situates tensor decompositions as a way to represent neural-network score functions without storing full weight tensors. It describes patch-based image inputs and feature maps, then relates tensor-form score functions to prior work.

2 DEEP LEARNING AND TENSOR NETWORKS

  • Images are represented as ordered sequences of possibly overlapping, vectorized patches; Figure 2 illustrates 7 × 7 patches from a 28 × 28 image arranged as a 49 × 16 matrix.Source: §2 · p. 2, Figure 2 · p. 2
  • Each patch is mapped by a shared affine transformation followed by a pointwise activation, resembling a convolutional feature map.The feature map is fθ(x) = σ(Ax + b).Source: §2 · p. 2
  • The section reviews score functions formed by an inner product between a feature representation and a trainable weight tensor, with universal representation as feature dimension grows.Related score functions are also noted in Novikov et al. (2016); Stoudenmire & Schwab (2016).Source: §2 · p. 3
  • Tensor decompositions reduce the degrees of freedom needed to represent weight tensors, and their ranks measure network complexity and representation capacity.The section identifies TT networks with recurrent-type architectures and states that they have greater representation power than shallow CP networks.Source: §2 · p. 3

3 TENSOR FORMATS REMINDER

This section reviews tensor formats and their ranks, which provide compact representations and measures of complexity for the later network comparisons.

3 TENSOR FORMATS REMINDER

  • A tensor is a multidimensional array, and matricization reshapes it into a matrix after dividing its axes into two groups.Source: §3 · p. 3

3.1 CANONICAL

  • The CP decomposition expresses a tensor using rank-one components, and its minimum number of components is the CP-rank.Source: §3.1 · p. 3
  • A rank-one CP tensor has separated modes; storing a tensor takes O(n^d) memory versus O(dnr) for its CP representation.Source: §3.1 · p. 3
  • Determining exact CP-rank and finding a CP decomposition are NP-hard, while approximation by a lower-CP-rank tensor is ill-posed.Source: §3.1 · p. 3

3.2 TENSOR TRAIN

  • In TT format, each tensor entry is computed from a sequence of TT-cores, whose minimal intermediate dimensions are the TT-ranks.Source: §3.2 · pp. 3–4
  • For fixed indices, the TT entry computation is a product of matrices; storing a tensor in TT format requires O(dnr^2) memory and decomposition uses sequential SVDs.The passage describes this SVD-based construction as more numerically stable than CP format.Source: §3.2 · p. 4

3.3 HIERARCHICAL TUCKER

  • The Hierarchical Tucker format generalizes TT and is defined using a dimension tree.Source: §3.3 · p. 4

4 ARCHITECTURES BASED ON TENSOR DECOMPOSITIONS

The section links tensor decompositions to neural-network architectures, including a recurrent architecture whose TT ranks determine its width. It also frames expressive-power comparisons among TT, CP, and HT networks in terms of decomposition rank.

4 ARCHITECTURES BASED ON TENSOR DECOMPOSITIONS

  • The proposed recurrent network computes score functions using bilinear units, with the first unit linear and the final output a scalar.At each step, the input representation and preceding unit output feed the next unit; the architecture has multiplicative connections and no nonlinearities.Source: §4 · p. 5
  • The network realizes the Tensor Train decomposition of the weight tensor, and its TT ranks correspond to network width.Each bilinear unit's output size is the corresponding TT rank.Source: §4 · p. 5
  • A CP-Network uses multilinear units for individual summands and a summation node; its decomposition rank corresponds to shallow-network width.The CP architecture has one hidden layer.Source: §4 · p. 5
  • An HT-Network uses a binary tree of bilinear internal units and linear leaves, with ranks given by intermediate-unit output sizes.Inputs enter at the leaves and data passes to the root, which outputs a number.Source: §4 · p. 5
  • The section compares how complex CP- or HT-Networks must be to realize a TT-Network's score function, using decomposition rank as the complexity measure.Table 1 aligns tensor-analysis terms with deep-learning terminology.Source: §4 · p. 6, Table 1 · p. 6

5 THEORETICAL ANALYSIS

The section proves that almost every tensor in the stated Tensor Train format has exponentially large CP-rank, implying that an equivalent shallow CP network can require exponentially greater width. It also gives a concrete network example and reports numerical checks of a related hypothesis for equal TT-cores.

Theoretical analysis

  • With probability 1, a random d-dimensional tensor in TT format with ranks r and modes n has exponentially large CP-rank, while TT-rank never exceeds CP-rank.The theorem considers even d, equal mode sizes, and equal intermediate ranks; its exceptional set has zero Lebesgue measure.Source: §5 · pp. 6–8
  • The proof constructs a TT-rank-bounded tensor whose alternating-axis matricization contains an identity submatrix of size q^(d/2) × q^(d/2), yielding CP-rank at least q^(d/2).Here q = min{n, r}; the matricization rank lower-bounds CP-rank.Source: §5 · pp. 6–8
  • The result means that, outside a negligible set, the equivalent CP network for a TT network has exponentially large width.The paper frames the comparison in terms of the rank of the corresponding tensor decomposition as a measure of network complexity.Source: §5 · pp. 6, 8

Example that requires exponential width in a shallow network

  • For a similarity function on d input vectors, a TT network of width n computes the example, whereas the equivalent CP network requires n^(d/2) terms and width.The TT network uses the input order x1, x_(d/2+1), …, x_(d/2), xd.Source: §5 · p. 8

The case of equal TT-cores

  • For equal intermediate TT-cores, the authors hypothesize that the theorem still holds and report numerical checks on d = 6 tensors across n = 2–10 and r = 2–20.They checked 1,000 examples for each parameter combination and leave an analytical maximal-rank example to future work.Source: §5 · p. 8

6 EXPERIMENTS

The experiments test whether TT-Networks retain their theoretical expressive advantage on data, where optimization, natural-data structure, and feature maps may affect the comparison. On CIFAR-10, the TT-Network's advantage over the CP-Network is only polynomial in practice.

6 EXPERIMENTS

  • The experiments examine whether CP-Networks need exponentially greater width to match TT-Network accuracy, while noting that natural data, optimization, and feature maps may separate theory from practice.Training selected the best run by training loss across learning rates, using Adam and batch size 32.Source: §6 · p. 9
  • On the moons and circles datasets, TT-Networks implemented nontrivial decision boundaries.Each example's two features were fed as two patches.Source: §6 · p. 9
  • On MNIST, both network types reached 1.0 train accuracy and 0.95 test accuracy without regularizers, or 0.98 test accuracy with dropout 0.8 applied to each patch.The authors describe MNIST as potentially too simple for drawing conclusions, but use it as a sanity check.Source: §6 · p. 9
  • On CIFAR-10, the TT-Network reached 0.45 test accuracy versus 0.2 for the CP-Network, with only a polynomial practical advantage.No regularizers were used in this comparison.Source: §6 · p. 9
  • On CIFAR-10, without regularizers, the best test accuracy achieved was 0.45 for the TT-Network and 0.2 for the CP-Network; TT-Network expressive power was only polynomially better.Source: §6 · p. 9

7 RELATED WORK

Prior tensor-decomposition analyses of depth efficiency focused on feedforward networks, while this paper addresses recurrent architectures. Related practical models and concurrent RNN work differ in the models or questions they consider.

7 RELATED WORK

  • Earlier tensor-decomposition analyses of depth efficiency focused on feedforward networks; the concurrent RNN study analyzed a different class of recurrent models.The concurrent work applied TT decomposition to model high-order interactions of previous hidden states (Yu et al., 2017).Source: §7 · pp. 9–10
  • Novikov et al. (2016) and Stoudenmire & Schwab (2016) proposed models implementing Eq. (2) with a predefined, non-learnable feature map.The paper contrasts those practical models with its theoretical analysis.Source: §7 · p. 10
  • Wu et al. (2016) explored multiplicative recurrent connections, interpretable as TT-Networks with shared bilinear maps and imposed low-rank structure.Source: §7 · p. 10

8 CONCLUSION

The conclusion presents the RNN–Tensor Train connection as the basis for an expressive-power theorem, while identifying worst-case analysis and ignored optimization issues as limitations. Future work would address optimization and extend the analysis to recurrent networks with nonlinearities.

8 CONCLUSION

  • The expressive-power theorem states that a shallow network of exponentially large width is required to mimic a recurrent neural network.Source: §8 · p. 10
  • The analysis is worst-case and does not account for optimization issues.Source: §8 · p. 10
  • Future work would use the Riemannian geometry of fixed-rank TT tensors to address optimization and extend the analysis to nonlinear recurrent connections.Source: §8 · p. 10

Related papers

Loading 1711.00811v2…