Differenza tra “informazione” e “informazioni utili” in teoria dell'informazione algoritmica

Question

Wikipedia :

Informalmente, dal punto di vista della teoria dell'informazione algoritmica, il contenuto informativo di una stringa è equivalente alla lunghezza del minimo rappresentazione indipendente possibile di tale stringa.

Qual è la analogo informale rigorosa definizione di "informazioni utili"? Perché è "informazioni utili" non presa come il concetto più naturale o più fondamentale; ingenuamente sembra una stringa must puramente casuali, per definizione, contengono informazioni pari a zero, quindi sto cercando di ottenere la mia testa intorno al fatto che si ritiene di avere informazioni massimo dalla definizione standard.

Answer 1

Il concetto centrale qui è Kolmogorov complessità , e più specificamente comprimibilità . Per ottenere una sensazione intuitiva di compressione, di prendere in considerazione due stringhe $ A \ in \ mathbb {N} ^ * $ e $ B \ in \ mathbb {B} ^ * $, dove $ \ mathbb {B} = \ {0,1 \} $. Lasciate

$ a = $ 1.010 $ 1.010 $ $ 1.010 $ $ 1.010 $, e

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

Si noti che $ | A | = | B | = 16 $. Come potremmo quantificare la quantità di informazioni $ A $ o $ B $ ha? Se pensiamo teoria dell'informazione classica, in generale, la trasmissione di una stringa di lunghezza $ n $ prende $ n $ bit in media. Tuttavia, non si può dire quanti bit abbiamo bisogno di trasmettere un specifica stringa di lunghezza $ n $.

Perché il contenuto informativo di una stringa casuale da zero?

Su uno sguardo più attento, possiamo vedere che in realtà $ A = 10 ^ 8 $. Tuttavia, è molto più difficile da dire se $ B $ ha eventuali modelli evidenti nella sua struttura, almeno sembra e si sente più casuale di $ A $. Perché possiamo trovare un modello in $ A $, possiamo facilmente comprimere $ A $ e rappresentarlo con meno di $ 16 $ bit. Allo stesso modo, dal momento che non è facile da individuare eventuali modelli in $ B $, non possiamo comprimere tanto. Quindi possiamo dire che $ B $ ha più informazioni di $ A $. Inoltre, una stringa casuale di lunghezza $ n $ ha informazioni massima poiché non c'è modo possiamo comprimere, e quindi rappresentare con meno di $ n $ bit.

Che cos'è informazioni utili, allora?

Per informazioni utili , sì, c'è una definizione utilizzando una macchina di Turing $ T $. Le informazioni utili per $ x \ in \ mathbb {B} ^ * $ è

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

dove $ l (T) $ indica la lunghezza di un autolimitante codificante per una macchina di Turing $ T $. La notazione è di solito tale che $ C (x) $ indica la complessità di Kolmogorov di $ x $ e $ C. (X | y) $ il condizionale Kolmogorov complessità di $ x $ dato y $ $

Qui $ T $ incarna la quantità di informazioni utili contenute in $ x $. Che cosa potremmo chiedere è quale ad esempio $ T $ per selezionare tra quelli che soddisfano il requisito. Il problema è quello di separare un programma più breve $ x ^ * $ in parti $ x ^ * = pq $ S.T. $ P $ rappresenta un adeguato $ T $. Questo è in realtà l'idea che ha generato minima lunghezza di descrizione (MDL) .

Answer 2

Potrebbe essere perché "utile" è difficile da definire. Supponiamo di avere un altamente strutturato, ricco di informazioni messaggio di $ x $ che può essere compresso al massimo di un fattore di $ \ alpha $ al messaggio $ y $. Intuitivamente, $ x $ e $ y $ contengono la stessa quantità di informazioni utili; infatti, essi contengono la stessa quantità di informazioni secondo la definizione usuale. Ora immaginate un prefisso $ Z $ di $ x $ della stessa lunghezza da $ y $; essa deve contenere informazioni più utili di $ x $, quindi, non più di $ y $. Tuttavia, $ y $ è più "casuale" di $ z $, poiché $ z $ può essere compresso e $ y $ non può. Quindi, se cerchiamo di associare le informazioni "utili" con comprimibilità, potremmo correre nel seguente paradosso:. Un prefisso di un messaggio potrebbe avere maggiore informazioni "utili" che l'intero messaggio, apparentemente una contraddizione

Answer 3

Da un punto di vista meno formale, penso che può aiutare se ti distacchi dalla parola "random", come siete sulla strada giusta che un insieme di bit veramente casuali non memorizzare tutte le informazioni in senso pratico. (Se io cifrare un insieme di nomi e inviare i valori crittografati a te, che possono avere molto elevata complessità di Kolmogorov, ma non sta andando per aiutarvi a capire i nomi).

Ma pensa in questo modo. Se si vede un sito web in lingua straniera (ad esempio svedese, a patto che non si parla di esso) è andare a guardare più o meno casuale. Ci sarà qualche ordine alle parole, ma non molto. Tuttavia, se si guarda a una pagina web con il testo che assomiglia a questo: 123456123456123456123456 ... e così via, sarete in grado di capire più rapidamente. Se non parlate svedese probabilmente sarete in grado di ottenere molto di più fuori di esso, anche se la pagina web svedese ha detto l'equivalente di "primi sei numeri ripetuti in sequenza". I siti web contengono le stesse informazioni, ma si guarda casuale voi. E per la quantità di spazio, quello che si capisce è il modo meno efficiente rispetto alla pagina web svedese, anche se esso memorizza le stesse informazioni. L'utente non può trovare queste informazioni "utili" perché è in svedese, ma le informazioni sono ancora lì.

Il concetto di "informazione" è destinata ad essere universale, così quello che sembra casuale - e quindi inutile - bit a si può memorizzare una grande quantità di informazioni a qualcun altro. La misura di informazioni è destinato ad essere una proprietà intrinseca della stringa, e non può dipendere da ciò che fa e non ha senso per te, e cosa si può e non si può interpretare.

Un altro punto (più tecnico) che l'aiuto maggio è che io sia un po 'in malafede qui. Come Juho sottolinea, informazioni è definita rispetto a chi sta interpretarlo. Si possono trovare la pagina web svedese completamente inutile come veicolo di informazioni, ma qualcuno che parla svedese potrebbe scoprire di avere una grande quantità di informazioni. La definizione non riflettono questo. Tuttavia, dalla matematica possiamo imparare che la differenza tra il più breve (più informativo per lo spazio) pagina web per comunicare questo sito web per voi e la pagina web più breve in grado di comunicare a qualcuno che parla svedese possono differire solo da una costante additiva. Perché? Perché per voi, come un altoparlante non-svedese, la via più breve per memorizzare la pagina che si può capire è "i primi sei numeri interi ripetuti in sequenza." Questo può essere un po 'più lungo del svedese. (Orso con me qui e supponiamo che svedese è super breve ed efficiente, mentre l'inglese è molto lunga e dispendiosa).

Ma anche se tu fossi in grado di parlare svedese, devi solo essere in grado di tagliare una costante additiva dalla lunghezza! Perché? Perché si può sempre andare a comprare un dizionario svedese-inglese. Poi i super-corti pagine web svedesi avrebbe senso per voi. Certo, hanno senso solo quando si ha la dizionario, ma il dizionario ha una lunghezza costante. Così $$ (\ mbox {rappresentazione più efficace delle informazioni in inglese}) \ leq (\ mbox {rappresentazione più efficace in Svedese}) + (\ mbox {Lunghezza del dizionario Svedese-Inglese}) $$. Questo sta diventando un off-topic po 'dalla tua domanda iniziale, ma il punto che sto cercando di fare è che non importa troppo chi sta leggendo le informazioni. La pagina web svedese casuale guardando non era "utile" a voi, ma è "utile" a qualcun altro, e tu sei solo una quantità costante di informazioni a partire da essere in grado di fare uso di voi stessi.