🧮 Computational Mathematics

Inicio · Parte 14 — Matemática de Machine Learning

296 — EM algorithm

ml-avanzado clase 16 de 20 4 horas demostración em_algorithm

EM alterna estimar lo latente y optimizar los parámetros, y la verosimilitud nunca baja.

Fórmulas

E-step: estimar la distribución de las latentes dados los parámetros
M-step: maximizar los parámetros dada esa distribución
garantía: la log-verosimilitud crece o se mantiene

Desarrollo

El algoritmo EM resuelve un problema circular: para estimar los parámetros haría falta saber qué componente generó cada dato, y para saberlo haría falta conocer los parámetros. La salida es alternar, empezando por una suposición cualquiera y refinando ambas cosas por turnos.

El paso E calcula, con los parámetros actuales, la distribución de probabilidad de las variables latentes. El paso M toma esas asignaciones blandas como si fueran datos ponderados y maximiza los parámetros. Se repite hasta que deja de haber cambio apreciable.

La garantía teórica es que la log-verosimilitud nunca decrece. La demostración construye una cota inferior que toca la verosimilitud en el punto actual y se maximiza en cada paso; esa cota es el ELBO, el mismo objeto que optimiza un autoencoder variacional. Ver EM primero hace que el ELBO de la parte 17 deje de parecer una construcción arbitraria.

Lo que no garantiza es alcanzar el óptimo global: converge a un óptimo local que depende de la inicialización, igual que k-means. Y puede ser lento cerca del óptimo. Su valor está en la generalidad: sirve para GMM, para modelos ocultos de Markov, para datos faltantes y para cualquier modelo con estructura latente.

Ejemplo trabajado

Dos monedas con sesgos desconocidos, sin saber cuál se usó.

20 tandas de 10 lanzamientos cada una
sesgos reales:    [0,80 ; 0,30]
inicialización:   [0,60 ; 0,40]

iteración    p_A        p_B
    1      0,726455   0,428502
    5      0,8xxxxx   0,4xxxxx
  final    0,848956   0,451121

Sin saber nunca qué moneda generó cada tanda,
EM recupera aproximadamente los dos sesgos.

El error residual viene de los datos finitos:
20 tandas no bastan para separar perfectamente.
La log-verosimilitud creció en cada iteración.   ✓

Qué calcula el laboratorio

EM: E-step y M-step sobre datos con una variable latente.

python classes/part-14-matematica-de-machine-learning/296-em-algorithm/lab.py
compmath run 296

Salidas del laboratorio (9)

Muestra de la ejecución real

{
  "tandas": 20,
  "lanzamientos_por_tanda": 10,
  "sesgos_reales": [
    0.8,
    0.3
  ],
  "inicializacion": [
    0.6,
    0.4
  ],
  "historial": [
    {
      "iter": 1,
      "p_A": 0.726455,
      "p_B": 0.428502
    },
    {
      "iter": 5,
      "p_A": 0.838551,
      "p_B": 0.445235
    },
    {
      "iter": 20,
      "p_A": 0.848954,
      "p_B": 0.45112
    },
    {
      "iter": 40,
      "p_A": 0.848956,
      "p_B": 0.451121
    }
  ],
  "estimacion_final": [
    0.848956,
    0.451121
  ]
}

Errores comunes

Dónde se usa

Ajuste de GMM, modelos ocultos de Markov, imputación de datos faltantes, topic models y base conceptual de la inferencia variacional.

Idea rectora de la parte

Cada algoritmo es un objetivo más un método de optimización; nada más.

Error a evitar

No estandarizar antes de aplicar regularización o k-NN.

Conexión con IA

Estos algoritmos siguen siendo la línea base honesta contra la que se debe comparar cualquier modelo profundo.

Bibliografía de la clase

Archivos de la clase

← 295 Gaussian Mixture Models 297 PCA aplicado a ML →