Fundamentos del aprendizaje automático (parte 3)

Teoría de la información

Introducción

Esta es la parte 3 de una serie de temas que considero fundamentales para el aprendizaje automático. Estos temas actúan como bloques de construcción para obtener una comprensión más profunda del campo. Hasta ahora hemos cubierto:

1. Teoría de la probabilidad
2. Estimación de probabilidad máxima

El propósito de este post es cubrir conceptos importantes de la teoría de la información y describir cómo se utilizan en el aprendizaje automático. Muchos de los temas aquí se basarán en los conceptos que discutimos en la publicación Teoría de la probabilidad, como la independencia y la expectativa.

Motivaré y construiré estos conceptos utilizando ideas del aprendizaje automático y las estadísticas. Si tiene experiencia en Física, puede haber visto estos conceptos motivados de manera diferente (es decir, a través de la termodinámica).

Información

Motivemos nuestra discusión asumiendo que nuestro objetivo es detectar al autor de un texto dado con las palabras que son usados. ¿Qué palabras son útiles para detectar la autoría? Intuitivamente, las palabras como “el”, “o”, y “esto” no serán muy útiles, porque esas palabras tienen una alta probabilidad de aparecer en cualquier texto, independientemente del autor. Parece que las palabras comunes contienen menos información que las palabras raras, y que el contenido de la información está de alguna manera directamente relacionado con la probabilidad.

Hagamos que esto sea más formal al permitir que x sea una variable aleatoria que representa todas las palabras posibles, y p ( x ) es la probabilidad de observar una palabra específica x . Nos gustaría crear una noción cuantificable para la información obtenida al observar una palabra específica.

Usaremos h ( x ) para representar la información obtenida al observar la palabra x . De manera similar, para dos palabras x y y podríamos escribir la información obtenida al observarlas juntas como h ( x, y ). Nuestro objetivo es encontrar un adecuado h .

Primero, consideremos la independencia de dos palabras x y y . Palabras como “fútbol” y “puntuación” no son independientes, ya que ver uno hace que el otro sea más probable. Por lo tanto, la información obtenida al ver “puntaje” después de “fútbol” debe ser pequeña. Recuerde de Parte 1 que independencia significa formalmente que p ( x, y ) = p ( x ) p ( y ). Si dos palabras x y y no están relacionadas, queremos h ( x, y ) = h ( x) + h ( y ). En otras palabras, la información obtenida al ver dos palabras no relacionadas juntas debe ser la suma de la información obtenida al verlas a ambas solas.

Queremos que nuestra fórmula para h esté relacionada con p , pero tenemos este problema donde la probabilidad conjunta de observaciones independientes es un producto, pero la información conjunta es una suma. Para resolver este problema, usamos la regla del producto de logaritmos para convertir el producto en una suma:

log [ p ( x, y )] = log [ p ( x ) p ( y )] = log p ( x ) + log p ( y ).

Relacionar la información con el registro de la probabilidad parece ser el truco que necesitábamos. Escribimos la información asociada con x como:

Esta fórmula cumple con los requisitos de que las observaciones más probables produzcan menos información, y para dos observaciones independientes x y y tenemos h ( x, y ) = -log p ( x, y ) = -log [ p ( x ) p ( y )] = = -log p ([19459017)] x )] + [-log p ( y )] = h ( x ) + h ( y ).

La ​​base del logaritmo es una opción arbitraria. Los teóricos de la información generalmente usan la base 2 y llaman a las unidades de información “bits”, mientras que en el aprendizaje automático es común usar la base e y llamar a las unidades de información “nats”. Una vista alternativa de esta cantidad de información es que h ( x ) nos da el número de bits (si la base 2) es necesario para enviar un mensaje x dado algunos codificación .

Entropía

Acabamos de anotar información en función de una variable aleatoria. En Parte 1 aprendimos que la expectativa de una función g en una variable aleatoria x, nos da el valor esperado (o promedio) de g:

La expectativa de nuestra función de información h es uno de los conceptos más fundamentales en la teoría de la información. Esta expectativa se denomina entropía de la variable aleatoria x y a menudo se representa con una H mayúscula:

La entropía es el valor esperado de la función de información, o en otras palabras, es la cantidad promedio de información obtenida al observar un sorteo aleatorio de p ( x ). ¡Este es un valor útil para saber!

Un teórico de la información podría usar la entropía para calcular el número esperado de bits necesarios para transmitir un mensaje de una longitud determinada. Mejor aún, para reducir el costo de transmisión, sería beneficioso encontrar una codificación de mensajes que minimice la entropía. Esto permitiría a un transmisor comprimir mensajes y enviar menos bits por mensaje.

Encontrar una codificación eficiente es similar a encontrar una representación eficiente de características para un problema de aprendizaje automático. Nos gustaría representar nuestros datos con la menor cantidad de funciones posibles (para evitar el sobreajuste y la maldición de la dimensionalidad) y al mismo tiempo mantener la información suficiente para tomar decisiones precisas.

Veremos que esta noción de entropía será útil para pensando en varias otras ideas importantes.

Cross Entropy

Volvamos a nuestro problema de clasificación de autores. Simplifiquemos el problema considerando solo dos clases: {el texto es del autor A, el texto no es del autor A}. Trataremos cada documento que tratemos de clasificar como una “bolsa de palabras”, lo que significa que no nos importa el orden de las palabras, solo cuáles están presentes. Representamos cada documento como un vector x donde la entrada j es un 1 si la palabra j está presente en el documento, y 0 en caso contrario.

Suponemos que hay alguna distribución de la verdad fundamental p ( x ) que nos da la probabilidad de que el documento x haya sido escrito por el autor A. Si podemos aprender esta distribución, entonces para cualquier documento donde p ( x )> 0.5, podemos adivinar que el documento fue escrito por A.

Pero no sabemos p , en lugar de eso, escribimos un modelo q y tratamos de ajustar los parámetros de q para que se aproxime a p. Luego usaremos q para tomar decisiones sobre si A es el autor de un texto dado.

Ya que estamos usando q la cantidad de información necesaria para La clasificación de un documento x es h ( x ) = -log q ( x ). Pero si x se distribuye en realidad por p entonces la expectativa de la información necesaria con respecto a x es:

Esto es la entropía cruzada de q con respecto a una distribución real p . Si usamos esto como una función de costo y encontramos los parámetros de q que minimizan la entropía cruzada, la mejor solución se producirá cuando q sea idéntico a p

Minimizar la entropía cruzada es a menudo el objetivo de la regresión logística y las redes neuronales utilizadas para la clasificación. Se puede demostrar que minimizar la entropía cruzada es equivalente a maximizar la probabilidad de nuestro modelo q. Por lo tanto, este enfoque para resolver la clasificación encuentra el Estimador de Probabilidad Máxima como se describe en Parte 2 .

Entropía relativa (KL-Divergencia)

La entropía cruzada nos da la cantidad promedio de información Necesitamos clasificar nuestros documentos dado que estamos usando q en lugar de p . Obviamente, si estamos usando p, entonces en promedio solo necesitaríamos H (x) cantidad de bits (la entropía de la distribución real). Pero ya que estamos usando q toma H ( p, q ) bits en promedio (la entropía cruzada).

¿Cuánto peor es el uso de q ? Utilizar q en lugar de p requiere H ( p, q ) – H (x) bits adicionales. Llamamos a este valor la entropía relativa o divergencia de Kullback-Leibler (KL). Si conectamos las ecuaciones de entropía cruzada y entropía y luego recopilamos los términos, obtendremos que KL-Divergence es:

Nuevamente, esto nos da el número extra de bits (o nats) necesarios dado que estamos usando q en lugar de p . La divergencia KL siempre es mayor que 0 a menos que q sea igual a p . Por lo tanto, también es una función objetivo común para minimizar. Minimizar la KL-Divergencia también minimiza la entropía cruzada, que ya hemos dicho que es el Estimador de Probabilidad Máxima.

Información mutua

Anteriormente, comentamos que algunas palabras no son independientes entre sí y que la dependencia causa que obtengamos información redundante cuando los observamos a ambos (“fútbol” y “puntuación”, por ejemplo). Nos gustaría una cierta medida de cuánta información comparten dos variables.

Recuerde, que si x y y son ​​variables independientes, entonces su distribución conjunta es p ( x, y) = p (x) p (y). Si no son independientes, entonces no podemos factorizar la distribución conjunta de esta manera. No tenemos ninguna redundancia cuando las variables son independientes y, a medida que las variables se vuelven más dependientes, la cantidad de información redundante aumenta. Para cuantificar esto, usamos la información mutua de xey:

La información mutua es la cantidad de información adicional necesaria si estamos representando la verdadera distribución conjunta con la factorización independiente. Si las variables son independientes, entonces KL-Divergence será 0, de lo contrario, aumentará a medida que las variables aumenten en la redundancia.

La ​​información mutua se ha utilizado con frecuencia para realizar la selección de características en el aprendizaje automático. Para una característica determinada, podemos medir la información mutua de la entidad con las etiquetas de clase. Si la información mutua es alta, entonces la característica es un indicador fuerte de la clase. Por ejemplo, si el autor A siempre incluye su nombre en sus documentos, entonces la información mutua entre su nombre y la clase será extremadamente alta.

De manera similar, si tenemos demasiadas funciones que considerar, podemos usar información mutua entre las funciones. para eliminar los que son redundantes. Si el autor A siempre incluye su nombre y su ciudad natal, entonces podemos eliminar con seguridad su ciudad natal de nuestro vocabulario y seguir desempeñándonos bien en la tarea.

Conclusión

En esta publicación, hemos cubierto los conceptos principales de Teoría de la información directamente aplicable al aprendizaje automático. Este no ha sido un tratamiento exhaustivo en ningún sentido, pero estos son conceptos que personalmente he visto surgir una y otra vez en la práctica.

Para más información, sugiero revisar el libro de Christopher Bishop Reconocimiento de patrones y aprendizaje automático . El libro completo es una mina de oro del conocimiento, pero los conceptos que he discutido se pueden encontrar en el Capítulo 1 en la sección de teoría de la información.

Libro de David MacKay Teoría de la información, Inferencia y Algoritmos de aprendizaje también es muy popular.

¡Nos vemos la próxima vez!

Fundamentos del aprendizaje automático (Parte 3) se publicó originalmente en Hacia la ciencia de datos en Medio, donde la gente continúa la conversación Destacando y respondiendo a esta historia.