No free lunch theorem
Encyclopedia
In mathematical folklore, the "no free lunch" theorem (sometimes pluralized) of Wolpert and Macready appears in the 1997 "No Free Lunch Theorems for Optimization." Wolpert had previously derived no free lunch theorems for machine learning (statistical inference). In 2005, Wolpert and Macready themselves indicated that the first theorem in their paper "state[s] that any two optimization
algorithms are equivalent when their performance is averaged across all possible problems." The 1997 theorems of Wolpert and Macready are mathematically technical and some find them unintuitive. The folkloric "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove. It is weaker than the proven theorems, and thus does not encapsulate them.
Various investigators have extended the work of Wolpert and Macready substantively. See No free lunch in search and optimization for treatment of the research area.
In essence, this says that when all functions f are equally likely, the probability of observing an arbitrary sequence of m values in the course of optimization does not depend upon the algorithm. In the analytic framework of Wolpert and Macready, performance is a function of the sequence of observed values, so it follows easily that all algorithms have identically distributed performance when objective functions are drawn uniformly at random, and also that all algorithms have identical mean performance. But identical mean performance of all algorithms does not imply Theorem 1, and thus the folkloric theorem is not equivalent to the original theorem.
Theorem 2 establishes a similar, but "more subtle," NFL result for time-varying objective functions.
proponents Robert J. Marks II
and William Dembski as supporting intelligent design and Dembski's concept of specified complexity
which he alleges is evidence of design. Many in the scientific community have rejected both the notions of specified complexity and that the no free lunch theorem supports intelligent design.
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
algorithms are equivalent when their performance is averaged across all possible problems." The 1997 theorems of Wolpert and Macready are mathematically technical and some find them unintuitive. The folkloric "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove. It is weaker than the proven theorems, and thus does not encapsulate them.
Various investigators have extended the work of Wolpert and Macready substantively. See No free lunch in search and optimization for treatment of the research area.
Original NFL theorems
Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. The first hypothesizes objective functions that do not change while optimization is in progress, and the second hypothesizes objective functions that may change.- Theorem 1: For any pair of algorithms a1 and a2
In essence, this says that when all functions f are equally likely, the probability of observing an arbitrary sequence of m values in the course of optimization does not depend upon the algorithm. In the analytic framework of Wolpert and Macready, performance is a function of the sequence of observed values, so it follows easily that all algorithms have identically distributed performance when objective functions are drawn uniformly at random, and also that all algorithms have identical mean performance. But identical mean performance of all algorithms does not imply Theorem 1, and thus the folkloric theorem is not equivalent to the original theorem.
Theorem 2 establishes a similar, but "more subtle," NFL result for time-varying objective functions.
Intelligent design and the NFL theorem
The folkloric NFL theorem is often invoked by intelligent designIntelligent design
Intelligent design is the proposition that "certain features of the universe and of living things are best explained by an intelligent cause, not an undirected process such as natural selection." It is a form of creationism and a contemporary adaptation of the traditional teleological argument for...
proponents Robert J. Marks II
Robert J. Marks II
Robert Jackson Marks II is a Distinguished Professor of Electrical and Computer Engineering at Baylor University and proponent of intelligent design. From 1977 to 2003, he was on the faculty of the University of Washington in Seattle...
and William Dembski as supporting intelligent design and Dembski's concept of specified complexity
Specified complexity
Specified complexity is an argument proposed by William Dembski and used by him and others to promote intelligent design. According to Dembski, the concept is intended to formalize a property that singles out patterns that are both specified and complex...
which he alleges is evidence of design. Many in the scientific community have rejected both the notions of specified complexity and that the no free lunch theorem supports intelligent design.