Sunday, May 11, 2014

Lecture Note: No Free Lunch

Setelah lama berkecimpung di dunia digital, saya sering mendapati tulisan "Free as speech, not free as beer." Ya kurang lebih maksudnya tentang kebebasan berpendapat. Masih ada hubungannya dengan kata "Free", tulisan lecture note yang dibuat oleh Pak Lala Septem Riza kali ini membahas tentang "No Free Lunch".
Berikut tulisan lecture note yang ditulis di grup jurusan Ilmu Komputer UPI:

[LECTURE NOTE] "No free lunch" theorem. Atau berarti "tak ada makan siang yang gratis". Dulu di Amerika, pernah punya kebiasaan memberikan makanan (camilan) gratis jika kita pesan bir di siang hari. Tapi kemudian, kebiasaan ini dihapuskan karena alasan ekonomi, dll. Sehingga, dikatakan tak ada lagi makan siang yang gratis. Walaupun, sampai saat ini di Spanyol masih punya budaya makan siang (camilan) gratis, kalau kita pesan minum bir (atau teh kalau buat saya :D), yang biasa dinamakan "Tapas". Jadi kita bayarnya seharga teh, tapi kita disuguhi camilan, seperti ikan goreng, udang goreng, burger, dll. Trus, "No free lunch" juga bisa berarti bahwa tak ada traktir - traktiran di budaya barat (Eropa dan Amerika). Jadi, jangan berharap bakal ditraktir jika diajakin makan siang bareng. Bahkan untuk pesta syukuran teman yg baru aja defense S3 sekalipun, kita harus bayar sendiri - sendiri. Jadi curcol nihh ceritanya hehehe, tapi inilah salah satu indahnya Indonesia, yang orangnya suka saling traktir .Tapi apa hubungannya budaya "no free lunch" dengan computer science ? . Teorema "no free lunch" menyatakan bahwa "tak ada satupun algoritma yang bisa mendapatkan akurasi terbaik untuk segala masalah". Jadi, jika ada algoritma A yang hebat di masalah x, maka algorithma A itu bisa jadi memberi akurasi yang jelek untuk masalah y. Itulah yang disebut tak ada makanan siang gratis, karena algorithma itu pasti membayar (jelek akurasinya) untuk masalah yang lain. Bahkan, bisa dikatakan bahwa algoritma yang baru dikembangkan dan dirasa canggih itu sebenarnya tak lebih baik dari algoritma acak/random atau brute force yang sederhana sekalipun untuk segala masalah. Teorema ini berlaku untuk algoritma di bidang supervised machine learning (classification) dan pelacakan&optimasi.
Apa efek teorema ini bagi kita ? Kita terkadang (entah di tugas akhir, dll) ingin membandingkan suatu algoritma dengan algoritma lain pada suatu kasus tertentu. Maka dengan memahami teorema ini, kita jadi lebih hati - hati dalam memutuskan hipotesa kita. Misalkan, tak lagi berkata: algoritma kita lebih baik dari algoritma lain. Karena kalaupun algoritma kita lebih bagus, maka sebenarnya algoritma kita bagus untuk kasus itu saja, untuk kasus lain algoritma kita bisa jadi lebih jelek. Disamping itu, untuk membandingkan algoritma kita dengan yang lain diperlukan mekanisme penarikan kesimpulan tertentu (secara statistik), tak bisa hanya membandingkan dengan satu kasus saja. Akhir kata, kalaupun kita tak pernah membandingkan algoritma - algoritma di tugas akhir, minimal kita jadi tahu kalau diajakin makan siang ama orang bule, maka kita harus siapin duit sendiri :D(kecuali dibilangin bakal dibayar-RED).

No comments:

Post a Comment

Comment is caring :)