No free lunch — why the bias can't be learned
Parent: learning-theory Prereq: learning-theory — defines
H(hypothesis class), the sample, and generalization error.
No Free Lunch (Wolpert, 1996)Averaged over all possible target functions (all ways the world could be), every learning algorithm has the same expected error on unseen data — no better than random guessing. No universal learner exists.
What it actually says
Take any learner that does well on some set of worlds. There is an exactly-as-large set of worlds (the ones where every unseen label is flipped) on which it does equally badly. The seen data is consistent with both, so nothing in the data distinguishes them. Good performance on your problems is never free — it's paid for by bad performance on the anti-problems you'll never meet.
So: learning well = your inductive bias happens to match the world you're actually in. Restricting H to "reasonable" hypotheses (small VC) is that bias.
The unlearnable base (tier-0)
This forces a regress. Learning requires a prior/bias — but the bias cannot itself be learned: to learn which bias is right you'd need examples of "biases that worked," which needs a prior over biases, and so on. The base assumptions are given, not learned — an unlearnable bottom layer.
This is the formal skeleton of Hume's problem of induction (no amount of past observation logically justifies a prediction) and the reason "assume nothing → learn nothing." Every learner smuggles in a world-assumption at tier-0; the honest move is to make it explicit.