No-free lunch theorems

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )

The no-free lunch theorems (“ no free lunch ” is English for “ no free lunch ” or “ nothing is free ”, hence the nothing-is-free theorems ) are essentially two sentences in computer science that show the limits of optimization algorithms or machine learning processes . They are impossibilities theorem, like Godel's incompleteness theorem in mathematics or the Arrow theorem in social choice theory. The name comes from the English saying There ain't no such thing as a free lunch . David Wolpert and William G. Macready they discovered 1995. In a more stringent formulation of 2001, the no-free-lunch theorem applies the optimization problem for quantities less than permutation completed are.

The theorems are based on the premise that the search space is given by a probability function. Simplifies do they say that there is no universally good method of solving an optimization problem or abstracting of records exist, if the amount of all problems or records is considered. If a certain strategy is better than another in one area , it must be worse in another area ( nothing is free ). In particular, it shows that no strategy, when applied to the population of all cases, does better than guessing.

There can be efficient algorithms if the search space has structure (e.g. represents a continuous , differentiable function ), or if there is even a closed solution (e.g. extremum of a quadratic function ) that can be determined without a search. So it is entirely possible to develop strategies for certain sets of problems that are better than others. In everyday life , the search space is in most cases already given a structure by the laws of nature , so that it can usually be searched / optimized efficiently.

Original formulation

Wolpert and Macready published the no-free lunch theorem on optimization problems that don't change during problem search, like this:

Theorem 1 : For two algorithms a ₁ and a ₂ applies:

${\displaystyle \sum _{f}P(h_{m}^{y}|f,m,a_{1})=\sum _{f}P(h_{m}^{y}|f,m,a_{2}).}$

If all functions are equally likely to occur, the probability of encountering any sequence of values ​​during the optimization does not depend on the optimization algorithm. ${\displaystyle f}$ ${\displaystyle P}$ ${\displaystyle m}$

Attempted application to evolutionary processes

William A. Dembski has applied the no-free lunch theorems to his controversial hypotheses of specified complexity , which he believes form mathematical bounds for evolutionary processes . Dembski uses these barriers as an argument against the theory of evolution and for an intelligent design .

However, this reasoning is generally not considered scientifically sound. Among other objections is mainly stated that evolutionary processes not as a search for a particular from the outset given can be considered optimal element within a search amount as the No-free lunch assume -Theoreme. Darwinian evolution is generally to be seen as an "avoidance strategy" rather than a "search strategy", since survival and reproduction are what count and only those evolutionary steps are safely excluded that lead to species that are fundamentally incapable of doing so. The no-free lunch theorems are therefore not applicable at all.

Another objection is that the theorems make a statement about the average of all conceivable problems. In evolutionary theory this means: averaged over all possible fitness landscapes . The theorems cannot say anything about the effectiveness of the mutation and selection process for the fitness landscapes that actually occur. In particular, the majority of all theoretically conceivable fitness landscapes are completely random, while the laws of nature already require a certain structure.

Wolpert himself rejects Dembski's statements as non-mathematical ( written in jello ) and also adds that the fitness function of evolutionary systems can neither be viewed as constant in time nor as identical for all individuals. However, this is an important prerequisite for the no-free lunch theorems and therefore also makes an application to evolutionary processes impossible. In fact, Wolpert and Macready were able to prove the existence of optimal algorithms for a certain class of such co-evolutionary systems.

See also

• List of theorems of computer science

literature

• Delbaen, Schachermayer: What is ... a free lunch? , Notices of the AMS, May 2004

Web links

• David H. Wolpert, William G. Macready:, December 31, 1996 (PDF file; 343 kB)
• Article from the 1995 International Conference on Genetic Algorithms (ICGA-95) in Pittsburgh
• Collection of articles on the topic of no-free lunch

Individual evidence

1. ↑ Ethem Alpaydin: Machine Learning. , 2nd, extended edition, De Gruyter, Berlin 2019, ISBN 978-3-11-061789-4 (accessed via De Gruyter Online)
2. ^ David H. Wolpert, William G. Macready: No free lunch theorems for search. Vol. 10, Technical Report SFI-TR-95-02-010, Santa Fe Institute, 1995.
3. ^ Anne Auger, Benjamin Doerr: Theory of Randomized Search Heuristics: Foundations and Recent Developments. P. 258.
4. ^ Xinjie Yu, Mitsuo Gen: Introduction to Evolutionary Algorithms. P. 102.
5. ↑ Peter Flach: Machine Learning: The Art and Science of Algorithms that Make Sense of Data. P. 10.
6. ^ Raymond Chiong: Nature-Inspired Algorithms for Optimization. P. 34.
7. ^ William A. Dembski: No Free Lunch: Why Specified Complexity Cannot Be Purchased without Intelligence. Rowman & Littlefield, Lanham, Md. 2002, ISBN 0-7425-1297-5 .
8. ↑ J. Rose House: Probability, Optimization Theory, and Evolution. In: evolution. 56 (8), 2002, pp. 1721-1722.
9. ^ ^{A b} H. Allen Orr: Book Review of No Free Lunch. Boston Review
10. ^ ^{A b c} David Wolpert: William Dembski's treatment of the No Free Lunch theorems is written in jello. Mathematical Reviews, 2003.
11. ^ ^{A b c} Richard Wein: Not a Free Lunch But a Box of Chocolates. 2002.
12. ^ M. Perakh: There is a free lunch after all: William Dembski's wrong answers to irrelevant questions. In: M. Young, T. Edis (eds.): Why Intelligent Design Fails. Rutgers University Press, 2004, chapter 11.
13. ^ Richard Dawkins: The Blind Watchmaker. WW Norton & Company , New York 1996, p. 50.
14. ^ DH Wolpert, WG Macready: Coevolutionary free lunches. In: IEEE Transactions on Evolutionary Computation. 2005, 9 (6), pp. 721-735.