Perbedaan antara “informasi” dan “informasi yang berguna” dalam teori informasi algoritmik

Menurut Wikipedia :

Informal, dari sudut pandang teori informasi algoritma, isi informasi dari string setara dengan panjang mungkin representasi mandiri terpendek dari string.

Apa analog definisi ketat informal "informasi yang berguna"? Mengapa "informasi yang berguna" tidak diambil sebagai konsep yang lebih alami atau yang lebih mendasar; naif tampaknya murni string acak keharusan menurut definisi mengandung informasi nol, jadi saya mencoba untuk mendapatkan kepala saya sekitar fakta bahwa itu dianggap memiliki informasi maksimal oleh definisi standar.

Konsep sentral di sini adalah kompleksitas Kolmogorov , dan lebih khusus kompresibilitas . Untuk mendapatkan perasaan kompresibilitas yang intuitif, pertimbangkan dua string dan B ∈ B ∗ , di mana B = { 0 , 1 } . Membiarkan$A \in \mathbb{B}^*$$B \in \mathbb{B}^*$$\mathbb{B} = \{ 0,1 \}$

1010 1010 1010 , dan$A = 1010$ $1010$ $1010$ $1010$

0110 0111 1001 .$B = 1011$ $0110$ $0111$ $1001$

Perhatikan bahwa . Bagaimana kita dapat mengukur berapa banyak informasi yang dimiliki A atau B ? Jika kita berpikir tentang teori informasi klasik, secara umum, mentransmisikan string dengan panjang n membutuhkan n bit rata-rata. Namun kita tidak bisa mengatakan berapa banyak bit kita perlu mengirimkan tertentu string dengan panjang n .$|A| = |B| = 16$$A$$B$$n$$n$$n$

Mengapa konten informasi dari string acak tidak nol?

Pada melihat lebih dekat, kita dapat melihat bahwa sebenarnya . Namun, jauh lebih sulit untuk mengatakan jika B memiliki setiap pola yang jelas dalam struktur, setidaknya itu tampaknya dan terasa lebih acak dari A . Karena kita dapat menemukan pola dalam A , kita dapat dengan mudah kompres A dan mewakilinya dengan kurang dari 16 bit. Demikian juga, karena tidak mudah untuk mendeteksi pola dalam B , kita tidak bisa kompres sebagai banyak. Oleh karena itu kita dapat mengatakan bahwa B memiliki informasi lebih dari A . Selain itu, string acak dengan panjang $A = 10^8$$B$$A$$A$$A$$16$$B$$B$$A$$n$memiliki informasi maksimal karena tidak ada cara kita dapat memampatkannya, dan karenanya mewakili dengan kurang dari bit.$n$

Lalu apa informasi yang berguna?

Untuk informasi yang berguna , ya, ada definisi menggunakan Turing mesin . Informasi yang berguna dalam x ∈ B ∗ adalah$T$$x \in \mathbb{B}^*$

$$\min_T \space \{\space l(T) + C(x|T) : T \in \{ T_0, T_1, ... \} \},$$

di mana menunjukkan panjang dari encoding membatasi diri untuk Turing mesin T . Notasi biasanya sehingga C ( x ) menunjukkan kompleksitas Kolmogorov dari x dan C ( x | y ) kompleksitas Kolmogorov bersyarat x diberikan y .$l(T)$$T$$C(x)$$x$$C(x|y)$$x$$y$

Berikut mewujudkan jumlah informasi yang berguna yang terkandung dalam x . Apa yang kita bisa meminta adalah yang seperti T untuk memilih di antara mereka yang memenuhi persyaratan. Masalahnya adalah untuk memisahkan program terpendek x * menjadi bagian-bagian x * = p q st p merupakan yang tepat T . Ini sebenarnya adalah gagasan yang menelurkan panjang deskripsi minimum (MDL) .$T$$x$$T$$x^*$$x^* = pq$$p$$T$

Bisa jadi karena "berguna" sulit untuk menentukan. Katakanlah kita memiliki yang sangat terstruktur, kaya informasi pesan yang dapat dikompresi paling dengan faktor α ke pesan y . Secara intuitif, x dan y mengandung jumlah yang sama dari informasi yang berguna; memang, mereka mengandung jumlah informasi yang sama sesuai dengan definisi biasa. Sekarang bayangkan sebuah awalan z dari x dari panjang yang sama dengan y ; itu harus berisi informasi tidak lebih berguna daripada x , maka, tidak lebih dari y . Namun, y lebih "acak" dari z , karena $x$$\alpha$$y$$x$$y$$z$$x$$y$$x$$y$$y$$z$$z$dapat dikompresi dan tidak bisa. Jadi jika kita mencoba untuk menghubungkan informasi "berguna" dengan kompresibilitas, kita bisa lari ke paradoks berikut: awalan dari pesan bisa memiliki informasi yang lebih tinggi "berguna" dari seluruh pesan, tampaknya kontradiksi.$y$

Dari sudut pandang kurang formal pandang, saya pikir mungkin membantu jika Anda melepaskan diri dari kata "acak," karena Anda benar bahwa satu set bit benar-benar acak tidak menyimpan informasi dalam arti praktis. (Jika saya mengenkripsi satu set nama dan mengirimkan nilai-nilai terenkripsi untuk Anda, mereka mungkin memiliki kompleksitas Kolmogorov sangat tinggi tetapi tidak akan membantu Anda mengetahui nama-nama).

Tapi berpikir tentang hal dengan cara ini. Jika Anda melihat situs web dalam bahasa asing (katakanlah bahasa Swedia, anggap Anda tidak berbicara) itu akan terlihat kurang lebih acak. Akan ada beberapa untuk kata-kata, tapi tidak banyak. Namun, jika Anda melihat halaman web dengan teks yang terlihat seperti ini: 123456123456123456123456 ... dan seterusnya, Anda akan dapat memahaminya lebih cepat. Jika Anda tidak berbicara bahasa Swedia, Anda mungkin bisa mendapatkan lebih banyak darinya, bahkan jika halaman web Swedia mengatakan setara dengan "enam angka pertama yang diulang secara berurutan". Situs berisi informasi yang sama, tapi satu terlihat acak untuk Anda. Dan untuk jumlah ruang, yang Anda pahami jauh lebih efisien daripada halaman web Swedia, meskipun menyimpan informasi yang sama. Anda mungkin tidak menemukan informasi ini "berguna" karena'

Gagasan "informasi" dimaksudkan untuk menjadi universal, jadi apa yang tampak seperti acak - bit untuk Anda dapat menyimpan banyak informasi kepada orang lain - dan karena itu tidak berguna. Ukuran informasi dimaksudkan untuk menjadi properti intrinsik dari string, dan tidak dapat bergantung pada apa yang dilakukan dan tidak masuk akal bagi Anda, dan apa yang dapat dan tidak dapat menafsirkan.

Lain (yang lebih teknis) saat itu bantuan Mei adalah bahwa aku menjadi sedikit jujur di sini. Seperti yang Juho tunjukkan, informasinya adalahdidefinisikan relatif terhadap siapa yang menafsirkannya. Anda mungkin menemukan halaman web Swedia benar-benar berguna sebagai kendaraan untuk informasi, tetapi seseorang yang berbicara Swedia mungkin merasa memiliki banyak informasi. Definisi tersebut mencerminkan hal ini. Namun, dari matematika kita bisa belajar bahwa perbedaan antara terpendek (paling informatif untuk ruang) halaman web untuk berkomunikasi situs ini untuk Anda dan halaman web terpendek yang dapat berkomunikasi kepada seseorang yang berbicara Swedia dapat berbeda hanya oleh konstan aditif. Mengapa? Karena bagi Anda, sebagai pembicara non-Swedia, jalan terpendek untuk menyimpan halaman yang Anda dapat memahami adalah "enam bilangan bulat pertama diulang secara berurutan." Ini mungkin sedikit lebih lama dari Swedia.

$$(\mbox{Most efficient representation of information in English}) \leq (\mbox{Most efficient representation in Swedish}) + (\mbox{Length of Swedish-English dictionary})$$ . Ini semakin sedikit off-topik dari pertanyaan asli Anda, tapi titik aku berusaha untuk membuat adalah bahwa tidak peduli terlalu banyak yang membaca informasi. Halaman web Swedia acak-cari tidak "berguna" bagi Anda, tapi itu "berguna" kepada orang lain, dan Anda hanya jumlah konstan informasi dari mampu memanfaatkan sendiri.