6 ms·

Learning Theory from First Principles [pdf]

279 points by magnio 3y ago

scythmic_waves 3y ago
Interesting! I’ll have to look over it when I have more time. From a quick glance, it looks like it covers much of the same material as this text [1]. I wonder how they compare. [1]: https://www.cambridge.org/core/books/understanding-machine-learning/3059695661405D25673058E43C8BE2A6 https://www.cambridge.org/core/books/understanding-machine-l...
- throwaway81523 3y ago
  A 2014 book on machine learning sounds quaint and historical.
  - nerdponx 3y ago
    It depends on the particular subtopics it covers. Machine Learning: A Probabilistic Perspective is from 2012 and it's still a great resource, although Murphy's newer book will certainly cover more up-to-date material.
  - dawnofdusk 3y ago
    Depends on what you want from a (text)book. In my mind books should be authoritative, they should include things that have had some thought put into them and are fairly well studied/verified. Modern advances in deep learning/ML are exciting but are very often not this. I would not a read a book which is just some recent hype papers from NeurIPS/ICML stapled together.
p1esk 3y ago
I can’t wait until I tell GPT-5 “I have this idea I want to try, read this book and tell me there’s anything relevant there to make it work better”.
- deleted 3y ago
  [deleted]
- ralphist 3y ago
  I've never heard of an LLM making up a new idea. Shouldn't this only work if your thing has already been tried before?
  - p1esk 3y ago
    In my example I already have an idea, but I’m not sure how good or novel it is, or perhaps I tried it and it didn’t work but I don’t understand why.
  - westoncb 3y ago
    How people define "new" varies a lot in this context. I've spent a lot of time talking with ChatGPT exploring interdisciplinary ideas and while I think it frequently says things that qualify as new, I've only run into one situation where I was trying to find some way of doing something technical and it just invented something non-trivially original to handle it: https://x.com/Westoncb/status/1763733064478335326?s=20 https://x.com/Westoncb/status/1763733064478335326?s=20
  - bonoboTP 3y ago
    Have you heard of a person making up a new idea? Can you definitely state that it's not just a combination of a few previous ideas?
    - ralphist 3y ago
      The brain is able to make better associations than an LLM. From what I’ve seen, LLMs always stay on topic, even when that means outputting only platitudes. A human can go past that and try different approaches to a question. It can also take part of a problem, choose a lead at random, think through the results, and step back if that doesn’t work. A forward pass in an LLM doesn’t do that, yet. Basically it seems to me that LLMs may have part of what makes us good at inventing ideas, but they’re missing part of that process.
canjobear 3y ago
Have they figured out what causes double descent yet?
- a_wild_dandan 3y ago
  No. We don't know. My favorite hypothesis: SGD is...well, stochastic. Meaning you're not optimizing w.r.t the training corpus, but a tiny subset, so your gradient isn't quite right. Over-training allows you to bulldoze over local optima and recurse toward the true distribution rather than drive around a local over-fitting basin.
  - canjobear 3y ago
    You can get it with full gradient descent though... https://www.nature.com/articles/s41467-020-14663-9 https://www.nature.com/articles/s41467-020-14663-9 Honestly the fact that there doesn't seem to be a good explanation for this makes me think that we just fundamentally don't understand learning.
- arolihas 3y ago
  There was actually a very recent blog post claiming that statistical mechanics can explain double descent https://calculatedcontent.com/2024/03/01/describing-double-descent-with-weightwatcher/ https://calculatedcontent.com/2024/03/01/describing-double-d... Some more detail here: https://calculatedcontent.com/2019/12/03/towards-a-new-theory-of-learning-statistical-mechanics-of-deep-neural-networks/ https://calculatedcontent.com/2019/12/03/towards-a-new-theor...
- iaseiadit 3y ago
  Not an expert, but this paper explores double descent with simple models. The interpretation there: when you extend into the overparameterized regime, that permits optimization towards small-norm weights, which generalize well again. Does that explain DD generally? Does it apply to other models (e.g. DNNs)? https://arxiv.org/pdf/2303.14151.pdf https://arxiv.org/pdf/2303.14151.pdf
- tel 3y ago
  I don't know if it's a generalized result, but the Circuits team at Anthropic has a very compelling thesis: the first phase of descent corresponds to the model memorizing data points, the second phase corresponds to it shifting geometrically toward learning "features". Here a "feature" might be seen as an abstract, very, very high dimensional vector space. The team is pretty deep in investigating the idea of superposition, where individual neurons encode for multiple concepts. They experiment with a toy model and toy data set where the latent features are represented explicitly and then compressed into a small set of data dimensions. This forces superposition. Then they show how that superposition looks under varying sizes of training data. It's obviously a toy model, but it's a compelling idea. At least for any model which might suffer from superposition. https://transformer-circuits.pub/2023/toy-double-descent/index.html https://transformer-circuits.pub/2023/toy-double-descent/ind...
da39a3ee 3y ago
There are so many great mathematical PDFs available for free on the Internet, written by academics/educators/engineers. A problem is that there is a huge amount of overlap. I wonder if an AI model could be developed that would do a really good job of synthesizing an overlapping collection into a coherent single PDF without duplication.
- hef19898 3y ago
  One could also just pick the books used in the corresponding university courses.
  - da39a3ee 3y ago
    In more advanced undergraduate math, PDF lecture notes written by professors but not published in book form often contain excellent explanations and proofs that are not available in books. Also, making undergraduate buy expensive text books is more of a thing in first year American classes. Look at the lecture notes at Oxford for example. https://courses.maths.ox.ac.uk/ https://courses.maths.ox.ac.uk/
- nerdponx 3y ago
  No need for an AI model. Probabilistic Machine Learning by Murphy is an excellent reference and resource.
  - da39a3ee 3y ago
    I'm not talking about this specific subject.
sampo 3y ago
> 2.5 No free lunch theorem > > Although it may be tempting to deﬁne the optimal learning algorithm that works optimally for all distributions, this is impossible. In other words, learning is only possible with assumptions. A mention of no free lunch theorem should come with a disclaimer that the theorem is not relevant in practice. An assumption that your data originates from the real world, is sufficient that the no free lunch theorem is not a hindrance. This book doesn't discuss this at all. Maybe mention that "all distributions" means a generalization to higher dimensional spaces of discontinuous functions (including the tiny subset of continuous functions) of something similar to all possible bit sequences generated by tossing a coin. So basically if you data is generated from an even random distribution of "all possibilities", you cannot learn to predict the outcome of the next coin tosses, or similar.
- nextos 3y ago
  Yes, most free lunch theorems and results of this kind, which make overly general assumptions, tend to be too pessimistic. For example, many people naively think that static program analysis is unfeasible due to the halting problem, Rice's theorem, etc.
  - boberoni 3y ago
    Just curious, how does program analysis on real-world programs exactly circumvent the problems of the halting problem or Rice’s theorem? In the real world, do we only ever have statically analyze a special subset of all programs?
    - gryn 3y ago
      In the real World Turing machines don't exist only finite state Machines. (No infinite tape or infinite time) I guess something related to this one way or another.
      - pdonis 3y ago
        You don't need an infinite tape to make a finite state machine that never halts. As Legend2440 pointed out upthread, while(1) is a simple finite state machine that never halts.
throwaway81523 3y ago
This is pretty hard to read. For example, on the first page of chapter 1, it talks about "minimization of quadratic forms" and shows what looks like the formula for linear least squares. Is that right? It doesn't say anything about this. Some more exposition would help. I do like that there are lots of exercises.
- guimplen 3y ago
  I think the text is geared towards people with some mathematical background who want to understand learning theory. Besides it is clearly stated that this chapter is a review (so its assumed that you learned or will learn these things elsewhere).
  - throwaway81523 3y ago
    Well I have some math background but that section is brisk and slow at the same time, as it were. Such as how it explains how to find inverses of 2x2 matrices. This is older but is supposed to be good: https://www.deeplearningbook.org/ https://www.deeplearningbook.org/
- garydevenay 3y ago
  Certainly doesn't seem like first principles...
  - bonoboTP 3y ago
    "First principles" doesn't mean "introduction". It is to contrast with anecdotal experience / tacit knowledge / empirical best practice approaches.
- nerdponx 3y ago
  The sibling comment is right in that this is clearly not intended for first timers. But your instincts are correct here. When you write out the objective function for ordinary least squares, it turns out to be a quadratic form. The choice of the word "quadratic" here is not a coincidence: it is the generalization of quadratic functions to matrices. That section covers the vector equivalent of minimizing quadratic functions.
jabowery 3y ago
Learning theory is the attempt to formalize natural science up to decision. Natural science's unstated assumption is that a sufficiently sophisticated algorithmic world model can be used to predict future observations from past observations. Since this is the same assumption as Solomonoff's assumption in his proof of inductive inference, you have to start there: with Turing complete coding rather than Rissanen's so-called "universal" coding. It's ok* to depart from that starting point in creating subtheories but if you don't start there you'll end up with garbage like the last 50 years of confusion over what "The Minimum Description Length Principle" really means. *It is, however, _not_ "ok" if what you are trying to do is come up with causal models. You can't get away from Turing complete codes if you're trying to model dynamical systems even though dynamical systems can be thought of as finite state machines with very large numbers of states. In order to make optimally compact codes you need Turing complete semantics that execute on a finite state machine that just so happens to have a really large but finite number of flipflops or other directed cyclic graph of universal (eg NOR, NAND, etc.) gates.
ogogmad 3y ago
Minor nitpick: The title is confusing. The first word should be substituted with "Machine-Learning" or "Statistical-Learning". Ideally, the author of the piece should do that at some point.
noonething 3y ago
Fascinating, does anyone have any good books on this?

279 points by magnio 3y ago

Interesting! I’ll have to look over it when I have more time. From a quick glance, it looks like it covers much of the same material as this text [1]. I wonder how they compare. [1]: https://www.cambridge.org/core/books/understanding-machine-learning/3059695661405D25673058E43C8BE2A6 https://www.cambridge.org/core/books/understanding-machine-l...

throwaway81523 3y ago
A 2014 book on machine learning sounds quaint and historical.
- nerdponx 3y ago
  It depends on the particular subtopics it covers. Machine Learning: A Probabilistic Perspective is from 2012 and it's still a great resource, although Murphy's newer book will certainly cover more up-to-date material.
- dawnofdusk 3y ago
  Depends on what you want from a (text)book. In my mind books should be authoritative, they should include things that have had some thought put into them and are fairly well studied/verified. Modern advances in deep learning/ML are exciting but are very often not this. I would not a read a book which is just some recent hype papers from NeurIPS/ICML stapled together.

p1esk 3y ago

I can’t wait until I tell GPT-5 “I have this idea I want to try, read this book and tell me there’s anything relevant there to make it work better”.

deleted 3y ago
[deleted]
ralphist 3y ago
I've never heard of an LLM making up a new idea. Shouldn't this only work if your thing has already been tried before?
- p1esk 3y ago
  In my example I already have an idea, but I’m not sure how good or novel it is, or perhaps I tried it and it didn’t work but I don’t understand why.
- westoncb 3y ago
  How people define "new" varies a lot in this context. I've spent a lot of time talking with ChatGPT exploring interdisciplinary ideas and while I think it frequently says things that qualify as new, I've only run into one situation where I was trying to find some way of doing something technical and it just invented something non-trivially original to handle it: https://x.com/Westoncb/status/1763733064478335326?s=20 https://x.com/Westoncb/status/1763733064478335326?s=20
- bonoboTP 3y ago
  Have you heard of a person making up a new idea? Can you definitely state that it's not just a combination of a few previous ideas?
  - ralphist 3y ago
    The brain is able to make better associations than an LLM. From what I’ve seen, LLMs always stay on topic, even when that means outputting only platitudes. A human can go past that and try different approaches to a question. It can also take part of a problem, choose a lead at random, think through the results, and step back if that doesn’t work. A forward pass in an LLM doesn’t do that, yet. Basically it seems to me that LLMs may have part of what makes us good at inventing ideas, but they’re missing part of that process.

canjobear 3y ago

Have they figured out what causes double descent yet?

a_wild_dandan 3y ago
No. We don't know. My favorite hypothesis: SGD is...well, stochastic. Meaning you're not optimizing w.r.t the training corpus, but a tiny subset, so your gradient isn't quite right. Over-training allows you to bulldoze over local optima and recurse toward the true distribution rather than drive around a local over-fitting basin.
- canjobear 3y ago
  You can get it with full gradient descent though... https://www.nature.com/articles/s41467-020-14663-9 https://www.nature.com/articles/s41467-020-14663-9 Honestly the fact that there doesn't seem to be a good explanation for this makes me think that we just fundamentally don't understand learning.
arolihas 3y ago
There was actually a very recent blog post claiming that statistical mechanics can explain double descent https://calculatedcontent.com/2024/03/01/describing-double-descent-with-weightwatcher/ https://calculatedcontent.com/2024/03/01/describing-double-d... Some more detail here: https://calculatedcontent.com/2019/12/03/towards-a-new-theory-of-learning-statistical-mechanics-of-deep-neural-networks/ https://calculatedcontent.com/2019/12/03/towards-a-new-theor...
iaseiadit 3y ago
Not an expert, but this paper explores double descent with simple models. The interpretation there: when you extend into the overparameterized regime, that permits optimization towards small-norm weights, which generalize well again. Does that explain DD generally? Does it apply to other models (e.g. DNNs)? https://arxiv.org/pdf/2303.14151.pdf https://arxiv.org/pdf/2303.14151.pdf
tel 3y ago
I don't know if it's a generalized result, but the Circuits team at Anthropic has a very compelling thesis: the first phase of descent corresponds to the model memorizing data points, the second phase corresponds to it shifting geometrically toward learning "features". Here a "feature" might be seen as an abstract, very, very high dimensional vector space. The team is pretty deep in investigating the idea of superposition, where individual neurons encode for multiple concepts. They experiment with a toy model and toy data set where the latent features are represented explicitly and then compressed into a small set of data dimensions. This forces superposition. Then they show how that superposition looks under varying sizes of training data. It's obviously a toy model, but it's a compelling idea. At least for any model which might suffer from superposition. https://transformer-circuits.pub/2023/toy-double-descent/index.html https://transformer-circuits.pub/2023/toy-double-descent/ind...

da39a3ee 3y ago

There are so many great mathematical PDFs available for free on the Internet, written by academics/educators/engineers. A problem is that there is a huge amount of overlap. I wonder if an AI model could be developed that would do a really good job of synthesizing an overlapping collection into a coherent single PDF without duplication.

hef19898 3y ago
One could also just pick the books used in the corresponding university courses.
- da39a3ee 3y ago
  In more advanced undergraduate math, PDF lecture notes written by professors but not published in book form often contain excellent explanations and proofs that are not available in books. Also, making undergraduate buy expensive text books is more of a thing in first year American classes. Look at the lecture notes at Oxford for example. https://courses.maths.ox.ac.uk/ https://courses.maths.ox.ac.uk/
nerdponx 3y ago
No need for an AI model. Probabilistic Machine Learning by Murphy is an excellent reference and resource.
- da39a3ee 3y ago
  I'm not talking about this specific subject.

sampo 3y ago

> 2.5 No free lunch theorem > > Although it may be tempting to deﬁne the optimal learning algorithm that works optimally for all distributions, this is impossible. In other words, learning is only possible with assumptions. A mention of no free lunch theorem should come with a disclaimer that the theorem is not relevant in practice. An assumption that your data originates from the real world, is sufficient that the no free lunch theorem is not a hindrance. This book doesn't discuss this at all. Maybe mention that "all distributions" means a generalization to higher dimensional spaces of discontinuous functions (including the tiny subset of continuous functions) of something similar to all possible bit sequences generated by tossing a coin. So basically if you data is generated from an even random distribution of "all possibilities", you cannot learn to predict the outcome of the next coin tosses, or similar.

nextos 3y ago
Yes, most free lunch theorems and results of this kind, which make overly general assumptions, tend to be too pessimistic. For example, many people naively think that static program analysis is unfeasible due to the halting problem, Rice's theorem, etc.
- boberoni 3y ago
  Just curious, how does program analysis on real-world programs exactly circumvent the problems of the halting problem or Rice’s theorem? In the real world, do we only ever have statically analyze a special subset of all programs?
  - gryn 3y ago
    In the real World Turing machines don't exist only finite state Machines. (No infinite tape or infinite time) I guess something related to this one way or another.
    - pdonis 3y ago
      You don't need an infinite tape to make a finite state machine that never halts. As Legend2440 pointed out upthread, while(1) is a simple finite state machine that never halts.

throwaway81523 3y ago

This is pretty hard to read. For example, on the first page of chapter 1, it talks about "minimization of quadratic forms" and shows what looks like the formula for linear least squares. Is that right? It doesn't say anything about this. Some more exposition would help. I do like that there are lots of exercises.

guimplen 3y ago
I think the text is geared towards people with some mathematical background who want to understand learning theory. Besides it is clearly stated that this chapter is a review (so its assumed that you learned or will learn these things elsewhere).
- throwaway81523 3y ago
  Well I have some math background but that section is brisk and slow at the same time, as it were. Such as how it explains how to find inverses of 2x2 matrices. This is older but is supposed to be good: https://www.deeplearningbook.org/ https://www.deeplearningbook.org/
garydevenay 3y ago
Certainly doesn't seem like first principles...
- bonoboTP 3y ago
  "First principles" doesn't mean "introduction". It is to contrast with anecdotal experience / tacit knowledge / empirical best practice approaches.
nerdponx 3y ago
The sibling comment is right in that this is clearly not intended for first timers. But your instincts are correct here. When you write out the objective function for ordinary least squares, it turns out to be a quadratic form. The choice of the word "quadratic" here is not a coincidence: it is the generalization of quadratic functions to matrices. That section covers the vector equivalent of minimizing quadratic functions.

jabowery 3y ago

Learning theory is the attempt to formalize natural science up to decision. Natural science's unstated assumption is that a sufficiently sophisticated algorithmic world model can be used to predict future observations from past observations. Since this is the same assumption as Solomonoff's assumption in his proof of inductive inference, you have to start there: with Turing complete coding rather than Rissanen's so-called "universal" coding. It's ok* to depart from that starting point in creating subtheories but if you don't start there you'll end up with garbage like the last 50 years of confusion over what "The Minimum Description Length Principle" really means. *It is, however, _not_ "ok" if what you are trying to do is come up with causal models. You can't get away from Turing complete codes if you're trying to model dynamical systems even though dynamical systems can be thought of as finite state machines with very large numbers of states. In order to make optimally compact codes you need Turing complete semantics that execute on a finite state machine that just so happens to have a really large but finite number of flipflops or other directed cyclic graph of universal (eg NOR, NAND, etc.) gates.

ogogmad 3y ago

Minor nitpick: The title is confusing. The first word should be substituted with "Machine-Learning" or "Statistical-Learning". Ideally, the author of the piece should do that at some point.

noonething 3y ago

Fascinating, does anyone have any good books on this?