Entropía da información

Na teoría da información a entropía, tamén chamada entropía da información e entropía de Shannon (en honra a Claude E. Shannon), mide a incerteza dunha fonte de información.

A entropía tamén se pode considerar como a cantidade de información media que conteñen os símbolos usados. Os símbolos con menor probabilidade son os que achegan maior información; por exemplo, se se considerase como sistema de símbolos as palabras nun texto, palabras frecuentes como «que», «o», «a» achegan pouca información, mentres que palabras menos frecuentes como «corren», «neno», «can» achegan máis información. Se dun texto dado se borra un «que», seguramente non afectará á comprensión e sobreentenderase, non sendo así se se borra a palabra «neno» do mesmo texto orixinal. Cando todos os símbolos son igualmente probables (distribución de probabilidade plana), todos achegan información relevante e a entropía é máxima.

O concepto entropía emprégase en termodinámica, mecánica estatística e teoría da información. En todos os casos a entropía concíbese como unha «medida da desorde» ou a «peculiaridade de certas combinacións». A entropía pode ser considerada como unha medida da incerteza e da información necesaria para, en calquera proceso, poder acoutar, reducir ou eliminar a incerteza. O concepto de información e o de entropía están basicamente relacionados entre si, aínda que se precisaron anos de desenvolvemento da mecánica estatística e da teoría da información antes de que isto fose percibido.

Relación coa entropía termodinámica

A entropía da teoría da información está estreitamente relacionada coa entropía termodinámica. Na termodinámica estúdase un sistema de partículas cuxos estados X (usualmente posición e velocidade) teñen unha certa distribución de probabilidade, podendo ocupar varios microestados posibles (equivalentes aos símbolos na teoría da información). A entropía termodinámica é igual á entropía da teoría da información desa distribución (medida usando o logaritmo neperiano) multiplicada pola constante de Boltzmann k, a cal permite pasar de nats (unidade semellante ao bit) a J/K. Cando todos os microestados son igualmente probables, a entropía termodinámica toma a forma k log(N). Nun sistema illado, a interacción entre as partículas tende a aumentar a súa dispersión, afectando as súas posicións e as súas velocidades, o que causa que a entropía da distribución aumente co tempo até chegar a un certo máximo (cando o mesmo sistema é o máis homoxéneo e desorganizado posible); o que se denomina segunda lei da termodinámica. A diferenza entre a cantidade de entropía que ten un sistema e o máximo que pode chegar a ter denomínase neguentropía, e representa a cantidade de organización interna que ten o sistema. A partir desta última pódese definir a enerxía libre de Gibbs, que indica a enerxía que pode liberar o sistema ao aumentar a entropía até o seu máximo e pode ser transformada en traballo (enerxía mecánica útil) usando unha máquina ideal de Carnot. Cando un sistema recibe un fluxo de calor, as velocidades das partículas aumentan, o que dispersa a distribución e fai aumentar así a entropía. Así, o fluxo de calor produce un fluxo de entropía na mesma dirección.

Concepto intuitivo

Entropía da información nun ensaio de Bernoulli X (experimento aleatorio en que X pode tomar os valores 0 ou 1). A entropía depende da probabilidade P(X=1) de que X tome o valor 1. Cando P(X=1)=0.5, todos os resultados posibles son igualmente probables, polo que o resultado é pouco predicible e a entropía é máxima.

O concepto básico de entropía en teoría da información ten moito que ver coa incerteza que existe en calquera experimento ou sinal aleatorio. É tamén a cantidade de «ruído» ou «desorde» que contén ou libera un sistema. Desta forma, poderemos falar da cantidade de información que leva un sinal.

Como exemplo, considérese un texto escrito en galego, codificado como unha cadea de letras, espazos e signos de puntuación (o noso sinal será unha cadea de caracteres). Xa que, estatisticamente, algúns caracteres non son moi comúns (por exemplo, «w»), mentres outros si o son (como o «a»), a cadea de caracteres non será tan "aleatoria" como podería chegar a ser. Obviamente, non se pode predicir con exactitude cal será o seguinte carácter na cadea, e iso faríaa aparentemente aleatoria. Pero é a entropía a encargada de medir precisamente esa aleatoriedad, e foi presentada por Shannon no seu artigo de 1948, A Mathematical Theory of Communication ("Unha teoría matemática da comunicación", en inglés).

Shannon ofrece unha definición de entropía que satisfai as seguintes afirmacións:

• A medida de información debe ser proporcional (linear continua). É dicir, o cambio pequeno nunha das probabilidades de aparición dun dos elementos do sinal debe cambiar pouco a entropía.
• Se todos os elementos do sinal son equiprobables (igual de probables) á hora de aparecer, entón a entropía será máxima.

Exemplos de máxima entropía: supóñase que estamos esperando dun texto, por exemplo un cable cunha mensaxe. En devandito cable só se reciben as letras en minúscula do a até o z, entón se a mensaxe que nos chega é "qalmnbphijcdgketrsfuvxyzwño" o cal posúe unha lonxitude de 27 caracteres, pódese dicir que esta mensaxe chega a nós coa máxima entropía (ou desorde posible); xa que é pouco probable que se poida prognosticar a entrada de caracteres, pois estes non se repiten nin están ordenados nunha forma predicible.

Definición formal

Supóñase que un evento (variable aleatoria) ten un grao de indeterminación inicial igual a k {\displaystyle ${\displaystyle }$} (i.e. existen k {\displaystyle ${\displaystyle }$} estados posibles) e supóñanse todos os estados equiprobables.${\displaystyle }$ Entón a ${\displaystyle }$probabilidade de que se dea unha desas combinacións será p = ${\displaystyle }$

/

${\displaystyle }$

{\displaystyle p=1/k} . Entón pódese representar a expres${\displaystyle }$ón

${\displaystyle }$

i {\displaystyle c_{i}} como:

S${\displaystyle }$ agora cada un dos k {\dis${\displaystyle }$laystyle ${\displaystyle }$} estados ten unha probabilidade p i {\displaystyle p_{i}} , entón a entropía virá dada pola suma ponderada da cantidade de información:${\displaystyle }$

Polo tanto, a entropía dunh${\displaystyle }$a mensaxe

${\displaystyle }$

{${\displaystyle }$ ${\displaystyle }$} , denotada por H ( X ) {\displaystyle H(X)} , é o valor medio ponderado da cantidade de información dos diversos estados da mensaxe:${\displaystyle }$

que representa unha medida da incerteza media sobre unha variable aleatoria e polo tanto da cantidade de información.

Exemplos

• A entropía dunha mensaxe M de lonxitude 1 carácter que emprega o conxunto de caracteres ASCII, supondo unha equiprobabilidade nos 256 caracteres ASCII, será:

• Supóñase que o número de estados dunha mensaxe é igual a ₃, M1, M2 e M3 onde a probabilidade de M1 é 50 %, a de M2 25 % e a de M3 25 %. Polo tanto, a entropía da información é:

Información mutua

A entropía pode verse como caso especial da información mutua. A información mutua de dúas variables aleatorias, denotado por I(X;Y), é unha cantidade que mide a dependencia mutua das dúas variables; é dicir, mide a redución da incerteza (entropía) dunha variable aleatoria, X, debido ao coñecemento do valor doutra variable aleatoria, Y. Da definición pódese concluír que, se X e Y son iguais, entón I(X;X)=H(X).

Propiedades

A entropía ten as seguintes propiedades:

1. A entropía é non negativa. Isto é evi${\displaystyle }$dente xa que ao ser p i {\dis${\displaystyle }$laystyle p_{i}} unha probabilidade entón

       ${\displaystyle }$
       ${\displaystyle }$                    p             i          
       
       ${\displaystyle }$         1     {\displaystyle 0<p_{i}\leq ${\displaystyle }$} .${\displaystyle }$ Entón, ${\displaystyle }$pódese dici${\displaystyle }$r que            log             2         ⁡           p             i          
       
       ${\displaystyle }$         0     {${\displaystyle }$ \${\displaystyle }$ _{${\displaystyle }$}p_{i}\leq ${\displaystyle }$}  e polo tanto       
     
       ${\displaystyle }$                    log             2          
       
       ${\displaystyle }$                    p             i          
       
       ${\displaystyle }$         0     {\displaystyle -\log _{2}p_{i}\geq ${\displaystyle }$}${\displaystyle }$  

1. H

       ${\displaystyle }$
       
         ${\displaystyle }$                        a ${\displaystyle }$                                    (
       ${\displaystyle }$         )     {\displ${\displaystyle }$ystyle ${\displaystyle }$\leq \log _{a}(n)}  , é dicir, a entropía H está limitada superiormente (cando é máxima) e non supón perda de información.

1. Dado un proceso con posibles resultados {A1,..,An} co_n probabilidades relativas ${\displaystyle }$1,...,${\displaystyle }$_n, a función

       ${\displaystyle }$         (
       
         ${\displaystyle }$
         
           ${\displaystyle }$                            ,
       ${\displaystyle }$         ,           p             n         )     {${\displaystyle }$ H(p_{1},\dots ,p_{n})\,}  é máxima no caso de que            p             1         =
       ${\displaystyle }$         =           p             n         =         1           /         n     {\displaystyle p_{1}=\dots =p_{n}=1/n\,} .${\displaystyle }$ O resultado é intuitivo xa que se ten a maior incerteza da mensaxe, cando os valores posibles da variable son equiprobables

1. Dado un proceso con posibles resultados {A1,..,A_n} con probabil${\displaystyle }$dades relativas ${\displaystyle }$1,...,${\displaystyle }$n, a función

       ${\displaystyle }$         (
       
         ${\displaystyle }$                        1                            ,
       ${\displaystyle }$         ,           p             n         )     {${\displaystyle }$ H(p_{1},\dots ,p_{n})\,}  é nula no caso de que            p             i         =
       ${\displaystyle }$                {${\displaystyle }$ p_{i}=0}  para todo i, agás para unha clase, tal que:            p
         
           ${\displaystyle }$                            =         1     {\displaystyle p_{j}=1} .${\displaystyle }$ De forma intuitiva pódese pensar que cando un ou máis estados teñen unha probabilidade alta, diminúe significativamente a entropía porque, como é lóxico, existe unha menor incerteza respecto á mensaxe que se recibirá.

Codificador óptimo

Un codificador óptimo é aquel que emprega o mínimo número de bits para codificar unha mensaxe. Un codificador óptimo usará códigos curtos para codificar mensaxes frecuentes e deixará os códigos de maior lonxitude para aquelas mensaxes que sexan menos frecuentes. Desta forma optimízase o rendemento da canle ou zona de almacenamento e o sistema é eficiente en termos do número de bits para representar a mensaxe.

Por exemplo, o código Morse aprovéitase deste principio para optimizar o número de caracteres para transmitir a partir do estudo das letras máis frecuentes do alfabeto inglés. Aínda que o código Morse non é un codificador óptimo, asigna ás letras máis frecuente códigos máis curtos. Outro exemplo sería o algoritmo de Huffman de codificación que serve para compactar información. Este método baséase no codificador óptimo. Para iso o primeiro que fai é percorrer toda a información para atopar a frecuencia dos caracteres e logo a partir desta información busca o codificador óptimo por medio de árbores binarios. Algunhas técnicas de compresión como LZW ou deflación non usan probabilidades dos símbolos illados, senón que usan as probabilidades conxuntas de pequenas secuencias de símbolos para codificar a mensaxe, polo que poden lograr un nivel de compresión maior.

Pódese construír un codificador óptimo baseándose na entropía dunha variable aleatoria de información X. En efecto, a entropía dá o número medio de bits (se se usan logaritmos de base 2) necesarios para codificar a mensaxe a través dun codificador óptimo e polo tanto determínase o límite máximo ao que se pode comprimir unha mensaxe usando un enfoque símbolo a símbolo sen ningunha perda de información (demostrado analiticamente por Shannon), o límite de compresión (en bits) é igual á entropía multiplicada pola lonxitude da mensaxe. Reescribindo a ecuación de cálculo da entropía chégase a que:

Polo tanto, a ${\displaystyle }$información (que se atopa definida en bits, dado que a base do logaritmo é 2) que achega un determinado valor ou símbolo x i {${\displaystyle }$ ${\displaystyle }$_{i}\,\!} dunha variable aleatoria discreta X {\displaystyle X\,\!} defínese como:${\displaystyle }$

Esta expresión representa o número necesario de bits para codificar a mensaxe X no codificador óptimo e polo tanto a entropía tamén se pode considerar como unha medida da información media contida en cada símbolo da mensaxe.

Exemplo

Supóñase que o número de estados dunha mensaxe é igual a ₃ M1, M2 e M3 onde a probabilidade de M1 é 50 %, a de M2 25 % e a de M3 25 %.

${\displaystyle }$Para ${\displaystyle }$1 tense que log 2 ⁡

       ${\displaystyle }$
       ${\displaystyle }$                    /         p         (           M                        1                            )
       ${\displaystyle }$         =
       
         ${\displaystyle }$
         
           ${\displaystyle }$          
       
       ${\displaystyle }$
       ${\displaystyle }$         =         1     {\displaystyle \log _{2}[1/p(M_{1})]=\log _{2}2=1}  

${\displaystyle }$Para ${\displaystyle }$2 tense que log

           ${\displaystyle }$                            ⁡
       ${\displaystyle }$
       ${\displaystyle }$                    /         p         (           M
         
           ${\displaystyle }$                            )
       ${\displaystyle }$         =
       
         ${\displaystyle }$                        2          
       
       ${\displaystyle }$
       ${\displaystyle }$         =         2     {\displaystyle \log _{2}[1/p(M_{2})]=\log _{2}4=2}  

${\displaystyle }$Para ${\displaystyle }$₃ tense que log 2 ⁡

       ${\displaystyle }$
       ${\displaystyle }$                    /         p         (           M             3         )
       ${\displaystyle }$         =
       
         ${\displaystyle }$
         
           ${\displaystyle }$          
       
       ${\displaystyle }$
       ${\displaystyle }$         =
       ${\displaystyle }$                {\displaystyle \log _{2}[1/p(M_{3})]=\log _{2}4=2}
 

Polo tanto, no codificador óptimo para transmitir M1 fará falta un bit e para M2 e M3 será necesario contar con dous bits. Por exemplo, poderíase codificar M1 con "0", M2 con "10" e M3 con "11". Usando este convenio para codificar a mensaxe M1M2M1M1M3M1M2M3 usariamos "010001101011" e polo tanto 12 bits. O valor da entropía sería:

Polo tanto, o codificador óptimo necesita de media 1,5 bits para codificar calquera valor de X.

Entropía condicional

Supóñase que no canto de ter unha única variable aleatoria X, existe outra variable Y dependentes entre si, é dicir o coñecemento dunha (por exemplo, Y) entrega información sobre a outra (por exemplo, X). Desde o punto de vista da entropía da información podemos dicir que a información de Y diminuirá a incerteza de X. Polo tanto, pódese dicir que a entropía de X será condicional a Y, e polo tanto:

Como polo teorema de Bayes tense que p(x,y)=p(y)p(x|y) onde p(x|y) é a probabilidade de que se dea un estado de X coñecida Y, podemos dicir:

Aplicación en criptoanálise

O concepto de entropía condicional é moi interesante no campo do criptoanálise. Proporciona unha ferramenta para avaliar o grao de seguridade dos sistemas. Por exemplo, para un sistema de cifrado hai dúas entropías condicionais interesantes: Supóñase

• Unha mensaxe M1 é sometido a un proceso de cifrado usando a clave K1 obtendo E(K1,M1)=C1.
• P C ( K ) {\dis${\displaystyle }$laystyle P_{${\displaystyle }$}(${\displaystyle }$)} representan a probabilidade condicional da clave ${\displaystyle }$ dado o criptograma recibido C. Ás veces tamén se denota por P ( K

         ${\displaystyle }$                  C         )     {\displaystyle P(K|C)}${\displaystyle }$  

• P C ( M ) {\dis${\displaystyle }$laystyle P_{${\displaystyle }$}(${\displaystyle }$)} representan a probabilidade condicional da ${\displaystyle }$mensaxe M dado o criptograma recibido C. Ás veces tamén se denota por P ( M

         ${\displaystyle }$                  C         )     {\displaystyle P(M|C)}${\displaystyle }$
 

Entón:

• Pódese cal${\displaystyle }$ular a entropía do coñecemento da clave unha vez coñecido o texto cifrado, e polo tanto medir a equivocación da mensaxe (en inglés, message equivocation),

         ${\displaystyle }$                        C         (         K         )     {${\displaystyle }$ H_{C}(${\displaystyle }$)} , tamén denotada por           H (         K
       
         ${\displaystyle }$                  C         )     {\displaystyle H(K|C)} , mediante a fórmula:${\displaystyle }$

A primeira igualdade é pola definición da entropía condicional e a segunda por aplicación do teorema de Bayes.

Obsérvese que se

         ${\displaystyle }$
         
           ${\displaystyle }$                            (
       ${\displaystyle }$         )         =
       ${\displaystyle }$                {\displaystyle H_{C}(K)=0}  significa que se poderá romper o cifrado pois xa non hai incerteza. Esta anulación introduce o concepto de distancia de unicidade.

• Pódese calc${\displaystyle }$ular a entropía do coñece${\displaystyle }$mento da mensaxe unha vez coñecido o texto cifrado, e polo tanto medir a equivocación da clave (en inglés, key equivocation),

         ${\displaystyle }$                        C         (         M         )     {${\displaystyle }$ H_{C}(M)} , tamén denotada por           H (         M
       
         ${\displaystyle }$                  C         )     {\displaystyle H(M|C)} , mediante a fórmula:${\displaystyle }$

A primeira igualdade é pola definición da entropía condicional e a segunda por aplicación do teorema de Bayes.

Supóñase unha vari${\displaystyle }$able X con catro estados:

${\displaystyle }$

1 ,

${\displaystyle }$

${\displaystyle }$

,

${\displaystyle }$

${\displaystyle }$

,

${\displaystyle }$

4 {${\displaystyle }$ ${\displaystyle }$_{${\displaystyle }$},x_{2},x_{3},x_{${\displaystyle }$}} todos equiprobables e polo tanto p ( x i ) = 1 / 4 {\displaystyle p(x_{i})=1/4} .${\displaystyle }$${\displaystyle }$ Existe${\displaystyle }$ ade${\displaystyle }$mais outra variable${\displaystyle }$ ${\displaystyle }$ con tre${\displaystyle }$s estados;

${\displaystyle }$

1 , e 2 , e 3 {${\displaystyle }$ e_{${\displaystyle }$},e_{${\displaystyle }$},e_{${\displaystyle }$}} con p${\displaystyle }$robabilidades

${\displaystyle }$ ( e

${\displaystyle }$

) = ${\displaystyle }$

/

${\displaystyle }$

{${\displaystyle }$ p(e_{1})=1/2} e p ( e 2 ) = p ( e 3 ) = 1 /

${\displaystyle }$

{\displaystyle p(e_{2})=p(e_{3})=1/4} .${\displaystyle }$ Coñécense, ademais, as seguintes dependencias:

Se E =

         ${\displaystyle }$                        1     {${\displaystyle }$ E=e_{${\displaystyle }$}}  entón os posibles valores de x son             
       
         ${\displaystyle }$                        1         ,
       
         ${\displaystyle }$
         
           ${\displaystyle }$                            ,
       
         ${\displaystyle }$
         
           ${\displaystyle }$                            ,
       
         ${\displaystyle }$
         
           ${\displaystyle }$                                  {\displaystyle x_{1},x_{2},x_{3},x_{4}}${\displaystyle }$  

Se E =

         ${\displaystyle }$                        2     {${\displaystyle }$ E=e_{${\displaystyle }$}}  entón os posibles valores de x son             
       
         ${\displaystyle }$                        2         ,
       
         ${\displaystyle }$
         
           ${\displaystyle }$                                  {\displaystyle x_{2},x_{3}}${\displaystyle }$  

Se E =

         ${\displaystyle }$                        3     {${\displaystyle }$ E=e_{${\displaystyle }$}}  entón os posibles valores de x son             
       
         ${\displaystyle }$                        3         ,
       
         ${\displaystyle }$
         
           ${\displaystyle }$                                  {\displaystyle x_{3},x_{4}}${\displaystyle }$
 

Aplicando as fórmulas tense:

Neste caso o coñecemento da dependencia de X respecto de Y reduce a entropía de X de 2 a 1,5.

Entropía dun proceso estocástico

Un proceso estocástico

{

${\displaystyle }$

i } {\displaystyle \{X_{i}\}} é unha secuencia indexada de variables aleatorias. En xeral, pode haber dependencias entre as variables aleatorias. Para estudar a probabilidade de certo conxunto de valores adóitase adoptar o seguinte convenio:

Sex${\displaystyle }$a {

${\displaystyle }$

i }

${\displaystyle }$ = 1 , . . n {${\displaystyle }$ \{X_{${\displaystyle }$}\}_{i=${\displaystyle }$,..${\displaystyle }$}} un${\displaystyle }$ proceso estocástico de ${\displaystyle }$ variables aleatorias, e sexa A n {\displaystyle A^{n}} o conxunto das posibles combinacións de valores de { X i } i = 1 , . . n {\displaystyle \{X_{i}\}_{i=1,..n}} .${\displaystyle }$${\displaystyle }$${\displaystyle }$ Defí${\displaystyle }$nese a entropía do proceso estocástico, tamén c${\displaystyle }$hamada entropía do n-grama e denotado por H n {\displaystyle H_{n}} , como:

Cociente de entropía

O cociente de entropía dunha secuencia de n variables aleatorias (proceso estocástico) caracteriza a taxa de crecemento da entropía da secuencia co crecemento de n.

O cociente de entropía dun proceso estocástico {

${\displaystyle }$

i } {\displaystyle \{X_{i}\}} vén definida pola ecuación:

sempre que devandito límite exista.

Véxase tamén

• Entropía cruzada
• Perplexidade

Notas e referencias

Bibliografía

• Jorge Ramió Aguirre, Aplicaciones criptográficas. Libro guía da materia de Seguridade Informática. Escola Universitaria de Informática. Universidade Politécnica de Madrid. Xaneiro 1998.

Ligazóns externas

• Unha teoría matemática da comunicación (en inglés)
• Calculadora da entropía de Shannon (en inglés)
• Calculadora da entropía de Shannon para ficheiros (en inglés)