Teoria de la informació

De Viquipèdia
Jump to navigation Jump to search

La Teoria de la Informació estudia la quantificació, l'emmagatzemament i la comunicació de la informació Va ser proposada originalment per Claude E. Shannon el 1948 quan estudiava els límits fonamentals en el processament del senyal i operacions com la compressió de dades en l'article cabdal "A Mathematical Theory of Communication" (Una teoria matemàtica de la comunicació). Aplicacions d'aquesta disciplina inclouen la compressió de dades sense pèrdua (com els fitxers .ZIP), compressió amb pèrdua de dades (com els MP3 o JPEG) i la codificació de canal (com per exemple l'ADSL). El seu impacte ha estat immens en la societat del segle XX: la invenció del Disc Compacte (CD), els telèfons mòbils, el desenvolupament d'Internet, la comunicació amb satèl·lits i sondes espacials, l'estudi del llenguatge i la percepció humana, la comprensió dels forats negres, neurobiologia,[1] ecologia,[2] visió humana,[3] etc.[4][5]

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

Introducció[modifica]

La teoria de la informació estudia la transmissió, processat, extracció i ús de la informació. De forma abstracta, la informació pot ser vista com la resolució d'una incertesa. En el cas de comunicació d'informació sobre un canal sorollós, aquesta abstracció es va concretar en l'article de 1948 de Shannon "A Mathematical Theory of Communication", on "informació" es tractada com un conjunt de possibles missatges, i l'objectiu és enviar aquests missatges a través d'un canal sorollós, i a la part del receptor reconstruir el missatge amb una baixa probabilitat d'error tot i el soroll del canal. El resultat principal de l'article de Shannon, 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.[1]

La teoria de codis s'ocupa de trobar mètodes, anomenats codis, per incrementar l'eficiència i reduir la tassa 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òria[modifica]

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.

Abans d'aquest article, algunes idees inicials s'havien treballat als laboratoris Bell, totes assumint implícitament esdeveniments d'igual probabilitat. L'article de Nyquits de 1924, Certain Factors Affecting Telegraph Speed, contenia una secció teòria on quantificava "inteligè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 el 1928 en el seu article Transmissión of Information, utilitza la paraula informació com una quantitat mesurable, com la 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 el 1940 va usar idees similars com a part de les anàlisis estadístiques per trencar els codis almenys durant al segona guerra mundial.

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

En l'article de Shannon s'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 importants és l'entropia, la informació en una variable aleatòria, i la informació mútua, la quantitat d'informació en comú entre dues variables aleatòries. La quantitat anterior indica la facilitat amb què les dades del missatge pot ser comprimit, mentre que l'últim pot ser utilitzat 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 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) per que 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 cada un 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:[7]

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 conjunta[modifica]

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 condicional[modifica]

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

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ó per que 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 la punt d'informació mútua.

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

Que 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 te 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 quantitats[modifica]

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]

Referències[modifica]

  1. 1,0 1,1 Spikes : exploring the neural code. Cambridge, Mass.: MIT, 1999. ISBN 9780262681087. 
  2. Margalef, Ramon «Información y diversidad específica en comunidades de organismos». Investigación Pesquera, 1956, pàg. 99-106.
  3. 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.
  4. 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. 
  5. Diccionario de Arte I (en castellà). Barcelona: Biblioteca de Consulta Larousse. Spes Editorial SL (RBA), 2003, p.300. ISBN 84-8332-390-7 [Consulta: 1 desembre 2014]. 
  6. 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.
  7. M., Reza, Fazlollah. An introduction to information theory. Nova York: Dover, 1994. ISBN 0486682102. 
  8. Robert B. Ash. Information Theory. Dover Publications, Inc., 1990. ISBN 0-486-66521-6. 

Vegeu també[modifica]

Bibliografia[modifica]

Enllaços externs[modifica]