Hasil empiris dalam makalah CS

Saya baru di bidang CS dan saya perhatikan bahwa di banyak makalah yang saya baca, tidak ada hasil empiris (tidak ada kode, hanya lemma dan bukti). Mengapa demikian? Menimbang bahwa Ilmu Komputer adalah ilmu, tidakkah seharusnya mengikuti metode ilmiah?

Matematika juga ilmu, dan Anda harus mencari waktu yang lama untuk menemukan hasil empiris yang dipublikasikan di bidang ini (walaupun saya kira pasti ada beberapa). Ada domain ilmiah lain di mana "lemma dan bukti" dinilai lebih dari pengalaman, seperti fisika kuantum. Yang mengatakan, sebagian besar ilmu mencampur teori dan praktik (dengan berbagai rasio), dan Ilmu Komputer tidak terkecuali.

Ilmu Komputer berakar pada Matematika (lihat biografi Turing misalnya http://en.wikipedia.org/wiki/Alan_Turing ), dan karena itu banyak hasil (umumnya dijuluki sebagai dalam bidang "ilmu komputer teoretis") terdiri dalam bukti bahwa komputer dalam beberapa model komputasi dapat menyelesaikan beberapa masalah dalam sejumlah operasi tertentu (misalnya konferensi seperti FOCS, STOC, SODA, SoCG, dll.). Namun demikian, banyak hasil lain dari ilmu komputer berkaitan dengan penerapan teori-teori tersebut ke kehidupan praktis, melalui analisis hasil eksperimen (misalnya konferensi seperti WADS, ALENEX, dll ...).

Sering disarankan bahwa cita-cita adalah keseimbangan yang baik antara teori dan praktik, seperti dalam "Ilmu Pengetahuan Alam", di mana pengamatan eksperimen mendorong munculnya teori-teori baru, yang pada gilirannya menyarankan eksperimen baru untuk mengkonfirmasi atau menegaskan teori-teori tersebut: seperti banyak konferensi berupaya menerima hasil eksperimen dan teoretis (mis. ESA, ICALP, LATIN, CPM, ISAAC, dll ...). Subbidang "Algoritma dan Struktur Data" dalam ilmu komputer mungkin menderita ketidakseimbangan dalam arti bahwa konferensi "Teoritis" umumnya lebih tinggi peringkatnya daripada yang eksperimental. Saya percaya bahwa ini tidak benar di subbidang ilmu komputer lainnya, seperti HCI atau AI.

Semoga ini bisa membantu?

Menerapkan algoritma dengan baik adalah keterampilan yang membutuhkan seperangkat alat yang berbeda dari sekadar membuktikan teorema. Banyak algoritma yang ditemukan oleh komunitas teori memang telah diimplementasikan dalam praktiknya (walaupun saya ingin melihat komunitas teori mengambil peran yang lebih besar dalam proses ini). Fisika tidak meminta peneliti yang sama untuk melakukan teori dan eksperimen, meskipun diharapkan kedua kelompok berkomunikasi. Mengapa Anda tidak berharap melihat kesenjangan yang sama dalam ilmu komputer?

TAMBAH DALAM EDIT:

Memperluas komentar saya sebagai jawaban untuk Suresh tentang apa yang saya maksud dengan "peran" di atas, di Bell Labs dan AT&T Labs, para peneliti dalam algoritma didorong untuk berbicara dengan orang-orang dalam pembangunan. Saya tidak melakukan sebanyak ini seperti yang seharusnya saya lakukan, tetapi saya mendapatkan setidaknya satu kertas dari itu, dan saya pikir itu akan baik untuk lapangan jika ada lebih banyak komunikasi antara orang-orang secara teori di universitas dan praktisi . Ini tidak berarti bahwa saya pikir semua orang yang membuat algoritma harus mengkodekannya (walaupun itu praktis).

Di sisi lain, algoritma pengkodean (atau memiliki kode siswa) yang menurut Anda praktis dapat berguna untuk menyesuaikannya dengan praktisi. Pertimbangkan satu contoh. Lempel dan Ziv menulis dua makalah teknis pada tahun 1977 dan 1978 tentang algoritma kompresi data baru. Semua orang mengabaikannya. Pada tahun 1984, Welch menulis sebuah makalah yang kurang teknis memberikan sedikit sentuhan pada LZ78 yang agak meningkatkan kinerjanya, dan memberikan hasil penelitian kecil membandingkan kinerjanya dengan metode kompresi data lainnya. Itu diterbitkan dalam jurnal yang dibaca oleh sejumlah programmer, dan algoritma diberikan oleh beberapa baris pseudocode. Metode ini dengan cepat diadaptasi di sejumlah tempat, akhirnya menghasilkan perselisihan kekayaan intelektual yang terkenal.

Tentu saja, salah satu cara terbaik bagi para peneliti algoritma untuk berkomunikasi dengan praktik adalah menghasilkan mahasiswa pascasarjana yang bekerja dan bekerja di Google, IBM, atau perusahaan lain, dan kami sudah melakukan itu. Cara lain mungkin untuk menjawab pertanyaan praktisi di forum ini. Semoga kami melakukan pekerjaan yang masuk akal juga.

Salah satu area penelitian yang menggunakan metode empiris dan metode Theoretical Computer Science adalah bidang yang disebut "Experimental Algorithmics" atau "Algorithm Engineering". Seperti yang disebutkan Chris, komputasi berkinerja tinggi sangat bergantung pada hal ini karena sistem modern memiliki masalah cache dan latensi yang rumit sehingga kami memiliki pemodelan yang sulit.

Gerth Brodal dan Peter Sanders adalah contoh yang baik dari para peneliti yang mempertahankan kaki di ranah "bukti" dan "empiris".

--Perbaruan 20/01/2013 - Saya juga akan menyebutkan presentasi yang hebat oleh Robert Sedgewick .

Ini tergantung pada disiplin Anda; seperti yang dikatakan Jeremy, ada spektrum teori vs. praktik.

Topik-topik seperti kompleksitas cenderung ditimbang ke sisi teori, karena seringkali tujuannya adalah untuk menemukan batas untuk ruang atau runtime. Menerapkan algoritma dalam C ++ dan kemudian menjalankannya beberapa kali tidak akan membuktikan bahwa masalah adalah NP-complete.

Sebagai kebalikannya, komputasi kinerja tinggi (dengan konferensi seperti Supercomputing ) semuanya empiris; tidak ada yang akan menyerahkan bukti ke publikasi HPC karena ada terlalu banyak variabilitas berkaitan dengan hirarki memori dan overhead kernel.

Jadi apa yang tampaknya seperti pertanyaan yang sama (Berapa lama waktu yang dibutuhkan untuk menjalankan?) Akan didekati dengan dua cara yang sangat berbeda tergantung pada tujuan, teknik, komunitas, dll. Lihat Poul-Henning Kamp Anda Melakukannya Salah untuk contoh disonansi.

Dalam penelitian bahasa pemrograman banyak ide untuk konstruksi bahasa pemrograman baru atau mekanisme pemeriksaan tipe baru berasal dari teori (mungkin diinformasikan oleh pengalaman dalam praktik, mungkin tidak). Seringkali sebuah makalah ditulis tentang mekanisme seperti itu dari perspektif formal / teoretis / konseptual. Itu relatif mudah dilakukan. Berikutnya adalah rintangan pertama: menerapkan konstruksi baru dalam konteks kompiler yang ada dan bereksperimen dengannya, dalam hal efisiensi atau fleksibilitas. Ini juga relatif mudah.

Tetapi dapatkah kita kemudian mengatakan bahwa konstruksi pemrograman merupakan kemajuan bagi ilmu pemrograman? Bisakah kita mengatakan itu membuat program menulis lebih mudah? Bisakah kita mengatakan bahwa itu membuat bahasa pemrograman lebih baik?

Jawabannya adalah tidak. Evaluasi empiris yang tepat yang melibatkan sejumlah programmer berpengalaman dalam periode waktu yang besar akan diperlukan untuk menjawab pertanyaan-pertanyaan semacam itu. Penelitian ini hampir tidak pernah dilakukan. Satu-satunya hakim dari nilai bahasa pemrograman (dan konstruknya) adalah popularitas bahasa tersebut. Dan untuk puritan bahasa pemrograman, ini bertentangan dengan apa yang dikatakan hipotesis kami.

Mungkin saya kehilangan motivasi untuk pertanyaan Anda, tetapi ada banyak contoh hasil empiris yang memotivasi penelitian, algoritme, dan hasil lainnya.

MP3 menggunakan psychoacoustic untuk mengoptimalkan algoritma pengkodean manusia.

Plouffe memberikan penjelasan tentang penemuan algoritma keran BBP untuk digit$\pi$ mana dia menceritakan penggunaan apa pun yang Algoritma Relation Algoritma Mathematica gunakan untuk menemukan rumus.

Sejalan dengan itu, Bailey dan Borwein adalah pendukung besar matematika eksperimental. Lihat "Komputer sebagai Crucible: Pengantar Matematika Eksperimental" , "Wisata Komputasi dalam Teori Angka" antara lain . Orang mungkin berpendapat bahwa ini adalah Matematika yang lebih eksperimental, tetapi saya berpendapat bahwa pada tingkat diskusi ini perbedaannya adalah semantik.

Transisi fase masalah NP-Complete adalah area lain di mana hasil empiris banyak digunakan. Lihat Monasson, Zecchina, Kirkpatrick, Selman dan Troyansky dan Gent dan Walsh sebagai permulaan, meskipun ada banyak, banyak lagi (lihat di sini untuk survei singkat).

Meskipun tidak cukup pada tingkat Ilmu Komputer Teoritis atau Matematika, ada diskusi di sini tentang bagaimana runtime case utilitas unix utilitas grep mengalahkan algoritma kasus terburuk yang dioptimalkan karena bergantung pada fakta bahwa itu mencari teks yang dapat dibaca manusia (grep melakukan hal yang buruk atau terburuk pada file dengan karakter acak di dalamnya).

Bahkan Gauss menggunakan bukti eksperimental untuk memberikan hipotesisnya tentang teorema bilangan prima.

Penambangan data ( solusi Bellkor untuk Hadiah Netflix untuk membuat sistem rekomendasi yang lebih baik) mungkin diperdebatkan sebagai teori yang sepenuhnya didasarkan pada bukti empiris. Kecerdasan Buatan (algoritma genetika, jaringan saraf, dll.) Sangat bergantung pada eksperimen. Kriptografi terus menerus mendorong dan menarik antara pembuat kode dan pemecah kode. Saya benar-benar hanya menyebutkan beberapa dan jika Anda melonggarkan definisi empiris Anda, maka Anda bisa menciptakan jaringan yang lebih luas.

Saya minta maaf karena begitu sibuk menjawab pertanyaan Anda, tetapi saya harap saya telah memberikan setidaknya beberapa contoh yang membantu.