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 por la probabilidad de registro de esa misma etiqueta

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

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 aprender a clasificar los nombres de pila en grupos de hombres / mujeres. Se le da una lista de nombres etiquetados con mo con f, o queremos aprender un modelo 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 decidir qué características 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 á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 a la izquierda o derecha dependiendo del resultado de la prueba. Seguimos atravesando el árbol hasta llegar a un nodo hoja que contiene la predicción de clase ( mo f)

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

El árbol de decisión se construye de arriba hacia abajo , pero la pregunta es cómo elegir qué atributo dividir en cada nodo. La respuesta es encontrar la característica 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 información . Representa la cantidad esperada de información que se necesitaría para especificar si una nueva instancia (nombre) debe 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.

La entropía, por otro lado, es una medida de impureza (lo contrario). Se define para una clase binaria con valoresa/bas:

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

Esta función de entropía binaria se representa 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.5o de manera similar, p(X=b)=0.5tiene un 50% / 50% de posibilidades de ser ao b(la incertidumbre es máxima). La función de entropía está en cero mínimo cuando la probabilidad es p=1o p=0con certeza completa ( p(X=a)=1o p(X=a)=0respectivamente, esto último implica p(X=b)=1).

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

(el logen la fórmula generalmente se toma como el logaritmo de 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/14y 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

Luego 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, 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 usando el número de instancias hacia abajo de cada rama como factor de peso (7 instancias fueron a la izquierda y 7 instancias a la derecha), y obtenemos 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 cuánta información obtuvimos al hacer la división usando esa característica particular:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Puede interpretar el cálculo anterior de la siguiente manera: al dividir con la end-vowelsfunción, pudimos reducir la incertidumbre en el resultado de la predicción del subárbol en una pequeña cantidad de 0.1518 (medido 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 una manera codiciosa (favoreciendo así las características que producen divisiones puras con baja incertidumbre / entropía). Este proceso se aplica de forma recursiva 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 omití algunos detalles que están más allá del alcance de esta publicación, incluido cómo manejar características numéricas , valores faltantes , sobreajustar y podar árboles, etc.

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

¿Cómo hacemos measurela información?

Cuando sucede algo poco probable, decimos que es una gran noticia. Además, cuando decimos algo predecible, no es realmente interesante. Para cuantificar esto 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 debería dar un número alto
• si ocurren 0.5 eventos de probabilidad, da one bitinformació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á adentro bit, la misma computadora de bit usa. 0 o 1.

Ejemplo 1

Lanzamiento de moneda justo:

¿Cuánta información podemos obtener de un lanzamiento de moneda?

Responder : -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 ~ 1entonces es 0 bit de información.

Entropía

Entonces, si asumimos la expectativa interesting-nessde 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 todo el registro.

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

Supongamos que tenemos un canal de información, como una luz que parpadea una vez al día en rojo o verde. ¿Cuánta información transmite? La primera suposición podría ser un bit por día. Pero, ¿qué pasa si agregamos azul, para que el remitente tenga tres opciones? Nos gustaría tener una medida de la información que pueda manejar cosas que no sean potencias de dos, pero aún así ser 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 apagado (esto es de conocimiento común) de modo que la lámpara siempre debe parpadear en verde. El canal ahora es inútil, sabemos cuál será el próximo flashasí que los flashes no transmiten información ni noticias. Ahora reparamos la bombilla pero imponemos una regla de que la bombilla roja no parpadee dos veces seguidas. Cuando la lámpara parpadea en rojo, sabemos cuál será el próximo parpadeo. Si intenta enviar un flujo de bits por este canal, encontrará que debe codificarlo con más flashes de los que tiene (50% más, de hecho). Y si desea describir una secuencia de flashes, puede hacerlo con menos bits. Lo mismo se aplica si cada destello es independiente (sin contexto), pero los destellos verdes son más comunes que los rojos: cuanto más sesgada sea la probabilidad, menos bits necesitará para describir la secuencia, y menos información contiene, hasta el final Límite totalmente verde, con bombilla fundida.

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 se} vuelve 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 sabemos las probabilidades), entonces 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 instante.

Bombilla roja quemada: p rojo = 0, p verde = 1, I = - (0 + 0) = 0
Equipable rojo y verde: p rojo = 1/2, p verde = 1/2 , I = - (2 * 1/2 * log (1/2)) = log (2)
Tres colores, equipables: p i = 1/3, I = - (3 * 1/3 * log (1/3)) = log (3)
Verde y rojo, verde dos veces más probable: p rojo = 1/3 , p verde = 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áximo cuando los diferentes símbolos son equiprobables. Si eres un físico, usas el registro natural, si eres un científico de la computación, usas el registro ₂ y obtienes bits.

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

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

Esos métodos de inferencia son realmente mucho más generales que solo la minería de texto y realmente no puedo imaginar cómo uno aprendería 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 Machine Learning y MaxEnt bayesian métodos.

La conexión entre la entropía y la teoría de la probabilidad con el procesamiento y almacenamiento de la información es muy, muy profunda. Para probarlo, hay un teorema debido a Shannon que establece que la cantidad máxima de información que puede pasar sin error 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 un dato 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 los conceptos básicos sobre qué es la entropía, cómo se calcula, cuál es su relación con la información y la inferencia, etc. ...

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

Este es el pseudocódigo que utilicé, deberá adaptarlo para que funcione 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 alguna parte, pero no puedo desenterrar el enlace.

Informalmente

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

La información relevante de cualquier tipo 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 oración o la palabra "carne" no está presente. Esto se llama ganancia de información

Formalmente

la entropía es la falta de orden de predecibilidad

Mientras lee un libro sobre NLTK, sería interesante que leyera 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, transmisión al vapor, selección de funciones con ganancia de información ...), 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 se clasifica con MaxEnt, seguro que esto es solo un ejemplo.