Approssimando la complessità di Kolmogorov

Question

ho studiato qualcosa sulla Kolmogorov Complessità , leggere alcuni articoli e libri da Vitanyi e Li e ha usato il concetto di normalizzato Compression Distanza per verificare la stilometry di autori (identificare come ogni autore scrive alcuni documenti di testo e di gruppo per la loro somiglianza).

In questo caso, compressori dati sono stati usati per approssimare la complessità Kolmogorov, poiché il compressore di dati potrebbe essere utilizzato come una Macchina di Turing.

Oltre compressione dei dati e linguaggi di programmazione (in cui si può scrivere un qualche tipo di compressore), che altro potrebbe essere utilizzato per approssimare la complessità di Kolmogorov? Ci sono altri approcci che potrebbero essere utilizzati?

Answer 1

Credo che una possibile risposta alla tua domanda è questa: Prendete un numeri pseudo generatore $ G $. Cercate di scegliere un generatore che ha alcuni potenti attacchi contro di essa: un di numeri casuali attacco generatore $ G $ è (per i nostri scopi), un algoritmo $ a che, $ quando somministrato una stringa imput $ s $, determina un seme $ a (s) $, in modo tale che $ G (a ( s)) = s $. Poi approssimare il KC di $ s $:

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

Dove $ | G | $ è la lunghezza del programma che calcola $ G (s) $ (spesso molto breve, come per i generatori lineari).

Si noti che, in pratica, di numeri casuali attacchi generatore sono non come descritti: possono sicuro o produrre risultati incompleti. In tal caso, si può adattare l'algoritmo in modo che restituisca $ | s | $ quando il risultato dell'attacco è insoddisfacente. La stessa osservazione vale per algoritmi di compressione.

L'avvertimento di questo approccio rispetto agli algoritmi di compressione è che gli algoritmi di compressione sono in generale molto più adatto al calcolo KC quanto sono ideate per lavorare su qualsiasi stringa, mentre un attacco può funzionare solo se $ s $ sembra essere a immagine di $ G $ ( molto improbabile ).

Answer 2

Ogni distribuzione di probabilità. Se si dispone di una distribuzione di probabilità calcolabile che dà il vostro probabilità di dati $ p (x) $, poi con la disuguaglianza di Kraft, c'è un compressore computabile che comprime in $ - \ log p (x) $ bit (fino rotonda Se non si desidera bit frazionari). Questo significa praticamente qualsiasi macchina generativa algoritmo di apprendimento possono essere utilizzati.

Questo è il motivo per cui complessità di Kolmogorov è così interessante, non perché è l'algoritmo di compressione finale (che si preoccupa per la compressione in ogni caso), ma perché è l'ultima di apprendimento algoritmo. La compressione e l'apprendimento sono fondamentalmente la stessa cosa: trovare i modelli dei dati. Il quadro statistico costruito su questa idea si chiama minima Descrizione Lunghezza, ed è stato direttamente ispirato da Kolmogorov complessità.

questa domanda sopra al StackExchange cstheory.

Answer 3

grammatica codifica è una versione meno frequente di un compressione algoritmo e può essere preso come una 'stima approssimativa' della complessità di Kolmogorov. grammatica codifica non è come comunemente usato come un algoritmo di compressione come altri più comuni approcci forse soprattutto perché doesnt migliorare tanto su di compressione da esempio Lempel-Ziv sulla base di-corpus di testo, ma può fare bene su altri tipi di dati. l'idea è quella di "comprimere" una stringa utilizzando regole grammaticali. una derivazione grammaticale può tradursi in un DAG (vs un albero meno complessa) per cui v'è sostanziale complessità rappresentativo possibile.

Un'altra opzione è quella di trovare più piccolo / minimal che rappresenta una stringa, ma questo è noto per avere molto elevata complessità di calcolo e potrebbe avere successo solo su piccole stringhe.

in genere il più vicino qualsiasi ravvicinamento tratta di calcolare $ K (x) $ , il più intrattabile che è.

in senso informale, generalmente qualsiasi "approssimazione" di $ K (x) $ deve essere anche un "algoritmo di compressione".

ci sono anche altri metodi algoritmo di compressione oltre Lempel-Ziv "Run Length Encoding" tipo avvicina, per esempio algebra vettoriale e la SVD può essere usato come un algoritmo di compressione. anche Fourier trasforma vengono spesso utilizzati per comprimere immagini esempio in JPG standard.