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

41–50 of 66 posts

Re: Learning Theory from First Principles [pdf]

#41

Post by jabowery »

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.

Re: Learning Theory from First Principles [pdf]

#43

Post by magnio »

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?

Re: Learning Theory from First Principles [pdf]

#44

Post by TeMPOraL »

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, if program analysis hits a blocker like this, you tweak stuff until it don't. Top-level post is correct in that, while theory applies to the general case, data and programs we actually use are not completely random/general - there's lots of properties baked in as a consequence of being real-world, physical entities.

Re: Learning Theory from First Principles [pdf]

#45

Post by TeMPOraL »

tel wrote: post #19
canjobear wrote: post #4

Have they figured out what causes double descent yet?

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 suddenly each pixel contains information about every pixel of the original image! You can do some interesting things there, like erasing the centre of the picture (higher frequencies), which will give you blurred original image when you run FFT on the frequency-image to get proper pixels again.

Re: Learning Theory from First Principles [pdf]

#46

Post by fweimer »

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 commercial static analyzers I've seen generate false positives (bogus issues that just aren't there) and false negatives (e.g., unconditional out of bounds pointer writes if that particular piece of C code is ever executed). Some of that comes with the territory because commonly used languages and their libraries are underspecified and commonly used at the boundaries of what is specified. And these tools must always produce some result even if they cannot even parse (or see) the entire code base.

Usually, when people say “static analysis“ they accept unsoundness and use of heuristics. Otherwise, they call the tool a type checker or a verifier. Such tools may run into the theoretical issues you mentioned. For them, the solution is to change the program until it compiles in a reasonable amount of time.

Re: Learning Theory from First Principles [pdf]

#47

Post by falcor84 »

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 theoretical halting problem is required to return a yes/no answer, whereas in the real world, it's actually really valuable to get back a "maybe doesn't halt" answer, so you can then more specifically iterate on those "here be dragons" areas of your system.

Re: Learning Theory from First Principles [pdf]

#48

Post by da39a3ee »

hef19898 wrote: post #11
da39a3ee wrote: post #6

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.

One could also just pick the books used in the corresponding university courses.

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/

Re: Learning Theory from First Principles [pdf]

#49

Post by da39a3ee »

nerdponx wrote: post #29
da39a3ee wrote: post #6

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.

No need for an AI model. Probabilistic Machine Learning by Murphy is an excellent reference and resource.

I'm not talking about this specific subject.

Re: Learning Theory from First Principles [pdf]

#50

Post by carlthome »

grekiki wrote: post #40
pdonis wrote: post #36

Earlier quoted context omitted.

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.

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?

Post reply on HN