🧮 Computational Mathematics

Inicio · Parte 17 — Frontera matemática para IA e investigación

346 — Optimal transport

frontera-investigacion clase 6 de 20 4 horas demostración optimal_transport

Sinkhorn convierte un problema de programación lineal en escalados alternos.

Fórmulas

min_P Σ Pᵢⱼ·Cᵢⱼ  sujeto a marginales fijas
regularizado: + ε·Σ Pᵢⱼ·log Pᵢⱼ
solución: escalados alternos de filas y columnas

Desarrollo

El transporte óptimo pregunta cuál es la forma más barata de mover una distribución de masa hasta convertirla en otra, dado un coste por unidad transportada. La formulación de Kantorovich lo plantea como un programa lineal sobre planes de transporte con marginales fijas.

Resolver ese programa lineal exactamente cuesta O(n³ log n), prohibitivo para distribuciones grandes. La aportación de Cuturi fue añadir una regularización entrópica: penalizar planes de baja entropía suaviza el problema, lo vuelve estrictamente convexo, y su solución adopta una forma que se calcula con escalados alternos de filas y columnas.

Ese algoritmo —Sinkhorn— es sencillo, paralelizable y diferenciable, lo que permite usarlo como capa dentro de una red neuronal. Esas tres propiedades juntas son las que llevaron el transporte óptimo de la matemática pura al aprendizaje automático aplicado en apenas unos años.

El parámetro ε controla el compromiso. Valores grandes dan convergencia rápida y planes muy difusos, lejos del óptimo verdadero; valores pequeños se acercan al transporte exacto pero convergen despacio y sufren problemas numéricos por desbordamiento en los exponentes. El capstone de la clase 360 mide exactamente esa convergencia.

Ejemplo trabajado

Sinkhorn entre dos distribuciones de tres átomos.

origen:  [0,4 ; 0,3 ; 0,3]
destino: [0,2 ; 0,5 ; 0,3]

matriz de coste:
  [0,5  1,5  3,0]
  [0,5  0,5  2,0]
  [1,5  0,5  1,0]

regularización ε = 0,05

plan de transporte:
  [0,200000  0,199750  0,000000]
  [0,000000  0,299813  0,000000]
  [0,000000  0,000437  0,299999]

marginales de fila: [0,399751 ; 0,299813 ; 0,300436]
coinciden con el origen                              ✓

El plan evita las celdas caras (coste 3,0 y 2,0)
y concentra la masa en las baratas.

Qué calcula el laboratorio

Transporte óptimo por Sinkhorn: coste de mover una distribución a otra.

python classes/part-17-frontera-matematica-para-ia-e-investigacion/346-optimal-transport/lab.py
compmath run 346

Salidas del laboratorio (11)

Muestra de la ejecución real

{
  "distribucion_origen": [
    0.4,
    0.3,
    0.3
  ],
  "distribucion_destino": [
    0.2,
    0.5,
    0.3
  ],
  "matriz_de_coste": [
    [
      0.5,
      1.5,
      3.0
    ],
    [
      0.5,
      0.5,
      2.0
    ],
    [
      1.5,
      0.5,
      1.0
    ]
  ],
  "regularizacion_entropica": 0.05,
  "plan_de_transporte": [
    [
      0.2,
      0.19975,
      0.0
    ],
    [
      0.0,
      0.299813,
      0.0
    ],
    [
      0.0,
      0.000437,
      0.299999
    ]
  ],
  "marginales_fila": [
    0.399751,
    0.299813,
    0.300436
  ]
}

Errores comunes

Dónde se usa

Comparación de distribuciones, adaptación de dominios, flow matching, emparejamiento de formas y análisis de datos de una sola célula.

Idea rectora de la parte

Un proceso gaussiano define una distribución sobre funciones, no sobre parámetros.

Error a evitar

Interpretar una cota teórica como predicción del error real.

Conexión con IA

Score matching fundamenta los modelos de difusión; el transporte óptimo aparece en flow matching; la teoría estadística del aprendizaje explica el scaling.

Bibliografía de la clase

Archivos de la clase

← 345 Variational inference avanzada 347 Wasserstein distance →