<antirez>

antirez 7137 days ago. 16080 views.
Entropia 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.
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 Originally published on oldblog.antirez.com on 3 May 2007.

13 comments from the original post

Emanuele 4 May 2007
Devo dire che come Prima visita a questo blog, questo post mi ha piacevolmente impressionato, complimenti per la chiarezza !
antirez 4 May 2007
@Emanuele: Grazie Emanuele.
Massimo Moruzzi 4 May 2007
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?
antirez 4 May 2007
@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).
antirez 4 May 2007
@riffraff: grazie, aggiunto un link all'articolo.
Domenico 4 May 2007
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
antirez 4 May 2007
@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.
Domenico 4 May 2007
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!
antirez 5 May 2007
@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.
Massimiliano Monittola 21 Apr 2009
bravissimo. mi e' piaciuto moltissimo, in contenuto e chiarezza.
grazie.
Massimiliano
Samuele 15 Jun 2009
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
Navigatore Anonimo 26 Mar 2010
blog comments powered by Disqus
: