On the Expressive Power of Deep Learning: A Tensor Analysis

By Nadav Cohen, Or Sharir, Amnon Shashua. 2015

493 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

Citations in the corpus

Robust Large Margin Deep Neural Networks (2016, background): “Similarly, the authors in [11] conclude that functions implemented by DNNs are exponentially more expressive than functions implemented by shallow networks.”
AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, background): “The choice of norm p here is left to the learner and will determine both the sparsity of the network and the accompanying learning guarantee of the resulting model.”
On the Expressive Power of Deep Neural Networks (2016, background): “For any generic trajectory x ( t ) , we can thus deﬁne T ( F A ( x ( t ); W )) to be the number of transitions undergone by output neurons (i.e. the number of linear regions) as we sweep the input x ( t ) .”
The Power of Depth for Feedforward Neural Networks (2015, background): “Delalleau and Bengio [2011], Martens and Medabalimi [2014] and Cohen et al. [2015] show strong approximation hardness results for certain neural network architectures (such as polynomials or representing a certain tensor structure), which are however fundamentally different than the standard neural…”
Demystifying Parallel and Distributed Deep Learning (2018, background): “ after another, we create deep networks (as shown in Fig.7b) that can approximatearbitrarilycomplex continuousfunctions. Whiletheexact classofexpressiblefunctions is currently an open problem, results[47,59] show that neural network depth can reduce breadth requirements exponentially with each addit”
Inductive Bias of Deep Convolutional Networks through Pooling Geometry (2016, methodology): “The convolutional arithmetic circuit architecture on which we focus in this paper is the one considered in [8], portrayed in ﬁg.”
On the Ability of Neural Nets to Express Distributions (2017, background): “Eldan and Shamir (Eldan and Shamir (2015)) show a certain radial function can be approximated by a 3-layer neural net but not by a 2-layer neural net with a subexponential number of nodes.”
The Expressive Power of Neural Networks: A View from the Width (2017, background): “In fact, as pointed out in [2], proving existence is inevitable; There is always a positive measure of network parameters such that deep nets can’t be realized by shallow ones without substantially larger size.”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions (2016, unknown): “5 Links between TNs and Machine Learning models Table 4 summaries the connections of tensor networks with graphical and neural network models in machine learning and statistics [54,55,64,65,138,192,198, 285].”
Long-term Forecasting using Tensor-Train RNNs (2017, background): “For example, (Cohen et al., 2016) shows convolutional neural networks have equivalence to hierarchical tensor factorizations.”
Transferring Inductive Biases through Knowledge Distillation (2020, background): “, the student model can realize functions that are realizable by the teacher [3], while the teacher has a preference inductive bias so that the desired solutions are easily learnable for the teacher [32].”
A high-bias, low-variance introduction to Machine Learning for physicists (2018, unknown): “More recently, it has been shown that CNNs can be thought of as performing tensor decompositions on the data similar to those commonly used in numerical methods in modern quantum condensed matter (Cohen et al., 2016).”
TensorLy: Tensor Learning in Python (2016, background): “…and compositional function spaces in order to learn latent variable models (e.g., mulitiview mixture model, Gaussian mixtures, Independent Component Analysis) [3], train deep neural networks with theoretical guarantees [13], and also theoretically analyze their impressive empirical performance [8].”
Universal approximations of permutation invariant/equivariant functions by deep neural networks (2019, background): “There exists classes of deep convolutional ReLU networks that cannot be realized by shallow ones if the size is no more than an exponential bound [Cohen et al. , 2016].”
Representation Benefits of Deep Feedforward Networks (2015, background): “Since buckets are intervals and signs must alternate within any such interval, at least a third of the points in any of these buckets are labeled incorrectly by ˜ f .”
Neural Networks with Finite Intrinsic Dimension have no Spurious Valleys (2018, background): “Whereas several authors have studied this question from the lens of approximation theory [9, 8, 5] by focusing on specific aspects of the parameterisation, e.”
ResNet with one-neuron hidden layers is a Universal Approximator (2018, background): “Consequently, theoretically analyzing the benefit of depth has gained much attention in the recent literature [31, 6, 9, 32, 23, 20, 25].”