no free lunch theorem
In plain wordsA mathematical result saying that no learning or search method is best for every possible problem: any method that wins on some problems must lose on others.
Any of several theorems showing that, averaged uniformly over all possible problems, all learning or optimization algorithms perform equally well. In supervised learning (David Wolpert), when every possible target function is equally likely, every learner has the same expected error on examples outside the training set; in search and optimization (Wolpert and William Macready), all black-box algorithms have identical average performance over all objective functions. The practical lesson is that a learner succeeds only insofar as its assumptions — its inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases. — match the structure of the problems it actually faces; there is no universally best algorithm, model or hyperparameterhyperparameter, n.: A setting chosen by people before training, such as how fast a model learns or how big it is, as opposed to the internal values the model learns by itself from data. setting. The theorems do not make all methods equal on real tasks, which are far from uniformly distributed: natural data has regularities (smoothness, compositionality, low intrinsic dimensionalitydimensionality, n.: How many separate numbers are needed to describe something. A point on a map needs two; an AI's description of a single word may use thousands.) that some inductive biases exploit far better than others, a point often used to explain the broad success of deep learning and of simplicity priors such as Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise. and Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next..
No free lunch: the architecture that wins on images may be a poor choice for tabular data.
Origin
Introduced for search and optimization by David Wolpert and William Macready in a 1995 Santa Fe Institute report, published as 'No Free Lunch Theorems for Optimization' (IEEE Transactions on Evolutionary Computation, 1997), and for supervised learning in Wolpert's 'The Lack of A Priori Distinctions Between Learning Algorithms' (Neural Computation, 1996). The name borrows the saying 'there ain't no such thing as a free lunch'.
Related
- inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases.
- Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise.
- PAC learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right.
- generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers.
- Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next.
- statistical learning theorystatistical learning theory, n.: The mathematics of when and why learning from examples works: how much data is needed, and how well a model trained on some examples will do on new ones.
Sources
- Wolpert, D. H. (1996). The Lack of A Priori Distinctions Between Learning Algorithms. Neural Computation, 8(7).
- Wolpert, D. H. & Macready, W. G. (1997). No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1).
Mentioned in
inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases., Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise., hypothesis spacehypothesis space, n.: The full menu of possible models a learning method is allowed to choose from — for example, all straight lines. Learning means picking the item on the menu that best fits the data., Leslie ValiantLeslie Valiant, prop. n.: A British computer scientist who in 1984 gave the first rigorous definition of what it means for a computer to learn from examples, founding the theory of machine learning., metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one., PAC learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right., statistical learning theorystatistical learning theory, n.: The mathematics of when and why learning from examples works: how much data is needed, and how well a model trained on some examples will do on new ones.