Entropía de la información

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de enero de 2020; las comprobaciones requieren 35 ediciones .

La entropía de la información es una medida de la incertidumbre de un determinado sistema (en física estadística o teoría de la información ), en particular, la imprevisibilidad de la aparición de cualquier carácter del alfabeto primario . En este último caso, en ausencia de pérdida de información, la entropía es numéricamente igual a la cantidad de información por símbolo del mensaje transmitido.

Por ejemplo, en una secuencia de letras que forman una oración en ruso, aparecen diferentes letras con diferentes frecuencias , por lo que la incertidumbre de ocurrencia de unas letras es menor que la de otras. Si tenemos en cuenta que algunas combinaciones de letras (en este caso hablan de la entropía de orden -ésimo, ver más abajo ) son muy raras, entonces la incertidumbre disminuye aún más. $norte$

Definiciones formales

La entropía binaria de la información , en ausencia de pérdida de información, se calcula utilizando la fórmula de Hartley :

$i=\log _{2}N$ ,

donde está la potencia del alfabeto, es la cantidad de información en cada símbolo del mensaje. Para una variable aleatoria que toma valores aleatorios independientes con probabilidades ( ), la fórmula de Hartley se convierte en la fórmula de Shannon: $norte$ $i$ $X$ $norte$ $x_{yo}$ $Pi}$ ${\ estilo de visualización i = 1,..., n}$

$H(x)=-\sum_{i=1}^{n}p_{i}\log_{2}p_{i}.$

Esta cantidad también se denomina entropía media del mensaje . La cantidad se llama entropía parcial , que caracteriza solo el estado -e. $H_{i}=-\log _{2}{p_{i))$ $i$

Así, la entropía del sistema es la suma con signo opuesto de todas las frecuencias relativas de ocurrencia del estado (evento) con el número , multiplicado por sus logaritmos binarios [1] . Esta definición para eventos aleatorios discretos puede extenderse formalmente a distribuciones continuas dadas por la distribución de densidad de probabilidad , sin embargo, el funcional resultante tendrá propiedades ligeramente diferentes (ver entropía diferencial ). $X$ $i$

En general, la base del logaritmo en la definición de entropía puede ser mayor que 1 (ya que un alfabeto que consta de un solo carácter no puede transmitir información); la elección de la base del logaritmo determina la unidad de entropía. Para los sistemas de información basados en el sistema numérico binario, la unidad de medida de la entropía de la información (en realidad, información) es un bit . En problemas de estadística matemática, puede ser más conveniente utilizar el logaritmo natural , en cuyo caso la unidad de entropía de la información es nat .

Definición de Shannon

Claude Shannon sugirió que la ganancia de información es igual a la pérdida de incertidumbre y estableció los requisitos para su medición:

la medida debe ser continua; es decir, un cambio en el valor del valor de probabilidad por una cantidad pequeña debería causar un cambio neto pequeño en la función;
en el caso de que todas las opciones (letras en el ejemplo anterior) sean igualmente probables, aumentar el número de opciones (letras) siempre debería aumentar el valor de la función;
debería ser posible hacer una elección (letras en nuestro ejemplo) en dos pasos, en los que el valor de la función del resultado final debería ser la suma de las funciones de los resultados intermedios.[ aclarar ]

Por lo tanto, la función de entropía debe satisfacer las condiciones $H$

$H(p_{1},\;\ldots,\;p_{n})$ es definida y continua para todos , donde para todos y . (Esta función solo depende de la distribución de probabilidad, no del alfabeto). ${\displaystyle p_{1},\dotsc,p_{n))$ $p_{i}\en [0,\;1]$ $i=1,\dotsc,n$ $p_{1}+\dotsb +p_{n}=1$
Para números enteros positivos , se debe cumplir la siguiente desigualdad: $norte$ $H\soporte {\left({\frac {1}{n)),\;\ldots,\;{\frac {1}{n}}\right)}_{n}<H\soporte {\left ({\frac {1}{n+1)),\;\ldots,\;{\frac {1}{n+1}}\right)}_{{n+1}}.$
Para números enteros positivos , donde , la igualdad debe cumplirse $bi}$ $b_{1}+\ldots +b_{k}=n$ $H\underbrace {\left({\frac {1}{n)),\;\ldots,\;{\frac {1}{n))\right)}_{n}=H\left({\ fracción {b_{1}}{n}},\;\ldots,\;{\frac {b_{k}}{n}}\right)+\sum_{{i=1}}^{k} {\frac {b_{i}}{n}}H\soporte {\left({\frac {1}{b_{i}}},\;\ldots,\;{\frac {1}{b_{ i}}}\right)}_{{b_{i}}}.$

Shannon demostró [2] que la única función que satisface estos requisitos es

-K\sum_{{i=1}}^{n}p(i)\log_{2}p(i),

donde es una constante positiva (y realmente solo se necesita para elegir la unidad de entropía; cambiar esta constante es equivalente a cambiar la base del logaritmo). $k$

Shannon determinó que la medida de la entropía ( ) aplicada a una fuente de información puede determinar los requisitos mínimos de ancho de banda requeridos para una transmisión confiable de información en forma de números binarios codificados. Para derivar la fórmula de Shannon, es necesario calcular la expectativa matemática de la "cantidad de información" contenida en la figura de la fuente de información. La medida de la entropía de Shannon expresa la incertidumbre de la realización de una variable aleatoria. Así, la entropía es la diferencia entre la información contenida en un mensaje y la parte de la información que se conoce exactamente (o es altamente predecible) en el mensaje. Un ejemplo de esto es la redundancia del idioma : existen patrones estadísticos claros en la aparición de letras, pares de letras consecutivas, triples, etc. (ver cadenas de Markov ). $H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}$

La definición de la entropía de Shannon está relacionada con el concepto de entropía termodinámica . Boltzmann y Gibbs trabajaron mucho en termodinámica estadística, lo que contribuyó a la aceptación de la palabra "entropía" en la teoría de la información. Existe una conexión entre la termodinámica y la entropía informacional. Por ejemplo, el demonio de Maxwell también contrasta la entropía termodinámica de la información, y ganar cualquier cantidad de información es igual a perder la entropía.

Definición utilizando información propia

También es posible determinar la entropía de una variable aleatoria introduciendo primero el concepto de distribución de una variable aleatoria que tiene un número finito de valores: [3] $X$

P_{X}(x_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots,\;n

\sum_{{i=1}}^{n}p_{i}=1

e información propia :

I(X)=-\log P_{X}(X).

Entonces la entropía se define como:

H(X)=\mathbb {E} (I(X))=-\sum _{i=1}^{n}p(i)\log p(i).

Unidades de entropía de la información

La unidad de medida de la cantidad de información y entropía depende de la base del logaritmo: bit , nat , trit o hartley .

Propiedades

La entropía es una cantidad definida en el contexto de un modelo probabilístico para una fuente de datos . Por ejemplo, lanzar una moneda tiene entropía:

-2\left({\frac {1}{2}}\log _{2}{\frac {1}{2}}\right)=-\log _{2}{\frac {1}{2 }}=\registro _{2}2=1

bits por lanzamiento (suponiendo que sea independiente), y el número de estados posibles es igual a: estados posibles (valores) ("cara" y " cruz ").

2^{1}=2

Para una fuente que genera una cadena que consta solo de las letras "A", la entropía es cero: , y el número de estados posibles es: el estado posible (valor) ("A") y no depende de la base de la logaritmo. Esta es también información que también hay que tener en cuenta. Un ejemplo de dispositivos de memoria que utilizan bits con una entropía igual a cero, pero con una cantidad de información igual a un estado posible , es decir, no igual a cero, son los bits de datos grabados en ROM , en los que cada bit tiene solo un estado posible . estado _ $-\sum_{{i=1}}^{\infty}\log_{2}1=0$ $2^{0}=1$

Así, por ejemplo, se puede establecer empíricamente que la entropía de un texto en inglés es de 1,5 bits por carácter, que variará para diferentes textos. El grado de entropía de la fuente de datos significa el número promedio de bits por elemento de datos necesarios para su cifrado (datos) sin pérdida de información, con una codificación óptima.

Algunos bits de datos pueden no llevar información. Por ejemplo, las estructuras de datos a menudo almacenan información redundante o tienen secciones idénticas independientemente de la información en la estructura de datos.
La cantidad de entropía no siempre se expresa como un número entero de bits.

Propiedades matemáticas

No negatividad : . $H(X)\geqslant 0$
Acotación : , que se deriva de la desigualdad de Jensen para la función cóncava y . Si todos los elementos de son igualmente probables, . $H(X)=-\mahop {\mathbb {E} } (\log _{2}p_{i})=\sum _{i=1}^{n}p_{i}\log _ {2}{\frac {1}{p_{i}}}=\sum_{i=1}^{n}p_{i}f(g_{i})\leqslant f\left(\sum_{ i=1}^{n}p_{i}g_{i}\right)=\log _{2}n$ $f(g_{i})=\log _{2}g_{i}$ $g_{i}={\frac{1}{p_{i}}}$ $norte$ $X$ $H(X)=\log _{2}n$
Si es independiente, entonces . $X,\;Y$ $H(X\cdot Y)=H(X)+H(Y)$
La entropía es una función convexa hacia arriba de la distribución de probabilidad de los elementos.
Si tienen la misma distribución de probabilidad de elementos, entonces . $X,\;Y$ $H(X)=H(Y)$

Eficiencia

El alfabeto puede tener una distribución de probabilidad que está lejos de ser uniforme . Si el alfabeto original contiene caracteres, entonces se puede comparar con un "alfabeto optimizado" cuya distribución de probabilidad es uniforme. La relación de la entropía del alfabeto original y optimizado es la eficiencia del alfabeto original, que se puede expresar como un porcentaje. La eficiencia del alfabeto simbólico original también se puede definir como su entropía -aria. $norte$ $norte$ $norte$

La entropía limita la máxima compresión posible sin pérdidas (o casi sin pérdidas) que se puede realizar utilizando un conjunto teóricamente típico o, en la práctica, la codificación Huffman , la codificación Lempel-Ziv-Welch o la codificación aritmética .

Variaciones y generalizaciones

entropía b -aria

En general, la entropía b - aria (donde b es 2, 3,…) de una fuente con un alfabeto inicial y una distribución de probabilidad discreta donde es una probabilidad ( ) viene dada por: ${\mathcal {S}}=(S,\;P)$ $S=\{a_{1},\;\ldots ,\;a_{n}\}$ $P=\{p_{1},\;\ldots ,\;p_{n}\},$ $Pi}$ $ai}$ $p_{i}=p(a_{i})$

H_{b}({\mathcal {S)))=-\sum_{{i=1}}^{n}p_{i}\log_{b}p_{i}.

En particular, cuando , obtenemos la entropía binaria habitual, medida en bits . Con , obtenemos una entropía trinaria medida en trits (un trit tiene una fuente de información con tres estados equiprobables). Cuando obtenemos información medida en nats . $b=2$ $b=3$ $b=e$

Entropía condicional

Si el orden de los caracteres del alfabeto no es independiente (por ejemplo, en francés, la letra "q" casi siempre va seguida de "u", y después de la palabra "peredovik" en los periódicos soviéticos, la palabra "producción" o generalmente se seguía "trabajo"), la cantidad de información transportada por la secuencia de tales símbolos (y por lo tanto la entropía) es menor. La entropía condicional se utiliza para dar cuenta de tales hechos.

La entropía condicional de primer orden (similar al modelo de Markov de primer orden) es la entropía del alfabeto, donde se conocen las probabilidades de aparición de una letra tras otra (es decir, las probabilidades de combinaciones de dos letras) :

H_{1}({\mathcal {S))=-\sum_{i}p_{i}\sum_{j}p_{i}(j)\log_{2}p_{i}(j ) ,

donde es el estado dependiente del carácter anterior y es la probabilidad dada de que era el carácter anterior. $i$ $p_{i}(j)$ $j$ $i$

Por ejemplo, para el idioma ruso sin la letra "e" [4] . $H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01$

En términos de entropía condicional privada y general, las pérdidas de información se describen completamente durante la transmisión de datos en un canal ruidoso. Para ello se utilizan las denominadas matrices de canales . Para describir la pérdida en el lado de la fuente (es decir, se conoce la señal enviada), considere la probabilidad condicional de recibir un símbolo por parte del receptor , siempre que el símbolo haya sido enviado . En este caso, la matriz del canal tiene la siguiente forma: $p(b_{j}\mid a_{i})$ $b_{j}$ $ai}$

	$b_{1}$	$b_{2}$	…	$b_{j}$	…	$b_{m}$
$un_{1}$	$p(b_{1}\mid a_{1})$	$p(b_{2}\mid a_{1})$	…	$p(b_{j}\mid a_{1})$	…	$p(b_{m}\mid a_{1})$
$un_{2}$	$p(b_{1}\mid a_{2})$	$p(b_{2}\mid a_{2})$	…	$p(b_{j}\mid a_{2})$	…	$p(b_{m}\mid a_{2})$
…	…	…	…	…	…	…
$ai}$	$p(b_{1}\mid a_{i})$	$p(b_{2}\mid a_{i})$	…	$p(b_{j}\mid a_{i})$	…	$p(b_{m}\mid a_{i})$
…	…	…	…	…	…	…
$soy$	$p(b_{1}\mid a_{m})$	$p(b_{2}\mid a_{m})$	…	$p(b_{j}\mid a_{m})$	…	$p(b_{m}\mid a_{m})$

Las probabilidades ubicadas a lo largo de la diagonal describen la probabilidad de recepción correcta, y la suma de todos los elementos de cualquier fila da 1. Las pérdidas por señal transmitida se describen en términos de entropía condicional parcial: $ai}$

H(B\mid a_{i})=-\sum_{{j=1}}^{m}p(b_{j}\mid a_{i})\log_{2}p(b_{j }\mid a_{i}).

Para calcular la pérdida de transmisión de todas las señales, se utiliza la entropía condicional total:

H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i}).

$H(B\mid A)$ significa la entropía del lado de la fuente, la entropía del lado del receptor se considera de manera similar: en cambio , se indica en todas partes (resumiendo los elementos de la cadena, puede obtener , y los elementos de la diagonal significan la probabilidad de que exactamente el carácter que se recibió fue enviado, es decir, la probabilidad de transmisión correcta). $H(A\media B)$ $p(b_{j}\mid a_{i})$ $p(a_{i}\mid b_{j})$ $p(a_{i})$

Entropía mutua

La entropía mutua o entropía de unión está diseñada para calcular la entropía de sistemas interconectados (la entropía de la aparición conjunta de mensajes estadísticamente dependientes) y se denota por , donde caracteriza al transmisor, y - al receptor. $H(AB)$ $A$ $B$

La relación de señales transmitidas y recibidas se describe mediante probabilidades de eventos conjuntos , y solo se requiere una matriz para describir completamente las características del canal: $p(a_{i}b_{j})$

$p(a_{1}b_{1})$	$p(a_{1}b_{2})$	…	$p(a_{1}b_{j})$	…	$p(a_{1}b_{m})$
$p(a_{2}b_{1})$	$p(a_{2}b_{2})$	…	$p(a_{2}b_{j})$	…	$p(a_{2}b_{m})$
…	…	…	…	…	…
$p(a_{i}b_{1})$	$p(a_{i}b_{2})$	…	$p(a_{i}b_{j})$	…	$p(a_{i}b_{m})$
…	…	…	…	…	…
$p(a_{m}b_{1})$	$p(a_{m}b_{2})$	…	$p(a_{m}b_{j})$	…	$p(a_{m}b_{m})$

Para un caso más general, cuando no se describe un canal, sino sistemas que interactúan como un todo, la matriz no tiene que ser cuadrada. La suma de todos los elementos de la columna con el número da , la suma de la fila con el número es , y la suma de todos los elementos de la matriz es 1. La probabilidad conjunta de eventos y se calcula como el producto de la probabilidad inicial y condicional: $j$ $p(b_{j})$ $i$ $p(a_{i})$ $p(a_{i}b_{j})$ $ai}$ $b_{j}$

p(a_{i}b_{j})=p(a_{i})p(b_{j}\mid a_{i})=p(b_{j})p(a_{i}\mid b_{ j}).

Las probabilidades condicionales son producidas por la fórmula de Bayes . Por lo tanto, hay todos los datos para calcular las entropías de la fuente y el receptor:

H(A)=-\sum_{i}\left(\sum_{j}p(a_{i}b_{j})\log \sum_{j}p(a_{i}b_{j} )\Correcto),

H(B)=-\sum_{j}\left(\sum_{i}p(a_{i}b_{j})\log \sum_{i}p(a_{i}b_{j} )\Correcto).

La entropía mutua se calcula sumando filas (o columnas) sucesivas de todas las probabilidades de la matriz multiplicadas por su logaritmo:

H(AB)=-\sum_{i}\sum_{j}p(a_{i}b_{j})\log p(a_{i}b_{j}).

La unidad de medida es bit/dos caracteres, esto se debe a que la entropía mutua describe la incertidumbre para un par de caracteres: enviado y recibido. Por transformaciones simples, también obtenemos

H(AB)=H(A)+H(B\mid A)=H(B)+H(A\mid B).

La entropía mutua tiene la propiedad de completar la información : todas las cantidades consideradas se pueden obtener de ella.

Historia

En 1948, mientras investigaba el problema de la transmisión racional de información a través de un canal de comunicación ruidoso, Claude Shannon propuso un enfoque probabilístico revolucionario para comprender las comunicaciones y creó la primera teoría verdaderamente matemática de la entropía . Sus ideas sensacionales sirvieron rápidamente como base para el desarrollo de dos áreas principales: la teoría de la información , que utiliza el concepto de probabilidad y la teoría ergódica para estudiar las características estadísticas de los sistemas de comunicación y datos, y la teoría de la codificación , que utiliza principalmente herramientas algebraicas y geométricas. desarrollar códigos eficientes.

El concepto de entropía como medida de la aleatoriedad fue introducido por Shannon en su artículo " A Mathematical Theory of Communication " , publicado en dos partes en Bell System Technical Journal en 1948.

Notas

↑ Esta representación es conveniente para trabajar con información presentada en forma binaria; en general, la base del logaritmo puede ser diferente.
↑ Shannon, Claude E. Una teoría matemática de la comunicación (sin especificar) // Bell System Technical Journal. - 1948. - julio ( vol. 27 , n. 3 ). - S. 419 . -doi : 10.1002 / j.1538-7305.1948.tb01338.x .
↑ Gabidulin E. M. , Pilipchuk N. I. Conferencias sobre teoría de la información - MIPT , 2007. - P. 16. - 214 p. — ISBN 978-5-7417-0197-3
↑ Lebedev D.S., Garmash V.A. Sobre la posibilidad de aumentar la velocidad de transmisión de mensajes telegráficos. - M .: Electrosvyaz, 1958. - No. 1. - S. 68-69.

Véase también

Entropía diferencial (entropía para distribución continua)
información mutua
Codificación de entropía
cadena de Markov
Kullback-Leibler distancia

Enlaces

Shannon Claude E. A Mathematical Theory of Communication Archivado el 31 de enero de 1998 en Wayback Machine .
Korotaev S.M. La entropía y la información son conceptos universales de las ciencias naturales .

Literatura

Shannon K. Trabaja en teoría de la información y cibernética. - M. : Ed. extranjero iluminado, 2002.
Volkenshtein M. V. Entropía e información. — M .: Nauka, 2006.
Tsymbal VP Teoría de la información y codificación. - K. : Escuela Vishcha, 2003.
Martin, Nathaniel FG & England, James W. Teoría matemática de la entropía. - Prensa de la Universidad de Cambridge, 2011. - ISBN 978-0-521-17738-2 .
Shambadal P. Desarrollo y aplicación del concepto de entropía. — M .: Nauka, 1967. — 280 p.
Martin N., England J. Teoría matemática de la entropía. — M .: Mir, 1988. — 350 p.
Khinchin A. Ya. El concepto de entropía en la teoría de la probabilidad // Avances en Ciencias Matemáticas . - Academia Rusa de Ciencias , 1953. - V. 8 , no. 3(55) . - S. 3-20 . (Ruso)
Brulluen L. Teoría de la ciencia y la información. - M. , 1960.
Viner N. Cibernética y sociedad. - M. , 1958.
Wiener N. Cibernética o Control y Comunicación en Animal y Máquina. - M. , 1968.
Petrushenko L. A. Automovimiento de la materia a la luz de la cibernética. - M. , 1974.
Ashby W. R. Introducción a la cibernética. - M. , 1965.
Yaglom A.M. , Yaglom I.M. Probabilidad e información. - M. , 1973.
Volkenshtein M. V. Entropía e información. - M. : Nauka, 1986. - 192 p.
Vereshchagin N.K., Shchepin E.V. Información, codificación y predicción. - M. : FMOP, MTsNMO, 2012. - 238 p. - ISBN 978-5-94057-920-5 .

diccionarios y enciclopedias

En catálogos bibliográficos
BNE : XX535116 BNF : 11985913j TIERRA : 4743861-7 J9U : 987007550784405171 LCCN : sh85044152 NDL : 01191172 NKC : ph425914