Mendekati kompleksitas Kolmogorov

Saya telah mempelajari sesuatu tentang Kompleksitas Kolmogorov , membaca beberapa artikel dan buku dari Vitanyi dan Li dan menggunakan konsep Normalized Compression Distance untuk memverifikasi stilometri penulis (mengidentifikasi bagaimana setiap penulis menulis beberapa teks dan dokumen kelompok berdasarkan kesamaan mereka).

Dalam hal itu, kompresor data digunakan untuk memperkirakan kompleksitas Kolmogorov, karena kompresor data dapat digunakan sebagai Mesin Turing.

Selain kompresi data dan bahasa pemrograman (di mana Anda akan menulis semacam kompresor), apa lagi yang bisa digunakan untuk memperkirakan kompleksitas Kolmogorov? Apakah ada pendekatan lain yang bisa digunakan?

Saya kira salah satu jawaban yang mungkin untuk pertanyaan Anda adalah ini: Ambil jumlah pseudorandom generator yang . Cobalah untuk memilih generator yang memiliki beberapa kuat serangan terhadap itu: a nomor acak serangan Generator untuk adalah (untuk tujuan kita), sebuah algoritma yang bila diberi imput tali , menentukan benih , sehingga . Kemudian perkiraan KC dari :G A s A ( s ) G ( A ( s ) ) = s $G$$G$$A$$s$ $A(s)$$G(A(s))=s$$s$

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Di manaadalah panjang dari program yang menghitung (seringkali cukup pendek, seperti untuk generator linier).G ( s $|G|$$G(s)$

Perhatikan bahwa dalam praktiknya, serangan generator angka acak tidak seperti yang dijelaskan: mereka mungkin gagal atau menghasilkan hasil yang tidak lengkap. Dalam hal ini, Anda dapat mengadaptasi algoritme sehingga mengembalikanketika hasil serangan tidak memuaskan. Komentar yang sama berlaku untuk algoritma kompresi.$|s|$

The peringatan untuk pendekatan ini sebagai lawan algoritma kompresi adalah bahwa algoritma kompresi pada umumnya jauh lebih cocok untuk komputasi KC karena mereka disesuaikan dengan bekerja pada setiap tali, sedangkan serangan dapat bekerja hanya jika kebetulan di citra ( sangat tidak mungkin ).$s$$G$

Distribusi probabilitas apa pun. Jika Anda memiliki distribusi probabilitas yang dapat dihitung yang memberikan probabilitas data Anda , maka dengan ketidaksetaraan Kraft, ada kompresor yang dapat mengompresnya dalam bit (bulat jika Anda keberatan dengan bit fraksional). Ini berarti hampir semua algoritma pembelajaran mesin generatif dapat digunakan.- log p ( x $p(x)$$-\log p(x)$

Inilah sebabnya mengapa kompleksitas Kolmogorov sangat menarik, bukan karena itu adalah algoritma kompresi ultimat (yang peduli tentang kompresi), tetapi karena itu adalah algoritme pembelajaran utama . Kompresi dan pembelajaran pada dasarnya adalah hal yang sama: menemukan pola dalam data Anda. Kerangka kerja statistik yang dibangun berdasarkan ide ini disebut Panjang Deskripsi Minimum, dan secara langsung terinspirasi oleh kompleksitas Kolmogorov.

Lihat juga pertanyaan ini di StstExchange cstheory.

grammar coding adalah versi yang lebih jarang digunakan dari algoritma kompresi dan dapat dianggap sebagai perkiraan "kasar" dari kompleksitas Kolmogorov. grammar coding tidak biasa digunakan sebagai algoritma kompresi seperti pendekatan yang lebih umum lainnya mungkin terutama karena itu tidak meningkatkan banyak pada kompresi dari misalnya Lempel-Ziv pada berbasis teks-corpus, tetapi dapat dilakukan dengan baik pada jenis data lainnya. idenya adalah untuk "memampatkan" string menggunakan aturan tata bahasa. derivasi tata bahasa dapat menghasilkan DAG (vs pohon yang kurang kompleks) sehingga ada kompleksitas representasional substansial mungkin.

Pilihan lain adalah menemukan rangkaian terkecil / minimal yang mewakili string, tetapi ini dikenal memiliki kompleksitas komputasi yang sangat tinggi dan hanya dapat berhasil pada string kecil.

$K(x)$

$K(x)$

ada juga metode algoritma kompresi lain selain pendekatan tipe Lempel-Ziv "run length encoding", misalnya aljabar vektor dan SVD dapat digunakan sebagai algoritma kompresi. juga transformasi Fourier sering digunakan untuk mengompres gambar misalnya dalam standar JPG.