Релаксация Канторовича и расстояние Вассерштейна

1942 год. Блокадный Ленинград. Канторович решает задачу о распределении ресурсов - и по пути изобретает инструмент, который в 2017-м починит GAN. Wasserstein GAN за 4 страницы решил главную проблему генеративных сетей - mode collapse - заменив KL-дивергенцию одним математическим примитивом. Число-шок: KL-дивергенция между двумя точечными массами в разных точках равна бесконечности. Расстояние Вассерштейна - просто расстоянию между ними. Это не технический нюанс. Это другая геометрия мира.

• **WGAN (Arjovsky, 2017)**: замена JS-дивергенции на $W_1$ устранила mode collapse в GAN-обучении. Stable Diffusion, DALL-E - потомки этого открытия.
• **Flow matching (Lipman, 2022)**: FLUX, Stable Diffusion 3 используют OT-пути из Wasserstein-геометрии для прямого обучения генеративных потоков без диффузионных шагов.
• **Domain adaptation**: Wasserstein измеряет сдвиг распределений между доменами (source/target). DANN и аналоги минимизируют $W_p$ для выравнивания признакового пространства.
• **Облака точек**: сравнение 3D-объектов в PointNet++ и NeRF через Chamfer distance - аппроксимация Wasserstein для облаков точек. Применяется в робототехнике и LIDAR.
• **Sinkhorn в deep learning**: GeomLoss от Feydy реализует дифференцируемый $W_p$ на GPU через энтропийную регуляризацию - потеря Wasserstein как loss-функция в нейросетях.

Предварительные знания

• Задача Монжа: перемещение горы с минимальной работой

От карт к планам: идея coupling

1942 год. Блокадный Ленинград. Леонид Канторович, 30-летний математик, работает над задачей распределения ресурсов в условиях дефицита. Монж в 1781 году поставил задачу: найти карту $T$, которая переносит каждый «ком земли» точно в одну точку назначения. Жёстко. Детерминировано. Канторович спрашивает: а что если позволить делить?

Вот где Монж ломается. Два завода $\{A, B\}$ с единичными запасами, два склада $\{C, D\}$ с единичным спросом. Карта Монжа должна отправить $A \to C$ или $A \to D$, и $B$ - в оставшийся. Но что если оптимально отправить половину груза $A$ в $C$ и половину в $D$? Карта это не умеет - она функция, не мера.

**Канторовский сдвиг парадигмы**: вместо транспортной карты $T: X \to Y$ ищется **транспортный план** - совместная вероятностная мера $\gamma$ на $X \times Y$. Её маргинали должны совпадать с исходными мерами: $\gamma(A \times Y) = \mu(A)$ и $\gamma(X \times B) = \nu(B)$. Множество всех таких мер обозначают $\Gamma(\mu, \nu)$.

Транспортный план $\gamma(x, y)$ - это матрица потоков: $\gamma(x, y) d x d y$ - «сколько массы» из $x$ отправляется в $y$. Для дискретного случая это просто матрица $P_{ij} \geq 0$ с суммами строк $\mu_i$ и суммами столбцов $\nu_j$. Такие матрицы называют **дважды стохастическими** (с поправкой на нормировку). В линейном программировании это политоп - компактное выпуклое множество. Минимум на компакте всегда достигается.

Ключевой факт: любая карта Монжа $T$ порождает канторовский план $\gamma_T = (id, T)_\# \mu$ - «детерминированный план» с массой, сосредоточенной на графике $T$. Но не любой план является картой. Канторович строго обобщает Монжа: $\min_{\text{Monge}} \geq \min_{\text{Kantorovich}}$.

Расстояние Вассерштейна: геометрия мер

KL-дивергенция между $\delta_0$ и $\delta_1$ равна бесконечности. Расстояние Вассерштейна между ними равно 1 - просто расстоянию между точками. Это не мелочь. Это фундаментальная разница в том, что считается «близостью» распределений.

**Расстояние Вассерштейна-p** ($W_p$): минимальная стоимость транспортировки по всем допустимым планам: $$W_p(\mu, \nu) = \left(\inf_{\gamma \in \Gamma(\mu, \nu)} \int_{X \times Y} c(x,y)^p \, d\gamma(x,y)\right)^{1/p}$$ Где $c(x,y)$ - стоимость единичного переноса (обычно $|x - y|$ или $|x - y|^2$). При $p=1$ это задача линейного программирования. При $p=2$ - квадратичная задача, тесно связанная с теоремой Брение.

Почему это расстояние? Три аксиомы метрики выполняются: $W_p(\mu, \nu) = 0 \Leftrightarrow \mu = \nu$, симметричность и неравенство треугольника. При этом $W_p$ метризует слабую сходимость мер - именно ту сходимость, которая нужна в теории вероятностей и ML.

В чём преимущество перед KL? Для двух гауссиан $\mathcal{N}(0,1)$ и $\mathcal{N}(100, 1)$ KL = 5000, а $W_2 \approx 100$ - просто расстояние между центрами. Если распределения не перекрываются по носителю (типичная ситуация при обучении GAN), KL бесполезна как сигнал для обратного распространения: градиент равен нулю почти везде. Wasserstein даёт осмысленный градиент даже для разнесённых распределений.

**Sliced Wasserstein**: проецировать оба распределения на случайные 1D-направления, вычислить $W_p$ для каждого (в 1D это сортировка - $O(n \log n)$), усреднить. Результат аппроксимирует $W_p$ в исходном пространстве за $O(Ln \log n)$, где $L$ - число проекций. GeomLoss в PyTorch реализует это за несколько строк.

Двойственность Канторовича: цены как потенциалы

Канторович не просто расслабил задачу Монжа - он обнаружил, что у неё есть двойственник. Прямая задача: найти оптимальный план перевозок. Двойственная задача: найти оптимальные «ценовые потенциалы». И оптимумы совпадают - сильная двойственность линейного программирования.

**Двойственность Канторовича** для $W_1$ (стоимость = расстояние): $$W_1(\mu, \nu) = \sup_{f: \text{1-Lip}} \left( \int f \, d\mu - \int f \, d\nu \right) = \sup_{\|f\|_L \leq 1} \mathbb{E}_{x \sim \mu}[f(x)] - \mathbb{E}_{y \sim \nu}[f(y)]$$ Где супремум берётся по всем 1-липшицевым функциям ($|f(x) - f(y)| \leq |x - y|$). Это формула Канторовича-Рубинштейна 1958 года.

Экономический смысл двойственной задачи элегантен. $f(x)$ - цена товара в точке $x$. Условие 1-Lipschitz означает: цены не могут расти быстрее, чем расстояние между точками (иначе выгоднее везти самому). Оптимальная $f$ - это «арбитражно справедливые цены». Разница $\mathbb{E}_\mu[f] - \mathbb{E}_\nu[f]$ - это максимальная прибыль от перепродажи - и она равна стоимости оптимального транспорта.

Именно эта двойственность лежит в основе Wasserstein GAN. В WGAN (Arjovsky et al., 2017) дискриминатор $D_\theta$ обучается аппроксимировать оптимальную 1-Lipschitz функцию $f^*$. Градиентное наказание (gradient penalty) или weight clipping обеспечивают ограничение Lipschitz. Генератор обучается минимизировать $\mathbb{E}_{x \sim p_g}[D_\theta(x)] - \mathbb{E}_{x \sim p_{data}}[D_\theta(x)]$ - то есть буквально приближает $W_1(p_g, p_{data})$. Четыре страницы статьи - и mode collapse практически исчезает.

Двойственная формулировка также открывает путь к **дифференцируемому OT**. Sinkhorn-алгоритм, регуляризуя прямую задачу энтропийным членом $\varepsilon H(\gamma)$, получает гладкое приближение $W_p$ с градиентами по параметрам распределения. GeomLoss от Feydy et al. реализует это для GPU, делая Wasserstein-loss практичным в deep learning.

Ключевые идеи

• **Relaxation Монжа**: вместо карты $T$ ищется план $\gamma \in \Gamma(\mu,\nu)$ - совместная мера с фиксированными маргиналями. Минимум всегда достигается (компактный политоп).
• **$W_p(\mu,\nu) = \left(\inf_{\gamma \in \Gamma} \int c^p \, d\gamma\right)^{1/p}$** - расстояние Вассерштейна. Метризует слабую сходимость. Конечно там, где KL = $\infty$.
• **Двойственность Канторовича**: $W_1 = \sup_{f: \text{1-Lip}} \mathbb{E}_\mu[f] - \mathbb{E}_\nu[f]$. Именно эта формула - критерий WGAN.
• **Нобелевская премия по экономике 1975**: Канторович (единственный математик) за линейное программирование и ресурсное планирование - тот же математический аппарат.

Связанные темы

Канторовичева релаксация - фундамент. Дальше строится многое:

• Двойственность Канторовича — Полная теория потенциалов и теорема Брение
• Sinkhorn-алгоритм — Энтропийная регуляризация делает Wasserstein дифференцируемым
• Wasserstein GAN — Прямое применение $W_1$ как loss для генеративных моделей
• KL-дивергенция и cross-entropy — Альтернативная метрика на распределениях - сравнение подходов

Вопросы для размышления

• Сильная двойственность LP утверждает, что минимум прямой задачи равен максимуму двойственной. Что это означает для экономической интерпретации: когда перевозчик и посредник согласятся на одну цену?
• Sinkhorn добавляет $\varepsilon H(\gamma)$ к стоимости транспорта. При $\varepsilon \to 0$ получается точный Wasserstein. При $\varepsilon \to \infty$ - что-то другое. Какое распределение $\gamma$ максимизирует энтропию при фиксированных маргиналях?
• WGAN требует, чтобы дискриминатор был 1-Lipschitz. Weight clipping обрезает веса в $[-c, c]$. Почему это приближает 1-Lipschitz? Какова принципиальная проблема этого подхода и почему gradient penalty лучше?

Связанные уроки

• ot-05-dual — Двойственность Канторовича: Lipschitz-функции как цены
• ot-04-sinkhorn — Sinkhorn регуляризует Wasserstein, делая его дифференцируемым
• ot-07-wgan — WGAN использует W1 как loss вместо JS-дивергенции
• it-03 — KL-дивергенция vs Wasserstein: два разных способа мерить близость мер
• ot-01-monge — Задача Монжа - жёсткая версия, которую Канторович обобщает
• calc-01-sequences