In mathematical folklore, the "no free lunch" (NFL) theorem (sometimes pluralized) of David Wolpert and William Macready, alludes to the saying "no such thing as a free lunch", that is, there are no easy shortcuts to success.
Dalam cerita rakyat matematika, teorema "tidak ada makan siang gratis" (bahasa Inggris: no free lunch theorem(s); disingkat NFL) dikemukakan oleh David Wolpert dan William Macready, merujuk pada pepatah Tidak ada makan siang gratis (no such a thing as free lunch)
The "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove.
Teorema "tidak ada makan siang gratis" (NFL) lebih mudah disebutkan dan dipahami, dibandingkan teorema sebenarnya yang dibuktikan Wolpert dan Macready.
While some scholars argue that NFL conveys important insight, others argue that NFL is of little relevance to machine learning research.
Meskipun beberapa pakar berpendapat bahwa NFL mengungkapkan wawasan penting, sebagian lainnya berpendapat bahwa NFL tidak begitu relevan dengan penelitian pemelajaran mesin.
If all histories are equally likely, then any prediction strategy will score the same, with the same accuracy rate of 0.5.
Jika semua sejarah memiliki probabilitas yang sama, maka semua strategi prediksi akan memiliki performa yang setara, dengan akurasi 0.5.
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.
Dalam karya ilmiah mereka, mereka menyatakan: 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.
The first theorem hypothesizes objective functions that do not change while optimization is in progress, and the second hypothesizes objective functions that may change.
Teorema pertama menghipotesiskan fungsi objektif yang tidak berubah selama proses optimasi berlangsung dan teorema kedua menghipotesiskan fungsi objektif yang dapat berubah selama proses
The theorem can be equivalently formulated as follows: Here, blind search means that at each step of the algorithm, the element v ∈ V is chosen at random with uniform probability distribution from the elements of V that have not been chosen previously.
Teorema tersebut dapat dirumuskan secara ekuivalen sebagai berikut:Pencarian buta dalam konteks ini berarti bahwa pada setiap langkah algoritma, elemen v ∈ V dipilih secara dipilih secara acak dari elemen V yang belum dipilih sebelumnya dengan distribusi probabilitas seragam.
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.
Inti teorema ini adalah: jika semua fungsi f memiliki probabilitas yang sama, maka probabilitas untuk mengamati barisan nilai yang acak berukuran 𝑚 selama proses optimasi tidak bergantung pada algoritma yang digunakan.
Theorem 2 establishes a similar, but "more subtle", NFL result for time-varying objective functions.
Teorema 2 menetapkan hasil NFL yang serupa, tetapi "lebih halus" untuk fungsi tujuan yang berubah terhadap waktu.
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".
Teorema NFL secara eksplisit bukan berdasarkan pertanyaan terkait apa yang dapat diinferensikan (dalam kasus NFL untuk pemelajaran mesin) atau ditemukan (dalam kasus NFL untuk pencarian) ketika "lingkungan (environment)-nya seragam acak".
Rather uniform randomness was used as a tool, to compare the number of environments for which algorithm
Sebaliknya, keacakaan yang seragam tersebut digunakan sebagai alat untuk membandingkan jumlah lingkungan yang algoritma
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.
Pernyataan tentang himpunan prior inilah yang paling penting terkait NFL, bukan persamaan performa dua algoritma pada distribusi prior tunggal yang memberikan probabilitas sama untuk semua lingkungan.
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.
Meskipun NFL memiliki signifikansi dalam memahami batasan fundamental suatu himpunan masalah, tetapi NFL tidak menyediakan informasi tentang setiap contoh masalah yang mungkin muncul dalam implementasinya.
Therefore, if we have a "good" problem in practice or if we can choose a "good" learning algorithm for a given particular problem instance, then the NFL does not mention any limitation about this particular problem instance.
Oleh karena itu, jika terdapat masalah yang "baik" dalam konteks praktis, atau jika dapat dipilih algoritma pemelajaran yang "baik" untuk suatu masalah tertentu, maka NFL tidak memberikan batasan spesifik terhadap masalah tersebut.
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.
mendorong generalisasi dari algoritma pemelajaran atau heuristik pencarian, penting untuk memahami perbedaan antara logika matematis yang tepat dari NFL dan interpretasinya secara intuitif.
In other words, 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.
Dengan kata lain, untuk memutuskan apakah akan menggeneralisasi d dengan C atau D, kita melihat mana di antara keduanya yang memiliki kinerja di luar sampel yang lebih
Call this algorithm A. (Arguably, A is a simplified model of the scientific method itself.)
Sebut saja algoritma ini A. (Bisa dibilang, A adalah model sederhana dari metode ilmiah itu sendiri.)
We could also use anti-cross-validation to make our choice.
Kita juga bisa menggunakan anti-validasi-silang untuk menentukan pilihan.
In other words, we could choose between C and D based on which has worse out-of-sample performance within d. Again, since C and D are fixed, this use of anti-cross-validation is itself an algorithm.
, kita dapat memilih antara C dan D berdasarkan mana yang memiliki kinerja di luar sampel yang lebih buruk pada d. Kemudian, karena C dan D adalah tetap, penggunaan anti-validasi silang ini sendiri merupakan sebuah algoritma.
Call that algorithm B. NFL tells us (loosely speaking) that B must beat A on just as many target functions (and associated datasets d) as A beats B.
Sebut saja algoritma itu B. Secara umum, NFL mengungkapkan bahwa B harus mengalahkan
In this very specific sense, the scientific method will lose to the "anti" scientific method just as readily as it wins.
A atas B. Dalam pengertian yang sangat spesifik ini, metode ilmiah juga akan kalah dengan “anti” metode ilmiah dengan mudah sama seperti metode ilmiah itu menang.
NFL only applies if the target function is chosen from a uniform distribution of all possible functions.
NFL hanya berlaku jika fungsi target dipilih dari distribusi seragam dari semua fungsi yang mungkin.
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.
Jika hal ini tidak terjadi, dan fungsi target tertentu lebih mungkin dipilih dibandingkan yang lain, maka A mungkin berkinerja lebih baik daripada B secara keseluruhan.
The contribution of NFL is that it tells us that choosing an appropriate algorithm requires making assumptions about the kinds of target functions the algorithm is being used for.
Kontribusi NFL adalah memberi tahu kita bahwa memilih algoritma yang tepat memerlukan asumsi tentang jenis fungsi target yang digunakan algoritma tersebut.
With no assumptions, no "meta-algorithm", such as the scientific method, performs better than random choice.
Tanpa asumsi, tidak ada "meta-algoritma", seperti metode ilmiah, yang berkinerja lebih baik daripada pilihan acak.
If Occam's razor is correct, for example if sequences of lower Kolmogorov complexity are more probable than sequences of higher complexity, then (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).
Jika pisau cukur Ockham benar, misalnya jika rangkaian dengan kompleksitas Kolmogorov yang lebih rendah lebih mungkin terjadi daripada rangkaian dengan kompleksitas yang lebih tinggi, maka (seperti yang diamati dalam kehidupan nyata) beberapa algoritma, seperti validasi silang, rata-rata berkinerja lebih baik pada masalah praktis (ketika dibandingkan dengan pilihan acak atau dengan validasi anti-silang).
However, there are major formal challenges in using arguments based on Kolmogorov complexity to establish properties of the real world, since it is uncomputable, and undefined up to an arbitrary additive constant.
Di sisi lain, terdapat tantangan formal besar dalam menggunakan argumen berdasarkan kompleksitas Kolmogorov untuk membuktikan sifat dunia nyata, karena sifatnya yang tidak dapat dihitung, dan tidak terdefinisi hingga konstanta tambahan yang sembarang.