On the Expressive Power of Deep Learning: A Tensor Analysis
  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.
