Entropia dell'informazione
Thursday, 03 May 07
In questi giorni ho passato una buona parte del mio tempo studiando algoritmi di compressione, e ho immancabilmente incontrato il concetto di entropia dell'informazione. E' una vecchia conoscenza, anche in crittografia e' estremamente ricorrente, ma nella prospettiva della compressione delle informazioni ho l'impressione che il concetto assuma delle sfumature ancora piu' interessanti, e ho collegato tre idee semplici ma importanti che vorrei condividere con voi.
Facciamo un gioco
Cos'e' l'entropia dell'informazione? Non voglio parlare di matematica, ma trovare un modo qualitativo di esprimere il concetto in modo che sia comprensibile in maniera tangibile, reale.
Immaginate di avere una informazione, composta da diversi caratteri. Potrebbe essere un testo, o una sequenza completamente casuale, qualunque cosa. Ammettiamo che l'alfabeto possibile includa tutte le lettere dell'alfabeto piu' lo spazio (27 simboli in tutto).
Vi comunicano questa informazione lettera dopo lettara. A, D, N, ... Dopo ogni lettera che sentite, il vostro compito e' quello di cercare di prevedere con la maggior precisione possibile la prossima lettera.
Tanto maggiore sara' la vostra capacita' di prevedere le lettere successive, tanto minore sara' l'entropia dell'informazione che vi stanno comunicando.
Vi comunicano questa informazione lettera dopo lettara. A, D, N, ... Dopo ogni lettera che sentite, il vostro compito e' quello di cercare di prevedere con la maggior precisione possibile la prossima lettera.
Tanto maggiore sara' la vostra capacita' di prevedere le lettere successive, tanto minore sara' l'entropia dell'informazione che vi stanno comunicando.
Per essere piu' pratici, ammettiamo che l'esperimento sia condotto con l'informazione costituita dal seguente testo: "AAABBBAAABBBAAABBBAAABBB". Dopo alcune lettere e' banale prevedere con maggiore probabilita' di 1/27 (ammettendo di usare un alfateto di 27 simboli) cosa viene dopo. Persino dopo aver visto solo "AA" molti si butterebbero sull'idea che la terza sara' nuovamente una "A" no? Questa informazione ha evidentemente una entropia molto bassa.
Se invece la stringa fosse stata "YBOLMAGBNMAQLQYVTKZTQPTIBYXCLI" la nostra capacita' di previsione sarebbe stata ben piu' bassa. Con una stringa molto lunga (alias asintoticamente), e se la distribuzione dei caratteri nella stringa fosse stata completamente casuale, la nostra capacita' di prevedere in maniera corretta il prossimo carattere sarebbe stata in media di 1/27.
Compressione
Una strategia che un computer potrebbe seguire cercando di giocare al gioco appena visto e' quella di costruire una tabella con delle sotto stringhe ricorrenti all'interno della porzione di informazione che gli e' gia' stata comunicata. Anche se inizialmente non conoscesse l'italiano dopo qualche migliaio di caratteri se incontrasse la successione "ROSS" potrebbe stimare come probabile che la prossima lettera sia una "O", perche' ha gia' incontrato la parola ROSSO alcune volte.Bene, pensate alla seguente idea: man mano che il computer riceve le lettere compila una tabella con tutte le sotto stringhe che incontra: Ad ogni stringa assegna anche un valore numerico. Se quando trova una stringa gia' nel dinzionario la sostituisce con il numero ad essa assegnato di fatto sta comprimendo! Questa idea e' la base degli algoritmi LZW, LZ77, ed altre varianti di questi.
Chiaramente se l'entropia dell'informazione e' bassa, come nel caso di AAABBBAAABBB ... il trucco funzionera' molto bene, ad esempio se la tabella fosse costituita da simboli composti da 3 lettere la stringa potrebbe essere compressa in AAABBB01 in cui il numero 0 significa sostituisci col primo gruppo di tre lettere incontrato e cosi' per il secondo numero.
Provando a comprimere con questo sistema la seconda stringa, "YBOLMAGBNMAQLQYVTKZTQPTIBYXCLI", non otterremo gli stessi risultati perche' l'entropia dell'informazione e' piu' alta.
Ora dovrebbe essere chiaro cos'e' l'entropia della informazione, e come e' intimamente connessa all'idea di compressione delle informazioni. Cio' che non e' chiaro e' rispetto a quale modello e' possibile misurare l'entropia. Ad esempio un italiano riuscira' a prevedere che dopo le lettere CIA viene probabilmente una O, mentre un cinese che non parla la nostra lingua potrebbe essere meno bravo. Ma qual'e' l'entropia dell'informazione "CIAO" realmente?
PI greco
Le cifre di PI, 3.14...., hanno una distribuzione piu' o meno casuale. Non c'e' alcun pattern evidente. Cercare di comprimere PI tramite un dizionario di simboli non funzionera', alla fine ogni simbolo deve essere rappresentato come numero, e ogni numero deve essere rappresentato con un certo numero di bit. Maggiore e' la dimensione della nostra tabella di simboli maggiore e' il numero di bit che ci serve per rappresentare ogni indice della tabella: insomma il concetto e' che se scrivete PI in un file come un lungo numero binario e tentate di comprimere tale file, il file risultante sara' piu' grande di quello originale.Questo significa che l'entropia di PI e' alta? Potremmo essere tentati di pensare cosi'.
Poi pero' fate una riflessione: milioni di cifre di PI possono essere generate tramite un piccolo programma per computer, e tale computer dentro la sua memoria non contiene alcuna parte di PI. Non possiamo dunque pensare che il programma stesso che genera PI sia una forma per scrivere il numero in maniera compressa?
Si... e il programma per scomprimerlo e' il compilatore e/o il runtime che permettono di eseguire tale programma. E a pensarci bene... giocando al "gioco dell'entropia" con le cifre di PI, sarebbe stato semplice dopo aver visto la prima parte, anche per un extraterrestre che conoscesse la geometria, indovinare tutte le cifre successive.
Il punto e' che l'entropia si misura sempre rispetto ad un modello. Ma un modello interessante per misurarla e' quello di pensare che una informazione ha entropia alta se non e' possibile scrivere un programma piu' breve della informazione stessa che genera per output tale informazione, o per meglio dire maggiore e' la differenza tra la lunghezza in bit dell'informazione e quella del programma, minore e' l'entropia dell'informazione, assumendo che il programma giri in un ambiente minimo che dia appena tutto quello che serve semanticamente ad una macchina di Turing.
Il nostro viaggio termina qui, ma se leggendo questo articolo pensate che questa branca della scienza sia interessante ringraziate Claude Shannon leggendo la sua pagina su wikipedia :)
Per approfondire
Primo teorema di Shannon
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Comments
1
04 May 07, 03:29:02
Devo dire che come Prima visita a questo blog, questo post mi ha piacevolmente impressionato, complimenti per la chiarezza !
04 May 07, 06:10:48
quindi l'entropia delle cifre del pi greco è bassa perchè è generabile da una semplice divisione fra la circonferenza di un cerchio e il suo diametro?
04 May 07, 06:17:31
@Massimo Moruzzi: per meglio dire l'entropia del PI e' bassa rispetto ad un determinato modello perche' l'informazione che costituisce tutte le sue cifre e' esprimibile attraverso un rapporto matematico, o in maniera simile attraverso un algoritmo, esprimibile utilizzando una quantita' di informazione molto piu' piccola rispetto alle cifre di PI (che sono infinite).
04 May 07, 07:11:25
siccome inspiegabilmente non è linkata dalla pagina su shannon, penso sia utile anche il link al primo teorema di shannon, che contiene anche una definizione di entropia:
http://it.wikipedia.org/wiki/Primo_teorema_di_Shan...
:)
http://it.wikipedia.org/wiki/Primo_teorema_di_Shan...
:)
04 May 07, 16:25:58
Come al solito la tua capacità espressiva è invidiabile, tuttavia permettimi un po' di pignoleria:
[quote]
Se invece la stringa fosse stata "YBOLMAGBNMAQLQYVTKZTQPTIBYXCLI" la nostra capacita' di previsione sarebbe stata ben piu' bassa [...]sarebbe stata in media di 1/27[/quote]
1/27 è comunque il caso peggiore, la media potrebbe essere migliore.
[quote]milioni di cifre di PI possono essere generate tramite un piccolo programma per computer[/quote]
Non credo possa esistere un programma che sappia generare PI. Posto X (numero finito) il diametro, la circonferenza sarebbe uguale a X moltiplicato un numero con infinite cifre quindi anch'esso un numero con cifre infinite. Se ne conclude che l'entropia di PI è elevata.
Naturalmente noi potremmo avere una soglia di precisione limitata (100 cifre decimali) in questo caso allora sarebbe possibile scrivere un algoritmo che ritorni questo valore, anche se dubito possa essere inferiore a 102 cifre (3,100cifre).
Ciao
[quote]
Se invece la stringa fosse stata "YBOLMAGBNMAQLQYVTKZTQPTIBYXCLI" la nostra capacita' di previsione sarebbe stata ben piu' bassa [...]sarebbe stata in media di 1/27[/quote]
1/27 è comunque il caso peggiore, la media potrebbe essere migliore.
[quote]milioni di cifre di PI possono essere generate tramite un piccolo programma per computer[/quote]
Non credo possa esistere un programma che sappia generare PI. Posto X (numero finito) il diametro, la circonferenza sarebbe uguale a X moltiplicato un numero con infinite cifre quindi anch'esso un numero con cifre infinite. Se ne conclude che l'entropia di PI è elevata.
Naturalmente noi potremmo avere una soglia di precisione limitata (100 cifre decimali) in questo caso allora sarebbe possibile scrivere un algoritmo che ritorni questo valore, anche se dubito possa essere inferiore a 102 cifre (3,100cifre).
Ciao
04 May 07, 17:42:04
@Domenico: Grazie per i complimenti, per il resto:
Se hai 27 simboli, e tenti di indovinare, ne becchi 1/27 NEL CASO MEDIO :) non in quello peggiore.
Per quanto riguarda PI, ci sono sul web diversi siti con programmi che generano 200 MILIONI di cifre di PI :)
Non solo, molti algoritmi hanno come input il numero di cifre che vuoi generare, dunque anche PI come numero composto da numero infinito di cifre ha una entropia bassa. Anche se un PC ci stara' tanto ad andare oltre alcuni milioni di cifre il punto e' che quell'algoritmo contiene tutto il necessario per generare teoricamente tutte le cifre che vuoi.
Ciao e grazie del commento.
Se hai 27 simboli, e tenti di indovinare, ne becchi 1/27 NEL CASO MEDIO :) non in quello peggiore.
Per quanto riguarda PI, ci sono sul web diversi siti con programmi che generano 200 MILIONI di cifre di PI :)
Non solo, molti algoritmi hanno come input il numero di cifre che vuoi generare, dunque anche PI come numero composto da numero infinito di cifre ha una entropia bassa. Anche se un PC ci stara' tanto ad andare oltre alcuni milioni di cifre il punto e' che quell'algoritmo contiene tutto il necessario per generare teoricamente tutte le cifre che vuoi.
Ciao e grazie del commento.
04 May 07, 19:09:34
Sul PI, scusami, avevo interpretato capacità come probabilità, che effettivamente non può essere peggiore di 1 su 27 con 27 simboli, cioè tiri sempre ad indovinare.
Per l'algoritmo, effettivamente al link:
http://it.wikipedia.org/wiki/Calcolo_di_pi_greco (e link collegati)
Ne vengono illustrati alcuni che non si basano sulla frazione circonferenza/raggio che avevo subito ipotizzato, rimane forse aperta la problema dell'esattezza dovuta all'arrotondamento, ma non ho approfondito... devo dire però che sono molto complessi.
Ciao e grazie per i costanti stimoli!
Per l'algoritmo, effettivamente al link:
http://it.wikipedia.org/wiki/Calcolo_di_pi_greco (e link collegati)
Ne vengono illustrati alcuni che non si basano sulla frazione circonferenza/raggio che avevo subito ipotizzato, rimane forse aperta la problema dell'esattezza dovuta all'arrotondamento, ma non ho approfondito... devo dire però che sono molto complessi.
Ciao e grazie per i costanti stimoli!
04 May 07, 20:22:45
@Domenico: forse abbiamo usato una terminlogia diversa su questa cosa del calcolo delle probabilita':
Quando dico nel caso medio, non dico ad entropia media.
Se la sequenza da indovinare e' totalmente casuale, dunque altissima entropia dell'informazione che non puo' essere affatto compressa, la probabilita' di indovinare il prossimo simbolo e' nel caso medio 1/27.
Forse l'incomprensione e' nata dal fatto che nell'articolo non ho scritto che "YBOLMAGBNMAQLQYVTKZTQPTIBYXCLI" e' davvero una stinga presa da /dev/urandom di Linux! Dunque se fosse piu' lunga asintoticamente si puo' indovinare ogni carattere con probabilita' 1/27.
E' esattamente come il problema del lancio di una moneta. I simboli sono due, nel caso medio si potra' indovinare il 50% delle uscite.
Grazie a te, a presto.
Quando dico nel caso medio, non dico ad entropia media.
Se la sequenza da indovinare e' totalmente casuale, dunque altissima entropia dell'informazione che non puo' essere affatto compressa, la probabilita' di indovinare il prossimo simbolo e' nel caso medio 1/27.
Forse l'incomprensione e' nata dal fatto che nell'articolo non ho scritto che "YBOLMAGBNMAQLQYVTKZTQPTIBYXCLI" e' davvero una stinga presa da /dev/urandom di Linux! Dunque se fosse piu' lunga asintoticamente si puo' indovinare ogni carattere con probabilita' 1/27.
E' esattamente come il problema del lancio di una moneta. I simboli sono due, nel caso medio si potra' indovinare il 50% delle uscite.
Grazie a te, a presto.
21 Apr 09, 03:24:28
bravissimo. mi e' piaciuto moltissimo, in contenuto e chiarezza.
grazie.
Massimiliano
grazie.
Massimiliano
15 Jun 09, 08:03:54
Ho fatto ricerche su ricerche per approfondire il concetto di entropia e di informazione. Questo è risultato uno dei siti migliori. Se posso invece dare un consiglio personale, potresti chiarire il concetto preciso di entropia, che da quello che ho capito da altri siti, è la lunghezza media di bit con il quale noi potremo rappresentare i nostri caratteri :D
26 Mar 10, 09:04:30