Оптимальный транспорт
Расстояния Вассерштейна
WGAN (2017) был первым GAN, стабильно обучавшимся без mode collapse - именно благодаря W₁. Алгоритм Синхорна позволил дифференцировать через OT на GPU, открыв эпоху differentiable OT в deep learning.
- **WGAN-GP (Gulrajani 2017):** gradient penalty для Lipschitz constraint. Стандарт для high-resolution GAN до эпохи диффузии.
- **POT library:** Python Optimal Transport - scipy-style API для Sinkhorn, LP, слайсированного OT. 1M+ downloads/month.
- **GeomLoss (Feydy 2019):** GPU-ускоренные Sinkhorn divergences для point clouds. Используется в 3D shape matching.
Задача Канторовича: определение W_p
**Wasserstein GAN (WGAN, 2017) использует W₁ расстояние вместо JS-дивергенции - устраняет mode collapse, стабилизирует обучение для генерации 1024×1024 изображений.** Ключевой вопрос: как формально измерить расстояние между двумя вероятностными мерами?
W_p задаёт метрику на пространстве вероятностных мер с конечным p-м моментом. При p=2 это риманова метрика на бесконечномерном пространстве - основа для геодезик и gradient flows.
Чему равно W₁(δ₀, δ₁) - расстояние между двумя атомарными мерами в точках 0 и 1?
W₁(δ₀, δ₁) = |0−1| = 1: нужно переместить всю единицу массы на расстояние 1.
Двойственность Канторовича: 1-Lipschitz функции
Прямая задача (инфимум по планам) вычислительно дорогая для непрерывных мер. **Двойственность Канторовича-Рубинштейна** переформулирует W₁ как супремум по функциям - именно это используется в WGAN для обучения critic.
Gradient penalty в WGAN-GP (Gulrajani 2017): штрафовать ‖∇f(x̂)‖₂ ≠ 1 на интерполяции x̂ = αx_real + (1−α)x_fake. Это мягкое ограничение Lipschitz стабильнее weight clipping.
Какое ограничение накладывает WGAN на critic (дискриминатор)?
По двойственности Канторовича-Рубинштейна супремум берётся по 1-Lipschitz функциям. WGAN обеспечивает это через weight clipping или gradient penalty.
Алгоритм Синхорна: быстрое вычисление OT
Решение задачи Канторовича через LP имеет сложность O(n³). **Энтропийная регуляризация** (Cuturi 2013) добавляет −εH(γ) к функционалу и даёт замкнутое решение через итерации Синхорна - O(n²) на итерацию, GPU-параллелизуемо.
При ε→0 регуляризованное решение сходится к точному OT. На практике ε = 0.05 - 0.5 даёт хорошее приближение за 50 - 200 итераций. Sinkhorn реализован в POT, GeomLoss, OTT-JAX (GPU).
Что происходит при ε→0 в алгоритме Синхорна?
При ε→0 энтропийная регуляризация исчезает и регуляризованное решение сходится к оптимальному плану задачи Канторовича.
Ключевые идеи
- **W_p distance:** инфимум стоимости транспорта ∫∫|x−y|^p dγ по всем планам γ∈Π(μ,ν).
- **Двойственность K-R:** W₁ = sup_{‖f‖_L≤1} [∫f dμ − ∫f dν]. WGAN обучает critic как 1-Lipschitz функцию.
- **Sinkhorn:** добавить −εH(γ), оптимум γ*=diag(u)Kdiag(v). Итерации u←μ/(Kv), v←ν/(Kᵀu). O(n²) per iter.
- **ε→0:** регуляризованное OT → точное OT. Компромисс: малый ε = точность, большой ε = скорость.
Связанные уроки
- ot-17-applications — Продолжает тему применений OT
- ot-07-wgan — WGAN использует W1 через двойственность