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 :)