Bagaimana cara menipu heuristik inspeksi plot?

23

Di sini , Dave Clarke mengusulkan bahwa untuk membandingkan pertumbuhan asimptotik, Anda harus merencanakan fungsinya. Sebagai ilmuwan komputer yang secara teori cenderung, saya menyebut (ed) vodoo ini sebagai plot tidak pernah menjadi bukti. Setelah dipikir-pikir, saya harus setuju bahwa ini adalah pendekatan yang sangat berguna yang bahkan kadang kurang dimanfaatkan; plot adalah cara yang efisien untuk mendapatkan ide pertama, dan terkadang hanya itu yang Anda butuhkan.

Saat mengajar TCS, selalu ada siswa yang bertanya: "Apa yang saya butuhkan bukti formal jika saya bisa melakukan X yang selalu berhasil?" Terserah gurunya untuk menunjukkan dan mengilustrasikan kesalahan tersebut. Ada serangkaian contoh pola yang jelas yang akhirnya gagal di matematika. SE, tetapi itu adalah skenario yang cukup matematis.

Jadi, bagaimana Anda menipu heuristik inspeksi plot? Ada beberapa kasus di mana perbedaan sulit untuk dijelaskan, misalnya

contoh contoh contoh
^{[ sumber ]}

Buat tebakan, lalu periksa sumber untuk fungsi yang sebenarnya. Tapi itu tidak spektakuler seperti yang saya harapkan, khususnya karena hubungan sebenarnya mudah dikenali dari fungsinya sendiri, bahkan untuk pemula.

Apakah ada contoh pertumbuhan asimptotik (relatif) di mana kebenaran tidak jelas dari definisi fungsi dan inspeksi plot untuk yang cukup besar $n$ memberi Anda ide yang sepenuhnya salah? Fungsi matematika dan set data nyata (misalnya runtime dari algoritma tertentu) keduanya diterima; tolong jangan melakukan fungsi yang didefinisikan sedikit demi sedikit.

asymptotics didactics Raphael
sumber

2

Sebenarnya, saya mengusulkannya sebagai tip untuk memahami masalah.

Dave Clarke

@DaveClarke: Saya tahu; Saya menggunakan formulasi awal Anda hanya sebagai pembuka provokatif. Tidak ada pelanggaran yang dimaksudkan.

Raphael

23

$(\log n)^a$ $n^b$ $O(\sqrt{n} \log n)$ $O(n^{0.6})$

merencanakan
^{[ sumber ]}

$[0,1]$ $n^{0.6}$ $n^{0.7}$ $n^{1/2}\log^{3/4}n$ $n^{2/3}$

Peter Shor
sumber

15

Berikut adalah contoh lain (memang agak dibangun), tetapi saya masih menemukan yang luar biasa. Hal ini dimaksudkan untuk menunjukkan bahwa plot bisa sangat menyesatkan untuk menilai pertumbuhan asimptotik.

$f$ $g$

Bisakah Anda menebak fungsi mana yang tumbuh (asimptotik) lebih cepat?

plot f dan g hingga 2000 plot f dan g hingga 10.000 plot f dan g hingga 200.000

$f\sim g$

f (x) = x^{2}

$f(x) = x^2$

g (x) = \iint \sin (\log (x)) + 1 d x d x = x^{2} (1 - \frac{3}{5} \cos (\log (x)) + \frac{1}{5} \sin (\log (x))) .

$g(x) = \iint \sin(\log(x))+1 \;dx\,dx = x^2\Bigl(1 - \tfrac{3}{5} \cos(\log(x)) + \tfrac{1}{5} \sin(\log(x)) \Bigr)\;.$

Jadi pada dasarnya , yaitu sama dengan , tetapi turunan keduanya tidak seragam , tetapi terombang-ambing antara dan dengan periode pertumbuhan eksponensial. Osilasi ini tidak terlihat dalam plot biasa. $g$ $x^2$ $f$ $2$ $0$ $4$

Untuk contoh ini , kita dapat melakukan demos osilasi dengan mempertimbangkan log-log-plot:

log-log-plot dari f dan g hingga 200.000

Tentu saja, ini tidak membantu, secara umum; misalnya, kita mungkin memiliki periode eksponensial ganda ...

Sebastian
sumber

12

Contoh yang bagus adalah algoritma DFA minimal yang sangat ajaib dari Brzozowski. Diberi otomat terbatas , kita dapat menghitung otomat terbatas deterministik minimal darinya: $N = (Q, S \subseteq Q, F \subseteq Q, R \subseteq Q \times \Sigma \times Q)$

M i n i m i z e : N F A \to D F A = D e t e r m i n i z e \circ R e v e r s e \circ D e t e r m i n i z e \circ R e v e r s e

$\mathrm{Minimize} : \mathrm{NFA \to DFA} = \mathrm{Determinize\circ Reverse \circ Determinize \circ Reverse}$

Ini jelas merupakan algoritma waktu eksponensial kasus terburuk, karena dapat mengambil otomat non-deterministik dan memberi Anda yang deterministik (atau lebih jelas lagi, ia menyebut konstruksi himpunan bagian dua kali).

Namun, jika Anda memberikan DFA sebagai algoritme Brzozowski sebagai input, pada banyak jenis input yang sama, ia dapat bersaing dengan dan seringkali mengungguli algoritme minimalisasi DFA khusus (yang biasanya , atau jika Anda hard-core dan mengimplementasikan algoritma Hopcraft). $O(n^2)$ $O(n \log(n))$

Ini menyentuh bagian "plot" dari "heuristik inspeksi plot" --- kita harus memilih titik mana yang akan diambil sampel saat menggambar plot, dan Anda dapat menipu plot naif jika Anda tidak memilih poin dengan hati-hati. Ini juga berlaku untuk contoh lain, seperti Quicksort dan algoritma Simplex, tetapi untuk pedagogi saya lebih suka algoritma ini daripada keduanya.

Perbedaan Quicksort adalah "hanya" kuadrat versus log-linear, yang kurang spektakuler daripada perbedaan polinomial / eksponensial. Algoritma simpleks memang memiliki perbedaan yang sama spektakulernya, tetapi analisisnya jauh lebih rumit daripada algoritma Brzozowski.

(Juga, saya merasa bahwa algoritma minimisasi DFA Brzozowski jauh kurang dikenal daripada yang seharusnya, tetapi tentu saja itu masalah selera.)

Neel Krishnaswami
sumber

Maaf, tapi saya tidak begitu melihat koneksi ke menafsirkan plot fungsi.

Raphael

3

Saya berasumsi Anda akan melakukan sesuatu seperti kinerja plot versus ukuran instance untuk pengambilan sampel instance - dan algoritma Brzozowski akan "terlihat" polinomial kecuali jika Anda memilih instance untuk menjadikannya waktu yang eksponensial.

Neel Krishnaswami

1

Saya melihat. Itu tentu merupakan masalah ketika algoritma pembandingan dan merencanakan runtimes rata-rata, yaitu masalah merencanakan data yang tepat . Ketika saya mengajukan pertanyaan, saya hanya berpikir untuk menafsirkan plot dengan benar , yang merupakan binatang buas lainnya. Bisakah Anda menambahkan perspektif ini ke jawabannya?

Raphael

Anda akan memiliki masalah yang sama untuk semua algoritma yang memiliki perilaku rata-rata dan kasus terburuk yang berbeda; Quicksort dan Simplex muncul di pikiran.

Raphael

8

Teknik matematika dari fitting curve dapat digunakan untuk memberikan jumlah jawaban yang tidak terbatas untuk pertanyaan Anda. Diberikan kurva dan rentang, orang dapat dengan mudah menemukan polinomial yang sesuai dengan kurva dengan tingkat akurasi apa pun. Contoh dari wikipedia ini menunjukkan bagaimana gelombang dosa dapat cukup akurat dipasangkan dengan polinomial orde keempat (kurva biru).

masukkan deskripsi gambar di sini

Saya dapat menggunakan polinomial orde tinggi, dan mengelabui heuristik inspeksi plot bahkan lebih baik daripada grafik ini.

Dave Clarke
sumber

2

Itu benar. Ini juga memiliki rasa buatan. Tentu saya bisa menghasilkan contoh tandingan untuk siswa dengan cara ini tetapi saya tidak melihat semakin skeptis diyakinkan olehnya. Adakah kejadian "alami" dari fenomena ini (yaitu fungsi polinom tingkat tinggi yang dapat disalahartikan sebagai fungsi lain) di mana salah tafsir "fatal"?

Raphael

Saya tahu itu bukan jawaban yang Anda cari.

Dave Clarke

Bagaimana cara menipu heuristik inspeksi plot?

Jawaban: