# No free lunch theorem

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".[3] Il "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. In terms of how the NFL theorem is used in the context of the research area, the no free lunch in search and optimization is a field that is dedicated for purposes of mathematically analyzing data for statistical identity, particularly search[4] and optimization.[5] While some scholars argue that NFL conveys important insight, others argue that NFL is of little relevance to machine learning research.[6][7] Contenuti 1 Esempio 2 Origin 3 Motivazione 4 Implicazioni 5 Appunti 6 External links Example Posit a toy universe that exists for exactly two days and on each day contains exactly one object, a square or a triangle. The universe has exactly four possible histories: (square, triangolo): the universe contains a square on day 1, and a triangle on day 2 (square, square) (triangolo, triangolo) (triangolo, square) Any prediction strategy that succeeds for history #2, by predicting a square on day 2 if there is a square on day 1, will fail on history #1, e viceversa. If all histories are equally likely, then any prediction strategy will score the same, with the same accuracy rate of 0.5.[8] Origin Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. In their paper, they state: We have dubbed the associated results NFL theorems because they demonstrate that if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.[5] The first theorem hypothesizes objective functions that do not change while optimization is in progress, and the second hypothesizes objective functions that may change.[5] Teorema 1: For any algorithms a1 and a2, at iteration step m {somma dello stile di visualizzazione _{f}P(d_{m}^{y}mid f,m,un_{1})=somma _{f}P(d_{m}^{y}mid f,m,un_{2}),} dove {stile di visualizzazione d_{m}^{y}} denotes the ordered set of size {stile di visualizzazione m} of the cost values {stile di visualizzazione y} associated to input values {stile di visualizzazione xin X} , {stile di visualizzazione f:Xrightarrow Y} is the function being optimized and {stile di visualizzazione P(d_{m}^{y}mid f,m,un)} is the conditional probability of obtaining a given sequence of cost values from algorithm {stile di visualizzazione a} run {stile di visualizzazione m} times on function {stile di visualizzazione f} .

The theorem can be equivalently formulated as follows: Teorema 1: Given a finite set {stile di visualizzazione V} and a finite set {stile di visualizzazione S} di numeri reali, assume that {stile di visualizzazione f:Vto S} is chosen at random according to uniform distribution on the set {stile di visualizzazione S^{V!}} of all possible functions from {stile di visualizzazione V} a {stile di visualizzazione S} . For the problem of optimizing {stile di visualizzazione f} over the set {stile di visualizzazione V} , then no algorithm performs better than blind search.

Qui, blind search means that at each step of the algorithm, l'elemento {displaystyle vin V} is chosen at random with uniform probability distribution from the elements of {stile di visualizzazione V} that have not been chosen previously.

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 (and not e.g. of wall-clock time), 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.

Teorema 2 establishes a similar, ma "more subtle", NFL result for time-varying objective functions.[5] Motivation The NFL theorems were explicitly not motivated by the question of what can be inferred (in the case of NFL for machine learning) or found (in the case of NFL for search) when the "environment is uniform random". Rather uniform randomness was used as a tool, to compare the number of environments for which algorithm A outperforms algorithm B to the number of environments for which B outperforms A. NFL tells us that (appropriately weighted)[chiarimenti necessari] there are just as many environments in both of those sets.

This is true for many definitions of what precisely an "environment" è. In particolare, there are just as many prior distributions (appropriately weighted) in which learning algorithm A beats B (on average) as vice versa.[citazione necessaria] This statement about sets of priors is what is most important about NFL, not the fact that any two algorithms perform equally for the single, specific prior distribution that assigns equal probability to all environments.

While the NFL is important to understand the fundamental limitation for a set of problems, it does not state anything about each particular instance of a problem that can arise in practice. Questo è, the NFL states what is contained in its mathematical statements and it is nothing more than that. Per esempio, it applies to the situations where the algorithm is fixed a priori and a worst-case problem for the fixed algorithm is chosen a posteriori. Perciò, se abbiamo un "Buona" problem in practice or if we can choose a "Buona" learning algorithm for a given particular problem instance, then the NFL does not mention any limitation about this particular problem instance. Though the NFL might seem contradictory to results from other papers suggesting generalization of learning algorithms or search heuristics, it is important to understand the difference between the exact mathematical logic of the NFL and its intuitive interpretation.[9] Implications Further information: Problem of induction To illustrate one of the counter-intuitive implications of NFL, suppose we fix two supervised learning algorithms, C and D. We then sample a target function f to produce a set of input-output pairs, d. How should we choose whether to train C or D on d, in order to make predictions for what output would be associated with a point lying outside of d?

It is common in almost all of science and statistics to answer this question – to choose between C and D – by running cross-validation on d with those two algorithms. In altre parole, to decide whether to generalize from d with either C or D, we see which of them has better out-of-sample performance when tested within d.

Since C and D are fixed, this use of cross-validation to choose between them is itself an algorithm, cioè., a way of generalizing from an arbitrary dataset. Call this algorithm A. (Arguably, A is a simplified model of the scientific method itself.) We could also use anti-cross-validation to make our choice. In altre parole, we could choose between C and D based on which has worse out-of-sample performance within d. Ancora, since C and D are fixed, this use of anti-cross-validation is itself an algorithm. Call that algorithm B.

NFL tells us (parlando in modo approssimativo) that B must beat A on just as many target functions (and associated datasets d) as A beats B. In this very specific sense, the scientific method will lose to the "anti" scientific method just as readily as it wins.[10] NFL only applies if the target function is chosen from a uniform distribution of all possible functions. If this is not the case, and certain target functions are more likely to be chosen than others, then A may perform better than B overall. The contribution of NFL is that it tells us choosing an appropriate algorithm requires making assumptions about the kinds of target functions the algorithm is being used for. With no assumptions, No "meta-algorithm", such as the scientific method, performs better than random choice.

While some scholars argue that NFL conveys important insight, others argue that NFL is of little relevance to machine learning research.[6][7] If Occam's razor is correct, for example if sequences of lower Kolmogorov complexity are more probable than sequences of higher complexity, poi (as is observed in real life) some algorithms, such as cross-validation, perform better on average on practical problems (when compared with random choice or with anti-cross-validation).[11] Notes ^ Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary Computation 1, 67. ^ Wolpert, Davide (1996), "The Lack of A Priori Distinctions between Learning Algorithms", Neural Computation, pp. 1341–1390. Archiviato 2016-12-20 at the Wayback Machine ^ Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches", IEEE Transactions on Evolutionary Computation, 9(6): 721–735 ^ Wolpert, D. H.; Macready, w. G. (1995). "No Free Lunch Theorems for Search" (PDF). Technical Report SFI-TR-95-02-010. Santa Fe Institute. S2CID 12890367. ^ Salta su: a b c d Wolpert, D. H.; Macready, w. G. (1997). "No Free Lunch Theorems for Optimization". IEEE Transactions on Evolutionary Computation. 1: 67–82. doi:10.1109/4235.585893. ^ Salta su: a b Whitley, Darrell, and Jean Paul Watson. "Complexity theory and the no free lunch theorem." In Search Methodologies, pp. 317–339. Springer, Boston, MA, 2005. ^ Salta su: a b Giraud-Carrier, Cristofe, and Foster Provost. "Toward a justification of meta-learning: Is the no free lunch theorem a show-stopper." In Proceedings of the ICML-2005 Workshop on Meta-learning, pp. 12–19. 2005. ^ Forster, Malcolm R. (1999). Minds and Machines. 9 (4): 543–564. doi:10.1023/UN:1008304819398. S2CID 8802657. {{cite journal}}: Missing or empty |title= (help) ^ Kawaguchi, K., Kaelbling, L.P, and Bengio, Y.(2017) "Generalization in deep learning", https://arxiv.org/abs/1710.05468 ^ Wolpert, D.H. (2013) "What the no free lunch theorems really mean", Ubiquity, Volume 2013, Dicembre 2013, doi:10.1145/2555235.2555237 ^ Lattimore, Tor, and Marcus Hutter. "No free lunch versus Occam’s razor in supervised learning." In Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence, pp. 223–235. Springer, Berlino, Heidelberg, 2013. External links No Free Lunch Theorems Graphics illustrating the theorem Categories: Scientific folklorePhilosophy of mathematicsMathematical theorems

Se vuoi conoscere altri articoli simili a No free lunch theorem puoi visitare la categoria Mathematical theorems.

Vai su

Utilizziamo cookie propri e di terze parti per migliorare l'esperienza dell'utente Maggiori informazioni