math - ¿Qué es la "entropía y la ganancia de información"?

text computer-science (7)

Informalmente

La entropía es la disponibilidad de información o conocimiento. La falta de información conlleva dificultades para predecir el futuro, que es una alta entropía (predicción de la siguiente palabra en la minería de textos) y la disponibilidad de información / conocimiento nos ayudará a realizar una predicción más realista del futuro (baja entropía).

La información relevante de cualquier tipo reducirá la entropía y nos ayudará a predecir un futuro más realista, esa información puede ser que la palabra "carne" está presente en la oración o la palabra "carne" no está presente. Esto se llama ganancia de información

Formalmente

La entropía es falta de orden de previsibilidad.

Estoy leyendo este libro ( NLTK ) y es confuso. La entropía se define como :

La entropía es la suma de la probabilidad de cada etiqueta multiplicada por la probabilidad de registro de esa misma etiqueta

¿Cómo puedo aplicar la entropía y la máxima entropía en términos de minería de textos? ¿Puede alguien darme un ejemplo fácil, simple (visual)?

Cuando estaba implementando un algoritmo para calcular la entropía de una imagen, encontré estos enlaces, vea here y here .

Este es el pseudo-código que utilicé, deberá adaptarlo para trabajar con texto en lugar de imágenes, pero los principios deberían ser los mismos.

//Loop over image array elements and count occurrences of each possible //pixel to pixel difference value. Store these values in prob_array for j = 0, ysize-1 do $ for i = 0, xsize-2 do begin diff = array(i+1,j) - array(i,j) if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1 endif endfor //Convert values in prob_array to probabilities and compute entropy n = total(prob_array) entrop = 0 for i = 0, array_size-1 do begin prob_array(i) = prob_array(i)/n //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element //here and divide final sum by Ln(2) if prob_array(i) ne 0 then begin entrop = entrop - prob_array(i)*alog(prob_array(i)) endif endfor entrop = entrop/alog(2)

Obtuve este código de algún lugar, pero no puedo desenterrar el enlace.

Mientras lee un libro sobre NLTK, sería interesante que lea sobre MaxEnt Classifier Module http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

Para la clasificación de minería de texto, los pasos podrían ser: preprocesamiento (tokenización, vaporización, selección de características con Información Ganancia ...), transformación a numérico (frecuencia o TF-IDF) (creo que este es el paso clave para entender cuando se usa texto como entrada a un algoritmo que solo acepta números) y luego clasifique con MaxEnt, seguro que esto es solo un ejemplo.

No puedo darte gráficos, pero quizás pueda darte una explicación clara.

Supongamos que tenemos un canal de información, como una luz que parpadea una vez al día, ya sea roja o verde. ¿Cuánta información transmite? La primera suposición podría ser un poco por día. Pero, ¿y si agregamos azul, para que el remitente tenga tres opciones? Nos gustaría tener una medida de información que pueda manejar cosas distintas a las potencias de dos, pero que aún sea aditiva (la forma en que multiplicar el número de mensajes posibles por dos agrega un bit). Podríamos hacer esto tomando el registro ₂ (número de mensajes posibles), pero resulta que hay una forma más general.

Supongamos que volvemos a rojo / verde, pero la bombilla roja se ha quemado (esto es bien sabido), por lo que la lámpara siempre debe parpadear en verde. El canal ahora es inútil, sabemos cuál será el próximo flash, por lo que los flashes no transmiten información ni noticias. Ahora reparamos la bombilla, pero imponemos una regla de que la bombilla roja puede no parpadear dos veces seguidas. Cuando la lámpara parpadee en rojo, sabemos cuál será el próximo flash. Si intenta enviar un flujo de bits por este canal, encontrará que debe codificarlo con más destellos que bits (de hecho, 50% más). Y si desea describir una secuencia de flashes, puede hacerlo con menos bits. Lo mismo se aplica si cada flash es independiente (libre de contexto), pero los destellos verdes son más comunes que el rojo: cuanto más sesgada sea la probabilidad, menos bits necesitará para describir la secuencia, y menor será la información que contenga, hasta el final. Todo verde, límite de la bombilla quemada.

Resulta que hay una manera de medir la cantidad de información en una señal, en función de las probabilidades de los diferentes símbolos. Si la probabilidad de recibir el símbolo x _i es p _i , entonces considere la cantidad

-log p_i

Cuanto menor sea p _i , mayor será este valor. Si x _i es el doble de improbable, este valor aumenta en una cantidad fija (log (2)). Esto debería recordarle que debe agregar un bit a un mensaje.

Si no sabemos cuál será el símbolo (pero sí las probabilidades), podemos calcular el promedio de este valor, cuánto obtendremos, sumando las diferentes posibilidades:

I = -Σ p_i log(p_i)

Este es el contenido de la información en un flash.

Red bulb burnt out: p_red = 0, p_green=1, I = -(0 + 0) = 0 Red and green equiprobable: p_red = 1/2, p_{green = 1/2}, I = -(2 * 1/2 * log(1/2)) = log(2) Three colors, equiprobable: p_i=1/3, I = -(3 * 1/3 * log(1/3)) = log(3) Green and red, green twice as likely: p_red=1/3, p_green=2/3, I = -(1/3 log(1/3) + 2/3 log(2/3)) = log(3) - 2/3 log(2)

Este es el contenido de información, o entropía, del mensaje. Es máxima cuando los diferentes símbolos son equiprobables. Si eres un físico, utilizas el registro natural, si eres un científico informático, utilizas el registro ₂ y obtienes los bits.

Para empezar, sería mejor entender the measure of information .

¿Cómo `measure` la información?

Cuando sucede algo improbable, decimos que es una gran noticia. Además, cuando decimos algo predecible, no es realmente interesante. Así que para cuantificar esta interesting-ness , la función debe satisfacer

si la probabilidad del evento es 1 (predecible), entonces la función da 0
si la probabilidad del evento es cercana a 0, entonces la función debe dar un número alto
Si los eventos de probabilidad 0.5 ocurren, da one bit de información.

Una medida natural que satisface las restricciones es

I(X) = -log_2(p)

donde p es la probabilidad del evento X Y la unidad está en bit , el mismo bit que usa la computadora. 0 o 1.

Ejemplo 1

Tirón de la moneda justo:

¿Cuánta información podemos obtener de una sola moneda?

Respuesta: -log(p) = -log(1/2) = 1 (bit)

Ejemplo 2

Si un meteorito golpea la Tierra mañana, p=2^{-22} entonces podemos obtener 22 bits de información.

Si el Sol sale mañana, p ~ 1 entonces es 0 bit de información.

Entropía

Entonces, si tomamos la expectativa de la interesting-ness de un evento Y , entonces es la entropía. es decir, la entropía es un valor esperado de lo interesante de un evento.

H(Y) = E[ I(Y)]

Más formalmente, la entropía es el número esperado de bits de un evento.

Ejemplo

Y = 1: un evento X ocurre con probabilidad p

Y = 0: un evento X no ocurre con probabilidad 1-p

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) = - p log p - (1-p) log (1-p)

Base de registro 2 para todos los registros.

Realmente recomiendo que lea sobre teoría de la información, métodos bayesianos y MaxEnt. El lugar para comenzar es este libro (disponible gratuitamente en línea) por David Mackay:

http://www.inference.phy.cam.ac.uk/mackay/itila/

Esos métodos de inferencia son mucho más generales que la minería de texto y realmente no puedo idear cómo se podría aprender cómo aplicar esto a la PNL sin aprender algunos de los conceptos básicos generales contenidos en este libro u otros libros introductorios sobre Aprendizaje automático y Bayesiano MaxEnt. metodos

La conexión entre la entropía y la teoría de la probabilidad con el procesamiento y almacenamiento de la información es realmente profunda. Para darle una idea de ello, existe un teorema de Shannon que dice que la cantidad máxima de información que puede pasar sin errores a través de un canal de comunicación ruidoso es igual a la entropía del proceso de ruido. También hay un teorema que conecta cuánto puede comprimir una parte de los datos para ocupar la memoria mínima posible en su computadora con la entropía del proceso que generó los datos.

No creo que sea realmente necesario que aprendas sobre todos esos teoremas sobre la teoría de la comunicación, pero no es posible aprender esto sin aprender lo básico sobre qué es la entropía, cómo se calcula, qué es la relación con la información y la inferencia, etc. ...

Supongo que la entropía se mencionó en el contexto de la construcción de árboles de decisión .

Para ilustrar, imagine la tarea de learning a classify los nombres de pila en grupos de hombres y mujeres. A eso se le da una lista de nombres, cada uno etiquetado con m o f , queremos aprender un model que se ajuste a los datos y se pueda usar para predecir el género de un nuevo nombre invisible.

name gender ----------------- Now we want to predict Ashley f the gender of "Amro" (my name) Brian m Caroline f David m

El primer paso es deciding qué features de los datos son relevantes para la clase objetivo que queremos predecir. Algunas características de ejemplo incluyen: primera / última letra, longitud, número de vocales, ¿termina con una vocal, etc.? Entonces, después de la extracción de características, nuestros datos se ven así:

# name ends-vowel num-vowels length gender # ------------------------------------------------ Ashley 1 3 6 f Brian 0 2 5 m Caroline 1 4 8 f David 0 2 5 m

El objetivo es construir un árbol de decisión . Un ejemplo de un tree sería:

Básicamente, cada nodo representa una prueba realizada en un solo atributo, y vamos a la izquierda o a la derecha dependiendo del resultado de la prueba. Continuamos recorriendo el árbol hasta que llegamos a un nodo de hoja que contiene la predicción de clase ( m o f )

Entonces, si ejecutamos el nombre Amro en este árbol, comenzamos por probar " ¿la longitud es <7? " Y la respuesta es sí , por lo que bajamos esa rama. Después de la rama, la siguiente prueba " es el número de vocales <3? " Nuevamente se evalúa como verdadero . Esto lleva a un nodo de hoja etiquetado m , y por lo tanto la predicción es masculina (lo que sucede es que el árbol predijo el resultado correctly ).

El árbol de decisiones se construye de manera descendente , pero la pregunta es ¿cómo elige qué atributo dividir en cada nodo? La respuesta es encontrar la función que mejor divide la clase objetivo en los nodos hijos más puros posibles (es decir, nodos que no contienen una mezcla de nodos masculinos y femeninos, sino nodos puros con una sola clase).

Esta medida de pureza se llama information . Representa la cantidad de information expected que se necesitaría para especificar si una nueva instancia (nombre de pila) debería clasificarse como masculina o femenina, dado el ejemplo que llegó al nodo. Lo calculamos en función del número de clases masculinas y femeninas en el nodo.

Entropy otro lado, la Entropy es una medida de impureza (lo opuesto). Se define para una clase binaria con valores a / b como:

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

Esta función de entropía binaria se muestra en la figura a continuación (la variable aleatoria puede tomar uno de dos valores). Alcanza su máximo cuando la probabilidad es p=1/2 , lo que significa que p(X=a)=0.5 o similarmente p(X=b)=0.5 con una probabilidad del 50% / 50% de ser a o b (incertidumbre) está en un máximo). La función de entropía está en el mínimo de cero cuando la probabilidad es p=1 o p=0 con certeza completa ( p(X=a)=1 o p(X=a)=0 respectivamente, este último implica p(X=b)=1 ).

Por supuesto, la definición de entropía se puede generalizar para una variable aleatoria discreta X con N resultados (no solo dos):

(el log en la fórmula generalmente se toma como el logaritmo a la base 2 )

Volviendo a nuestra tarea de clasificación de nombres, veamos un ejemplo. Imagínese en algún momento durante el proceso de construcción del árbol, estábamos considerando la siguiente división:

ends-vowel [9m,5f] <--- the [..,..] notation represents the class / / distribution of instances that reached a node =1 =0 ------- ------- [3m,4f] [6m,1f]

Como puede ver, antes de la división teníamos 9 hombres y 5 mujeres, es decir, P(m)=9/14 y P(f)=5/14 . Según la definición de entropía:

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

A continuación, lo comparamos con la entropía calculada después de considerar la división al observar dos ramas secundarias. En la rama izquierda de ends-vowel=1 de ends-vowel=1 , tenemos:

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

y la rama derecha de ends-vowel=0 de ends-vowel=0 , tenemos:

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

Combinamos las entropías izquierda / derecha utilizando el número de instancias de cada rama como factor de peso (7 instancias fueron a la izquierda y 7 instancias a la derecha) y obtuvimos la entropía final después de la división:

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

Ahora, al comparar la entropía antes y después de la división, obtenemos una medida de la ganancia de información , o la cantidad de información que obtenemos al hacer la división utilizando esa característica particular:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Puede interpretar el cálculo anterior de la siguiente manera: haciendo la división con la característica de end-vowels , pudimos reducir la incertidumbre en el resultado de la predicción del subárbol en una pequeña cantidad de 0.1518 (medida en bits como unidades de información ).

En cada nodo del árbol, este cálculo se realiza para cada característica, y la característica con la mayor ganancia de información se elige para la división de manera greedy (favoreciendo así las características que producen divisiones puras con baja incertidumbre / entropía). Este proceso se aplica recursivamente desde el nodo raíz hacia abajo y se detiene cuando un nodo hoja contiene instancias que tienen la misma clase (no es necesario dividirlo más).

Tenga en cuenta que me salté algunos details que están más allá del alcance de esta publicación, incluyendo cómo manejar las características numéricas , los valores faltantes , el overfitting y pruning árboles de pruning , etc.