Why does deep and cheap learning work so well?

Abstract

We show how the success of deep learning could depend not only on mathematics but also on physics: although well-known mathematical theorems guarantee that neural networks can approximate arbitrary functions well, the class of functions of practical interest can frequently be approximated through "cheap learning" with exponentially fewer parameters than generic ones. We explore how properties frequently encountered in physics such as symmetry, locality, compositionality, and polynomial log-probability translate into exceptionally simple neural networks. We further argue that when the statistical process generating the data is of a certain hierarchical form prevalent in physics and machine-learning, a deep neural network can be more efficient than a shallow one. We formalize these claims using information theory and discuss the relation to the renormalization group. We prove various "no-flattening theorems" showing when efficient linear deep networks cannot be accurately approximated by shallow ones without efficiency loss, for example, we show that $n$ variables cannot be multiplied using fewer than 2^n neurons in a single hidden layer.

arXiv commentReplaced to match version published in Journal of Statistical Physics: https://link.springer.com/article/10.1007/s10955-017-1836-5 Improved refs & discussion, typos fixed. 16 pages, 3 figs

References in corpus (10)

• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• A Line of Sight Approach to Cosmic Microwave Background Anisotropies
• A class of quantum many-body states that can be efficiently simulated
• A high resolution foreground cleaned CMB map from WMAP
• Estimating the Power Spectrum of the Cosmic Microwave Background
• Dimensionless constants, cosmology and other dark matters
• How to measure CMB power spectra without losing information
• Planck 2013 results. XII. Component separation
• How to make maps from CMB data without losing information
• First Year Wilkinson Microwave Anisotropy Probe (WMAP) Observations: Data Processing Methods and Systematic Errors Limits

Cited by in corpus (114)

• Quantum Convolutional Neural Networks
• Recent Advances and Applications of Deep Learning Methods in Materials Science
• Parameterized quantum circuits as machine learning models
• A high-bias, low-variance introduction to Machine Learning for physicists
• Deep physical neural networks enabled by a backpropagation algorithm for arbitrary physical systems
• Social physics
• The Challenge of Machine Learning in Space Weather Nowcasting and Forecasting
• Continuous-variable quantum neural networks
• Hierarchical quantum classifiers
• Machine Learning Topological States
• Image sensing with multilayer, nonlinear optical neural networks
• Equivalence of restricted Boltzmann machines and tensor network states
• Identifying Quantum Phase Transitions using Artificial Neural Networks on Experimental Data
• Approximating quantum many-body wave-functions using artificial neural networks
• Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations
• A test case for application of convolutional neural networks to spatio-temporal climate data: Re-identifying clustered weather patterns
• Training convolutional neural networks to estimate turbulent sub-grid scale reaction rates
• Mutual Information, Neural Networks and the Renormalization Group
• Deep learning and the Schrödinger equation
• Quantum Machine Learning for Chemistry and Physics
• Machine Learning of Explicit Order Parameters: From the Ising Model to SU(2) Lattice Gauge Theory
• Neural Network Renormalization Group
• Tree Tensor Networks for Generative Modeling
• Review: Deep Learning in Electron Microscopy
• Discriminative Cooperative Networks for Detecting Phase Transitions
• Information Perspective to Probabilistic Modeling: Boltzmann Machines versus Born Machines
• Deep Learning and AdS/CFT
• Machine Learning for Condensed Matter Physics
• Learning to fail: Predicting fracture evolution in brittle material models using recurrent graph convolutional neural networks
• Neural network wave functions and the sign problem
• Applying Deep Learning to Fast Radio Burst Classification
• Machine Learning Spatial Geometry from Entanglement Features
• Scale-invariant Feature Extraction of Neural Network and Renormalization Group Flow
• Supervised Learning with Projected Entangled Pair States
• How deep is deep enough? -- Quantifying class separability in the hidden layers of deep neural networks
• Machine Learning meets Quantum Foundations: A Brief Survey
• Sleep-wake classification via quantifying heart rate variability by convolutional neural network
• A prediction and behavioural analysis of machine learning methods for modelling travel mode choice
• Efficient Modelling of Trivializing Maps for Lattice ${\varphi }^4$ Theory Using Normalizing Flows: A First Look at Scalability
• Parameters Estimation for the Cosmic Microwave Background with Bayesian Neural Networks
• Improving Galaxy Clustering Measurements with Deep Learning: analysis of the DECaLS DR7 data
• The Presence and Absence of Barren Plateaus in Tensor-network Based Machine Learning
• Machine Learning Holographic Mapping by Neural Network Renormalization Group
• Matrix Product Operators for Sequence to Sequence Learning
• Revisiting Efficient Multi-Step Nonlinearity Compensation with Machine Learning: An Experimental Demonstration
• Generative Tensor Network Classification Model for Supervised Machine Learning
• Drawing Phase Diagrams of Random Quantum Systems by Deep Learning the Wave Functions
• Thermodynamics and Feature Extraction by Machine Learning
• Partial Scanning Transmission Electron Microscopy with Deep Learning
• Precision Machine Learning
• Improving Electron Micrograph Signal-to-Noise with an Atrous Convolutional Encoder-Decoder
• Efficient approximation of high-dimensional functions with neural networks
• Neural network reconstructions for the Hubble parameter, growth rate and distance modulus
• Is Deep Learning a Renormalization Group Flow?
• Deep learning black hole metrics from shear viscosity
• Renormalization Group Flow as Optimal Transport
• Extracting Critical Exponent by Finite-Size Scaling with Convolutional Neural Networks
• Enforcing constraints for interpolation and extrapolation in Generative Adversarial Networks
• Geometry of energy landscapes and the optimizability of deep neural networks
• Observational cosmology with Artificial Neural Networks
• Machine-Learning Non-Conservative Dynamics for New-Physics Detection
• Hierarchical quantum circuit representations for neural architecture search
• Identifying Product Order with Restricted Boltzmann Machines
• Provably scale-covariant continuous hierarchical networks based on scale-normalized differential expressions coupled in cascade
• Explicitly antisymmetrized neural network layers for variational Monte Carlo simulation
• Bayesian Renormalization
• The Loss Surface of XOR Artificial Neural Networks
• Impossibility Results in AI: A Survey
• Language Design as Information Renormalization
• Variational Neural-Network Ansatz for Continuum Quantum Field Theory
• Neural Network flows of low q-state Potts and clock Models
• Neural Monte Carlo Renormalization Group
• Do Neural Nets Learn Statistical Laws behind Natural Language?
• A Hyperparameter Study for Quantum Kernel Methods
• An Active Galactic Nucleus Recognition Model based on Deep Neural Network
• RG-Flow: A hierarchical and explainable flow model based on renormalization group and sparse prior
• Deep neural networks have an inbuilt Occam's razor
• Warwick Electron Microscopy Datasets
• Three Learning Stages and Accuracy-Efficiency Tradeoff of Restricted Boltzmann Machines
• Decomposing neural networks as mappings of correlation functions
• On the descriptive power of Neural-Networks as constrained Tensor Networks with exponentially large bond dimension
• Dark energy reconstruction analysis with artificial neural networks: Application on simulated Supernova Ia data from Rubin Observatory
• Entropy Regularized Reinforcement Learning Using Large Deviation Theory
• Statistical modeling of equilibrium phase transition in confined fluids
• Wavelet Conditional Renormalization Group
• Machine learning algorithms based on generalized Gibbs ensembles
• A Flexible Framework for Anomaly Detection via Dimensionality Reduction
• Short sighted deep learning
• Investigation of Finite-size 2D Ising Model with a Noisy Matrix of Spin-Spin Interactions
• Thermodynamics of the Ising model encoded in restricted Boltzmann machines
• Quantum System Compression: A Hamiltonian Guided Walk Through Hilbert Space
• Identification of Invariant Sensorimotor Structures as a Prerequisite for the Discovery of Objects
• Post-synaptic potential regularization has potential
• Deep Neural Networks for Automatic Speaker Recognition Do Not Learn Supra-Segmental Temporal Features
• Exploring explicit coarse-grained structure in artificial neural networks
• Categorical Representation Learning and RG flow operators for algorithmic classifiers
• Machine Learning S-Wave Scattering Phase Shifts Bypassing the Radial Schrödinger Equation
• Tensor networks and efficient descriptions of classical data
• Quaternion-based machine learning on topological quantum systems
• Comparison of generalised additive models and neural networks in applications: A systematic review
• Machine learning, quantum chaos, and pseudorandom evolution
• When and Why Metaheuristics Researchers Can Ignore "No Free Lunch" Theorems
• Lateral predictive coding revisited: Internal model, symmetry breaking, and response time
• On functions computed on trees
• Constructive expansion for quartic vector fields theories. I. Low dimensions
• On the approximation of functions by tanh neural networks
• inclusiveAI: A machine learning representation of the $F_2$ structure function over all charted $Q^2$ and $x$ range
• An Enquiry on similarities between Renormalization Group and Auto-Encoders using Transfer Learning
• Efficiency of the hidden fermion determinant states Ansatz in the light of different complexity measures
• Dynamic neuron approach to deep neural networks: Decoupling neurons for renormalization group analysis
• Dynamical transition in controllable quantum neural networks with large depth
• Response time of lateral predictive coding and benefits of modular structures
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• Exact maximum-entropy estimation with Feynman diagrams