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

31–40 of 66 posts

Re: Learning Theory from First Principles [pdf]

#31

Post by boberoni »

nextos wrote: post #17
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…

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.

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?

Re: Learning Theory from First Principles [pdf]

#32

Post by gryn »

boberoni wrote: post #31
nextos wrote: post #17

Earlier quoted context omitted.

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.

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?

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.

Re: Learning Theory from First Principles [pdf]

#33

Post by p1esk »

erbdex wrote: post #13
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 am realising that passing context for $this is the tricky part as- 1. It is very difficult for me to tell you about my context as a user within low dimension variables. 2. I do not understand my situation in the universe to be able to tell AI. 3. I dont have a vocabulary with AI. Internet i feel aced this with shared HTTP protocol to consistently share agreed upon state. For ex within Uber I am a very narrow reques…

What you described is what some of the recent startups are working on: https://www.rewind.ai (I’m not associated with them). To me it seems like a rather trivial problem to solve, compared to creating an LLM in the first place.

Re: Learning Theory from First Principles [pdf]

#34

Post by Legend2440 »

boberoni wrote: post #31
nextos wrote: post #17

Earlier quoted context omitted.

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.

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.

Re: Learning Theory from First Principles [pdf]

#35

Post by dawnofdusk »

throwaway81523 wrote: post #16
scythmic_waves wrote: post #2

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

A 2014 book on machine learning sounds quaint and historical.

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.

Re: Learning Theory from First Principles [pdf]

#36

Post by pdonis »

gryn wrote: post #32
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?

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.

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.

Re: Learning Theory from First Principles [pdf]

#37

Post by dawnofdusk »

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.

First principles doesn't mean easy to read unfortunately

Re: Learning Theory from First Principles [pdf]

#38

Post by nextos »

boberoni wrote: post #31
nextos wrote: post #17

Earlier quoted context omitted.

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.

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?

The main strategy is to build sound but imperfect analyzers, i.e. analyzers that never raise false negatives but that may raise some false positives. See §1.6 in [1], a simplified version of the classic Principles of Program Analysis. Good analyzers are practical, rarely raising false positives for well-written programs. The Astreé analyzer reported zero false positives for the 1 MLOC fly-by-wire A380 code.

Another complementary strategy is to avoid Turing-complete constructs as much as possible, i.e. use DSLs with restricted semantics. This way, advanced semantic properties such as termination are provable.

[1] Program Analysis, An Appetizer. https://arxiv.org/pdf/2012.10086.pdf

Re: Learning Theory from First Principles [pdf]

#39

Post by [deleted] »

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…

[deleted]

Re: Learning Theory from First Principles [pdf]

#40

Post by grekiki »

pdonis wrote: post #36
gryn wrote: post #32

Earlier quoted context omitted.

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.

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.

Sure but halting problem is solvable for finite state machines.
Post reply on HN