Ratio de entropía

La ratio de entropía de una secuencia de n variables aleatorias (proceso estocástico) caracteriza la tasa de crecimiento de la entropía de la secuencia con el crecimiento de n.

La tasa de entropía de un proceso estocástico $\{X_{i}\}$ viene definida por la ecuación:

H(X)=\lim _{n\to \infty }{\dfrac {1}{n}}H(X_{1},...,X_{N})

siempre que dicho límite exista.

Una cantidad relacionada con la ratio de entropía ( H(X) ) es:

H'(X)=\lim _{n\to \infty }H(X_{n}|X_{n-1},X_{n-1},...,X_{1})

cuando dicho límite existe.

H'(X) mide la entropía condicional de la última variable aleatoria en función de todas las anteriores. Para proceso estocásticos estacionarios se cumple H(X)=H'(X)

Ejemplos

Consideremos el caso de una máquina de escribir que tiene m teclas con igual probabilidad de ser tecleada. Podemos decir que $H(X_{1},...,X_{N})=\log m^{n}$ y por tanto $H(X)=\log m$ . Podemos generalizar, si $\{X_{i}\}$ es un proceso estocástico con variables aleatorias independientes e idénticamente distribuida. Entonces:

H(X)=\lim _{n\to \infty }{\dfrac {H(X_{1},...,X_{N})}{n}}=\lim _{n\to \infty }{\dfrac {nH(X_{1})}{n}}=H(X_{1})

Supongamos un proceso estocástico con variables aleatorias independientes pero no idénticamente distribuidas. Por tanto:

H(X_{1},...,X_{N})=\sum _{i=1}^{n}H(X_{i})

Sin embargo depende de la distribución de las variables aleatorias que exista, o no, el límite y por tanto la tasa de entropía. Por ejemplo si definimos una secuencia binaria aleatoria en la que

p_{i}=P(X_{i}=1)

no es constante sino una función de i de la forma

p_{i}=0.5

si

2k<\log \log i\leq 2k+1

p_{i}=0

si

2k+1<\log \log i\leq 2k+2

para k=0,1,2...

Entonces H(X) no está definida para este proceso.

Ratio de un idioma

Un idioma o lengua, es un sistema de comunicación verbal o gestual propio de una comunidad humana. Podemos observar que en los idiomas existen letras, conjuntos de letras y palabra más comunes que otras. La gramática del idioma también restringe qué palabras y en que orden se pueden encontrar. Además el resto del mensaje (el contexto) también afecta a la probabilidad de aparición de una palabra. Por ejemplo si estamos en un contexto judicial y aparecen las letras "im", podemos determinar que la palabra "impugnar" es más probable que la palabra "imbécil". En este caso podríamos decir que hay una probabilidad de las palabras condicionada por el contexto (resto de palabras).

Por tanto podemos decir que los idiomas son 'ineficientes', es decir, contienen mucha redundancia. No sería necesario usar todos los símbolos que usamos para expresar algo. Por ejemplo si queremos transmitir el mensaje "This is a suny day" podríamos usar la expresión "This is a suny dy" de forma que el receptor nos entendería igual.^[1] Esta es el fundamento en el que se basa el uso habitual de un montón de abreviaturas cuando la gente se comunica con SMSs.

Podemos considerar un idioma como un proceso estocástico $\{X_{i}\}$ de variables aleatorias donde cada una tiene como valor un símbolo del lenguaje. Debido a las características vistas de los lenguajes, y usando la entropía condicionada, podemos decir:

H(X_{1},...,X_{n})=H(X_{1})+H(X_{2}/X_{1})+H(X_{3}/X_{1},X_{2})+...+H(X_{n}/X_{1},...,X_{n})

Definimos la ratio de entropía de un idioma (vamos a denotar por R), también llamada simplemente ratio del idioma, como la ratio de entropía del proceso:

R=H(X)=\lim _{n\to \infty }{\dfrac {1}{n}}H(X_{1},...,X_{n})

Es decir, la ratio de entropía de un idioma es el límite de la entropía de un ejemplo de texto en el idioma, cuando la longitud del texto se hace muy grande. La ratio de un idioma la podemos interpretar como la cantidad de información que contiene cada letra de nuestro alfabeto. En otras palabras, si un alfabeto consta de L elementos, existirán $2^{(\log _{2}N)*N}$ mensajes posibles de longitud N. Sin embargo como los mensajes son redundante solo obtendremos $2^{r*N}$ (con r la ratio del idioma) mensajes que tengan sentido

Para el castellano se estima que el ratio está entre 1.2 y 1.5. Para el inglés se estima en torno al 1.3.

Se llama ratio absoluta (vamos a denotar por $R_{0}$ ) de un idioma al valor máximo que puede tener la ratio de un idioma. Es decir si tenemos un idioma con n símbolos la ratio máxima del idioma será aquel en el que todos los símbolos son equiprobables e independientes. Por tanto $R_{0}=\log _{2}n$ . Este valor identifica el máximo número de bits que pueden ser codificados con cada carácter (símbolo) asumiendo que cada carácter de la secuencia es equiprobable.

Se llama redundancia de un idioma (vamos a denotar por $D$ ) a la diferencia entre la ratio absoluta y la ratio de un idioma. Por tanto $D=R_{0}-R$ . Este valor muestra cuanto puede ser reducido la longitud de un texto en un idioma sin perder ninguna información.

Dado que la redundancia $D$ nos indica el número de bits extra usados para codificar un mensaje (bits redundantes) y $R_{0}$ es el número de bits para codificar un alfabeto de n símbolos letra a letra, entonces la relación $D/R$ expresará porcentualmente que tan redundante es el lenguaje utilizado. Para el castellano tenemos $68.42<D/R_{0}<74.73$ como porcentaje de redundancia

Métodos de cálculo

Se han usado distintos métodos para aproximarse al valor de la ratio de entropía de un idioma. Estos métodos se han aplicado habitualmente al idioma inglés pero, en general, esos métodos son aplicables a cualquier otro idioma obteniendo su propio valor aproximado. Vamos a ver los métodos propuestos más importantes y cuales han sido los resultados para el idioma inglés. El idioma inglés se suele considerar formado por un alfabeto de 27 símbolos (26 letras más el espacio en blanco).

Aproximación sucesiva

Shannon^[2] describió un método para aproximarnos al cálculo de la ratio de un idioma basándose en el estudio de los n-gramas. Para ello Shannon propone una serie de lenguajes artificiales que convergen con el idioma y que van aproximándose cada vez más a él. En cada paso se van cogiendo más características del idioma pareciéndose cada vez más a él y por tanto la incertidumbre de cada símbolo, condicionada por el conocimiento de los anteriores, se va reduciendo. De esta forma va acotando paulatinamente la ratio del idioma. La serie de lenguajes artificiales que propone son los siguientes:

Aproximación de símbolos orden 0. En esta aproximación todos los símbolos son equiprobables e independientes. Por tanto el valor de ratio del idioma será igual a la ratio absoluta e igual a $\log _{2}27$ y por tanto 4.76.
Aproximación de símbolos de orden 1. En esta aproximación tenemos símbolos independientes pero cada símbolo tendrá la misma probabilidad que el símbolo tiene en el idioma que se está trabajando, en este caso el inglés. El valor de la ratio de este lenguaje se ha calculado y es aproximadamente 4.03
Aproximación de símbolos de orden 2. Es similar a la aproximación de orden 1 pero en lugar de aplicar la frecuencia de los símbolos se aplica la frecuencia de los digramas (secuencias de 2 símbolos) en el idioma. Es decir, dado un símbolo se calcula la probabilidad del siguiente en función de la probabilidad de los digramas que forma con el símbolo anterior. El valor de la ratio de este lenguaje se ha calculado y es aproximadamente 3.9
Aproximación de símbolos de orden 3. Es similar a la aproximación de orden 2 pero en lugar de aplicar la frecuencia de los digramas se aplica la frecuencia de los trigramas (secuencias de 3 símbolos) en el idioma. Es decir, dado un símbolo se calcula la probabilidad del siguiente en función de la probabilidad de los trigramas que forma con los dos símbolo anteriores.
Aproximación de símbolos de orden 4. Es similar a la aproximación de orden 3 pero en lugar de aplicar la frecuencia de los trigramas se aplica la frecuencia de los tetragramas (secuencias de 4 símbolos) en el idioma. Es decir, dado un símbolo se calcula la probabilidad del siguiente en función de la probabilidad de los tetragramas que forma con los tres símbolo anteriores. Esta aproximación no fue propuesta por el documento original de Shannon. El valor de la ratio de este lenguaje se ha calculado y es aproximadamente 2.8
Aproximación de palabras de orden 1. Se escogen palabras del inglés y la frecuencia de cada una es la que tiene cada palabra en el idioma.
Aproximación de palabras de orden 2. Se usa las probabilidades de transición entre palabras del idioma. Sin embargo no se incluye ninguna otra probabilidad en la estructura.

Sin embargo estos valores sólo sirven para acotar ya que no capturan toda la estructura del idioma, sólo capturan una parte (aunque cada vez más importante).

La aplicación de esta técnica de acotación se puede extender para acotar la ratio de entropía de otros tipos de fuentes de información. Por ejemplo, podríamos aplicarla a los distintos métodos de codificación de imágenes.

Estimación mediante el juego de adivinación de Shannon

Este método de estimación fue realizado por Shannon en 1950^[3] obteniendo un valor de 1.3.

El método consiste en coger un ejemplo de texto suficientemente largo y preguntar sucesivamente a un humano que adivine la próxima letra. Si un sujeto contesta con un símbolo x podemos interpretar que el sujetoo estima que el símbolo x es el más probable en el contexto que está analizando. Si fallara contestaría con el siguiente más probable y así sucesivamente. El experimentador guarda el número de intentos necesitados para calcular cada siguiente carácter. Con los datos obtenidos se puede calcular la distribución empírica de la frecuencia del número de adivinaciones requeridas para calcular el siguiente carácter. Muchas letras requerirán sólo un intento, sin embargo otras serán más difíciles (por ejemplo las iniciales de palabras o frases).

Usando este método con distintos textos independientes podemos hacer una estimación de la ratio del idioma ya que podemos conjeturar que la entropía de las secuencia a adivinar es la entropía del idioma. Por tanto la entropía de la secuencia a adivinar está vinculada con la entropía del histograma construido contabilizando los intentos en el experimento.

Estimación mediante apuestas

En este enfoque hacemos que un sujeto humano apueste sobre la próxima letra de un texto en inglés. Esto permite ser más finos en la gradación de los juicios sobre la adivinación de la próxima letra. En este caso, la elección óptima es proporcional a la probabilidad condicional de la próxima letra. Como tenemos 27 símbolos entonces se pagará con la proporción 27 a 1 si se elige la letra correcta.

La apuesta de forma secuencial es equivalente a apostar sobre la secuencia completa. Por tanto la apuesta después de n letras puede ser escrita como:

S_{n}=(27)^{n}b(X_{1},X_{2},...,X_{n})

donde $b(X_{1},X_{2},...,X_{n}$ ) es la fracción de la ganancia del apostante en la secuencia.

Si asumimos que el sujeto conoce la distribución de probabilidad subyacente podemos estimar que:

H_{n}(X)\leq \log _{2}27-{\dfrac {1}{n}}\log S_{n}

siendo $H_{n}(X)$ la entropía. A partir de ahí se puede estimar la ratio de entropía

En un experimento^[4] con 12 sujetos con un texto de 75 letras devolvió una estimación de 1.34 como ratio del idioma inglés.

Referencias

Thomas M. Cover, Joy A. Thomas,"Elements of Information Theory", John Wiley & Sons. Second Edition 2006
Jorge Ramió Aguirre, Aplicaciones criptográficas. Libro guía de la asignatura de Seguridad Informática. Escuela Universitaria de Informática. Universidad Politécnica de Madrid. Enero 1998.

↑ Denis Trček,"Managing information systems security and privacy", Springer-Verlag Berling Heidelberg 1996
↑ C. E. Shannon,"A Mathematical Theory of Communication",The Bell System Technical Journal Vol 27 pp. 379–423, 623–656, July, October, 1948
↑ C. E. Shannon, "Prediction and entropy of printed English". Bell Syst. Tech. J., 30:50–64, Enero 1951
↑ T. M. Cover and R. King. A convergent gambling estimate of the entropy of English. IEEE Trans. Inf. Theory, IT-24:413–421, 1978.

Datos: Q1345213

[1] Denis Trček,"Managing information systems security and privacy", Springer-Verlag Berling Heidelberg 1996

[2] C. E. Shannon,"A Mathematical Theory of Communication",The Bell System Technical Journal Vol 27 pp. 379–423, 623–656, July, October, 1948

[3] C. E. Shannon, "Prediction and entropy of printed English". Bell Syst. Tech. J., 30:50–64, Enero 1951

[4] T. M. Cover and R. King. A convergent gambling estimate of the entropy of English. IEEE Trans. Inf. Theory, IT-24:413–421, 1978.

[1]

[2]

[3]

[4]