Teoria de la informació

teoria matemàtica del camp de la teoria del probabilitat i de l'estadística

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 a una ciència. El mateix any va publicar "A Mathematical Theory of Communication"[1] quan estudiava els límits fonamentals en el processament del senyal, i operacions com la compressió de dades. Aquesta disciplina inclou aplicacions com ara la compressió de dades sense pèrdua (com els fitxers .ZIP), amb pèrdua (com 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,[2] ecologia,[3] visió humana,[4] etc.[5][6]

La clau de volta de l'estudi de Shannon va ser la definició d'entropia en el seu article; la va definir com la quantitat d'informació obtinguda d'una font d'informació. Per exemple, el llançament d'una moneda (cara o creu) dona menys informació (té menys entropia) que el llançament d'un dau (sis valors possibles).[7]

IntroduccióModifica

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 coneixment (sabem que en el procés del coneximent 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, 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.[2]

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 son els algorismes criptogràfics.

HistòriaModifica

L'article que va iniciar aquesta disciplina va ser l'article de Claude E. Shannon "A Mathematical Theory of Communication" 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 Sn = 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:

Estudi de la quantitat d'informacióModifica

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.[8]

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   per qualsevol logaritme.

Entropia de la font d'informacióModifica

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:

 

on pi é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 HX 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, Hb(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  , i p(x) és la probabilitat que  , llavors l'entropia, H de X es defineix com:[9]

 

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:

 

Entropia conjuntaModifica

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:

 

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

Entropia condicionalModifica

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:[10]

 

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

 

Informació mútua (transinformació)Modifica

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:

 

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

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

 

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:

 

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:

 

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:

 

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ó)Modifica

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:

 

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 quantitatsModifica

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óModifica

Vegeu tambéModifica

ReferènciesModifica

  1. E. Shannon, Claude. «A Mathematical Theory of Communication» (PDF) (en anglès), Juliol, Octubre 1948. [Consulta: 5 novembre 2020].
  2. 2,0 2,1 Spikes: exploring the neural code. Cambridge, Mass.: MIT, 1999. ISBN 9780262681087. 
  3. Margalef, Ramon «Información y diversidad específica en comunidades de organismos». Investigación Pesquera, 1956, pàg. 99-106.
  4. Delgado-Bonal, Alfonso; Martín-Torres, Javier «Human vision is determined based on information theory» (en en). Scientific Reports, 6, 1, 03-11-2016. DOI: 10.1038/srep36038. ISSN: 2045-2322.
  5. Burnham, K. P.; Anderson, D. R.. Model selection and multimodel inference: A practical information-theoretic approach (en anglès). segona edició. Nova York: Springer Science, 2002. 
  6. Diccionario de Arte I (en castellà). Barcelona: Biblioteca de Consulta Larousse. Spes Editorial SL (RBA), 2003, p.300. ISBN 84-8332-390-7 [Consulta: 1r desembre 2014]. 
  7. Shannon, C. E. «A mathematical theory of communication». The Bell System Technical Journal, 27, 3, juliol 1948, pàg. 379–423. DOI: 10.1002/j.1538-7305.1948.tb01338.x. ISSN: 0005-8580.
  8. «INFORMATION THEORY: INFORMATION THEORY AND THE DIGITAL AGE» (PDF) (en anglés). Massachusetts Institute of Technology, 29-10-2020. [Consulta: 5 novembre 2020].
  9. M., Reza, Fazlollah. An introduction to information theory. Nova York: Dover, 1994. ISBN 0486682102. 
  10. Robert B. Ash. Information Theory. Dover Publications, Inc., 1990. ISBN 0-486-66521-6. 

BibliografiaModifica

Enllaços externsModifica