Teorema tidak ada makan siang gratis

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) yang berarti tidak ada jalan pintas yang mudah menuju kesuksesan. Teorema ini pertama kali dipublikasikan dalam makalah ilmiah keduanya yang berjudul "No Free Lunch Theorems for Optimization" pada tahun 1997.^[1] Wolpert sebelumnya telah menemukan teorema serupa untuk pemelajaran mesin (inferensi statistik).^[2]

Pada tahun 2005, Wolpert dan Macready menjelaskan teorema pertama NFL dalam makalah mereka, "menyatakan bahwa dua sembarang algoritma optimasi akan memiliki performa rata-rata yang sama, jika diuji pada seluruh kemungkinan masalah".^[3]

Teorema "tidak ada makan siang gratis" (NFL) lebih mudah disebutkan dan dipahami, dibandingkan teorema sebenarnya yang dibuktikan Wolpert dan Macready. Teorema NFL kurang kuat dan tidak mencakup keseluruhan temuan mereka. Berbagai penelitian telah dilakukan untuk memperluas penelitian Wolpert dan Macready secara substansial. Penggunaan teorema NFL dalam konteks area penelitian tersendiri adalah teorema tidak ada makan siang gratis dalam pencarian dan optimasi. Teorema tersebut menjadi subdisiplin sendiri yang berfokus dalam analisis data secara matematis untuk sifat-sifat statistik, khususnya dalam pencarian^[4] dan optimasi.^[1]

Meskipun beberapa peneliti melihat teorema NFL sebagai suatu wawasan penting, peneliti lain berpendapat bahwa NFL kurang relevan dalam penelitian pembelajaran mesin.^[5] ^[6]

Contoh

Misalkan sebuah semesta hipotetis yang berdurasi tepat dua hari. Pada setiap harinya, semesta ini hanya memuat tepat satu objek, yang bisa berupa persegi atau segitiga. Dengan batasan tersebut, semesta ini memiliki empat kemungkinan sejarah yang dapat terjadi:

(persegi, segitiga): semesta tersebut berisi persegi pada hari ke-1 dan segitiga pada hari ke-2
(persegi, persegi)
(segitiga, segitiga)
(segitiga kotak)

Setiap strategi prediksi yang berhasil untuk sejarah #2, dengan meramalkan persegi di hari ke-2 jika ada persegi di hari ke-1, pasti akan gagal untuk sejarah #1, dan sebaliknya. Jika semua sejarah memiliki probabilitas yang sama, maka semua strategi prediksi akan memiliki performa yang setara, dengan akurasi 0.5.^[7]

Asal muasal

Wolpert dan Macready memaparkan dua teorema NFL yang berkaitan erat dengan teorema pepatah "no free lunch" yang dikenal luas. 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.^[1]
Terjemahan:
Hasil-hasil terkait yang kami sebut sebagai teorema NFL menunjukkan bahwa performa baik suatu algoritma pada kelas masalah tertentu harus dibayar dengan performa yang lebih buruk pada seluruh masalah yang tersisa.

Teorema pertama menghipotesiskan fungsi objektif yang tidak berubah selama proses optimasi berlangsung dan teorema kedua menghipotesiskan fungsi objektif yang dapat berubah selama proses optimasi.^[1]

Teorema 1: Untuk sembarang algoritma a₁ and a₂, pada langkah iterasi m

\sum _{f}P(d_{m}^{y}\mid f,m,a_{1})=\sum _{f}P(d_{m}^{y}\mid f,m,a_{2}),

dengan $d_{m}^{y}$ menunjukkan himpunan berurutan berukuran $m$ dari nilai biaya (cost values) $y$ yang dihasilkan dari masukan-masukan $x\in X$ , $f:X\rightarrow Y$ yang merupakan fungsi yang dioptimalkan, dan $P(d_{m}^{y}\mid f,m,a)$ adalah probabilitas bersyarat untuk memperoleh himpunan nilai biaya tertentu dari algoritma $a$ yang dijalankan sebanyak $m$ kali pada fungsi $f$ . Teorema tersebut dapat dirumuskan secara ekuivalen sebagai berikut:

Theorem 1: Given a finite set

V

and a finite set

S

of real numbers, assume that

f:V\to S

is chosen at random according to uniform distribution on the set

S^{V\!}

of all possible functions from

V

to

S

. For the problem of optimizing

f

over the set

V

, then no algorithm performs better than blind search.

Terjemahan:

Teorema 1: Diberikan himpunan terbatas

V

dan himpunan terbatas

S

berisi bilangan riil, diasumsikan bahwa

f:V\to S

dipilih secara acak sesuai dengan distribusi seragam pada himpunan

S^{V\!}

dari semua fungsi yang mungkin dari

V

ke

S

. Untuk masalah optimasi

f

pada himpunan

V

, maka tidak ada algoritma yang dapat mengalahkan pencarian buta.

Pencarian buta dalam konteks ini berarti bahwa pada setiap langkah algoritma, elemen $v\in V$ dipilih secara dipilih secara acak dari elemen $V$ yang belum dipilih sebelumnya dengan distribusi probabilitas seragam.

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. Dalam kerangka analitik Wolpert dan Macready, performa dipengaruhi oleh urutan nilai yang diamati (bukan misalnya waktu komputasi). Dengan demikian, mudah disimpulkan bahwa semua algoritma memiliki distribusi performa yang sama ketika fungsi objektif dipilih secara acak dan seragam. Ini juga berarti semua algoritma memiliki performa rata-rata yang sama. Namun, performa rata-rata yang sama untuk semua algoritma tidak serta merta menyiratkan Teorema 1, sehingga teorema "no free lunch" dalam pepatah tidak sepenuhnya setara dengan teorema yang asli.

Teorema 2 menetapkan hasil NFL yang serupa, tetapi "lebih halus" untuk fungsi tujuan yang berubah terhadap waktu.^[1]

Motivasi

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". Sebaliknya, keacakaan yang seragam tersebut digunakan sebagai alat untuk membandingkan jumlah lingkungan yang algoritma A mengungguli algoritma B dengan jumlah lingkungan yang algoritma B mengungguli algoritma A. NFL menunjukkan bahwa (dengan bobot yang sesuai)^{[butuh klarifikasi]}, jumlah lingkungan di kedua himpunan tersebut sama banyaknya yang berarti bahwa kedua algoritma memiliki peluang yang sama untuk unggul di lingkungan yang berbeda-beda.

Hal ini berlaku untuk banyak definisi tentang apa sebenarnya makna dari suatu “lingkungan”. Secara khusus, terdapat banyak distribusi prior (dengan bobot yang sesuai) yang algoritma pemelajaran A mengalahkan B (dalam rata-rata) dan sebaliknya.^{[butuh rujukan]} 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.

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. NFL hanya menyatakan apa yang tercakup dalam pernyataan matematisnya tanpa tambahan. Sebagai contoh, konsep ini berlaku pada situasi yang algoritma telah ditetapkan sebelumnya dan kemudian dipilih masalah yang algoritma tersebut terburuk dalam pengerjaannya. 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. Meskipun NFL mungkin terlihat bertentangan dengan hasil dari penelitian lain yang mendorong generalisasi dari algoritma pemelajaran atau heuristik pencarian, penting untuk memahami perbedaan antara logika matematis yang tepat dari NFL dan interpretasinya secara intuitif.^[8]

Implikasi

Untuk mengilustrasikan salah satu implikasi kontra-intuitif dari NFL, misalkan kita memilih dua algoritma pemelajaran terarah (supervised learning), C dan D. Kemudian kita mengambil sampel fungsi target f untuk menghasilkan satu himpunan pasangan masukan-luaraan, d. Bagaimana kita memilih apakah akan melatih C atau D pada d, untuk membuat prediksi keluaran apa yang akan dikaitkan dengan titik yang terletak di luar d?

Di hampir semua ilmu sains dan statistik, sudah menjadi hal yang umum untuk menjawab pertanyaan ini–memilih antara C dan D–dengan menjalankan validasi silang pada d dengan kedua algoritma tersebut. 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 baik ketika diuji dalam d.

Karena C dan D adalah tetap, penggunaan validasi silang untuk memilih di antara keduanya merupakan suatu algoritma, yaitu cara menggeneralisasi dari kumpulan data yang berubah-ubah. Sebut saja algoritma ini A. (Bisa dibilang, A adalah model sederhana dari metode ilmiah itu sendiri.)

Kita juga bisa menggunakan anti-validasi-silang untuk menentukan pilihan. Dengan kata lain, 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. Sebut saja algoritma itu B.

Secara umum, NFL mengungkapkan bahwa B harus mengalahkan A pada jumlah fungsi target (dan kumpulan data terkait d) yang sama banyaknya dengan keunggulan 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.^[9]

NFL hanya berlaku jika fungsi target dipilih dari distribusi seragam dari semua fungsi yang mungkin. 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. Kontribusi NFL adalah memberitahu kita bahwa memilih algoritma yang tepat memerlukan asumsi tentang jenis fungsi target yang digunakan algoritma tersebut. Tanpa asumsi, tidak ada "meta-algoritma", seperti metode ilmiah, yang berkinerja lebih baik daripada pilihan acak.

Meskipun beberapa pakar berpendapat bahwa NFL mengungkapkan wawasan penting, sebagian lainnya berpendapat bahwa NFL tidak begitu relevan dengan penelitian pemelajaran mesin.^[5] ^[6] 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).^[10]

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. Sebagian disadari akan tantangan-tantangan ini, baru-baru ini diusulkan bahwa ada cara untuk mengatasi teorema no free lunch tanpa memanggil mesin Turing, dengan menggunakan "meta-induksi".^[11] ^[12]

Lihat juga

Referensi

^ ^a ^b ^c ^d ^e 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.
^ Wolpert, David (1996), "The Lack of A Priori Distinctions between Learning Algorithms", Neural Computation, pp. 1341–1390. Diarsipkan 2016-12-20 di 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". Technical Report SFI-TR-95-02-010. Santa Fe Institute.
^ ^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.
^ ^a ^b Giraud-Carrier, Christophe, 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). "How do Simple Rules 'Fit to Reality' in a Complex World?". Minds and Machines. 9 (4): 543–564. doi:10.1023/A:1008304819398.
^ 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, December 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, Berlin, Heidelberg, 2013.
^ Schurz, G. (2019). Hume's Problem Solved: The Optimality of Meta-Induction. MIT Press.
^ Wolpert, D. H. (2023). "The Implications of the No-Free-Lunch Theorems for Meta-induction". Journal for General Philosophy of Science. 54: 421–432. arXiv:2103.11956  . doi:10.1007/s10838-022-09609-2.

Pranala luar

[WM97-1] 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.

[Wolpert96-2] Wolpert, David (1996), "The Lack of A Priori Distinctions between Learning Algorithms", Neural Computation, pp. 1341–1390. Diarsipkan 2016-12-20 di Wayback Machine.

[WM-coev-3] Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches", IEEE Transactions on Evolutionary Computation, 9(6): 721–735

[WM95-4] Wolpert, D. H.; Macready, W. G. (1995). "No Free Lunch Theorems for Search". Technical Report SFI-TR-95-02-010. Santa Fe Institute.

[whitley-5] Whitley, Darrell, and Jean Paul Watson. "Complexity theory and the no free lunch theorem." In Search Methodologies, pp. 317–339. Springer, Boston, MA, 2005.

[carrier-6] Giraud-Carrier, Christophe, 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.

[7] Forster, Malcolm R. (1999). "How do Simple Rules 'Fit to Reality' in a Complex World?". Minds and Machines. 9 (4): 543–564. doi:10.1023/A:1008304819398.

[KA-deep-8] Kawaguchi, K., Kaelbling, L.P, and Bengio, Y.(2017) "Generalization in deep learning", https://arxiv.org/abs/1710.05468

[9] Wolpert, D.H. (2013) "What the no free lunch theorems really mean", Ubiquity, Volume 2013, December 2013, DOI:10.1145/2555235.2555237

[10] 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, Berlin, Heidelberg, 2013.

[SCHU19-11] Schurz, G. (2019). Hume's Problem Solved: The Optimality of Meta-Induction. MIT Press.

[WOLP23-12] Wolpert, D. H. (2023). "The Implications of the No-Free-Lunch Theorems for Meta-induction". Journal for General Philosophy of Science. 54: 421–432. arXiv:2103.11956  . doi:10.1007/s10838-022-09609-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]