Formula di entropia di Shannon. Aiuta la mia confusione

Question

la mia comprensione della formula entropica è che viene utilizzato per calcolare il numero minimo di bit richiesti per rappresentare alcuni dati. Di solito è formulato diversamente quando definito, ma la comprensione precedente è ciò su cui ho fatto affidamento fino ad ora.

Ecco il mio problema. Supponiamo che io abbia una sequenza di 100 '1' seguita da 100 '0' = 200 bit. L'alfabeto è {0,1}, la base dell'entropia è 2. Probabilità del simbolo "0". è 0,5 e "1"; è 0,5. Quindi l'entropia è 1 o 1 bit per rappresentare 1 bit.

Tuttavia, è possibile codificarlo per una lunghezza pari a qualcosa come 100/1/100/0 dove è il numero di bit da emettere seguito dal bit. Sembra che io abbia una rappresentazione più piccola dei dati. Soprattutto se aumenti il ??numero da 100 a un numero molto più grande.

Sto usando: http://en.wikipedia.org/wiki/Information_entropy come riferimento al momento. Dove ho sbagliato? È la probabilità assegnata ai simboli? Non penso sia sbagliato. O ho sbagliato la connessione tra compressione ed entropia? Nient'altro?

Grazie.

Modifica

Seguendo alcune delle risposte il mio seguito è: applicheresti la formula entropica a una particolare istanza di un messaggio per cercare di scoprirne il contenuto informativo? Sarebbe valido prendere il messaggio "aaab" e dire che l'entropia è ~ 0.811. Se sì, qual è l'entropia di 1 ... 10 .... 0 dove 1 e 0 vengono ripetuti n volte usando la formula di entropia. La risposta è 1?

Sì, ho capito che stai creando una variabile casuale dei simboli di input e indovinando la funzione di massa di probabilità in base al tuo messaggio. Quello che sto cercando di confermare è che la formula dell'entropia non tiene conto della posizione dei simboli nel messaggio.

Answer 1

  

O ho sbagliato la connessione tra compressione ed entropia?

Sei abbastanza vicino, ma quest'ultima domanda è dove si trovava l'errore. Se riesci a comprimere qualcosa in una forma più piccola della sua rappresentazione originale, significa che la rappresentazione originale aveva almeno una ridondanza. Ogni bit nel messaggio in realtà non stava trasmettendo 1 bit di informazioni.

Poiché i dati ridondanti non contribuiscono al contenuto informativo di un messaggio, non aumentano anche la sua entropia. Immagina, ad esempio, un "generatore di bit casuale" che restituisce solo il valore "0". Questo non trasmette alcuna informazione! (In realtà, trasmette una indefinita quantità di informazioni, poiché qualsiasi messaggio binario costituito da un solo tipo di simbolo richiede una divisione per zero nella formula entropica.

Al contrario, se avessi simulato un gran numero di lanci di monete casuali, sarebbe molto difficile ridurre di molto le dimensioni di questo messaggio. Ogni bit contribuirebbe quasi a 1 bit di entropia.

Quando comprimi i dati, estrai quella ridondanza. In cambio, si paga un prezzo entropico una tantum dovendo escogitare uno schema che sappia comprimere e decomprimere questi dati; che di per sé richiede alcune informazioni.

  

Tuttavia, è possibile codificarlo per una lunghezza pari a qualcosa come 100/1/100/0 dove è il numero di bit da emettere seguito dal bit. Sembra che io abbia una rappresentazione più piccola dei dati. Soprattutto se aumenti il ??numero da 100 a un numero molto più grande.

Per riassumere, il fatto che tu possa escogitare uno schema per rendere la codifica dei dati più piccola dei dati originali ti dice qualcosa di importante. Vale a dire, dice che i tuoi dati originali contenevano pochissime informazioni .

---

Ulteriori letture

Per un trattamento più approfondito di questo, incluso esattamente come calcoleresti l'entropia per qualsiasi sequenza arbitraria di cifre con alcuni esempi, dai un'occhiata a questo breve white paper .

Answer 2

Dai un'occhiata a Complessità di Kolmogorov

  

Il numero minimo di bit in cui è possibile comprimere una stringa senza perdere informazioni. Questo è definito rispetto a uno schema di decompressione fisso, ma universale, dato da una macchina di Turing universale.

E nel tuo caso particolare, non limitarti all'alfabeto {0,1}. Per il tuo esempio usa {0 ... 0, 1 ... 1} (centinaia di 0 e centinaia di 1)

Answer 3

La tua codifica funziona in questo esempio, ma è possibile concepire un caso altrettanto valido: 010101010101 ... che sarebbe codificato come 1/0/1/1 / ...

L'entropia si misura attraverso tutti i possibili messaggi che possono essere costruiti nell'alfabeto dato e non solo esempi patologici!

Answer 4

John Feminella ha capito bene, ma penso che ci sia altro da dire.

L'entropia di Shannon si basa sulla probabilità e la probabilità è sempre negli occhi di chi guarda.

Hai detto che 1 e 0 erano ugualmente probabili (0,5). In tal caso, la stringa di 100 1 seguita da 100 0 ha una probabilità di 0,5 ^ 200, di cui -log (base 2) è 200 bit, come previsto. Tuttavia, l'entropia di quella stringa (in termini di Shannon) è il suo contenuto di informazioni moltiplicato per la sua probabilità, o 200 * 0,5 ^ 200, ancora un numero molto piccolo.

Questo è importante perché se si esegue la codifica di lunghezza di esecuzione per comprimere la stringa, nel caso di questa stringa otterrà una lunghezza ridotta, ma una media su tutte le 2 ^ 200 stringhe, non funzionerà bene. Con un po 'di fortuna, raggiungerà una media di circa 200, ma non di meno.

D'altra parte, se guardi la tua stringa originale e dici che è così sorprendente che chiunque lo abbia generato probabilmente ne genererà di più simili, allora stai davvero dicendo che la sua probabilità è maggiore di 0,5 ^ 200, quindi sei fare ipotesi diverse sulla struttura di probabilità originale del generatore della stringa, ovvero che ha un'entropia inferiore a 200 bit.

Personalmente, trovo questo argomento davvero interessante, specialmente quando si guardano le informazioni di Kolmogorov (Algorithmic). In tal caso, si definisce il contenuto informativo di una stringa come la lunghezza del programma più piccolo che potrebbe generarlo. Questo porta a tutti i tipi di approfondimenti sull'ingegneria del software e sulla progettazione del linguaggio.

Spero che sia d'aiuto, e grazie per la tua domanda.