Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Learning Theory from First Principles [pdf]

di.ens.fr

Post reply on HN
Print view View original

51–60 of 66 posts

Re: Learning Theory from First Principles [pdf]

#51

Post by carlthome »

magnio wrote: post #43
sampo wrote: post #15

> 2.5 No free lunch theorem > > Although it may be tempting to define 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 n…

I don't see how your disclaimer applies. My interpretation of no free lunch theorems is that no single algorithm works well for all classes of problems, not that some problems are unlearnable. The example in its proof might be contrived, but in actuality, additional assumptions can and do lead to different algorithms being picked, no?

Transformers go brrr

Re: Learning Theory from First Principles [pdf]

#52

Post by jumpCastle »

carlthome wrote: post #51
magnio wrote: post #43

Earlier quoted context omitted.

I don't see how your disclaimer applies. My interpretation of no free lunch theorems is that no single algorithm works well for all classes of problems, not that some problems are unlearnable. The example in its proof might be contrived, but in actuality, additional assumptions can and do lead to different algorithms being picked, no?

Transformers go brrr

Work pretty well for all classes of problems?

Re: Learning Theory from First Principles [pdf]

#53

Post by jameshart »

Legend2440 wrote: post #34
boberoni wrote: post #31

Earlier quoted context omitted.

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?

Halting problem only applies in the general case. I can trivially tell you that while(1) will never halt. There are many examples of programs whose halting behavior is not known (collatz conjecture for example) but many others where program analysis works just fine.

If you write a program whose behavior is Collatz-like (say, in some states it queues up more work for itself, and in other states it completes work from the queue, and you believe that in general it should always ultimately complete the queue) it is actually useful to have a static analyzer tell you ‘it’s not entirely clear that this code will ever terminate’.

You can make the analyzer happy by adding a max iteration limit or a recursion depth limit or something to make sure it fails out rather than looping forever.

Which is probably a good idea anyway, if you’re running code that you can’t mathematically prove will always complete.

Re: Learning Theory from First Principles [pdf]

#54

Post by bonoboTP »

sampo wrote: post #15

> 2.5 No free lunch theorem > > Although it may be tempting to define 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 n…

It's analogous to the problem of induction (Hume). Without assumptions, it's impossible to connect past observations to predictions about the future. Observing that the sun rises a thousand mornings does not automatically make it any more or less likely that it will rise tomorrow, unless we make some assumptions, for example that events tend to be similar over time. And those assumptions can't be extracted from the data. Maybe things tended to be similar over time in the past, but that says nothing about the future. The pattern might break tomorrow and to say that it likely won't, is simply an assumption on a higher level.

But it seems like science is "doing fine" despite this problem. Similarly machine learning chugs along fine, because people use their experience and prior knowledge when designing the algorithms. These assumptions are also called inductive biases. They are biasing the learning towards certain patterns (like "things tend to be similar locally").

Re: Learning Theory from First Principles [pdf]

#55

Post by bonoboTP »

garydevenay wrote: post #27
throwaway81523 wrote: post #21

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.

Certainly doesn't seem like first principles...

"First principles" doesn't mean "introduction". It is to contrast with anecdotal experience / tacit knowledge / empirical best practice approaches.

Re: Learning Theory from First Principles [pdf]

#56

Post by jameshart »

carlthome wrote: post #50
grekiki wrote: post #40

Earlier quoted context omitted.

Sure but halting problem is solvable for finite state machines.

Could you expand or provide a link to a good resource for me to understand this? If the judge program should say terminates yes/no and the program given is `while True: continue`, I guess the argument is that in the finite case, you could in principle just enumerate all programs that don't terminate and identify them as such?

In principle, you can enumerate all possible memory states of the system and determine what the next memory state would be from each one (including multiple possible next states if you account for things like interrupts)

Then you treeshake the unreachable parts of that directed graph from the start state, and look for closed loops in what remains.

Re: Learning Theory from First Principles [pdf]

#57

Post by bonoboTP »

ralphist wrote: post #9
p1esk wrote: post #3

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”.

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?

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?

Re: Learning Theory from First Principles [pdf]

#58

Post by ithinkso »

bonoboTP wrote: post #54
sampo wrote: post #15

> 2.5 No free lunch theorem > > Although it may be tempting to define 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 n…

It's analogous to the problem of induction (Hume). Without assumptions, it's impossible to connect past observations to predictions about the future. Observing that the sun rises a thousand mornings does not automatically make it any more or less likely that it will rise tomorrow, unless we make some assumptions, for example that events tend to be similar over time. And those assumptions can't be extracted from the d…

One just assumes Occam's razor and you're good to go in a vast majority of cases

Re: Learning Theory from First Principles [pdf]

#59

Post by bonoboTP »

ithinkso wrote: post #58
bonoboTP wrote: post #54

Earlier quoted context omitted.

It's analogous to the problem of induction (Hume). Without assumptions, it's impossible to connect past observations to predictions about the future. Observing that the sun rises a thousand mornings does not automatically make it any more or less likely that it will rise tomorrow, unless we make some assumptions, for example that events tend to be similar over time. And those assumptions can't be extracted from the d…

One just assumes Occam's razor and you're good to go in a vast majority of cases

If you formalize Occam's "simplicity" as description length, then that depends on encoding. By assuming an encoding, you implicitly assume a distribution (according to entropy coding, eg Huffman coding) and hence inject an inductive bias.

I'm not saying that it's bad to assume one. The point is that it is an assumption. My bigger point is that the no free lunch theorem should only bother you as much as the induction problem bothers you. Which in practice means not at all.

Re: Learning Theory from First Principles [pdf]

#60

Post by tel »

TeMPOraL wrote: post #45
tel wrote: post #19

Earlier quoted context omitted.

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

> The team is pretty deep in investigating the idea of superposition, where individual neurons encode for multiple concepts. Wonder if it's a matter of perspective - that is, of transform. Consider an image. Most real-world images have pixels with high locality - distant pixels are less correlated than immediate neighbours. Now take an FFT of that. You get an equivalent 2D image containing the same information, but s…

I think that’s basically correct, the FFT representation is a better feature representation.
Post reply on HN