HackerPapers

arXiv:1608.08225cond-mat.dis-nn

Why does deep and cheap learning work so well?

Henry W. Lin, Max Tegmark, David Rolnick

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 comments
Replaced 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
Journal reference
DOI
doi:10.1007/s10955-017-1836-5
Subjects
cond-mat.dis-nnDisordered Systems and Neural Networks cs.LGMachine Learning cs.NENeural and Evolutionary Computing stat.MLMachine Learning (Statistics)

On Hacker News

Linked by 9 identifiable commenters in 13 comments across 12 threads, from Sep 2016 to Apr 2023. Found in 4 HN submissions from Aug 2016 to Oct 2019. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments12 threads

  1. A Cookbook of Self-Supervised Learning 1 comment

    • 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…

      cs702View on HNParent context

  2. Why deep learning works even though it shouldn’t 1 comment

    • Another interesting explanation for deep learning's success in the physical world: Why does deep and cheap learning work so well? Max Tegmark et al., https://arxiv.org/abs/1608.08225

      mikhailfrancoView on HNParent context

  3. How I Transitioned from Physics Academia to the ML Industry 1 comment

    • 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…

      laclarView on HNParent context

  4. Why does deep and cheap learning work so well? 1 comment

    • Here's an HTML version of the paper if you're on a phone: https://www.arxiv-vanity.com/papers/1608.08225/

      bfirshView on HNParent context

  5. Shut up and calculate: an extreme mathematical universe 1 comment

    • 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…

      cs702View on HNParent context

  6. Deep Learning and Quantum Entanglement [pdf] 1 comment

    • 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…

      mikhailfrancoView on HNParent context

  7. Understanding deep learning requires re-thinking generalization 1 comment

    • 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…

      cs702View on HNParent context

  8. Unreasonable Ineffectiveness of Machine Learning in Computer Systems Research 1 comment

    • 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…

      colorincorrectView on HNParent context

  9. OpenAI Universe 2 comments

    • 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…

      BickNowstromView on HNParent context

    • 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…

      epberryView on HNParent context

  10. The Neural Network Zoo 1 comment

    • 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…

      cs702View on HNParent context

  11. [MIT Lecture] Connections between physics and deep learning 1 comment

    • Thanks for sharing this lecture by Max Tegmark. He comments on the video linking to two papers on arXiv which relate to the material in the lecture: https://arxiv.org/abs/1608.08225 and https://arxiv.org/abs/1606.06737

      throwaway000002View on HNParent context

  12. Is artificial intelligence permanently inscrutable? 1 comment

    • 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…

      sgt101View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.