En l'àmbit de la teoria de l'informació la entropía, també cridada entropía de l'informació i entropía de Shannon (en honor a Claude I. Shannon), medix l'incertitut d'una font d'informació.

La entropía també es pot considerar com la cantitat d'informació promig que contenen els símbols usats. Els símbols en menor provabilitat són els que aporten major informació; per eixemple, si es considera com a sistema de símbols a les paraules en un text, paraules freqüents com «que», «el», «a» aporten poca informació, mentres que paraules menys freqüents com «corren», «chiquet», «gos» aporten més informació. Si d'un text donat borrem un «que», segurament no afectarà a la comprensió i es sobreentenderá, no sent aixina si borrem la paraula «chiquet» del mateix text original. Quan tots els símbols són igualment provables (distribució de provabilitat plana), tots aporten informació rellevant i la entropía és màxima.

El concepte d'entropía és usat en termodinàmica, mecànica estadística, teoria de l'informació i seguritat entrópica. En tots els casos la entropía es concep com una «peculiaritat de certes combinacions». La entropía pot ser considerada com una mida de l'incertitut i de l'informació necessària para, en qualsevol procés, poder acotar, reduir o eliminar l'incertitut. Resulta que el concepte d'informació i el d'entropía estan bàsicament relacionats entre sí, encara que es varen necessitar anys de desenroll de la mecànica estadística i de la teoria de l'informació ans que açò fora percebut.

Relació en la entropía termodinàmica

La entropía de la teoria de l'informació està estretament relacionada en l'entropía termodinàmica. En la termodinàmica s'estudia un sistema de partícules els estats de les quals X (usualment posició i velocitat) tenen una certa distribució de provabilitat, podent ocupar varis microestats possibles (equivalents als símbols en la teoria de l'informació). La entropía termodinàmica és igual a la entropía de la teoria de l'informació d'eixa distribució (mida usant el logaritme natural) multiplicada per la constant de Boltzmann k, la qual permet passar de nats (unitat semblant al bit) a J/K. Quan tots els microestats són igualment provables, la entropía termodinàmica pren la forma k log(N). En un sistema aïllat, l'interacció entre les partícules tendix a aumentar la seua dispersió, afectant les seues posicions i les seues velocitats, lo que causa que la entropía de la distribució aumente en el temps fins a aplegar a un cert màxim (quan el mateix sistema és lo més homogéneu i desorganisat possible); lo que és denominat segona llei de la termodinàmica. La diferència entre la cantitat d'entropía que té un sistema i el màxim que pot aplegar a tindre es denomina neguentropía, i representa la cantitat d'organisació interna que té el sistema. A partir d'esta última es pot definir l'energia lliure de Gibbs, que indica l'energia que pot lliberar el sistema en aumentar la entropía fins al seu màxim i pot ser transformada en treball (energia mecànica útil) usant una màquina ideal de Carnot. Quan un sistema rep un fluix de calor, les velocitats de les partícules aumenten, lo que dispersa la distribució i fa aumentar aixina la entropía. Aixina, el fluix de calor produïx un fluix d'entropía en la mateixa direcció.

Concepte intuïtiu

El concepte bàsic d'entropía en teoria de l'informació té mucho que ver en l'incertitut que existix en qualsevol experiment o senyal aleatòria. És també la cantitat de «soroll» o «desorde» que conté o llibera un sistema. D'esta forma, podrem parlar de la cantitat d'informació que du una senyal.

Com a eixemple, considerem algun text escrit en espanyol, codificat com una cadena de lletres, espais i signes de puntuació (nostra senyal serà una cadena de caràcters). Ya que, estadísticament, alguns caràcters no són molt comuns (per eixemple, «w»), mentres uns atres sí ho són (com la «a»), la cadena de caràcters no serà tan "aleatòria" com podria aplegar a ser. Òbviament, no podem predir en exactitut quin serà el següent caràcter en la cadena, i això la faria aparentment aleatòria. Pero la entropía és l'encarregada de medir precisament eixa aleatorietat, i va ser presentada per Shannon en el seu artícul de 1948 Una teoria matemàtica de la comunicació.[1]

Shannon oferix una definició d'entropía que satisfà les següents afirmacions:

  • La mida d'informació deu ser proporcional (llineal contínua). És dir, el canvi chicotet en una de les provabilitats d'aparició d'un dels elements de la senyal deu canviar poc la entropía.
  • Si tots els elements de la senyal són equiprobables (igual de provables) a l'hora d'aparéixer, llavors la entropía serà màxima.

Eixemples de màxima entropía: Suponent que estem a l'espera d'un text, per eixemple un cable en un mensage. En dit cable solament es reben les lletres en minúscula de la a fins a la z, llavors si el mensage que nos aplega és "qalmnbphijcdgketrsfuvxyzwño" el qual posseïx una llongitut de 27 caràcters, es pot dir que este mensage aplega a nosatres en la màxima entropía (o desorde possible); ya que és poc provable que es puga pronosticar l'entrada de caràcters, puix estos no es repetixen ni estan ordenats en una forma predible.

Definició formal

Supongam que un event (variable aleatòria) té un grau de indeterminació inicial igual a k (i.i. existixen k estats possibles) i supongam tots els estats equiprobables. Llavors la provabilitat de que es done una d'eixes combinacions serà p=1/k. Després podem representar l'expressió ci com:[lower-alpha 1]

Si ara cada u dels k estats té una provabilitat pi, llavors la entropía vindrà donada per la suma ponderada de la cantitat d'informació:[2][lower-alpha 2]

Per lo tant, la entropía d'un mensage X, denotat per H(X), és el valor mig ponderat de la cantitat d'informació dels diversos estats del mensage:

que representa una mida de l'incertitut mija sobre una variable aleatòria i per tant de la cantitat d'informació.

Eixemples

  • La entropía d'un mensage M de llongitut 1 caràcter que utilisa el conjunt de caràcters ASCII, suponent una equiprobabilidad en els 256 caràcters ASCII, serà:
Erro al representar (erro de sintaxis): {\displaystyle H(M)= - sum_{i=1}^{256} �rac{1}{256}log_2 �iggl( �rac{1}{256}�iggr) = (-�rac{256}{256}) log_2�iggl(�rac{1}{256}�iggr) = 1 log_2(256)=8 }
  • Supongam que el número d'estats d'un mensage és igual a 3, M1, M2 i M3 a on la provabilitat de M1 és 50 %, la de M2 25 % i la de M3 25 %. Per tant, la entropía de l'informació és:
H(M)=1/2log2(2)+1/4log2(4)+1/4log2(4)=1,5

Informació mútua

La entropía pot vore's com a cas especial de l'informació mútua. l'informació mútua de dos variables aleatòries, denotat per I(X;I), és una cantitat que medix la dependència mútua de les dos variables; és dir, medix la reducció de l'incertitut (entropía) d'una variable aleatòria, X, pel coneiximent del valor d'una atra variable aleatòria, I.[3] De la definició podem concloure que, si X i I són iguals, llavors I(X;I)=H(X).

Propietats

La entropía té les següents propietats:

  1. La entropía és positiva. Açò és evident ya que en ser pi una provabilitat llavors 0<=pili1. Per tant, podem dir que log2pili0 i per tant −log2pige0
  2. Hlilog2(n) És dir, la entropía H està acotada superiorment (quan és màxima) i no supon pèrdua d'informació.
  3. Donat un procés en possibles resultats {A1,..,An} en provabilitats relatives p1,...,pn, la funció H(p1,dots,pn), és màxima en el cas de que p1=dots=pn=1/n,. El resultat és intuïtiu ya que tenim la major incertitut del mensage, quan els valors possibles de la variable són equiprobables
  4. Donat un procés en possibles resultats {A1,..,An} en provabilitats relatives p1,...,pn, la funció H(p1,dots,pn), és nula en el cas de que pi=0 per a tot i, llevat para una classe, tal que: pj=1. De forma intuïtiva podem pensar que quan un o més estats tenen una provabilitat alta, disminuïx significativament la entropía perque, com és llògic, existix una menor incertitut respecte al mensage que es rebrà.

Codificador òptim

Un codificador òptim és aquell que utilisa el mínim número de bits per a codificar un mensage. Un codificador òptim usarà còdics curts per a codificar mensages freqüents i deixarà els còdics de major llongitut per a aquells mensages que siguen menys freqüents. D'esta forma s'optimisa el rendiment del canal o zona d'almagasenament i el sistema és eficient en térmens del número de bits per a representar el mensage.

Per eixemple, el còdic Morse s'aprofita d'este principi per a optimisar el número de caràcters a transmetre a partir de l'estudi de les lletres més freqüents de l'alfabet anglés. Encara que el còdic Morse no és un codificador òptim, assigna a les lletres més freqüent còdics més curts. Un atre eixemple seria l'algoritme de Huffman de codificació que servix per a compactar informació.[4] Este método es basa en el codificador òptim. Per a això lo primer que fa és recórrer tota l'informació per a trobar la freqüència dels caràcters i despuix a partir d'esta informació busca el codificador òptim per mig d'arbres binaris. Algunes tècniques de compressió com LZW o deflación no usen provabilitats dels símbols aïllats, sino que usen les provabilitats conjuntes de chicotetes seqüències de símbols per a codificar el mensage, per lo que poden conseguir un nivell de compressió major.

Podem construir un codificador òptim basant-nos en la entropía d'una variable aleatòria d'informació X. En efecte, la entropía nos dona el número mig de bits (si usem logaritmes de base 2) necessaris per a codificar el mensage a través d'un codificador òptim i per tant nos determina el llímit màxim al que es pot comprimir un mensage usant un enfocament símbol a símbol sense cap pèrdua d'informació (demostrat analíticamente per Shannon), el llímit de compressió (en bits) és igual a la entropía multiplicada pel llarc del mensage. Reescrivint l'equació de càlcul de la entropía apleguem a que:

H(X)=−sumip(xi)log2p(xi)=sumi−p(xi)log2p(xi)=sumip(xi)[log2(1)−log2(p(xi))]=sumxp(x)log2(1/p(x))

Per lo tant, l'informació (que es troba definida en bits, ya que la base del logaritme és 2) que aporta un determinat valor o símbol xi,! d'una variable aleatòria discreta X,! es definix com:

Esta expressió representa el número necessari de bits per a codificar el mensage x en el codificador òptim i per tant la entropía també es pot considerar com una mida de l'informació promig continguda en cada símbol del mensage.

Eixemple

Supongam que el número d'estats d'un mensage és igual a 3 M1, M2 i M3 a on la provabilitat de M1 és 50 %, la de M2 25 % i la de M3 25 %.

Per a M1 tenim que log2[1/p(M1)]=log22=1
Per a M2 tenim que log2[1/p(M2)]=log24=2
Per a M3 tenim que log2[1/p(M3)]=log24=2

Per tant, en el codificador òptim per a transmetre M1 farà falta un bit i per a M2 i M3 serà necessari contar en dos bits. Per eixemple, podríem codificar M1 en "0", M2 en "10" i M3 en "11". Usant este conveni per a codificar el mensage M1M2M1M1M3M1M2M3 usaríem "010001101011" i per tant 12 bits. El valor de la entropía seria:

H(X)=1/2log2(2)+1/4log2(4)+1/4log2(4)=1,5

Per tant, el codificador òptim necessita de mija 1,5 bits per a codificar qualsevol valor de X.

Entropía condicional

Vore també artícul dedicat: Entropía condicional

Supongam que en lloc de tindre una única variable aleatòria X, existix una atra variable I dependents entre sí, és dir el coneiximent d'una (per eixemple, I) entrega informació sobre l'atra (per eixemple, X). Des del punt de vista de la entropía de l'informació podem dir que l'informació d'I disminuirà l'incertitut de X. Per tant, podem dir que la entropía de X serà condicional a I, i per tant:

Com pel teorema de Bayes tenim que p(x,i)=p(i)p(x|i) a on p(x|i) és la provabilitat de que es done un estat de X coneguda I, podem dir:

Aplicació en criptoanálisis

El concepte d'entropía condicional és molt interessant en el camp del criptoanálisis. Proporciona una ferramenta per a evaluar el grau de seguritat dels sistemes. Per eixemple, per a un sistema de sifrat hi ha dos entropía condicionals interessants:[5] Supongam

  • Un mensage M1 és somés a un procés de sifrat usant la clau K1 obtenint I(K1,M1)=C1.
  • PC(K) representen la provabilitat condicional de la clau K donat el criptograma rebut C. A voltes també es denota per P(K|C)
  • PC(M) representen la provabilitat condicional del mensage M dau el criptograma rebut C. A voltes també es denota per P(M|C)

Llavors:

  • Podem calcular la entropía del coneiximent de la clau una volta conegut el text sifrat, i per tant medir la equivocació del mensage (en anglés, message equivocation), HC(K), també denotada per H(K|C), per mig de la fòrmula:
La primera igualtat és per la definició de la entropía condicional i la segona per aplicació del teorema de Bayes.
Observar que si HC(K)=0 significa que es podrà trencar el sifrat puix ya no hi ha incertitut. Esta anulació nos introduïx en el concepte de distància d'unicitat.
  • Podem calcular la entropía del coneiximent del mensage una volta conegut el text sifrat, i per tant medir la equivocació de la clau (en anglés, key equivocation), HC(M), també denotada per H(M|C), per mig de la fòrmula:
La primera igualtat és per la definició de la entropía condicional i la segona per aplicació del teorema de Bayes.

Eixemple

Supongam una variable X en quatre estats: x1,x2,x3,x4 tots equiprobables i per tant p(xi)=1/4.

Existix ademés una atra variable I en tres estats; i1,i2,i3 en provabilitats p(i1)=1/2 i p(i2)=p(i3)=1/4. Es coneixen, ademés, les següents dependències:

Si I=i1 llavors els possibles valors de x són x1,x2,x3,x4
Si I=i2 llavors els possibles valors de x són x2,x3
Si I=i3 llavors els possibles valors de x són x3,x4

Aplicant les fòrmules tenim:

H(X)=2
H(I)=1,5
H(X/I)=1,5

En este cas el coneiximent de la dependència de X respecte I reduïx la entropía de X de 2 a 1,5.

Entropía d'un procés estocàstic

[6] Un procés estocàstic Xi és una seqüència indexada de variables aleatòries. En general, pot haver dependències entre les variables aleatòries. Per a estudiar la provabilitat de cert conjunt de valors se sol adoptar el següent conveni:

Pr[(X1,X2,...,Xn)=(x1,x2,...,xn)]=p(x1,x2,...,xn)

Siga Xii=1,..n un procés estocàstic de n variables aleatòries, i siga An el conjunt de la possibles combinacions de valors de Xii=1,..n. Es definix la entropía del procés estocàstic, també cridada entropía del n-grama i denotat per Hn, com:

Hn=H(X1,...,Xn)=sumsinAn−P((X1,...,Xn)=s)logP((X1,...,Xn)=s)

Ràtio d'entropía

Vore també artícul dedicat: Ràtio d'entropía[6] La ràtio d'entropía d'una seqüència de n variables aleatòries (procés estocàstic) caracterisa la taxa de creiximent de la entropía de la seqüència en el creiximent de n.

La ràtio d'entropía d'un procés estocàstic Xi ve definida per l'equació:

sempre que dit llímit existixca.

Atres tipos d'entropía

Algunes voltes resulta convenient usar atres mides d'informació distintes a la definició de Shannon. Entre elles, per a un conjunt de provabilitats pi dau, es poden definir les següents:

  1. Entropía llineal: L=sumipi(1−pi)
  2. Entropía de Rényi d'orde q: Erro al representar (erro de sintaxis): {\displaystyle R_{q}=�rac{1}{1-q}ln(sum_{i}p^{q}_{i}) }
  3. Entropía de tsallis d'orde q: Tq(pi)=koverq−1left(1−sumipiqight),

Per a tots estos tipos d'entropía es verifica que: Totes són majors o igual a zero. Lgeq0 ; Rqgeq0 ; Tqgeq0 per a tot qgeq0 Prenen el seu valor màxim si les provabilitats pi són iguals. La entropía de Shannon Hiés major o igual que L. i.i. HigeqL ocorrent igualtat solament en cas que Hi=0 Les entropía de Rényi i Tsallis són generalisacions de la entropía de Shannon Hi ya que limqo1Rq=limqo1Tq=Hi

Vore també

Notes

  1. ↑ Observe's que s'usa el logaritme en base 2 perque es considera que l'informació es va a representar per mig de còdic binari (es vol representar en bits). Si per a representar l'informació s'usaren valors en una base a llavors seria convenient utilisar el logaritme en base a.
  2. ↑ Observe's que és una cantitat adimensional, és dir no du unitat.

Referències

  1. ↑ A Mathematical Theory of Communication
  2. ↑ Cuevas Agustín, Gonzalo, "Teoria de l'informació, codificació i llenguages", Ed. SÀPIA (Societat per a Estudis Pedagògics Argentins), Série Informàtica 1986
  3. ↑ Donen C. Marinescu, Gabriela M. Marinescu, "Classical and Quàntum Information",Academic Press 2012
  4. ↑ Huffman, D., "A method for the Construction of Minimum-Redundancy Codes", Proc. IRE, Vol 40 1952
  5. ↑ "Applied cryptology, cryptographic protocols and computer security models", Richard A. DeMillo et al. American Mathematical Society 1983
  6. ↑ 6,0 6,1 Thomas M. Cover, Joy A. Thomas,"Elements of Information Theory", John Wiley & Sons. Second Edition 2006

Bibliografia

Enllaços externs

Referències