Utente:Salparadiso/sandbox/Teoria dell'informazione

La teoria dell'informazione è una disciplina della matematica applicata che ha come scopo la quantificazione della quantità di dati (ossia di informazione), con lo scopo di essere di in grado di salvarli o di trasmetterli su un canale in modo affidabile. La grandezza che misura la quantità di dati prende il nome di entropia ed è solitamente espressa come numero di bit necessari per immagazzinare o trasmettere l'informazione. Ad esempio, se un alfabeto ha un'entropia pari a 4 bit, allora, preso un numero sufficiente di parole costruite con tale alfabeto, in media sono necessari 4 bit per rappresentare ogni lettera L'applicazione dei concetti fondamentali della teoria dell'informazione includono la compressione senza perdite dei file (es. zip), la codifica con perdita (es. mp3) e le modulazioni digitali utilizzate nelle trasmissioni ethernet. La teoria dell'informazione si pone a metà strada tra la matematica, la statistica, la fisica, le telecomunicazioni e lìinformatica. Il suo impatto è stato fondamentale nelle missioni spaziali, nell'invenzione del CD, dei telefonini, di Internet, nello studio della linguistica ed in numerosissimi altri campi.

Panoramica

I concetti principali alla base della teoria dell'informazione possono essere colti facendo riferimento ad un semplice esempio: il linguaggio umano. In genere in un linguaggio, le parole più usate sono più corte di quelle meno usate. Ad esempio "ciao" è più breve di "sostanzioso"; inoltre, anche se a volte non si riescono a cogliere tutte la parole di un discorso, il senso rimane chiaro. Lo scopo della teoria dell'informazione è proprio quello di fornire metodi per comprimere al massimo l'informazione prodotta da una sorgente eliminando tutta la ridondanza (si parla di codifica di sorgente), prima di aggiungere un certo livello di ridondanza in modo mirato, allo scopo di rendere la comunicazione (o l'archiviazione) più protetta dal rumore (si parla in questo caso di codifica di canale). Lo studio di questa teoria, i cui principi sono già presenti nelle forme di comunicazione umane, ha consentito a partire dagli anni '40 uno sviluppo incredibile della trasmissione.e dell'archiviazione dell'informazione.

In generale si considera come nascita della teoria dell'informazione, la pubblicazione del lavoro "A Mathematical Theory of Communication" (Una teoria matematica della comunicazione) da parte di Claude Shannon; i risultati fondamentali presenti nello scritto sono due: l'enunciazione del Primo teorema di Shannon (o Teorema della codifica di sorgente) che stabilisce che, in media, il numero di bit necessari a rappresentare il risultato di un evento stocastico è pari alla sua entropia, fornendo così un limite superiore alla possibilità di comprimere dati; il secondo risultato, noto come Secondo Teorema di Shannon o Teorema della codifica di canale, stabilisce invece che il massimo tasso di informazione trasferibile in modo affidabile su un canale affetto da rumore sta sotto una certa soglia che prende il nome di capacità di canale. La capacità può essere avvicinata a piacere, utilizzando sistemi di codifica e decodifica opportuni.

La teoria dell'informazione è strettamente legata ad una serie di discipline pure ed applicate che sono state studiate ed ingegnerizzate negli ultimi sessant'anni. sistemi adattivi, intelligenza artificiale, sistemi complessi, cibernetica, informatica, apprendimento automatico e molti altri. La teoria dell'informazione è quindi un'ampia ed approfondita teoria matematica, con applicazioni ugualmente ampie e profonde, il cui ambito principale rimane però la teoria della codifica.

La teoria della codifica riguarda lo studio di metodi pratici, chiamati codici, per aumentare l'efficienza di una trasmissione e ridurre la probabilità di errore, il più possibile, nei limiti stabiliti e dimostrati da Shannon per un dato canale; Questi codici possono essere divisi in tecniche di compressione dei dati (codifica di sorgente) e correzione degli errori (codifica di canale). Nel secondo caso, sono stati necessari molti anni, prima che fosse possibile ottenere risultati vicini ai limiti forniti da Shannon. Una terza classe di codici sono gli algoritmi di crittografia. Concetti e metodi della teoria dell'informazione sono infatti utilizzati ampiamente in crittografia e crittoanalisi.

La teoria dell'informazione è oggi usata anche nella teoria del gioco e nello studio dei mercati azionari, oltreche nella composizione musicale.

Ambientazione Storica

L'evento decisivo che determinò la nascita della teoria dell'informazione e la portò immediatamente all'attenzione mondiale, fu la pubblicazione dell'articolo "A Mathematical Theory of Communication" da parte di Claude Shannon sul Bell System Technical Journal nel Luglio e nell'Ottobre del 1948.

Prima di questo articolo, sempre nei Bell Labs, erano state sviluppati pochi concetti teorici sull'informazione ed era sempre stata assunta implicitamente l'ipotesi di trattare eventi equiprobabili. L'articolo del 1924 di Harry Nyquist, Certain Factors Affecting Telegraph Speed (Alcuni Fattorie che Influenzano la Velocità del Telegrafo), contiene alcune sezioni teoriche in cui si quantificano l'"intelligenza" e la "velocità" a cui si può trasmettere su un sistema di comunicazione, dando la relazione $W=K\log m$, dove W è la velocità della trasmissione di intelligenza, m è il numero di differenti livelli di tensione su cui si può scegliere ad ogni passo e K è una costante. L'articolo del 1928, ad opera di Ralph Hartley, Transmission of Information (Trasmissione dell'Informazione), usa la parola informazione per indicare una quantità misurabile, che riflette la capacità del ricevitore di distinguere una sequenza di simboli da un'altra; l'informazione nel testo viene definita come $H=\log S^{n}=n\log S$, dove S è il numero di simboli possibili, n il numero di simboli trasmessi. La naturale unità di misura dell'informazione era quindi la cifra decimale, rinominata più tardi hartley in suo onore. Alan Touring nel 1940 usò un'idea simile in una parte dell'analisi statistica sulla decifrazione dei codici crittografici Enigma) usati dai tedechi nella Seconda Guerra Mondiale.

Gran parte della matematica che sta dietro alla teoria dell'informazione nel caso di eventi a diversa probabilità fu sviluppata nel campo della termodinamica da Ludwig Boltzmann e Willard Gibbs. I legami tra l'entropia definita in teoria dell'informazione e quella definita in termodinamica, comresi gli importanti contributi di Rolf Landauer degli anni '60 sono esplorati nell'opera Entropy in thermodynamics and information theory.

Nel rivoluzionario articolo di Shannon, questi per la prima volta introdusse i modelli quantitativi e qualitativi della comunicazione, pensata come un processo statistico, alla base della teoria dell'informazione. L'articolo si apre con l'affermazione che

"Il problema findamentale della comunicazione è quello di riprodurre in un certo punto, o esattamente o approssimetivamente, un messaggio selezionato in un altro punto."

Con esso nacquero le idee di

• entropia e ridondanza di una sorgente e la sua importanza mediante il teorema della codifica di sorgente;
• l'informazione mutua e la capacità di un canale rumoroso, compreso la promessa di una comunicazione senza perdite, mediante il teorema della codifica di canale;
• il risultato pratico del teorema di Shannon-Hartley per la capacità di un canale gaussiano;
• il bit, ossia un nuovo modo di intendere l'unità fondamentale dell'informazione

Quantità della teoria dell'informazione

la teoria dell'informazione è basata sulla teoria della probabilità e sulla statistica. Le principali quantità dell'informazione sono l'entropia, ossia l'informazione contenuta in una variabile aleatoria, e l'informazione mutua, ossia la quantità di informazione in comune tra due variabili aleatorie. La prima quanto sia possibile comprimere un messaggio, mentre la seconda è utile per trovare il tasso di comunicazione possibile su un canale.

La scelta della base logaritmica usata nelle formule che seguono determina l'unità di misura usata per l'entropia. L'unità di misura più comune è senza dubbio il bit, che si usa nel caso in cui si scelga di utilizzare logaritmi in base 2. Altre unità di misura includono il nat, nel caso si usi il logaritmo naturale e l'hartley, che si basa sul logaritmo in base 10.

Nel seguito, un'espressione nella forma $p\log p\,$ è considerata per convenzione pari a 0 quando è nulla p. Questo è giustificabile con il fatto che $\lim _{p\rightarrow 0+}p\log p=0$ per qualunque base logaritmica.

Entropia

Entropia di una variabile di Bernoulli

in funzione della probabilità di successo, spesso indicata come entropia binaria, $H_{\mbox{b}}(p)$. L'entropia è massima e vale 1 bit, quando la probabilità di successo è 0.5, come nel caso del lancio di una moneta.]]

L' entropia, $H$, di una variabile aleatoria discreta $X$, è la misura della quantità di incertezza associata al valore di $X$.

Supponiamo di trasmettere 1000 bit (0 e 1). Se questi bit sono noti prima della trasmissione (ossia assumono un certo valore con probabilità 1), la logica impone che non sia stata trasmessa informazione. Al contrario, se ogni bit è indipendente dagli altri e ha uguale probabilità di valere 0 o 1, sono stati inviati (nel senso della teoria dell'informazione) 1000 bit. Tra questi due estremi, la quantità di informazione può essere quantificata come segue. Se $\mathbb {X} \,$ è l'insieme di tutti i valori $x$ che la variabile $X$ può assumere e $p(x)=Pr(X=x)$ è la brobabilità che $X$ valga $x$, allora $X$ ha

$H(X)=\mathbb {E} _{X}[I(x)]=-\sum _{x\in \mathbb {X} }p(x)\log p(x)$

bit di entropia (Qui,$I(x)$ è l'autoinformazione, ossia il contributo di entropia legato ad ogni singolo messaggio). Una importante proprietà dell'entropia è che è massima quando tutti i messaggi nello spazio dei possibili messaggi sono equiprobabili, ossia maggiormente impredicibili. In questo caso $H(X)=\log |\mathbb {X} |.$

Il caso speciale di una variabile casuale con due possibili uscite è l' entropia binaria:

$H_{\mbox{b}}(p)=-p\log p-(1-p)\log(1-p).\,$

Entropia congiunta

L'entropia congiunta di due variabili aleatorie discrete $X$ ed $Y$ è semplicemente l'entropia della coppia : $(X,Y)$. Questo implica che, se $X$ e $Y$ sono indipendenti ,allora la loro entropia congiunta è la somma delle loro entropie individuali.

Per esempio, se $(X,Y)$ rappresenta la posizione di un pezzo di scacchi ($X$ la riga ed $Y$ la colonna), allora l'entropia congiunta della riga e della colonna su cui è posto il pezzo sarà l'entropia della posizione del pezzo.

$H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)\,$

Nonostante la notazione simile, l'entropia congiunta non deve essere confusa con l' entropia incrociata.

Entropia condizionale

L' entropia condizionale di una variabile aleatoria $X$ , data la variabile aleatoria $Y$ è

$H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=\sum _{x,y}p(x,y)\log {\frac {p(y)}{p(x,y)}}.$

The conditional entropy of $X$ given random variable $Y$ (also called the equivocation of $X$ about $Y$) is the average conditional entropy over $Y$:

Una proprietà fondamentale dell'entropia condizionata è che:

$H(X|Y)=H(X,Y)-H(Y).\,$

Informazione mutua

L' Informazione mutua misura la quantità di informazione su una variabile aleatoria che può essere ricavata osservandone un'altra. In un sistema di comunicazione è importante che sia massimizzata la quantità di informazione condivisa dai segnali inviati e ricevuti. L'informazione mutua di $X$, relativamente a $Y$ è:

$I(X;Y)=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}$

Un'importante proprietà dell'informazione mutua è che

$I(X;Y)=H(X)-H(X|Y).\,$

Ossia, conoscendo Y, possiamo risparmiare in media $I(X;Y)$ bit nella codificsa di X, rispetto al caso in cui Y è ingota.

L'informazione mutua è simmetrica;

$I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y).\,$

L'informazione mutua può essere espressa come media della divergenza di Kullback–Leibler della probabilità a posteriori di X, dato il valore di Y, rispetto alla [[probabilità a priori di X:

$I(X;Y)=\mathbb {E} _{p(y)}[D_{\mathrm {KL} }(p(X|Y=y)\|p(X))].$

In altre parole, essa misura quanto, in media, al probabilità della distribuzione X cambia se conosciamo il valore di Y. Questo è spesso calcolato come divergenza dal prodotto delle sitribuzioni marginali rispetto alla vera distribuzione congiunta:

$I(X;Y)=D_{\mathrm {KL} }(p(X,Y)\|p(X)p(Y)).$

L'informazione mutua può essere considerata una statistica per stabilire l'indipendenza tra una coppia di variabili ed ha una distribuzione asintotica ben specificata.

Divergenza di Kullback–Leibler

La Divergenza di Kullback–Leibler (o entropia relativa) è un modo per confrontare due distribuzioni: una "vera" distribuzione di probabilità p(X) ed una distribuzione arbitraria q(X). Se comprimiamo dei dati in un qualche modo, per cui q(x) è la distribuzione seguita ddai dati compressi, quando in realtà la distribuzione dei dati è p(x), la divergenza di Kullback–Leibler è il numero di bit addizionali medi per dato necessari alla compressione. E' quindi definita come

$D_{\mathrm {KL} }(p(X)\|q(X))=\sum _{x\in X}-p(x)\log {q(x)}\,-\,\left(-p(x)\log {p(x)}\right)=\sum _{x\in X}p(x)\log {\frac {p(x)}{q(x)}}.$

Nonostante sia in alcuni casi usata come una metrica per la "distanza", essa non è una vera metrica, poichè non è simmetrica.

Applicazioni

Capacità di canale

Lo studio della comunicazione su un canale, come ad esempio un cavo Ethernet, è la motivazione prima della nascita della teoria dell'informazione. Come sa chiunque abbia usato un telefono, può accadere che il canale non sia in grado di trasportare il segnale senza "danneggiarlo"; distorsioni, echi o rumore sono solo alcuni esempi di corruzione di un segnale che portano ad un degrado nella qualità della comunicazione. La domanda che sorge spontanea è dunque quale sia il massimo tasso (o bitrate) a cui posso sperare di comunicare su un canale "rumoroso" (ossia che degrada la comunicazione)?

Consideriamo il processo di comunicare su un canale discreto. Un semplice modello del processo è mostrato in figura

Qui X rappresenta lo spazio dei messaggi trasmessi, ed Y lo spazio dei messaggi ricevuti durante un'unità di tempo sul nostro canale.Sia $p(y|x)$ la distribuzione di probabilità condizionata di Y data X. Considereremo $p(y|x)$ una proprietà del canale, che non cambia e che in sostanza rappresenta il rumore da cui è affetto il canale. Allora la distribuzione congiunta di X e Y è completamente determinata dal canale e dalla scelta di $f(x)$, ossia la distribuzione marginale del messaggio che decidiamo di inviare sul canale. Dati questi vincoli, desideriamo massimizzare la quantità di informazione, o il segnale, che vogliamo comunicare sul canale. La misura appropriata per questa quantità è l'informazione mutua e il massimo dell'informazione muta è chiamato capacità di canale, che è data da:

$C=\max _{f}I(X;Y).\!$

Questa capacità ha la seguente proprietà, legata al tasso di informazione trasmesso R (dove R è solitamente in bit per simbolo). Per ogni tasso di informazione R < C ed errore di codifica ε > 0, per N grande abbastanza, esistono un codice di lunghezza N e tasso R ed un algoritmo di codifica tali che la massima probabilità di errore sia minore uguale a ε; in altre parole, è sempre possinile trasmettere con un tasso di errore basso a piacere. In più, per ogni tasso R > C, non è possibile trasmettere con un tasso di errore basso a piacere.

Teoria delle sorgenti

Quanlunque processo che generi messaggi successivi può essere considerato una sorgente di informazione. Una sorgente priva di memoria è una sorgente tale per cui ogni messaggio è una variabile aleatoria indipendente e identicamente distribuita, mentre le proprietà di ergodicità e stazionarietà impongono vincoli più restrittivi. Tutte queste sorgenti sono stocastiche.

Tasso

Information rate is the average entropy per symbol. For memoryless sources, this is merely the entropy of each symbol, while, in the most general case, it is

$r=\mathbb {E} H(M_{t}|M_{t-1},M_{t-2},M_{t-3},\ldots ).$

Precisely speaking, this is the expected conditional entropy per message (i.e. per unit time) given all the previous messages generated. It is common in information theory to speak of the "rate" or "entropy" of a language. This is appropriate, for example, when the source of information is English prose. The rate of a memoryless source is simply $H(M)$, since by definition there is no interdependence of the successive messages of a memoryless source. The rate of a source of information is related to its redundancy and how well it can be compressed.

Coding theory

Coding theory is the most important and direct application of information theory. It can be subdivided into source coding theory and channel coding theory. Using a statistical description for data, information theory quantifies the number of bits needed to describe the data, which is the information entropy of the source.

• Data Compression (Source Coding): There are two formulations for the compression problem:

1. lossless data compression the data must be reconstructed exactly;
2. lossy data compression allocates bits needed to reconstruct the data, within a specified fidelity level measured by a distortion function. This subset of Information Theory is called rate distortion theory.

• Error Correcting Code (Channel coding):While data compression removes as much redundancy as possible, an error correcting code adds just the right kind of redundancy (i.e. error correction) needed to transmit the data efficiently and faithfully across a noisy channel.

This division of coding theory into compression and transmission is justified by the information transmission theorems, or source–channel separation theorems that justify the use of bits as the universal currency for information in many contexts. However, these theorems only hold in the situation where one transmitting user wishes to communicate to one receiving user. In scenarios with more than one transmitter (the multiple-access channel), more than one receiver (the broadcast channel) or intermediary "helpers" (the relay channel), or more general networks, compression followed by transmission may no longer be optimal. Network information theory refers to these multi-agent communication models.

Intelligence Uses & Secrecy applications

Information theoretic concepts are widely used in making and breaking cryptographic systems. For an interesting historical example, see the article on deciban. Shannon himself defined an important concept now called the unicity distance. Based on the redundancy of the plaintext, it attempts to give a minimum amount of ciphertext necessary to ensure unique decipherability.

Shannon's theory of information is extremely important in work, much more so than its use in cryptography indicates. Intelligence agencies use Information Theory to keep classified information secret, and to discover as much information as possible about an adversary, in a future-proof secure way. The fundamental theorem leads us to believe it is much more difficult to keep secrets than it might first appear. In general it is not possible to stop the leakage of classified information, only to slow it. Furthermore, the more people who have access to the information, and the more those people have to work with and review that information, the greater the redundancy that information acquires. It is extremely hard to contain the flow of information that has high redundancy. This inevitable leakage of classified information is due to the psychological fact that what people know does somewhat influence their behavior, however subtle that influence might be.

Pseudo Random Number generation

A good example of the application of information theory to covert signaling is the design of the Global Positioning System signal encoding. The system uses a pseudorandom encoding that places the radio signal below the noise floor. Thus, an unsuspecting radio listener would not even be aware that there was a signal present, as it would be drowned out by assorted noise sources (eg, atmospheric and antenna noise). However, if one integrates the signal over long periods of time, using the "secret" (but known to the listener) pseudorandom sequence, one can eventually detect a signal, and then discern modulations of that signal. In the GPS system, the C/A signal has been publicly disclosed to be a 1023-bit sequence, but the pseudorandom sequence used in the P(Y) signal remains a secret. The same technique can be used to transmit and receive covert intelligence from short-range, extremely low power systems, without an Enemy even being aware of the existence of a radio signal. This is analogous to steganography. See also spread spectrum communications.

Altre applicazioni

La teoria dell'informazione ha applicazioni anche nei campi del gioco d'azzardo, della bioinformatica e della musica.

Riferimenti

L'articolo classico

• (EN) Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Technical Journal, 27, pp. 379–423 & 623–656, Luglio e Ottobre, 1948. PDF.
  Note ed altri formati.

Altri articoli scientifici

• (EN) R.V.L. Hartley, "Transmission of Information," Bell System Technical Journal, Luglio 1928
• (EN) J. L. Kelly, Jr., "A New Interpretation of Information Rate," Bell System Technical Journal, Vol. 35, Luglio 1956, pp. 917-26
• (EN) R. Landauer, "Information is Physical" Proc. Workshop on Physics and Computation PhysComp'92 (IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1-4.
• (EN) R. Landauer, "Irreversibility and Heat Generation in the Computing Process" IBM J. Res. Develop. Vol. 5, No. 3, 1961

Libri di testo

• (EN) Claude E. Shannon, Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1949. ISBN 0-252-72548-4
• (EN) Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968. ISBN 0-471-29048-3
• (EN) Thomas M. Cover, Joy A. Thomas. Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6.

2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.

• (EN) Fazlollah Reza. An Introduction to Information Theory. New York: McGraw-Hill 1961. New York: Dover 1994. ISBN 0-486-68210-2
• (EN) Raymond W. Yeung. A First Course in Information Theory Kluwer Academic/Plenum Publishers, 2002. ISBN 0-306-46791-7
• (EN) David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

Altri libri

• (EN) James Bamford, The Puzzle Palace, Penguin Books, 1983. ISBN 0-14-006748-5
• (EN) Leon Brillouin, Science and Information Theory, Mineola, N.Y.: Dover, [1956, 1962] 2004. ISBN 0-486-43918-6
• (EN) A. I. Khinchin, Mathematical Foundations of Information Theory, New York: Dover, 1957. ISBN 0-486-60434-9
• (EN) H. S. Leff and A. F. Rex, Editors, Maxwell's Demon: Entropy, Information, Computing, Princeton University Press, Princeton, NJ (1990). ISBN 0-691-08727-X
• (EN) Tom Siegfried, The Bit and the Pendulum, Wiley, 2000. ISBN 0-471-32174-5
• (EN) Charles Seife, Decoding The Universe, Viking, 2006. ISBN 0-670-03441-X

Articoli correlati

Applicazioni

• Crittografia
• Crittoanalisi
• Gioco d'azzardo

Storia

• Storia della teoria dell'informazione
• Shannon, C.E.
• Hartley, R.V.L.
• Yockey, H.P.

Teoria

• Codifica di sorgente
• Teoria della rivelazione
• Teoria della stima
• Informazione di Fisher
• Complessità di Kolmogorov
• Codifica di rete

Concetti

• Autoinformazione
• Entropia congiunta
• Entropia condizionale
• Canale (telecomunicazioni)
• Sorgente (teoria dell'informazione)
• Ricevitore (teoria dell'informazione)
• Informazione mutua
• Entropia differenziale
• Capacità di canale

Collegamenti esterni

• (EN) Gibbs, M., "Quantum Information Theory", Eprint
• (EN) Schneider, T., "Information Theory Primer", Eprint
• (EN) IEEE Information Theory Society
• (EN) On-line textbook: Information Theory, Inference, and Learning Algorithms, by David MacKay - da un'introduzione piacevole e completa della teoria di Shannon, che include i metodi più recenti di codifica come i codici di parità a bassa densità e i Turbo codici