Deep Learning and Hierarchal Generative Models

Abstract

It is argued that deep learning is efficient for data that is generated from hierarchal generative models. Examples of such generative models include wavelet scattering networks, functions of compositional structure, and deep rendering models. Unfortunately so far, for all such models, it is either not rigorously known that they can be learned efficiently, or it is not known that "deep algorithms" are required in order to learn them. We propose a simple family of "generative hierarchal models" which can be efficiently learned and where "deep" algorithm are necessary for learning. Our definition of "deep" algorithms is based on the empirical observation that deep nets necessarily use correlations between features. More formally, we show that in a semi-supervised setting, given access to low-order moments of the labeled data and all of the unlabeled data, it is information theoretically impossible to perform classification while at the same time there is an efficient algorithm, that given all labelled and unlabeled data, perfectly labels all unlabelled data with high probability. For the proof, we use and strengthen the fact that Belief Propagation does not admit a good approximation in terms of linear functions.

References in corpus (2)

• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
• A Probabilistic Theory of Deep Learning

Cited by in corpus (7)

• The Gaussian equivalence of generative models for learning with shallow neural networks
• A Provably Correct Algorithm for Deep Learning that Actually Works
• On Data-Augmentation and Consistency-Based Semi-Supervised Learning
• Computational Separation Between Convolutional and Fully-Connected Networks
• The non-tightness of the reconstruction threshold of a 4 states symmetric model with different in-block and out-block mutations
• The staircase property: How hierarchical structure can guide deep learning
• From Boltzmann Machines to Neural Networks and Back Again