No free lunch and inductive bias
Averaged over every possible world, every learning algorithm is exactly as good as a coin on data it hasn't seen. State the no-free-lunch theorems carefully — Wolpert's and the textbook version — and see why assumptions are not a weakness of learning but its engine.
40 min
After this lesson you can
- State Wolpert's (1996) no-free-lunch result for off-training-set error and say what is averaged over
- State the Shalev-Shwartz–Ben-David no-free-lunch theorem and sketch its proof
- Decompose the risk of ERM into approximation and estimation error, and explain the bias–complexity trade-off
- Explain how architectures encode inductive biases, with convolution as the example
- State the Occam / minimum-description-length bound and the condition that makes it valid
In this lesson
- Wolpert’s theorem: every learner is a coin, on average
- The picture: two biases, three worlds
- The textbook version: every learner has a nemesis
- Inductive bias: the only way out
- Occam’s razor, made precise
- In code
- Limits and open questions
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.