Apa implikasi teorema “Tanpa Makan Siang Gratis” untuk pembelajaran mesin?

Teorema No Free Lunch (NFL) menyatakan (lihat makalah Coevolutionary Free Lunches oleh David H. Wolpert dan William G. Macready)

setiap dua algoritma setara ketika kinerjanya dirata-rata untuk semua masalah yang mungkin terjadi

Apakah teorema "Tanpa Makan Siang Gratis" itu benar? Apa artinya itu sebenarnya? Contoh yang bagus (dalam konteks ML) menggambarkan pernyataan ini akan bagus.

Saya telah melihat beberapa algoritma yang berperilaku sangat buruk, dan saya sulit percaya bahwa mereka benar-benar mengikuti teorema yang disebutkan di atas, jadi saya mencoba memahami apakah interpretasi saya terhadap teorema ini benar atau tidak. Atau apakah itu hanya teorema hias seperti teorema Universal Approximation Cybenko?

Ini adalah reaksi yang sangat umum setelah pertama kali bertemu teorema No Free Lunch (NFL). Yang untuk pembelajaran mesin sangat tidak intuitif, karena terbang di hadapan segala sesuatu yang dibahas dalam komunitas ML. Yang mengatakan, teorema itu benar, tetapi apa artinya terbuka untuk beberapa perdebatan.

Untuk menyatakan kembali teorema bagi orang-orang yang tidak mengetahuinya, teorema NFL untuk pembelajaran mesin benar-benar merupakan kasus khusus dari teorema NFL untuk pencarian dan optimisasi lokal . Versi pencarian lokal lebih mudah dimengerti. Teorema tersebut membuat klaim berikut yang agak radikal:

Rata-rata di semua masalah optimasi yang mungkin terjadi, kualitas rata-rata solusi yang ditemukan oleh algoritma pencarian lokal apa pun yang Anda pilih untuk digunakan persis sama dengan kualitas rata-rata algoritma "pencarian" lokal yang hanya menghasilkan solusi yang mungkin dengan mengambil sampel secara seragam secara acak secara acak dari luar angkasa. dari semua solusi.

Perumusan lain, ketika orang menginginkan reaksi yang lebih kuat, adalah mengatakan bahwa jika Anda ingin menemukan solusi terbaik untuk suatu masalah, sama baiknya untuk mencoba hal-hal yang tampaknya membuat solusi Anda menjadi lebih buruk berulang daripada mencoba hal-hal yang tampaknya membuat solusi Anda menjadi lebih baik secara berulang. Rata-rata, kedua pendekatan ini sama-sama bagus.

Oke, jadi mengapa ini benar? Kuncinya ada di detail. Wolpert kadang-kadang menggambarkan teorema sebagai spesialisasi pekerjaan Hume pada masalah induksi . Pernyataan dasar dari masalah induksi adalah: kita tidak memiliki dasar logis untuk mengasumsikan bahwa masa depan akan seperti masa lalu. Secara logis, tidak ada alasan bahwa hukum fisika tidak bisa berubah secara radikal besok saja. Dari perspektif yang murni logis , sangat masuk akal bahwa masa depan dapat berbeda dari masa lalu dalam berbagai cara. Masalah Hume adalah bahwa, secara umum masa depan adalah seperti masa lalu dalam banyak cara. Dia mencoba merumuskan argumen filosofis (logis) bahwa ini perlu dilakukan, tetapi pada dasarnya gagal.

Teorema No Free Lunch mengatakan hal yang sama. Jika Anda tidak tahu seperti apa ruang pencarian Anda, maka jika Anda mengulangi dugaan Anda seperti apa solusi yang baik, sebagai tanggapan terhadap pengamatan yang Anda buat di masa lalu tentang seperti apa solusi yang baik itu (yaitu belajar dari data), maka kemungkinan besar operasi yang Anda lakukan membantu karena menyakitkan. Itu sebabnya bagian "rata-rata atas semua masalah optimasi yang mungkin" adalah kuncinya. Untuk setiap masalah optimasi di mana pendakian bukit adalah strategi yang bagus setelahnya$k$bergerak, kita dapat membuat satu yang identik, kecuali bahwa langkah mendaki bukit k mengarah pada solusi yang mengerikan. Buktinya sebenarnya lebih halus dari itu, tapi itu ide dasarnya.

Ringkasan awam yang sangat singkat mungkin:

Algoritma pembelajaran mesin hanya dapat dibuat untuk bekerja lebih baik pada beberapa jenis masalah dengan dibuat bekerja lebih buruk pada jenis masalah lainnya.

Jadi, apa ini berarti dalam arti praktis? Ini berarti bahwa Anda perlu memiliki alasan apriori untuk berpikir bahwa algoritma Anda akan efektif pada masalah tertentu . Persis apa yang baik alasan penampilan suka adalah subyek perdebatan sengit dalam komunitas ML. Ini sangat terkait erat dengan tradeoff bias / varians .

Beberapa tanggapan umum adalah:

• Ketika Anda melihat masalah pengoptimalan baru, meskipun bisa memiliki struktur acak, masalah yang sebenarnya kita temui di dunia nyata jauh lebih teratur, dan tema umum tertentu hadir, seperti kenyataan bahwa bergerak " menanjak "(meminimalkan kesalahan) iteratif cenderung mengarah pada solusi yang baik. Pada dasarnya, aliran pemikiran ini mengatakan NFL adalah teorema hias: sebagian besar algoritma ML bekerja lebih baik pada "jenis masalah yang kita lihat dalam kehidupan nyata", dengan bekerja lebih buruk pada "jenis masalah yang tidak kita lihat dalam kehidupan nyata".
• Ketika Anda melihat masalah pengoptimalan baru di [masukkan domain aplikasi favorit Anda], meskipun bisa memiliki struktur acak, masalah cenderung terlihat seperti [apa pun yang Anda pikirkan], yang membuat [algoritme favorit Anda] lebih banyak efektif daripada tebakan acak.
• Wolpert & McCready sendiri menerbitkan hasil yang menarik yang menunjukkan bahwa sebenarnya ada proses optimasi khusus, berdasarkan co-evolusi, yang secara konsisten lebih baik daripada menebak secara acak.

Bagaimanapun, tidak dapat disangkal bahwa beberapa algoritma lebih baik daripada yang lain, dalam sub-domain tertentu (kita bisa melihatnya secara empiris). NFL memberitahu kita bahwa untuk menjadi lebih baik di sana, mereka harus menjadi lebih buruk di tempat lain. Pertanyaan yang perlu diperdebatkan adalah apakah "tempat lain" adalah masalah nyata, atau murni buatan.