Entropia de Shannon

Dos bits d'entropia: en el cas de llançar a l'aire dues monedes justes, l'entropia d'informació en bits és el logaritme en base 2 del nombre de possibles resultats; amb dues monedes hi ha quatre possibles resultats, i dos bits d'entropia. En general, l'entropia d'informació és la quantitat mitjana d'informació que es transmet en un esdeveniment, considerant-ne tots els possibles resultats.

L'entropia de Shannon, (formulada per Claude Shannon) és una funció matemàtica que intuïtivament es correspon amb la quantitat d'informació continguda o lliurada per una font d'informació. Aquesta font pot ser un text escrit en un idioma determinat, un senyal elèctric, un fitxer d'ordinador o qualsevol (col·lecció de bytes). Des del punt de vista d'un receptor, com més informació diferent emet la font, més gran és l'entropia (o incertesa sobre el que emet la font), i viceversa. Com més informació rep el receptor sobre el missatge transmès, més disminueix l'entropia (incertesa) respecte aquest missatge, per raó d'aquest augment d'informació. La definició d'entropia de Shannon és tal que com més redundant sigui la font, menys informació conté. En absència de restriccions particulars, l'entropia és màxima per a una font en la que tots els símbols són igualment probables (equiprobables).

Donada una variable aleatòria discreta $X$, que pren valors en l'alfabet ${\mathcal {X}}$ i segueix una certa distribució $p:{\mathcal {X}}\to [0,1]$:

$\mathrm {H} (X)=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log \mathrm {P} (x_{i})}$

on $\Sigma$ denota la suma al llarg dels possibles valors de la variable aleatòria. La tria de base per $\log$, el logaritme, varia en funció de l'apliació. Usant la base 2, s'obté l'entropia en bits (o en "shannons"), mentre que la base e dóna les "unitats naturals" nat, i la base 10 dóna unitats de "dits", "bans", o "hartleys". Una definició equivalent de l'entropia és l'esperança de la auto-informació d'una variable.

Descripció

En el cas particular d'un sistema de Telecomunicacions, l'entropia de la font d'informació (l'emissor) indica la incertesa del receptor respecte del que la font transmetrà. Per exemple, una font que es considera que sempre envia el mateix símbol, per exemple, la lletra "a", té una entropia zero, és a dir, mínima. De fet, un receptor que coneix només les estadístiques de transmissió de la font assegura que el símbol següent serà un "a", sense por d'equivoca-se. El receptor no necessita rebre cap senyal per eliminar la incertesa sobre el que ha transmès la font. D'altra banda, si es considera que la font envia una "a" la meitat de temps i una "b" l'altra meitat, el receptor no està segur que el següent caràcter a rebre sigui una "a". L'entropia de la font en aquest cas, per tant, no és zero (és positiva) i representa quantitativament la incertesa que reina sobre la informació que emana de la font. Des del punt de vista del receptor, l'entropia indica la quantitat d'informació que necessita obtenir per eliminar completament la incertesa (o dubte) sobre el que ha transmès la font.

Història

El 1948, mentre treballava a Bell Laboratories, l'enginyer elèctric Claude Shannon va formalitzar matemàticament la naturalesa estadística de la "informació perduda" en senyals de línia telefònica. Per això, va desenvolupar el concepte general d'entropia de la informació, fonamental en la seva teoria de la informació.

Inicialment, no sembla que Shannon tingués especial coneixement de l'estreta relació entre la seva nova mesura i el treball anterior en termodinàmica. El terme entropia va ser suggerit pel matemàtic John von Neumann per la raó que aquesta noció s'assemblava a la que ja es coneixia com a entropia en física estadística, i podia afegir, per triomfar en qualsevol debat, que aquest terme s'havia entès malament.

El 1957, Edwin Thompson Jaynes demostrà el vincle formal entre l'entropia macroscòpica introduïda per Clausius el 1847, la microscòpica introduïda per Gibbs i l'entropia matemàtica de Shannon. Aquest descobriment va ser descrit per Myron Tribus com una "revolució passada desapercebuda".

Preàmbul

A principis de la dècada de 1940, les telecomunicacions estaven dominades pels sistemes analògics. La transmissió de ràdio i televisió es basaven en modulacions contínues com la modulació d'amplitud (AM) i la modulació de freqüència (FM). Els sons i les imatges es transformen en senyals elèctrics l'amplitud i / o freqüència els quals són funcions contínues, de vegades proporcionals, al senyal d'entrada. En el cas del so, es mesura amb un micròfon el fenomen de la pressió i la depressió que viatja a l'aire. En el cas de la televisió, la blancor de la imatge (la seva brillantor) és el principal senyal d'interès. Aquest procediment implica que el soroll afegit durant la transmissió produeix una degradació del senyal rebut. L'arquetip d'aquest tipus de soroll pren la forma de xerraire de ràdio i neu per a la televisió. La modulació analògica implica l'ús de nombres reals la dilatació decimal és infinita per representar informació (pressió sonora, intensitat de la llum, etc.). Un soroll, per petit que sigui, tingui una conseqüència directa en el senyal.

Els investigadors han admès així que una manera eficaç de protegir el soroll seria transformar el so i la imatge en nombres discrets, en lloc d'utilitzar nombres reals la precisió dels quals requereix un nombre infinit de dígits. Per exemple, es podria utilitzar el número 0 per representar la negror total i el número 10 per a un blanc perfecte, amb tots els enters entre els dos que representen nivells successius de gris. Si 11 nivells no semblen suficients, podem utilitzar el mateix mètode per a una divisió d'intensitats tan grans com sigui necessari per satisfer l'ull. Es pot fer un raonament similar per al so i arribem a un punt on és possible representar una pel·lícula i la seva banda sonora amb una quantitat limitada d'enters.

La transmissió d'aquests enters provoca el que anomenem comunicació digital. Si el soroll que parlem en el cas analògic es considera en una transmissió digital, es produiran errors quan aquest soroll és prou fort com per convertir un número en un altre. En el cas analògic, fins i tot un petit soroll es converteix en errors perceptibles. En digital, és poc probable que es produeixi un petit soroll per generar un error, però el soroll pot, però, fer-ho. Els investigadors han pensat que calia acceptar que la comunicació perfecta era impossible. És aquesta conjectura que va ser refutada per Shannon amb la seva teoria de la informació. Va demostrar que era possible transmetre informació sense errors utilitzant una estratègia de codificació digital mentre es consideri suficient una determinada velocitat de transmissió. Per error aquí, significa la capacitat del receptor per restaurar el missatge original fins i tot si el missatge rebut és modificat pel soroll.

Entropia d'un text comú

Shannon proposa una manera senzilla de determinar l'entropia d'un text donat per a un receptor determinat: A té el text i li demana a B que l'endevini lletra per lletra (espais inclosos). si B endevina correctament la lletra, es compta 1 (perquè A, mentre respon «sí», transmet 1 bit d'informació). Si B s'equivoca, se li dona la lletra correcta i es compta 4,75 (perquè un caràcter de 26 (és a dir, 27 - 1) representa 4.75 bits d'informació.

El mètode aplicat als texts dels diaris i als lectors normals mostra que es pot endevinar una lletra de dues, la redundància del llenguatge corrent té, per tant, un factor de 2, i el contingut informatiu d'una lletra, en aquest context, és de tan sols 2,35 bits.

Utilitat pràctica

L'entropia de Shannon s'utilitza en l'electrònica digital per a digitalitzar una font utilitzant el màxim nombre possible de bits sense perdre informació. També quantifica el nombre mínim de bits en què es pot codificar un fitxer, mesurant així els límits que els algorismes de compressió sense pèrdua poden esperar aconseguir. També s'utilitza en altres camps, com, per exemple, per a seleccionar el millor punt de vista d'un objecte tridimensional.

L'entropia com a mesura de similitud

A més d'utilitzar la codificació d'entropia com a forma de comprimir dades digitals, també es pot utilitzar un codificador d'entropia per mesurar la quantitat de similitud entre fluxos de dades i classes de dades ja existents. Això es fa generant un codificador / compressor d'entropia per a cada classe de dades; Les dades desconegudes es classifiquen donant les dades sense comprimir a cada compressor i veient quin compressor produeix la compressió més alta. El codificador amb la millor compressió és probablement el codificador format sobre les dades que eren més similars a les dades desconegudes.

Ús en aprenentatge automàtic

Les tècniques d'aprenentatge automàtic apareixen molt sovint en estadística i en teoria de la informació. En general, l'entropia és una mesura de la incertesa i l'objectiu de l'aprenentatge automàtic és precisament el de minimitzar la incertesa.

Els algorismes d'aprenentatge basat en arbres de decisió utilitzen l'entropia relativa per determinar les normes de decisió que governen les dades en cada node. El guany d'informació en arbres de decisió $IG(Y,X)$, que és igual a la diferència entre l'entropia de $Y$ i l'entropia condicional de $Y$ donat $X$, quantifica l'esperança en informació, o la reducció d'entropia, de saber addicionalment el valor d'un atribut $X$. S'utilitza el guany d'informació per identificar quins atributs del conjunt de dades proporcionen més informació i per tant s'han d'utilitzar per dividir els nodes de l'arbre òptimament.

Els models d'inferència bayesiana sovint apliquen el principi de màxima entropia per obtenir distribucions de probabilitat a priori. La idea és que la distribució que millor representa l'estat actual de coneixement d'un sistema és el que té més entropia, i que és per tant el més indicat a ser l'a priori.

La classificació estadística, ja sigui feta amb regressió logística o amb xarxes neuronals artificials sovint utilitza una funció de pèrdues estàndard, anomenada pèrdua d'entropia creuada que minimitza l'entropia creuada mitjana entre la veritat i les distribucions predites. En general, l'entropia creuada és una mesura de la diferència entre duos conjunts de dades amb divergència de Kullback-Liebler (o entropia relativa) similar.

Bibliografia

• Cover, Thomas M.; Thomas, Joy A. Elements of Information Theory (en anglès). Wiley, 1991-08-26. ISBN 978-0-471-06259-2. 
• Fano, Robert M. Transmission of Information: A Statistical Theory of Communications (en anglès). M.I.T. Press, 1961. ISBN 978-0-262-06001-1. 
• Feinstein, Amiel «A new basic theorem of information theory». Research Laboratory for Electronics - Technical Reports, 1954.
• MacKay, David J. C.. Information Theory, Inference and Learning Algorithms (en anglès). Cambridge University Press, 2003-09-25. ISBN 978-0-521-64298-9. 
• Shannon, C. E. «A mathematical theory of communication». The Bell System Technical Journal, 27, 3, 1948-07, pàg. 379–423. Arxivat de l'original el 1998-01-31. DOI: 10.1002/j.1538-7305.1948.tb01338.x. ISSN: 0005-8580 [Consulta: 15 març 2024].
• Wolfowitz, J. «The coding of messages subject to chance errors». Illinois Journal of Mathematics, 1, 4, 01-12-1957. DOI: 10.1215/ijm/1255380682. ISSN: 0019-2082.

Vegeu també

• Segon teorema de Shannon
• A Mathematical Theory of Communication

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Entropia de Shannon

• Un applet de Java que representa l'Experiment de Shannon per calcular l'entropia de l'Anglès