Skip to content
The methodOpen data
Back to the collection

Why does deep and cheap learning work so well?

Henry W. Lin, Max Tegmark, David Rolnick

2016 · arXiv

MathematicsMachine learningStatistics & probability
Read the paper
HN score
1
Mentions
12
Readers
8
Months
10
What’s in a score?

From the 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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

12 selected excerpts · 12 total mentions

cs702
Recommendation · rule
As stated by the author, this is necessarily a speculative piece ("assuming that..."), but still worth reading -- as long as you keep that in mind. It makes no sense to criticize it or dismiss it for being speculative, as others have done here! By the way, if you enjoy reading this piece, you might also enjoy really interesting paper coauthored by the same person: "Why does deep and cheap learning work so well?," available at https://arxiv.org/abs/1608.08225 -- it posits that deep learning works well because of the particular structure of the laws of physics in the universe in which we happen to live.
Original comment Shut up and calculate: an extreme mathematical universe
laclar
Neutral mention · rule
As for over-fitting, I am not in my 50s, and I knew what over-fitting was from my undergrad (or highschool?). The idea is very commonplace in engineering. Numerous times, when encountering a "new term" in a different field, such as overfitting in machine learning, I have found myself thinking in overly complicated ways, because I never thought that what I considered so simple could be the central point of discussion. Perhaps the physicists who could not describe what over-fitting was, were in the same shoes. The other unfortunate scenario is that the interviewers expect certain responses that are just not the generalized things one knows of. But regarding other matters, I…
Read the full comment
hardly doubt that the sentiment you are suggesting is lost on all. One point of view is that the self affirmation bias is easy to come these days. The material on basics of machine learning are beyond trivial, but the hype makes money. Even traditional engineering does that to some extent, at least that's what I saw in my education. Same goes for basic finance. I see hype attempts in non-"computer science" engineering research, which amounts to noise. Some writers are oblivious, some are doing it for money. The problem is these days every noise is amplified, and at first I was confusing noise for signal. Particularly at a period when I was practically doing solo research despite having colleagues. All being said, and I could be too quick or too short on this, large scale computation may automate many aspects of our lives, and funding goes for automation whereas mathematical modeling does not automate things in and of itself. As for new mathematics, I doubt serious researchers would disagree on looking for more. I came across this today, you might recognize one of the names, haven't read it and doubt will find the time for a while, but perhaps it could be of interest to you. https://arxiv.org/abs/1608.08225
Original comment How I Transitioned from Physics Academia to the ML Industry
colorincorrect
Neutral mention · rule
Perhaps this paper provides an explanation? https://arxiv.org/pdf/1608.08225.pdf "The exceptional simplicity of physics-based functions hinges on properties such as symmetry, locality, compositionality and polynomial log-probability, and we explore how these properties translate into exceptionally simple neural networks approximating both natural phenomena such as images and abstract representations thereof such as drawings."
Original comment Unreasonable Ineffectiveness of Machine Learning in Computer Systems Research
epberry
Neutral mention · rule
Part of me says that you are correct on all of these points. However I think you went too far on 3. Experimentation does not always follow theory in science. I would argue that many of the great discoveries of physics in the 20th century followed directly from startling results of experiments conducted at the end of the 19th century (the photoelectric effect for example). I agree that there seems to be an awful lot of experimenting going on and that hardware and large datasets have helped tremendously but there are also many researchers poking and prodding at deep learning theory [1, 2]. So from a glass-half-full perspective we have rapid (sometimes iterative) experimentation coupled with yawning gaps in theory to explain surprising results. In other words, the opposite of previous AI booms and a big reason to be optimistic despite all the hype. [1] https://arxiv.org/pdf/1410.3831v1.pdf [2] https://arxiv.org/abs/1608.08225
Original comment OpenAI Universe
BickNowstrom
Neutral mention · rule
1. Games are great for studying intelligent agent behavior and intelligence itself. An intelligent agent will find hidden abstractions and patterns in a large dimensionality. Language understanding, vision, decision science, solving long-temporal credit assignment etc. all are present. Russell & Norvig (2003) considered goal-directed behavior as the essence of intelligence. Also see possibly the first papers on AI and their focus on parlor games: https://en.wikipedia.org/wiki/Theory_of_Games_and_Economic_B... & http://www.loebner.net/Prizef/TuringArticle.html 2. This platform will provide a test bed for AI algo's and help "democratize" AI. One does not need to set up…
Read the full comment
their own platform. One can compare approaches. One can learn from other implementations running on a common ground. Being resource constrained forces one to be more creative and this paves the way for more energy-friendly methods. Sure, a high school student will not dominate the power houses like DeepMind et al. But the high school student can get up and running in a week or few days. 3. https://arxiv.org/abs/1608.08225 Physics and Deep Learning are well entwined. Deep Learning certainly is a big idea, up there with VC theory and boosting. It exists for decades now, I agree the more recent incarnation was made possible with more computing power and better bigger datasets, and relies less on new tricks. Yet, still tricks are being invented in the recent years that have majorly contributed to better generalization. Dropout being one. DL, and especially the relevant Deep Reinforcement Learning, is not just GPU's, but a lot of new (and budding) theory. One can run Random Forests (and other approaches) on CUDA too. The Neural Turing Machine heralded a whole new, intellectually deep and stimulating, field in Deep Learning, and we haven't seen the best of it yet. There are also fields, like vision, where the other approaches are significantly underperforming relative to DL. Try to train a SVM or RF on ImageNet. Also, one is not required to use DL for your agent. Experiment with the classic approaches and see which is better (https://arxiv.org/abs/1603.04119). I actually shared some of your concern, not for AI research, but for game development. I thought it was very hard to actually get a good job in that field. Then the mobile game market started booming, and indy developers could make a living. AI has got the backing of all the major players in industry. Instead of pipe dreams and philosophical meanderings, we have actually business-value adding working models now. It is not going anywhere soon. If all else fails, you remain a good coder or data analyst with a lot of automation skills.
Original comment OpenAI Universe
sgt101
Neutral mention · rule
No one really knows, there was a paper by Max Tegmark on HN yesterday with some new ideas and results, but I haven't had time to read it yet. http://arxiv.org/abs/1608.08225 The other responses to your question in this thread are as good I as could give you, but I would feel like I am recounting ideas that may be true but for which there is little evidence.
Original comment Is artificial intelligence permanently inscrutable?
cs702
Neutral mention · rule
Yes, I agree: In practice, all learning tasks have a common underlying structure because our physical reality can behave only in certain ways, determined by the symmetries in our universe. However, as far as I know, no one has formally specified or proved this commonality in learning tasks. The most persuasive argument I've seen for this view -- our view -- is laid out in this paper by Lin, Tegmark, and Rolnick, written between 2016 and 2017 (although it feels like it was written a century ago!): https://arxiv.org/abs/1608.08225
Original comment A Cookbook of Self-Supervised Learning
mikhailfranco
Neutral mention · rule
My random stream-of-consciousness reference reactions ... Tegmark & Lin's discussion of how deep learning maps onto the physical world: Why does deep and cheap learning work so well? [1][2] The work of Aerts et al. more than 10 years ago, including how vector space models of human categorization show QM structure [3]. Lucien Hardy's exquisite teasing out of the difference between classical and quantum probability: Quantum Theory From Five Reasonable Axioms [4] It turns out that the innovation, power and strangeness of QM is related to separating physical processes into: 1. Linear continuous unitary reversible evolution relying on complex amplitudes (wavefunction…
Read the full comment
propagation). 2. Non-linear discontinuous irreversible 'collapse' or 'measurement' or 'entanglement' or 'correlated branching', with probabilities based on the Born Rule (real values from the square of wave function amplitudes). Neural nets also decompose a problem into successive alternating layers of reversible continuous functions and discrete irreversible categorical decisions (e.g. softmax/sigmoid logistic classifiers). An even more obscure tangent is that most of the financial market is now constructed from 'options', which track continuous values with a continuous payoff, but offer a choice of execution to collapse the option and create a real financial result, e.g. see N.N.Taleb's dicussion of optionality [5]. [1] http://arxiv.org/pdf/1608.08225.pdf [2] http://www.youtube.com/watch?v=5MdSE-N0bxs [3] http://en.wikipedia.org/wiki/Diederik_Aerts#Quantum_structur... [4] http://arxiv.org/abs/quant-ph/0101012 [5] http://fooledbyrandomness.com/ConvexityScience.pdf
Original comment Deep Learning and Quantum Entanglement [pdf]
cs702
Neutral mention · rule
Hmm... it could very well be true. Perhaps deep networks work well because they learn to memorize "the most common patterns of auto-correlation" they see in the training data at different levels of function composition. In fact, we do this explicitly in convolutional layers, which by design learn to represent every input sample as a combination of a finite number of fixed-size square filters. ...and the reason why deep networks might be "generalizing" so well is because not all distributions of natural data are equally likely! In practice, objects with the same or similar labels tend to lie on or close to lower-dimensional manifolds embedded in data space. ...and this…
Read the full comment
concentration of natural data distributions might be a result of the laws of Physics of the universe in which we happen to live: https://arxiv.org/abs/1608.08225 So, yes, deep learning could very well be a really fancy form of memorization. I hadn't thought of it in this way before. Very interesting :-)
Original comment Understanding deep learning requires re-thinking generalization
cs702
Neutral mention · rule
Houshalter: the no-free-lunch theorem assumes that all possible "real world" problems are equally probable. That does not appear to be true in theory (due to the laws of physics, e.g., see https://arxiv.org/abs/1608.08225 ) nor in practice (e.g., in complicated AI-type problems, the objects of interest always seem to lie on/near lower-dimensional manifolds embedded in a high-dimensional input space).
Original comment The Neural Network Zoo

Keep following the thread.

More in Mathematics

More from the same topics.

1994arXiv

On proof and progress in mathematics

William P. Thurston

In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.

Mathematics
29 mentions21 months
9HN score