Hubungan antara kompleksitas komputasi dan informasi

11

Saya bekerja di laboratorium ilmu saraf komputasi yang menghitung informasi timbal balik antara pasangan atau kelompok neuron. Baru-baru ini, bosnya menggeser fokusnya untuk mengukur "kompleksitas dinamika saraf". Dalam mengejar garis penelitian itu, beberapa orang dalam kelompok saya tampaknya menyamakan "kompleks" dengan "memiliki entropi tinggi".

Adakah yang bisa membimbing saya tentang hubungan antara kompleksitas komputasi (dalam pengertian CS) dan entropi dalam pengertian teori informasi?

Untuk menjelaskan sedikit lebih jauh, langkah-langkah seperti kompleksitas Lempel-Ziv, bagi saya, tampaknya bukan ukuran kompleksitas yang valid karena mereka mengonfigurasi informatif (kepada pengguna) dengan membawa banyak bit. Langkah-langkah lain, seperti [Causal State Splitting Reconstruction][1]jauh lebih sedikit diketahui tetapi memiliki sifat menarik bahwa proses acak tidak memiliki kompleksitas, karena nol keadaan tersembunyi diperlukan untuk mewakili proses acak stasioner.

cc.complexity-theory it.information-theory mac389
sumber
1
Bisakah Anda jelaskan apa arti "kompleks" di bidang Anda? Apakah ini berarti, neuron-neuron itu menembak secara bermakna atau lebih banyak dari mereka yang berpartisipasi?
vs
@vs: Ada banyak definisi yang bersaing untuk "complex". Ada yang mengatakan proses yang paling kompleks adalah dengan entropi tertinggi. Namun, itu akan menyiratkan bahwa proses acak itu rumit, yang tampaknya tidak realistis secara biologis. Meski begitu, "menembak secara bermakna" lebih dekat daripada "lebih banyak ... berpartisipasi" meskipun kemungkinan "lebih banyak berpartisipasi secara bermakna" bahkan lebih dekat.
mac389
1
Kami memahami kompleks menyiratkan entropi yang lebih besar dari bidang kami. Saya menanyakan pertanyaan itu untuk memahami apa arti bidang Anda dengan kompleks. Jadi "" lebih banyak berpartisipasi secara bermakna "lebih dekat. Oke. Ini adalah dugaan saya. Bagi saya" lebih banyak berpartisipasi secara bermakna "menyiratkan neuron berkomunikasi" secara cerdas "atau" lebih suka menanggapi rangsangan "untuk" hasil yang diinginkan ". Komunikasi yang bermakna ini biasanya dikaitkan dengan entropi atau informasi yang lebih tinggi dalam teori informasi
vs
@vs: Ada pertanyaan tentang bagaimana dua mengukur entropi ketika skema pengkodean tidak diketahui dan kemungkinan beralih, seperti yang tampaknya terjadi di otak. Orang-orang mengatakan menggunakan informasi timbal balik antara satu neuron dan stimulus untuk menghitung seberapa selektif neuron itu untuk stimulus itu. Masalahnya menjadi lebih kacau ketika mempertimbangkan kasus yang lebih realistis dari banyak neuron.
mac389
1
@ mac389 kita dapat berarti sejumlah hal sebagai kompleksitas suatu objek. beberapa contoh adalah: Kompleksitas Kolmogorov (yang Anda dapatkan jawabannya) dan berbagai pengertian kompleksitas Kolmogorov yang terikat waktu; ketika Anda memiliki kumpulan objek dengan ukuran yang berbeda-beda, kami melihat berapa banyak waktu / ruang (sebagai fungsi dari ukuran objek) yang dibutuhkan suatu algoritma untuk mengenali bahwa suatu objek milik kelas. Anda memiliki masalah pemodelan yang cukup non-sepele di sini saya pikir.
Sasho Nikolov

Jawaban:

9

Ada cukup koneksi antara teori informasi dan kompleksitas komputasi untuk mendapatkan program pascasarjana, misalnya yang ini: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Sasho Nikolov
sumber
Terima kasih, bersama dengan diskusi dengan orang-orang yang lebih berpengetahuan, inilah yang sebenarnya saya cari.
mac389
7

Banyak orang telah menyebutkan kompleksitas Kolmogorov atau varian terbatas sumber dayanya, tapi saya pikir sesuatu yang lebih dekat dengan apa yang Anda cari adalah gagasan kedalaman (logis) . Ada beberapa varian pada kedalaman, tetapi mereka semua mencoba untuk mendapatkan sesuatu seperti apa yang Anda bicarakan. Secara khusus, baik string murni acak maupun string sangat berulang / sangat dalam.

Satu gagasan tentang kedalaman adalah secara intuitif: sebuah string sangat dalam jika memiliki deskripsi singkat, tetapi satu-satunya cara untuk merekonstruksi string dari deskripsi singkat itu membutuhkan waktu yang sangat lama. Ini adalah gagasan tentang kedalaman dan beberapa lainnya diperkenalkan dan dikembangkan dalam [1]. Referensi standar lainnya adalah [2]. Saya akan melihat itu, kemudian melakukan pencarian referensi ke depan.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Kedalaman komputasi: konsep dan aplikasi . Teoritis Comp. Sci. 354 (3): 391--404. Juga tersedia secara bebas dari halaman web penulis .

[2] CH Bennett. Kedalaman logis dan kompleksitas fisik. Dalam R. Herken (Ed.), Mesin Universal Turing: A Half-Century Survey, Oxford University Press, Oxford (1988), 227–257.

Joshua Grochow
sumber
Terima kasih banyak atas jawaban ini. Kedalaman logis tampaknya sangat dekat dengan apa yang saya maksud dengan kompleksitas.
mac389
3

Hal pertama yang muncul di benak Anda sebagai sesuatu yang mungkin menarik adalah kompleksitas Kolmogorov; Saya tentu menemukan itu menarik, dan karena Anda tidak menyebutkannya, saya pikir itu mungkin layak disebut.

Karena itu, pendekatan yang lebih umum untuk menjawab pertanyaan ini mungkin didasarkan pada teori bahasa dan automata. Automata hingga deterministik adalah prosesor string O (n). Yaitu, diberi string dengan panjang n, mereka memproses string dengan tepat n langkah (banyak dari ini tergantung pada bagaimana Anda mendefinisikan automata terbatas deterministik; namun, DFA tentu tidak memerlukan langkah-langkah lebih lanjut). Automata terbatas Nondeterministc mengenali bahasa yang sama (set string) seperti DFA, dan dapat ditransformasikan ke DFA, tetapi untuk mensimulasikan NFA pada mesin deterministik berurutan, Anda biasanya harus menjelajahi "ruang pencarian" seperti pohon yang dapat meningkatkan kompleksitas secara dramatis. Bahasa reguler tidak terlalu "kompleks" dalam arti komputasi,

Anda juga dapat melihat tingkat lain dari hierarki bahasa Chomsky - bebas konteks deterministik, bebas konteks (termasuk bahasa bebas konteks nondeterministik, yang tidak dapat dikenali oleh deterministic pushdown automata), bahasa yang peka konteks, rekursif, dan rekursif bahasa yang dapat dihitung, dan bahasa yang tidak dapat ditentukan.

Automata yang berbeda berbeda terutama dalam penyimpanan eksternal mereka; yaitu, penyimpanan eksternal apa yang diperlukan agar automata memproses bahasa dengan jenis tertentu dengan benar. Automata terbatas tidak memiliki penyimpanan eksternal; PDA memiliki tumpukan, dan mesin Turing memiliki kaset. Dengan demikian Anda dapat menafsirkan kompleksitas masalah pemrograman tertentu (yang terkait dengan bahasa) yang terkait dengan jumlah atau jenis penyimpanan yang diperlukan untuk mengenalinya. Jika Anda tidak memerlukan atau jumlah penyimpanan tetap, terbatas untuk mengenali semua string dalam bahasa, itu adalah bahasa biasa. Jika yang Anda butuhkan adalah tumpukan, Anda memiliki bahasa bebas konteks. Dll

Secara umum, saya tidak akan terkejut jika bahasa yang lebih tinggi dalam hierarki Chomsky (karenanya dengan kompleksitas yang lebih tinggi) juga cenderung memiliki entropi yang lebih tinggi dalam pengertian informasi-teoretis. Yang sedang berkata, Anda mungkin bisa menemukan banyak contoh berlawanan dengan ide ini, dan saya tidak tahu apakah ada manfaatnya sama sekali.

Juga, ini mungkin lebih baik ditanyakan di "teoretis cs" (cstheory) StackExchange.

Patrick87
sumber
Saya telah memigrasikannya dan terima kasih atas saran Anda.
mac389
1

Kompleksitas komputasi membahas sumber daya yang diperlukan: Mengingat jenis masalah tertentu, dengan ukuran tertentu, sumber daya apa yang diperlukan (biasanya waktu, ruang, atau keduanya; dan jenis perangkat komputasi tertentu) untuk menyelesaikannya. Masalah kemudian dikelompokkan bersama dalam "kelas" kompleksitas.

Beberapa di antaranya agak umum dan abstrak: Apakah masalahnya dapat dipecahkan, bahkan secara prinsip? Apakah itu memerlukan mesin jenis ini, atau itu? Pengantar ide-ide ini masih merupakan topik ilmu komputer tingkat pascasarjana, dan materi pengantar biasanya membuat referensi ke hierarki Chomsky, yang dengan rapi (dan indah!) Memetakan bersama beberapa jenis mesin abstrak, dan beberapa jenis abstrak, spesifikasi bahasa matematika.

Beberapa di antaranya, pada tingkat yang lebih rendah, lebih praktis dalam penggunaan sehari-hari: Apakah skala masalah ini sebagai kuadrat dari ukuran masalah, atau kubus, atau beberapa fungsi lainnya? Menariknya, saya tahu bahwa argumen untuk entropi masalah yang diberikan telah berguna dalam menentukan beberapa batas bawah untuk beberapa masalah komputasi. Salah satu yang menonjol dalam pikiran saya (meskipun saya mungkin tidak bisa mengulanginya tanpa memeriksa buku teks) adalah argumen berbasis entropi untuk jumlah perbandingan minimum yang diperlukan selama pengurutan. Koneksi ke entropi adalah melalui teori informasi.

Jadi ada beberapa manfaat untuk ide itu, saya pikir.

Novak
sumber