Learning Theory from First Principles [pdf]
di.ens.fr
di.ens.fr
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.
For example, many people naively think that static program analysis is unfeasible due to the halting problem, Rice's theorem, etc.
I guess something related to this one way or another.
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?
Then you treeshake the unreachable parts of that directed graph from the start state, and look for closed loops in what remains.
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.
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.
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
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.
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").
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.
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.
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.
Some more detail here: https://calculatedcontent.com/2019/12/03/towards-a-new-theor...
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/ind...
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.
I do like that there are lots of exercises.
This is older but is supposed to be good: https://www.deeplearningbook.org/
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.
Quadratic means square terms.
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...
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.
Think about how often narrowly specialized academics reinvent a bad version of something that already has an elaborately understood theory in another field. (a meme example is when a medical researcher working on insulin metabolism reinvented the trapezoid rule for integration - but of course many more mundane cases happen every day). It would be a great opportunity to avoid this by checking with an LLM. Arguably if that researcher fed his idea to an LLM as it exists today, the LLM would have recognized that this is just the trapezoid rule. In fact I also use it for such "sounding board" where it gives me good googleable terms like, "what you're looking for is called an XYZ".
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 request response universe with.. POST phone, car, gps(a,b,c,d), now, payment.
But as a student wanting to learn algorithms how do I pass that I'm $age $internet-type from $place and prefer graphical explanations of algorithms, have tried but gotten scared of that thick book and these $milestones-cs50, know $python upto $proficiency(which again is a fractal variable with research papers on how to define for learning).
Similarly how do I help you understand what stage my startup idea is beyond low traction, but want to know have $networks/(VC, devs, sales) APIs, have $these successful partnerships with such evidence $attendance, $sales. Who should I speak to? Could you pls write the needful in mails and engage in partnership with other bots under $budget.
Even in the real world this vocabulary is in smaller pockets as our contexts are too different.
4. Learning assumes knowledge exists as a global forever variable in a wider than we understand universe. $meteor being a non maskable interrupt to the power supply at unicorn temperatures in a decade. Similarly one time trends in disposable $companies that $ecosystem uses to learn. I'm in a desert village with with absent electricity might mean those machines never reach me and perhaps most people don't have a basic phone in the world to be able to share state. Their local power mafia politics and absent governance might mean the pdf AI recommends i read might or might not help.
I don't know how this will evolve but to think of the possibilities has been so interesting. It's like computers can talk to us easily and they're such smart babies on day 1 and "folks we aren't able to put right, enough, cheap data in" is perhaps the real bottleneck to how much usefulness we are being able to uncover.