Teoria de la informació

La teoria de la informació estudia la quantificació, l'emmagatzamatge i la comunicació de la informació. El seu pioner va ser Claude E. Shannon a l'any 1948, quan va demostrar que aquesta teoria es podia mesurar i definir com una ciència. El mateix any va publicar "A Mathematical Theory of Communication" on estudiava els límits fonamentals en el processament del senyal, i operacions com la compressió de dades. Aquesta disciplina inclou aplicacions com la compressió de dades sense pèrdua (com per exemple els fitxers .ZIP), amb pèrdua (com per exemple els MP3 o JPEG), i la codificació de canal (com per exemple l'ADSL). L'impacte d'aquest principi ha estat immens en la societat del segle XX: la invenció del disc compacte (CD), els telèfons mòbils, el desenvolupament d'Internet, els satèl·lits de comunicacions i sondes espacials, l'estudi del llenguatge i la percepció humana, la comprensió dels forats negres, neurobiologia, ecologia, visió humana, etc.

La clau de volta de l'estudi de Shannon va ser la definició d'entropia en el seu article. Shannon, la va definir com la quantitat d'informació obtinguda d'una font d'informació. Un exemple per a representar-ho seria el llançament d'una moneda (cara o creu) dona menys informació (és a dir, té menys entropia) que el llançament d'un dau (que té sis valors possibles).

Introducció

La teoria de la informació estudia la transmissió, el procés, l'extracció i l'ús de la informació. De forma abstracta, la informació pot ser vista com la resolució d'una incertesa, o d'una manca de coneixement (sabem que en el procés del coneixement primerament obtenim dades, que es converteixen en informació, i nosaltres la fem coneixement). D'altra banda, en el cas de comunicació d'informació sobre un canal sorollós, en l'article de Shannon "A Mathematical Theory of Communication", es tracta la informació com un conjunt de possibles missatges, i l'objectiu és enviar aquests missatges a través d'un canal sorollós. Per la part del receptor, l'objectiu és reconstruir el missatge amb una baixa probabilitat d'error, tot i el soroll del canal. El resultat principal de l'article de Shannon és el teorema de codificació de canal, que demostra que la quantitat màxima d'informació que es pot transmetre per un canal sorollós és asimptòticament igual a la capacitat del canal, quantitat que depèn només de l'estadística del canal.

La teoria de codis s'ocupa de trobar mètodes, anomenats codis. La seva funció és incrementar l'eficiència i reduir la taxa d'errors en la comunicació de dades sobre canals sorollosos fins al límit teòric del canal. Aquests codis poden classificar-se en tècniques de compressió de dades i tècniques en correcció d'errors. Un altre tipus de codis són els algorismes criptogràfics.

Història

L'article que va iniciar aquesta disciplina va ser l'article de Claude E. Shannon, que s'anomena "A Mathematical Theory of Communication", i va ser escrit per ell mateix mentre treballava als Laboratoris Bell el 1948.

Algunes idees inicials de l'obra s'havien treballat anteriorment als Laboratoris Bell, totes assumint implícitament esdeveniments d'igual probabilitat. L'article de Harry Nyquist de 1924, "Certain Factors Affecting Telegraph Speed", contenia una secció on quantificava "intel·ligència" i "velocitat de la línia", donant la relació W = K log m (similar a la constant de Boltzmann), on "W "és la velocitat de transmissió d'inteligència, "m" és el nombre de valors de voltatge a cada moment i "K" és una constant. Ralph Hartley l'any 1928 en el seu article "Transmissión of Information", utilitza la paraula "informació" com una quantitat mesurable, com l'habilitat del receptor de distingir una seqüència de símbols d'una altra, i quantificant-la com: H = log Sⁿ = n log S. On "S" és el nombre de possibles símbols i "n" el nombre de símbols en una transmissió. La unitat de transmissió era per tant un dígit decimal, anomenat Hartley, com a escala o unitat de mesura d'informació. Alan Turing l'any 1940 va usar idees similars com a part de les anàlisis estadístiques per trencar els codis almenys durant la segona guerra mundial.

Part de les matemàtiques sobre la teoria de la informació amb esdeveniments amb diferents probabilitats, es van desenvolupar en el camp de la termodinàmica per Ludwig Boltzmanni i J. Willarg Gibbs. La connexió entre l'entropia teòrica de la informació i l'entropia de la termodinàmica és font d'estudis diversos.

Tornant a Shannon, ell introdueix per primer cop un model de comunicació quantitatiu i qualitatiu com un procés estadístic, començant amb la frase:

- "El problema fonamental de la comunicació és el de reproduir en un punt, de forma exacta o aproximada, el missatge seleccionat en un altre lloc."

D'aquí sorgiren idees per:

• L'entropia de la informació i redundància de la font, i la seva rellevància en el teorema de la codificació.
• Informació mútua i la capacitat d'un canal sorollós, incloent la comunicació sense pèrdues donat pel teorema de codificació de canal.
• Els resultats pràctics de la llei de Shannon-Hartley de la capacitat d'un canal Gaussià.
• La definició de bit com a unitat fonamental d'informació.

Estudi de la quantitat d'informació

La teoria de la informació es basa en la teoria de probabilitat i estadística. La quantitat d'informació més important és l'entropia; la informació en una variable aleatòria, i la informació mútua, la quantitat d'informació comú entre dues variables aleatòries. La quantitat primera indica la facilitat amb què les dades del missatge pot ser comprimit, mentre que la segona pot ser utilitzada per trobar el tipus de comunicació a través d'un canal.

L'elecció de la base logarítmica en la següent fórmula, determina la unitat de l'entropia d'informació que s'utilitza. La unitat més comuna de la informació és el bit, basat en el logaritme en base 2. Altres unitats inclouen el NAT, que es basa en el logaritme natural, i el Hartley, que es basa en el logaritme comú (base 10).

En el que segueix, l'expressió p log p es considera per convenció que val 0 sempre que p = 0. Es justifica per $\lim _{p\rightarrow 0+}p\log p=0$ per qualsevol logaritme.

Entropia de la font d'informació

Basada en la funció de probabilitat de cada símbol per ser comunicat, l'entropia de Shannon H en unitats de bit (per símbol), es defineix com:

$H=-\sum _{i}p_{i}\log _{2}(p_{i})$

on p_i és la probabilitat d'ocorrència del símbol i-er. Aquesta equació dona l'entropia en unitats de bit (per símbol) perquè usa logaritme en base 2, i aquesta mesura de l'entropia en base 2 es diu "de Shannon" en el seu honor. Si es fa servir logaritmes neperians, la mesura es dona en "nats" i de vegades s'usa per evitar l'ús de constants a les fórmules. Si es fa servir logaritmes en base 10 la unitat resultats és en dígits decimals o Hartleys per símbol.

Intuïtivament, l'entropia H_X d'una variable aleatòria discreta X és una mesura de la "quantitat d'incertesa" associada amb el valor X quan només se'n coneix la seva distribució.

L'entropia d'una font que emet una seqüència de N símbols que son independents i idènticament distribuïts és N·H bits (per missatge d'N símbols). Si els símbols de la font estan idènticament distribuïts però no son independents, l'entropia d'un missatge de longitud N serà menor que N·H.

L'entropia d'un Assaig de Bernoulli com a funció de probabilitat d'èxit, sovint anomenada funció d'entropia binaria, H_b(p). L'entropia es maximitza fins a 1 bit per prova quan els dos resultats possibles son igualment probables com en el llançament d'una moneda.

Si es transmeten 1000 bits (0s i 1s) i el valor de cadascun dels bits és conegut pel receptor abans de la transmissió, és evident que no s'ha tramès informació. En canvi, si cada bit pot ser 0 o 1 independentment, s'hauran transmès 1000 shannons (o bits) d'informació. Entre aquests dos extrems, la informació es pot quantificar com segueix: Si 𝕏 és el conjunt de tots els missatges $\{X_{1},...,X_{n}\}$, i p(x) és la probabilitat que $x\in \mathbb {X}$, llavors l'entropia, H de X es defineix com:

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

On I(x) és l'autoinformació, que és la contribució a l'entropia d'un missatge individual i 𝔼_X és l'esperança. Un propietat de l'entropia és que es maximitza quan tots els missatges a l'espai de missatges son equiprobables p(x) = 1/n, en aquest cas H(X) = log n. El cas especial per una variable aleatòria amb dos valors, que és la funció d'entropia binaria, normalment amb logaritmes en base 2:

$H_{\mathrm {b} }(p)=-p\log _{2}p-(1-p)\log _{2}(1-p)$

Entropia conjunta

L'entropia conjunta de dues variables aleatòries discretes X i Y és l'entropia de la parella: (X, Y). Això implica que si X i Y són independents, la seva entropia conjunta és la suma de les entropies individuals.

Per exemple, si (X, Y) representa la posició d'una peça d'escacs — X la fila i Y la columna, l'entropia conjunta de la fila de la peça i la columna de la peça serà l'entropia de la posició de la peça:

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

Tot i la nomenclatura similar, no s'ha de confondre amb la entropia creuada.

Entropia condicional

L'entropia condicional o incertesa condicional d'X donada la variable aleatòria Y (també anomenat l'equivocació d'X sobre Y) és l'entropia mitja condicional sobre 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 p(x|y).$

Una propietat bàsica d'aquesta entropia condicional és:

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

Informació mútua (transinformació)

La informació mútua mesura la quantitat d'informació que es pot obtenir d'una variable aleatòria observant-ne una altra. És important en comunicació perquè pot maximitzar la quantitat d'informació compartida entre els senyals enviats i rebuts. L'informació mútua d'X relativa a Y es dona per:

$I(X;Y)=\mathbb {E} _{X,Y}[SI(x,y)]=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}$

on SI (d'Specific mutual Information) és el punt d'informació mútua.

Una propietat bàsica de la informació mútua és:

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

Això vol dir, que coneixent Y poden estalviar-se de mitja I(X; Y) bits per codificar X comparat amb no saber Y

La informació mútua és simètrica:

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

La informació mútua es pot expressar com la mitja de la divergència de Kullback-Leibler entre la probabilitad a posteriori d'X donat el valor d'Y i la probabilitat a priori d'X:

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

En altres paraules, és una mesura de quant, de mitja, la probabilitat de distribució d'X canviarà si es té el valor d'Y. Habitualment es recalcula com la divergència entre el producte de la distribució marginal i la distribució conjunta:

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

La informació mútua està relacionada amb el test de raó de versemblança en el context de les taules de contingència i la distribució polinomial i la prova de khi-quadrat de Pearson.

Divergència de Kullback–Leibler (guany d'informació)

La divergència de Kullback–Leibler (o divergència de la informació, guany d'informació o entropia relativa) és una forma de comparar dues distribucions: una "veritable" distribució de probabilitats p(X) i una distribució de probabilitat arbitrària q(X). Si es comprimeix les dades de tal manera que s'assumeix que q(X) és la distribució que mana les dades, quan en realitat és p(X) la distribució correcta, la divergència de Kullback–Leibler és la mitja de bits que cal afegir per cada dada. Per tant, es defineix com:

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

Tot i que alguns cops es fa servir com a mètrica de distància, la divergència KL no és una mètrica, ja que no és simètrica i no satisfà la desigualtat triangular.

Altres quantitats

Altres quantitats importants en teoria de la informació inclouen la entropia de Rényi (una generalització de l'entropia), entropia diferencial (una generalització de quantitats d'informació per distribucions continues) i la informació mútua condicional.

Aplicacions de la teoria de la informació

• Cibernètica
• Compressió de dades
• Criptoanàlisi
• Criptografia
• Informació asimètrica
• Intel·ligència
• Joc d'atzar
• Network Coding
• Teoria de detecció de senyals

Vegeu també

• Criteri de Nyquist
• Distància de Hamming
• Entropia de Shannon
• Inferència bayesiana
• Quantificador vectorial
• Redundància informàtica

Bibliografia

• Arndt, C. Information Measures, Information and its Description in Science and Engineering (Springer Series: Signals and Communication Technology), 2004, ISBN 978-3-540-40855-0
• Ash, RB. Information Theory. New York: Interscience, 1965. ISBN 0-470-03445-9. New York: Dover 1990. ISBN 0-486-66521-6
• Gallager, R. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968. ISBN 0-471-29048-3
• Goldman, S. Information Theory. New York: Prentice Hall, 1953. New York: Dover 1968 ISBN 0-486-62209-6, 2005 ISBN 0-486-44271-3
• Cover, Thomas; Thomas, Joy A. Elements of information theory. 2nd. Nova York: Wiley-Interscience, 2006. ISBN 0-471-24195-4. 
• Csiszar, I, Korner, J. Information Theory: Coding Theorems for Discrete Memoryless Systems Akademiai Kiado: 2nd edition, 1997. ISBN 963-05-7440-3
• MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Mansuripur, M. Introduction to Information Theory. New York: Prentice Hall, 1987. ISBN 0-13-484668-0
• McEliece, R. The Theory of Information and Coding". Cambridge, 2002. ISBN 978-0521831857
• Pierce, JR. "An introduction to information theory: symbols, signals and noise". Dover (2nd Edition). 1961 (reprinted by Dover 1980).
• Reza, F. An Introduction to Information Theory. New York: McGraw-Hill 1961. New York: Dover 1994. ISBN 0-486-68210-2
• Shannon, Claude; Weaver, Warren. The Mathematical Theory of Communication. Urbana, Illinois: University of Illinois Press, 1949. ISBN 0-252-72548-4. LCCN 49-11922. 
• Stone, JV. Chapter 1 of book "Information Theory: A Tutorial Introduction", University of Sheffield, England, 2014. ISBN 978-0956372857.
• Yeung, RW. A First Course in Information Theory Kluwer Academic/Plenum Publishers, 2002. ISBN 0-306-46791-7.
• Yeung, RW. Information Theory and Network Coding Springer 2008, 2002. ISBN 978-0-387-79233-0
• Holik, Federico. 2016. Teoría de la información de Claude E. Shannon. En Diccionario Interdisciplinar Austral, editado por Claudia E. Vanney, Ignacio Silva y Juan F. Franck. Recuperado de: http://dia.austral.edu.ar/Teoría_de_la_información_de_Claude_E._Shannon

Enllaços externs

• A Mathematical Theory of Communication by Claude E. Shannon Arxivat 1998-01-31 a Wayback Machine.
• Michiel Hazewinkel (ed.). Information. Encyclopedia of Mathematics (en anglès). Springer, 2001. ISBN 978-1-55608-010-4. 
• Lambert F. L. (1999), "Shuffled Cards, Messy Desks, and Disorderly Dorm Rooms - Examples of Entropy Increase? Nonsense!", Journal of Chemical Education
• IEEE Information Theory Society Arxivat 2009-01-22 a Wayback Machine. and ITSoc review articles Arxivat 2009-01-22 a Wayback Machine.
• Curs en línia sobre teoria de la informació Arxivat 2019-10-20 a Wayback Machine. (The Chinese University of Hong Kong)