¿Qué es la "entropía y la ganancia de información"?
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 logarítmica 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 fácil y sencillo (visual)?
Supongo que la entropía se mencionó en el contexto de la construcción de árboles de decisión .
Para ilustrar, imaginemos la tarea de aprender a clasificar los nombres en grupos masculinos y femeninos. Se le proporciona una lista de nombres, cada uno de ellos etiquetado con o m, fqueremos aprender un modelo que se ajuste a los datos y pueda usarse 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 en 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 decisiones . Un ejemplo de á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 sobre un solo atributo, y vamos hacia la izquierda o hacia la derecha según el 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 Amro en este árbol, comenzamos probando "¿ la longitud es <7? " y la respuesta es sí , entonces bajamos por esa rama. Después de la rama, la siguiente prueba "¿ el número de vocales es <3? " se evalúa nuevamente como verdadero . Esto conduce a un nodo de hoja etiquetado my, por lo tanto, la predicción es masculina (que resulta que soy yo, por lo que el árbol predijo el resultado correctamente ).
El árbol de decisión está construido de arriba hacia abajo , pero la pregunta es ¿cómo se elige qué atributo dividir en cada nodo? La respuesta es encontrar la característica que mejor divida la clase objetivo en los nodos secundarios más puros posibles (es decir, nodos que no contengan una mezcla de hombres y mujeres, 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). Está definido para una clase binaria con valoresa/bcomo:
Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))
Esta función de entropía binaria se muestra en la siguiente figura (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 un mínimo de cero cuando la probabilidad es p=1o p=0con total certeza ( p(X=a)=1o p(X=a)=0respectivamente, lo ú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 logen la fórmula generalmente se toma como el logaritmo en base 2 )
Volviendo a nuestra tarea de clasificación de nombres, veamos un ejemplo. Imagínese que en algún momento durante el proceso de construcción del árbol, estuviéramos 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 puedes ver, antes de la división teníamos 9 machos y 5 hembras, 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
A continuación lo comparamos con la entropía calculada después de considerar la división observando 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 en 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 ganancia de información , o cuánta información obtuvimos al realizar la división usando esa característica en particular:
Information_Gain = Entropy_before - Entropy_after = 0.1518
Puede interpretar el cálculo anterior de la siguiente manera: al dividir 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 (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 voraz (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 todas 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 , sobreajuste y poda de árboles, etc.
Para empezar, lo mejor sería entenderlo the measure of information.
¿Cómo obtenemos measurela información?
Cuando sucede algo improbable, decimos que es una gran noticia. Además, cuando decimos algo predecible, no es realmente interesante. Entonces, 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 ocurre un evento con probabilidad de 0,5, proporciona
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á en bit, el mismo bit que usa la computadora. 0 o 1.
Ejemplo 1
Lanzamiento de moneda justo:
¿Cuánta información podemos obtener al lanzar una moneda?
Respuesta :-log(p) = -log(1/2) = 1 (bit)
Ejemplo 2
Si mañana un meteorito choca contra la Tierra, p=2^{-22}podremos obtener 22 bits de información.
Si el sol sale mañana, p ~ 1entonces es 0 bit de información.
entropía
Entonces, si tomamos la expectativa de interesting-nessun evento Y, entonces es la entropía. es decir, la entropía es un valor esperado del interés 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)
Registro base 2 para todos los registros.
No puedo darte gráficos, pero tal vez pueda dar 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 estimación podría ser un bit por día. Pero ¿y si añadimos azul, para que el remitente tenga tres opciones? Nos gustaría tener una medida de información que pueda manejar cosas distintas a potencias de dos, pero que aún sea aditiva (la forma en que multiplicar el número de mensajes posibles por dos suma un bit). Podríamos hacer esto tomando el registro 2 (número de mensajes posibles), pero resulta que hay una forma más general.
Supongamos que volvemos al rojo/verde, pero la bombilla roja se ha quemado (esto es de conocimiento común), por lo que la lámpara siempre debe parpadear en verde. El canal ahora es inútil, sabemos cuál será el próximo destello, por lo que los destellos no transmiten información ni noticias. Ahora reparamos la bombilla pero imponemos la regla de que la bombilla roja no puede parpadear dos veces seguidas. Cuando la lámpara parpadea en rojo, sabemos cuál será el próximo destello. Si intentas enviar un flujo de bits por este canal, encontrarás que debes codificarlo con más flashes que bits tienes (un 50% más, de hecho). Y si desea describir una secuencia de destellos, puede hacerlo con menos bits. Lo mismo se aplica si cada destello es independiente (libre de contexto), pero los destellos verdes son más comunes que los rojos: cuanto más sesgada es la probabilidad, menos bits necesitará para describir la secuencia y menos información contiene, hasta el final. todo verde, límite de bombilla fundida.
Resulta que hay una manera de medir la cantidad de información en una señal, basándose en 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 dos veces más 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 conocemos 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 fundida: p rojo = 0, p verde =1, I = -(0 + 0) = 0 Equiprobable rojo y verde: p rojo = 1/2, p verde = 1/2 , I = -(2 * 1/2 * log(1/2)) = log(2) Tres colores, equiprobable: 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 registro(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 físico, usas el registro natural, si eres informático, usas el registro 2 y obtienes bits.
Realmente recomiendo leer sobre Teoría de la Información, 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 en realidad mucho más generales que la simple minería de texto y realmente no puedo imaginar cómo uno podría aprender a 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 MaxEnt bayesiano. métodos.
La conexión entre la entropía y la teoría de la probabilidad con el procesamiento y almacenamiento de información es realmente profunda. Para darnos una idea, hay un teorema de Shannon que establece que la cantidad máxima de información que se 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 puedes comprimir un dato para ocupar la mínima memoria posible en tu computadora con la entropía del proceso que generó los datos.
No creo que sea realmente necesario que aprendas 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. ...
