¿Puede el valor de ganancia de información ser negativo?

Question

¿Existe la posibilidad de obtener el valor de ganancia de información sea negativo? Se calcula según la fórmula en el siguiente artículo. No puedo escribir la fórmula porque incluye algunas anotaciones difíciles.

http://citeseerx.ist.psu.edu

Gracias!

Answer 1

IG(Y|X) = H(Y) - H(Y|X) >= 0, ya H(Y) >= H(Y|X) peor de los casos es que X e Y son independientes, por lo tanto H(Y|X)=H(Y)

Otra forma de pensar en ello es que mediante la observación de la variable aleatoria X toma un cierto valor, que o bien no adquieren ninguna o alguna información acerca Y (no pierdes ninguno).

---

EDITAR

Aclaro ganancia de información en el contexto de los árboles de decisión (que en realidad tenía en cuenta, en primer lugar, ya que provenía de un ambiente de aprendizaje automático).

asumir un problema de clasificación en el que dando Dado un conjunto de instancias y las etiquetas (clases discretas).

La idea de elegir qué atributo dividir por en cada nodo del árbol, es seleccionar la característica que divide el atributo de clase en los dos grupos más puros de instancias (es decir, la entropía más baja).

Esto a su vez es equivalente a elegir la función con la ganancia de información más alto desde

InfoGain = entropyBeforeSplit - entropyAfterSplit 

donde la entropía después de la división es la suma de las entropías de cada rama ponderado por el número de casos abajo esa rama.

Ahora existe ningún posible división de los valores de la clase que generarán un caso con una pureza aún peor (mayor entropía) que antes de separarse.

Tome este sencillo ejemplo de un problema de clasificación binaria. En un nodo determinado, tenemos 5 instancias positivas y 4 negativas (un total de 9). Por lo tanto, la entropía (antes de la división) es:

H([4,5]) = -4/9*lg(4/9) -5/9*lg(5/9) = 0.99107606 

Consideremos ahora algunos casos de divisiones.El mejor de los casos es que el atributo actual divide los casos perfectamente (es decir, una rama es todos positivos, el otro todos negativos):

[4+,5-] 
    / \  H([4,0],[0,5]) = 4/9*(-4/4*lg(4/4)) + 5/9*(-5/5*lg(5/5)) 
    / \      = 0   // zero entropy, perfect split 
[4+,0-] [0+,5-] 

entonces

IG = H([4,5]) - H([4,0],[0,5]) = H([4,5])  // highest possible in this case 

imaginar que el segundo atributo es el peor caso posible, donde una de las ramas creadas no tiene instancias sino todas las instancias pasan a la otra (podría suceder si, por ejemplo, el atributo es constante entre instancias, por lo tanto inútil):

[4+,5-] 
    / \  H([4,5],[0,0]) = 9/9 * H([4,5]) + 0 
    / \      = H([4,5]) // the entropy as before split 
[4+,5-] [0+,0-] 

y

IG = H([4,5]) - H([4,5],[0,0]) = 0    // lowest possible in this case 

Ahora, en algún lugar entre estos dos casos, verá cualquier número de casos como:

[4+,5-] 
    / \  H([3,2],[1,3]) = 5/9 * (-3/5*lg(3/5) -2/5*lg(2/5)) 
    / \      + 4/9 * (-1/4*lg(1/1) -3/4*lg(3/4)) 
[3+,2-] [1+,3-] 

y

IG = H([4,5]) - H([3,2],[1,3]) = [...] = 0.31331323 

así que no importa cómo dividir los 9 instancias, siempre obtiene una ganancia positiva en la información. Me doy cuenta de que esto no es una prueba matemática (¡vaya a MathOverflow para eso!), Solo pensé que un ejemplo real podría ayudar.

(Nota: Todos los cálculos según Google)

Answer 2

seguro de que puede.

ganancia de información es sólo el cambio de entropía de la información de un estado a otro:

IG (Ex, a) = H (Ex) - H (Ex | a)

Ese cambio de estado puede ir en cualquier dirección, puede ser positivo o negativo.

Esto es fácil ver por ejemplo: algoritmos de árboles de

Decision funciona así: en un nodo dado, se calcula la entropía de la información (para la variable independiente).

Puede pensarlo de esta manera: la entropía de la información es para variables categóricas/discretas, ya que la varianza es para variables continuas). La varianza, por supuesto, es solo el cuadrado de la desviación estándar. Entonces, por ejemplo, si estamos buscando predecir precios basados ​​en varios criterios, y hemos agrupado arbitrariamente nuestro conjunto de datos en dos grupos, en los cuales los precios para el grupo A son (50, 60 y 70) y los precios para el grupo B son (50, 55, 60), el grupo B tiene la varianza más baja, es decir, están muy juntos. Por supuesto, la varianza no puede ser negativa (porque después de sumar las distancias de cada punto con respecto a la media, la cuadra) pero la diferencia en varianza ciertamente puede ser.

Para ver cómo esto se relaciona con Entropía de información/Ganancia de información, supongamos que no estamos pronosticando precio sino otra cosa, como si el visitante de nuestro Sitio se convertirá en un usuario registrado o un suscriptor premium, o ninguno. La variable indepdendent aquí es discreta, no continua como el precio, por lo que no puede calcular la varianza de una manera significativa. La entropía de la información es lo que se usa en su lugar. (Si dudas sobre la estrecha analogía aquí entre varianza e IE, debes saber que la mayoría de los algoritmos de árbol de decisión son capaces de manejar variables discretas y continuas, en el último caso, el algoritmo usará la varianza como criterio de división, en lugar de usar IG.)

En cualquier caso, después de calcular la entropía de información para un nodo determinado, divide los datos en ese nodo (que es el conjunto de datos completo si se encuentra en el nodo raíz) en cada valor para cada variable, luego, para cada división, calcule el IE para ambos grupos y tome el IE promedio ponderado. A continuación, tome la división que da como resultado el IE promedio ponderado más bajo y compárelo con el nodo IE (que obviamente es solo un grupo). Si ese IE promedio ponderado para la división es inferior a IE del nodo, entonces se dividen los datos en ese nodo (formando una rama); si no, se detiene, es decir, ese nodo no puede dividirse más - Estás en la parte inferior.

En suma, en el corazón del algoritmo del árbol de decisión se encuentra el criterio para determinar si se divide un nodo, así es como se construyen. Ese criterio es si IG es positivo o negativo.

Answer 3

Para cualquier otra persona que se encuentre con esta pregunta, a pesar de su edad, ofrezco esta respuesta y consejo.

Primero, la respuesta es no, no puede ser negativo. La peor posibilidad absoluta es no cambiar, o un IG de cero. Si desea una prueba, busque la prueba completa en MathOverFlow como señaló Amro.

Ahora para el consejo. Si solo hace el primer nivel de un árbol de decisión, parece obvio que nunca resultará negativo. Sin embargo, cuando construí mi primer árbol usando Information Gain, me encontré con una ganancia negativa en mi tercera ramificación. Esto no parecía útil o posible, así que me apresuré a verificar mis cálculos. La matemática estuvo bien. La parte que tenía mal fue la primera parte de la fórmula base. Estaba usando la respuesta del nivel anterior como mi entropía inicial, pero esto es incorrecto porque incluye información de otros conjuntos de datos. ¡Debes asegurarte de que para tu entropía de inicio determina la entropía solo para esa rama! Esto significa que su "entropía inicial" podría ser mayor que en el nivel anterior a este.

En otras palabras, al calcular IG, asegúrese de que solo está utilizando el conjunto de datos actual.