¿Cuál es el papel del logaritmo en la entropía de Shannon?

72

La entropía de Shannon es el negativo de la suma de las probabilidades de cada resultado multiplicado por el logaritmo de probabilidades para cada resultado. ¿Para qué sirve el logaritmo en esta ecuación?

¡Una respuesta intuitiva o visual (a diferencia de una respuesta profundamente matemática) recibirá puntos extra!

entropy intuition sequence-analysis Histelheim
fuente

11

Usted (u otros lectores) pueden disfrutar: A. Renyi (1961), Sobre medidas de entropía e información , Proc. del Cuarto Simposio de Berkeley sobre Estadística matemática y probabilidad , vol. 1, 547-561.

cardenal

Según su reacción , supongo que lo que quiere decir es por qué Shannon usó el logaritmo en su fórmula, ¿verdad?

Ooker

@Ooker: Esa es una forma de expresarlo. "¿Por qué" lo puso? "¿Qué" es su función o función "?" ¿Qué "logra?" ¿Cómo "es útil? Para mí, todos están en el mismo vecindario ..."

histelheim

Mira mi respuesta aquí: stats.stackexchange.com/questions/66186/…

kjetil b halvorsen

Véase mi respuesta, creo que el significado de un registro realmente sólo puede entenderse mediante el examen de las raíces de la entropía de Shannon en la mecánica estadística

Aksakal

51

La entropía de Shannon es una cantidad que satisface un conjunto de relaciones.

En resumen, el logaritmo es hacer que crezca linealmente con el tamaño del sistema y "comportarse como información".

El primero significa que la entropía de lanzar una moneda $n$ veces es $n$ veces la entropía de lanzar una moneda:

- \sum_{i = 1}^{2^{n}} \frac{1}{2^{n}} \log (\frac{1}{2^{n}}) = - \sum_{i = 1}^{2^{n}} \frac{1}{2^{n}} n \log (\frac{1}{2}) = n (- \sum_{i = 1}^{2} \frac{1}{2} \log (\frac{1}{2})) = n .

$- \sum_{i=1}^{2^n} \frac{1}{2^n} \log\left(\tfrac{1}{2^n}\right) = - \sum_{i=1}^{2^n} \frac{1}{2^n} n \log\left(\tfrac{1}{2}\right) = n \left( - \sum_{i=1}^{2} \frac{1}{2} \log\left(\tfrac{1}{2}\right) \right) = n.$

O simplemente para ver cómo funciona cuando se lanzan dos monedas diferentes (tal vez injusto - con caras con probabilidad $p_1$ y colas $p_2$ para la primera moneda, y $q_1$ y $q_2$ para la segunda)

- \sum_{i = 1}^{2} \sum_{j = 1}^{2} p_{i} q_{j} \log (p_{i} q_{j}) = - \sum_{i = 1}^{2} \sum_{j = 1}^{2} p_{i} q_{j} (\log (p_{i}) + \log (q_{j}))

$-\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(p_i q_j) = -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \left( \log(p_i) + \log(q_j) \right)$

= - \sum_{i = 1}^{2} \sum_{j = 1}^{2} p_{i} q_{j} \log (p_{i}) - \sum_{i = 1}^{2} \sum_{j = 1}^{2} p_{i} q_{j} \log (q_{j}) = - \sum_{i = 1}^{2} p_{i} \log (p_{i}) - \sum_{j = 1}^{2} q_{j} \log (q_{j})

$= -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(p_i) -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(q_j) = -\sum_{i=1}^2 p_i \log(p_i) - \sum_{j=1}^2 q_j \log(q_j)$ por lo que las propiedades dellogaritmo(logaritmo del producto es la suma de logaritmos) son cruciales.

Pero también la entropía de Rényi tiene esta propiedad (es la entropía parametrizada por un número real $\alpha$ , que se convierte en entropía de Shannon para $\alpha \to 1$ ).

Sin embargo, aquí viene la segunda propiedad: la entropía de Shannon es especial, ya que está relacionada con la información. Para tener una sensación intuitiva, puede mirar

H = \sum_{i} p_{i} \log (\frac{1}{p_{i}})

$H = \sum_i p_i \log \left(\tfrac{1}{p_i} \right)$ como el promedio de

\log (1 / p)

$\log(1/p)$ .

Podemos llamar a la información de $\log(1/p)$ . ¿Por qué? Porque si todos los eventos ocurren con probabilidad $p$ , significa que hay eventos $1/p$ . Para saber qué evento ha sucedido, necesitamos usar bits de $\log(1/p)$ (cada bit duplica la cantidad de eventos que podemos distinguir).

Puede sentirse ansioso "OK, si todos los eventos tienen la misma probabilidad, tiene sentido usar $\log(1/p)$ como una medida de información. Pero si no lo son, ¿por qué promediar información tiene sentido?" - Y es una preocupación natural.

Pero resulta que tiene sentido - fuente de Shannon teorema de codificación dice que una cadena con las letras uncorrelted con probabilidades $\{p_i\}_i$ de longitud $n$ no puede comprimirse (en promedio) a cadena binaria más corto que $n H$ . Y de hecho, podemos utilizar la codificación de Huffman para comprimir la cadena y llegar muy cerca de $n H$ .

Ver también:

Una buena introducción es la entrada de la teoría de la información de Cosma Shalizi
¿Qué es realmente la entropía? - MathOverflow
Diseccionando el formato GZIP

Piotr Migdal
fuente

11

Esta respuesta tiene muchos detalles agradables, pero desde la perspectiva de un laico aún evita el problema: ¿cuál es el papel del logaritmo? ¿Por qué no podemos calcular la entropía sin el logaritmo?

histelheim

66

@histelheim ¿Qué quieres decir con "sin el logaritmo"?

es solo uno. Si desea otra medida de diversidad sin

, observe los índices de diversidad , por ejemplo, el denominado índice de Simpson inverso

que indica el número efectivo de opciones (una probabilidad por encima del promedio), hay un índice de Gini-Simpson

\sum_{i} p_{i}

$\sum_i p_i$

\log

$\log$

1 / \sum_{i} p_{i}^{2}

$1/\sum_i p_i^2$

1 - \sum_{i} p_{i}^{2}

$1-\sum_i p_i^2$ que siempre está entre 0 y uno. Y si no le interesan las propiedades sutiles relacionadas con la información de la entropía de Shannon, puede usar cualquiera de ellas (sin embargo, tienen diferentes probabilidades de bajo y alto).

Piotr Migdal

10

Me desconcierta su último comentario, Histelheim: ¿a qué podría referirse "entropía sin el logaritmo"? Eso sugiere que aún no ha articulado claramente su pregunta, porque parece que tiene en mente un concepto no declarado de "entropía". No nos haga adivinar: edite su pregunta para que sus lectores puedan proporcionar el tipo de respuestas que está buscando.

whuber

1

@ Piotr Migdal: escribe "el logaritmo es hacer que crezca linealmente con el tamaño del sistema y" comportarse como la información "". - Esto me parece crucial para comprender el papel del logaritmo, sin embargo, no tengo muy claro qué significa.

histelheim

1

@ Piotr Migdal: además, su explicación después de "Podemos llamar a la información de registro (1 / p). ¿Por qué?" Parece tener sentido para mi. Es que el logaritmo esencialmente nos mueve de un índice de diversidad a un índice de información, midiendo el número de bits que necesitamos para distinguir los eventos.

histelheim

25

Esto es lo mismo que las otras respuestas, pero creo que la mejor manera de explicarlo es ver lo que dice Shannon en su artículo original.

La medida logarítmica es más conveniente por varias razones:

Es prácticamente más útil. Los parámetros de importancia de ingeniería, como el tiempo, el ancho de banda, el número de relés, etc., tienden a variar linealmente con el logaritmo del número de posibilidades. Por ejemplo, agregar un relé a un grupo duplica el número de estados posibles de los relés. Agrega 1 al logaritmo de base 2 de este número. Duplicar el tiempo ajusta al cuadrado el número de mensajes posibles, o duplica el logaritmo, etc.

Está más cerca de nuestro sentimiento intuitivo en cuanto a la medida adecuada. Esto está estrechamente relacionado con (1) ya que intuitivamente mide entidades por comparación lineal con estándares comunes. Uno siente, por ejemplo, que dos tarjetas perforadas deben tener el doble de capacidad que una para almacenar información, y dos canales idénticos dos veces la capacidad de una para transmitir información.

Es matemáticamente más adecuado. Muchas de las operaciones limitantes son simples en términos del logaritmo, pero requerirían una reformulación torpe en términos del número de posibilidades.

Fuente: Shannon, A Mathematical Theory of Communication (1948) [ pdf ].

$\Omega$ $\log \Omega$ $\Omega$ $\Omega$ $\log \Omega$

Flounderer
fuente

Esta respuesta parece ser la más enfocada pero informativa.

estrella brillante

1

No es por eso que el registro aparece en el cálculo de entropía. Es por eso que la información reportada se reporta como tal. Hay una cantidad alternativa: la "perplejidad" que informa la información sin el registro. En esta parte de su artículo, Shannon está argumentando a favor de bits / nats / hartleys, y en contra de la perplejidad.

Neil G

15

$x$ $1 \leq x \leq N$ $x$ $O(\log_2N)$ $x$ $N=8$ $x$ .

$x$ $1 \leq x \leq N$ $p(x) = 1/N$ $1 \leq x \leq N$ $x$

h (x) = \log_{2} \frac{1}{p (x)}

$\begin{equation} h(x) = \log_2 \frac{1}{p(x)} \end{equation}$

$x=4$ $h(4) = 3$ $x$ $4$ $x=4$

$x$ $x$ $h(x)$ $x$

⟨ h (x) ⟩ = \sum_{1 \leq x \leq N} p (x) h (x)

$\begin{equation} \langle h(x) \rangle = \sum_{1 \leq x \leq N} p(x) h(x) \end{equation}$

$\langle h(x) \rangle$ $H(X)$ $H(X)$

omidi
fuente

1

+ Esta es una de mis aplicaciones favoritas de la teoría de la información: el análisis de algoritmos. Si tiene puntos de decisión con> 2 resultados, como cuando indexa una matriz, ese es el principio detrás de la codificación hash y el tipo O (n).

Mike Dunlavey

Este argumento está bien para la entropía discreta, pero no se generaliza fácilmente a la entropía continua.

Neil G

12

Aquí hay una explicación extravagante. Se podría decir que 2 libros del mismo tamaño tienen el doble de información que 1 libro, ¿verdad? (Considerando que un libro es una cadena de bits). Bueno, si cierto resultado tiene probabilidad P, entonces se podría decir que su contenido de información es sobre el número de bits que necesita para escribir 1 / P. (por ejemplo, si P = 1/256, son 8 bits). La entropía es solo el promedio de la longitud de ese bit de información, sobre todos los resultados.

Mike Dunlavey
fuente

5

$\log(p_i)$ $\log(p_i)$ $H(p_1, \ldots ,p_N)$

Shannon proporcionó una prueba matemática de este resultado que ha sido cuidadosamente seleccionada y ampliamente aceptada. El propósito y la importancia del logaritmo en la ecuación de entropía son, por lo tanto, independientes de los supuestos y la prueba.

Esto no lo hace fácil de entender, pero en última instancia es la razón por la que aparece el logaritmo.

He encontrado útiles las siguientes referencias además de las enumeradas en otros lugares:

Teoría de la probabilidad: la lógica de la ciencia por ET Jaynes . Jaynes es uno de los pocos autores que obtiene muchos resultados desde cero; ver Capítulo 11.
Teoría de la información, inferencia y algoritmos de aprendizaje por David MacKay. Contiene un análisis en profundidad del teorema de codificación de fuente de Shannon; ver Capítulo 4.

usuario119961
fuente

4

Resumen:

$n$ $n$

Ejemplo:

$6$ $6$ $1$ $n=2$ $1$

$3.5$ $6/2=3$

$1$

Hagámoslo:

$6$ $> 3.5$
$6/2=3$ $\ge 5$
$6/2/2=1.5$ $= 6$

$6$ $3$ $ceil(\log_2(6)) = ceil(2.58) = 3$

$ceil$

$2.58$

$\log_2(...)$ $n$ $n$ $2$ $\log_n(...)$

Simulación:

import random

total_questions = 0
TOTAL_ROUNDS = 10000

for i in range(0,TOTAL_ROUNDS):
    outcome = random.randrange(1,7)
    total_questions += 1
    if outcome > 3.5:
        total_questions += 1
        if outcome >= 5:
            total_questions += 1
            if outcome == 5:
                pass
            else:
                # must be 6! no need to ask
                pass
        else:
            # must be 4! no need to ask
            pass
    else:
        total_questions += 1
        if outcome >= 2:
            total_questions += 1
            if outcome == 2:
                pass
            else:
                # must be 3! no need to ask
                pass
        else:
            # must be 1! no need to ask
            pass


print 'total questions: ' + str(total_questions)
print 'average questions per outcome: ' + str(total_questions/float(TOTAL_ROUNDS))

Resultados:

total questions: 26634
average questions per outcome: 2.6634

$2.6634 \ne \log_2(6) \ne 2.58$

Que pasa Está casi cerca, pero no tan cerca como esperaba. ¿Es el PRNG de Python tratando de decir una broma lenta? ¿O se equivoca Shannon? ¿O es, Dios no lo quiera, mi comprensión es incorrecta? De cualquier manera AYUDA. SOS ya amigo.

cavernícola
fuente

2

6^{5} = 7776

$6^5=7776$

⌈ \log_{2} (6^{5}) ⌉ = 13

$\lceil\log_2(6^5)\rceil=13$

13 / 5 = 2.6

$13/5=2.6$

190537

$190537$

492531

$492531$

492531 / 190537 \approx 2.584962500722

$492531/190537\approx 2.584962500722$

@whuber, ¿no es esto lo que estoy haciendo en mi código? Lanzo 10000 dados y sumo el número total de preguntas que hago para todos los dados. Luego hago suma / 10000 obtengo 2.66.

hombre de las cavernas

1

¡No, no estás haciendo eso en tu código en absoluto! Necesitas hacer un conjunto de preguntas diseñadas para obtener simultáneamente el estado de todos los dados a la vez. Eso no es lo mismo que el número promedio de preguntas necesarias para encontrar el estado de un dado a la vez.

whuber

3

$\Omega = \{\omega_1, \dotsc, \omega_n\}$ $p_1, \dotsc, p_n$ $H(p_1, \dotsc, p_n)$

$H$
$H$ $n$ $p_1 = \dots = p_n = \frac1n$
$H$ $\begin{aligned} H (\frac{1}{2}, \frac{1}{6}, \frac{1}{3}) & = H (\frac{1}{2}, \frac{1}{2}) + \frac{1}{2} H (\frac{1}{3}, \frac{2}{3}) . \end{aligned}$ $\begin{align} H\left(\frac12, \frac16, \frac13\right) &= H\left(\frac12, \frac12\right) + \frac12 H\left(\frac13, \frac23\right). \end{align}$

$H$

\begin{aligned} H (p_{1}, \dots, p_{n}) & = - \sum_{i = 1}^{n} p_{i} \log_{k} p_{i} \end{aligned}

$\begin{align} H(p_1, \dotsc, p_n) &= -\sum_{i=1}^np_i\log_kp_i \end{align}$

k > 1

$k>1$

k = 2

$k=2$

Neil G
fuente

3

Esta pregunta se planteó hace dos años y ya ha habido muchas respuestas increíbles, pero me gustaría agregar la mía que me ayudó mucho.

La pregunta es

¿Para qué sirve el logaritmo en esta ecuación?

El logaritmo (generalmente basado en 2) se debe a la desigualdad de Kraft .

$\sum_{i=1}^m 2^{-l_i} <= 1$

$l_i$ $L_x$ $P(x)$

$P(x) = 2^{-L(x)}$

$L_{(x)} = -logP(x)$ $P(x)$ $L_{(x)}$

$L_{(x)}$ $P(x)$ $-P(x)logP(x)$

Una ilustración intuitiva y una respuesta visual (como lo requirió, pero más específicamente para la desigualdad de Kraft) se articula en este árbol de código de papel y la desigualdad de Kraft .

Lerner Zhang
fuente

1

Según su no aceptación de las respuestas ya existentes, creo que lo que está buscando es la razón por la cual Shannon usó el logaritmo en su fórmula en primer lugar. En otras palabras, la filosofía de la misma.

_{Descargo de responsabilidad : estoy en este campo durante una semana, viniendo aquí por tener la pregunta como tú . Si tiene más conocimiento sobre esto, hágamelo saber.}

Tengo esta pregunta después de leer uno de los artículos más importantes de Ulanowicz, Incremento de la entropía: ¿muerte por calor o armonías perpetuas? . Este es el párrafo que explica por qué la fórmula tiene -log (p) en lugar de (1-p):

Antes de desempaquetar más la definición formal de entropía, uno estaría justificado al preguntar por qué no simplemente elegir (1 - p) en lugar de [–log (p)] como la medida más apropiada de inexistencia. La respuesta es que el producto resultante con p (es decir [p – p ^ 2]) es perfectamente simétrico alrededor del valor p = 0.5. Los cálculos de conformidad con dicha combinación simétrica serían capaces de describir solo un universo reversible. Boltzmann y Gibbs, sin embargo, buscaban cuantificar un universo irreversible. Al elegir la función logarítmica convexa univariada, Boltzmann impartió un sesgo al no ser sobre el ser. Uno nota, por ejemplo, que max [–xlog {x}] = {1 / e} ≈ 0.37, de modo que la medida de indeterminación se sesga hacia valores más bajos de pi.

Parece que Shannon eligió el logaritmo sin ninguna razón. Simplemente "olió" que debería usar el logaritmo. ¿Por qué Newton eligió la operación de multiplicación en su fórmula F = m * a?

Tenga en cuenta que en ese momento, no tenía idea sobre la entropía :

Mi mayor preocupación era cómo llamarlo. Pensé en llamarlo 'información', pero la palabra se usó demasiado, así que decidí llamarlo 'incertidumbre'. Cuando lo discutí con John von Neumann, tuvo una idea mejor. Von Neumann me dijo: 'Deberías llamarlo entropía, por dos razones. En primer lugar, su función de incertidumbre se ha utilizado en mecánica estadística con ese nombre, por lo que ya tiene un nombre. En segundo lugar, y más importante, nadie sabe qué es realmente la entropía, por lo que en un debate siempre tendrá la ventaja.

Entonces mi respuesta es: no hay razón para esto. Él eligió esto porque simplemente funcionó mágicamente.

Ooker
fuente

0

La entropía se define como el logaritmo de la media geométrica del coeficiente multinomial que expresa el número de estados en los que puede estar un sistema:

\log \sqrt[N]{(\binom{N}{n_{1}, \dots, n_{k}})}

$\log \sqrt[N]{N \choose n_1,\ldots,n_k}$

Los logaritmos aparecen en la fórmula después de usar la aproximación de Stirling del factorial (vea esta explicación )

Atamiri
fuente

3

Creo que el OP sabe que el logaritmo es parte de la definición. Preguntan por qué está ahí?

whuber

0

El registro proviene de la derivación de una función H que satisface ciertos requisitos naturales. Ver pág. 3 seg. 2 de esta fuente:

http://www.lptl.jussieu.fr/user/lesne/MSCS-entropy.pdf

Dados los axiomas, si llevas a cabo la optimización, obtienes una función única (hasta constantes) con un registro en ella.

Todas las respuestas anteriores son correctas, excepto que interpretan el registro, pero no explican la fuente del mismo.

Swapnil Bhatia
fuente

0

Supongo que su pregunta es más sobre el "significado" de ese logaritmo y por qué cada componente contribuye al significado general de la fórmula, en lugar del mero formalismo que muestra la coherencia de la definición a ciertos requisitos.

$p(x)$ $-log(p(x))$

$p(x)$
$-log(p(x))$

$p(x)$ $-log(p(x))$

De ahora en adelante, discutiré cómo la GENERALIDAD afecta la fórmula de entropía final.

l o g_{2} (x) = n u m b e r_o f_b i t s_t o_e n c o d e_t h e_m e s s a g e s

$log_2(x) = number\_of\_bits\_to\_encode\_the\_messages$

Ahora, siéntese, relájese y observe cuán bellamente funciona la Entropía de Shannon: se basa en la suposición (razonable) de que los mensajes que son más GENERALES son, en consecuencia, más FRECUENTES.

Por ejemplo, diré que está lloviendo si es una lluvia promedio, fuerte o muy fuerte. Por lo tanto, propuso codificar la GENERALIDAD de los mensajes en función de cuán FRECUENTES son ... y ahí está:

l o g_{2} N = - l o g_{2} 1 / N = - l o g_{2} P

$log_2 N = -log_2 1/N = -log_2 P$

$N$ $x$

La ecuación se puede interpretar como: los mensajes raros tendrán una codificación más larga porque son menos generales, por lo que necesitan más bits para codificarse y son menos informativos. Por lo tanto, tener mensajes más específicos y raros contribuirá más a la entropía que tener muchos mensajes generales y frecuentes.

$p(x)$ $-log(p(x))$

La mayor entropía es cuando tenemos un sistema con muchos mensajes raros y específicos. La entropía más baja con mensajes frecuentes y generales. En el medio, tenemos un espectro de sistemas equivalentes de entropía que pueden tener mensajes raros y generales o mensajes frecuentes pero específicos.

Gabrer
fuente

0

No creo que sea posible darle una respuesta universal "intuitiva". Le daré una respuesta intuitiva para algunas personas, como los físicos. El logaritmo está ahí para obtener la energía promedio del sistema. Aquí hay detalles.

Shannon usó una palabra " entropía " porque adaptó el concepto de la mecánica estadística . En mecánica estadística hay una distribución seminal que lleva el nombre de Boltzmann. Curiosamente, ¡es una distribución importante ahora en el aprendizaje automático!

P = e^{\frac{a - E}{b}}

$P=e^{\frac{a-E} b}$

a, b

$a, b$

E

$E$

d V

$dV$

V

$V$

d V = d p d x

$dV=dpdx$

x, p

$x,p$

a, b

$a,b$

\int_{V} P d V = 1

$\int_VPdV=1$

b

$b$ corresponde a una temperatura del sistema.

$\ln P\sim E$

S \equiv - \int_{V} P \ln P d V =< E >

$S\equiv -\int_VP\ln P dV=<E>$

η = - \sum_{i} P_{i} \ln P_{i}

$\eta=-\sum_i P_i\ln P_i$

e^{- P_{i}}

$e^{-P_i}$

¿Es esto lo suficientemente intuitivo para ti? Es para mí, pero fui un físico teórico en vidas pasadas. Además, puede llegar a un nivel más profundo de intuición al vincular conceptos de termodinámica aún más antiguos, como la temperatura y los trabajos de Boltzmann y Clausius.

Aksakal
fuente

¿Cuál es el papel del logaritmo en la entropía de Shannon?

Respuestas:

Resumen:

Ejemplo:

Simulación: