stringtranslate.com

Entropía (teoría de la información)

En teoría de la información , la entropía de una variable aleatoria cuantifica el nivel promedio de incertidumbre o información asociada con los estados potenciales o resultados posibles de la variable. Esto mide la cantidad esperada de información necesaria para describir el estado de la variable, considerando la distribución de probabilidades en todos los estados potenciales. Dada una variable aleatoria discreta , que toma valores en el conjunto y se distribuye de acuerdo con , la entropía es donde denota la suma sobre los valores posibles de la variable. [Nota 1] La elección de la base para , el logaritmo , varía para diferentes aplicaciones. La base 2 da la unidad de bits (o " shannons "), mientras que la base e da "unidades naturales" nat , y la base 10 da unidades de "dits", "bans" o " hartleys ". Una definición equivalente de entropía es el valor esperado de la autoinformación de una variable. [1]

Dos bits de entropía: en el caso de dos lanzamientos de moneda justos, la entropía de información en bits es el logaritmo en base 2 del número de resultados posibles : con dos monedas hay cuatro resultados posibles y dos bits de entropía. En general, la entropía de información es la cantidad promedio de información transmitida por un evento, al considerar todos los resultados posibles.

El concepto de entropía de la información fue introducido por Claude Shannon en su artículo de 1948 " Una teoría matemática de la comunicación ", [2] [3] y también se conoce como entropía de Shannon . La teoría de Shannon define un sistema de comunicación de datos compuesto por tres elementos: una fuente de datos, un canal de comunicación y un receptor. El "problema fundamental de la comunicación", como lo expresó Shannon, es que el receptor pueda identificar qué datos fueron generados por la fuente, en función de la señal que recibe a través del canal. [2] [3] Shannon consideró varias formas de codificar, comprimir y transmitir mensajes desde una fuente de datos, y demostró en su teorema de codificación de fuente que la entropía representa un límite matemático absoluto sobre qué tan bien los datos de la fuente pueden comprimirse sin pérdida en un canal perfectamente sin ruido. Shannon reforzó este resultado considerablemente para canales ruidosos en su teorema de codificación de canal ruidoso .

La entropía en la teoría de la información es directamente análoga a la entropía en la termodinámica estadística . La analogía se produce cuando los valores de la variable aleatoria designan energías de microestados, por lo que la fórmula de Gibbs para la entropía es formalmente idéntica a la fórmula de Shannon. La entropía tiene relevancia para otras áreas de las matemáticas, como la combinatoria y el aprendizaje automático . La definición puede derivarse de un conjunto de axiomas que establecen que la entropía debe ser una medida de cuán informativo es el resultado promedio de una variable. Para una variable aleatoria continua, la entropía diferencial es análoga a la entropía. La definición generaliza lo anterior.

Introducción

La idea central de la teoría de la información es que el "valor informativo" de un mensaje comunicado depende del grado en que el contenido del mensaje sea sorprendente. Si ocurre un evento muy probable, el mensaje transmite muy poca información. Por otro lado, si ocurre un evento muy improbable, el mensaje es mucho más informativo. Por ejemplo, el conocimiento de que un número en particular no será el número ganador de una lotería proporciona muy poca información, porque es casi seguro que cualquier número elegido no ganará una lotería. Sin embargo, el conocimiento de que un número en particular ganará una lotería tiene un alto valor informativo porque comunica la ocurrencia de un evento de probabilidad muy baja.

El contenido de información , también llamado sorpresa o autoinformación, de un evento es una función que aumenta a medida que disminuye la probabilidad de un evento. Cuando está cerca de 1, la sorpresa del evento es baja, pero si está cerca de 0, la sorpresa del evento es alta. Esta relación se describe mediante la función donde es el logaritmo , que da 0 sorpresa cuando la probabilidad del evento es 1. [4] De hecho, log es la única función que satisface un conjunto específico de condiciones definidas en la sección § Caracterización .

Por lo tanto, podemos definir la información o sorpresa de un evento por o equivalentemente,

La entropía mide la cantidad esperada (es decir, promedio) de información transmitida al identificar el resultado de una prueba aleatoria. [5] : 67  Esto implica que lanzar un dado tiene mayor entropía que lanzar una moneda porque cada resultado de un lanzamiento de dado tiene menor probabilidad ( ) que cada resultado de un lanzamiento de moneda ( ).

Consideremos una moneda con probabilidad p de caer en cara y probabilidad 1 − p de caer en cruz. La sorpresa máxima es cuando p = 1/2 , para la cual no se espera un resultado sobre el otro. En este caso, un lanzamiento de moneda tiene una entropía de un bit . (De manera similar, un trit con valores equiprobables contiene (alrededor de 1,58496) bits de información porque puede tener uno de tres valores). La sorpresa mínima es cuando p = 0 o p = 1 , cuando el resultado del evento se conoce de antemano, y la entropía es cero bits. Cuando la entropía es cero bits, esto a veces se conoce como unidad, donde no hay incertidumbre en absoluto - no hay libertad de elección - no hay información . Otros valores de p dan entropías entre cero y un bit.

Ejemplo

La teoría de la información es útil para calcular la cantidad mínima de información necesaria para transmitir un mensaje, como en la compresión de datos . Por ejemplo, considere la transmisión de secuencias que comprenden los 4 caracteres 'A', 'B', 'C' y 'D' a través de un canal binario. Si las 4 letras tienen la misma probabilidad (25%), no hay nada mejor que usar dos bits para codificar cada letra. 'A' podría codificarse como '00', 'B' como '01', 'C' como '10' y 'D' como '11'. Sin embargo, si las probabilidades de cada letra son desiguales, digamos que 'A' ocurre con un 70% de probabilidad, 'B' con un 26% y 'C' y 'D' con un 2% cada uno, se podrían asignar códigos de longitud variable. En este caso, 'A' se codificaría como '0', 'B' como '10', 'C' como '110' y 'D' como '111'. Con esta representación, el 70% de las veces solo se necesita enviar un bit, el 26% de las veces dos bits y solo el 4% de las veces 3 bits. En promedio, se requieren menos de 2 bits ya que la entropía es menor (debido a la alta prevalencia de "A" seguido de "B" - en conjunto el 96% de los caracteres). El cálculo de la suma de las probabilidades logarítmicas ponderadas por probabilidad mide y captura este efecto.

El texto en inglés, considerado como una cadena de caracteres, tiene una entropía bastante baja, es decir, es bastante predecible. Podemos estar bastante seguros de que, por ejemplo, "e" será mucho más común que "z", que la combinación "qu" será mucho más común que cualquier otra combinación que contenga una "q" y que la combinación "th" será más común que "z", "q" o "qu". Después de las primeras letras, a menudo se puede adivinar el resto de la palabra. El texto en inglés tiene entre 0,6 y 1,3 bits de entropía por carácter del mensaje. [6] : 234 

Definición

Llamado así por el teorema Η de Boltzmann , Shannon definió la entropía Η (letra griega mayúscula eta ) de una variable aleatoria discreta , que toma valores en el conjunto y se distribuye de tal manera que :

Aquí está el operador de valor esperado , e I es el contenido de información de X. [7] : 11  [8] : 19–20  es en sí mismo una variable aleatoria.

La entropía se puede escribir explícitamente como: donde b es la base del logaritmo utilizado. Los valores comunes de b son 2, el número de Euler e y 10, y las unidades correspondientes de entropía son los bits para b = 2 , nats para b = e y bans para b = 10. [ 9]

En el caso de para algunos , el valor del sumando correspondiente 0 log b (0) se toma como 0 , lo cual es consistente con el límite : [10] : 13 

También se puede definir la entropía condicional de dos variables y tomando valores de los conjuntos y respectivamente, como: [10] : 16  donde y . Esta cantidad debe entenderse como la aleatoriedad restante en la variable aleatoria dada la variable aleatoria .

Teoría de la medida

La entropía se puede definir formalmente en el lenguaje de la teoría de la medida de la siguiente manera: [11] Sea un espacio de probabilidad . Sea un evento . La sorpresa de es

La sorpresa esperada es

Una partición casi es una familia de conjuntos tal que y para todos los . (Esta es una relajación de las condiciones usuales para una partición). La entropía de es

Sea una sigma-álgebra sobre . La entropía de es Finalmente, la entropía del espacio de probabilidad es , es decir, la entropía con respecto a de la sigma-álgebra de todos los subconjuntos mensurables de .

Ejemplo

Entropía Η( X ) (es decir, la sorpresa esperada ) de un lanzamiento de moneda, medida en bits, graficada versus el sesgo de la moneda Pr( X = 1) , donde X = 1 representa un resultado de cara. [10] : 14–15  Aquí, la entropía es como máximo 1 bit, y para comunicar el resultado de un lanzamiento de moneda (2 valores posibles) se requerirá un promedio de como máximo 1 bit (exactamente 1 bit para una moneda justa). El resultado de un dado justo (6 valores posibles) tendría una entropía log 2 6 bits.

Considere lanzar una moneda con probabilidades conocidas, no necesariamente justas, de que salga cara o cruz; esto se puede modelar como un proceso de Bernoulli .

La entropía del resultado desconocido del siguiente lanzamiento de la moneda se maximiza si la moneda es justa (es decir, si tanto cara como cruz tienen la misma probabilidad 1/2). Esta es la situación de máxima incertidumbre, ya que es más difícil predecir el resultado del siguiente lanzamiento; el resultado de cada lanzamiento de la moneda proporciona un bit completo de información. Esto se debe a que

Sin embargo, si sabemos que la moneda no es justa, pero sale cara o cruz con probabilidades p y q , donde pq , entonces hay menos incertidumbre. Cada vez que se lanza, es más probable que salga un lado que el otro. La incertidumbre reducida se cuantifica en una entropía menor: en promedio, cada lanzamiento de la moneda proporciona menos de un bit completo de información. Por ejemplo, si p = 0,7, entonces

La probabilidad uniforme produce una incertidumbre máxima y, por lo tanto, una entropía máxima. La entropía, entonces, solo puede disminuir a partir del valor asociado con la probabilidad uniforme. El caso extremo es el de una moneda de dos caras que nunca sale cruz, o una moneda de dos caras que nunca sale cara. En ese caso, no hay incertidumbre. La entropía es cero: cada lanzamiento de la moneda no proporciona información nueva, ya que el resultado de cada lanzamiento de moneda siempre es seguro. [10] : 14–15 

Caracterización

Para entender el significado de −Σ p i log( p i ) , primero definamos una función de información I en términos de un evento i con probabilidad p i . La cantidad de información adquirida debido a la observación del evento i se desprende de la solución de Shannon de las propiedades fundamentales de la información : [12]

  1. I( p ) es monótonamente decreciente en p : un aumento en la probabilidad de un evento disminuye la información de un evento observado, y viceversa.
  2. I(1) = 0 : los eventos que siempre ocurren no comunican información.
  3. I( p 1 · p 2 ) = I( p 1 ) + I( p 2 ) : la información aprendida de eventos independientes es la suma de la información aprendida de cada evento.

Dados dos eventos independientes, si el primer evento puede producir uno de n resultados equiprobables y otro tiene uno de m resultados equiprobables, entonces hay mn resultados equiprobables del evento conjunto. Esto significa que si se necesitan log 2 ( n ) bits para codificar el primer valor y log 2 ( m ) para codificar el segundo, se necesita log 2 ( mn ) = log 2 ( m ) + log 2 ( n ) para codificar ambos.

Shannon descubrió que una elección adecuada de viene dada por: [13]

De hecho, los únicos valores posibles de son para . Además, elegir un valor para k es equivalente a elegir un valor para , de modo que x corresponde a la base del logaritmo . Por lo tanto, la entropía se caracteriza por las cuatro propiedades anteriores.

Las diferentes unidades de información ( bits para el logaritmo binario log 2 , nats para el logaritmo natural ln , bans para el logaritmo decimal log 10 y así sucesivamente) son múltiplos constantes entre sí. Por ejemplo, en el caso de un lanzamiento de moneda justo, si sale cara, se obtiene log 2 (2) = 1 bit de información, que es aproximadamente 0,693 nats o 0,301 dígitos decimales. Debido a la aditividad, n lanzamientos proporcionan n bits de información, que son aproximadamente 0,693 n nats o 0,301 n dígitos decimales.

El significado de los eventos observados (el significado de los mensajes ) no importa en la definición de entropía. La entropía solo tiene en cuenta la probabilidad de observar un evento específico, por lo que la información que encapsula es información sobre la distribución de probabilidad subyacente , no el significado de los eventos en sí.

Caracterización alternativa

Otra caracterización de la entropía utiliza las siguientes propiedades. Denotamos p i = Pr( X = x i ) y Η n ( p 1 , ..., p n ) = Η( X ) .

  1. Continuidad: H debe ser continua , de modo que cambiar los valores de las probabilidades en una cantidad muy pequeña solo debería cambiar la entropía en una pequeña cantidad.
  2. Simetría: H no debería cambiar si se reordenan los resultados x i . Es decir, para cualquier permutación de .
  3. Máximo: debe ser máximo si todos los resultados son igualmente probables, es decir .
  4. Número creciente de resultados: para eventos equiprobables, la entropía debería aumentar con el número de resultados, es decir
  5. Aditividad: dado un conjunto de n elementos distribuidos uniformemente que están divididos en k cajas (subsistemas) con b 1 , ..., b k elementos cada uno, la entropía de todo el conjunto debe ser igual a la suma de la entropía del sistema de cajas y las entropías individuales de las cajas, cada una ponderada con la probabilidad de estar en esa caja en particular.

Discusión

La regla de aditividad tiene las siguientes consecuencias: para números enteros positivos b i donde b 1 + ... + b k = n ,

Si se elige k = n , b 1 = ... = b n = 1 , esto implica que la entropía de un determinado resultado es cero: Η 1 (1) = 0 . Esto implica que la eficiencia de un conjunto fuente con n símbolos se puede definir simplemente como igual a su entropía n -aria. Véase también Redundancia (teoría de la información) .

La caracterización aquí impone una propiedad aditiva con respecto a una partición de un conjunto . Mientras tanto, la probabilidad condicional se define en términos de una propiedad multiplicativa, . Obsérvese que un logaritmo media entre estas dos operaciones. La entropía condicional y las cantidades relacionadas heredan, a su vez, la relación simple. La definición de teoría de la medida en la sección anterior definió la entropía como una suma sobre sorpresas esperadas para una partición extremal. Aquí el logaritmo es ad hoc y la entropía no es una medida en sí misma. Al menos en la teoría de la información de una cadena binaria, se presta a interpretaciones prácticas.

Motivados por tales relaciones, se ha definido una plétora de cantidades relacionadas y en competencia. Por ejemplo, el análisis de David Ellerman de una "lógica de particiones" define una medida en competencia en estructuras duales a la de los subconjuntos de un conjunto universal. [14] La información se cuantifica como "dits" (distinciones), una medida de particiones. Los "dits" se pueden convertir en bits de Shannon , para obtener las fórmulas de la entropía condicional, y así sucesivamente.

Caracterización alternativa mediante aditividad y subaditividad

Otra caracterización axiomática sucinta de la entropía de Shannon fue dada por Aczél , Forte y Ng [15] , a través de las siguientes propiedades:

  1. Subaditividad: para variables aleatorias distribuidas conjuntamente .
  2. Aditividad: cuando las variables aleatorias son independientes.
  3. Expansibilidad: es decir, agregar un resultado con probabilidad cero no cambia la entropía.
  4. Simetría: es invariante bajo la permutación de .
  5. Pequeño para pequeñas probabilidades: .

Discusión

Se demostró que cualquier función que satisfaga las propiedades anteriores debe ser un múltiplo constante de la entropía de Shannon, con una constante no negativa. [15] En comparación con las caracterizaciones de la entropía mencionadas anteriormente, esta caracterización se centra en las propiedades de la entropía como una función de variables aleatorias (subaditividad y aditividad), en lugar de las propiedades de la entropía como una función del vector de probabilidad .

Vale la pena señalar que si descartamos la propiedad "pequeño para probabilidades pequeñas", entonces debe ser una combinación lineal no negativa de la entropía de Shannon y la entropía de Hartley . [15]

Otras propiedades

La entropía de Shannon satisface las siguientes propiedades, para algunas de las cuales es útil interpretar la entropía como la cantidad esperada de información aprendida (o incertidumbre eliminada) al revelar el valor de una variable aleatoria X :

.
. [10] : 29 
Entonces , la entropía de una variable sólo puede disminuir cuando ésta pasa a través de una función.
. [10] : 29 
para todas las funciones de masa de probabilidad y . [10] : 32 

Aspectos

Relación con la entropía termodinámica

La inspiración para adoptar la palabra entropía en la teoría de la información surgió de la estrecha similitud entre la fórmula de Shannon y fórmulas conocidas muy similares de la mecánica estadística .

En termodinámica estadística, la fórmula más general para la entropía termodinámica S de un sistema termodinámico es la entropía de Gibbs.

donde k B es la constante de Boltzmann y p i es la probabilidad de un microestado . La entropía de Gibbs fue definida por J. Willard Gibbs en 1878 después de un trabajo previo de Boltzmann (1872). [16]

La entropía de Gibbs se traslada casi sin cambios al mundo de la física cuántica para dar la entropía de von Neumann introducida por John von Neumann en 1927:

donde ρ es la matriz de densidad del sistema mecánico cuántico y Tr es la traza . [17]

En un nivel práctico cotidiano, los vínculos entre la entropía de la información y la entropía termodinámica no son evidentes. Los físicos y químicos tienden a estar más interesados ​​en los cambios en la entropía a medida que un sistema evoluciona espontáneamente alejándose de sus condiciones iniciales, de acuerdo con la segunda ley de la termodinámica , en lugar de una distribución de probabilidad inmutable. Como lo indica la minuciosidad de la constante de Boltzmann k B , los cambios en S / k B para cantidades incluso minúsculas de sustancias en procesos químicos y físicos representan cantidades de entropía que son extremadamente grandes en comparación con cualquier cosa en la compresión de datos o el procesamiento de señales . En la termodinámica clásica, la entropía se define en términos de mediciones macroscópicas y no hace referencia a ninguna distribución de probabilidad, que es central para la definición de entropía de la información.

La conexión entre la termodinámica y lo que ahora se conoce como teoría de la información fue realizada por primera vez por Ludwig Boltzmann y expresada mediante su ecuación :

donde es la entropía termodinámica de un macroestado particular (definido por parámetros termodinámicos como temperatura, volumen, energía, etc.), W es el número de microestados (varias combinaciones de partículas en varios estados de energía) que pueden producir el macroestado dado, y k B es la constante de Boltzmann . [18] Se supone que cada microestado es igualmente probable, de modo que la probabilidad de un microestado dado es p i = 1/ W . Cuando estas probabilidades se sustituyen en la expresión anterior para la entropía de Gibbs (o equivalentemente k B por la entropía de Shannon), resulta la ecuación de Boltzmann. En términos de teoría de la información, la entropía de información de un sistema es la cantidad de información "faltante" necesaria para determinar un microestado, dado el macroestado.

En opinión de Jaynes (1957), [19] la entropía termodinámica, tal como la explica la mecánica estadística , debe verse como una aplicación de la teoría de la información de Shannon: la entropía termodinámica se interpreta como proporcional a la cantidad de información adicional de Shannon necesaria para definir el estado microscópico detallado del sistema, que permanece sin comunicar mediante una descripción únicamente en términos de las variables macroscópicas de la termodinámica clásica, siendo la constante de proporcionalidad simplemente la constante de Boltzmann . Agregar calor a un sistema aumenta su entropía termodinámica porque aumenta el número de posibles estados microscópicos del sistema que son consistentes con los valores mensurables de sus variables macroscópicas, lo que hace que cualquier descripción completa del estado sea más larga. (Véase el artículo: termodinámica de máxima entropía ). El demonio de Maxwell puede (hipotéticamente) reducir la entropía termodinámica de un sistema utilizando información sobre los estados de las moléculas individuales; pero, como Landauer (desde 1961) y sus colaboradores [20] han demostrado, para funcionar el propio demonio debe aumentar la entropía termodinámica en el proceso, al menos en la cantidad de información de Shannon que se propone adquirir y almacenar primero; y por lo tanto la entropía termodinámica total no disminuye (lo que resuelve la paradoja). El principio de Landauer impone un límite inferior a la cantidad de calor que debe generar un ordenador para procesar una cantidad dada de información, aunque los ordenadores modernos son mucho menos eficientes.

Compresión de datos

La definición de entropía de Shannon, cuando se aplica a una fuente de información, puede determinar la capacidad mínima del canal requerida para transmitir de manera confiable la fuente como dígitos binarios codificados. La entropía de Shannon mide la información contenida en un mensaje en oposición a la porción del mensaje que está determinada (o es predecible). Los ejemplos de esto último incluyen la redundancia en la estructura del lenguaje o las propiedades estadísticas relacionadas con las frecuencias de ocurrencia de pares de letras o palabras, tripletes, etc. La capacidad mínima del canal se puede lograr en teoría utilizando el conjunto típico o en la práctica utilizando Huffman , Lempel–Ziv o codificación aritmética . (Véase también complejidad de Kolmogorov .) En la práctica, los algoritmos de compresión incluyen deliberadamente cierta redundancia juiciosa en forma de sumas de comprobación para protegerse contra errores. La tasa de entropía de una fuente de datos es el número promedio de bits por símbolo necesarios para codificarla. Los experimentos de Shannon con predictores humanos muestran una tasa de información entre 0,6 y 1,3 bits por carácter en inglés; [21] El algoritmo de compresión PPM puede lograr una relación de compresión de 1,5 bits por carácter en texto en inglés.

Si un esquema de compresión es sin pérdidas (uno en el que siempre se puede recuperar todo el mensaje original mediante la descompresión), entonces un mensaje comprimido tiene la misma cantidad de información que el original pero comunicada en menos caracteres. Tiene más información (mayor entropía) por carácter. Un mensaje comprimido tiene menos redundancia . El teorema de codificación de fuente de Shannon establece que un esquema de compresión sin pérdidas no puede comprimir mensajes, en promedio, para tener más de un bit de información por bit de mensaje, pero que cualquier valor menor a un bit de información por bit de mensaje se puede lograr empleando un esquema de codificación adecuado. La entropía de un mensaje por bit multiplicada por la longitud de ese mensaje es una medida de cuánta información total contiene el mensaje. El teorema de Shannon también implica que ningún esquema de compresión sin pérdidas puede acortar todos los mensajes. Si algunos mensajes resultan más cortos, al menos uno debe resultar más largo debido al principio del palomar . En la práctica, esto no suele ser un problema, porque normalmente sólo interesa comprimir ciertos tipos de mensajes, como un documento en inglés, en lugar de un texto sin sentido, o fotografías digitales en lugar de ruido, y no es importante si un algoritmo de compresión hace que algunas secuencias poco probables o poco interesantes sean más grandes.

Un estudio de 2011 en Science estima la capacidad tecnológica mundial para almacenar y comunicar información comprimida de manera óptima normalizada en los algoritmos de compresión más efectivos disponibles en el año 2007, estimando así la entropía de las fuentes tecnológicamente disponibles. [22] : 60–65 

Los autores estiman la capacidad tecnológica de la humanidad para almacenar información (totalmente comprimida entrópicamente) en 1986 y nuevamente en 2007. Dividen la información en tres categorías: para almacenar información en un medio, para recibir información a través de redes de transmisión unidireccionales o para intercambiar información a través de redes de telecomunicaciones bidireccionales . [22]

La entropía como medida de diversidad

La entropía es una de las diversas formas de medir la biodiversidad y se aplica en forma de índice de Shannon . [23] Un índice de diversidad es una medida estadística cuantitativa de cuántos tipos diferentes existen en un conjunto de datos, como las especies en una comunidad, que representa la riqueza ecológica , la uniformidad y el dominio . Específicamente, la entropía de Shannon es el logaritmo de 1 D , el verdadero índice de diversidad con parámetro igual a 1. El índice de Shannon está relacionado con las abundancias proporcionales de los tipos.

Entropía de una secuencia

Hay una serie de conceptos relacionados con la entropía que cuantifican matemáticamente el contenido de información de una secuencia o mensaje:

(La "tasa de autoinformación" también puede definirse para una secuencia particular de mensajes o símbolos generados por un proceso estocástico dado: ésta siempre será igual a la tasa de entropía en el caso de un proceso estacionario .) También se utilizan otras cantidades de información para comparar o relacionar diferentes fuentes de información.

Es importante no confundir los conceptos anteriores. A menudo, solo queda claro a qué se refieren a partir del contexto. Por ejemplo, cuando alguien dice que la "entropía" del idioma inglés es de aproximadamente 1 bit por carácter, en realidad está modelando el idioma inglés como un proceso estocástico y hablando de su tasa de entropía . El propio Shannon utilizó el término de esta manera.

Si se utilizan bloques muy grandes, la estimación de la tasa de entropía por carácter puede llegar a ser artificialmente baja porque la distribución de probabilidad de la secuencia no se conoce con exactitud; es sólo una estimación. Si se considera el texto de cada libro publicado como una secuencia, siendo cada símbolo el texto de un libro completo, y si hay N libros publicados, y cada libro se publica sólo una vez, la estimación de la probabilidad de cada libro es 1/ N , y la entropía (en bits) es −log 2 (1/ N ) = log 2 ( N ) . Como código práctico, esto corresponde a asignar a cada libro un identificador único y utilizarlo en lugar del texto del libro siempre que se quiera hacer referencia al libro. Esto es enormemente útil para hablar de libros, pero no es tan útil para caracterizar el contenido de información de un libro individual, o del lenguaje en general: no es posible reconstruir el libro a partir de su identificador sin conocer la distribución de probabilidad, es decir, el texto completo de todos los libros. La idea clave es que debe tenerse en cuenta la complejidad del modelo probabilístico. La complejidad de Kolmogorov es una generalización teórica de esta idea que permite considerar el contenido de información de una secuencia independientemente de cualquier modelo de probabilidad particular; considera el programa más corto para una computadora universal que genera la secuencia. Un código que alcanza la tasa de entropía de una secuencia para un modelo dado, más el libro de códigos (es decir, el modelo probabilístico), es uno de esos programas, pero puede que no sea el más corto.

La secuencia de Fibonacci es 1, 1, 2, 3, 5, 8, 13, .... tratando la secuencia como un mensaje y cada número como un símbolo, hay casi tantos símbolos como caracteres en el mensaje, dando una entropía de aproximadamente log 2 ( n ) . Los primeros 128 símbolos de la secuencia de Fibonacci tienen una entropía de aproximadamente 7 bits/símbolo, pero la secuencia se puede expresar utilizando una fórmula [ F( n ) = F( n −1) + F( n −2) para n = 3, 4, 5, ... , F(1) =1 , F(2) = 1 ] y esta fórmula tiene una entropía mucho menor y se aplica a cualquier longitud de la secuencia de Fibonacci.

Limitaciones de la entropía en criptografía

En el criptoanálisis , la entropía se suele utilizar de forma aproximada como medida de la imprevisibilidad de una clave criptográfica, aunque su incertidumbre real no se puede medir. Por ejemplo, una clave de 128 bits que se genera de forma uniforme y aleatoria tiene 128 bits de entropía. También se necesitan (en promedio) conjeturas para descifrarla mediante fuerza bruta. La entropía no logra capturar la cantidad de conjeturas necesarias si las posibles claves no se eligen de manera uniforme. [24] [25] En cambio, se puede utilizar una medida llamada conjetura para medir el esfuerzo necesario para un ataque de fuerza bruta. [26]

Otros problemas pueden surgir de distribuciones no uniformes utilizadas en criptografía. Por ejemplo, un bloc de notas binario de un solo uso de 1.000.000 de dígitos que utiliza el método O exclusivo. Si el bloc de notas tiene 1.000.000 bits de entropía, es perfecto. Si el bloc de notas tiene 999.999 bits de entropía, distribuidos uniformemente (cada bit individual del bloc de notas tiene 0,999999 bits de entropía), puede proporcionar una buena seguridad. Pero si el bloc de notas tiene 999.999 bits de entropía, donde el primer bit es fijo y los 999.999 bits restantes son perfectamente aleatorios, el primer bit del texto cifrado no se cifrará en absoluto.

Los datos como un proceso de Markov

Una forma habitual de definir la entropía de un texto se basa en el modelo de texto de Markov. Para una fuente de orden 0 (cada carácter se selecciona independientemente de los últimos caracteres), la entropía binaria es:

donde p i es la probabilidad de i . Para una fuente de Markov de primer orden (una en la que la probabilidad de seleccionar un carácter depende únicamente del carácter inmediatamente anterior), la tasa de entropía es:

[ cita requerida ]

donde i es un estado (ciertos caracteres anteriores) y es la probabilidad de j dado i como carácter anterior.

Para una fuente de Markov de segundo orden, la tasa de entropía es

Eficiencia (entropía normalizada)

Un conjunto de fuentes con una distribución no uniforme tendrá menos entropía que el mismo conjunto con una distribución uniforme (es decir, el "alfabeto optimizado"). Esta deficiencia en la entropía se puede expresar como una relación denominada eficiencia: [27]

Aplicando las propiedades básicas del logaritmo, esta cantidad también se puede expresar como:

La eficiencia tiene utilidad para cuantificar el uso efectivo de un canal de comunicación . Esta formulación también se conoce como entropía normalizada, ya que la entropía se divide por la entropía máxima . Además, la eficiencia es indiferente a la elección de la base (positiva) b , como lo indica la insensibilidad dentro del logaritmo final anterior.

Entropía para variables aleatorias continuas

Entropía diferencial

La entropía de Shannon está restringida a variables aleatorias que toman valores discretos. La fórmula correspondiente para una variable aleatoria continua con función de densidad de probabilidad f ( x ) con soporte finito o infinito en la línea real se define por analogía, utilizando la forma anterior de la entropía como expectativa: [10] : 224 

Esta es la entropía diferencial (o entropía continua). Un precursor de la entropía continua h [ f ] es la expresión para el funcional Η en el H-teorema de Boltzmann .

Aunque la analogía entre ambas funciones es sugerente, cabe plantearse la siguiente pregunta: ¿es la entropía diferencial una extensión válida de la entropía discreta de Shannon? La entropía diferencial carece de una serie de propiedades que posee la entropía discreta de Shannon –puede incluso ser negativa– y se han sugerido correcciones, en particular limitando la densidad de puntos discretos .

Para responder a esta pregunta es necesario establecer una conexión entre ambas funciones:

Para obtener una medida generalmente finita a medida que el tamaño del intervalo tiende a cero, en el caso discreto, el tamaño del intervalo es el ancho (implícito) de cada uno de los n intervalos (finitos o infinitos) cuyas probabilidades se denotan por p n . Como el dominio continuo se generaliza, el ancho debe hacerse explícito.

Para ello, se parte de una función continua f discretizada en compartimentos de tamaño . Por el teorema del valor medio, existe un valor x i en cada compartimento tal que la integral de la función f se puede aproximar (en el sentido de Riemann) por donde este límite y el "tamaño del compartimento tiende a cero" son equivalentes.

Denotaremos y desarrollando el logaritmo, tenemos

Como Δ → 0 , tenemos

Nota; log(Δ) → −∞ cuando Δ → 0 , requiere una definición especial de la entropía diferencial o continua:

que, como se dijo antes, se denomina entropía diferencial. Esto significa que la entropía diferencial no es un límite de la entropía de Shannon para n → ∞ . Más bien, difiere del límite de la entropía de Shannon por un desplazamiento infinito (véase también el artículo sobre la dimensión de la información ).

Limitación de la densidad de puntos discretos

Como resultado, resulta que, a diferencia de la entropía de Shannon, la entropía diferencial no es en general una buena medida de incertidumbre o información. Por ejemplo, la entropía diferencial puede ser negativa; además, no es invariante bajo transformaciones de coordenadas continuas. Este problema puede ilustrarse con un cambio de unidades cuando x es una variable adimensional. f ( x ) tendrá entonces las unidades de 1/ x . El argumento del logaritmo debe ser adimensional, de lo contrario es impropio, de modo que la entropía diferencial dada anteriormente será impropia. Si Δ es algún valor "estándar" de x (es decir, "tamaño de bin") y, por lo tanto, tiene las mismas unidades, entonces una entropía diferencial modificada puede escribirse en forma apropiada como:

y el resultado será el mismo para cualquier elección de unidades para x . De hecho, el límite de entropía discreta como también incluiría un término de , que en general sería infinito. Esto es lo esperado: las variables continuas normalmente tendrían entropía infinita cuando se discretizan. La densidad límite de puntos discretos es realmente una medida de cuánto más fácil es describir una distribución que una distribución que es uniforme en su esquema de cuantificación.

Entropía relativa

Otra medida útil de la entropía que funciona igualmente bien en el caso discreto y continuo es la entropía relativa de una distribución. Se define como la divergencia de Kullback–Leibler de la distribución a una medida de referencia m de la siguiente manera. Supongamos que una distribución de probabilidad p es absolutamente continua con respecto a una medida m , es decir, tiene la forma p ( dx ) = f ( x ) m ( dx ) para alguna función m -integrable no negativa f con m -integral 1, entonces la entropía relativa se puede definir como

En esta forma, la entropía relativa generaliza (hasta el cambio de signo) tanto la entropía discreta, donde la medida m es la medida de conteo , como la entropía diferencial, donde la medida m es la medida de Lebesgue . Si la medida m es en sí misma una distribución de probabilidad, la entropía relativa es no negativa y cero si p = m como medidas. Está definida para cualquier espacio de medida, por lo tanto, independiente de las coordenadas e invariante bajo reparametrizaciones de coordenadas si se tiene en cuenta adecuadamente la transformación de la medida m . La entropía relativa, y (implícitamente) la entropía y la entropía diferencial, dependen de la medida de "referencia" m .

Uso en teoría de números

Terence Tao utilizó la entropía para hacer una conexión útil al intentar resolver el problema de discrepancia de Erdős . [28] [29]

Intuitivamente, la idea detrás de la prueba era si hay poca información en términos de la entropía de Shannon entre variables aleatorias consecutivas (aquí la variable aleatoria se define usando la función de Liouville (que es una función matemática útil para estudiar la distribución de primos) X H = . Y en un intervalo [n, n+H] la suma sobre ese intervalo podría volverse arbitrariamente grande. Por ejemplo, una secuencia de +1 (que son valores de X H' podría tomar) tiene una entropía trivialmente baja y su suma se volvería grande. Pero la idea clave fue mostrar una reducción en la entropía en cantidades no despreciables a medida que uno expande H, lo que conduce a su vez al crecimiento ilimitado de un objeto matemático sobre esta variable aleatoria, es equivalente a mostrar el crecimiento ilimitado según el problema de discrepancia de Erdős .

La prueba es bastante compleja y no solo incluye avances en el uso novedoso de la entropía de Shannon, sino que también utiliza la función de Liouville junto con promedios de funciones multiplicativas moduladas Archivado el 28 de octubre de 2023 en Wayback Machine en intervalos cortos. Demostrando que también rompió la "barrera de paridad" Archivado el 7 de agosto de 2023 en Wayback Machine para este problema específico.

Si bien el uso de la entropía de Shannon en la prueba es novedoso, es probable que abra nuevas investigaciones en esta dirección.

Uso en combinatoria

La entropía se ha convertido en una cantidad útil en combinatoria .

Desigualdad de Loomis-Whitney

Un ejemplo simple de esto es una prueba alternativa de la desigualdad de Loomis-Whitney : para cada subconjunto AZ d , tenemos

donde P i es la proyección ortogonal en la i- ésima coordenada:

La prueba se deduce como un corolario simple de la desigualdad de Shearer : si X 1 , ..., X d son variables aleatorias y S 1 , ..., S n son subconjuntos de {1, ..., d } tales que cada entero entre 1 y d se encuentra exactamente en r de estos subconjuntos, entonces

donde es el producto cartesiano de variables aleatorias X j con índices j en S i (por lo que la dimensión de este vector es igual al tamaño de S i ).

Esbozamos cómo se sigue de esto el principio de Loomis-Whitney: De hecho, sea X una variable aleatoria uniformemente distribuida con valores en A y de modo que cada punto en A ocurre con la misma probabilidad. Entonces (por las propiedades adicionales de la entropía mencionadas anteriormente) Η( X ) = log| A | , donde | A | denota la cardinalidad de A . Sea S i = {1, 2, ..., i −1, i +1, ..., d }. El rango de está contenido en P i ( A ) y, por lo tanto , . Ahora use esto para acotar el lado derecho de la desigualdad de Shearer y exponenciar los lados opuestos de la desigualdad resultante que obtenga.

Aproximación al coeficiente binomial

Para números enteros 0 < k < n sea q = k / n . Entonces

dónde

[30] : 43 

Una buena interpretación de esto es que el número de cadenas binarias de longitud n con exactamente k muchos 1 es aproximadamente . [31]

Uso en aprendizaje automático

Las técnicas de aprendizaje automático surgen en gran medida de la estadística y también de la teoría de la información. En general, la entropía es una medida de incertidumbre y el objetivo del aprendizaje automático es minimizar la incertidumbre.

Los algoritmos de aprendizaje de árboles de decisión utilizan la entropía relativa para determinar las reglas de decisión que gobiernan los datos en cada nodo. [32] La ganancia de información en los árboles de decisión , que es igual a la diferencia entre la entropía de y la entropía condicional de dado , cuantifica la información esperada, o la reducción de la entropía, al conocer adicionalmente el valor de un atributo . La ganancia de información se utiliza para identificar qué atributos del conjunto de datos proporcionan la mayor cantidad de información y se deben utilizar para dividir los nodos del árbol de manera óptima.

Los modelos de inferencia bayesianos a menudo aplican el principio de máxima entropía para obtener distribuciones de probabilidad previa . [33] La idea es que la distribución que mejor representa el estado actual de conocimiento de un sistema es la que tiene la mayor entropía y, por lo tanto, es adecuada para ser la previa.

La clasificación en el aprendizaje automático realizada por regresión logística o redes neuronales artificiales a menudo emplea una función de pérdida estándar, llamada pérdida de entropía cruzada , que minimiza la entropía cruzada promedio entre la verdad fundamental y las distribuciones previstas. [34] En general, la entropía cruzada es una medida de las diferencias entre dos conjuntos de datos similar a la divergencia KL (también conocida como entropía relativa).

Véase también

Notas

  1. ^ Esta definición permite eventos con probabilidad 0, lo que da como resultado el indefinido . Vemos y se puede suponer que es igual a 0 en este contexto. Alternativamente, se puede definir , lo que no permite eventos con probabilidad igual a exactamente 0.

Referencias

  1. ^ Pathria, RK; Beale, Paul (2011). Mecánica estadística (tercera edición). Academic Press. pág. 51. ISBN 978-0123821881.
  2. ^ ab Shannon, Claude E. (julio de 1948). "Una teoría matemática de la comunicación" . Bell System Technical Journal . 27 (3): 379–423. doi :10.1002/j.1538-7305.1948.tb01338.x. hdl : 10338.dmlcz/101429 .(PDF, archivado desde aquí Archivado el 20 de junio de 2014 en Wayback Machine )
  3. ^ ab Shannon, Claude E. (octubre de 1948). "Una teoría matemática de la comunicación" . Bell System Technical Journal . 27 (4): 623–656. doi :10.1002/j.1538-7305.1948.tb00917.x. hdl : 11858/00-001M-0000-002C-4317-B .(PDF, archivado desde aquí Archivado el 10 de mayo de 2013 en Wayback Machine )
  4. ^ "La entropía (para la ciencia de datos) ¡explicada claramente!". Archivado desde el original el 5 de octubre de 2021. Consultado el 5 de octubre de 2021 – vía YouTube .
  5. ^ MacKay, David JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje. Cambridge University Press. ISBN 0-521-64298-1Archivado desde el original el 17 de febrero de 2016 . Consultado el 9 de junio de 2014 .
  6. ^ Schneier, B: Criptografía aplicada , segunda edición, John Wiley and Sons.
  7. ^ Borda, Mónica (2011). Fundamentos de teoría de la información y codificación. Springer. ISBN 978-3-642-20346-6.
  8. ^ Han, Te Sun; Kobayashi, Kingo (2002). Matemáticas de la información y codificación. American Mathematical Society. ISBN 978-0-8218-4256-0.
  9. ^ Schneider, TD, Introducción a la teoría de la información con un apéndice sobre logaritmos [ enlace muerto permanente ] , Instituto Nacional del Cáncer, 14 de abril de 2007.
  10. ^ abcdefghijk Thomas M. Cover; Joy ​​A. Thomas (1991). Elementos de la teoría de la información . Hoboken, Nueva Jersey: Wiley. ISBN 978-0-471-24195-9.
  11. ^ Entropía en el laboratorio n
  12. ^ Carter, Tom (marzo de 2014). Introducción a la teoría de la información y la entropía (PDF) . Santa Fe. Archivado (PDF) del original el 4 de junio de 2016. Consultado el 4 de agosto de 2017 .{{cite book}}: CS1 maint: location missing publisher (link)
  13. ^ Chakrabarti, CG e Indranil Chakrabarty. "Entropía de Shannon: caracterización axiomática y aplicación". Revista internacional de matemáticas y ciencias matemáticas 2005. 17 (2005): 2847-2854 url ​​Archivado el 5 de octubre de 2021 en Wayback Machine.
  14. ^ Ellerman, David (octubre de 2017). «Teoría de la información lógica: nuevos fundamentos lógicos para la teoría de la información» (PDF) . Logic Journal of the IGPL . 25 (5): 806–835. doi :10.1093/jigpal/jzx022. Archivado (PDF) desde el original el 25 de diciembre de 2022 . Consultado el 2 de noviembre de 2022 .
  15. ^ abc Aczél, J.; Forte, B.; Ng, CT (1974). "Por qué las entropías de Shannon y Hartley son 'naturales'"". Avances en probabilidad aplicada . 6 (1): 131–146. doi :10.2307/1426210. JSTOR  1426210. S2CID  204177762.
  16. ^ Comparar: Boltzmann, Ludwig (1896, 1898). Vorlesungen über Gastheorie: 2 volúmenes - Leipzig 1895/98 UB: O 5262-6. Versión en inglés: Conferencias sobre teoría de los gases. Traducido por Stephen G. Brush (1964) Berkeley: University of California Press; (1995) Nueva York: Dover ISBN 0-486-68455-5 
  17. ^ Życzkowski, Karol (2006). Geometría de estados cuánticos: una introducción al entrelazamiento cuántico . Cambridge University Press. pág. 301.
  18. ^ Sharp, Kim; Matschinsky, Franz (2015). "Traducción del artículo de Ludwig Boltzmann "Sobre la relación entre el segundo teorema fundamental de la teoría mecánica del calor y los cálculos de probabilidad sobre las condiciones de equilibrio térmico"". Entropía . 17 : 1971–2009. doi : 10.3390/e17041971 .
  19. ^ Jaynes, ET (15 de mayo de 1957). "Teoría de la información y mecánica estadística". Physical Review . 106 (4): 620–630. Bibcode :1957PhRv..106..620J. doi :10.1103/PhysRev.106.620. S2CID  17870175.
  20. ^ Landauer, R. (julio de 1961). "Irreversibilidad y generación de calor en el proceso computacional". Revista IBM de Investigación y Desarrollo . 5 (3): 183–191. doi :10.1147/rd.53.0183. ISSN  0018-8646. Archivado desde el original el 15 de diciembre de 2021. Consultado el 15 de diciembre de 2021 .
  21. ^ Mark Nelson (24 de agosto de 2006). «El premio Hutter». Archivado desde el original el 1 de marzo de 2018. Consultado el 27 de noviembre de 2008 .
  22. ^ ab "La capacidad tecnológica mundial para almacenar, comunicar y computar información" Archivado el 27 de julio de 2013 en Wayback Machine , Martin Hilbert y Priscila López (2011), Science , 332(6025); acceso gratuito al artículo a través de aquí: martinhilbert.net/WorldInfoCapacity.html
  23. ^ Spellerberg, Ian F.; Fedor, Peter J. (2003). "Un homenaje a Claude Shannon (1916–2001) y una petición de un uso más riguroso de la riqueza de especies, la diversidad de especies y el índice 'Shannon–Wiener'". Ecología global y biogeografía . 12 (3): 177–179. Bibcode :2003GloEB..12..177S. doi : 10.1046/j.1466-822X.2003.00015.x . ISSN  1466-8238. S2CID  85935463.
  24. ^ Massey, James (1994). "Guessing and Entropy" (PDF) . Proc. IEEE International Symposium on Information Theory . Archivado (PDF) del original el 1 de enero de 2014. Consultado el 31 de diciembre de 2013 .
  25. ^ Malone, David; Sullivan, Wayne (2005). "Las conjeturas no son un sustituto de la entropía" (PDF) . Actas de la Conferencia sobre Tecnología de la Información y Telecomunicaciones . Archivado (PDF) desde el original el 15 de abril de 2016. Consultado el 31 de diciembre de 2013 .
  26. ^ Pliam, John (1999). "Áreas seleccionadas en criptografía". Taller internacional sobre áreas seleccionadas en criptografía . Apuntes de clase en informática. Vol. 1758. págs. 62–77. doi : 10.1007/3-540-46513-8_5 . ISBN . 978-3-540-67185-5.
  27. ^ Índices de variación cualitativa. AR Wilcox - 1967 https://www.osti.gov/servlets/purl/4167340
  28. ^ Klarreich, Erica (1 de octubre de 2015). "Una respuesta mágica a un rompecabezas de 80 años". Quanta Magazine . Consultado el 18 de agosto de 2014 .
  29. ^ Tao, Terence (28 de febrero de 2016). «El problema de la discrepancia de Erdős». Discrete Analysis . arXiv : 1509.05363v6 . doi :10.19086/da.609. S2CID  59361755. Archivado desde el original el 25 de septiembre de 2023. Consultado el 20 de septiembre de 2023 .
  30. ^ Aoki, Nuevos enfoques para el modelado macroeconómico.
  31. ^ Probabilidad y computación, M. Mitzenmacher y E. Upfal, Cambridge University Press
  32. ^ Batra, Mridula; Agrawal, Rashmi (2018). "Análisis comparativo de algoritmos de árboles de decisión". En Panigrahi, Bijaya Ketan; Hoda, MN; Sharma, Vinod; Goel, Shivendra (eds.). Computación inspirada en la naturaleza . Avances en sistemas inteligentes y computación. Vol. 652. Singapur: Springer. págs. 31–36. doi :10.1007/978-981-10-6747-1_4. ISBN 978-981-10-6747-1Archivado desde el original el 19 de diciembre de 2022 . Consultado el 16 de diciembre de 2021 .
  33. ^ Jaynes, Edwin T. (septiembre de 1968). "Prior Probabilities". IEEE Transactions on Systems Science and Cybernetics . 4 (3): 227–241. doi :10.1109/TSSC.1968.300117. ISSN  2168-2887. Archivado desde el original el 16 de diciembre de 2021 . Consultado el 16 de diciembre de 2021 .
  34. ^ Rubinstein, Reuven Y.; Kroese, Dirk P. (9 de marzo de 2013). El método de entropía cruzada: un enfoque unificado para la optimización combinatoria, la simulación de Montecarlo y el aprendizaje automático. Springer Science & Business Media. ISBN 978-1-4757-4321-0.

Este artículo incorpora material de La entropía de Shannon en PlanetMath , que se encuentra bajo la licencia Creative Commons Attribution/Share-Alike License .

Lectura adicional

Libros de texto sobre teoría de la información

Enlaces externos