La entropía en Ciencia de Datos (y la compresión)
En concepto de entropía es fundamental en la ciencia de datos. Sin ella no podríamos utilizar conceptos tan importantes como la función de ganancia de los árboles de decisión los cuales son uno de los modelos más interpretables y utilizados en Ciencia de Datos. Como otro ejemplo donde la entropía es muy importante existe una función de entrenamiento llamada entropía cruzada que es enormemente utilizada en redes neuronales profundas.
El objetivo de este texto es invitar a nuestra comunidad a estudiar los fundamentos de la entropía la cual es indispensable para entender además la teoría de la compresión la cual es la base de los métodos matemáticos para codificar la información.
Entropía de Shannon y sus Aplicaciones en Machine Learning
La teoría de la información se puede dividir en dos vertientes principales, cada una consecuencia de un punto de vista distinto. Una es la de Kolmogorov, que consiste en estudiar la información mediante la complejidad de un programa de computadora capaz de reproducirla. La otra, que estudiaremos aquí, es la de Claude Shannon, quien analizó la interacción entre un emisor y un receptor de un mensaje.
La teoría de la información según Shannon parte de una hipótesis fundamental: el mensaje es un experimento dentro de una experiencia aleatoria, es decir, puede considerarse como una variable aleatoria o un espacio de probabilidad.
Ejemplo: Codificación de un alfabeto
Supongamos que tenemos un alfabeto con 4 letras: ω₁, ω₂, ω₃, ω₄. Queremos representarlas de manera binaria. Consideremos dos maneras:
ω₁ → 00, ω₂ → 01, ω₃ → 10, ω₄ → 11
ω₁ → 1, ω₂ → 10, ω₃ → 100, ω₄ → 1000
Ingenuamente pensaríamos que lo mejor es utilizar el menor número de dígitos posibles sin embargo esto no siempre es cierto.
Consideremos ahora dos casos de frecuencia con que ocurren las letras. En el primer caso todas son equiprobables. En el segundo, supongamos que las probabilidades son:
P(ω₁) = 1/2
P(ω₂) = 1/4
P(ω₃) = P(ω₄) = 1/8
¿Cuántos dígitos, en promedio, se necesitan para representar las letras binariamente en cada caso? ¿Cuál forma es mejor?
La teoría de la información de Shannon contesta precisamente a esta pregunta utilizando el concepto de entropía.
Entropía Combinatoria
Comenzaremos a formalizar el concepto de entropía, el cual tiene orígenes en la física. Esto nos ayudará a comprender lo observado en el ejemplo anterior. Empezamos con el caso equiprobable.
Pensemos en un conjunto Ω. Si elegimos cualquier elemento, queremos cuantificar la cantidad de información necesaria para transmitir el mensaje: “tal elemento ha sido elegido”. Supondremos que el receptor no conoce nada del conjunto Ω, o al menos que Ω es tan grande que no puede memorizar todos los elementos.
Si Ω tiene dos elementos, basta con transmitir una unidad de información (un bit). Si el número de elementos es 2ⁿ, como por ejemplo Ω = {0,1}ⁿ, entonces necesitamos n instrucciones para identificar un elemento.
Definición: La entropía combinatoria de un elemento ω ∈ Ω se define como:
E_comb(ω) = log₂(|Ω|)
Para un subconjunto A ⊆ Ω, la entropía combinatoria es:
E_comb(A) = log₂(|Ω|) - log₂(|A|)
Entropía en un Espacio de Probabilidad
La definición combinatoria asume equiprobabilidad en todos los elementos del conjunto. Ahora estudiaremos conjuntos no equiprobables. Recordemos dos propiedades de los logaritmos:
log₂(|Ω|) - log₂(|A|) = log₂(|Ω| / |A|)
log₂(|Ω| / |A|) = -log₂(|A| / |Ω|)
Definición: Sea (Ω, P) un espacio de probabilidad finito con elementos {σ₁, σ₂, ..., σₙ} y pᵢ = P(σᵢ). La entropía del espacio es:
E(Ω, P) = -p₁·log₂(p₁) - ... - pₙ·log₂(pₙ)
Nota: Por convención, se toma 0·log₂(0) = 0. Notemos que esto no es una arbitrariedad pues el límite de 1/N (Log( 1/N) ) es igual a cero.
Como un caso particular si n = 2ᴺ y la probabilidad es uniforme, entonces E(Ω, P) = N.
Teorema de Shannon sobre la Compresión
La primera aplicación del concepto de entropía fue en la teoría de compresión, en particular para un problema parecido al inicio de cómo codificar un mensaje de la mejor manera posible.
Esquemas de Compresión
Uno de los primeros usos de la teoría de la información es el primer teorema de Shannon, que establece cuánta información puede comprimirse según su entropía. Pensemos en el ejemplo del inicio para elegir el alfabeto.
Definición: Sea Ω un alfabeto finito y b = {0,1}. Un código de m bits es una función:
C: Ω → bᵐ
El código es fiel si C es una función inyectiva.
Por alguna versión del principio del palomar si |Ω| = 2ⁿ, entonces existe un código de n bits y no existe uno fiel de tamaño m < n. A continuación enunciamos la definición formal de una técnica de compresión
Definición: Dado un espacio de probabilidad (Ω, P), decimos que tiene un esquema de compresión de N muestras (δ-preciso y de orden α) si existen funciones C y D tales que, para un muestreo de N elementos ω₁, ..., ω_N:
P(D(C(ω₁, ..., ω_N)) = (ω₁, ..., ω_N)) ≥ 1 - δ
Y m está entre α·n y α·n + 1
Primer Teorema de Shannon
Este teorema es uno de los resultados más importantes en matemáticas y apareció en el célebre artículo de Shannon: A Mathematical Theory of Information.
Sea (Ω, P) un espacio de probabilidad. Para cualquier 0 < α ≤ 1 y δ ∈ [0,1]:
Si E(Ω, P) > α, sólo existen finitos N tales que (Ω, P) tiene un esquema de compresión δ-preciso y orden α.
Si E(Ω, P) < α, entonces para todos los N suficientemente grandes, existe un esquema de compresión δ-preciso y orden α.
Este teorema justifica la importancia de la entropía: garantiza eficacia estadística en la compresión cuando la entropía es baja. Los códigos de Huffman alcanzan la mejor compresión teórica garantizada por Shannon.
¿Dónde aprender más sobre la entropía y sus aplicaciones?
En el Colegio de Matemáticas Bourbaki enseñamos con detalle las matemáticas y las bases para que nuestros estudiantes estén listos para aprender los modelos más avanzados de Inteligencia Artificial, Ciencia de Datos y Finanzas Cuantitativas. Estos son los dos cursos que están por comenzar y durarán todo el 2025.
Track de Ciencia de Finanzas Cuantitativas (05 de Mayo 2025, 49 semanas).
Track de Ciencia de Datos (06 de Mayo 2025, 49 semanas).