Membenarkan analisis kasus terburuk asimptotik kepada para ilmuwan

Saya telah berupaya memperkenalkan beberapa hasil dari kompleksitas komputasi ke dalam biologi teoretis, terutama evolusi & ekologi , dengan tujuan menjadi menarik / berguna bagi para ahli biologi. Salah satu kesulitan terbesar yang saya hadapi adalah membenarkan kegunaan analisis kasus terburuk asimptotik untuk batas bawah. Apakah ada referensi panjang artikel yang membenarkan batas bawah dan analisis kasus terburuk asimptotik kepada khalayak ilmiah?

Saya benar-benar mencari referensi yang baik yang bisa saya tunda dalam tulisan saya daripada harus melalui pembenaran di ruang terbatas yang saya miliki (karena itu bukan titik pusat artikel). Saya juga mengetahui jenis dan paradigma analisis lainnya, jadi saya tidak mencari referensi yang mengatakan kasus terburuk adalah analisis "terbaik" (karena ada pengaturan ketika sangat tidak), tetapi tidak completeletely berguna: masih bisa memberi kita wawasan teoritis yang berguna dalam perilaku aktual algoritma pada aktual input. Penting juga tulisan ini ditujukan untuk para ilmuwan umum dan bukan hanya insinyur, ahli matematika, atau ilmuwan komputer.

Sebagai contoh, esai Tim Roughgarden yang memperkenalkan teori kompleksitas kepada para ekonom berada di jalur yang benar untuk apa yang saya inginkan. Namun, hanya bagian 1 dan 2 yang relevan (sisanya terlalu spesifik secara ekonomi) dan audiens yang dituju sedikit lebih nyaman dengan pemikiran teorema-lemma-bukti daripada kebanyakan ilmuwan ^[1] .

Detail

Dalam konteks dinamika adaptif dalam evolusi , saya telah bertemu dua jenis resistensi khusus dari ahli biologi teoretis:

[A] "Mengapa saya harus peduli pada perilaku untuk sewenang-wenang ? Saya sudah tahu bahwa genom memiliki pasangan basa (atau mungkin gen) dan tidak lebih." $n$ $n = 3*10^9$ $n = 2*10^4$

Ini relatif mudah untuk disingkirkan dengan argumen "kita bisa membayangkan menunggu detik, tetapi bukan ". Tapi, argumen yang lebih rumit mungkin mengatakan bahwa "yakin, Anda mengatakan Anda hanya peduli pada spesifik , tetapi teori Anda tidak pernah menggunakan fakta ini, mereka hanya menggunakan itu besar tapi terbatas, dan itu adalah teori Anda yang sedang kami pelajari dengan analisis asimptotik ". $10^9$ $2^{10^9}$ $n$

[B] "Tetapi Anda hanya menunjukkan bahwa ini sulit dengan membangun lansekap spesifik ini dengan gadget ini. Mengapa saya harus peduli dengan ini alih-alih rata-rata?"

Ini adalah kritik yang lebih sulit untuk diatasi, karena banyak alat yang biasa digunakan orang dalam bidang ini berasal dari fisika statistik di mana seringkali aman untuk mengasumsikan distribusi yang seragam (atau sederhana tertentu lainnya). Tetapi biologi adalah "fisika dengan sejarah" dan hampir semuanya tidak setimbang atau 'tipikal', dan pengetahuan empiris tidak cukupuntuk membenarkan asumsi tentang distribusi melalui input. Dengan kata lain, saya ingin argumen yang mirip dengan yang digunakan terhadap analisis kasus rata-rata distribusi seragam dalam rekayasa perangkat lunak: "kami memodelkan algoritme, kami tidak dapat membuat model yang masuk akal tentang bagaimana pengguna akan berinteraksi dengan algoritma atau apa distribusi mereka. input akan menjadi; itu untuk psikolog atau pengguna akhir, bukan kita. " Kecuali dalam kasus ini, sains tidak berada pada posisi di mana setara dengan 'psikolog atau pengguna akhir' ada untuk mengetahui distribusi yang mendasarinya (atau jika itu bahkan bermakna).

Catatan dan pertanyaan terkait

Tautan ini membahas ilmu kognitif, tetapi pola pikirnya serupa dalam biologi. Jika Anda menelusuri Evolution atau Journal of Theoretical Biology , Anda jarang akan melihat teorema-lemma-proof, dan ketika Anda melakukannya biasanya akan hanya perhitungan daripada sesuatu seperti bukti keberadaan atau konstruksi rumit.
Paradigma untuk analisis kompleksitas algoritma
Jenis lain dari analisis waktu berjalan selain kasus terburuk, rata-rata, dll?
Ekologi dan evolusi melalui lensa algoritmik
Mengapa para ekonom harus peduli pada kompleksitas komputasi

cc.complexity-theory reference-request big-picture application-of-theory worst-case Artem Kaznatcheev
sumber

Perilaku terburuk tidak mungkin dibenarkan ... algoritma simpleks memiliki perilaku buruk yang eksponensial, dan satu-satunya orang yang pernah peduli adalah ahli teori. Yang perlu Anda perdebatkan adalah (a) perilaku asimptotik kasus rata-rata adalah penting; (B) perilaku asimptotik kasus rata-rata dan perilaku asimptotik kasus terburuk sering serupa; (c) perilaku asimptotik kasus terburuk sering lebih mudah untuk dihitung daripada perilaku asimptotik kasus rata-rata (terutama karena tidak ada yang tahu apa distribusi probabilitas yang relevan).

Peter Shor

Asimptotik sudah merupakan aspek yang bermasalah. Kita semua tahu cerita tentang algoritma perkalian matriks (batas atas asimptotik tidak ada artinya dalam praktik), dan mungkin juga kisah tentang memilih parameter dalam kriptografi (batas bawah asimptotik tidak berarti dalam praktik; algoritma eksponensial kadang-kadang layak [DES]). Jika analisis Anda memiliki konstanta aktual, maka itu lebih meyakinkan.

Yuval Filmus

Jika Anda berpikir tentang perhitungan sebagai permainan (yaitu perang) antara penyedia input dan algoritme, maka analisis kasus terburuk adalah pendekatan militer standar - Anda ingin tahu seberapa buruknya. Kedua, dan yang lebih penting, analisis kasus terburuk tidak memungkinkan Anda untuk menjadi malas secara intelektual dan menerima solusi yang mungkin baik untuk apa yang Anda yakini sebagai dunia (dan bukan apa sebenarnya dunia itu). Akhirnya, dan mungkin yang paling penting, ini menyediakan cara yang seragam untuk membandingkan algoritma dengan cara yang semoga bermakna. Singkatnya, ini adalah pendekatan terburuk, kecuali yang lainnya.

Sariel Har-Peled

Saya pikir batas bawah terburuk harus dilihat sebagai menempatkan bola kembali di pengadilan mereka. Anda telah menunjukkan bahwa tidak ada algoritma yang dapat menyelesaikan masalah mereka pada semua contoh dalam kerangka waktu yang masuk akal. Mereka mungkin percaya bahwa contoh mereka mudah - tetapi Anda baru saja menunjukkan bahwa jika demikian, itu adalah fakta yang tidak sepele. Oleh karena itu model mereka tidak lengkap kecuali mereka datang dengan penjelasan mengapa demikian.

Aaron Roth

(Ini adalah pendekatan yang tampaknya bekerja ketika berbicara dengan para ahli teori permainan. Itu menimbulkan pertanyaan - jika pasar benar-benar seimbang dengan cepat - properti khusus apa yang dimiliki pasar nyata yang dapat mengatasi kekerasan kasus terburuk? Kemungkinan besar mungkin untuk menentukan yang masuk akal properti seperti itu, dan batas bawah hanya menyarankan bahwa melakukan itu adalah arah penelitian yang penting)

Aaron Roth

Jawaban:

Menurut saya pribadi (dan bias) adalah bahwa analisis kasus terburuk asimptotik adalah batu loncatan historis untuk jenis analisis yang lebih praktis berguna. Karena itu tampaknya sulit untuk dibenarkan kepada praktisi.

Membuktikan batasan untuk kasus terburuk seringkali lebih mudah daripada membuktikan batasan untuk bahkan "bagus" definisi kasus rata-rata. Analisis asimptotik juga seringkali jauh lebih mudah daripada membuktikan batas yang cukup ketat. Analisis asimptotik kasus terburuk adalah tempat yang tepat untuk memulai.

Karya Daniel Spielman dan Shanghua Teng tentang analisis Simplex yang mulus bagi saya merupakan pertanda dari apa yang bisa terjadi ketika kita mulai mendapatkan pemahaman yang lebih baik tentang bentuk masalah: menangani kasus terburuk terlebih dahulu memungkinkan pemahaman yang lebih bernuansa menjadi dikembangkan. Lebih lanjut, seperti yang disarankan Aaron Roth dalam komentar, jika perilaku "biasa" suatu sistem secara signifikan berbeda dari kasus terburuknya, maka sistem tersebut belum sepenuhnya ditentukan dan diperlukan lebih banyak pekerjaan untuk meningkatkan model. Jadi melampaui kasus terburuk umumnya tampak penting sebagai tujuan jangka panjang.

Sejauh analisis asimptotik yang bersangkutan, biasanya berfungsi untuk menjaga bukti panjang dan berantakan dari detail yang mengganggu. Sayangnya ada saat ini tampaknya tidak ada cara untuk menghargai pekerjaan yang membosankan mengisi rincian untuk mendapatkan konstanta yang sebenarnya, sehingga sepertinya jarang dilakukan. (Batas halaman juga berfungsi melawan hal ini.) Analisis yang cermat terhadap detail ikatan asimptotik telah menyebabkan algoritma yang sebenarnya, dengan batasan yang baik pada konstanta, jadi saya pribadi ingin melihat lebih banyak dari jenis pekerjaan ini. Mungkin jika lebih banyak bukti diformalkan menggunakan sistem asisten bukti, maka konstanta dapat diperkirakan dengan upaya tambahan yang lebih sedikit. (Atau batas pada konstanta, sepanjang garis Gower terikat untuk Szemerédi Regularity Lemma, mungkin menjadi lebih rutin.) Ada juga cara untuk membuktikan batas bawah yang bebas dari konstanta, dengan menggunakan model mesin yang lebih eksplisit (seperti automata finite-state deterministik). Namun, batas bawah yang tepat (hampir) persis seperti itu untuk model komputasi yang lebih umum mungkin memerlukan banyak pekerjaan, atau berada di luar jangkauan sama sekali. Hal ini tampaknya telah dikejar pada ~ 1958–1973 selama masa kejayaan teori automata pertama, tetapi sejauh yang saya tahu sejak itu sebagian besar ditinggalkan sendirian.

$O$ $(n^k)$

András Salamon
sumber

Saya tidak berbagi antusiasme Anda untuk membuang asimptotik demi batas yang tepat dengan konstanta yang pasti. Asimptotik mungkin tidak tepat - tetapi bermanfaat tidak tepat. Mereka abstrak atas perbedaan implementasi untuk model mesin yang sama. Misalnya, algoritma pengurutan yang kuadrat pada perangkat keras tahun 1950-an masih akan kuadrat pada perangkat keras saat ini. Selanjutnya, formula asimptotik menyusun dengan baik. Linear dan polinomial ditutup di bawah komposisi, misalnya. (Perhatikan bahwa berdebat untuk batas yang lebih baik pada kasus rata-rata dibandingkan dengan kasus terburuk adalah ortogonal dari berdebat melawan asimptotik.)

brandjon

Secara umum Anda benar, tetapi ada perbedaan besar antara konstanta kecil dan konstanta yang merupakan fungsi non-elementer dari parameter yang relevan.

András Salamon

Saya suka jawaban ini secara keseluruhan, tetapi saya setuju dengan @brandjon bahwa menyembunyikan konstanta sangat penting. Bagi saya, alasan TCS berguna dalam biologi adalah karena ia perlu membuat jauh lebih sedikit asumsi tentang dinamika mikro daripada fisika. Namun, jika Anda tidak membuat asumsi tentang dinamika mikro (yaitu spesifikasi yang tepat dari model komputasi) maka Anda tidak bisa mengeluarkan faktor konstan. Fitur lain yang bermanfaat dari TCS adalah dikotomi kualitatif yang ketat (sesuatu yang lebih mudah dibandingkan dengan pengamatan kualitatif dalam bio), biasanya untuk mendapatkannya Anda juga harus membuang konstanta.

Artem Kaznatcheev

\tilde{O} (n^{\tilde{O} (1 / ϵ)})

$\tilde{O}(n^{\tilde{O}(1/\epsilon)})$

Sebagai catatan, ada beberapa contoh di mana analisis kasus terburuk masuk akal. Misalnya, ketika Anda mengembangkan perpustakaan subrutin untuk keperluan umum dan tidak tahu dalam domain aplikasi apa mereka akan berguna: Anda tidak dapat mengantisipasi semua kasus kapan dan mengapa seseorang ingin menghitung pencocokan bipartit biaya minimum, misalnya. Pengaturan permusuhan, seperti kriptografi, bahkan lebih jelas (namun, dalam crypto Anda benar-benar ingin mengetahui konstanta dalam hal parameter keamanan).

Sasho Nikolov

Batas bawah dan analisis kasus terburuk biasanya tidak berjalan bersama. Anda tidak mengatakan algoritma akan membutuhkan setidaknya waktu eksponensial dalam kasus terburuk, oleh karena itu buruk. Anda mengatakan itu bisa memakan waktu paling linier dalam kasus terburuk, dan karenanya bagus. Yang pertama hanya berguna jika Anda akan menjalankan algoritma Anda pada semua input yang mungkin, dan bukan hanya input rata-rata.

Jika Anda ingin menggunakan batas bawah untuk menunjukkan kejahatan, maka Anda ingin analisis kasus terbaik atau analisis kasus rata-rata. Anda dapat menyederhanakan hal-hal dengan mengandalkan titik @ PeterShor yang terburuk dan rata-rata sering sangat mirip, dan memberikan daftar algoritma algoritma yang benar. (Mis: semua jenis klasik selain quicksort.)

Adapun menunjukkan bahwa asimptotik penting jika dibandingkan dengan input konstan dan faktor konstan, artikel favorit saya tentang topik ini adalah Jon Bentley "Pemrograman mutiara: teknik desain algoritma". Dia menyajikan empat solusi berbeda untuk masalah array sederhana, dan menunjukkan bagaimana pendekatan linear memusnahkan yang kubik. Dia menyebut mejanya "The Tyranny of Asymptotics", setelah istilah yang digunakan oleh fisikawan untuk ketidakterapan persamaan roket. Saya menggunakan contoh ini untuk memotivasi pencarian algoritma yang lebih baik untuk siswa pra-perguruan tinggi.

Akankah ilmuwan non-komputer membaca artikel yang berisi kode, dan tahu untuk melewatkan detail level rendah untuk mendapatkan gambaran besar? Saya tidak tahu Mungkin ada presentasi yang lebih baik di tempat lain. Tapi saya pikir ini adalah sumber yang layak untuk dikutip.

Dan jika mereka berpendapat bahwa mereka tidak peduli dengan n besar yang sewenang-wenang, minta mereka menjalankan Fibonacci rekursif tanpa memo pada 3 * 10 ⁹ pasangan basa, dan katakan itu O (1) karena ukuran urutan DNA ditetapkan. ;)

brandjon
sumber

Saya suka contoh fibonacci :)

Suresh Venkat

Re: paragraf pertama Anda: sebenarnya, itulah yang persis banyak dilakukan oleh teori kompleksitas. Jika masalah adalah EXP-selesai, itu berarti membutuhkan waktu eksponensial pada input kasus terburuk. Ini umumnya dianggap sebagai indikasi kesulitan secara keseluruhan (yang, jujur saja, dalam praktiknya sering tidak seburuk indikator umum). Ini adalah standar de facto, yang disebut "tak terhingga sering" atau io batas bawah; mendapatkan kasus rata-rata atau hampir di mana-mana batas bawah (yaitu, untuk semua input kecuali terbatas) adalah tujuan yang kadang-kadang dikejar, tetapi seringkali jauh dari jangkauan dibandingkan dengan batas bawah.

Joshua Grochow

Izinkan saya menunjukkan bahwa Anda tidak hanya dapat memberikan daftar algoritma cucian dengan analisis kasus terburuk dan rata-rata sama, tetapi Anda juga dapat memberikan banyak contoh di mana mereka sangat berbeda (algoritma simpleks hanya menjadi yang paling terkenal ini). Anda benar-benar perlu berdebat bahwa mereka sama untuk aplikasi khusus Anda; pengujian eksperimental adalah cara yang baik untuk melakukan ini.

Peter Shor

@ JoshuaGrochow Cukup adil. Bagaimana kalau kita merevisi pernyataan sebagai berikut: Batas bawah pada kasus terburuk adalah penting ketika Anda ingin menunjukkan tidak adanya jaminan matematika non-horribleness. ;)

brandjon

-3

banyak yang setuju bahwa ini adalah topik penting untuk disurvei / dibahas tetapi tampaknya belum banyak. beberapa referensi dengan beragam gaya / liputan / audiensi / formalitas tidak persis seperti yang diminta tetapi agak dekat (paling baik dilihat online sejauh ini pada pencarian sedang, berharap untuk mendengar lebih jauh dari yang lebih baik; lebih banyak catatan di bawah):

Kompleksitas algoritma Atkinson (sayangnya hanya satu referensi untuk biologi di koran, tetapi mungkin cukup pada istilah sains / teknik yang lebih umum)

Teori algoritma modern berasal dari akhir 1960-an ketika metode pengukuran waktu eksekusi asimptotik mulai digunakan. Dikatakan bahwa subjek memiliki sayap teknik dan ilmiah. Sayap rekayasa terdiri dari metodologi desain yang dipahami dengan baik sementara sayap ilmiah berkaitan dengan dasar-dasar teoretis. Isu-isu kunci dari kedua sayap disurvei. Akhirnya beberapa pendapat pribadi tentang ke mana subjek akan pergi berikutnya ditawarkan.
Kompleksitas dan Algoritma J. Diaz. 100 slide. luas; seseorang dapat mengutip yang relevan pada khususnya.
Pengantar Analisis Kompleksitas Algoritma Dionisis "dionyziz" Zindros

dengan kata lain apakah ada semacam pengantar / survei / tinjauan umum tentang kompleksitas teori lensa dalam kombinasi dekat / konjungsi / pendamping dengan lensa algoritmik maju dalam sains, seperti "teori kompleksitas untuk ilmuwan, insinyur, dan peneliti" ?

ada referensi yang baik pada "lensa algoritmik" yang telah Anda sebutkan sebelumnya, misalnya Papadimitriou tetapi tampaknya tidak ada referensi yang sangat memuaskan oleh seorang ahli di bidang yang telah ditulis pada "lensa kompleksitas" yang terakhir ... namun (mungkin beberapa "elit " anggota situs ini akan menganggap itu sebagai proyek buku atau kertas mereka berikutnya).

perhatikan juga ada banyak referensi tentang relevansi P vs NP di luar teori kompleksitas & dalam bidang ilmiah lainnya yang dapat digunakan agak untuk tujuan ini. akan menambahkannya di komentar jika ada minat.

ay
sumber

Saya tidak berpikir ini benar-benar menjawab pertanyaan itu.

Huck Bennett

eh huh, apakah Anda melihat salah satu referensi? sebagian jawaban saya adalah bahwa belum (belum) ada jawaban ideal / sempurna: |

vzn

Mereka tampaknya mendefinisikan analisis kasus asimptotik dan terburuk daripada berfokus pada membenarkannya, tetapi mungkin saya melewatkan sesuatu?

Huck Bennett

Sebenarnya, saya pikir para peneliti di luar TCS dapat dengan mudah mengabaikan kasus terburuk sebagai "contoh buatan buatan yang tidak akan pernah terjadi dalam praktik" dan akan (tanpa meyakinkan kuat sebaliknya) jauh lebih tertarik pada kasus rata-rata (walaupun faktanya tidak jelas bahwa kasus rata-rata adalah bahwa jauh lebih dekat dengan contoh dunia nyata).

Joshua Grochow

@vzn: Asimptotik (mis. besar-Oh) dan yang terburuk agak ortogonal. Seseorang dapat melakukan analisis kasus terburuk asimptotik, analisis kasus rata-rata asimptotik, atau bahkan analisis-kasus termudah asimptotik (meskipun saya akui yang terakhir tampaknya agak menyimpang). Sebagai gantinya, orang dapat melakukan analisis kasus terburuk yang tepat , atau analisis kasus rata-rata yang tepat , dan seterusnya, meskipun ini akan jauh lebih bergantung pada model dan kurang kuat. Membenarkan penggunaan asimptotik (dan menyembunyikan hal-hal seperti faktor konstan) sepenuhnya berbeda dari membenarkan kasus terburuk vs rata-rata atau "nyata-" (apa pun yang terakhir mungkin berarti ...).

Joshua Grochow