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

https://stackoverflow.com/questions/1859554

13-09-2019
|

Pregunta

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

La entropía es la suma de la probabilidad de cada etiqueta veces el registro de la probabilidad de que la misma etiqueta

¿Cómo puedo aplicar la entropía y la máxima entropía en términos de minería de texto?Alguien puede darme una fácil y simple ejemplo (visual)?

Solución

Asumo la entropía se menciona en el contexto de la construcción de árboles de decisión .

Para ilustrar, imaginar la tarea de href="https://en.wikipedia.org/wiki/Supervised_learning" aprender a clasificar primeros nombres en / grupos femeninos masculinos. Eso se da una lista de los nombres de cada una etiquetada con cualquiera m o f, queremos aprender un que se ajuste a los datos y se puede utilizar para predecir el sexo de un nuevo nombre de pila no se ve.

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 decidir lo características de los datos son relevantes para la clase de destino queremos predecir. Algunas de las características de ejemplo son: primera / última carta, longitud, número de vocales, no se termina con una vocal, etc .. Así que después de la extracción de características, nuestros datos se ve 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 una árbol de decisión . Un ejemplo de un árbol sería:

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

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

Así que si corremos el nombre de Amro este árbol, que empezar por probar " es la longitud <7? " y la respuesta es Sí , por lo que bajan de esa rama. A raíz de la rama, la próxima prueba " es el número de vocales <3? " de nuevo se evalúa como true . Esto conduce a una marcada m nodo hoja, y por lo tanto la predicción es hombre (que da la casualidad que, por lo que el árbol predicho el resultado correctamente ).

El árbol de decisión es href="https://en.wikipedia.org/wiki/ID3_algorithm" construido de una manera de arriba hacia abajo, pero la pregunta es cómo hacer elegir qué atributo se divida en cada nodo? La respuesta es encontrar la función que mejor se divide la clase de destino en las más puras posibles nodos hijos (es decir: los nodos que no contienen una mezcla de ambos hombres y mujeres, los nodos más puros con una sola clase).

Esta medida de pureza se llama el información . Representa la rel="noreferrer"> de información que se necesitarían para especificar si una nueva instancia (nombre de pila) debe clasificarse hombre o mujer, dado el ejemplo que alcanzó el nodo. Lo calculamos basado en el número de clases masculinos y femeninos en el nodo.

Entropía por el contrario es una medida de impureza (lo contrario). Se define para un clase binario con valores a / b como:

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

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

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

entropía

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

Volver a nuestra tarea de clasificación de nombre, veamos un ejemplo. Imagínese en algún momento durante el proceso de construcción del árbol, estábamos teniendo en cuenta 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 se 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. De acuerdo con la definición de la entropía:

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

A continuación comparamos con la entropía calculada después de considerar la división examinado dos ramas secundarias. En la rama izquierda 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, 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 casos por cada rama como factor de peso (7 casos fue hacia la izquierda, y 7 casos fue a la derecha), y obtener la entropía final después de la escisión:

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

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

Information_Gain = Entropy_before - Entropy_after = 0.1518

Se puede interpretar el cálculo anterior de la siguiente manera: haciendo de la ruptura con la característica end-vowels, hemos sido capaces de reducir la incertidumbre en el resultado de predicción de sub-árbol por una pequeña cantidad de 0,1518 (medido en bits de como unidades de información ).

En cada nodo del árbol, este cálculo se realiza para cada función, y la función con el mayor ganancia de información se elige para la división en un manera codicioso (características favoreciendo así que producen puro divide con baja incertidumbre / entropía). Este proceso se aplica de forma recursiva de la raíz-nodo hacia abajo, y se detiene cuando un nodo hoja contiene todas las instancias que tienen la misma clase (sin necesidad de dividir aún más).

Tenga en cuenta que me he saltado sobre algunos detalles cuales están más allá del alcance de este post, incluyendo cómo manejar , los valores que faltan , sobreajuste y < a href = "https://en.wikipedia.org/wiki/Pruning_%28decision_trees%29" rel = "noreferrer"> poda de árboles , etc ..

Otros consejos

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

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

Cuando sucede algo poco probable, decimos que es una gran noticia. Además, cuando decimos que algo predecible, no es realmente interesante. Así que para cuantificar este 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 está cerca de 0, entonces la función debe dar número alto
si probabilidad 0,5 eventos ocurre que dan one bit de información.

Una medida natural que satisface las restricciones es

I(X) = -log_2(p)

donde p es la probabilidad de que el X evento. Y la unidad está en bit, el mismo equipo bits utiliza. 0 o 1.

Ejemplo 1

Feria cara o cruz:

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

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

Ejemplo 2

Si un meteoro 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.

Entropy

Así que si tenemos la expectativa sobre la interesting-ness de un Y caso, entonces es la entropía. es decir, la entropía es un valor esperado de la interesante-dad 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 se produce con una probabilidad de p

Y = 0: un evento X no se produce con una probabilidad de 1-p

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

logaritmo en base 2 para todos log.

No puedo dar a los gráficos, pero tal vez pueda dar una explicación clara.

Supongamos que tenemos un canal de información, tal como una luz que parpadea una vez al día, ya sea rojo o verde. ¿Cuánta información se transmite? La primera suposición podría ser un bit por día. Pero lo que si sumamos azul, por lo que el remitente tiene tres opciones? Nos gustaría tener una medida de información que puede manejar las cosas que no sean potencias de dos, pero aún así ser aditivos (la forma en que multiplicar el número de posibles mensajes por dos añade un bit). Podríamos hacer esto mediante la adopción de registro ₂ (número de posibles mensajes), pero resulta que hay una manera más general.

Supongamos que estamos de vuelta a rojo / verde, pero la bombilla roja se ha quemado (esto es de conocimiento común) para que la lámpara siempre debe parpadear en verde. El canal está ahora inútil, sabemos cuál será el siguiente relámpago por lo que los destellos transmiten ninguna información, no hay noticias. Ahora reparamos la bombilla, pero imponer una regla de que la bombilla roja no parpadea dos veces seguidas. Cuando la lámpara parpadea en rojo, sabemos lo que será la próxima flash. Si intenta enviar un flujo de bits por este canal, usted encontrará que es necesario codificarla con más destellos de lo que tiene bits (un 50% más, de hecho). Y si se quiere describir una secuencia de destellos, puede hacerlo con menos bits. Lo mismo se aplica si cada destello es independiente (independiente del contexto), pero verde parpadea son más comunes de lo rojo: la más sesgada la probabilidad de los menos bits que necesita para describir la secuencia, y cuanto menos información que contiene, todo el camino a la totalmente verde, bombilla fundida límite.

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 símbolo x _i es p _i, y luego considerar la cantidad

-log p_i

El p menor _i, el más grande de este valor. Si x _i convierte el doble de poco probable, este valor aumenta por una cantidad fija (log (2)). Esto se debe recordar a la adición de un bit de un mensaje.

Si no sabemos cuál será el símbolo (pero sabemos que las probabilidades), entonces podemos calcular la media de este valor, cuánto vamos a conseguir, mediante la suma de 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 la información, o entropía, del mensaje. Es máxima cuando los diferentes símbolos son equiprobables. Si usted es un físico que utiliza el logaritmo natural, si usted es un científico de la computación se utiliza de registro ₂ y obtener trozos.

Realmente recomiendo que lea sobre Teoría de la Información, los métodos bayesianos y MaxEnt. El punto de partida es este libro (en línea de libre acceso) por David Mackay:

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

Los métodos de inferencia son realmente mucho más general que sólo la minería de texto y realmente no puedo concebir cómo se podría aprender cómo aplicar esto a la PNL sin tener que aprender algunos de los fundamentos generales contenidas en este libro u otros libros de introducción de la máquina de aprendizaje y métodos bayesianos MAXENT.

La conexión entre la entropía y la teoría de la probabilidad de procesamiento de la información y el almacenamiento es muy, muy profundo. Para dar una idea de ella, hay un teorema de Shannon, debido a que indica que la máxima cantidad de información que puede pasar sin error a través de un canal de comunicación ruidosa es igual a la entropía del proceso de ruido. También hay un teorema que se conecta cuánto puede comprimir una pieza de datos para ocupar la memoria mínima posible en el ordenador a la entropía del proceso que genera los datos.

No creo que sea realmente necesario que vaya aprendiendo sobre todos aquellos teoremas sobre teoría de la comunicación, pero no es posible aprender esto sin tener que aprender los conceptos básicos acerca de lo que es la entropía, cómo se calcula, ¿cuál es su relación con la información y inferencia, etc ...

Cuando yo estaba aplicando un algoritmo para calcular la entropía de una imagen que encontré estos enlaces, consulte aquí y aquí .

Este es el pseudo-código que usé, tendrá que adaptarlo para trabajar con texto en lugar de imágenes, pero los principios debe ser el mismo.

//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)

Tengo este código de alguna parte, pero no puedo desenterrar el enlace.

De manera informal

entropía es la disponibilidad de la información o del conocimiento, la falta de información se lleva a dificultades en la predicción del futuro, que es alta entropía (Predicción de palabra en la minería de texto) y la disponibilidad de la información / conocimiento nos ayudará predicción más realista de futuro (baja entropía).

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

Formalmente

entropía es la falta de orden de predicabilidad

A medida que se está leyendo un libro sobre NLTK sería interesante leer acerca de MaxEnt clasificador Módulo 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: pre-procesamiento (tokenización, al vapor, la selección de características con ganancia de información ...), la transformación a numérico (frecuencia o TF-IDF) (creo que este es el paso clave para entender cuando se utiliza el texto como entrada a un algoritmo que sólo aceptan numérico) y luego clasificar con MaxEnt, seguro de que esto es sólo un ejemplo.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow